Limbajul C. Sortarea unei liste

Este vorba despre o lista simplu inlantuita (LSI), ale carei noduri servesc drept container pentru valori numerice (numere intregi in cazul de fata). Sigur ca se poate obiecta ca e un efort inutil sa scrii cod pentru a sorta secvente de numere intregi folosind structuri, recte LSI. 

Exista varianta binecunoscuta de sortare folosind vectori sau tablouri monodimensionale drept container.

Totusi, structura fiind un tip de data definit de utilizator, este mai flexibila decat un tablou, fie si prin faptul ca un nod al listei, spre deosebire de elementul unui tablou, poate contine mai mult de o variabila de baza la un moment dat.

Ne putem imagina, de pilda, o LSI care stocheaza in fiecare nod trei intregi corespunzand unei date calendaristice: ziua, luna, anul.

Intr-un astfel de caz, LSI este optiunea naturala, in detrimentul celei cu tablouri.

Sortarea unei astfel de liste ar trebui gandita dupa urmatorul algoritm:

- daca valoarea-an din nodul curent este mai mica decat valoarea-an din nodul urmator, atunci se trece la nodul urmator; altfel,

- daca valoarea-an din nodul curent este mai mare decat valoarea-an din nodul urmator, atunci se interschimba toate cele trei valori; altfel,

- daca valorile-an sunt egale si daca valoarea-luna din nodul curent este mai mare decat valoarea-luna din nodul urmator atunci se interschimba doar valorile-luna si valorile-zi. Ex: daca avem nodul 1(1997, 4, 27) si nodul 2(1997, 3, 31) se interschimba martie cu aprilie (4 cu 3) si 27 cu 31; altfel,

- daca valorile-luna sunt deja ordonate strict crescator atunci se trece la nodul urmator in conditiile in care am stabilit ca anii sunt egali; altfel,

- daca valorile-luna sunt egale iar valorile-zi sunt in ordine inversa atunci se interschimba aceste ultime doua valori; altfel se trece la urmatorul nod.

Codul urmator, dupa cum am precizat, trateaza un caz mai simplu - sortarea urmatoarei liste:

struct s

{
  int x;

  struct s * next;

} head;

struct s * phead = &head;

Sortarea se face trivial, dupa metoda bubble-sort, optiunea fiind justificata de simplitate, nu de eficienta.

Sunt implementate functii pentru:

- generarea nodurilor listei;

- popularea cu valori a nodurilor listei;

- afisarea valorilor continute in nodurile listei;

- sortarea valorilor stocate in nodurile listei;

- dealocarea spatiului alocat dinamic pentru nodurile listei.

De remarcat ca pentru functiile amintite argumentele sunt transferate prin valoare chiar daca, potrivit definitiei, parametrul formal este un pointer (la structura struct s in acest caz). 

Intr-adevar, daca luam cazul unei functii oarecare void Function(struct s * ptr) si ii furnizam ca argument capatul listei,

struct s head;

struct s * phead = &head;

in blocul functiei se va lucra pe o copie a lui phead. Insa doi pointeri cu aceeasi valoare (care indica spre aceeasi adresa de memorie) dau, prin dereferentiere, acelasi rezultat.

Acesta este motivul pentru care in interiorul blocului functiei putem altera valorile indirectate de phead, fara a avea pretentia ca alteram insasi valoarea continuta (adresa nodului indirectat) de phead J 

Daca am fi dorit in mod specific acest lucru, ar fi trebuit sa definim functia (functiile) astfel incat argumentul formal sa fie un pointer la pointer la structura (dubla indirectare). 

Cu o astfel de situatie ne intalnim atunci cand, de pilda, vrem sa inseram un nod inaintea capului listei. Insa aceste aspecte nu fac obiectul codului de mai jos.

// sortarea unei liste

#include <stdio.h>

struct s

{

            int x;

            struct s * next;

};

void display(struct s *);

void Bsort(struct s *);

void Input(struct s *);

void AdaugNod(struct s *, int n);

void Dellist(struct s *);

int main(void)

{

            int nnod;

            struct s * phead;

            puts("Cream capul listei.");

            phead = (struct s *)malloc(sizeof(struct s));

            puts("Dupa capatul listei adaugam inca un numar de noduri:");

            scanf("%d", &nnod);

            AdaugNod(phead, nnod);

            Input(phead);

            display(phead);

            puts("Vom sorta/rearanja crescator valorile x in nodurile listei.");

            Bsort(phead);

            display(phead);

            puts("\nVom elibera spatiul alocat dinamic pentru lista.");

            Dellist(phead);

            phead = NULL;

            //display(phead);

           return 0;

}

void display(struct s * phead)

{

            int i = 0;

            printf("\n");

            while(phead != NULL)

    {

      printf("Nodul %d: %d.\n", i + 1, phead->x);

      phead = phead->next;

      i++;

    }      

    printf("\n");

}

void Bsort (struct s * phead)

{

     int aux, temp;

     struct s * iter;

     do

             {

        aux = 0;

        iter = phead;

        while(iter->next != NULL)

        {

         if(iter->x > iter->next->x)

                                    {

                                                aux = 1;

                                                temp = iter->x;

                                                iter->x = iter->next->x;

                                                iter->next->x = temp;

                                    }

         iter = iter->next;

                        }

            }

    while(aux);

}

void Input(struct s * phead)

{

    int i = 0;

    printf("\n");

            while(phead != NULL)

            {

                        printf("Initializam membrul intreg al nodului %d cu valoarea: ", i + 1);

                        scanf("%d", &(phead->x));

                        _flushall();

                        phead = phead->next;

                        i++;

            }

}

void AdaugNod(struct s * phead, int n)

{

    //struct s * iter = phead;

            while(n)

            {

                        phead->next = (struct s *)malloc(sizeof(struct s));

                        phead = phead->next;

        phead->next = NULL;

                        n--;

            }

}

void Dellist(struct s * phead)

{

            struct s * current;

            while(phead != NULL)

            {

                        current = phead;

                        phead = phead->next;

                        free(current);

            }

}