listy_wskazniki,pascal.pdf

Dynamiczne struktury danych: listy

Mirosław Mortka

Zaczynając programować w dowolnym języku programowania jesteśmy

zmuszeni do opanowania zasad posługiwania się podstawowymi typami danych. Na

przykład w języku Pascal posługujemy się m.in. typami: integer , real , string ,

array , record itp. Zmienne zadeklarowane za ich pomocą nazywamy zmiennymi

statycznymi . Ich zastosowanie łączy się z uzyskaniem wielu zalet, choćby spójność

danych czy szybki dostęp do elementów. Posiadają jednak bardzo istną wadę, mocno

ograniczającą możliwość ich zastosowania: musimy z góry określić wielkość i ilość

elementów. Jednakże wiele zagadnień charakteryzuje się zmiennością struktur danych

podczas procesu obliczeniowego. W tym wypadku z pomocą przychodzą nam zmienne

dynamiczne .

Niewątpliwą korzyścią wynikającą ze stosowania tych typów jest możliwość

określenia wielkości zajmowanej przez nich pamięci dopiero w trakcie trwania

programu. Taka deklaracja struktury danych powoduje jednak, iż kompilator nie jest

w stanie określić konkretnych adresów dla poszczególnych zmiennych ani przydzielić

na nie pamięci. W konsekwencji zmuszeni jesteśmy do dynamicznego przydzielania

pamięci , tzn. przydzielania pamięci zmiennym w momencie użycia ich przez program

(utworzenia nowej zmiennej w trakcie wykonania programu) zamiast przydzielania im

stałej ilości pamięci podczas translacji programu. Kompilator przydziela wtedy stałą

ilość pamięci na adres zmiennej umieszczanej dynamicznie w pamięci zamiast na

samą zmienną. Zmienne, które zawierają adres i tym samym wskazują położenie

innego obiektu lub zmiennej w pamięci, nazywamy wskaźnikami . W języku Pascal

zmienną wskaźnikową oznaczamy ^.

Korzystając z dynamicznych struktur danych możemy operować na listach ,

drzewach czy grafach .

Listy jednokierunkowe

Najprostszym sposobem pozwalającym grupować dowolną ilość danych

(ograniczoną tylko rozmiarem dostępnej pamięci) jest lista jednokierunkowa (patrz rys.

1). W tym przypadku każdy element jest pojedynczym rekordem składającym się z co

najmniej dwóch pól: pola wartości i wskaźnika do następnego elementu listy.

Wartością wskaźnika umożliwiającą jednoznaczne zidentyfikowanie ostatniego

elementu listy w języku Pascal jest specjalna wartość nil ( NULL w C/C++).

Rys. 1. Przykład listy jednokierunkowej

W przypadku list jednokierunkowych nie jest możliwy bezpośredni dostęp do

dowolnego jej elementu. Ponieważ każdy element posiada jedynie wskaźnik do jego

następnika, więc dotarcie do n -tego elementu listy wymaga wcześniej przejścia przez

n-1 poprzedników.

Oto najprostsze operacje, jakie możemy wykonać na liście jednokierunkowej:

–wstawienie elementu na początek listy,

–wstawienie elementu na koniec listy,

–usunięcie pierwszego elementu listy,

–odczyt pierwszego elementu listy,

–dostęp do dowolnego elementu listy.

W zależności od wyboru podstawowych operacji wykonywanych na liście

możemy wyróżnić dwa podstawowe rodzaje struktur implementowanych na podstawie

list jednokierunkowych:

– stos : możliwe jest wstawianie, usuwanie i odczyt pierwszego elementu listy

– wierzchołka; tego typu struktura nazywana jest LIFO 1 (rys. 2),

– kolejka (pojedyncza, jednokierunkowa): wstawianie elementu na koniec

listy, odczyt i usuwanie elementu pierwszego – struktura typu FIFO 2 (rys. 3).

wierzchołek

wstawianie, usuwanie, odczyt

dno stosu

Rys. 2. Struktura stosu

poc kon

usuwanie, odczyt

wstawianie

Rys. 3. Struktura kolejki

1 ang . last in, first out

2 ang . first in, first out

Podstawowe operacje dotyczące listy jednokierunkowej omówimy na podstawie

zadania 1.

Zadanie 1.

Napisać program odwracający plik tekstowy plik.wej . Wynikiem wykonania

programu ma być drugi plik tekstowy plik.wyj . Pierwszym wierszem pliku

wyjściowego ma być ostatni wiersz pliku wejściowego, drugim – przedostatni itd.

Założyć, że wiersze nie przekraczają 255 znaków 3 .

Rozwiązanie

