Liste

Liste simplu înlănțuite

Listele simplu înlănțuite sunt structuri de date dinamice omogene. Spre deosebire de masive, listele nu sunt alocate ca blocuri omogene de memorie, ci ca elemente separate de memorie. Fiecare nod al listei conține, în afară de informația utilă, adresa următorului element. Această organizare permite numai acces secvențial la elementele listei.
Pentru accesarea listei trebuie cunoscută adresa primului element (numită capul listei); elementele următoare sunt accesate parcurgând lista.
Lista simplu înlănțuită poate fi reprezentată grafic astfel:

Liste dublu înlănțuite

Listele dublu înlănțuite sunt structuri de date dinamice omogene. Ele au aceleași caracteristici de bază ca și listele simplu înlănțuite. Diferența față de acestea constă în faptul că, pentru fiecare nod, se reține și adresa elementului anterior, ceea ce permite traversarea listei în ambele direcții.
Lista dublu înlănțuită poate fi reprezentată grafic astfel:

Implementare C++ Operații cu liste simplu înlănțuite:

#include <iostream.h>
#include <vector.h>
#include <algorithm>
#include <conio.h>
#include <stdio.h>
#include <string.h>
 
struct student
{
       char nume[20];
       char facultate[20];
       int varsta;
       float media;
     
      
};
 
class nod_lista
{
      private:
              student s;
              nod_lista *urmatorul; //legatura catre nodul urmator
      
             
      public:
             nod_lista * adauga_inceput (nod_lista * lis, student stud)
             {
              nod_lista * nou = new nod_lista; //aloca memorie dinamic
          
                  strcpy(nou->s.nume,stud.nume);
                  nou->s.varsta=stud.varsta;
                  strcpy(nou->s.facultate,stud.facultate);
                  nou->s.media=stud.media;
                  nou->urmatorul=lis; //leg elementul nou de primul lista
                  return nou;         //returnez element nou
             }
 
