/*
  Toate operatiile de baza asupra listelor liniare dublu inlantuite.
*/

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

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, *ant;/*pointeri catre urmatorul, anteriorul nod din lista*/
	};								 
typedef struct nod Tnod;
typedef Tnod* ref; /*referinta catre o structura de tipul Tnod*/

ref p,q,r,s; /*p - pointer catre primul nod al listei*/
int k;       /*cheia dupa care se face cautarea unui nod*/

void insd_d(void);
void insd_i(void);
void insd_p(void);
void listare(void);
void creare(void);
void cautare(void);
void delete_lista(void);
void insd_cf(void);  /*insereaza un nod in fata unei l.l.d.i.*/
void suprima(void); /*suprima un nod dat de cheie r*/

main()
{
	char c;
	system("cls");
	do
	{
		printf("\nL.l.d.i. cu inserarea elementelor la inceputul listei\n\n");
		printf("C. Crearea listei\n");
		printf("I. Inserarea unui element la inceputul listei\n");
		printf("D. Inserarea unui element dupa un element de o cheie data\n");
		printf("B. Inserarea unui element in fata unui nod dat\n");
		printf("F. Cautarea unui element dupa o cheie data\n");
		printf("S. Sterge un nod de cheie data\n");
		printf("V. Sterge l.l.d.i.\n");
		printf("L. Afisarea listei\n");
		printf("E. Exit\n");
		printf("Tastati optiunea : ");
		fflush(stdin); scanf("%c", &c); c = toupper(c);
		switch(c)
		{
			case 'C':creare();listare();break;
			case 'L':listare();break;
			case 'I':
							 if(p!=NULL)
								 {
									 insd_cf();listare();
								 }
								 else
										 printf("Lista este vida!\n")	;								 
							 break;
			case 'D':
					  	 if(p!=NULL)
								 {
								 printf("Introduceti cheia nodului dupa care sa inseram : ");
								 scanf("%d",&k);cautare();
								 if(r!=NULL)
									 insd_d();
									 else
										 printf("Nu exista nici un nod cu cheia introdusa!\n");
								 }
							 else
								 printf("Lista este vida!\n");
							 break;
			case 'B':
							 if(p!=NULL)
								 {
								 printf("Introduceti cheia nodului inainte caruia inseram : ");
								 scanf("%d",&k);cautare();
								 if(r!=NULL)
									 insd_i();
									 else
										 printf("Nu exista nici un nod cu cheia introdusa!\n");
								 }
								 else
									 printf("Lista este vida!\n");
							 break;                           
			case 'S':
							 if(p!=NULL)
								 {
								 printf("Introduceti cheia nodului pe care doriti sa-l stergeti : ");
								 scanf("%d", &k);
								 cautare();
								 if(r==NULL)
									 printf("Nu exista nici un nod cu cheia introdusa\n");
									 else
										 {
										 suprima();
										 printf("Nodul a fost sters\n");
										 }
								 }
							 else 
								 printf("Lista este vida!\n");
							 break;
			case 'F':
							 if(p==NULL)
								 {
									 printf("Lista este vida!\n");
									 break;
								 }
							 printf("Introduceti cheia nodului ce doriti sa-l cautati : ");
							 fflush(stdin); scanf("%d", &k);
							 cautare();
							 if(r!=NULL)
								 printf("Informatia din nodul cu cheia \"%d\" este : %s\n", k, r->info);
								 else printf("Nu exista nici un nod cu cheia \"%d\" !\n", k);
							 break;
			case 'V':
				delete_lista();
				printf("Spatiul ocupat de l.l.d.i a fost eliberat!\n");
				break;
			default:
				printf("Comanda gresita!\n");
				break;
		}
	printf("Apasati o tasta pt. a continua!");
  getch();system("cls");
	}
	while(c!='E');
	delete_lista();
	printf("Spatiul ocupat de l.l.d.i. a fost eliberat\n");
}

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

	printf("Introduceti primul nod al l.l.d.i.\n");
	insd_p();
	printf("Continuati(D/N) : ");
	fflush(stdin); scanf("%c", &c); c = toupper(c);
	while(c=='D')
	{
		insd_cf();
		printf("Continuati(D/N) : ");
		fflush(stdin); scanf("%c", &c); c = toupper(c);
	}
}/*sfarsit creare*/

void insd_p(void)
	{
		p = malloc(sizeof(Tnod));/*2*/
		printf("Introduceti cheia : ");scanf("%d",&p->cheie); /*2*/
		printf("Introduceti informatia : ");
		fflush(stdin); scanf("%s", p->info);/*2*/
		p->urm = NULL; /*3*/
		p->ant = NULL; /*4*/
	}

void insd_cf(void)  /*insereaza un nod in fata unei l.l.d.i.*/
	{
		q = (ref)malloc(sizeof(Tnod));
		printf("Introduceti cheia nodului : ");
		fflush(stdin); scanf("%d", &q->cheie);
		printf("Introduceti informatia utila : ");
 		fflush(stdin); scanf("%s", q->info);
		q->urm = p;
		q->ant = NULL;
 		p->ant = q;
		p = q;
	}/*sfarsit insd_cf*/

void insd_d(void)/*inserarea unui nod dupa un nod dat intr-o l.l.d.i.*/
	{
		ref s,succ;
		succ = r->urm; /*1*/
		s = malloc(sizeof(Tnod));/*2*/
		printf("Introduceti cheia : ");scanf("%d",&s->cheie); /*2*/
		printf("Introduceti informatia : ");
		fflush(stdin); scanf("%s", s->info);/*2*/
		s->ant = r;/*3*/
		s->urm = succ;/*4*/
		r->urm = s; /*5*/
		if(succ!=NULL)
			succ->ant = s;/*6*/
	}/*sfarsit insd_d*/

void insd_i(void)/*inserarea unui nod in fata unui nod dat intr-o l.l.d.i.*/
	{
		ref s,pred;
		pred = r->ant; /*1*/
		s = malloc(sizeof(Tnod));/*2*/
		printf("Introduceti cheia : ");scanf("%d",&s->cheie); /*3*/
		printf("Introduceti informatia : ");
		fflush(stdin); scanf("%s", s->info);/*3*/
		s->ant = pred;/*4*/
		s->urm = r;/*5*/
		r->ant = s;/*6*/
		if(pred!=NULL)
			pred->urm = s;/*7 *r nu eprimul, are predecesor*/
			else p = s;   /*7 *r nu are predecesor, *s devine primul */
	}/*sfarsit insd_i*/

void suprima(void) /*suprima nodul referit de *r*/
	{
		ref pred, succ;
		pred = r->ant; /*1*/
		succ = r->urm; /*2*/
		if(r->ant!=NULL) pred->urm =succ; /*3*/
		if(r->urm!=NULL) succ->ant =pred; /*4*/
		if(r==p)
			p=p->urm;
		free(r);
	}/*sfarsit suprima*/

void listare(void) /*listeaza elementele l.l.d.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*/

void cautare(void) /*cauta nodul cu cheia k*/
{
	int b = 0;
	r = p;
	while((b==0) && (r!=NULL))
		if(r->cheie == k)
			b=1;
			else r = r->urm;
}/*sfarsit cautare*/

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*/