Vektory, Seznamy a Sekvence
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Vektory - ADT
•Rozšiřují pojem pole ukládáním sekvence libovolných objektů
•Prvek může být čten, vkládán a odebírán pomocí určení jeho pořadí
•Operace s vektorem:
•object elemAtRank (integer r)
•object replaceAtRank (integer r, object o)
•insertAtRank(integer r, object o)
•object removeAtRank(integer r)
•Pomocné operace
•integer size() boolean isEmpty()

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Vektory - ADT
•Výjimky
•Nesprávný index prvku (záporný index…)
•Aplikace
•Přímé
•Tříděná kolekce objektů (základní databáze)
•Nepřímé
•Pomocná datová struktura pro algoritmy
•Části jiných datových struktur

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Vektory – implementace pomocí pole
•Použití pole V o délce N
•Proměnná n určuje délku vektoru
•Operace isEmpty(), elemAtRank(r), replaceAtRank(r, O) - časová náročnost O(1)
•Operace insertAtRank(r, O) - časová náročností O(n)
•Operace removeAtRank(r) - časová náročností O(n)
•
•
V
0
1
2
n
r

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Seznam – ADT
•Posloupnost pozic ukládajících libovolná data
•Zavádí vztahy před/po mezi pozicemi
•
•
•Aktualizační operace
•replaceElement(p, o), swapElements(p, q), insertBefore(p, o), insertAfter(p, o), insertFirst(o),
insertLast(o), remove(p)
•
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Seznam
•Single linked list – jednosměrný spojový seznam
•Prvek obsahuje odkaz pouze na následují uzel
•Lze použít pro implementaci zásobníku  (O(n) pro paměť, O(1) pro každou operaci) i fronty (O(n)
pro paměť, O(1) pro každou operaci)
•
•
•Double linked list – obousměrný spojový seznam
•Prvek obsahuje odkaz na předcházející i následující uzel
následující
hodnota
uzel
předchozí
následující
hodnota
uzel

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Sekvence – ADT
•Spojení Vektoru a Seznamu
•Přístup k prvkům pomocí pořadí nebo pozice
•Obecné operace
•size(), isEmpty()
•Vektorové operace
•elemAtRank (r), replaceAtRank (r, o), insertAtRank(r, o), removeAtRank(r)
•Seznamové operace
•first(), last(), before(), after(), replaceElement(p, o), swapElements(p, q), insertBefore(p, o),
insertAfter(p, o), insertFirst(o), insertLast(o), remove(p)
•Propojující operace
•atRank(r), rankOf(p)

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Sekvence
•Základní, obecně použitelný datový typ pro ukládání uspořádaného souboru prvků
•Aplikace
•Přímé
•Obecná náhrada za zásobník, frontu, vektor, nebo seznam
•Malá databáze
•Nepřímé
•Stavební blok pro komplexnější datové struktury