Transcript
Programowanie z wykorzystaniem dynamicznych struktur danych Cel ćwiczenia: opanowanie umiejętności tworzenia złożonych, dynamicznych struktur danych oraz wykonywania na nich podstawowych operacji (np. dołączanie, odłączanie, sortowanie elementów); zwrócenie uwagi na praktyczne zastosowania takich struktur, jak: listy cykliczne, macierze rzadkie, drzewa i grafy.
Zagadnienia do przygotowania:
listy uporządkowane, listy cykliczne, macierze rzadkie; drzewa binarne i wielokierunkowe; grafy i sposoby ich reprezentacji (macierz incydencji, macierz sąsiedztwa wierzchołków, lista incydencji); zmienne dynamiczne i wskaźniki; procedury dynamicznego przydziału pamięci (New, GetMem).
Literatura: [1] A. Sielicki (red.), Laboratorium programowania w języku Pascal. Wydawnictwo PWr. , Wrocław, 1994. [2] A. Marciniak, Borland Pascal 7.0. Wydawnictwo Nakom, Poznań, 1994. [3] W. Lipski, Kombinatoryka dla programistów. WNT, Warszawa, 1982. [4] N. Wirth, Algorytmy + struktury danych = programy. WNT, Warszawa, 1989. [5] R. Kott, Programowanie w języku Pascal. WNT, Warszawa, 1990.
1. Wstęp Dynamiczne struktury danych są zakładane w trakcie wykonywania programu, a nie, jak w przypadku statycznych struktur danych, w trakcie kompilacji programu. Struktury tego typu są lokowane w obszarze sterty programu, a przydzielanie pamięci może być realizowane za pomocą procedur standardowych New i GetMem [1,2]. Dynamiczna struktura danych jest zbiorem logicznie powiązanych elementów. Rozmiar tego zbioru nie jest z góry określony i może zmieniać się w trakcie wykonywania programu. W języku Pascal każdy element struktury dynamicznej ma postać rekordu, który zawiera pola danych oraz pola wskaźnikowe, określające adresy kolejnych elementów struktury. Należy podkreślić, że elementy te są kolejne w sensie uporządkowania struktury i nie muszą być umieszczone kolejno w pamięci. Ponadto, elementy (rekordy) mogą być różnych typów.
2. Klasyfikacja dynamicznych struktur danych Ze względu na organizację dynamiczne struktury danych można podzielić na [2,4]:
listy uporządkowane (jednokierunkowe i dwukierunkowe); listy cykliczne (jednokierunkowe i dwukierunkowe); drzewa (binarne i wielokierunkowe); grafy (zorientowane i niezorientowane).
Do przetwarzania listy jednokierunkowej można wykorzystywać następujące typy danych [2,3,4,5]: type L = ^lst; lst = record dana : typ_danej; nast : L; end; var start : L; Zmienna statyczna start określa początek listy jednokierunkowej. Jeżeli E jest składnikiem listy to E^.nast jest wskaźnikiem do następnego elementu listy. Jeżeli E jest ostatnim składnikiem listy to E^.nast = NIL. Elementy mogą być dopisywane (usuwane) na dowolnej pozycji w liście.
Elementy listy dwukierunkowej określa się następująco: type T= ^lstd; lstd = record dana : typ_danej; nast, pop : T; end; var start : T; Zmienna statyczna start określa początek (koniec) listy dwukierunkowej. Jeżeli E jest składnikiem listy to E^.nast jest wskaźnikiem do następnego elementu listy, natomiast E^.pop jest wskaźnikiem do poprzedniego elementu listy. Jeżeli E jest pierwszym (ostatnim) składnikiem listy to E^.pop = NIL (E^.nast = NIL). Elementy mogą być dopisywane (usuwane) na dowolnej pozycji w liście. Lista cykliczna jednokierunkowa może być przetwarzana za pomocą tych samych typów danych co lista jednokierunkowa. Różnica pomiędzy tymi strukturami wynika z innej definicji ostatniego elementu i zmiennej start. Jeżeli x jest pierwszym elementem listy, natomiast y ostatnim elementem listy, to spełnione są następujące zależności:
lista jednokierunkowa: start:= x; lista cykliczna: start:= y;
y^.nast:= NIL; y^.nast:= x.
Za pomocą listy cyklicznej jednokierunkowej można zrealizować takie struktury danych jak stos, kolejka i macierz rzadka [1,2,3,4,5]. Stos jest listą cykliczną jednokierunkową, w której zmienna start wskazuje na wierzchołek stosu. Elementy mogą być dołączane (odłączane) tylko w miejsce wierzchołka stosu. Każdy dołączony składnik staje się nowym wierzchołkiem stosu. Kolejka jest listą cykliczną jednokierunkową, w której zmienna start wskazuje na koniec kolejki, natomiast zmienna start^.nast wskazuje na początek kolejki. Elementy mogą być dołączane tylko na koniec kolejki, natomiast odłączane tylko z początku kolejki (na tej zasadzie działa bufor klawiatury w komputerach PC). Macierz rzadka jest strukturą danych, która składa się z wzajemnie powiązanych ze sobą list cyklicznych jednokierunkowych. Powstaje ona z dowolnej macierzy A w wyniku odrzucenia elementów równych 0. Każdy wiersz (kolumna) macierzy A jest przekształcana w listę cykliczną, która zawiera tylko niezerowe elementy wiersza (kolumny). Każda lista cykliczna rozpoczyna się od elementu neutralnego, do którego dołączane są niezerowe składniki macierzy A. Zmienna start wskazuje na element neutralny (0,0). Przedstawione rozważania ilustruje następujący przykład.
Macierz: 1 2 0 A 0 0 0 . 3 0 4
Macierz rzadką utworzoną dla macierzy A pokazano na Rys.2.1.
Rys.2.1 Przykładowa macierz rzadka. Kolejność tworzenia elementów macierzy rzadkiej: (0,0), (1,0), (0,1), (1,1), (0,2), (1,2), (0,3); (2,0); (3,0), (3,1), (3,3).
W języku Pascal elementy macierzy rzadkiej można określić następująco: type MZ = ^element; element = record dana : typ_danej; nr_wiersza, nr_kol : word; nast_wiersz, nast_kol : MZ; end; var start : MZ; Na macierzach rzadkich można wykonywać takie same operacje jak na "zwykłych" macierzach (np. dodawanie, mnożenie, itp.). Są one szczególnie przydatne, wtedy gdy "zwykłe" macierze zawierają wiele elementów zerowych i mają znaczne rozmiary. Lista cykliczna dwukierunkowa może być przetwarzana za pomocą tych samych typów danych co lista dwukierunkowa. Jeżeli x jest pierwszym elementem listy, natomiast y ostatnim elementem listy, to spełnione są następujące zależności:
lista dwukierunkowa:
start:= x; lub start:= y; x^.pop:= NIL; y^.nast:= NIL; lista cykliczna dwukierunkowa: start:= y; y^.nast:= x;
x^.pop:=y.
Drzewem nazywa się strukturę, w której dla każdego składnika (poza pierwszym, nazywanym korzeniem drzewa) istnieje tylko jeden element poprzedni i dla każdego składnika (poza ostatnimi w strukturze, nazywanymi liśćmi drzewa) istnieje n (n 2) elementów następnych. Jeżeli n = 2 to drzewo takie nazywane jest drzewem binarnym. Może ono być określone za pomocą następujących typów: type D = ^drzewoB; drzewoB = record dana poziom lewy, prawy end; var start : D;
: typ_danej; : word; {odległość od poziomu korzenia } : D; { korzeń - poziom 0 }
Jeżeli n 2 to drzewo takie nazywane jest drzewem wielokierunkowym. Może ono być określone następująco: type DW = ^drzewoW; drzewoW = record dana poziom wsk_wierz_1 wsk_wierz_n end; var start : DW;
: typ_danej; : word; {odległość od poziomu korzenia } : DW; { wskaźniki wierzchołków incydentnych } : DW; { korzeń - poziom 0 }
Przyjmuje się, że elementy mogą być dołączane (odłączane) w dowolnym miejscu drzewa. Grafy definiowane są za pomocą zbioru wierzchołków i zbioru krawędzi, określających powiązania pomiędzy wierzchołkami. Rozważane są zarówno grafy zorientowane, jak i niezorientowane. Każdy graf można opisać następująco [3]: G W, K ,
gdzie W - zbiór wierzchołków K - zbiór krawędzi
( W oznacza liczbę wierzchołków grafu), ( K oznacza liczbę krawędzi grafu),
przy czym KWW
dla grafu zorientowanego
oraz K { {a,b} : a,b W & a b }
dla grafu niezorientowanego.
W teorii grafów klasycznym sposobem reprezentacji grafów jest macierz incydencji [3]. Jest to macierz X, która ma W wierszy i K kolumn. Jeżeli w grafie zorientowanym istnieje krawędź (a,b) to X[a,{a,b}] = -1 oraz X[b,{a,b}] = 1, natomiast jeżeli wierzchołki nie są incydentne to odpowiednie pozycje macierzy wypełniane są zerami. Jeżeli istnieją krawędzie postaci (a,a) to przyjmuje się X[a,{a,a}] = 2. W przypadku grafu niezorientowanego pozycje macierzy X, odpowiadające wierzchołkom incydentnym, wypełniane są jedynkami, natomiast pozostałe pozycje wypełniane są zerami. Przedstawione rozważania ilustruje następujący przykład. Niech Ga Wa , Ka oraz Gb Wb , Kb ,
Wa Wb { 1,2,3,4 }, Ka Kb { {1,2}, {2,3}, {3,4}, {4,1} }. Na Rys.2.2 pokazano grafy Ga i Gb oraz ich macierze incydencji. gdzie
0 1 1 0 1 1 0 0 Xa 0 1 1 0 0 0 1 1
2 0 0 2 0 0 0 0
1 1 Xb 0 0
0 0 1 1 0 0 1 1 0 0 1 1
Rys.2.2 (a) Graf zorientowany Ga oraz jego macierz incydencji X a , (b) Graf niezorientowany Gb oraz jego macierz incydencji X b . Bardziej efektywnym sposobem reprezentacji grafu jest macierz sąsiedztwa wierzchołków (MSW), określana jako macierz kwadratowa MSW mij , gdzie: i = 1, ... ,W & j = 1, ... ,W; mij 1 jeżeli istnieje krawędź prowadząca od i-tego do j-tego wierzchołka oraz mij 0 w przeciwnym przypadku.
Dla grafów Ga i Gb , pokazanych na Rys.2.2, zachodzi:
1 0 MSWa 0 1
1 0 0 1 1 0 , 0 0 1 0 0 0
0 1 MSWb 0 1
1 0 1 0 1 0 . 1 0 1 0 1 0
Główną zaletą macierzy MSW jest fakt, iż w jednym kroku możemy otrzymać odpowiedź na pytanie "czy istnieje krawędź (a,b)", gdzie a,b W. Wadą jest jednak fakt, że niezależnie od liczby krawędzi zajętość pamięci wynosi WW. Wadę tę można jednak wyeliminować stosując reprezentację w postaci macierzy rzadkiej. Grafy można również reprezentować za pomocą struktury nazywanej listą incydencji (LINC). Zawiera ona dla każdego wierzchołka a W listę wierzchołków, które są do niego incydentne. Dla rozpatrywanych grafów Ga i Gb listy incydencji mogą być określone następująco (Rys.2.3):
Rys.2.3 (a) Lista incydencji grafu Ga , (b) Lista incydencji grafu Gb . Listy incydencji można również reprezentować w postaci list dwukierunkowych oraz w postaci list cyklicznych. W praktyce przedstawione reprezentacje grafów są równoważne i łatwo na podstawie jednej z nich wyznaczyć wszystkie pozostałe. Można również zauważyć, że reprezentując graf w postaci MSW, sprowadzonej do macierzy rzadkiej, zajmujemy o W komórek pamięci więcej (wiersz zerowy) niż w przypadku reprezentacji za pomocą LINC. Ponadto, w praktyce wystarczy rozpatrywać tylko grafy zorientowane, gdyż każdą krawędź (a,b) grafu niezorientowanego można zastąpić dwoma krawędziami skierowanymi (a,b) i (b,a), otrzymując w ten sposób równoważny graf zorientowany.
