Podstawowe struktury danych

1) Listy

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

1

, x

2

, ... , x

n

].

Skrajne elementy x

1

i x

n

nazywamy końcami listy, a

wielkość |q| = n długością (rozmiarem) listy.
Szczególnym przypadkiem jest lista pusta: q = [ ].

Podstawowe abstrakcyjne operacje na listach
q =[x

1

, x

2

, ... , x

n

] i r =[y

1

, y

2

, ... , y

m

] dla 1

≤ i ≤ j ≤ n to:

• dostęp do elementu listy - q[i] = x

i

;

• podlista - q[i..j] = [x

i

, x

i+1

, ... , x

j

] ;

• złożenie - q&r = [x

1

, ... , x

n

, y

1

, ... ,y

m

] ;

Na podstawie operacji podstawowych można zdefiniować
inne operacje, np. wstawianie elementu x za element x

i

, na

liście q: q[1..i] & [x] & q[i+1 .. |q| ].

W operacjach na listach ograniczamy się zwykle do zmian
ich końców:
a)

front(q)

= q[1] - pobierz lewy koniec listy

b)

push(q,x)

= [x]&q - wstaw element na lewy koniec

c)

pop(q)

=q[2..|q| ] - usuń bieżący lewy koniec

d)

rear(q)

= q[|q|] - pobierz prawy koniec listy

e)

inject(q,x)

=q&[x] -wstaw element na prawy koniec

f)

eject(q)

=q[1..|q|-1 ] - usuń bieżący prawy koniec

W zależności od możliwości wykonania różnych operacji
wyróżniemy:
•

kolejkę podwójną

- wszystkie sześć operacji

•

stos

- tylko operacje front, push, pop

•

kolejkę

- tylko operacje front, pop , inject

Dwie podstawowe implementacje (reprezentacje) listy
q =[x

1

, x

2

, ... , x

n

] to:

• tablicowa - q[i] = x

i

, gdzie 1

≤

i

≤

n,

• dowiązaniowa

W implementacjach pojedynczej liniowej i podwójnej
liniowej dowiązanie prowadzące do listy wskazuje na
pierwszy element na liście.

W implementacji pojedynczej cyklicznej i podwójnej
cyklicznej dowiązanie prowadzące do listy wskazuje na
element ostatni.

Aby dowiązana struktura nigdy nie była pusta dodaje się
na początku listy element pusty zwany

GŁOWĄ

lub

WARTOWNIKIEM

listy.

Operacje na listach o stałej złożoności czasowej:
a) w implementacji pojedynczej liniowej: operacje stosu,

wstawianie jednego elementu za drugi, usuwanie
następnego elementu,

b) w implementacji pojedynczej cyklicznej: te co w a) oraz

złożenie i operacje rear i inject,

c) w implementacji podwójnej cyklicznej: te co w b) oraz

eject, wstawianie jednego elementu przed drugim,
wstawianie danego elementu, odwracanie listy.

LISTY JEDNOKIERUNKOWE

Lista jednokierunkowa jest oszczędną pamięciowo
strukturą danych, pozwalającą grupować dowolną -
ograniczoną tylko ilością dostępnej pamięci - liczbę
elementów: liczb, znaków, rekordów.

Do budowy listy używane są dwa typy rekordów:
-

informacyjny

- wskaźniki, dowiązania do początku listy

(głowa) i końca listy (ogon)

-

robocze

- pole wartości i wskaźnik do następnego

elementu listy

Dzięki rekordowi informacyjnemu mamy ciągły dostęp do
niektórych operacji, np. dołączanie elementu na koniec
listy.

Głowa, ogon i następny

to wskaźniki,

wartość

to dowolna

wielkość (znanego typu).

Wskaźniki NULL oznaczają adresy pamięci pod którymi
nie ma żadnej zmiennej.

Przykład listy jednokierunkowej:

Pola głowa i ogon pozwalają na przeglądanie elementów
listy i dołączanie nowych elementów.

Przykład (pseudokod) przeglądania elementów listy:
_________________________________________________
adres_tmp=info.głowa;
while

(adres_tmp <> NULL )

{
if(adres_tmp.wartość == x)
{
Wypisz "Znalazłem szukany element"
opuść procedurę
}

else

adres_tmp=adres_tmp.następny

}
Wypisz

"Nie znalazłem elementu"

_________________________________________

Dokładanie nowych elementów (dwa podejścia):
1)potraktowanie listy jak worek nie-uporządkowanych
elementów i umieszczanie nowych elementów na
początku

