Laboratorium Podstaw Informatyki
Kierunek Elektrotechnika
Ćwiczenie 3.2
Dynamiczne struktury danych
Listy, Drzewa, Grafy
Zakład Metrologii AGH
Kraków 1997
Wprowadzenie
Dynamiczna struktura danych charakteryzuje się zdolnością do zmiany rozmiaru w czasie wykonywania programu. Efekt ten uzyskuje się przez dynamiczną (tj. w trakcie wykonywania programu) alokację pamięci dla nowych elementów struktury typu podstawowego. Zorganizowanie elementów w strukturę uzyskuje się przez tworzenie połączeń między elementami w formie wskaźników. Przykładem typu elementu struktury dynamicznej, przy dowolnym typie INFORMACJA, jest definicja:
typedef struct ElementStruktury {
INFORMACJA info;
struct ElementStruktury *następny;
} ELEMENT_STRUKTURY;
Ze względu na ilość wskaźników na typ podstawowy zawarty w tym typie i zasady organizacji struktury rozróżniamy listy, drzewa i grafy opisane w kolejnych rozdziałach.
Istotne jest utrzymywanie porządku w tworzonej strukturze. Podstawową zasadą jest przypisywanie wartości NULL wskaźnikom nie użytym i testowanie wartości wskaźnika przed jego użyciem. Użycie wskazania (dereferencja) wskaźnika o wartości NULL prowadzi do błędów wykonania programu.
Wygodnie jest, po zdefiniowaniu podstawowego typu struktury, używać funkcji tworzącej nowe elementy tego typu. Funkcja, dla powyższej definicji typu, może mieć postać:
ELEMENT_STRUKTURY *NowyElement() {
return (ELEMENT_STRUKTURY*)malloc(sizeof(ELEMENT_STRUKTURY));
}
Biblioteczna funkcja malloc(), z deklaracją w pliku malloc.h, przydziela pamięć o żądanym rozmiarze w obszarze sterty.
Zadanie 1 - listy
Lista jest najprostszym rodzajem struktury dynamicznej. Posiada w odmianie jednokierunkowej (tzw. kolejka lub ciąg) jedno pole dowiązania do elementu sąsiedniego, jak w przykładzie przedstawionym na rysunku:
Odmiana dwukierunkowa zawiera dodatkowo pole dowiązania do drugiego sąsiada. Przykład listy dwukierunkowej o definicji typu podstawowego:
typedef struct typ_podstawowy {
char Nazwa[20];
struct typ_podstawowy *Nastepny;
struct typ_podstawowy *Poprzedni;
} TYP_PODSTAWOWY;
przedstawia następujący rysunek:
Zmienna wskaźnikowa Poczatek typu TYP_PODSTAWOWY* jest tzw. głową lub korzeniem listy i służy za punkt wejścia do niej.
Przesunięcie wskaźnika aktualnego elementu do końca listy od jej początku realizuje instrukcja (dla niepustej listy):
for(aktualny=Poczatek;aktualny->Nastepny!=NULL;aktualny=aktualny->Nastepny);
Dodanie do listy dwukierunkowej nowego elementu między aktualnym i następnym, można wykonać sekwencją instrukcji, poprawną dla elementu aktualnego różnego od ostatniego:
nowy->Nastepny=aktualny->Nastepny;
nowy->Poprzedni=aktualny;
aktualny->Nastepny->Poprzedni=nowy;
aktualny->Nastepny=nowy;
Listy dwukierunkowe, w porównaniu z jednokierunkowymi, dają większą swobodę poruszania się po liście.
Lista jednokierunkowa
Program studenci z poprzedniego ćwiczenia posiada istotną wadę, jaką jest stały rozmiar tablicy zawierającej dane studentów. Przy takim rozwiązaniu nie ma możliwości zwiększania liczebności studentów w opisywanej grupie poza określony limit. Problemem jest również niska efektywność wykorzystania pamięci przy małej liczebności grupy.
Zmiana struktury danych z tablicy na listę dynamiczną uwalnia nas od tych wad. Ceną płaconą za to jest konieczność obsługi pamięci dynamicznej i zmiana sposobu dostępu do elementów z indeksowania na sekwencyjne przesuwanie wskaźnika.
typedef struct student {
STUDENT *StudentNowy(char *Nazwisko, char *Imie, double SredniaOcen) {
void StudentUsun(STUDENT *stp) { Zmień indeksowanie tablicy studentów (np. w funkcji WypiszListe()) na przesuwanie się po liście studentów przez pole Następny. |
Używanie pamięci dynamicznej wymaga ostrożności, ze względu na możliwość nieudanej alokacji pamięci na stercie. W takim przypadku biblioteczne funkcje grupy alloc zwracają wartość NULL. Testowanie używanej wartości wskaźnika, jak w funkcji StudentNowy(), chroni przed błędami wykonania.
Lista dwukierunkowa
Obserwując rozwój technologii programowania począwszy od metody strukturalnej, z wydzielonymi funkcjami realizującymi określone działania, przez programowanie modułowe, dzielące program na elementy przeznaczone do obsługi poszczególnych zadań i wymienne na etapie linkowania, aż do podejścia obiektowego zastępującego moduł obiektem z jego atrybutami i operacjami, w całym tym procesie ewolucji można zauważyć dominującą tendencję do ukrywania aktualnej postaci danych. Taka organizacja programu uwalnia programistę wykorzystującego elementy bibliotek od konieczności poznawania ich implementacji i pozwala na większą ich wymienność. Poniższy przykład ilustruje zasadę ukrywania implementacji w programowaniu modułowym w języku C i wskazuje na jej ograniczenia.
Zaimplementujemy pojęcie kolejki dwukierunkowej, tj. modułu przechowującego zbiór jednorodnych danych z określoną kolejnością, do których dostęp uzyskuje się za pomocą operacji:
KOLEJKA *KolejkaNowa();
TYP_DEF *ElementPierwszy(KOLEJKA *kp);
TYP_DEF *ElementOstatni(KOLEJKA *kp);
TYP_DEF *ElementNastepny(KOLEJKA *kp);
TYP_DEF *ElementPoprzedni(KOLEJKA *kp);
TYP_DEF *ElementDodajPrzed(KOLEJKA *kp, TYP_DEF *tdp);
TYP_DEF *ElementDodajPo(KOLEJKA *kp, TYP_DEF *tdp);
void ElementUsun(KOLEJKA *kp,TYP_DEF *tdp);
int KolejkaIleElementow(KOLEJKA *kp);
void KolejkaUsun(KOLEJKA *kp);
TYP_DEF może być dowolnym typem zdefiniowanym przez użytkownika i dostarczonym w pliku typ_def.h. Użytkownik może wygenerować dowolną ilość kolejek, ale tylko z jednym typem podstawowym. Spośród możliwych reprezentacji tablicowej i listowej bardziej odpowiadającą zestawowi operacji jest druga z nich, a uwzględniając dwukierunkowość kolejki należy wybrać implementację z listą dwukierunkową.
Przyjmiemy definicje typów w pliku kolejka.h:
#include „typ_def.h”
typedef struct TypPodstawowy {
TYP_DEF *Informacja;
struct TypPodstawowy *Nastepny;
struct TypPodstawowy *Poprzedni;
} TYP_PODSTAWOWY;
typedef struct {
int IloscElementow;
TYP_PODSTAWOWY *Elementy;
} KOLEJKA;
Po zapoznaniu się z gotowymi funkcjami modułu kolejka zaimplementuj brakujące funkcje: ElementOstatni(), ElementPoprzedni(), ElementWstawPoAkt(). Zapoznaj się ze sposobem testowania poprawności modułu w funkcji main(), wywołującej funkcje opracowanego modułu. Skompiluj i uruchom program. |
W opracowywanym module widoczne było ukrycie szczegółów implementacji w funkcjach interfejsu modułu z otoczeniem - użytkownik nie zna definicji typu TYP_PODSTAWOWY i nie używa typu KOLEJKA poza wywołaniami funkcji interfejsu. Moduł jest również niezależny od typu opisywanych danych - pola wiążące strukturę dynamiczną są niezależne od części informacyjnej typu podstawowego listy. Ze względu na wymóg języka dotyczący unikalności nazw funkcji, nie można tworzyć w jednym programie kolejek dla różnych typów danych. Język C++ oferuje taką możliwość dzięki wzorcom i powiązaniu operacji z obiektem, a nie modułem [Stroustrup].
Zadanie 2 - Drzewa
Drzewo to struktura dynamiczna, w której każdy węzeł ma określoną ilość dowiązań do węzłów niższego rzędu (lub równorzędnych w wielokierunkowej odmianie drzewa). Określona jest więc hierarchia węzłów typu rodzic-potomkowie. Lista prosta jest nazywana drzewem zdegenerowanym - węzeł posiada tylko jednego potomka. Ważną odmianą drzewa jest drzewo binarne, w którym węzeł posiada dwa dowiązania do węzłów potomnych.
Korzeniem drzewa nazywa się najwyższy węzeł w drzewie, tj. ten który nie posiada rodzica. Węzły potomne powiązane w sposób bezpośredni lub pośredni z danym węzłem przez jedno z jego dowiązań nazywane są poddrzewem (mają taką samą zasadę konstrukcji jak całe drzewo). Węzły nie posiadające potomków nazywa się liśćmi drzewa.
Przykład drzewa binarnego dla deklaracji typu podstawowego:
typedef struct typ_p {
int idWezla;
struct typ_p *lewy, *prawy;
} TYP_P;
przedstawia poniższy rysunek:
Zmienna wskaźnikowa typu TYP_P* wskazuje na korzeń drzewa. Ścieżką w drzewie jest każdy nieprzerwany ciąg powiązań rodzic-potomek. Długość ścieżki to ilość powiązań wzdłuż ścieżki. Głębokość drzewa to długość maksymalnej ścieżki powiększona o 1, czyli ilość węzłów znajdujących się na tej ścieżce.
Dla przedstawionego przykładu ścieżki opisane identyfikatorami węzłów i ich długości to np. 5-3 (długość 1), 5-8 (1), 5-8-9 (2). Głebokość przykładowego drzewa wynosi 3.
O pochodzeniu człowieka
Czy informatyka może nam pomóc w odpowiedzi na pytanie, które dręczyło Darwina ? Z pewnością. Należy tylko stworzyć odpowiedni algorytm i zastosować go do odpowiednich danych. Zajmiemy się programem, który nie da nam odpowiedzi na pytanie „Od kogo pochodzimy ?” (ze względu na brak danych z odległej przeszłości), ale przybliży nam sposób użycia struktury dynamicznej.
Strukturą, której użycie do opisu związków krwi wynika w naturalny sposób z charakteru danych jest drzewo binarne, tj. drzewo którego każdy węzeł może mieć nie więcej niż dwa bezpośrednie węzły potomne. W postawionym zadaniu mamy formalnie do czynienia z odwróconym drzewem, ponieważ węzły potomne opisują starszych członków rodziny - rodziców. Nie zmienia to jednak zasad konstrukcji drzewa.
Uzupełnij brakujące elementy programu rodzina z następującymi deklaracjami i funkcją główną:
typedef struct czlowiek { Funkcja CzlonekRodzinyNowy() powinna alokować pamięć dla struktury typu CZLONEK_RODZINY i inicjalizować jej składowe: Nazwisko i Imię wg. parametrów wywołania, a wskaźniki Ojciec, Matka na wartość NULL. Funkcja WypiszLinieMeska() powinna tworzyć na ekranie listę nazwisk występujących w drzewie wzdłuż wskaźnika Ojciec począwszy od wskaźnika przekazanego parametrem. |
Przyjęta struktura drzewa nie umożliwia opisywania związków poziomych, tj. rodzeństwa. Do pełnego opisu związków występujących w rodzinie należy użyć bardziej skomplikowanej struktury. Uwzględnić trzeba możliwość wystąpienia przypadków szczególnych (np. formalnie można być ojcem samego siebie, jak tego dowodzi historia Edypa).
Szybkie wyszukiwanie
Naszym zadaniem jest w tym punkcie opracowanie programu do obsługi wyborów. Zadanie polega na podliczaniu głosów dla poszczególnych kandydatów identyfikowanych nazwiskiem. Przy narzucającym się podejściu polegającym na utworzeniu struktury listowej jak w programie studenci wyszukiwanie nazwiska kosztowałoby nas maksymalnie N wywołań funkcji strcmp(). A jaki maksymalny koszt da drzewo binarne uporządkowane w ten sposób, że dla każdego węzła w jego lewym poddrzewie są elementy o mniejszym kluczu, a w prawym poddrzewie elementy o kluczu większym od klucza w tym węźle ? W przypadku kiedy będzie to drzewo wyważone, koszt wyniesie log2N. Dla wyborów, w których startuje 100 kandydatów oznacza to stosunek maksymalnej ilości porównań 100:7.
Opracuj program wybory wg. instrukcji: Dla kandydatów i ilości oddanych głosów: Kowalski 3 Nowak 1 Ziemba 2 zdefiniuj typ podstawowy, stwórz drzewo wyważone, wywołaj funkcję zwiększania liczby głosów odpowiednią ilość razy dla każdego z kandydatów. Wypisz na ekranie nazwisko i wynik dla kandydata, którego dane znajdują się w korzeniu drzewa. |
Wypisywanie danych z elementów drzewa wiąże się z jego przeglądaniem w określonym porządku. Najprostsze w implementacji i najbardziej czytelne są rekurencyjne algorytmy przeglądania struktur rozgałęzionych. To i inne zastosowania rekurencji będą tematem następnego ćwiczenia.
Zadanie 3 - grafy
Graf jest najogólniejszą strukturą dynamiczną. Jego węzły nie mają określonej maksymalnej ilości połączeń (krawędzi) z sąsiadami, ani określonej hierarchii typu rodzic-potomek czy poprzedni-następny. Połączeniu w grafie może być przypisana waga, tj. skojarzona z nim liczba. Połączenie może być jednokierunkowe lub dwukierunkowe. Graf z połączeniami jednokierunkowymi nazywany jest grafem skierowanym (zorientowanym), z połączeniami dwukierunkowymi grafem nieskierowanym (niezorientowanym). Graf, w którym istnieje droga (ciąg połączeń), której początek pokrywa się z końcem nazywany jest grafem cyklicznym. Jeśli takiej drogi nie ma, to jest to graf acykliczny.
Graf skierowany, cykliczny
Powróćmy do programu droga z poprzedniego ćwiczenia. Tablica odległości z poprzedniej implementacji może być widziana jako reprezentacja grafu (tzw. macierz incydencji) [Lipski]. W tym przypadku, z punktu widzenia wykorzystania pamięci, nie była to reprezentacja efektywna. Zaimplementujemy powtórnie algorytm wyznaczania odległości między miastami wojewódzkimi, używając tym razem struktury dynamicznej do opisu grafu połączeń między miastami sąsiadującymi. Przyjmijmy definicję typu podstawowego:
struct Miasto; /* deklaracja wstępna */
typedef struct Polaczenie {
struct Miasto *SasiednieMiasto;
int Odleglosc;
struct Polaczenie *NastepnePolaczenie;
} POLACZENIE;
typedef struct Miasto {
char *Nazwa;
POLACZENIE *ListaPolaczen;
} MIASTO;
Konieczność wstępnego deklarowania struktury Miasto wynika z wzajemnego powiązania definiowanych typów. Zauważmy, że tworzona na bazie typów podstawowych struktura dynamiczna jest grafem skierowanym - opisuje odległości od punktu początkowego do punktu końcowego. Z tego względu opis połączenia będzie dublowany. Możliwe jest również powstawanie w tworzonym grafie cykli, co w naturalny sposób wynika z charakteru opisywanych strukturą połączeń drogowych. Mamy więc do czynienia z grafem cyklicznym skierowanym.
Zapoznaj się z tekstem źródłowym przygotowanych funkcji:
MIASTO *MiastoNowe(char *nazwa); i wykorzystaj je do opracowania funkcji głównej realizującej zadania: Utworzenie opisu trasy Kraków - - Tarnów - - Reszów - - Przemyśl z zapamiętaniem wskaźnika na pierwsze miasto trasy Wypisanie na ekranie danych o trasie biegnącej przez miasta zapisane w tablicy Trasa i o nieopisanej trasie Kraków-Kielce w formacie „Miasto - Odległość - Miasto - Odległość - Miasto ...”. W przypadku braku bezpośredniego połączenia wypisanie informacji „... - Miasto - ??? - Miasto” i przerwanie wypisywania. |
Pamiętanie wskaźnika na początkowy punkt trasy wynika z chęci uniknięcia implementacji i stosowania algorytmu przeszukiwania grafu, co jest niezbędne w przypadku pełnego użytecznego programu [Lipski].
Dla tych, którzy chcą wiedzieć więcej - informacje dodatkowe
Struktury dynamiczne a pamięć komputera
Definicja języka C [Kernighan, Ritchie] z roku 1972, jest stale rozwijana i uzupełniana o nowe elementy. Do przyjętego w roku 19.. standardu ANSI języka C wprowadzono, porządkując sferę zarządzania pamięcią, m.in. typ void*, zamiast używanego dotąd przez funkcje alokacji pamięci typu char*. Chcąc uzyskać wskaźnik na dowolny inny typ należy zastosować rzutowanie.
Architektura IBM PC oparta o segmentację jest powodem rozróżnienia, w kompilatorach C na te maszyny, rodzajów wskaźników na bliskie typu near, odwołujące się do domyślnego segmentu danych przez offset i dalekie typu far z pełnym adresem segment-offset. Struktury o pamięci przydzielanej dynamicznie umieszczane są na tzw. stercie (ang. heap). Jest to obszar pamięci w segmencie danych przeznaczony do wykorzystania po przydzieleniu funkcjami grupy alloc(). W zależności od modelu pamięci z jakim kompilowany jest program, sterta mieści się w domyślnym segmencie danych dla modelu small (wywołania funkcji malloc() zwracają adres typu void near*) lub w innym segmencie danych dla pozostałych modeli pamięci (ze wskaźnikami typu void far*).
Windows 3.1 wprowadzają nowe funkcje alokacji pamięci z podziałem na stertę lokalną należącą do danej aplikacji i stertę globalną dostępną dla wszystkich aplikacji. Dodatkowo, wprowadzenie pamięci wirtualnej rozdziela operację przydziału pamięci na dwie fazy: Alloc() - przydział pamięci dynamicznej w przestrzeni pamięci wirtualnej, i Lock() - zablokowanie położenia przydzielonego obszaru w pamięci operacyjnej.
Funkcje biblioteczne grupy alloc()
Kompilatory firmy Microsoft (Quick C, Microsft C/C++, Visual C/C++) są rozprowadzane z biblioteką funkcji do zarządzania pamięcią dynamicznie przydzielaną, z deklaracjami w pliku nagłówkowym malloc.h. Najistotniejsze z tych funkcji to:
void *malloc(size_t size)
Przydziela obszar pamięci o rozmiarze size_t bajtów. W zależności od modelu pamięci wykorzystuje bliską lub daleką stertę (tzn. stertę w domyślnym segmencie danych lub poza nim) i zwraca bliski lub daleki wskaźnik na przydzielony obszar pamięci. Typ size_t jest używany do określenia ilości bajtów i jest zwracany np. przez operator sizeof.
void *calloc(size_t num, size_t size)
Przydziela obszar pamięci dla num elementów, każdy o rozmiarze size. Jest zależna od modelu pamięci podobnie jak malloc().
void free(void *memblock)
Funkcja zwalniania przydzielonej pamięci. Po zakończeniu działania programu cała przydzielona mu pamięć jest zwalniana automatycznie, ale do dobrych zwyczajów należy oddawanie pamięci po jej wykorzystaniu. Czasem jest to konieczność, z powodu ograniczonego rozmiaru tego zasobu komputera. Rozmiar zwalnianej pamięci jest znany systemowi dzięki informacji notowanej przy każdym przydzielanym obszarze.
void _huge *_halloc(long num, size_t size), void _hfree(void _huge* memblock)
Para funkcji do przydziału i zwalniania obszaru pamięci przekraczającego rozmiar segmentu (dla PC - 64kB). Zwraca wskaźnik typu _huge, poprawnie adresujący dane przekraczające granice segmentu, ale akceptowany tylko przez nieliczne funkcje biblioteczne.
Dla tych, którzy chcą być najlepsi - zadania dodatkowe
Dynamiczna alokacja macierzy
Przydzielanie pamięci dla macierzy w obliczeniach numerycznych dużej skali, przy ilości elementów rzędu milionów, wygodniej jest zorganizować w sposób dynamiczny. Przy takich rozmiarach struktur danych niedopuszczalne jest przetrzymywanie pamięci niewykorzystywanej. Do pełnej obsługi potrzebne są zatem dwie funkcje: przydzielenia i zwolnienia obszaru pamięci.
W języku C nie można zadeklarować wskaźnika na tablicę dwuwymiarową bez podania drugiego wymiaru. Z tego powodu należy zmienić organizację tablicy z tablicy tablic na tablicę wskaźników do tablic jednowymiarowych, co jest równoważne wskaźnikowi na wskaźnik na typ podstawowy. W użytkowaniu obydwie konstrukcje niczym się nie różnią. W przypadku tablicy wskaźników większa jest zajętość pamięci. Porównajmy deklaracje parametrów wywołania:
float Funkcja1(float Macierz[][10]) {
Macierz[1][1]=1.0;
}
float Funkcja2(float *Macierz[]) {
Macierz[1][1]=1.0;
}
W drugim przypadku nie musimy deklarować rozmiaru macierzy. Funkcja wołana w ten sposób musi jednak, w ogólnym przypadku znać wymiary przekazanej macierzy. Należy je podać jako dodatkowe parametry wywołania, jak w przykładzie:
float Funkcja(float **Macierz, int N, int M) {
Macierz[N-1][M-1]=1.0;
}
Szybkość dostępu do tak zorganizowanej macierzy może być mniejsza niż przy deklaracji statycznej, ze względu na adresowanie pośrednie.
Opracuj funkcje dynamicznego przydziału i zwalniania macierzy o zadanych wymiarach wg. deklaracji:
float **MacierzNowa(int N, int M); Porównaj swoją implementację z modułem alokacji profesjonalnego pakietu Numerical Recipes in C [Press, Flannery, Teukolsky, Vetterling]. |
Wyważanie binarnego drzewa uporządkowanego
Według definicji Adelson-Velskiego i Landisa [Wirth, str. 229] „drzewo jest wyważone wtedy i tylko wtedy, gdy dla każdego węzła wysokości jego dwóch poddrzew różnią się co najwyżej o 1”.
Opracuj na podstawie opisanych algorytmów [Wirth] funkcje sprawdzania dla drzewa binarnego jego wyważenia i wyważania dla drzewa niewyważonego. Użyteczna do realizacji tych zadań będzie rekurencja - temat następnego ćwiczenia. Zastosuj opracowane funkcje do uogólnienia programu wybory z pkt. 3.2. |
Algorytm przeszukiwania grafu
Konieczna w programie droga z implementacją grafową z pkt. 4.1, jest funkcja odnajdująca początkowy punkt trasy. Znane są dwa rozwiązania problemu przeszukiwania grafu [Lipski], zapewniające, że żaden wierzchołek nie będzie odwiedzony więcej niż jeden raz: metoda przeszukiwania w głąb i przeszukiwania wszerz. Obydwie wymagają dodatkowych struktur danych do opisu wierzchołków wymagających odwiedzenia i już odwiedzonych.
Na podstawie algorytmów [Lipski] dodaj do programu droga funkcję wyszukiwania w grafie początkowego miasta trasy. Zastosuj algorytm iteracyjny. Do pamiętania wierzchołków do odwiedzenia użyj konstrukcji kolejki z zadania dotyczącego list dwukierunkowych. Wierzchołki już odwiedzone pamiętaj w tablicy lub strukturze listowej. |
Literatura
Kernighan B. W., Ritchie D. M.: Język C; WNT, Warszawa 1988
Lipski W.: Kombinatoryka dla programistów; WNT, Warszawa 1989
Press W.H., Flannery B.P., Teukolsky S.A., Vetterling W.T.: Numerical Recipes in C; Cambridge University Press 1988
Stroustrup B.:Język C++; WNT, Warszawa 1992
Wirth N.: Algorytmy + Struktury Danych = Programy; WNT, Warszawa 1989