KMI/ZPP2 - 4. seminář - Propojené datové struktury 1

Propojené datové struktury

Na tomto semináři 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
    l2 = l1.copy()
    
    # vypíše: True (seznamy 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 prvky 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 = []
        # ověří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)

Varianty spojového seznamu

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ě.

Často používanou variantou spojového seznamu je obousměrný spojový seznam.

Cyklický obousměrný spojový seznam

    # Cyklický seznam
    HODNOTA = 0
    DALSI_PRVEK = 1
    # 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:
            seznam[DALSI_PRVEK] = [seznam[HODNOTA], seznam[DALSI_PRVEK]]
            seznam[HODNOTA] = x
            
    
    # Obousměrný spojový seznam
    PREDCHOZI_PRVEK = 0
    HODNOTA = 1
    DALSI_PRVEK = 2
    
    # funkce pro zatřízení prvku do obouseměného spojového 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