            nod_lista * adauga_sfarsit(nod_lista * nod, student stud)
            {
                      nod_lista*nou,*curent;
                      nou=new nod_lista; //alocare si initializare nod
                  
                  //atribuiri valori elem din lista                      
                  strcpy(nou->s.nume,stud.nume);
                  strcpy(nou->s.facultate,stud.facultate);
                  nou->s.varsta=stud.varsta;
                  nou->s.media=stud.media;
                      curent=nod;
                      if (nod==NULL)
                      {
                         nou->urmatorul=nod;
                         return nou;
                      }
                      //ne deplasam pe ultima pozitie a listei pt a insera
                      while (curent->urmatorul!=NULL)
                      {
                            curent=curent->urmatorul;
                      }
                      nou->urmatorul=curent->urmatorul; //noi->next= NULL
                      curent->urmatorul=nou;
                      return nod; //pointer la inceputul listei
            }
          
 
            void print_lista(nod_lista* nod)
            {
                 cout<<"Valorile sunt: "<<endl;
                 cout<<"\n\n"<<endl;
                 cout<<"Nume    Varsta  Facultate   Medie \n\n";
                 while (nod!=NULL) //cat timp mai avem elemente in lista
                 {     //afiseaza elementele curente
                       cout<<nod->s.nume<<"\t"<<nod->s.varsta<<"\t";
                       cout<<nod->s.facultate<<"\t    "<<nod->s.media<<"\n";
                       nod=nod->urmatorul;  //avanseaza la elementul urmator
                 }
                 getchar();
            }
            nod_lista * stergere_inceput(nod_lista * nod)
            {
                      nod_lista * de_sters;
                      if (nod==NULL) // daca lista e goala intorc null
                         return NULL;
                      de_sters=nod;  //setez valoarea de sters
                      nod=nod->urmatorul;    //modific inceputul
                      free(de_sters);        //sterg valoarea
                      return nod;            //intorc noul inceput
            }
            nod_lista * stergere_sfarsit(nod_lista * nod)
            {
                      nod_lista * de_sters , *curent;
                      if((nod==NULL)||(nod->urmatorul==NULL)) return NULL;
                      curent=nod;
                      //ne deplasam pana la penultima pozitie
                      while(curent->urmatorul->urmatorul != NULL)
                      {
                           curent=curent->urmatorul;
                      }
            de_sters=curent->urmatorul;             //marchez pt stergere ultimul element
                                                    //eu deja sunt pe penultimul
            curent->urmatorul=NULL; //pointez catre null de pe elementul penultim
            free(de_sters);         //sterg elementul ultim
            
            return nod;
            }                                              
             void cauta(nod_lista* nod,char *nume_cautat)
            {
                
                int gasit=0; //pozitia curenta
                
                 while (nod!=NULL) //parcurge lista pana la pozitia ceruta sau pana la sfarsitul liniei
                 {    
                      if(strcmp(nume_cautat,nod->s.nume)==0)  //daca lista continre elementul
                        {
                        cout<<"A fost gasit  " <<nume_cautat<<"   ";
                        gasit++;
                        }
                      else if(gasit==0)
                      {
                           cout<<"Nu a fost gasit  "<<nume_cautat;
                      }                    
                 nod=nod->urmatorul;        
                 }                    
                 getchar();
            }
 
nod_lista * adauga_dupa_poz_k(nod_lista * nod , student stud, int k)
{
          int poz;
          nod_lista * nou, *curent;
          nou= new nod_lista; //alocare si initializare nod
          nou->s=stud;
          curent = nod;
          poz =1;
          //dc lista e vida cream una noua          
          if ( nod == NULL) { //lista vida
                nou-> urmatorul = NULL;
                return nou;
                }
                
//iesim din ciclu fie cande se ajunge pe poz k 
// fie cand se ajunge pe ultima pozitie
 
while(curent != NULL)
{
              if (poz==k)
              {
                         //am ajuns pe poz k, adaug dupa ea si ies
                         
                         nou->urmatorul=curent->urmatorul;
                         curent->urmatorul=nou;
                         return nod;      //intoarcem pointer la inceputul listei
              }
              else
              {
                  if (curent->urmatorul==NULL)
                  {
                                         curent->urmatorul=nou;
                                         nou->urmatorul=NULL;
                                         return nod;
                  }
                  else
                  {
                      //mai am informatii in lista 
                      //trec la urmatorul mnod
                      curent=curent->urmatorul;
                  }
              }
              poz+=1;
} //daca s.a ajuns aici atunci avem o eroare
cerr<<"eroare"<<endl;
return NULL;
}
 
nod_lista * sterg_poz_k(nod_lista * nod , int k)
{
          int poz;
          nod_lista *de_sters, *curent;
          //dc clista e vida cream una noua
          if (nod==NULL) return NULL;
          
          if(k==1) return stergere_inceput(nod);  //daca este primul element, atunci il stergem si mutam capul
          curent=nod;
          poz=1;
          
          while(curent!=NULL)
          {
                             if(poz==k-1)
                             //Am ajuns la k-1 sterg el urmator si ies
                             {
                                  de_sters=curent->urmatorul;
                                  if(curent->urmatorul==NULL) return nod;
                                  //liste contine doar k-1 elemente
                                  curent->urmatorul=curent->urmatorul->urmatorul;
                                  free(de_sters);
                                  return nod;    //intorc pointer si la inc. listei
                             }
                             else //Mia ma informatii in lista ma tot duc
                             {
                                  curent=curent->urmatorul;
                             }
                             poz+=1;
                             }
                             return nod;
          }
};
           
