--- LISTY - kody

Kilka przydatnych algorytmów na listach

Wypisywanie listy:

void write (struct list *head){

  while(head!=NULL){

    printf(„%d ”, head->key);

          head=head->key;

    }

}

Kod chyba jest łatwy do zrozumienie musimy przejść całą listę, a następnie wypisać „key” każdego elementu.

///////////////////////////////////////////////////////

Wypisywanie listy od końca (za pomocą prev):

// tylko lista dwukierunkowa

void write_prev (struct list *head){

  

  while(head->next!=NULL) head=head->next;

    // pętla przechodzi do ostatniego elementu listy

  while(head!=NULL){ // pętla ponownie przechodzi listę

     printf(„%d ”, head->key);

            head=head->prev; // tylko teraz idzie wstecz

    }

}

Kod jest podobny do wypisywania elementów w naturalnej kolejności. Natomiast wadą tego kodu jest fakt, że musimy przechodzić listę dwa razy. Dla listy która jest bardzo duża może działać wolno oraz to, że ta funkcja działa tylko dla listy dwukierunkowej.

///////////////////////////////////////////////////////

Zwracanie adresu szukanego elementu(x) (jeśli nie ma to NULL)

struct list *find(struct list *head, int x){

   while(head!=NULL && head->key!=x) head=head->next;

        

   return head;

}

Tutaj też raczej sprawa jest jasna. Przechodzimy listę za pomocą pętli i jeśli natrafimy na nasz szukany klucz lub gdy przejdziemy całą listę pętla nam wyjdzie. Następnie pozostanie nam jedynie zwrócić otrzymany adres.

///////////////////////////////////////////////////////

Wypisywanie listy rekurencyjne:

void write_rek(struct list *head){

    if(head!=NULL){

           printf(„%d ”, head->key);

           write_rek(head->next);

   }

}

Jest to przejście całej listy tylko zamiast pętli while użyłem rekurencji. Jak już wcześnie wspominałem rekurencja to też taka jakby pętla. Warunkiem stopu rekurencji jest if na samym początku. Jeśli head przejdzie cała listę to będzie wskazywał na NULL i wtedy funkcja nic nie zrobi, czyli też nie będzie jeszcze jednego wywołania i zacznie się powrót i zamykanie kolejnych wywołań.

///////////////////////////////////////////////////////

Wypisywanie listy od końca rekurencyjne:

void write_wstecz_rek (struct list *head){

  

  if(head!=NULL){

     write_wstecz_rek(head->next);

     printf(„%d ”, head->key);

    }

}

Tutaj wykorzystujemy możliwości rekurencji. A dokładnie to, że rekurencja może „wracać”. Dzięki temu ten kod działa równie dla list jednokierunkowej. Dodatkową zaletą jest fakt, że listę musimy przejść tylko raz. Tu gdy funkcja już dojedzie do warunku stopu i zacznie to zacznie wracać i dopiero wtedy będzie wypisywała elementy. Dlatego elementy są wypisywane od końca.