Arbori Huffman si Arbori Ponderati in C++

Aici e un pic mai mult, programul contine doua clase ArboreHuffman si ArborePonderat si cu ajutorul lor realizeaza o forma foarte simpla de codificare (programul poate fi modificat pentru a fi un arhivator). Ca deobicei codul este in C++ si foloseste alocare dinamica a memoriei.

demo.cpp

// demo.cpp

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <fstream>
#include "liste.h"
#include "ArborePonderat.h"
#include "ArboreHuffman.h"

void AdaugaNodPonderatInLista(LISTA<NodPonderat*> & noduri, char * cheie)
{
	bool ok = true;
	for(int i=0; i<noduri.lungime(); i++)
		if(strcmp(cheie, noduri[i]->cheie) == 0)
		{
			ok = false;
			noduri[i]->pondere++;
		}
	if(ok)
	{
		NodPonderat* nodNou = new NodPonderat(cheie, 1);
		noduri.AdaugaInceput(nodNou);
	}
}

void AdaugaNodHuffmanInLista(LISTA<NodHuff*> & noduri, char cheie)
{
	bool ok = true;
	for(int i=0; i<noduri.lungime(); i++)
		if(cheie == noduri[i]->cheie)
		{
			ok = false;
			noduri[i]->pondere++;
		}
	if(ok)
	{
		NodHuff* nodNou = new NodHuff(cheie, 1);
		noduri.AdaugaInceput(nodNou);
	}
}


bool Citeste(LISTA<NodPonderat*> & noduri)
{
	ifstream fin("ponderat.txt", ios::in);
	if(fin.fail())
		return false;

	char buf[512];
	while(!fin.eof())
	{
		fin>>buf;
		AdaugaNodPonderatInLista(noduri, buf);
	}
	return true;
}

bool Citeste(LISTA<NodHuff*> & noduri)
{
	ifstream fin("huffman.txt", ios::in);
	if(fin.fail())
		return false;

	char c;
	while(!fin.eof())
	{
		fin>>c;
		AdaugaNodHuffmanInLista(noduri, c);
	}
	return true;
}

void main()
{
	//	ponderat
	/*
	cout<<endl<<"Ponderat: "<<endl<<endl;
	LISTA<NodPonderat*> noduriPond;
	if(!Citeste(noduriPond))
		return;

	ArborePonderat arbore;
	arbore.CreazaArbore(noduriPond);
	arbore.Nivele();
	*/

	//	huffman
	LISTA<NodHuff*> noduriHuff;
	if(!Citeste(noduriHuff))
		return;

	cout<<endl<<"Huffman: "<<endl<<endl;
	ArboreHuffman huff;
	huff.CreazaArbore(noduriHuff);
	cout<<"Arborele huffman: ";
	huff.Nivele();
	cout<<endl<<"Codurile huffman: "<<endl;
	huff.AfiseazaCod();

	char c;
	cin>>c;
}

ArboreHuffman.h

// ArboreHuffman.h
#pragma once

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include "liste.h"

using namespace std;

typedef struct NodHuff
{
	char cheie;
	int pondere;
	NodHuff *st;
	NodHuff *dr;
	NodHuff(char cheieNoua, int ponderea)	{
		cheie = cheieNoua;
		pondere = ponderea;
		st = dr = NULL;	}
}NodHuff;

class ArboreHuffman
{
private:
	NodHuff **frunze;
	NodHuff *rad;
	int nrNoduri;
	int nrElemente;

	void DetCod(NodHuff *rad, char cod[512], int poz);
public:
	ArboreHuffman(void);
	~ArboreHuffman(void);

	void Nivele();
	void CreazaArbore(LISTA<NodHuff*> & listaNoduri);
	void AfiseazaCod();
};

ArboreHuffman.cpp

// ArboreHuffman.cpp
#include "ArboreHuffman.h"

#include "ArborePonderat.h"

ArboreHuffman::ArboreHuffman(void)
{
	rad = NULL;
	frunze = NULL;
	nrElemente = nrNoduri = -1;
}

ArboreHuffman::~ArboreHuffman(void)
{
	if(frunze != NULL)
		delete []frunze;
}

