CWICZENIE_stos.doc

ĆWICZENIE 3

Podstawowe dynamiczne struktury danych  -  stos

Celem ćwiczenia jest zapoznanie studentów z najprostszą dynamiczną strukturą danych: stosem.

I. PRZEBIEG ĆWICZENIA

Tworzenie elementarnego stuktury:

Uwaga: Typy danych przechowywanych w dowolnego rodzaju dynamicznych strukturach danych są oczywiście całkowicie dowolne. W tej instrukcji dane te oznaczane są dużymi literami, np. „DOL”, „ELEMENT 3”, itd. Zamiast tych nazw oczywiście używa się danych odpowiedniego typu (np. liczb typu int).

Każdą tworzoną dynamicznie strukturę należy utworzyć przy pomocy instrukcji
wskaznik = new(TTypStrukturalny);
a następnie należy przypisać jego polom określone dane: Wskaznik jest najczęściej zwykłą zmienną statyczną (tworzoną przy pomocy TTypStrukturalny * Wskaznik).

TTypStrukturalny * Wskaznik;

Wskaznik = new TtypStrukturalny;

Wskaznik->DANE=Dane;

Wskaznik->Nastepny=NULL;

Stos:

Stos jest dynamiczną strukturą danych,  w której dołączanie i usuwanie elementów zachodzi tylko w jednym miejscu: na wierzchołku. Stos można wyobrazić sobie jako stos książek: chcąc wyjąć jedną,  należy wcześniej wyjąć wszystkie znajdujące się powyżej:

Rysunek 1 -  Stos

Tworzenie stosu:

Wierzcholek = new TTypStrukturalny;

Wierzcholek->DANE = DÓŁ;

Wierzcholek->Nastepny = NULL;

(To już jest stos, tyle, że nieco mało użyteczny.... Od teraz dodawanie każdego nowego elementu będzie przebiegało identycznie).

Najpierw należy utworzyć elementarną „cegiełkę”:

Tmp = new TTypStrukturalny;

Tmp->DANE = Element_3;

Tmp->Nastepny = NULL; //To przypisanie w zasadzie nie jest konieczne, gdyż zaraz zostanie                                           // zmienione

Następnie można połączyć tę nową „cegiełkę” z resztą stosu:

Tmp->Nastepny = Wierzcholek;

Ponieważ w przypadku stosu KONIECZNE jest zapewnienie, aby Wierzcholek wskazywał na rzeczywisty wierzchołek stosu:

Wierzcholek = Tmp;

(Gotowy stos; Zmienna Tmp nie jest już potrzebna i można ją wykorzystać do innych celów)

Dodawanie nowego elementu do stosu o dwóch elementach

Należy zauważyć, że dodawanie danych do stosu o dowolnym rozmiarze (od pustego stosu do utworzenia potrzebnej liczby elementów) przebiega zawsze w ten sam, omówiony wcześniej sposób:

Porównaj strzałkę (wskaźnik Tmp->Nastepny)

Tmp = new TtypStrukturalny;

Tmp->DANE = Element_2;

Tmp->Nastepny = Wierzcholek;

Wierzcholek = Tmp;

(Prawie) gotowy stos;

Gotowy stos. Zmienna Tmp nie jest już potrzebna i można ją wykorzystać do innych celów. 

Ta strzałka to Wierzchołek->Następny

Dodawanie pozostałych elementów następuje analogicznie.

Usuwanie elementów ze stosu:

Przy usuwaniu elementu ze stosu również będzie niezbędne użycie

pomocniczego wskaźnika Tmp.

Te strzałki reprezentują pole „następny” swoich rekordów

ODCZYTAJ_DANE_ZE_STUKTURY(Wierzcholek->DANE); tmp=Wierzcholek->Nastepny;

Przygotowanie danych do usunięcia. Zmienna dynamiczna “Element 2” zostanie usunięta, jednak ustawienie pola “Nastepny” na wartość NULL ułatwia odszukiwanie błędów. UWAGA: PRZED wykonaniem tego kroku (a więc przed “odcięciem” zmiennej dynamicznej, na którą wskazuje wskaźnik “Wierzcholek” KONIECZNE jest zapewnienie, że na resztę struktury wskazuje jakiś inny wskaźnik – tutaj Tmp. Jeśli w dowolnej chwili to nie będzie spełnione, wtedy NIE MA MOŻLIWOŚCI NAPRAWY TEGO BŁĘDU  - STRUKTURA ZOSTANIE NIEODWRACALNIE ZNISZCZONA!!!).

Wierzchołek->Następny=NULL;

Teraz można już usunąć element na wierzchołku stosu:

delete Wierzcholek; /*Usunięcie zmiennej dynamicznej, na którą wskazuje wskaźnik Wierzcholek. Po wykonaniu tej linii,                                           wskaźnik Wierzcholek  NIE wskazuje na żaden użyteczny obszar pamięci (napisanie więc                                           (*Wierzcholek) lub Wierzcholek->cokolwiek jest BŁĘDNE). */

Ponieważ wskaźnik Wierzcholek powinien zawsze wskazywać na wierzchołek stosu, dlatego konieczne jest jego ponowne ustawienie:

Wierzchołek:=Tmp; /*(Zmienna TMP nie jest już potrzebna i może zostać użyta do innych celów. Od teraz Wierzchołek znowu wskazuje na użyteczną zmienną dynamiczną – na początek stosu).*/

Usuwanie pozostałych elementów realizuje się analogicznie.

Zadania:

1.       Zaimplementować funkcję służącą do dodawania elementów do stosu

2.       Zaimplementować funkcję służącą do usuwania elementów stosu. W przypadku próby usunięcia elementu z pustego stosu należy wypisać komunikat o błędzie.

3.       Przy pomocy funkcji z p. 1 i 2, dodać do stosu po kolei liczby: 1,2,3,4,5,6,7,8,9,10. Następnie usunąć wszystkie elementy. Po usunięciu każdego z nich wypisać wartość liczby na ekranie.