Matematyka dyskretna 2004 - 07 Stosy, kolejki i drzewa.pdf

(83 KB) Pobierz
41217389 UNPDF
Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Stosy, kolejki i drzewa
1.1 Listy
Lista to uporz adkowany ci ag elementów. Przykładami list s a tablice jednowymiarowe. W
tablicach mamy dostep do dowolnego elementu, poprzez podanie indeksu tego elementu.
Przykład 1.1 W jezyku Pascal przykładem typu tablicy jednowymiarowej jest
array[1..N] of integer.
Jezeli mamy zmienn a tego typu
a:array[1..N] of integer,
to tablica a zawiera N elementów
a[1], a[2], ... ,a[N].
W programie mozemy odwoływac sie do całej tablicy, na przykład w instrukcji przypisania
a:=b,
lub do pojedynczych elementów:
a[i]:=a[i+1].
Mozemy takze uzywac tablic dwu lub wiecej wymiarowych. Przykładem tablicy dwuwy-
miarowej jest typ
array[1..N,1..M] of real.
Zmienna
c:array[1..N,1..M] of real
zawiera NM elementów. Dla kazdej pary liczb i; j spełniaj acej warunki 1iN ,
1jM , element c[i,j] zawiera liczbe typu real.
1.2 Stosy i kolejki
Czasami wygodniej posługiwac sie listami bez uzywania indeksów. Przykładami list, któ-
rych mozna uzywac bez koniecznosci odwoływania sie do indeksów poszczególnych ele-
3
4
Rozdział 1. Stosy, kolejki i drzewa
mentów, s a kolejki i stosy.
Definicja 1.2 Kolejka jest list a z trzema operacjami:
dodawania nowego elementu na koniec kolejki,
zdejmowania pierwszego elementu z pocz atku kolejki,
sprawdzania, czy kolejka jest pusta.
Taki sposób dodawania i odejmowania elementów jest okreslany angielskim skrótem
FIFO ( first in first out, czyli pierwszy, który wszedł, pierwszy wyjdzie). Przykłady kolejek
spotykamy w sklepach, gdzie klienci czekaj acy na obsłuzenie tworz a kolejki.
Definicja 1.3 Stos jest list a z trzema operacjami:
dodawania elementu na wierzch stosu,
zdejmowania elementu z wierzchu stosu,
sprawdzania, czy stos jest pusty.
Na stosie dodajemy i odejmujemy elementy z tego samego ko nca, podobnie jak w
stosie talerzy spietrzonym na stole. Talerze dokładane s a na wierzch stosu i zdejmowane
z wierzchu stosu. Taka organizacja obsługi listy okreslana jest angielskim skrótem LIFO
( last in first out, czyli ostatni, który wszedł, pierwszy wyjdzie). Niektórzy w ten sposób
organizuj a prace na biurku. Przychodz ace listy układaj a na stosie i jak maj a czas, to zdej-
muj a jeden list i odpowiadaj a na niego.
Przyjrzyjmy sie zastosowaniu kolejki lub stosu do szukania. Przypuscmy, ze szukamy
przez telefon pewnej informacji (na przykład chcielibysmy sie dowiedziec, kto z naszych
znajomych ma pewn a ksi azke).
Algorytm szukania ksi azki wsród znajomych
tworzymy STOS, który na pocz atku jest pusty,
wkładamy na STOS numery telefonów swoich znajomych,
dopóki na stosie s a jakies numery, powtarzamy:
zdejmujemy z wierzchu STOSU jeden numer telefonu,
dzwonimy pod ten numer,
jezeli osoba, do której sie dodzwonilismy, posiada szukan a ksi azke,
to koniec poszukiwa n,
w przeciwnym przypadku
pytamy j a o znajomych, którzy mog a miec ksi azke
numery tych znajomych s a dopisywani na STOS.
W powyzszym algorytmie zamiast stosu moze by c uzyta kolejka.
1.3. Implementacja stosu
5
1.3 Implementacja stosu
W wielu jezykach programowania stosy i kolejki nie wystepuj a jako standardowe struktu-
ry danych. W tym i nastepnym podrozdziale pokazemy jak mozna je utworzy c za pomoc a
tablic.
Tworzymy tablice
ST OS[0::max]
oraz zmienna W ierzchStosu . W tablicy przechowujemy elementy stosu. Element ST OS[0]
lezy na dnie stosu, a kolejne elementy nad nim. Zmienna W ierzchStosu wskazuje na
pierwsze wolne miejsce w tablicy ST OS . W pustym stosie W ierzchStosu = 0 . Opera-
cja włozenia nowego elementu x na ST OS implementujemy za pomoc a instrukcji:
ST OS[W ierzchStosu] := x;
W ierzchStosu := W ierzchStosu + 1;
Tak skonstruowany stos moze pomiescic co najwyzej max + 1 elementów. Jezeli
W ierzchStosu = max + 1 , to stos jest pełny i nie mozna na niego wkłada c nowych
elementów. Operacja zdejmowania elementu z wierzchu ST OSU implementujemy za
pomoc a instrukcji:
W ierzchStosu := W ierzchStosu1;
x := ST OS[W ierzchStosu];
Operacje t a mozna wykonac, jezeli stos nie jest pusty, to znaczy jezeli W ierzchStosu >
0 .
1.4 Implementacja kolejki
Kolejke tez mozna utworzyc za pomoc a tablicy. W tym celu deklarujemy tablice
KOLEJKA[0:::max]
oraz dwie zmienne P oczatekKolejki , KoniecKolejki . W tablicy przechowujemy ele-
menty kolejki. Zmienna P oczatekKolejki wskazuje na pierwsze element kolejki, a zmien-
na KonieckKolejki na pierwsze wolne miejsce za kolejk a. Kolejka jest pusta, jeze-
li P oczatekKolejki = KonieckKolejki . Operacja włozenia nowego elementu x do
KOLEJKI implementujemy za pomoc a dwóch instrukcji:
KOLEJKA[KoniecKolejki] := x;
KoniecKolejki := KoniecKolejki + 1;
Operacja zdejmowania elementu z ko nca KOLEJKI implementujemy za pomoc a in-
strukcji:
x := KOLEJKA[P oczatekKolejki];
P oczatekKolejki := P oczatekKolejki + 1;

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin