20. cvičení

Spojový seznam

Dokončení spojového seznamu z předchozího cvičení.

Funkce pro hledání daného prvku v seznamu.

Při hledání prvku se zadanou hodnotou v seznamu použijeme stejný cyklus jako ve funkci pro výpis prvků seznamu, ale při nalezení prvku přímo vrátíme aktuální prvek. Pokud celý cyklus proběhne až do konce a žádný vyhovující prvek nenajdeme, vrátíme nulový ukazatel.

uzel* najdi(spojovy_seznam s, float c)
{
    uzel* aktualni = s.zacatek;
    while (aktualni != NULL) {
        if (aktualni->cislo1 == c)
            return aktualni;
        aktualni = aktualni->naslednik;
    }
    return NULL;
}

Funkce pro vložení nového prvku za daný prvek.

Nejprve vytvoříme nový prvek pomocí funkce z předchozího cvičení a poté jej vložíme do seznamu – ukazatele na následující prvky nastavíme podobně jako při vkládání prvku na konec seznamu.

void vloz_za(uzel* u, float c1, float c2)
{
    // dynamicka alokace
    uzel* novy = vytvor_prvek(c1, c2);
    if (novy == NULL)
        return;
    // vlozeni do seznamu
    novy->naslednik = u->naslednik;
    u->naslednik = novy;
}

Funkce pro vložení nového prvku před daný prvek.

Vložit prvek před daný prvek jednosměrně zřetězeného spojového seznamu nelze provést stejným postupem jako při vkládání za daný prvek, protože nemáme přímý odkaz na předchozí prvek a hledání předchůdce pomocí procházení seznamu od začátku by bylo zbytečně neefektivní. Elegantní varianta spočívá v tom, že nový prvek nejprve vložíme za daný prvek, a poté přehodíme hodnoty ve dvou následujících prvcích, aby byly v seznamu v požadovaném pořadí.

void vloz_pred(uzel* u, float c1, float c2)
{
    vloz_za(u, c1, c2);
    // vymenit hodnoty mezi u a jeho naslednikem
    u->naslednik->cislo1 = u->cislo1;
    u->naslednik->cislo2 = u->cislo2;
    u->cislo1 = c1;
    u->cislo2 = c2;
}

Funkce pro smazání daného prvku ze seznamu.

Pokud chceme z jednosměrně zřetězeného seznamu smazat nějaký prvek, nelze to provést jednoduše, protože nemáme přímý přístup k předchozímu prvku, kde je třeba aktualizovat ukazatel na následníka. Proto se používá podobný trik jako při vkládání před daný prvek:

  1. Prostřední prvek, který chceme smazat, označíme jako u, jeho následníka označíme jako n1 a následníka prvku n1 označíme jako n2.
  2. Přesuneme data z prvku n1 do prvku u (tím „smažeme“ původní data prvku u, čehož jsme chtěli dosáhnout).
  3. Aktualizujeme ukazatel, aby následník prvku u byl prvek n2.
  4. Dealokujeme prvek n1.

Tímto postupem lze smazat libovolný prvek jednosměrně zřetězeného spojového seznamu s výjimkou posledního prvku.

void smaz_uzel(uzel* u)
{
    if (u->naslednik == NULL) {
        printf("Neumime smazat posledni prvek seznamu.\n");
    }
    else {
        // prepsat hodnoty z naslednika do u
        u->cislo1 = u->naslednik->cislo1;
        u->cislo2 = u->naslednik->cislo2;
        // zapamatovani si prvku
        uzel* puvodni_naslednik = u->naslednik;
        // prepiseme ukazatele
        u->naslednik = u->naslednik->naslednik;
        // dealokace
        free(puvodni_naslednik);
    }
}

Použití nových funkcí

Ve funkci main můžeme nové funkce použít následujícím způsobem:

// hledani prvku
float cislo = 2;
uzel* u = najdi(s, cislo);
if (u != NULL) {
    printf("nalezeno: %g, %g\n", u->cislo1, u->cislo2);
}
else {
    printf("V seznamu neni prvek s prvnim cislem rovnym %g.\n", cislo);
}

// vlozeni za nalezeny prvek
vloz_za(u, 5, 5);

// vlozeni pred nalezeny prvek
vloz_pred(u, 6, 6);

// smazani prvku
u = najdi(s, cislo);
smaz_uzel(u);

Modifikovaný spojový seznam

Ve spojovém seznamu, který jsme programovali doposud, máme jedno podstatné omezení – neumíme smazat poslední prvek seznamu. Aby bylo možné smazat libovolný prvek spojového seznamu s platnými daty, používá se modifikace obsahující jeden „prázdný“ prvek na konci seznamu. Pro tuto modifikaci je potřeba upravit (téměř) všechny doposud naprogramované funkce. Výsledný program ze cvičení si můžete stáhnout zde: modifikovany_spojovy_seznam.c.

Stručný seznam změn:

  1. Do struktury spojovy_seznam jsme přidali ukazatel na konec seznamu (tj. „prázdný“ prvek, který nemá platná data).
  2. Při vkládání nového prvku na začátek seznamu kontrolujeme, jestli existuje „prázdný“ prvek, a případně ho také vytvoříme.
  3. Při vkládání nového prvku na konec seznamu nemusíme hledat konec seznamu, ale přímo využijeme ukazatel konec.
  4. Při výpisu prvků v seznamu a při hledání ukončujeme cykly o jeden prvek dříve, abychom nepracovali s „prázdným“ prvkem.
  5. Při mazání prvku ze seznamu kontrolujeme, jestli je potřeba aktualizovat ukazatel na konec seznamu. Ukazatel na začátek seznamu se při mazání prvku nemůže změnit.