void ArboreHuffman::CreazaArbore(LISTA<NodHuff*> & noduri)
{
	NodHuff *min1, *min2, *aux;
	int i;
	nrElemente = noduri.lungime();
	nrNoduri = 2*noduri.lungime() - 1;
	frunze = new NodHuff*[nrElemente];
	for(i=0; i<noduri.lungime(); i++)
		frunze[i] = noduri[i];
	while(noduri.lungime() > 1)
	{
		min1 = noduri[0];
		min2 = noduri[1];
		for(i=2; i<noduri.lungime(); i++)
			if(noduri[i]->pondere < min1->pondere)
			{
				min1 = noduri[i];
				if(min1->pondere < min2->pondere)
				{
					aux  = min1;
					min1 = min2;
					min2 = aux;
				}
			}
		//	cream un sungraf cu cele 2 noduri ca subgraf stang si drept
		aux = new NodHuff('*', min1->pondere + min2->pondere);
		aux->st = min1;
		aux->dr = min2;
		//	stergem minimele si adaugam nodul nou
		noduri.Sterge(min1);
		noduri.Sterge(min2);
		noduri.AdaugaSfarsit(aux);
	}
	//	ar trebui sa avem un singur element in lista, radacina
	rad = noduri[0];
	noduri.Sterge();
}

void ArboreHuffman::Nivele()
{
	//	verificari
	if(rad == NULL)
	{
		cout<<"Arborele e gol!\n";
		return;
	}
	//	variabile auxiliare
	NodHuff ** coada = new NodHuff*[nrNoduri];	//	retine nodurile parcurse in latime
	int *nivele = new int[nrNoduri];	//	retine nivelul pe care se afla fiecare nod
	NodHuff *x;
	int inc, sf;	//	inceputul si sfarsitul cozii
	//	initializam nivelele, coada.
	nivele[0] = 1;	//	nivelul nodurilor
	coada[0] = rad;	//	primul nod din coada
	inc = sf = 0;	//	inceputul si sfasitul cozii
	//	cata vreme avem noduri in coada
	cout<<"\nNivel 1: ";
	while(inc <= sf)
	{
		//	afisam primul nod din coada
		x = coada[inc];
		cout<<x->cheie<<" ";
		//	bagam fii ultimului nod in coada
		//	si completam nivelul nodurilor
		if(x->st)
		{
			coada[++sf] = x->st;
			nivele[sf] = nivele[inc]+1;
		}
		if(x->dr)
		{
			coada[++sf] = x->dr;
			nivele[sf] = nivele[inc]+1;
		}
		//	scoatem primul nod din coada
		inc++;
		//	afisam nivelul daca este diferit de nivelul nodului precedent
		if(nivele[inc] != nivele[inc-1] && inc <= sf)
			cout<<"\nNivel "<<nivele[inc]<<": ";
	}

	//	stergem memoria folosita pentru retinerea cozii si a nivelului nodului
	delete[] coada;
	delete[] nivele;
}

void ArboreHuffman::DetCod(NodHuff *rad, char cod[], int poz)
{
	if(rad == NULL)
		return;
	if(rad->cheie != '*')
	{
		cout<<"cheie: "<<rad->cheie<<" cod: "<<cod<<endl;
		return;
	}
	cod[poz+1] = '\0';

	cod[poz] = '0';
	DetCod(rad->st, cod, poz+1);
	cod[poz] = '1';
	DetCod(rad->dr, cod, poz+1);

	cod[poz] = '\0';
}

void ArboreHuffman::AfiseazaCod()
{
	int t = 0;
	for(int i=0; i<nrElemente; i++)
	{
		cout<<"cheia: "<<frunze[i]->cheie<<" apare de "<<frunze[i]->pondere<<endl;
		t += frunze[i]->pondere;
	}
	cout<<"total: "<<t<<endl;
	//
	char cod[512];
	cod[0] = '\0';
	DetCod(rad, cod, 0);
}

ArborePonderat.h

// ArborePonderat.h
#pragma once

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include "liste.h"

using namespace std;

typedef struct NodPonderat
{
	char *cheie;
	int pondere;
	NodPonderat *st;
	NodPonderat *dr;
	NodPonderat(char *cheieNoua, int ponderea)	{
		cheie = new char[strlen(cheieNoua)+1];
		strcpy(cheie, cheieNoua);
		pondere = ponderea;
		st = dr = NULL;	}
	~NodPonderat()	{	if(cheie)	delete []cheie;	}
}NodPonderat;

