Struktury danych

Elementarne struktury danych

Piotr Prokopowicz

Plan wykładu

•Stos i kolejka

•Abstrakcyjne typy danych

(ang. abstract data

types)

•Zmienna, tablica, rekord, wskaźnik

•Listy

Podstawy

•Rekord/struktura – wiązanie pudełek (różnych)
w jedną paczkę

•Wskaźnik – gdzie jest pudełko?

•Tablica – ponumerowany szereg pudełek

•Zmienna – pudełko do przechowywania
wartości

•Struktura danych (ang. data structure) -
sposób

przechowania

i

wykorzystania

informacji w komputerze.

Zbiory dynamiczne

Wyróżnione pole obiektu (nie w każdym zbiorze) - klucz –
istotne ze względu na realizację zbioru.
W elemencie mogą być inne pola, wskaźniki, mniej lub bardziej
istotne ze względu na dostęp.

Elementem zbioru dynamicznego jest obiekt, który można
odczytać oraz zmienić, dysponując wskaźnikiem do niego.

Na zbiorach dynamicznych operują algorytmy
W odróżnieniu od zbiorów w kontekście matematycznym –
zbiory dynamiczne mogą się powiększać, zmniejszać zmieniać w
różny sposób.

Porównywalność

kluczy

(liniowy

porządek)

-

częste

przyjmowane założenie.

Typowe operacje

SEARCH(S,k) – zapytanie

Typowe operacje: zapytania, operacje modyfikujące.

S-zbiór, k-klucz, x-element lub wskaźnik do elementu, NIL(NULL) –
element nie istnieje

INSERT(S,x) – modyfikacja

DELETE(S,x) – modyfikacja

MINIMUM(S) – zapytanie

MAXIMUM(S) – zapytanie

SUCCESOR(S,x) – zapytanie o najmniejszy element większy od x

PREDECESOR(S,x) – zapytanie o największy element mniejszy
od x

Zbiory co najmniej z operacjami: INSERT, DELETE, FIND(S,x) –
słowniki.

ADT

(abstrakcyjny typ danych)

W komputerze:
Typ danych np. integer (lub int)– przechowywanie danych
Operacje – implementacja poprzez procedury
Struktura danych – przechowanie złożonej informacji w
komputerze

Przykład:
Liczby całkowite wraz z operacjami.
Argumentami operacji także mogą być ADT.
Operacje: działania matematyczne, sprawdzanie czy argument
jest liczbą całkowitą, różne działania nie tylko matematyczne
związane ze specyfiką modelu

ADT – model (bez szczegółów implementacji) z powiązaną z nim
listą operacji.
Zbiór dynamiczny w kontekście realizacji komputerowej.
Idea klasy w programowaniu obiektowym.

Lista

Lista – skończony ciąg elementów
q = [x

1

, x

2

, ... x

n

]

Skrajne elementy listy – końce : lewy - x

1

,

prawy - x

n

Wielkość listy – długość (rozmiar) |q| = n

Szczególny przypadek listy – lista pusta |q| = 0
, q=[ ]
Podstawowe operacje:

INSERT (x) – dołączenie elementu x do listy
DELETE (x) – usunięcie elementu x z listy

Stos

•Operacje na stosie:
INSERT(x) – PUSH (x) – wstawianie argumentu
operacji na stos
DELETE – POP – usuwanie – zdjęcie ze stosu

(bez

argumentu)

• Wykorzystanie stosu

•Stos (ang. last-in first-out, LIFO)

Kolejka

•Operacje na kolejce:
INSERT (x) – ENQUEUE (x) – wstawianie
DELETE – DEQUEUE – zdjęcie z kolejki

(bez

argumentu)

•Kolejka (ang. first-in first-out, FIFO)

Początek – głowa
Koniec - ogon

• Wykorzystanie kolejki

Lista z dowiązaniami

(wskaźnikowa, dynamiczna)

STATYCZNIE a DYNAMICZNIE w kontekście implementacji

Lista z dowiązaniami – elementy listy ułożone w liniowym
porządku

Porządek jest wyznaczany

(inaczej niż w tablicy, nie przez indeks)

przez wskaźniki, będące składowymi poszczególnych
elementów listy.
Pierwszy element – głowa, ostatni – ogon
Lista z dowiązaniami jest strukturą pozwalającą na
realizację wszystkich podstawowych operacji

(niekoniecznie

optymalnie)

na zbiorach dynamicznych

nil

HEAD

kluc

z

popr

z

nas

t

nil

5

20

8

Różne listy

Dwukierunkowa, jednokierunkowa

Uporządkowana, posortowana – kolejność zgodna z
porządkiem na kluczach

Cykliczna – głowa wskazuje na ogon a ogon na głowę

Wartownik

–

uproszczenie

warunków

brzegowych,

skracanie czasu operacji

Struktury wskaźnikowe

Rekordy z wskaźnikami – reprezentowanie ukorzenionych
drzew binarnych

Reprezentowanie dowolnych ukorzenionych drzew

Reprezentowanie grafów

Koniec

Dziękuję za uwagę