19. cvičení

Spojový seznam

Spojový seznam je dynamická datová struktura podobná poli, ale jednotlivé prvky nejsou v paměti počítače umístěny těsně vedle sebe. Namísto toho jsou jednotlivé prvky alokovány samostatně a zřetězeny pomocí ukazatelů. Běžně se používají dvě varianty spojového seznamu:

• Jednosměrně zřetězený spojový seznam: každý prvek seznamu zná svého následníka, ale ne svého předchůdce.
• Dvousměrně zřetězený spojový seznam: každý prvek seznamu zná svého následníka i předchůdce.

Práce s dvousměrně zřetězeným seznamem je jednodušší, proto se budeme v následujících cvičeních zabývat jednosměrně zřetězeným seznamem.

Pro práci se spojovým seznamem je potřeba definovat struktury pro reprezentaci jednotlivých prvků seznamu (těm budeme říkat uzel) a pro reprezentaci celého seznamu (struktura spojovy_seznam). Struktura uzel bude definována rekurzivně, protože kvůli zřetězení musí uzel obsahovat ukazatel na sebe sama. V jazyce C je tedy potřeba nejprve provést tzv. dopřednou deklaraci (v jazyce C++ to není potřeba):

// dopredna deklarace
typedef struct uzel uzel;

Poté můžeme definovat strukturu uzel, která obsahuje data (např. cislo1 a cislo2) a ukazatel na následující prvek seznamu (naslednik):

struct uzel
{
    // datove polozky
    float cislo1;
    float cislo2;
    // ukazatel na nasledujici prvek
    uzel* naslednik;
};

Struktura pro reprezentaci celého seznamu bude obsahovat pouze ukazatel na první prvek (dopředná deklarace není potřeba):

typedef struct
{
    uzel* zacatek;
}
spojovy_seznam;

Prázdný spojový seznam vytvoříme tak, že vytvoříme proměnnou typu spojovy_seznam a ukazatel na první prvek nastavíme na NULL:

spojovy_seznam s;
s.zacatek = NULL;

Pro další operace se spojovým seznamem budeme vytvářet samostatné funkce, protože operace budou komplikovanější a budeme je používat častěji.

Přidání nového prvku na začátek seznamu

Nejjednodušší operace se spojovým seznamem je přidání prvku na začátek, které lze provést pomocí následujících kroků:

1. vytvoření nového prvku a nastavení dat,
2. nastavení následníka nového prvku na původní první prvek,
3. nastavení začátku spojového seznamu na nový prvek.

Vytváření nového prvku s požadovanými daty umístíme do samostatné funkce:

uzel* vytvor_prvek(float c1, float c2)
{
    // dynamicka alokace
    uzel* novy = malloc(sizeof(uzel));
    if (novy == NULL) {
        printf("chyba alokace\n");
        return NULL;
    }
    // zapis dat
    novy->cislo1 = c1;
    novy->cislo2 = c2;
    novy->naslednik = NULL;
    return novy;
}

Výsledná funkce pro přidání prvku na začátek seznamu může vypadat např. takto:

void vloz_na_zacatek(spojovy_seznam* s, float c1, float c2)
{
    uzel* novy = vytvor_prvek(c1, c2);
    if (novy == NULL)
        return;
    // vlozeni do seznamu
    novy->naslednik = s->zacatek;
    s->zacatek = novy;
}

Poznámka: Parametr seznam je potřeba předat pomocí ukazatele, protože dochází ke změně položky seznam->zacatek, která má být viditelná i mimo tuto funkci.

Výpis prvků seznamu

Pro výpis prvků seznamu použijeme cyklus while:

void vypis_seznam(spojovy_seznam s)
{
    uzel* aktualni = s.zacatek;
    while (aktualni != NULL) {
        printf("%g, %g\n", aktualni->cislo1, aktualni->cislo2);
        aktualni = aktualni->naslednik;
    }
}

Přidání nového prvku na konec seznamu

Při přidání nového prvku na konec seznamu je potřeba odlišit situaci, kdy je seznam prázdný a kdy už obsahuje nějaké prvky. V prvním případě jednoduše vytvoříme první prvek seznamu, ve druhém je nejprve potřeba najít konec seznamu:

void vloz_na_konec(spojovy_seznam* s, float c1, float c2)
{
    if (s->zacatek == NULL) {
        vloz_na_zacatek(s, c1, c2);
    }
    else {
        // najdeme konec seznamu
        uzel* konec = s->zacatek;
        while (konec->naslednik != NULL) {
            konec = konec->naslednik;
        }
        // dynamicka alokace
        uzel* novy = vytvor_prvek(c1, c2);
        if (novy == NULL)
            return;
        // vlozeni do seznamu
        novy->naslednik = NULL;
        konec->naslednik = novy;
    }
}

Poznámka: Podmínka pro cyklus v této funkci je odlišná od podmínky ve funkci pro výpis prvků, protože potřebujeme skončit o jeden prvek dříve (po nalezení posledního prvku nesmíme přeskočit na jeho následníka).

Zrušení seznamu (dealokace)

Při dealokaci celého seznamu budeme postupně mazat první prvek, dokud to jde. Navíc potřebujeme pomocnou proměnnou pro zapamatování si následníka původního začátku seznamu.

void zrus_seznam(spojovy_seznam* s)
{
    while (s->zacatek != NULL) {
        uzel* aktualni = s->zacatek;
        s->zacatek = aktualni->naslednik;
        free(aktualni);
    }
}

Použití spojového seznamu

Spojový seznam můžeme pomocí funkcí výše používat např. takto:

int main()
{
    spojovy_seznam s;
    s.zacatek = NULL;

    vloz_na_konec(&s, 3, 3);
    vloz_na_zacatek(&s, 0, 0);
    vloz_na_zacatek(&s, 1, 0);
    vloz_na_zacatek(&s, 2, 0);
    vloz_na_konec(&s, 4, 4);
    vypis_seznam(s);

    zrus_seznam(&s);
    vypis_seznam(s);

    return 0;
}