class ArborePonderat
{
private:
	NodPonderat *rad;
	int nrNoduri;
public:
	ArborePonderat(void);
	~ArborePonderat(void);

	void Nivele();
	void CreazaArbore(LISTA<NodPonderat*> & listaNoduri);
};

ArborePonderat.cpp

// ArborePonderat.cpp
#include "ArborePonderat.h"

ArborePonderat::ArborePonderat(void)
{
}

ArborePonderat::~ArborePonderat(void)
{
}

void ArborePonderat::CreazaArbore(LISTA<NodPonderat*> & noduri)
{
	NodPonderat *min1, *min2, *aux;
	int i;
	nrNoduri = 2*noduri.lungime() - 1;
	while(noduri.lungime() > 1)
	{
		for(int j=0; j<noduri.lungime(); j++)
			cout<<noduri[j]->cheie<<" ";
		cout<<endl;

		min1 = noduri[0];
		min2 = noduri[1];
		for(i=2; i<noduri.lungime(); i++)
			if(noduri[i]->pondere < min1->pondere)
			{
				//cout<<noduri[i]->cheie<<" ";
				min1 = noduri[i];
				if(min1->pondere < min2->pondere)
				{
					aux  = min1;
					min1 = min2;
					min2 = aux;
				}
			}
		//	cream un sungraf cu cele 2 noduri ca subgraf stang si drept
		char buf[512];
		strcpy(buf, min1->cheie);
		strcat(buf, min2->cheie);
		aux = new NodPonderat(buf, min1->pondere + min2->pondere);
		aux->st = min1;
		aux->dr = min2;
		//	stergem minimele si adaugam nodul nou
		noduri.Sterge(min1);
		noduri.Sterge(min2);
		noduri.AdaugaSfarsit(aux);
	}
	//	ar trebui sa avem un singur element in lista, radacina
	rad = noduri[0];
	noduri.Sterge();
}

void ArborePonderat::Nivele()
{
	//	verificari
	if(rad == NULL)
	{
		cout<<"Arborele e gol!\n";
		return;
	}
	//	variabile auxiliare
	NodPonderat ** coada = new NodPonderat*[nrNoduri];	//	retine nodurile parcurse in latime
	int *nivele = new int[nrNoduri];	//	retine nivelul pe care se afla fiecare nod
	NodPonderat *x;
	int inc, sf;	//	inceputul si sfarsitul cozii
	//	initializam nivelele, coada.
	nivele[0] = 1;	//	nivelul nodurilor
	coada[0] = rad;	//	primul nod din coada
	inc = sf = 0;	//	inceputul si sfasitul cozii
	//	cata vreme avem noduri in coada
	cout<<"\nNivel 1: ";
	while(inc <= sf)
	{
		//	afisam primul nod din coada
		x = coada[inc];
		cout<<x->cheie<<" ";
		//	bagam fii ultimului nod in coada
		//	si completam nivelul nodurilor
		if(x->st)
		{
			coada[++sf] = x->st;
			nivele[sf] = nivele[inc]+1;
		}
		if(x->dr)
		{
			coada[++sf] = x->dr;
			nivele[sf] = nivele[inc]+1;
		}
		//	scoatem primul nod din coada
		inc++;
		//	afisam nivelul daca este diferit de nivelul nodului precedent
		if(nivele[inc] != nivele[inc-1] && inc <= sf)
			cout<<"\nNivel "<<nivele[inc]<<": ";
	}

	//	stergem memoria folosita pentru retinerea cozii si a nivelului nodului
	delete[] coada;
	delete[] nivele;
}

liste.h - ar trebuie rearanjat un pic codul
deasemenea atentie la folosirea listei, suntem in C++, si se poate sa apara rezultate
nesteptate in cazul folosirii pointerilor

// liste.h
//****************************************************************************
//	LISTE
//****************************************************************************
#pragma once

