/*
Bucalaete Nicolae
An II, Informatica
Grupa 1, Subgrupa 1

Laboratorul nr. 5

Tema 2. Crearea si vizualizarea unei liste liniare cu inserare in spate.
Cautarea, stergerea unui element cu o cheie data.
*/

#include <stdio.h>
#include <stdlib.h>  /*pt functia malloc*/
#include <ctype.h>   /*pt functia toupper*/

typedef struct nod 
{
	int cheie;       /*cheia dupa care are loc identificarea nodurilor in cadrul listei*/
	char info[10];   /*informatia utila din cadrul listei*/
	struct nod *urm; /*un pointer catre urmatorul nod din lista*/
}Tnod;
typedef Tnod* ref;   /*referinta catre o structura de tipul Tnod*/

ref p=NULL, q=NULL, r=NULL; /*p - pointer catre primul nod din lista
							  q - pointer catre ultimul nod din lista
							  r - pointer auxiliar*/
unsigned int dinamic=0; /*controleaza meniul ce se afiseaza*/

void meniu(void);
void ins_spate(void);
void listare(void);
void creare(void);
void delete_nod(int);
int cautare(int);
void delete_lista(void);

main()
{
	char c;

	printf("\n");
	printf(" Crearea si vizualizarea unei liste liniare cu inserare in spate.\n");
	printf("        Cautarea, stergerea unui element cu o cheie data.\n");
	do
	{
		meniu(); fflush(stdin); scanf("%c", &c); c = toupper(c);
		switch(c)
		{
			int cheie;

		case 'C':
			creare();
			dinamic = 1;
			break;
		case 'L':
			listare();
			break;
		case 'D':
			printf("Introduceti cheia nodului ce doriti sa-l stergeti : ");
			fflush(stdin); scanf("%d", &cheie);
			delete_nod(cheie);
			break;
		case 'I':
			ins_spate();
			break;
		case 'S':
			printf("Introduceti cheia nodului ce doriti sa-l cautati : ");
			fflush(stdin); scanf("%d", &cheie);
			if(cautare(cheie)==1)
				printf("Informatia din nodul cu cheia \"%d\" este : %s\n", cheie, r->info);
			else 
				printf("Nu exista nici un nod cu cheia \"%d\" !\n", cheie);
			break;
		case 'V':
			delete_lista();
			printf("Spatiul ocupat de l.l.s.i a fost eliberat!\n");
			dinamic = 0;
			break;
		default:
			printf("Comanda gresita!\n");
		}
	}
	while(c!='E');	
	delete_lista();
	printf("Spatiul ocupat de l.l.s.i. a fost eliberat\n");
}

void creare() /*Creaza o l.l.s.i. prin apeluri succesive ale functiei ins_spate*/
{
	char c;

	do
	{
		ins_spate();
		printf("Continuati(D/N) : ");
		fflush(stdin); scanf("%c", &c); c = toupper(c);
	}
	while(c=='D');
}/*sfarsit creare*/

void ins_spate(void)  /*insereaza un nod in fata unei l.l.s.i.*/
{
	r = (ref)malloc(sizeof(Tnod));
	printf("Introduceti cheia nodului : ");
	fflush(stdin); scanf("%d", &r->cheie); /*de adaugat validarea cheii*/
	printf("Introduceti informatia utila : ");
	fflush(stdin); scanf("%s", r->info);
	r->urm = NULL;
	if(p==NULL) /*creeaza primul nod al listei*/
	{
		p = r;
		q = p;
	}
	else
	{
		q->urm = r;
		q = r;
	}
}/*sfarsit ins_spate*/

void listare(void) /*listeaza elementele l.l.s.i. cu inserare in fata
					 in ordinea inversa a introducerii cheilor*/
{
	if(p==NULL)
		printf("Lista este vida!\n");
	else
	{
		printf("Elementele listei sunt :\n");
		r = p;
		while(r!=NULL)
		{
			printf("Cheia = %d        ", r->cheie);
			printf("Informatia = %s", r->info);
			printf("\n");
			r = r->urm;
		}
	}
}/*sfarsit listare*/

int cautare(int k) /*cauta nodul cu cheia k*/
{
	r = p;
	while((r!=NULL) && (r->cheie!=k))
		r = r->urm;
	if(r==NULL)
		return -1; /*returneaza -1 daca nu a gasit un nod cu cheia k*/
	else
		return 1; /*returneaza 1 daca a gasit un nod cu cheia k*/
}/*sfarsit cautare*/

void delete_nod(int k) /*sterge nodul cu cheia k*/
{
	if(p->cheie == k)
	{
		r = p->urm;
		free(p);
		p = r;
		printf("Nodul cu cheia \"%d\" a fost sters.\n", k);
		if(p==NULL)
		{
			dinamic = 0;
			printf("Lista este vida.\n");
		}
	}
	else
	{
		r = p;
		q = p;
		while((r!=NULL) && (r->cheie!=k))
		{
			q = r;
			r = r->urm;
		}
		if(r!=NULL)
		{
			q->urm = r->urm;
			free(r);
			r = NULL;
			printf("Nodul cu cheia \"%d\" a fost sters\n", k);
		}
		else 
			printf("Nu exista nici un nod cu cheia \"%d\"\n", k);
	}
}/*sfarsit delete_nod*/

void delete_lista(void) /*sterge lista liniara <=> elibereaza spatiul ocupat*/
{
	for(r = p; r != NULL; r = q)
	{
		q = r->urm;
		free(r);
		r = NULL;
	}
	p = NULL;
} /*sfarsit delete_lista*/

void meniu(void)
{	
	printf("\nL.l.s.i. cu inserarea elementelor la sfarsitul listei\n\n");
	if(dinamic==0)
		printf("C. Crearea listei\n");
	if(dinamic)
	{
		printf("I. Inserarea unui element la sfarsitul listei\n");
		printf("S. Cauta un element dupa o cheie data\n");
		printf("D. Sterge un element cu o cheie data\n");
		printf("V. Sterge l.l.s.i.\n");
		printf("L. Afiseaza lista liniare\n");
	}
	printf("E. Exit\n");
	printf("Tastati optiunea : ");
}