int main()
{
    nod_lista list;
    int nr,k=0,pozitie=0;;
    char nume_cautat[20];  
    nod_lista * nod = new nod_lista;
    nod=NULL;
    student std;
    do
    {   
    cout<<"\n\n\n\n 1 - Intoducere \n 2 - Stergere \n 3 - Listare \n ";
    cout<<"4 - Cautare \n 5 - Stergere de pe pozitie k \n 6 - adaugare de pe pozitie k \n 7 - Iesire \n";
    cin>>nr;            
    switch(nr)
    {
     case 1:  
    k=0;           
    while (!feof(stdin) && k<1)
           {
          system("cls");
          cout<<"Nume student :";
          cin>>std.nume;
          cout<<"Varsta student : ";
          cin>>std.varsta;
          cout<<"Facultate : ";
          cin>>std.facultate;
          cout<<"Media : ";
          cin>>std.media;
          nod=list.adauga_inceput(nod,std); // se poate insera un meniu pentru tipul
          k=k+1;                           // de adaugare          
          system("cls");
           }
         break;
    case 2:
         nod=list.stergere_inceput(nod); // se poate insera un meniu pentru tipul
                                         // de stergere
         break;
    case 3:
         system("cls");
         list.print_lista(nod);
         break;    
    case 4:
         
         cout<<"Intoduceti numele cautat";
         cin>>nume_cautat;
         list.cauta(nod,nume_cautat);         
         break;
    case 5:        
        cout<<"Pozitie : ";
        cin>>pozitie;
        nod=list.sterg_poz_k(nod,pozitie);
        break;
    case 6:     
         cout<<"Nume student :";
          cin>>std.nume;
          cout<<"Varsta student : ";
          cin>>std.varsta;
          cout<<"Facultate : ";
          cin>>std.facultate;
          cout<<"Media : ";
          cin>>std.media;
         nod=list.adauga_dupa_poz_k(nod,std,pozitie);
         break;
    case 7:
         exit(1);
         k=9;
         break;
    }
}
    while(k<9);    
    getchar();
    return 0;
    
    
}
    

Implementare C++ Operații cu liste dublu înlănțuite:

#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
 
 
 
class lista              // Definim structura lista ce va contine nodurile
{      
		private:   
				   student * lista::student_lista;      // Definim student_lista ca un element de tip Student
				   lista * urmator,*anterior;            // Urmator va contine campurile structurii "lista" si este pointer
									   // catre un element al listei
				   char nume[20];
					char prenume[20];
					int  nrmatricol;
		   
		public:     
					