//****************************************************************************
//	clasa pentru retinerea unei liste cu elemente de tipul ELEMENT
//****************************************************************************
template<class ELEMENT>
class LISTA
{
private:
	//	nod este o structura necesara doar in interiorul clasei lista
	typedef struct NOD
	{
		ELEMENT		data;
		NOD			*urm;
	}NOD;
	//	inceputul listei
	NOD *inceput;
	//	sfarsitul listei
	NOD *sfarsit;
	//	nodul curent folosit la iterarea listei
	int indexPrec;
	NOD *nodPrec;
	//	lungime
	int numarElemente;
	//	permite elemente duplicate
	bool permisDuplicat;
	//	cauta un element in lista
	bool CautaElement(ELEMENT pEl, NOD **outPrecedent, NOD **outCurent);

	
	//	Cauta un nod dupa pozitie in lista
	//	daca nu este gasit nici un nod pe pozitia specificata
	//	functia returneaza NULL, iar altfel adresa nodului
	NOD* CautaNodDupaPozitie(int pozitie)
	{
		NOD* p = inceput;
		int index = 0;
		while(index != pozitie && p != NULL)
		{
			index++;
			p = p->urm;
		}
		return p;
	}
	//	sterge nod
	void StergeNod(NOD* pNod)
	{
		delete pNod;
		numarElemente--;
	}
	//	creaza un nod nou
	NOD* CreazaNod(ELEMENT pEl)
	{
		//	alocam memorie
		NOD* pNod = new NOD;
		//	completam informatia din nod
		pNod->urm = NULL;
		pNod->data = pEl;
		numarElemente++;
		//	returnam nodul creat
		return pNod;
	}

public:
	//	constructor si destructor
	LISTA(bool permiteDuplicat = true);
	~LISTA(void);
	//	adauga un element nou in lista
	bool AdaugaInceput(ELEMENT el);
	bool AdaugaSfarsit(ELEMENT el);
	//	operator
	ELEMENT & operator[](int index);
	//	lungimea
	int lungime()	{	return numarElemente;	}
	//	returneaza pozitia elementului cautat
	int CautaPozitia(ELEMENT el);
	//	sterge un element
	ELEMENT Sterge(ELEMENT el);
	//	sterge toate elementele
	void Sterge();
};



//****************************************************************************
//	este initializata lista
//****************************************************************************

template <class ELEMENT>
LISTA<ELEMENT>::LISTA(bool permiteDuplicat)
{
	permisDuplicat = permiteDuplicat;
	inceput = sfarsit = NULL;
	nodPrec = NULL;
	indexPrec = -1;
	numarElemente = 0;
}



//****************************************************************************
//	destructor sunt sterse toate elementele listei
//****************************************************************************

template <class ELEMENT>
LISTA<ELEMENT>::~LISTA(void)
{
	Sterge();
}



//****************************************************************************
//	functia sterge un element al listei
//	returneaza elementul sters
//****************************************************************************

template <class ELEMENT>
ELEMENT LISTA<ELEMENT>::Sterge(ELEMENT el)
{
	NOD *precedent;
	NOD *curent;

	ELEMENT elSters;
	//	daca gasim nodul
	if(CautaElement(el, &precedent, &curent))
	{
		//	trebuie sters primul nod
		if(precedent == NULL)
		{
			//	verificam daca stergem nodul pentru parcurgere
			if(this->nodPrec == inceput)
				this->nodPrec = curent->urm;
			//	modificam legaturile
			inceput = curent->urm;
			if(inceput == NULL)
				sfarsit = NULL;
		}
		else
		{
			//	verificam daca stergem nodul pentru parcurgere
			if(this->nodPrec == curent)
				this->nodPrec = inceput;
			//	modificam legaturile
			precedent->urm = curent->urm;
			//	poate trebuie sa modificam sfarsitul
			if(curent == sfarsit)
				sfarsit = precedent;
		}
		//	stergem nodul
		elSters = curent->data;
		StergeNod(curent);
		//	nodul a fost sters
		return elSters;
	}
	//	nodul nu exista
	return elSters;
}



//****************************************************************************
//	functia sterge toate elementele listei
//****************************************************************************

template <class ELEMENT>
void LISTA<ELEMENT>::Sterge()
{
	NOD *curent;
	//	cata vreme mai exista noduri
	while(inceput != NULL)
	{
		//	se stocheaza nodul curent
		curent = inceput;
		//	nodul urmator
		inceput = inceput->urm;
		//	este sters nodul curent
		StergeNod(curent);
	}
	//nodul curent devine null
	this->nodPrec = NULL;
	this->indexPrec = -1;
}



//****************************************************************************
//	functia cauta un element in lista
//	returneaza pozitia lui, daca nu este in lista returneaza -1
//****************************************************************************

