4. seminář - Propojené datové struktury 1

Propojené datové struktury

Na tomto semináří si vysvětlíme pojmy mělká a hluboká kopie seznamu a ukážeme, jak lze seznamy využít při implementaci propojených datových struktur

Kopie seznamu

    # seznam obsahující vnořený seznam
    l1 = [1, [2, 3, 4], 5]
    # vytvoření kopie seznamu
    l1 = l1.copy()
    
    # vypíše: True (senamy obsahují stejné hodnoty)
    print(l2 == l1)
    # vypíše: False (seznamy nejsou stejné objekty)
    print(l2 is l1)
    
    # Metoda copy ale vytváří mělkou kopii, kdy vytvoří nový seznam a do něj 
    # uloží reference na prvnky uložené v původním seznamu.
   
    # změna l2
    l2[1][1] = 0
    # ovlivní l1
    print(l1) # vypíše: [1, [2, 0, 4], 5]
    
    # Je to způsobeno tím že seznamy jsou mutabilní. 
    # V případě nemutabilních prvků jako jsou čísla k tomuto 
    # jevu nedochází.
    l1 = [1, 2, 3, 4, 5]
    l2 = l1.copy()
    l2[1]= 0
    print(l1) # vypíše: [1, 2, 3, 4, 5]
    
    
    # Řešením je hluboká kopie seznamu
    # Seznam obsahující pouze číselné seznamy a samotná čísla
    def hluboka_kopie(data):
        kopie = []
        # oveříme zda jsou data číslo (int)
        if isinstance(data, int):
            kopie = data
        # data jsou seznam
        else:
            for polozka in data:
              kopie.append(hluboka_kopie(polozka))
        return kopie

Spojový seznam

Spojový seznam (linked list) je abstraktní datová struktura uchovávající posloupnost hodnot. Každý prvek spojového seznamu uchovává hodnotu a odkaz na následující prvek seznamu.

    # Prvek spojového seznamu
    [42, []]
    
    # Seznam obsahující hodnoty [1, 2, 3]
    s = [1, [2, [3, []]]]
    
    # Přístup k prvkům
    HODNOTA = 0 # Konstanta pro hodnotu uzlu
    DALSI_PRVEK = 1 # Konstanta pro další uzel
    
    print(s[HODNOTA]) # vypíše: 1
    print(s[DALSI_PRVEK]) # vypíše: [2, [3, []]] 
 
    # funkce pro přidání prvku do seznamu
    def pridej_do_seznamu(seznam, x):
        while seznam:
            seznam = seznam[DALSI_PRVEK]
        seznam.extend([x, []])
        
    # použití funkce pridej_do_seznamu()
    seznam = []
    pridej_do_seznamu(seznam, 1)
    pridej_do_seznamu(seznam, 2)
    pridej_do_seznamu(seznam, 3)
    
    # funkce pro zatřízení prvku do seznamu
    def zatrid_do_seznamu(seznam, x):
        while seznam and seznam[HODNOTA] < x:
            seznam = seznam[DALSI_PRVEK]
            if not seznam:
                seznam.extend([x, []])
            else:
                seznam[DALSI_PRVEK] = [seznam[HODNOTA], seznam[DALSI_PRVEK]]
                seznam[HODNOTA] = x

    # použití funkce zatrid_do_seznamu()
    seznam = []
    zatrid_do_seznamu(seznam, 2)
    zatrid_do_seznamu(seznam, 1)
    zatrid_do_seznamu(seznam, 3)

Cyklický spojový seznam

Často používanou variantou spojového seznamu je cyklický spojový seznam, kde poslední prvek cyklického spojového seznamu ukazuje na první prvek. Cyklický seznam si můžeme představit následovně.

Další často používanou variantou spojového seznamu je obousměrný spojový seznam

a cyklický obousměrný spojový seznam.

    # funkce pro přidání do cyklického spojového seznamu
    def pridej_do_cyklickeho_seznamu(seznam, x):
        if not seznam:
            seznam.extend([x, seznam])
        else:
            prvni_prvek_seznamu = seznam
            seznam[DALSI_PRVEK] = [seznam[HODNOTA], seznam[DALSI_PRVEK]]
            seznam[HODNOTA] = x
            
    
    # Obousměrný cyklický seznam
    PREDCHOZI_PRVEK = 0
    HODNOTA = 1
    DALSI_PRVEK = 2
    
    # funkce pro zatřízení prvku do seznamu
    def pridej_do_obousmerneho_seznamu(seznam, x):
        predchozi_prvek = []
        while seznam:
           predchozi_prvek = seznam
           seznam = seznam[DALSI_PRVEK]
        seznam.extend([predchozi_prvek, x, []])

Úkoly