2) dokładanie elementów we właściwym ustalonym przez

użytkownika porządku (całość listy musi być widziana
jako posortowana)

Możliwe są trzy przypadki:

a) wstawiamy element na początek listy

b) wstawiamy element na koniec listy

c) wstawiamy element gdzieś w środku

W każdym z przypadków musimy zapamietywać dwa
wskaźniki - przed który element wstawić i po którym
mamy to zrobić.

Podobnie postępujemy przy fuzji (łączeniu) list tak by
wypadkowa lista pozostała uporządkowana.

Podsumowując wady i zalety list jednokierunkowych:

Wady Zalety

nienaturalny dostęp do

elementów

małe zużycie pamięci

niełatwe sortowanie

elastyczność

Lista w której elementy są już na samym początku
wstawiane w określonym porządku, służy obok
gromadzenia danych, także do ich porządkowania.

W sytuacji, gdy jest tylko jedno kryterium sortowania
struktura działa bardzo dobrze "sama" dbając o
sortowanie.

Dla kilku kryteriów sortowania należy wprowadzić obok
listy danych, także kilka list z wskaźnikami do danych - list
tych powinno byś tyle ile kryteriów sortowania.
Sortowanie w takich wypadku polega na porządkowaniu
wskaźników bez ruszania listy danych.

Nieposortowaną listę DANE można uporządkować według

zech kryteriów:

tr

- imienia i nazwiska (Adam Fuks, Jan Kowalski, Michał

Zaremba)

- kodów ( 30, 34, 37)
- kwot ( 1200, 2000, 3000 )

Tablicowa implemantacja list jest niezwykle prosta jeśli
umówimy się, że i-temu indeksowi tablicy odpowiada i-ty
element listy. Wymagana jest dodatkowa informacja
wskazująca jak wiele elementów liczy lista (jak duża musi
być tablica).

Wadą jest marnotrawstwo pamięci bo najczęściej
przydzielamy na tablicę większy obszar pamięci niż to
zwykle potrzeba.

Operacje na listach są w implementacji tablicowej proste:
1)

front(q)

, x=q[1]

- pobierz lewy koniec listy

2)

push(q,x)

- przesuń wszystkie elementy tablicy o jeden w

prawo i

q[1]=x

- wstaw element na lewy koniec

3)

pop(q)

, przesuń wszystkie elementy tablicy poza

pierwszym o jeden w lewo - usuń bieżący lewy koniec

4)

rear(q), x=q[n]

- pobierz prawy koniec listy

5)

inject(q,x), q[n+1]=x

-wstaw element na prawy koniec

6)

eject(q), n=n-1

- usuń bieżący prawy koniec

Dodatkowo:

A) usunięcie k-tego elementu to - przesunąć w lewo

elementy tablicy q[k+1]...q[n], n=n-1

B) wstawienie elementu na pozycję k to - przesunąć w

prawo elementy tablicy q[k]...q[n], n=n+1

LISTY DWUKIERUNKOWE

Listy jednokierunkowe są wygodne i zajmują mało
pamięci. Operacje na nich zajmują dużo czasu.

W liście dwukierunkowej komórka robocza zawiera
wskaźniki do elementów: poprzedniego i następnego .
• pierwsza komórka na liście nie posiada swojego

poprzednika (pole poprzedni zawiera NULL wskaźnik
pokazujący pusty element pamięci)

• ostatnia komórka na liście nie posiada swojego

następnika (pole następny zawiera NULL wskaźnik
pokazujący pusty element pamięci)

Lista dwukierunkowa jest kosztowna jeśli chodzi o pamięć,
ale wygodna gdy chodzi o szybkość.

Usunięcie elementu listy dwukierunkowej:

Lista cykliczna jest zamknięta w pierścień , wskaźnik
„ostatniego” elementu wskazuje na „pierwszy” element.

Elementy „pierwszy” i „ostatni” są umowne.

STOSY

Stos jest struktura danych, do której dostęp jest możliwy
tylko od strony tzw. wierzchołka, czyli pierwszego wolnego
miejsca znajdującego się na nim.

Funkcje odkładania elementu X na stos (

push(X)

) i

pobieranie go ze stosu (

pop(X)

) można opisać

symbolicznie (wraz z kodem błędu s wprowadzonym przez
użytkownika):

Tablicowa implementacja stosu wygląda analogicznie jak
dla listy, ale z dostępnymi jedynie operacjami

front

,

push

,

pop

.