DYNAMICZNE STRUKTÓRY DANYCH W WYBRANYCH JĘZYKACH PROGRAMOWANIA

PRACA DYPLOMOWA

SPIS TREŚCI

1. Wstęp

2. Wiadomości ogólne

3. Słowa kluczowe i struktura programu

4. Zmienne, Typy danych

1. typy proste

2. zmienne wskazujące ( wskaźniki)

3. typy strukturalne

4.3.1 struktury występujące w języku C

4.3.2 rekordy występujące w języku Pascal

5. tablice

1. tablice i wskaźniki

2. tablice wielowymiarowe

7. struktury dynamiczne

1. listy

1. listy jednokierunkowe

2. listy dwukierunkowe

3. listy cykliczne

2. drzewa

3. Grafy

4. Stosy

5. kolejki

8. przykładowe funkcje i procedury (C, Pascal)

1. język programowania C

1. wstawianie elementu na początek listy jednokierunkowej

2. wstawianie elementu na koniec listy jednokierunkowej

3. ?

4. ?

2. język programowania Pascal

1. procedura tworzenia i dołączania do niego składnika

2. ?

3. ?

8. zakończenie .

1. Wstęp

Rozwiązanie dowolnego zadanie posługując się komputerem, należy skonstruować odpowiedni algorytm, tj. podać zbiór reguł rozwiązania zadania w skończonej liczbie kroków. Każdy algorytm składa się z dwóch zasadniczych części : opisu danych, na których działa, oraz czynności, które są wykonywane na tych danych. Algorytm napisany w języku programowania nazywa się programem, w którym czynności wykonywane na danych są opisane za pomocą odpowiednich instrukcji języka. Zagadnienia te przybliżye w dalszej części pracy.

Od wyboru właściwej w danym momencie struktury danych może zależeć wszystko : szybkość działania programu, możliwość jego łatwej modyfikacji, czytelności zapisu algorytmów i ... dobre samopoczucie programisty.

Każdy kto poznał jakikolwiek język programowania, został niejako zmuszony do opanowania zasad posługiwania się twz. typami podstawowymi. Przykładowo w C mamy do dyspozycji typy :int, long, float, char ,typy wskaźnikowe etc. Mogą one posłużyć jako elementy bazowe rekordów, tablic ,unii, które już zasługują na miano struktur danych. Prawdziwa przygoda rozpoczyna się dopiero, gdy dostajemy do ręki twz. listy, drzewa binarne, grafy... . wraz z nimi rozszerza się znacznie możliwości rozwiązania programowego wielu ciekawych zagadnień; zwiększa się wachlarz potencjalnych zastosowań informatyki. Ogólną nazywają się one dynamiczne struktury danych, i właśnie o tym traktuje ta praca.

Zanim jednak przejdę do szczegółowej charakterystyki dynamicznych struktur, chciałbym wspomnieć o językach programowania za pomocą, których będziemy je tworzyć. W poniższej pracy poruszę również problem struktur statycznych (tablic, rekordów itp.), które będziemy wykorzystywać w dynamicznych strukturach danych.

2. Wiadomości ogólne

Turbo Pascal , C są to języki programowania za pomocą których postara się przedstawić i wyjaśnić działanie dynamicznych struktur danych.

Język C jest wysoce modularny, każdy program można zdekompilować na oddzielnie kompilowane moduły z publicznym interfejsem i ukrytą implementacj. I odwrotnie : do każdego programu można dołączyć wcześniej opracowane moduły, przechowywane na dysku. W rezultacie każdy większy program składa się z dwóch rodzajów plików : - plików nagłówkowych, - pliki źródłowych. Implementacje operacji języka C są nazywane funkcjami. Użytkownik może również używać funkcji zewnętrzne, deklarowane i definiowane na zewnątrz.

Turbo Pascal jest jednym z najpopularniejszych języków programowania komputerów. Nie ulega wątpliwości , że język ten jest przyjazny dla początkującego programisty. Pozwoli mi to na przedstawienie mechanizmów zawartych w Pascalu, za pomocą których możemy stworzyć dynamiczne struktury danych. język ten może być również wykorzystywany w procesie tworzenia, analizowania i testowania najróżniejszych programów użytkowych.

3. Słowa kluczowe i struktura programu

W ramach przypomnienia przywołam kilka wiadomości dotyczących Pascal'a i C.

Niektóre identyfikatory zostały zastrzeżone przez twórców języka. Służą one do zapisu konstrukcji jakie są dopuszczalne w danych językach. Dlatego nazywa się je słowami kluczowymi. Słowa kluczowe nie mogą być użyte jako nazwy zmiennych, typów lub funkcji i nie są poprawnymi identyfikatorami .

W języku C występują

następujące słowa kluczowe:

auto double int struct

break else long switch

case enum register typedef

char extern return union

const float short unsigned

continue for signed void

default goto sizeof volatile

do if static while

W języku Pascal występują

następujące słowa kluczowe:

and file nil shr

array for not string

asm function object then

begin goto of to

case if or type

const packed unit constructor

in procedure until destructor

inherited program uses div

inline record var do