				lista * introduce_inceput(lista * info,student student_p);
				lista * introduce_sfarsit(lista * info,student student_p);
				lista * sterge_inceput(lista * info );
				lista * sterge_sfarsit(lista * info);
				void afiseaza(lista * nod);   
};                                
	
	
   lista * lista::introduce_inceput(lista * info,student student_p)        // Functie pentru introducerea de date
   {                                                                // Primeste ca parametrii info si o structura 
	   
			
	   lista * nod =new lista;                                      // Alocam dinamin un nod
	   strcpy(nod->student_lista->nume, student_p->nume);             // Copiem numele din structura primita in 
	   strcpy(nod->student_lista.prenume, student_p.prenume);
	   nod->student_lista.nrmatricol=student_p.nrmatricol;                                                             // structura numele nodului creat
	   nod->anterior=NULL;                                                             
	   nod->urmator=info;
	   if(info!=NULL)
		  info->anterior=nod;                                         
	   info=nod;                                                    // Legam elementul de capul listei
	   return nod;                                                  // si il returnam
	   
   }
   
   lista * lista:: introduce_sfarsit(lista * info,student student_p)
   {
	   
									// 2 pointeri de tip lista
	   lista * nod_nou  = new lista;                                        // Alocam dinamic un nod
	   strcpy(nod_nou->student_lista.nume, student_p.nume);         // Copiem datele necesare
	   strcpy(nod_nou->student_lista.prenume, student_p.prenume);
	   nod_nou->student_lista.nrmatricol=student_p.nrmatricol;
											  // atribuim nodului curent structura primita ca parametru
	   nod_nou->urmator = NULL;
	   nod_nou->anterior = NULL;
	   if(info==NULL)                                               // daca se afla la sfarsitul listei
			info=nod_nou;
	   else
	   {
		   lista * nod_crt = info;                       // Urmatorul element al nodului nod va "pointa" spre sfarsit
												// returnam nodul
	   
	   
	   while(nod_crt->urmator!=NULL)                             // ne deplasam spre sfarsitul listei pentru a adauga
			nod_crt=nod_crt->urmator;                          
	  
	   nod_crt->urmator=nod_nou;                        
	   nod_nou->anterior=nod_crt;
	   
	   
	   }// pointer la inceputul listei
	   return info; 
  }
					 
   lista * lista::sterge_inceput(lista * info )
   {
		 
		 lista * nod_de_sters;                                      // In caz de lista este goala returnez NULL
		 if (info==NULL) return NULL;  
		 nod_de_sters=info;                                         // nodul ce urmeaza a fi sters
		 info=info->urmator;                                        // Inceputul devine urmatorul element (al 2-lea)
		 delete nod_de_sters;                                       // Stergem valoarea
		 return info;                                               // Returnam inceputul listei
   }
   
   lista * lista::sterge_sfarsit(lista * info)
   {
		 lista *nod_de_sters,*nod_curent;
		 
		 if((info==NULL)||(info->urmator==NULL)) return NULL;        // Verificam daca lista este goala
		 
		 
		 nod_curent=info;                                            // Preluam informatiile din nod
		 
		 while(nod_curent->urmator->urmator != NULL)                 // Deplasare spre penultima pozitie
		 {
			nod_curent=nod_curent->urmator;    
		 }
		 
		 nod_de_sters=nod_curent->urmator;                           // Ultimul element (ce trebuie sters)
		 nod_curent->urmator=NULL;                                   // elementul penultim pointeaza catre NULL
		 delete nod_de_sters;
		 return info;
   }
 
   void afiseaza(lista * nod)                                       // Functie pentru afisarea listei
   {
 
	  system("cls"); 
	  cout<<"Lista contine urmatoarele date : \n\n";
	  cout<<"Nume \t Prenume Numar Matricol \n";
 
		 while(nod)                                                // Atat timp cat nod nu este NULL (adica sfarsitul listei)
		 {  
		 cout<<nod->student_lista.nume<<" \t ";                    // Afisam cate un element
		 cout<<nod->student_lista.prenume<<" \t ";   
		 cout<<nod->student_lista.nrmatricol<<endl;
 
		 nod=nod->urmator;                                          // si trecem la urmatorul 
		 }
   }
		
 
int main ()
{
   int caz;
   student student_main;                                            // un nou element de tip Student
   lista * nod_main = new lista;                                    // Alocam dinamic un nod
   nod_main=NULL;													// Setam nod ca fiind sfarsitul listei
   do
   {
																 
	   cout<<"\n\n\n 1 - Introducere inceput \n 2 - Introducere sfarsit \n";
	   cout<<" 3 - Stergere inceput\n 4 - Stergere sfarsit\n 5 - Afiseaza lista\n 6 - Iesire\n";                      
	   cin>>caz;
	   switch (caz)
	   {
			  case 1:
			   system("cls");	
			   cout<<" Nume: ";
			   cin>>student_main.nume; 
			   cout<<"\n Prenume: ";
			   cin>>student_main.prenume;
			   cout<<"\n Numar Matricol: ";
			   cin>>student_main.nrmatricol;
			   nod_main=introduce_inceput(nod_main,student_main);           // Nod_main va prelua valoarea returnata de functie 
			   break;     
																  
			  case 2:
			   system("cls");	
			   cout<<" Nume: ";
			   cin>>student_main.nume; 
			   cout<<"\n Prenume: ";
			   cin>>student_main.prenume;
			   cout<<"\n Numar Matricol: ";
			   cin>>student_main.nrmatricol;
			   nod_main=introduce_sfarsit(nod_main,student_main);    
			   break;
			  case 3:
			   system("cls");
			   nod_main=sterge_inceput(nod_main);
			   break;
			  case 4:
			   system("cls");
			   nod_main=sterge_sfarsit(nod_main);
			   break;
			  case 5:
			   afiseaza(nod_main);
			   break;
			  case 6: 
				   caz=6;  
				   
		}
   } 
    while(caz!=6);
	getchar();
	getchar();
	return 0;
}