Dictionare (TTree) in C++

Aceasta este o implementare mai putin eficienta a dictionarelor in C++.
Daca lucrati cu stringuri in JAVA sau PHP aveti ocazia sa vedeti cam cum functioneaza mecanismul lor interior.

demo.cpp

// demo.cpp
#include <iostream>
#include "TTree.h"

using namespace std;

void main()
{
	TTree tree;
	char buf[512];
	char opt;
	do
	{
		cout<<"V - face dictionarul vid\n";
		cout<<"A - adauga un cuvant\n";
		cout<<"S - suprima un cuvant\n";
		cout<<"C - verifica apartenenta unui cuvant\n";
		cout<<"L - listeaza cuvintele\n";
		cout<<"D - afiseaza toate cuvintele ce incep cu o litera data\n";
		cout<<"N - afiseaza numarul de cuvinte, primul si ultimul cuvant din dictionar si cuvintele de lungime minima si maxima\n";
		cout<<"X - terminare\n";
		cout<<"optiunea: ";
		cin>>opt;
		switch(opt)
		{
		case 'v':
			tree.sterge();
			break;
		case 'a':
			cout<<"cuvant: "; cin>>buf;
			tree.adauga(buf);
			break;
		case 's':
			cout<<"cuvant: "; cin>>buf;
			tree.sterge(buf);
			break;
		case 'c':
			cout<<"cuvant: "; cin>>buf;
			if(tree.cauta(buf))
				cout<<"cuvantul a fost gasit\n";
			else
				cout<<"cuvantul nu a fost gasit\n";
			break;
		case 'l':
			tree.afiseaza();
			break;
		case 'd':
			cout<<"litera: "; cin>>buf[0];
			tree.afiseaza(buf[0]);
			break;
		case 'n':
			tree.info();
			break;
		case 'x':
			break;
		default:
			cout<<"optiunea nu exista !\n";
		}
		cout<<endl;
	}
	while(opt != 'x');
}

TTree.h

// TTree.h
#pragma once

#include <iostream>

using namespace std;

const int N = 27;

class Nod
{
public:
	Nod* noduri[N];

	char caracter(int index) {
		if(index < N - 1)
			return 'a' + index;
		else
			return '#';
	}

	bool esteSfarsit() {
		return noduri[N-1] != NULL;
	}

	void puneSfarsit() {
		noduri[N-1] = this;
	}

	int nrUrmasi() {
		int s = 0;
		for(int i=0; i<N; i++)
			if(noduri[i])
				s++;
		return s;
	}

	Nod* urm(int index) {
		return noduri[index];
	}

	Nod* urm(char val) {
		int index;
		if(val >= 'a' && val <= 'z')
			index = val - 'a';
		else
			index = N-1;
		return noduri[index];
	}

	int index(char val) {
		int index;
		if(val >= 'a' && val <= 'z')
			index = val - 'a';
		else
			index = N-1;
		return index;
	}

	Nod() {
		for(int i=0; i<N; i++)
			noduri[i] = NULL;
	}

	~Nod() {
		for(int i=0; i<N-1; i++)
			if(noduri[i])
				delete noduri[i];
	}
};

class TTree
{
private:
	Nod *rad;
	char max[512], min[512];
	int lmin, lmax;

private:
	bool adauga(Nod*& rad, char *val);
	bool cauta(Nod* rad, char *val);
	bool sterge(Nod* rad, char *val);

	void parcurge(Nod* rad, char *buffer, int poz);

public:
	TTree(void);
	~TTree(void);

	void afiseaza()                                    { min[0]='z'+1; max[0]='a'-1; min[1]=max[1]= '\0'; char buf[512]; parcurge(rad, buf, 0); }
	void afiseaza(char start)                          { min[0]='z'+1; max[0]='a'-1; min[1]=max[1]= '\0'; char buf[512]; buf[0] = start; parcurge(rad->urm(start), buf, 1);	}
	void info();

	bool cauta(char *val)                              { return cauta(rad, val);	}
	bool adauga(char *val)                             { return adauga(rad, val);	}
	void sterge(char *val)                             { sterge(rad, val); lmin = 512; lmax = -1;	}
	void sterge()                                      { if(rad) { delete rad; rad = new Nod(); } lmin = 512; lmax = -1;	}
};

TTree.cpp

// TTree.cpp
#include "TTree.h"

TTree::TTree(void)
{
	rad = new Nod();
	lmax = -1;
	lmin = 512;
	min[0] = 'z'+1;
	max[0] = 'a'-1;
	min[1] = max[1] = '\0';
}

TTree::~TTree(void)
{
	sterge();
}

bool TTree::adauga(Nod *&rad, char *val)
{
	if(!rad)
		//	nu exista inca nici un nod in arbore
		rad = new Nod();
	if(val[0] == '\0')
	{
		rad->puneSfarsit();
		return true;
	}
	else
	{
		//	cautam prima litera
		int index = rad->index(val[0]);
		//	adaugam litera urmatoare
		return adauga(rad->noduri[index], val+1);
	}
}

bool TTree::sterge(Nod *rad, char *val)
{
	if(!rad)
		return false;
	if(val[0] == '\0')
	{
		rad->noduri[N-1] = NULL;
		return true;
	}

	int index = rad->index(val[0]);
	Nod *urm = rad->noduri[index];
	if(sterge(urm, val+1))
	{
		//	se poate sa trebuiasca sa stergem urm
		if(urm->nrUrmasi() == 0)
		{
			//	stergem nodul
			delete urm;
			rad->noduri[index] = NULL;
		}
		return true;
	}
	return false;
}

bool TTree::cauta(Nod *rad, char *val)
{
	if(rad == NULL)
		return false;
	if(val[0] == '\0')
	{
		if(rad->esteSfarsit())
			return true;
		else
			return false;
	}
	return cauta(rad->urm(val[0]), val+1);
}

void TTree::parcurge(Nod *rad, char *buffer, int poz)
{
	int i;
	if(rad==NULL)
		return;
	for(i=0; i<N-1; i++)
	{
		buffer[poz] = rad->caracter(i);
		buffer[poz+1] = '\0';
		parcurge(rad->noduri[i], buffer, poz+1);
		buffer[poz] = '\0';
	}
	if(rad->esteSfarsit())
	{
		if(lmin > poz)
			lmin = poz;
		if(lmax < poz)
			lmax = poz;
		if(strcmp(min, buffer) > 0)
			strcpy(min, buffer);
		if(strcmp(max, buffer) < 0)
			strcpy(max, buffer);
		cout<<buffer<<endl;
	}
}

void TTree::info()
{
	if(lmax <= 0)
		afiseaza();
	cout<<"\nlungime maxima: "<<lmax;
	cout<<"\nlungime minima: "<<lmin;
	cout<<"\ncuvant max: "<<max;
	cout<<"\ncuvant min: "<<min;
	cout<<endl;
}