3. Jednosmerný lineárny zoznam

3.2  Vytvorenie zoznamu, pridanie nového prvku

Kvôli zjednodušeniu budeme pracovať s lineárnym zoznamom znakov. Najskôr si definujme vhodné typy a deklarujme potrebné premenné - ukazovatele, pomocou ktorých budeme so zoznamom pracovať:

#include <stdlib.h>

typdef struct prvok {
  int hodnota;
  struct prvok *dalsi;
} TPrvok;

TPrvok *z, *k, *p; 

Deklarovali sme 3 pointery: jeden bude ukazovať na začiatok zoznamu, druhý na koniec, tretí poslúži v prípade potreby ako pomocný pointer.

Nový zoznam, ktorý bude na začiatku prázdny, vytvoríme príkazom

z = NULL;

Ak teraz chceme pridať do zoznamu prvok, ktorého hodnotovú časť prečítame zo vstupu, musíme najprv vytvoriť novú dynamickú premennú a potom zabezpečiť pripojenie nového prvku do zoznamu.

  Prvky budeme pridávať na koniec zoznamu. Kreslite si na papier ! :-)

Pridáme do zoznamu prvý prvok:

Pridanie druhého prvku

Príkazom z = (TPrvok*)malloc(sizeof(TPrvok)); by sme už navždy stratili prvý prvok, preto musíme použiť pomocný ukazovateľ:

Pridanie tretieho prvku by potom vyzeralo takto:

Tento spôsob pridávania prvkov do zoznamu je očividne dosť nepraktický, pre dlhšie zoznamy v podstate nepoužiteľný. Ak by sme totiž pridávali prvky do zoznamu týmto spôsobom, museli by sme napr. pri piatom prvku napísať:

z->dalsi->dalsi->dalsi->dalsi->dalsi = p;

čo určite nemožno pokladať za najvhodnejšie riešenie.

Oveľa výhodnejšie je mať k dispozícii nielen ukazovateľ, ktorý ukazuje na začiatok zoznamu, ale aj ukazovateľ, ktorý ukazuje na koniec, čiže posledný prvok zoznamu. Pridať nový prvok na koniec zoznamu je potom "maličkosť".

  Ukazovateľ na koniec zoznamu je možné získať aj bez toho, aby sme si ho uchovávali v samostatnej premennej. Stačí prejsť zoznamom postupne od prvého prvku (ukazovateľ na začiatok zoznamu poznáme) až po posledný !

Príslušná procedúra môže vyzerať napr. takto:

void pridaj(TPrvok **z, TPrvok **k)
{
  TPrvok *p; 
  printf("\nzadaj hodnotu prvku: ");

  if (*z == NULL) {
     *z = (TPrvok*)malloc(sizeof(TPrvok));
     (*z)->hodnota = getchar();
     (*z)->dalsi = NULL;
     *k = *z;
  }
  else {
     p = (TPrvok*)malloc(sizeof(TPrvok));
     p->hodnota = getchar();
     p->dalsi = NULL;
     (*k)->dalsi = p;
     *k = p;
  }
}

V programe potom stačí túto funkciu zavolať príkazom:

pridaj(&z, &k);

Oba parametre sú volané odkazom, t.j. po vykonaní funkcie budú obsahovať ukazovateľ na nový začiatok (v prípade pridávania prvého prvku) a nový koniec zoznamu (pridanie ďalších prvkov). Do funkcie sa ako parametre odovzdávajú adresy ukazovateľov z, k. Preto je nevyhnutné vo funkcii použiť zápis *z, *k!

Pridávaním prvkov na koniec zoznamu zachovávame aj ich poradie t.j. prvky budú v zozname uložené v takom poradí, v akom sme ich zadali zo vstupu.

Jednosmerný lineárny zoznam, ktorý bude mať 10 prvkov, môžeme teda vytvoriť napr. takto:

z = k = NULL;
for (int i = 1; i <= 10; i++) pridaj(&z, &k);

Precvičme si