interface repeat while downto

label set with else

mod shl xor end

Struktury programów :

C

#include <stdio.h> włączenie informacji o bibliotece standardowej

implementacja funkcji

main() definicja funkcji o nazwie main, która nie

oczekuje żadnych argumentów

{ nawiasy klamrowe otaczają instrukcje funkcji

deklaracje

instrukcje - ciało programu

}

Pascal

Program nazwa-programu;

User lista-nazwa-modułów;

Definicje-funkcji-i-procedur;

Begin

Instrukcje

End.

4. Zmienne i ich typy

Zmienną określany jest pewien obszar w pamięci komputera, w którym mogą być przechowywane dane. Z punktu widzenia osoby piszącej program, zmienna posiada następujące cechy podstawowe:

• nazwa (identyfikator)

• typ

• wartość

Nazwa zmiennej pozwala wskazać w programie, o który fragment pamięci nam chodzi. Łatwiej jest posługiwać się nazwą niż adresem liczbowym. Kompilator dokonując tłumaczenia napisanego programu zamienia wszystkie nazwy zmiennych na odpowiednie adresy w pamięci komputera. Wszystkie nazwy zmiennych przed użyciem muszą być zadeklarowane.

Wartość zmiennej jest tym, co przechowujemy w obszarze pamięci określanym przez nazwę. Wartość może się zmieniać w dowolnym momencie w czasie wykonania programu. Wartością może być liczba całkowita, zmiennoprzecinkowa (ułamek dziesiętny), adres w pamięci komputera (tzw. wskaźnik), tekst itp. W momencie deklaracji wartość zmiennej lokalnej (zadeklarowanej wewnątrz funkcji) jest nieokreślona tzn. jej wartość jest przypadkowa; zmienne globalne (deklarowane poza funkcjami) są inicjowane na zero.

Typ zmiennej określa jaką wartość można wpisać do obszaru wskazywanego przez nazwę (czy będzie to liczba całkowita, zmienno-przecinkowa ... , czy też inny rodzaj danej). W zależności od rodzaju wartości (typu zmiennej), inny będzie rozmiar pamięci potrzebny do jej zapamiętania. Kompilator na podstawie typu określa jaką ilość pamięci należy przydzielić zmiennej i jakie operacje są na niej dopuszczalne.

4.1. Typy danych

Typy proste

Pascal	C
Char	Char	typ znakowy. Można za jego pomocą przechowywać znaki w kodzie ASCII (American Standard Code for Information Interchange) lub innym stosowanym na danej maszynie. Bezpiecznie można więc przechowywać liczby z zakresu 0 .. 127. Na ogół typ char ma 1 bajt długości w związku z czym można za jego pomocą przechowywać liczby z zakresu -128 .. 127 (jeśli jest ze znakiem) lub 0 .. 255 (jeśli jest bez znaku).
Integer	Int	typ całkowity. Zmienne tego typu mogą przyjmować wartości całkowite dodatnie lub ujemne.
Shortint	Short int	typ całkowity krótki
Longint	Long int	typ całkowity długi
Real	Float	typ zmiennoprzecinkowy pojedynczej precyzji.
Byte		typ całkowity należący do przedziału od 0 do 255
Word		typ całkowity należący do przedziału od 0 do 65535
	Double	typ zmiennoprzecinkowy podwójnej precyzji.
	Long double	typ zmiennoprzecinkowy podwójnej precyzji długi.
	Void	typ pusty oznaczający brak wartości (stosowany w ANSI C). ¯adna zmienna nie może być typu void. Tylko parametry przekazywane do funkcji mogą być typu void (oznacza wtedy, że do funkcji nic się nie przekazuje) lub zwracane przez funkcję (funkcja nic nie zwraca). Oprócz tego typ void może być stosowany przy tworzeniu pewnych typów złożonych.
Bolean		typ logiczny

Dla każdego z typów całkowitych: int, short int, long int oraz char możliwe są następujące modyfikatory:

unsigned - typ bez znaku (tylko wartości dodatnie)

W ANSI C możliwy jest również modyfikator signed oznaczający typ ze znakiem.

Przykład:

C Pascal

#include<iosreaem.h> void main() { int a=1; float b=2.5; char znak='a'; cout << a << b << znak; }

Program Am1; Uses Crt; Var a : integer; b : real; znak : char; Begin a:=1; b:=2.5; znak:='a'; WriteLn(a); WriteLn(b); WriteLn(znak); End.

4.2 Zmienne wskazujące (wskaźniki)

Wskaźniki służą do wskazywania na inne zmienne lub pewien obszar w pamięci komputera:

Wskażnik jest zmienną, która zawiera adres innej zmiennej.

Wskaźniki deklaruje się pisząc przed nazwą zmiennej znak '*', np:

