Laborator de C/C++

Un mic program care lucreaza cu arbori generalizati scris in C++, cu alocarea dinamica a memoriei

in ArboreGen.h este definita clasa ArboreGen, in ArboreGen.cpp sunt implementate metodele clasei
iar in demo1.cpp este dat un exemplu de folosire a clasei de arbore generalizat

ArboreGen.h

#pragma once

#include <string.h>

typedef struct Nod
{
	char *cheia;
	Nod *fiuPrim;
	Nod *frateDrept;
	Nod *tata;

	Nod(Nod *nodTata, char *nume)
	{
		cheia = new char[strlen(nume)+1];
		strcpy(cheia, nume);
		tata = nodTata;
		fiuPrim = frateDrept = NULL;
	}
	~Nod() { delete cheia; }
}Nod, *PNod;




class Nivel
{
private:
	typedef struct ListaNod
	{
		PNod nod;
		ListaNod *nodUrm;

		ListaNod(PNod nodNou)	{	nod = nodNou; nodUrm = NULL;	}
	}ListaNod, *PListaNod;

	PListaNod prim;
	PListaNod ultim;
public:
	Nivel()         {	prim = ultim = NULL;	}
	~Nivel()        {	Sterge();				}
	bool EsteGol()  {	return prim == NULL;	}

	void AdaugaNod(PNod nod);
	void Afiseaza();
	void Sterge();
};

class ArboreGen
{
private:
	PNod radacina;

private:
	//	functii private
	void StergeArbore(PNod rad);
	PNod PointerNod(PNod rad, char *nume);

	PNod Tata(PNod nod)         {	return nod->tata;		}
	PNod PrimulFiu(PNod nod)    {	return nod->fiuPrim;	}
	PNod FrateDrept(PNod nod)   {	return nod->frateDrept;	}
	char* Cheia(PNod nod)       {	return nod->cheia;		}

	void ParcPreordine(PNod nod);
	void ParcInordine(PNod nod);
	void ParcPostordine(PNod nod);

	void ParcNivel(PNod nod, int nivel, Nivel *nivele);
	void DrumIntern(PNod nod, int *lungime);
	void AdancimeNod(PNod nod, int *adancime);

public:
	ArboreGen(void);
	~ArboreGen(void);

public:
	PNod GetNod(char *nume)    {	return PointerNod(radacina, nume);			}
	void Sterge()              {	StergeArbore(radacina); radacina = NULL;	}

	//	parcurgerile
	void AfiseazaPreordine()   {	ParcPreordine(radacina);	}
	void AfiseazaInordine()    {	ParcInordine(radacina);		}
	void AfiseazaPostordine()  {	ParcPostordine(radacina);	}
	void AfiseazaNiveluri();

	int LungimeDrumIntern()    {	int l=0; DrumIntern(radacina, &l); return l;	}

	bool AdaugaRadacina(char *nume);
	bool AdaugaFiu(PNod tata, char *numeFiu);
	bool AdaugaFiu(char *numeTata, char *numeFiu);

	int Adancime(PNod nod);
	int Adancime(char *numeNod);
};

ArboreGen.cpp

#include "ArboreGen.h"
#include <iostream>

using namespace std;

//*********************************************************************
//	class Nivel
//*********************************************************************

void Nivel::AdaugaNod(PNod nod)
{
	PListaNod p = new ListaNod(nod);
	if(ultim)
	{
		ultim->nodUrm = p;
		ultim = p;
	}
	else
	{
		prim = ultim = p;
	}
}

void Nivel::Afiseaza()
{
	PListaNod p = prim;
	while(p)
	{
		cout<<p->nod->cheia<<", ";
		p = p->nodUrm;
	}
}

void Nivel::Sterge()
{
	PListaNod p, q;
	p = prim;
	while(p)
	{
		q = p;
		p = p->nodUrm;
		delete q;
	}
	prim = ultim = NULL;
}

//*********************************************************************
//	class ArboreGen
//*********************************************************************

ArboreGen::ArboreGen(void)
{
	radacina = NULL;
}

ArboreGen::~ArboreGen(void)
{
	Sterge();
}

//	functii private

void ArboreGen::StergeArbore(PNod rad)
{
	if(rad)
	{
		PNod p, q;
		p = rad->fiuPrim;
		while(p)
		{
			q = p;
			p = p->frateDrept;
			StergeArbore(q);
		}
		delete rad;
	}
}

