Ordonarea unei liste

 

Principiul acestei operatii este acelasi ca si la vectori. Ordonarea se poate face prin aceleasi metode. In exemplul urmator este prezentata ordonarea prin metoda Bubble Sort:

 

#include<iostream.h>

#include<conio.h>

 

struct Nod

      {int info;

       Nod *next;

       };

 

Nod *prim, *ultim;

 

void creare()

    {prim=new Nod;

     cout<<"introduceti valoarea retinuta in primul nod:";

     cin>>prim->info;

     prim->next=0; //la crearea listei va  exista un singur nod, primul si prin urmare adresa urmatoare lui este 0

     ultim=prim; //evident, avand un singur element acesta va fi si primul si ultimul

     }

 

void adaugare()

    {Nod *c;

     c=new Nod;

     cout<<"valoarea de adaugat in lista ";

     cin>>c->info;

     ultim->next=c; //se "agata" noul nod c, dupa ultimul din lista

     ultim=c; //evident noul nod e ultimul...

     ultim->next=0;//...si dupa ultimul nu e nimic, deci nici o adresa

     }

 

void ordonare()

  {Nod *c;int ord,aux;

     do

     {c=prim;

      ord=1;

      while(c->next)

             {if(c->info > c->next->info)

                        {aux=c->info;

                        c->info=c->next->info;

                        c->next->info=aux;

                        ord=0;

                        }

              c=c->next;}

      }

    while(ord==0);

  }

 

void listare()

   {Nod *c;

    c=prim;

    while(c!=0)//cat timp mai sunt in lista

      {cout<<c->info<<"  ";

       c=c->next;//avansez in lista trecand la urmatoarea adresa

       }

    cout<<endl;

       }

 

 

 

 

void main()

   {int n,i;int val,nr;

    clrscr();

    cout<<"cate elemente va avea lista?";

    cin>>n;

    creare();

    for(i=2;i<=n;i++)

      adaugare();

    cout<<"Elementele listei sunt:";

    listare();

    ordonare();

    cout<<endl<<"elementele listei dupa ordonare;"<<endl;

    listare();

    getch();

    }

 

 

Este preferabil in unele situatii sa se genereze o lista ordonata (crescator de exemplu), in functia de creare a listei avand urmatoarele situatii:

-inserarea se face inainte de primul nod (informatia mai mica decat p->info)

-inserarea se face dupa ultimul nod (informatia mai mare decat u->info)

-inserarea se face in interior

 

Iata o solutie pt. functia de creare ordonata a listei:

 

#include<iostream.h>

#include<conio.h>

 

struct nod

       {int info;

       nod* next;

       };

 

nod *p,*u;

 

void cre_ord(int x) //creare lista ordonata

{nod *c,*a;

c=new nod;

c->info=x;

if(!p)//test lista vida

   {p=new nod;

    p->info=x;

    u=p;

    u->next=0;

    }

 else

    if(x<=p->info)//inserare inainte de primul

       {c->next=p;

            p=c;}

     else

       if(x>u->info)//dupa ultimul

             {u->next=c;

              u=c;

              u->next=0;}

            else //in interior

              {

              a=p;

               while(x>a->next->info)

                  a=a->next;

               c->next=a->next;

               a->next=c;

                  }

              }

 

void afisare()

{nod *c;

 c=p;

 cout<<endl<<"continutul listei "<<endl;

 while(c)

    {cout<<c->info<<" ";

    c=c->next;}

}

 

void main()

{int n,y;

clrscr();

cout<<"nr de noduri ";

cin>>n;

for(int i=1;i<=n;i++)

   {cout<<"informatia ";

    cin>>y;

    cre_ord(y);

   }

afisare();

getch();

}

 

Probleme propuse:

 

1.Se citesc n numere din fisierul date.txt.

a)      sa se treaca numerele intr-o lista si sa se afiseze ordonate crescator

b)      elementele listei pot fi o multime?

c)      toate numerele mai mici decat 10 se maresc cu 5. Sa se afiseze din nou lista apoi sa se reordoneze

d)      sa se ordoneze lista astfel incat elementele positive sa fie ordonate crescator si cele negative descrescator

e)      sa se ordoneze lista astfel incat elementele impare sa fie ordonate crescator si cele pare descrescator

f)        sa se scrie datele in fisier

2. Sa se concateneze doua liste care retin numele si mediile elevilor din clasa  a XI-a A si clasa a XI-a D. Sa se afiseze datele descrescator dupa medie

 

3. In fisierul gr1 se gasesc numele si mediile unor studenti din grupa 1 la examenul de informatica, iar in gr2 se gasesc datele elevilor de la grupa 2.

    a) Sa se afiseze datele studentilor din cele doua grupe

    b) Sa se afiseze datele studentilor ordonate alfabetic

    c) Sa se stearga elevii respinsi (cu medii sub 5).

    d) Sa se afiseze studentii ordonati crescator dupa medie

    e) Sa se genereze o singura lista in care datele studentilor se vor afisa crescator dupa medie

 

4. Aceeasi problema ca la 3 astfel incat listele se vor genera crescator dupa medie