template <class ELEMENT>
int LISTA<ELEMENT>::CautaPozitia(ELEMENT el)
{
	int poz = 0;
	//	iteram lista de la inceput
	NOD *start = inceput;
	while(start != NULL)
	{
		//	verificam daca am gasit elementul
		if(start->data == el)
			return poz;
		//	avansam in cautare
		start = start->urm;
		poz++;
	}
	//	nodul nu exista
	return -1;
}


//****************************************************************************
//	functia adauga un element in lista la inceput
//	returneaza true daca elementul a fost adaugat cu succes
//****************************************************************************
template <class ELEMENT>
bool LISTA<ELEMENT>::AdaugaInceput(ELEMENT el)
{
	NOD* precedent;
	NOD* curent;
	//	verificam daca avem voie sa avem elemente duplicate
	if(!permisDuplicat)
	{
		//	cautam elementul
		bool bExista = CautaElement(el, &precedent, &curent);
		//	verificam daca nodul exista deja in lista
		if(bExista)
			return false;
	}
	//	cream un nod nou
	NOD* nodNou = CreazaNod(el);
	nodNou->urm = inceput;
	inceput = nodNou;
	//	daca am adaugat primul nod
	if(inceput->urm == NULL)
		sfarsit = inceput;
	return true;
}

//****************************************************************************
//	functia adauga un element in lista la sfarsit
//	returneaza true daca elementul a fost adaugat cu succes
//****************************************************************************
template <class ELEMENT>
bool LISTA<ELEMENT>::AdaugaSfarsit(ELEMENT el)
{
	NOD* precedent;
	NOD* curent;
	//	verificam daca avem voie sa avem elemente duplicate
	if(!permisDuplicat)
	{
		//	cautam elementul
		bool bExista = CautaElement(el, &precedent, &curent);
		//	verificam daca nodul exista deja in lista
		if(bExista)
			return false;
	}
	//	cream un nod nou
	NOD* nodNou = CreazaNod(el);
	nodNou->urm = NULL;
	if(sfarsit != NULL)
	{
		sfarsit->urm = nodNou;
		sfarsit = nodNou;
	}
	else
		sfarsit = inceput = nodNou;
	return true;
}

//****************************************************************************
//	operatorul [] returneaza elementul de pe pozitia index
//****************************************************************************
template <class ELEMENT>
ELEMENT & LISTA<ELEMENT>::operator [](int index)
{
	//	verificam datele de intrare
	if(index < 0)
		index = 0;
	else if(index >= numarElemente)
		index = numarElemente-1;

	//	index se incrementeaza
	if(indexPrec+1 == index && indexPrec != -1)
	{
		indexPrec++;
		nodPrec = nodPrec->urm;
		return nodPrec->data;
	}
	//	nu avem index precedent
	nodPrec = CautaNodDupaPozitie(index);
	indexPrec = index;
	return nodPrec->data;
}

//****************************************************************************
//	functia cauta un element in lista
//
//	daca elementul este gasit functia returneaza true iar prec este adresa
//	nodului precedent nodului curent, iar curent este adresa nodului curent
//
//	daca elementul nu este gasit functia returneaza false iar prec si curent
//	sunt nodurile intre care poate fi inserat elementul cautat
//****************************************************************************
template <class ELEMENT>
bool LISTA<ELEMENT>::CautaElement(ELEMENT pEl, NOD **outPrecedent, NOD **outCurent)
{
	//	nu vrem sa lucram cu pointer dublu
	NOD *precedent = NULL;
	NOD *curent = NULL;
	//	pointer spre informatia din elementul curent
	ELEMENT data;

	//	verificam daca avem o lista goala
	if(inceput == NULL)
	{
		*outPrecedent = precedent;
		*outCurent = curent;
		return false;
	}
	//	daca lista nu e goala
	curent = inceput;
	while(curent != NULL)
	{
		//	informatia este stocata in data
		data = curent->data;
		//	cautam elementul
		if(data != pEl)
		{
			//	nu e elementul cautat, caontinuam
			precedent = curent;
			curent = curent->urm;
		}
		else
		{
			//	s-a ajuns la un elementul cautat
			*outCurent = curent;
			*outPrecedent = precedent;
			//	daca elementul este egal cu cel cautat returnam true, altfel false
			return true;
		}
	}
	//	lista a fost parcursa, dar elementul nu a fost gasit
	*outCurent = curent;
	*outPrecedent = precedent;
	return false;
}