PNod ArboreGen::PointerNod(PNod rad, char *nume)
{
	PNod p;
	PNod rez;
	if(rad)
	{
		//	e nodul cautat
		if(strcmp(rad->cheia, nume) == 0)
			return rad;
		//	cautam pe nivelul urmator
		p = rad->fiuPrim;
		while(p)
		{
			rez = PointerNod(p, nume);
			if(rez)
				return rez;
			p = p->frateDrept;
		}
	}
	return NULL;
}

bool ArboreGen::AdaugaRadacina(char *nume)
{
	//	verificam daca exista radacina
	if(radacina)
		return false;
	//	adaugam radacina
	//	radacina nu are tata
	radacina = new Nod(NULL, nume);
	return true;
}

bool ArboreGen::AdaugaFiu(PNod tata, char *numeFiu)
{
	//	verificam daca datele sunt valide
	if(!tata || !numeFiu)
		return false;
	//	cream un fiu nou
	PNod fiuNou = new Nod(tata, numeFiu);

	if(tata->fiuPrim)
	{
		//	tatal are cel putin un fiu
		PNod p = tata->fiuPrim;
		//	parcurgem fii sai
		while(p->frateDrept)
			p = p->frateDrept;
		//	am ajuns la ultimul fiu, care nu are frate drept
		//	adaugam frate drept
		p->frateDrept = fiuNou;
	}
	else
	{
		//	acesta e primul fiu
		tata->fiuPrim = fiuNou;
	}
	return true;
}

bool ArboreGen::AdaugaFiu(char *numeTata, char *numeFiu)
{
	PNod tata = GetNod(numeTata);
	return AdaugaFiu(tata, numeFiu);
}

void ArboreGen::ParcPreordine(PNod nod)
{
	if(nod)
	{
		//	parcurgem tatal
		cout<<nod->cheia<<", ";
		//	parcurgem fii
		PNod p = nod->fiuPrim;
		while(p)
		{
			ParcPreordine(p);
			p = p->frateDrept;
		}
	}
}

void ArboreGen::ParcInordine(PNod nod)
{
	if(nod)
	{
		PNod p = nod->fiuPrim;
		if(p)
		{
			//	parcurgem p
			ParcInordine(p);
		}

		//	parcurgem tata
		cout<<nod->cheia<<", ";
		if(p)
		{
			//	parcurgem restul fratilor
			p = p->frateDrept;
			while(p)
			{
				ParcInordine(p);
				p = p->frateDrept;
			}
		}
	}
}

void ArboreGen::ParcPostordine(PNod nod)
{
	if(nod)
	{
		//	parcurgem fii
		PNod p = nod->fiuPrim;
		while(p)
		{
			ParcPostordine(p);
			p = p->frateDrept;
		}
		//	parcurgem tatal
		cout<<nod->cheia<<", ";
	}
}

void ArboreGen::ParcNivel(PNod nod, int nivel, Nivel *nivele)
{
	if(nod)
	{
		//	adaugam nodul curent pe nivelul curent
		nivele[nivel].AdaugaNod(nod);
		PNod p = nod->fiuPrim;
		//	adaugam fii pe nivelul urmator
		while(p)
		{
			ParcNivel(p, nivel+1, nivele);
			p = p->frateDrept;
		}
	}
}

void ArboreGen::AfiseazaNiveluri()
{

	Nivel p[100];	//	aici nu e o implementare prea buna
					//	de prefereat ar fi sa avem o lista cu nivelele
					//	dar sa zicem, modific dupa daca am timp
	ParcNivel(radacina, 1, p);
	int i = 1;
	while(!p[i].EsteGol())
	{
		cout<<"Nivelul "<<i<<": ";
		p[i].Afiseaza();
		cout<<endl;
		i++;
	}
}

void ArboreGen::DrumIntern(PNod nod, int *lungime)
{
	if(nod)
	{
		//	parcurgem fii
		PNod p = nod->fiuPrim;
		while(p)
		{
			DrumIntern(p, lungime);
			p = p->frateDrept;
			(*lungime)++;
		}
	}
}

void ArboreGen::AdancimeNod(PNod nod, int *adancime)
{
	if(nod)
	{
		PNod p = nod;
		while(p)
		{
			(*adancime)++;
			p = p->tata;
		}
	}
}

int ArboreGen::Adancime(PNod nod)
{
	int adancime = 0;
	AdancimeNod(nod, &adancime);
	return adancime;
}

int ArboreGen::Adancime(char *numeNod)
{
	PNod nod = GetNod(numeNod);
	return Adancime(nod);
}

demo1.cpp

#include <iostream>
#include <fstream>

