stos kolejka, Ebooks, Informatyka, języki i metody programowania C2

[ Pobierz całość w formacie PDF ]

Dynamiczne struktury danych -nieuporządkowane(część I)

1.        Pojęcie rekurencyjnych typów danych

2.        Klasyfikacja struktur danych

3.        Podstawowe nieuporządkowane rodzaje dynamicznych struktur danych

3.1.       Stos

3.2.       Kolejka

3.3.       Lista jednokierunkowa

1.         Pojęcie rekurencyjnych typów danych

Przykład (Wirth N. „Algorytmy + Struktury Danych = Programy”, WNT 1989)

a) deklaracja modelu drzewa dziedziczenia:

type osoba =               record

                                        if znany then

                             (imię : alfa;

                               ojciec, matka: osoba)

                                                                                                  end;

b) opis reprezentacji zmiennej rodowód typu osoba:

jeśli znany = False, to istnieje tylko pole znacznikowe znany równe False (F)

jeśli znany = True, to istnieją jeszcze trzy pola (imię, ojciec, matka)

c) przypadek danych: rodowód =

(T,               Jan,

(T,               Marek,

(T,               Adam,

(F),

(F)

),

(F)

),

(T,               Maria,

(F),

                                   (T,               Ewa,

(F),

(F)

)

)

)                           

2.       Klasyfikacja struktur danych

Struktury danych można podzielić na:

1)       typy o stałych rozmiarach - realizowane jako tablice lub struktury z bezpośrednim  dostępem do każdego elementu tych struktur za pomocą operatorów indeksowania „[ ]” lub wyboru: „->” oraz „.”

2)       typy z możliwością zmiany rozmiarów,  - rekurencyjne typy danych realizowane jako dynamiczne struktury danych z pośrednim dostępem do ich elementów, przez:

2.1)      użycie struktur

2.2)      użycie wskaźników do deklaracji składowych tych struktur,

2.3)      dynamiczny przydział pamięci dla tych składowych,

2.4)      algorytm dostępu do poszczególnych składowych tej struktury określa programista  dzięki jawnemu użyciu wskaźników.

·     Dynamiczne przydzielanie pamięci zmiennej typ*P.

·     Wskaźnikowy model rekurencyjnych typów danych:

Przykład Wskaźnikowy model rodowodu

a) deklaracja typu

struct osoba

{

    char imie [10];

    osoba* ojciec, *matka;

  } 

b)       wskaźnikowa struktura rodowodu

                            osoba* Poczatek;

2.       Podstawowe nieuporządkowane dynamiczne struktury danych

Decyzja o zastosowaniu rekurencyjnych struktur danych jest podejmowana przy projektowaniu interfejsu nowego typu

Algorytm dostępu do poszczególnych elementów tej struktury określa programista  dzięki jawnemu użyciu wskaźników.

Algorytm dostępu jest podstawą do klasyfikacji dynamicznych struktur danych.

4.1. Stos

Etap 1 - Opis ADT

Nazwa typu -                             Stos elementów

Własności typu:               Potrafi przechować ciąg elementów o dowolnym rozmiarze

Dostępne działania:              

Inicjalizacja stosu

                                                        Określenie, czy stos jest pusty

                                                        Dodanie elementu do stosu,

                                                        Usuwanie ze stosu,

                                                        Przejście przez stos i przetwarzanie każdego elementu

                                                        Wyszukanie elementu ze szczytu stosu i przetwarzanie tego elementu

Usunięcie stosu

Etap 2 -  Budowa interfejsu

struct OSOBA                                                                                                                                                                                      //typ informacji umieszczanej na stosie

              { int Numer;

              char Nazwisko[DL];

              };

typedef struct ELEMENT* PELEMENT;                                                        //typ wskazania na element stosu

struct ELEMENT                                                                                                                                                                                      //typ  elementu stosu

              {

     OSOBA Dane;                                                                                                                                                                                      //informacja umieszczanej na stosie

                PELEMENT Nastepny;

              };

int Wstaw(PELEMENT& Poczatek, OSOBA Dana);

{działanie: dodaje element na początek ciągu, zwany szczytem stosu

warunki początkowe: Dana jest daną do wstawienia na szczyt zainicjowanego stosu

warunki końcowe: jeśli to możliwe, funkcja dodaje daną Pozycja na szczyt stosu i zwraca wartość 0, w przeciwnym wypadku 1 }

int Usun(PELEMENT& Poczatek);

{działanie: usuwa element na początku ciągu wstawionego do stosu

warunki początkowe: Poczatek jest zainicjowanym stosem

warunki końcowe: jeśli jest to możliwe, funkcja usuwa element na szczycie stosu i zwraca 3, w przeciwnym wypadku 2 }

void Usun_pamiec(PELEMENT& Poczatek);

{działanie: usuwa elementy ze stosu i inicjuje stos jako pusty

warunki początkowe:  Poczatek jest zainicjowanym stosem

warunki końcowe: liczba elementów na stosie jest równa 0}

int Wyswietl(PELEMENT Poczatek);

{działanie: wyświetla dane umieszczone w każdym wstawionym elemencie do stosu

warunki początkowe: Poczatek jest zainicjowanym stosem, Pokaz_dane jest  funkcją, która wyświetla strukturę typu OSOBA umieszczoną w elemencie stosu

warunki końcowe: jeśli stos nie jest pusty, funkcja Pokaz_dane tylko raz wyświetla każdą strukturę typu OSOBA wstawioną do stosu i funkcja zwraca 4, w przeciwnym przypadku 2 }

Etap 3. Implementacja stosu -

void Inicjalizacja(PELEMENT& Poczatek)             

        {  Poczatek = NULL;              }

{static - funkcja prywatna modułu mstos.cpp zawierającego definicję funkcji interfejsowych}

static PELEMENT Nowy_Element(OSOBA N_Dane)

              {              PELEMENT Nowy;

                            Nowy = new ELEMENT;

                            if (!Pusty(Nowy))             

                            Nowy->Dane= N_Dane;

                            return Nowy;             

                     }

·     wstawianie elementów zawsze na początek struktury

int Wstaw(PELEMENT& Poczatek, OSOBA Dana)

              { PELEMENT Nowy;

                            Nowy = Nowy_Element(Dana);

                            if ( Nowy == NULL) return 1;

                            Nowy->Nastepny= Poczatek;                                                                                    //nowy element na początek stosu

                               Poczatek= Nowy;

                            return 0;

              }

·     usuwanie elementów zawsze na początku struktury

int Usun(PELEMENT& Poczatek)

              {              PELEMENT Pop;

              if ( Poczatek == NULL) return 2;

              Pop = Poczatek;                                                                                                                //zapamiętanie pierwszego elementu do usunięcia

              Poczatek = Poczatek->Nastepny;                             //odłączenie pierwszego elementu od listy

              delete Pop;                                                                                                                                                                        //usunięcie pierwszego elementu z pamięci

              return 3;              }

void Usun_Pamiec(PELEMENT& Poczatek)

              { PELEMENT Pom;

                            while ( Poczatek != NULL)

                            {              Pom= Poczatek;

                                          ...