int *p; zaś w paslalu znak `^', np: ^wsk : integer;.

Podany zapis określa typ zmiennej na jaki może wskazywać wskaźnik (w tym wypadku wskaźnik p , będzie mógł wskazywać na zmienną typu int). Typ zmiennej, na jaką może wskazywać wskaźnik, jest wykorzystywany przez kompilator podczas tłumaczenia niektórych operacji. Jeśli chcemy, by wskaźnik wskazywał na obszar pamięci nieokreślonego typu, musimy zadeklarować go jako wskaźnik na void, czyli:

void *mem;

W programie nazwa zmiennej zadeklarowanej jako wskaźnik, określa ten wskaźnik. Nazwa poprzedzona gwiazdką określa zmienną wskazywaną przez wskaźnik:

*p = 5;

Należy pamiętać, że wskaźniki w momencie deklaracji mają wartość nieokreśloną lub równą 0. Aby wskaźnik wskazywał na pewną zmienną należy nadać mu odpowiednią wartość. Jednym ze sposobów jest użycie operatora nadania adresu (&):

int x=1, y=2, z[10];

int *ip; ip jest wskaźnikiem do obiektów typu int

ip = &x; teraz ip wskazuje na x

y = *ip; y ma teraz wartość 1

*ip = 0; x ma teraz wartość 0

ip = &z[0]; teraz ip wskazuje na element z[0]

4.3. Typy strukturalne

4.3.1Struktury stosoane w C,

Struktura jest zbiorem elementów różnych typów. Każdy element struktury nazywany jest polem. Definicja struktury ma następującą postać:

Składnia definicji pola jest taka sama jak składnia definicji pojedynczej zmiennej. Nazwa pola (odpowiadająca nazwie zmiennej) jest nazwą lokalną widoczną tylko wewnątrz struktury. Struktura może posiadać nazwę. Można wtedy deklarować zmienne, będące strukturami opisanymi w definicji. Bezpośrednio po definicji struktury można podać nazwy zmiennych, które będą tymi strukturami. Dlatego możliwe jest również definiowanie struktur bez nazwy - definiuje się wtedy od razu odpowiednie zmienne.

Przykład:

struct osoba {
char nazwisko[25];
char imie[10];
int wiek;
} klient;

W pewnych sytuacjach może istnieć potrzeba poinformowania kompilatora, że dana struktura zostanie zdefiniowana później.

Struktura taka nie musi być zdefiniowana, aż do momentu, w którym kompilator nie będzie musiał obliczyć jej rozmiaru, tzn. do momentu deklaracji pola lub zmiennej tego typu, wywołania operatora sizeof, itp.

Mając zdefiniowaną strukturę o określonej nazwie, można używać jej do definicji zmiennych lub pól innej struktury tak jak nowego typu.

Po zadeklarowaniu zmiennych strukturowych można odwoływać się do nich jako całości lub do poszczególnych pól. W szczególności można przypisywać jedną zmienną strukturową drugiej (tego samego typu) za pomocą pojedynczego operatora przypisania. Odwołanie do pola struktury jest możliwe przy użyciu operatora '.'. Z lewej strony podaje się nazwę zmiennej strukturowej, z prawej nazwę pola:

Przykład:

struct osoba {
char nazwisko[25];
char imie[10];
int wiek;
};

void main(void)
{
struct osoba klient;

printf(Nazwisko: ");
scanf(%s", klient.nazwisko);
printf(Imie: "); BRP> scanf(%s", klient.imie); BRP> printf(Wiek: "); BRP> scanf(%d", &klient.wiek);
printf(Klient: %s %s; %d lat\n", klient.imie,
klient.nazwisko, klient.wiek);
}

Struktury podobnie jak tablice można inicjować w deklaracji podając wartości kolejnych pól na liście zamkniętej w nawiasy klamrowe. Można również inicjować tablice struktur (we wszystkich kompilatorach możliwości inicjalizacji w deklaracji są dostępne od ANSI C):

struct complex {double re, double im};
struct complex l1 = {12.1, 45.7};
struct complex liczby[] = {{1,2}, {1.2, 3.6}, {1.4, 6.5}};

jest zbiorem elementów zajmujących ten sam obszar pamięci.

4.3.2. Rekordy

Rekordami nazywa się złożoną strukturę danych, której składowe, zwane polami, mogą mieć różne charakterystyki(należeć do różnych typów). Poszczególne pola mogą być same strukturami złożonymi, przy czym liczba pól rekordu jest ustalona. Przykładem może być karta pracownika, w której pewne pola są typu prostego, inne typu strukturalnego.

Definicja rekordu rozpoczyna się od słowa kluczowego record, po którym podaje się deklarację każdego pola, a kończy słowem kluczowym end. Poszczególne deklaracje pól oddziela się średnikami. Ostatnia deklaracja może być wariantowa.

Type identyfikator-typu = record

Lista-deklaracji-pól

End;

Przykład :

Type Przcownk = record

Nazwisko : string[15];

Imie : string[15];

Wiek : byte;

End;

5. Tablice

Tablica jest zbiorem elementów tego samego typu. Każdy element tablicy ma numer. Numer pierwszego elementu w tablicy jest zawsze równy zero w języku C, zaś w Pascalu jeden. W C nie można deklarować tablic wielowymiarowych, jest jednak możliwa deklaracja tablic zawierających tablice, co odpowiada tablicom wielowymiarowym w innych językach.

Przykład:

int arr[10]; - język C,

type Tablica = array[1..10] of integer - język Pascal,

Każdy element deklarowanej tablicy ma typ zadeklarowanej tablicy, pierwszy element będzie miał numer 0, drugi 1, ... , ostatni rozmiar-1.

Jeśli chodzi o język Pascal to pierwszy element ma wartość 1, ostatni rozmiar tablicy.

Tablicę w C można inicjować podając w deklaracji po jej nazwie i znaku równości listę wartości oddzielonych przecinkami i zamkniętych w nawiasach klamrowych. Jeśli tablica jest inicjowana w deklaracji, to nie jest konieczne podawanie jej rozmiaru. Możliwość ta jest dostępna we wszystkich kompilatorach ANSI C.

Przykład:

int a1[5] = {1,5,3,4,2};
int a2[] = {1,5,6,3,4,5,6};

a1[1]=1; - C

a1[1]:=1; - Pascal

Tablic używa się w programie podając nazwę zmiennej tablicowej oraz numer elementu, którego operacja ma dotyczyć ujęty w nawiasy kwadratowe. Jako numer elementu może służyć stała całkowita, zmienna typu całkowitego lub dowolne wyrażenie, którego wynikiem jest liczba całkowita. Nawiasy kwadratowe zawierające numer elementu tablicy nazywane są operatorem indeksowania.

Przykład:

int a[10];
int i;
i = 5;
a[5] = 10;
a[a[5] - 5] = 4;

Możliwe jest zadeklarowanie tablicy tablic (odpowiadającej tablicy dwu- lub więcej wymiarowej):

int a[10][15]; - C

type tablica = array[1..20,1..20] of integer - Pascal

Powyższa instrukcja deklaruje 10-cio elementową tablicę a, której polami są 15-sto elementowe tablice zmiennych typu int. Odwołanie do elementów tablicy następuje w sposób naturalny - najpierw podaje się numer tablicy, potem numer elementu wewnątrz tej tablicy:

a[4][5] = 10;

Niepoprawne jest: a[10][9] = 6;

Podobnie odwołujemy się do tablicy wielowymiarowej w Pascal.

5.1. Tablice i wskaźniki w języku C

Nazwa tablicy (bez nawiasów []) oznacza wskaźnik na pierwszy element tej tablicy (element o numerze 0). Nazwa tablicy jest jednak wskaźnikiem stałym, tzn. nie można przypisać jej innego wskaźnika. Możliwa jest jednak operacja odwrotna tzn. przypisanie wskaźnikowi nazwy tablicy:

int dane[10];
int *p;
p = dane;

Na wskaźnikach można wykonywać operacje dodawania lub odejmowania liczb całkowitych. Dodanie liczby całkowitej n do wskaźnika powoduje, że wynik wskazuje o n elementów dalej niż wskaźnik wyjściowy. Nie można stosować dodawania lub odejmowania liczb do wskaźników typu void *, ponieważ nie wiadomo na jakiego typu element wskazuje. Ponieważ nazwa tablicy jest wskaźnikiem na pierwszy element, więc również do tej nazwy można dodawać liczbę całkowitą (n) i w ten sposób uzyskać wskaźnik na element tablicy o numerze n. Aby uzyskać wartość zmiennej, na którą wskazuje wskaźnik należy przed nazwą tego wskaźnika napisać '*'. Operator '*' nazywa się operatorem wyłuskania. Dostęp do elementu tablicy o numerze n można, więc uzyskać na 2 sposoby:

1. dane[n]

2. *(dane + n)

W przypadku odwołania do wskaźnika, który nie jest tablicą (ale może wskazywać na pewien element tablicy) można również stosować oba podane wyżej sposoby!

Poprawne są zapisy:

p = dane;
p[2] = 2;

oraz

p = dane +1;
p[1] = 2;

i są one równoważne zapisowi:

dane[2] = 2;

5.2 Tablice wielowymiarowe.

W języku C nie można zadeklarować tablicy wielowymiarowej. Możliwe jest zadeklarowanie tylko tablicy tablic:

int dane[10][12];

Wyżej przedstawiona deklaracja powoduje utworzenie 10 elementowej tablicy 12 elementowych tablic zmiennych typu int. Nazwa tablicy jest wskaźnikiem na pierwszy element. Z tego wynika, że dane wskazuje na 12 elementową tablicę zmiennych typu int. Podobnie dane + 1, dane + 2, itd. Natomiast dane[2] będzie wskazywać na pierwszy element tablicy o numerze 2. Tablice o liczbie wymiarów większej od 1 zadeklarowane jako tablice tablic przechowywane są w ciągłym obszarze pamięci. Funkcjonalnie podobne (można stosować podwójny operator indeksowania), ale zajmujące nieco więcej pamięci, jest utworzenie tablicy wskaźników, które będą wskazywać na tablice jednowymiarowe. Zaletą tego rozwiązania jest to, że nie jest potrzebny jeden ciągły obszar pamięci o dużym rozmiarze, ale wystarczy kilka o mniejszym. Każda z tablic jednowymiarowych może znajdować się bowiem w innym miejscu pamięci.

Z powyższą deklaracją funkcjonalnie prawie równoważne jest utworzenie tablicy wskaźników na tablice trzyelementowe:

Do elementu każdej z tablic można się odwoływać za pomocą operatora indeksowania podając numer tablicy oraz numer elementu w tej tablicy:

dane[3][1] = 5;

Ta właściwość języka C pozwala na tworzenie tablic wielowymiarowych o dowolnych indeksach (numerach elementów) oraz takich, których całkowity rozmiar nie jest znany w momencie kompilacji.

6. 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.

7. Struktury dynamiczne

Każdy większy program wykorzystuje złożone struktury tworzone na stercie, które nazywane są strukturami dynamicznymi. Takie złożone struktury, zwane też listowymi, są uporządkowanymi zbiorami składników, niekonieczne o jednakowych typach. Poszczególne składniki mogą być elementami prostymi (np. liczbami i pojedynczymi znakami ) lub elementami złożonymi (np. tablicami, obiektami a nawet listami). Zmienne typów wskaźnikowych są wykorzystywane do programowania dynamicznych struktur danych, którym pamięć jest przydzielana i zwalniana w trakcie wykonywania programu. Do tych struktur możemy zaliczyć listy, drzewa, grafy, stosy i kolejki.

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.

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.

7.1 LISTY : lista jest oszczędną pamięciowo strukturą danych, pozwalającą grupować dowolną - ograniczoną tylko ilością dostępnej pamięci - liczbę elementów : liczb, znaków, rekordów... Listą nazywamy liniowo uporządkowany zbiór składników, z którego w dowolnym miejscu można usunąć składniki, jak również dołączyć nowy składnik.

W zależności od powiązań pomiędzy składnikami wyróżniamy :

• listy jednokierunkowe,

• listy dwukierunkowe,

• listy cykliczne.

7.1.1 Lista jednokierunkowa

Logiczną strukturę listy jednokierunkowej przedstawia rysunek:

Każdy element listy zawiera pewne dane oraz wskaźnik na następny element. Ostatni element listy jednokierunkowej ma wskaźnik ustawiony na NULL. Dostęp do listy umożliwia wskaźnik na jej pierwszy element (na rysunku nazwany "początek"). Zmienna wskaźnikowa Poczatek typu wskaznik_listy1* jest tzw. głową lub korzeniem listy i służy za punkt wejścia do niej.

Odpowiadająca jednemu elementowi listy definicja struktury ma następującą postać:

C	Pascal
Typedef struct wskaznik_listy1 { Typ_danych dane_1; Typ_danych dane_n; struct wskaznik_listy1 *Nastepny; } TYP_PODSTAWOWY;	Type wskaznik_lisy1=^składnik_listy1 Skladnik_listy1=record dane_1 : typ_danych; dane_n : typ_danych; Nastepny : wskaznik_listy1; End;

Listy jedno i dwukierunkowe są najczęściej wykorzystywanymi w programach strukturami dynamicznymi. Umożliwiają przechowywanie dowolnej ilości danych (zmiennej w czasie). Wstawianie do listy na początku, na końcu i w środku jest stosunkowo proste. Dlatego można łatwo zachować uporządkowanie. Wyszukiwanie w listach jest jednak mało efektywne - pomimo tego, że lista jest uporządkowana, należy przeglądać wszystkie elementy po kolei, co daje złożoność rzędu n/2, gdzie n jest liczbą elementów. Metoda binarna przy wyszukiwaniu w tablicy uporządkowanej ma natomiast złożoność logarytmiczną.

7.1.2 Lista dwukierunkowa

Struktura logiczna:

listyd.giflistyd.gif

Każdy element listy dwukierunkowej oprócz danych zawiera wskaźnik na element następny i element poprzedni. Dostęp do listy umożliwia wskaźnik na jej pierwszy element. Możliwe jest również zastosowanie wskaźnika na ostatni element listy dwukierunkowej - przeglądanie listy można wykonywać wtedy od przodu lub od tyłu. Wskaźnik na następny element w ostatnim elemencie listy ma wartość NULL. Podobnie wartość wskaźnika na poprzedni element listy w pierwszym elemencie jest równa NULL. Niektóre operacje wykonywane na liście dwukierunkowej są prostsze niż na jednokierunkowej. Ceną jest jednak zajęcie większej ilości miejsca w pamięci - każdy element zamiast jednego wskaźnika musi mieć dwa. Struktura odpowiadająca elementowi listy dwukierunkowej ma następującą postać:

C	Pascal
typedef struct wskaznik_listy1 { typ_danych dane_1; typ_danych dane_n; struct wskaznik_listy1 *Nastepny; struct wskaznik_listy1 *Poprzedni; } TYP_PODSTAWOWY;	Type wskażnik_lisy2=^składnik_listy2 Składnik_listy2=record Dane_1 : typ_danych; Dane_n : typ_danych; Nastepny : wskażnik_listy2; Poprzedni : wskażnik_listy2; End;

Listy dwukierunkowe, w porównaniu z jednokierunkowymi, dają większą swobodę poruszania się po liście.

7.1.3 Listy cykliczne

Listy cykliczne mogą być jedno lub dwukierunkowe. Różnią się tym od zwykłych list, że wskaźnik na następny element w ostatnim elemencie nie ma wartości NULL, ale wskazuje na początek listy. Dodatkowo w liście cyklicznej dwukierunkowej, wskaźnik na element poprzedni w pierwszym elemencie listy wskazuje na element ostatni. W przypadku list cyklicznych początek i koniec są pojęciami umownymi - można je odróżnić tylko za pomocą zewnętrznego wskaźnika, którego położenie może się dowolnie zmieniać. Struktury w języku C, Pascalu odpowiadające elementom list cyklicznych są takie same jak odpowiadających im list zwykłych.

Struktura logiczna listy cyklicznej jednokierunkowej.

Struktura logiczna listy cyklicznej dwukierunkowej.

7.2 Drzewa

Drzewa są strukturami hierarchicznymi i rekurencyjnymi. Można je podzielić na drzewa mnogościowe (każdy węzeł może mieć dowolną ilość potomków) lub najprostsze - drzewa binarne, gdzie każdy węzeł ma nie więcej niż dwóch potomków. Przykład drzewa binarnego przedstawia rysunek:

drzewa1.gifdrzewa1.gif

Wskaźnik umożliwiający dostęp do całego drzewa wskazuje na węzeł, który nie jest niczyim potomkiem. Węzeł ten nazywa się korzeniem drzewa. Każdy węzeł drzewa binarnego ma co najwyżej dwóch potomków - synów: lewego i prawego. Jeśli pewien węzeł nie ma jednego z potomków to odpowiedni wskaźnik jest ustawiony na NULL. Rekurencyjność struktury drzewiastej polega na tym, że każdy węzeł

może być rozpatrywany jako drzewo (część zaznaczona w kółku może być potomkiem korzenia), ale również może być traktowany tak jak osobne drzewo binarne. Stąd algorytmy operujące na strukturach drzewiastych są najczęściej funkcjami rekurencyjnymi.

Struktura odpowiadające węzłowi drzewa binarnego może mieć postać:

C	pascal
Typedef struct typ_p { int idWezla; typ_danych dane_1; typ_danych dane_n; struct typ_p *lewy, *prawy; } TYP_P;	Type wskażnik_drzewa=^składnik_drzewa; Składnik_drzewa=record Dane_1 : typ_danych; Dane_n : typ_danych; prawy : wskażnik_drzewa; lewy : wskażnik_drzewa; End;

Drzewa binarne mogą być używane do przechowywania danych, których ilość może się zmieniać i dane te trzeba szybko wyszukiwać. Dana, która ma zostać znaleziona jest wtedy przechowywana w węzłach drzewa. Pierwsza informacja jest wstawiana jako korzeń drzewa. Kolejne dane są wstawiane tak, że w każdym węźle dane mniejsze lub równe od danej w tym węźle znajdują się na lewo, natomiast większe - na prawo. Taka organizacja przyspiesza znacznie wyszukiwanie, ponieważ chcąc sprawdzić czy dana informacja istnieje, nie sprawdza się wszystkich elementów, ale tylko jedną ścieżkę w drzewie.

drzewa2.gifdrzewa2.gif

Wada tego typu reprezentacji polega na tym, że budowa drzewa, a więc również efektywność wyszukiwania, zależy od kolejności przychodzenia danych. W najgorszym przypadku drzewo wyszukiwań może się zdegenerować do listy, nie będzie więc żadnych pożytków z jego zastosowania. Aby uniknąć tego typu sytuacji stosuje się tzw. drzewa AVL-wyważone (są to zwykłe drzewa binarne, ale algorytmy obsługi zapewniają, by prawe i lewe poddrzewo w każdym węźle było mniej więcej tej samej wysokości).

7.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.

7.4. Stos

Stos jest bardzo często używaną w programowaniu strukturą. Stos bywa nazywany również kolejką LIFO (Last In First Out). Stos jest to struktura danych składająca się z liniowo uporządkowanych zbiorów składników (elementów), z których tylko „największy” jest w danej chwili dostępny. Miejsce dostępu nazywa się wierzchołkiem stosu. Jest to jedyne miejsce, do którego można dołączyć lub z którego można usuwać elementy. Elementy ostatnio położone na stosie są z niego zdejmowane przed elementami położonymi wcześniej. Do obsługi stosu służy zmienna nazywana wskaźnikiem stosu. Wskaźnik stosu może pokazywać ostatnio położony element lub pierwsze wolne miejsce na stosie. Zdejmowany ze stosu jest element, na który wskazuje wskaźnik stosu.

stos.gifstos.gif

Stos może być implementowany za pomocą tablicy. Wskaźnikiem stosu jest wtedy zmienna będąca indeksem w tablicy wskazująca ostatnio położony na stosie element. Stos może być również implementowany przy użyciu listy jednokierunkowej. Szczyt stosu znajduje się wtedy na początku listy. Nowe elementy kładzione na stos są zawsze dołączane na początek listy. Elementy zdejmowane są zawsze z początku. Implementacja stosu przy pomocy listy jest bardzo prosta i wygodna, dlatego jest często stosowana.

C	Pascal
typedef struct wskaznik_stosu { typ_danych dane; struct wskaznik_stosu *Najwiekszy; } TYP_PODSTAWOWY;	Type wskażnik_stosu=^składnik_stosu Składnik_stosu=record Dane : typ_danych; Najwiekszy : wskaźnik_stosu; End;

7.5 Kolejka

Kolejka jest dynamiczną strukturą danych typu FIFO (First In First Out). Kolejka może być w prosty sposób implementowana na liście jednokierunkowej przy pomocy dwóch wskaźników - wskaźnika na początek listy (jest to równocześnie wskaźnik na pierwszy element, który zostanie z kolejki pobrany) oraz wskaźnika na koniec listy (jest to miejsce, gdzie będą wstawiane elementy dopisywane do kolejki). Kolejka jest strukturą danych składającą się z liniowo uporządkowanych zbiorów składników, do której można dołączyć składnik tylko w jednym końcu(na koniec listy), usunąć tylko w drugim końcu (na początku kolejki).

C	Pascal
Typedef struct wskaznik_kolejki { TYP_DEF *Informacja; struct wskaznik_kolejk *Nastepny; struct wskaznik_kolejk *Poprzedni; } WSKAZNIK_KOLEJI; typedef struct { int IloscElementow; WSKAZNIK_KOLEJKI *Elementy; } KOLEJKA;	Type wskażnik_kolejki=^składnik_kolejki Składnik_kolejki=record Dane : typ_danych; Wskaźnik : wskażnik_kolejki; End;

8. Przykładowe funkcje

8.1. C

8.1.1 Wstawianie elementu na początek listy jednokierunkowej ( C )

Operacja wstawiania elementu na początek listy jednokierunkowej może być użyta do implementacji operacji Push(element) na stosie. Cyfry na rysunku wskazują kolejność wykonywania operacji (zmian wartości wskaźników).

Przykładowa funkcja Push(element) może mieć postać:

void Push(Elem element)
{
struct ListElem * wsk = malloc(sizeof(struct ListElem));
if (le == NULL)

{
printf("element nie zostal utwozony \n");
exit(1);
}

wsk -> dana_1 = element;
wsk -> nastepny = poczatek;
poczatek = wsk;

return;
}

8.1.2 Wstawianie elementu na koniec listy jednokierunkowej

Operacja wstawiania elementu na koniec listy jednokierunkowej może być wykorzystana do implementacji kolejki FIFO.

funljk.gif

Przykładowa funkcja wstaw wstawiająca element na końcu listy jednokierunkowej:

void rt(Elem element)

{
struct ListElem * le = malloc(sizeof(struct ListElem));
if (le == NULL)

{
printf("Blad w lokacji pamieci \n");
exit(1);
}

le -> dana_1 = element;
le -> nastepny = NULL;
koniec -> nastepny = le;
koniec = le;
return;
}

8.1.3 drzewo

typedef struct czlowiek {
char Nazwisko[30];
char Imie[15];
struct czlowiek *Ojciec;
struct czlowiek *Matka;
} CZLONEK_RODZINY;

CZLONEK_RODZINY *CzlonekRodzinyNowy(char *Nazwisko, char Imie);
void WypiszLinieMeska(CZLONEK_RODZINY *p);

main() {
CZLONEK_RODZINY *OstatniJagiellon;
CZLONEK_RODZINY *crp;
crp=OstatniJagiellon=CzlonekRodzinyNowy("Trzeci August", "Zygmunt");
crp->Ojciec=CzlonekRodzinyNowy("Drugi Stary", "Zygmunt");
crp->Matka=CzlonekRodzinyNowy("Sforza d'Aragona" , "Bona");
crp=crp->Ojciec;
crp->Ojciec=CzlonekRodzinyNowy("Czwarty", "Kazimierz");
WypiszLinieMeska(OstatniJagiellon);
}

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.

8.2 Pascal przykłady

8.2.1 Procedura tworzenia stosu i dołączenia do niego składników(pascal)

Procedure NaStos (var element : typ-danych;

var wierzcholek : wskaznik_stosu);

var punkt : wskaznik_stosu;

begin

punkt:=wierzchołek;

New(wierzchołek);

With wierzchołek^ do

Begin

Dane:=element;

Wskaznik:=punkt;

End;

End;

Wywołanie procedury NaStos w chwili tworzenia stosu, tj. zapisywania jego pierwszego składnika, wymaga, aby drugi argument wywołania (odpowiadający parametrowi wierzchołek) reprezentował adres pusty(nil). Pierwsza instrukcja przypisania, występująca w treści procedury, powoduje zapamiętanie pod zmienną punkt adresu aktualnego wierzchołka stosu. Następnie, za pomocą wywołania procedury New, jest tworzona zmienna dynamiczna o adresie podstawionym pod zmienną wierzcholek. A dokładniej : w segmencie pamięci przeznaczonym na zmienne dynamiczne zostanie przydzielony blok pamięci o rozmiarze równym rozmiarowi typu, z którym związana jest zmienna wierzcholek , a adres początku tego bloku zostanie przypisany tej zmiennej. Ostatnie dwie instrukcje przypisania powodują zapamiętanie w stosie wprowadzonego elementu oraz zapamiętanie dla danego składnika adresu składnika następnego w stosie, tzn. tego, który w chwili wywołania procedury znajdował się na jego wierzchołku.

8.2.2 Procedura tworzenia i dołączenia na jej końcu nowych składników(pascal)

Procedure DoKolejki (var element : typ-danych;

var koniec_kolejki : wskaznik_stosu);

var punkt : wskaznik_kolejki;

begin

punkt:=koniec_kolejki;

New(koniec_kolejki);

With koniec_kolejki^ do

Begin

Dane:=element;

Wskaznik:=nil;

End;

If punkt<>nil

Then punkt^.wskaznik:=koniec_kolejki

End;

End;

Wywołanie procedury DoKolejki w chwili tworzenia kolejki, tj. zapisywania pierwszego składnika, wymaga, by drugi argument wywołania (odpowiadający parametrowi koniec_kolejki) reprezentował adres pusty (nil). Wykonania instrukcji przypisania punkt:=koniec_kolejki; powoduje zapamiętanie pod zmienną punkt adresu aktualnego końca kolejki. Następnie, za pomocą procedury New, jest tworzona nowa zmienna dynamiczna, której adres zostanie podstawiony pod zmienną koniec_kolejki. Ponieważ jest to ostatni element kolejki, więc zmienna koniec_kolejki^.wskaznik wskazuje na adres pusty (nil). Elementu, który był ostatni w kolejce przed wywołaniem procedury musi wskazywać na aktualnie ostatni element. Skąd też konieczna jest ostatnia instrukcja przypisania ( jeśli do kolejki nie wprowadza się pierwszego elementu).

8.2.3 Procedura tworzenia listy jedno kierunkowej i dołączania do niej nowych składników.

Procedure DoListy (var element : typ-danych;

var skladnik_biezacy : wskaznik_listy);

var poprzedni_skladnik,nastepny_skladnik : wskaznik_listy;

begin

if skladnik_biezacy <>nil

then begin

poprzedni_skladnik:=skladnik_biezacy;

nastepny_skladnik:=skladnik_bieaacy^.wskaznik;

end

else begin

poprzedni_skladnik:=nil;

nastepny_skladnik:=nil;

end;

New(skladnik_biezacy);

With skladnik_biezacy^ do

Begin

Dane:=element;

Wskaznik:=nastepny_skladnik;

End;

If poprzedni_skladnik<>nil

Then poprzedni_skladnik^.wskaznik:=skladnik_biezacy

End;

Wywołanie Procedury DoListy w momencie tworzenia listy, tj. zapisywania jej pierwszego składnika, wymaga ,aby drugi argument wywołania (odpowiadający parametrowi skladnik_biezacy) reprezentował adres pusty (nil). W pierwszej instrukcji warunkowej sprawdza się, czy do listy dołącza się nowy składnik, czy też zapisuje się jej pierwszy składnik. Jeśli do listy dołącza się nowy składnik (adres tego elementu podaje drugi argument wywołania, odpowiadający parametrowi skladnik_biezacy), to pod zmiennymi poprzedni_skladnik i nastepny_skladnik zapamiętuje się powiązania z dołączanym składnikiem. W drugim przypadku zmiennym tym przypisuje się adres pusty(nil). Następnie, za pomocą procedury New, jest tworzona nowa zmienna dynamiczna, której adres zostanie postawiony pod zmienną skladnik_biezacy. Ustala się przy tym powiązania rekordu skladnik_biezacy^ z następnym składnikiem listyoraz wprowadza się do niego element (dokładniej :wartość zmiennej element jest przypisywania do pola skladnik_biezacy^.dane). Ostatnia instrukcja warunkowa służy do ustalenia powiązania pomiędzy starymi składnikami listy i nowym dołączonym do niej składnikiem.

9. Zakończenie

Listy ułatwiają tworzenie elastycznych baz danych. W dalszej części postaram się przedstawić najważniejsze struktury danych i sposoby posługiwania się nimi.

10. Wykaz literatury, adresów internetowych

Literatura

1. Andrzej Marciniak - „Turbo Pascal 7.0” Wydawnictwo NAKOM, Poznań 1994.

2. Brian W.Kernighan - „język C” Wydawnictwo Naukowo-Techniczne, Warszawa

3. Ss

4. Ss

5. Ss

Adresy internetowe

http://www.sun 10.ci.pwr.wroc.pl/~krukiew/nowell1.htm

http://www.ita.pwr.wroc.pl/cennik/sieci.htm

http://www.man.poznan.pl/~pawelw/dyplom

http://www.3com.com.pl

http://www.tmx.com.pl/R&deM/ceny.htm

http://www.man.poznan.pl/~pawelw/dyplom/topologie.html

http://www.techmex.com.pl

http://www.ws.pl

http://www.vatim.com.pl

http://www.kenopole.com.pl

---