#include "ArboreGen.h"

using namespace std;

int const BUF_SIZE = 512;
char* numeFisier = "arbore.txt";



bool Citeste(char *numeFisier, ArboreGen *pArbore)
{

	ifstream fin;
	char fiu[BUF_SIZE+1];
	char tata[BUF_SIZE+1];
	int i, nrFii;

	try
	{
		fin.open(numeFisier, ios::in);
		//	citim radacina
		fin.getline(tata, BUF_SIZE);
		pArbore->Sterge();
		pArbore->AdaugaRadacina(tata);

		//	nr de fii ai radacinei
		if(fin>>nrFii)
		{
			fin.get();
			for(i=0; i<nrFii; i++)
			{
				fin.getline(fiu, BUF_SIZE);
				pArbore->AdaugaFiu(tata, fiu);
			}

			while(fin.getline(tata, BUF_SIZE))
			{
				if(strlen(tata) == 0)
					continue;
				fin>>nrFii;
				fin.get();
				for(i=0; i<nrFii; i++)
				{
					fin.getline(fiu, BUF_SIZE);
					pArbore->AdaugaFiu(tata, fiu);
				}
			}
		}
	}
	catch(ifstream::failure e)
	{
		cout<<"Eroare la citirea din fisier!\n";
		return false;
	}
	fin.close();

	return true;
}

int main()
{
	ArboreGen arbore;

	int nrFii;
	char nume[BUF_SIZE], nume1[BUF_SIZE], nume2[BUF_SIZE];
	PNod n1, n2, p, n;
	char opt;

	do
	{
		//	afiseaza meniu
		cout<<" Meniu\n V - Arbore vid\n C - Citeste din fisier arborele\n N - Vizualizeaza arborele pe niveluri\n T - Afiseaza cheile in cele 3 parcurgeri\n P - Afiseaza lungimea drumului intern\n R - Verifica stramos-descendent\n I - Info cheie\n Optiunea:";

		cin>>opt;
		//	efectueaza operatiunea
		switch(opt)
		{
		case 'v':
			arbore.Sterge();
			cout<<"Arborele a fost sters\n";
			break;
		case 'c':
			if(Citeste(numeFisier, &arbore))
				cout<<"Arborele a fost citit\n";
			break;
		case 'n':
			cout<<"Arborele pe niveluri:\n";
			arbore.AfiseazaNiveluri();
			cout<<endl;
			break;
		case 'p':
			cout<<"Lungimea drumului intern: "<<arbore.LungimeDrumIntern()<<endl;
			break;
		case 't':
			cout<<"Preordine   : ";
			arbore.AfiseazaPreordine();
			cout<<"\nInordine  : ";
			arbore.AfiseazaInordine();
			cout<<"\nPostordine: ";
			arbore.AfiseazaPostordine();
			break;
		case 'i':
			//	citim nodul
			nrFii = 0;
			cout<<"nume nod: ";
			cin>>nume;
			n = arbore.GetNod(nume);
			if(!n) break;
			//	afisare info
			if(n->tata)
				cout<<"cheie tata: "<<n->tata->cheia<<endl;
			else
				cout<<" nu are tata!\n";
			p = n->fiuPrim;
			if(p)
			{
				cout<<"cheile fiilor: ";
				while(p)
				{
					cout<<p->cheia<<", ";
					p = p->frateDrept;
					nrFii++;
				}
				cout<<endl;
			}
			else
				cout<<" nu are fii!\n";
			p = n->frateDrept;
			if(p)
			{
				cout<<"cheile fratilor: ";
				while(p)
				{
					cout<<p->cheia<<", ";
					p = p->frateDrept;
				}
				cout<<endl;
			}
			else
				cout<<" nu are frati!\n";
			cout<<"nr fii: "<<nrFii<<endl;
			cout<<"adancime: "<<arbore.Adancime(n);
			break;
		case 'r':
			cout<<"nod 1: ";
			cin>>nume1;
			cout<<"nod 2: ";
			cin>>nume2;
			n1 = arbore.GetNod(nume1);
			n2 = arbore.GetNod(nume2);
			if(n1==NULL || n2==NULL) break;
			if(n1->tata == n2)
				cout<<nume1<<" este fiul "<<nume2<<endl;
			else if(n2->tata == n1)
				cout<<nume2<<" este fiul "<<nume1<<endl;
			else
				cout<<"intre noduri nu exista nici o relatie\n";
			break;
		}
		cout<<endl;
	}
	while(opt != 'x');

	return 0;
}