Definiowanie listy w Pascalu

Zdefiniujmy typ elementów listy wierszy pliku. Każdy taki element zawiera ciąg

znaków pochodzący z kolejnej linii pliku tekstowego oraz wskaźnik do elementu

następnego. W języku Pascal definicja ta będzie miał następujący wygląd:

type

PElem = ^TElem; (1)

TElem = record (2)

s: string;

nast: ^TElem; (3)

end;

Zaczynamy od zdefiniowania typu wskaźnikowego PElem do danych typu

TElem (1). Druga definicja (2) narzuca strukturę każdej zmiennej typu TElem

składającą się z dwóch pól: s zawierającego linię tekstu pliku oraz nast zawierającego

wskaźnik do następnego elementu. ^ to symbol wskaźnika. Deklarując zmienną p typu

PElem , używamy zapisu p^ do wskazania rekordu typu TElem .

Wśród zmiennych globalnych musimy zadeklarować zmienną poc typu PElem

wskazującą na początek listy wykorzystywanej w zadaniu.

var

poc: PElem;

Uwaga: Składnia języka Pascal zabrania użycia nazwy, której znaczenie nie

zostało wcześniej zdefiniowane. Definicja typu wskaźnikowego wykorzystującą nazwę

obiektu wskazywanego jest jedynym wyjątkiem od tej reguły.

3 K.Jakubczyk: Turbo Pascal i Borland C++. Przykłady. , Helion, Gliwice2002, s. 149

Dodawanie nowego elementu na początek listy

Wstawienie elementu p na początek listy poc wymaga wykonania dwóch

operacji przypisania wartości zmiennym typu wskaźnikowego:

a) nadanie polu nast wskazywanemu przez wskaźnik p wartości adresu

przechowywanego przez wskaźnik do początku listy poc (rys. 4a);

p^.nast:= poc;

b) uaktualnienie wartości zmiennej poc poprzez przypisanie jej wartości

wskaźnika do elementu p (element p zostaje umieszczony na pierwszym

miejscu listy poc – rys. 4b).

poc:= p;

poc

Rys. 4. Dodanie elementu p na początek listy poc

Wstawianie elementu p na początek listy poc możliwe jest wówczas, gdy

element p istnieje (został wcześniej utworzony). W przeciwnym wypadku musimy

utworzyć nowy element i uaktualnić jego pola (nadać im wartości początkowe).

Procedurą przydzielającą pamięć oraz generującą wskaźnik do nowego elementu jest

polecenie new .

new(p);

p^.s:= ‘Początkowa wartość’;

Procedura wczytującą kolejne linie tekstu i umieszczającą je na początku listy

będzie zatem miała następujący wygląd:

procedure UtworzListe;

var

p: PElem; {wskaźnik pomocniczy}

f: text; {zmienna reprezentującą

plik tekstowy}

s: string; {zmienna pomocnicza do

wczytywania linii tekstu

z pliku}

begin

ReadLn(f,s); {czytaj linię tekstu

z pliku}

new(p); {utwórz nowy element p}

p^.s:= s; {przypisz do pola s

wskazywanego przez p

łańcuch s}

p^.nast:= poc; {wstaw element}

poc:= p; {na początek listy poc}

end ;

Close(f); {zamknij plik}

end ;

Każda nowa wczytana linia tekstu zostaje wstawiona na początek listy.

W wyniku tej operacji uzyskujemy strukturę listową zawierająca w pierwszym

elemencie ostatnią linię tekstu znajdującego się w pliku, w drugim przedostatnią itp.

Wystarczy teraz wypisać kolejne elementy listy do pliku plik.wyj , aby nasze zadanie

zostało pomyślnie zakończone.

Przeglądanie listy

Zmienna poc przechowuje adres pierwszego elementu listy w pamięci. Nie

możemy modyfikować jej wartości, gdyż wiązałoby się to z utratą informacji na temat

położenia pierwszego elementu, a co z tym się wiąże – również pozostałej części listy.

Wprowadźmy więc zmienną pomocniczą p typu PElem (wskaźnik do TElem ) i z jej

pomocą dokonajmy przeglądu elementów listy.

Przeglądanie listy będzie przebiegać w następujących etapach:

a) zmienna p wskazuje na początek listy (rys. 5a);

p:= poc;

b) wypisz pole s zmiennej wskazywanej przez p;

WriteLn(p^.s);

begin

Assign(f,'plik.wej'); {otworzenie pliku}

Reset(f); {do odczytu}

poc:=nil; {początkowo lista jest

pusta}

while not Eof(f) do {dopóki nie został

osiągnięty koniec pliku}

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: