8720

Podstawy Programowania - semestr dmgi

wartości jakie może przechowywać /mieniu tego typu. ale również operacje jakie możemy wykonywać na tych wartościach. Najprostszym przykładem abstrakcyjnej struktury danej (również struktury dynamicznej) jest stos.

3. Staś

Stos jest przypadkiem szczególnym listy liniowej⁴. Elementy stosu, w których zapisane są dane powiązane są ze sobą tworząc listę. Operacje dodawania i usuwania dotyczą tylko jednego końca tej listy. Działanie stosu określa się angielskim skrótem LIFO (ang. Last In First Out -ostatni nadszedł pierwszy wychodzi). Pojedynczy element stosu może mieć następującą strukturę:

typc

wskaż ni k"^Aclcmcnt; demem - r cc ord

dana:integer, wsk: wskaźnik;

end;

Do zdefiniowania typu pojedynczego elementu stosu posługujemy się typem rekordowym. Pole Jana może mieć oczywiście inny typ. niż len który został zaprezentowany. W zapisie obok możemy dostrzec dwa ciekawe elementy składniowe. Typ wskaźnikowy rei zmienną typu .element'* jest zdefiniowany wcześniej niż typ tej zmiennej (.element’*). Rekord zawiera pole („wsk"), które jest wskaźnikiem iu rekord tego samego typu co on. Z lego względu stos nazwany jest też strukturą rekurcncyjną. Mając określony typ elementu stosu musimy jeszcze określić procedury, które na ty m elemencie będą wykonywały operacje. Tych procedur może być kilka jednak najważniejsze z nich to „push** i .pop*’.

1    procedurę push(var x:wskaznik; y:intcgcr);

2    {Odkłada element na stos.}

3    var

4    top wskaznik;

5    begin

6    ncw(top);

7    top^A.dana:-y;

8    top' .wxk;-x;

9    x:-lop;

10    end;

Procedura ..push” umieszcza nowy element na stosie. Przez parametry pobiera wskaźnik na element, który znajduje się na szczycie stosu (.je**) oraz wartość, która ma być zapisana w elemencie („y”). Należy zwrócić uwagę, że wskaźnik jest przekazany przez zmienną, gdyż procedura będzie modyfikowała jego zawartość. Procedura posada również zmienną lokalną, która jest typu ..wskaźnik na element stosu**. W wierszu szóstym za pomocą procedury .pcw” zostaje przydzielona pamięć na nowy element stosu, którego adres zostaje zapisany w zmiennej top. W wierszu siódmym w elemencie zostaje zapisana informacja, którą ma przechowywać. Teraz należy już tylko umieścić nowy element na szczycie stosu. Najpierw musimy .połączyć” go z resztą stosu. Adres elementu, który jest bieżącym wierzchołkiem stosu jest zapisany w zmiennej jt". Należy więc zawartość tej zmiennej przepisać do pola ..wsk" nowego elementu, co też czynimy w wierszu ósmym. Po wykonaniu instrukcji zawartej w tym wierszu nowy element jest pierwszym* elementem stosu, jednakże zmienna ,.x” nic zawiera jego adresu, lecz adres elementu poprzedniego. Należy więc zmodyfikować zawartość zmiennej .,x“ i zapisać w niej adres nowego wierzchołka stosu, co zrealizowane jest w wierszy dziewiątym procedury ..push'*. Jej działanie można również zobrazować rysunkiem¹':

I. Przed wykonaniem wiersza ósmego procedury .push” 2. Po wykonaniu wiersza ósmego 3. Po wykonaniu wiersza dziewiątego

Wartości jakie znajdą się w polach ulana” i „wsk” elementu mogą być różne, w zależności od tego do czego użyjemy stosu. Wyjątkiem jest ty lko pole „wsk” ostatniego elementu stosu. Ma ono mieć wartość „NIL”, oznaczającą że pole to nic wskazuje na żaden inny element, a element je zawierający jest ostatnim' elementem stosu. Należy zastanow ić się. czy procedura push zadziała praw idłowo, kiedy będziemy chcieć utworzyć ten element. Wartość pola „wsk” elementów jest ustalana w wierszu ósmym procedury. Jeśli adres wierzchołka stosu będziemy przechowywać w zmiennej globalnej, którą będziemy następnie przekazywać do procedury .push”. to w polu „wsk” ostatniego elementu zostanie zapisana prawidłowa wartość, gdyż zmienna gkibalna przechowująca wskaźnik domyślnie jest inicjalizowana wartością „NIL”. W innych przypadkach należy zadbać o odpowiednią imcjalizację zmiennej przechowujące adres wierzchołka przed wywołaniem po raz pierwszy w programie procedury „push”. Wyjaśnienia wymaga również kwestia zmiennej „top”. Ponieważ jest ona zmienną lokalną, więc po zakończeniu procedury jest automatycznie niszczona i nic będzie wskazyw ać na żaden z elementów stosu. Trzeba również zwrócić uwagę, że

prettdtłr* upyyh” nję posłmagt >jy zmknna wskaźnikową „top", dopóki nię pr/y<kiv!» na pomocą prwdun «atw“ <>bs/ąru. pamięci mu.lato-. M-ankmK*..Jcm    .imtii-.Mniikn«..d»redi. szczególnie

4    To pojęcie zostanie wyjaśnione na przyszłych wykładach

5    To znaczy: znajdującym się na szczycie stosu.

6    Rysunek obrazuje w jaki sposób obrazujemy powiązania między poszczególnymi elementami struktur dynamicznych. Prostokąty obrazują zmienne wskaźnikowe i elementy stosu. Strzałki określają, że zmienna wskaźnikowa, lub pole od którego strzałka „wychodzi” przechowuje adres elementu do którego strzałka .dochodzi'*.

7    To znaczy: znajduje się na dnie stosu.

2