Arbori si liste

[•beginner]

Vreau sa creez o agenda telefonica folosind arbori, in care stochez un nume si unul sau mai multe numere de telefon. Numarul/numerele de telefon sunt stocate intr-o lista. Informatiile sunt introduse sub acest format: <nume>spatiu<numar> pana la citirea unui anumit caracter (ex '.'). Daca un nume e introdus de mai multe ori cu numere diferite, retin toate numerele in lista  mentionata anterior.

Faptul ca  trebuie sa folosesc o lista ma baga putin in ceata.
Cum trebuie sa citesc datele introduse? Si cum exact introduc numerele in lista de care apartin?

Structurile mele arata asa:

Cod:

typedef struct lista {
	char *numar;
	struct lista *adr;
}lista;

typedef struct agenda {
	char *nume;
	lista *numar;
	struct agenda *stanga;
	struct agenda *dreapta;
}agenda;

[•beginner]

Uff Am reusit sa misc ceva, dar am greseli pentru ca nu returneaza ce trebuie. Asta e codul meu..

Cod:

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h>  

typedef struct list { 	
	char number[100];
	struct list *next;
	}List; 

List *head, *tail;

typedef struct tree { 	
	char name[100]; 	
	List *number; 	
	struct tree *left; 	
	struct tree *right;
	}Tree; 

void upper(char a[]){
  	int i; 	for(i=0;i<=strlen(a)-1;i++) {
  		if(a[i]>=97){ 		
			a[i]=a[i]-32; 		
		} 	
	} 
} 

List *addl(char *x)
{   
	List *newlist;
	newlist=(List *)calloc(1,sizeof(List));
	strcat(newlist->number, x);
    newlist->next = NULL;
    if( head == NULL )
        head = tail = newlist;
    else
    {
        tail->next = newlist;
        tail = tail->next;
    }
	return newlist;
}

void printlist(List *list) {
	list=head;
	while(list) {
		printf("%s\n", list->number);
		list=list->next;
	}
}


Tree *insertTree(char *name, char *number, Tree *p)
{
   if(!p
 
	{
	  p=(Tree*)malloc(sizeof(Tree));
	  strcpy(p->name,name);
	  p->number=addl(number);
	  p->left=NULL;
	  p->right=NULL;
	  return(p);
	 }
 
	if(name < p->name)
	p->left=insertTree(name, number, p->left);
	else
	if(name > p->name)
	p->right=insertTree(name, number, p->right);
	return(p);
 }

Tree *search(char *name, Tree *tree) {
	if( strcmp(name, tree->name) == 0) {
		printlist(tree->number); }
	else if( strcmp( name, tree->name ) < 0 ) {
	return search( name, tree->left ) ;
	} else {
	return search(name, tree->right) ;
	}
}


int main() {
		printf("%s\n", "100%");
		Tree *tree = NULL;
		char in[10],a[200],b[100], in2[10];
		do { 
		fgets(in,200,stdin); 
        *(strchr(in,'\n')) = '\0'; 
        if ((strlen(in) > 0) && (in[0] != '.')) { 
			sscanf(in,"%s %s", &a, &b ); 
			upper(a);
			tree=insertTree(a,b,tree);
		} 
    } while (in[0] != '.'); 
	
	
	while(in2[0] !='.') {
		printf("%s ", "Type a name please");
		fgets(in2,200,stdin); 
        *(strchr(in2,'\n')) = '\0'; 
		sscanf(in2,"%s", &a);
		if(in2[0] == '.') break;
		else { upper(a);
			search(a,tree); 
		}
	}
	
	return 0;
}

Cu siguranta creez lista gresit. In plus, cand introduc un nume care nu e in arbore se blocheaza. As aprecia orice forma de ajutor.
Multumesc.

P.S: trebuie sa introduc numele si numarul intr-o lista. Daca numele e deja acolo, adaug numarul la lista. Apoi caut numele introduse de user si returnez toate numerele persoanei respective.

[•TheNechiz]

Sunt puțin obosit.Nu reușesc să înțeleg ce trebuie să faci. Poți să scrii enunțul cum l-ai primit sau să reformulezi cerința ?

[•beginner]

Ok. Trebuie sa creez o "agenda telefonica" rudimentara. Programul meu citeste de la tastatura un nume si un numar (<nume>spatiu<numar>) si creaza un arbore, sortat dupa nume. Fiecare nod al arborelui contine un nume si o lista (care stocheaza toate numerele de telefon ale persoanei respective. Cu alte cuvinte, daca introduci de doua ori acelasi nume, dar cu numere diferite, adaug noul numar in lista de care apartine). Citirea se face pana la introducere caracterului '.', apoi, tot pana la introducerea acestui caracter cer user-ului sa introduca un nume. Fac cautarea dupa nume, daca numele exista, printez toate numerele care apartin de el. Altfel, afiez "Nu a fost gasit". (parte pe care inca nu am introdus-o in cod). De asemenea, programul nu tine cont de litere mari sau mici sau situatii de "GeNUl". De aceea am facut functia "upper".

[•TheNechiz]

Orice tip de ajutor...

Cod:

# include <iostream>
# include <cstring>
using namespace std;

char a[21],b[11];

struct nr
{
    char x[11]; // numarul de telefon
    nr *urm;
};
struct nod
{
    char Nume[21];
    nod * urm;
    nr *prim,*ultim; 
};
nod *p,*q; // Lista nodurilor

void Adaug_nr( nr *&prim , nr *&ultim)
{
    // Verific daca numarul mai apare in lista
    nr *x = prim;
    while( x && strcmp(x->x,b) )
        x = x->urm;
    if( x ) return;

    // Daca nu apare in lista , atunci il adaug
    x = new nr;
    strcpy(x->x,b);
    x->urm = NULL;
    if( !prim ) prim = ultim = x;
        else
        {
            ultim->urm = x;
            ultim = ultim->urm;
        }
}

void Adaug()
{
    // Creez lista ordonata
    nod *x = new nod;
    strcpy(x->Nume,a);
    x->urm = NULL;
    x->prim = NULL;
    x->ultim = NULL;
    Adaug_nr(x->prim,x->ultim);
    if( p ) // Daca lista nu este vida
    {   // Daca numele se gaseste in lista, atunci adaug numarul de telefon
        // Alfel adaug un nou nod cu numele
        if( strcmp(p->Nume,a) == 0 )
        {
            Adaug_nr(p->prim,p->ultim);
            delete x;
            return;
        }
        if( strcmp(p->Nume,a) > 0 )
        {
            x->urm = p;
            p = x;
        }
        else
        {
            nod *y = p;
            while( y->urm )
            {
                if( strcmp(y->urm->Nume,a) == 0 )
                {
                    Adaug_nr(y->urm->prim,y->urm->ultim);
                    delete x;
                    return;
                }
                else if( strcmp(y->urm->Nume,a) > 0 )
                    break;
                y = y->urm;
            }
            x->urm = y->urm;
            y->urm = x;
            if( y == q ) q = y; // Daca nodul a fost adaug la sfarsit listei
            // atunci mut pointerul q pe ultimul element
        }
    }
    else p = q = x; // Daca lista este vida , creez lista
}

void Tipar_nr( nr *prim )
{
    for( nr *i = prim ; i ; i = i->urm )
        cout << i->x << '\n';
}

void Corect( char *y )
{
    // Transform primul caracter in majuscula daca e cazul
    if( *y >= 'a' && *y <= 'z' )
        *y -= 32;
    // Transform restul caracterelor daca e cazul
    ++y;
    while( *y != '\0' )
    {
        if( *y >= 'A' && *y <= 'Z' )
            *y += 32;
        ++y;
    }
}

void Citire()
{
    char *x = a , aux;
    do
    {
        aux = cin.get();
        if( aux == ' ' ) x = b;
            else
            {   if( aux == '\n' || aux == '.' )
                {
                    Corect(a);
                    // Adaug in lista
                    Adaug();
                    *a = NULL;
                    *b = NULL;
                    x = a;
                }
                else
                {
                    *(x++) = aux;
                    *x = NULL;
                }
            }
    }while( aux != '.' );
}

nod * Cauta()
{
    nod * x = p;
    while( x && strcmp(x->Nume,a) )
        x = x->urm;
    return x;
}

void Rezolv()
{
    bool ok;
    nod * x;
    cin >> a;
    ok = true;
    while( 1 )
    {
        if( *a == '.' )
            break;
        if( *(a+strlen(a)-1) == '.' ){
            *(a+strlen(a)-1) = '\0';
            ok = false;
        }
        Corect(a);
        x = Cauta();
        if( !x ) cout << "Numele nu apare in agenda.\n";
            else
            {
                cout << '\n' << x->Nume << '\n';
                Tipar_nr(x->prim);
            }
        if( !ok ) break;
        cin >> a;
        ok = true;
    }

}

int main()
{
    Citire();
    Rezolv();
    return 0;
}

Am rezolvat problema.
Spune-mi dacă mai pot să te ajut cu ceva.  

PS: Încearcă să lucrezi pe un alt IDE. Poți alege între CodeBlocks,Dev C++, Mingw.  ( Borland nu se mai folosește de ceva timp )

[•beginner]

Multumesc mult mult mult de tot!
Acum o sa incerc sa o inteleg si apoi sa lucrez singur. Sunt nou cu arborii si mi-a fost destul de greu sa-i inteleg fara ajutor.

Legat de IDE, folosesc MinGW si CodeBlocks, dar lucrez in C si de acolo e diferenta de biblioteci, memory allocation etc.
Dar nu e problema, o sa adaptez algoritmul pentru C, dupa ce il inteleg perfect.
Multumesc inca o data!

Ooops Tocmai ce am realizat ca foloseste doua liste. (Sper sa nu gresesc). Eu trebuie sa folosesc o lista si un arbore. Dar o sa incerc sa ma iau dupa modelul tau. Sper sa reusesc. Multumesc inca o data.

[•TheNechiz]

Sunt mai multe feluri de a reprezenta un arbore in memoria calculatorul.
Arborele pe care il folosesc eu are doar doua niveluri.
Am reprezentat arborele sub forma asta:

Cod:

typedef struct nod{
	int inf;
	nod *fiu_stang, *frate_drept;
}ARBORE;

Daca vrei, poti modifica putin programul si sa reprezinti arborele asa:

Cod:

typedef struct nod{
	int inf;
	int nr;   //numărul descendenţilor
	nod *fiu[NR_MAXIM_FII];  //tablou cu adresele descendenţilor
}ARBORE;

[•beginner]

struct nod
{
    char Nume[21];
    nod * urm;
    nr *prim,*ultim; // lista de adiacenta
};

asta nu inteleg...  prim si ultim nu sunt de tip nod, sunt de tip nr.

[•TheNechiz]

Tipul "tatilor" este diferit de tipul "fiilor".

PS: Am vrut sa reprezint arborele prin lista de adiacenta,apoi m-am razgandit.Am uitat sa modific comentariul.

Varianta cu arbori binari.

Cod:

# include <iostream>
# include <cstring>
using namespace std;

char a[21],b[11];

struct nr
{
    char x[11]; // numarul de telefon
    nr *urm;
};
typedef struct nod
{
    char Nume[21];
    nod *st; // fiu stang
    nod *dr; // fiu drept
    nr *prim,*ultim; // lista numerelor de telefon
}arbore;
arbore *root; // radacina

void Adaug_nr( nr *&prim , nr *&ultim)
{
    // Verific daca numarul mai apare in lista
    nr *x = prim;
    while( x && strcmp(x->x,b) )
        x = x->urm;
    if( x ) return;

    // Daca nu apare in lista , atunci il adaug
    x = new nr;
    strcpy(x->x,b);
    x->urm = NULL;
    if( !prim ) prim = ultim = x;
        else
        {
            ultim->urm = x;
            ultim = ultim->urm;
        }
}

void Adaug()
{
    // Pregatesc frunza
    arbore *x = new arbore;
    x->st = x->dr = NULL;
    x->prim = x->ultim = NULL;
    strcpy(x->Nume,a); // copiez informatia utila
    Adaug_nr(x->prim,x->ultim); // adaug numarul de telefon la frunza
    // Verific daca arbore este vid
    if( !root )
    {
        root = x; // creez arborele
        return; // intrerupe functia
        // rularea ei nu mai are sens
    }
    else
    {
        arbore *i = root;
        // i - pentru a parcurge arborele in cautarea numelui
        while( i != NULL )
        {
            if( strcmp(x->Nume,i->Nume) == 0 )
            {
                // Am gasit numele , adaug numarul de telefon
                Adaug_nr(i->prim,i->ultim);
                delete x;
                return;
            }
            if( strcmp(i->Nume,x->Nume) > 0 )
            {
                // Daca nu exista un fiu stang
                if( !i->st )
                {
                    i->st = x; // il pun pe x in arbore ca fiu stang
                    return; // si am terminat aici
                }
                else i = i->st;

            }
            else
            {
                // Aceeasi poveste si pentru fiul drept
                if( !i->dr )
                {
                    i->dr = x;
                    return;
                }
                else i = i->dr;
            }
        }
        // Numele a fost adaugat in lista
    }

}

void Tipar_nr( nr *prim )
{
    for( nr *i = prim ; i ; i = i->urm )
        cout << i->x << '\n';
}

void Corect( char *y )
{
    // Transform primul caracter in majuscula daca e cazul
    if( *y >= 'a' && *y <= 'z' )
        *y -= 32;
    // Transform restul caracterelor daca e cazul
    ++y;
    while( *y != '\0' )
    {
        if( *y >= 'A' && *y <= 'Z' )
            *y += 32;
        ++y;
    }
}

void Citire()
{
    char *x = a , aux;
    do
    {
        aux = cin.get();
        if( aux == ' ' ) x = b;
            else
            {   if( aux == '\n' || aux == '.' )
                {
                    Corect(a);
                    // Adaug in lista
                    Adaug();
                    *a = NULL;
                    *b = NULL;
                    x = a;
                }
                else
                {
                    *(x++) = aux;
                    *x = NULL;
                }
            }
    }while( aux != '.' );
}

arbore * Cauta()
{
    arbore * x = root;
    while( x != NULL )
    {
        if( strcmp(a,x->Nume) == 0 )
            return x;
        if( strcmp(a,x->Nume) > 0 )
            x = x->dr;
        else
            x = x->st;
    }
    return x;
}

void Rezolv()
{
    bool ok;
    arbore * x;
    cin >> a;
    ok = true;
    while( 1 )
    {
        if( *a == '.' )
            break;
        if( *(a+strlen(a)-1) == '.' ){
            *(a+strlen(a)-1) = '\0';
            ok = false;
        }
        Corect(a);
        x = Cauta();
        if( !x ) cout << "Numele nu apare in agenda.\n";
            else
            {
                cout << '\n' << x->Nume << '\n';
                Tipar_nr(x->prim);
            }
        if( !ok ) break;
        cin >> a;
        ok = true;
    }

}

int main()
{
    Citire();
    Rezolv();
    return 0;
}