WY6TEPRO


Prof.nadzw.dr hab.inż. Władysław Brzozowski

Politechnika Częstochowska

Instytut Elektroenergetyki

Wykłady z przedmiotu:

TECHNIKA PROGRAMOWANIA

studia magisterskie, kierunek Elektrotechnika,

specjalno** Informatyka w Elektroenergetyce, sem.VI

Wyk*ad 6. J*zyk Turbo-Pascal. Dynamiczne struktury danych w systemie Turbo-Pascal

1. Formy danych w systemie Turbo Pascal. Cel stosowania dynamicznych struktur danych

W systemie Turbo Pascal wyr**niamy dane statyczne i dynamiczne. Dane statyczne dzielimy na lokalne i globalne.

Dane statyczne lokalne zajmuj* obszar tzw. segmentu stosowego (stack) o rozmiarze okre*lanym przez programist*, ale nie mniejszym ni* 1024 i nie wi*kszym ni* 65520 bajt*w.

Dane statyczne globalne zajmuj* obszar jednego segmentu pami*ci operacyjnej, a wi*c 65520 bajt*w. W efekcie **czny maksymalny rozmiar danych statycznych jest ograniczony i w przypadku programu operuj*cego na du*ej liczbie danych nie wystarcza.

Wprowadzamy zatem do programu dane dynamiczne w postaci zmiennych wskazywanych. Dane te zajmuj* obszar tzw. sterty (heap) o rozmiarze okre*lanym przez programist*, w przedziale od 0 do 655360 bajt*w. Oznacza to, *e ca*a pami** podstawowa komputera mo*e by* zaj*ta przez dane dynamiczne. Wiemy te*, *e zmienne dynamiczne tworzymy a nast*pnie odwo*ujemy w dowolnych punktach programu. Wyobra*my sobie, *e tworzymy zmienn* wskazywan* typu tablica rekord*w:

type

RekXYZ = record

i: integer;

x: real;

t: string [34]

end;

var

tabl1: ^array [1..1000] of RekXYZ;

Na og** nie wiemy ile rekord*w przyjdzie nam zapisa* do tablicy, st*d rozmiar tej tablicy musi by* du*y, gdy* musi uwzgl*dnia* maksymaln* spodziewan* liczb* rekord*w.

Tak zorganizowana struktura jest wi*c ma*o efektywna (mo*naby j* nazwa* zdeterminowan* struktur* danych dynamicznych).

Efektywniejsza jest dynamiczna struktura danych dynamicznych - to jest taka w kt*rej liczba obiekt*w nie jest w *aden spos*b zdeterminowana - jest zmienna w poszczeg*lnych przebiegach programu.

Wyr**nia si* nast*puj*ce dynamiczne struktury danych:

Dynamiczna struktura danych

| - stos

| - kolejka

| - lista

| | - liniowa

| | | - jednokierunkowa

| | | - dwukierunkowa

| | - cykliczna

| - drzewo

| - binarne

| - wielokierunkowe

Wsp*ln* cecha powy*szych struktur danych jest to, *e elementem struktury jest zawsze rekord, zawieraj*cy:

Wyja*nimy te poj*cia na przyk*adzie konkretnych struktur. Trzeba tu koniecznie podkre*li*, *e omawiamy struktury wy**cznie danych w pamieci operacyjnej komputera. Nie maj* one nic wsp*lnego z pami*cia dyskowa. Po wy**czeniu komputera struktury te ulegaj* likwidacji, je*li wcze*niej nie zostan* one zlikwidowane przez program.

2. Stos

Poj*cia tego nie nale*y myli* ze stosem danych statycznych lokalnych. Tu stos jest struktur* dynamiczn* danych dynamicznych, tak* do kt*rej dok*adamy elementy zawsze przy ko*cu stosu (koniec ten nazywa si* wierzcho*kiem stosu). Usuwamy elementy ze stosu rownie* poczynaj*c od wierzcho*ka, tj. od ostatniego elementu, kolejno w d** do podstawy stosu. Odczyt element*w r*wnie* odbywa si* od wierzcho*ka, kolejno w d**. Brak jest bezpo*redniego dost*pu do element*w innych ni* ostatni element stosu.

Elementem stosu jest, jak ju* powiedziano zawsze rekord, o postaci (przyjmijmy *e obiektem roboczym jest rekord z danymi pracownik*w):

type

DanePracownika = record

Nazwisko: string [30];

Imie: string [20];

GrupaZaszeregowania: integer

end;

TypElementuStosu= ^RekordStosowy;

RekordStosowy = record

ObiektRoboczy: DanePracownika;

AdresPoprzedniegoElementuNaStosie: pointer

end;

var

ElementBiezacy: TypElementuStosu;

AdresWierzcholkaStosu,AdresPomocniczy: pointer;

Tak zorganizowany stos b*dzie mia* struktur* jak ni*ej (przedstawion* tak jakgdyby mia* on 3 elementy):

W stosie zapisane s* adresy poszczeg*lnych element*w z wyj*tkiem ostatniego. Aby wi*c, po utworzeniu stosu, m*c znale** go w pamieci operacyjnej, nale*y zapami*ta* w odr*bnej zmiennej typu wska*nikowego adres ostatniego elementu, czyli wierzcho*ka stosu. W powy*szym przyk*adzie jest to zmienna AdresWierzcholkaStosu.

Elementy stosu w *aden spos*b nie s* w pami*ci operacyjnej uporz*dkowane. Przeciwnie: tworz*c nowy element stosu, system operacyjny przydziela mu miejsce w pami*ci operacyjnej przypadkowe, tj. takie jakie w danym momencie jest wolne. Identyfikacja stosu nast*puje wy**cznie przez adresy zapisane w kolejnych elementach.

Ci*g instrukcji przy tworzeniu stosu od pocz*tku przedstawia si* nast*puj*co:

{1} New(ElementBiezacy); {utworzenie elementu nr.1}

Instrukcj* New(ElementBiezacy) tworzymy ka*dy kolejny element stosu, a nast*pnie zapisujemy w jego polu roboczym jakie* u*yteczne dane np.

{2} ElementBiezacy^.ObiektRoboczy.Nazwisko:='Nowak'; {generowanie pola

roboczego elementu}

Jest to przyk*adowa instrukcja generowania pola roboczego w zakresie przyk*adowego pola rekordu roboczego. Nast*pnie:

{3} ElementBiezacy^.AdresPoprzedniegoElementuNaStosie:=nil; {wpisanie

w polu wskaznikowym elementu nr.1 adresu pustego nil}

Poniewa* brak elementu zerowego zatem brak adresu do zapisu w odniesieniu do elementu nr.1.

{4} AdresPomocniczy:=ElementBiezacy; {zapamietanie adresu elementu

nr.1}

Adres ten musi zosta* zapami*tany w zmiennej pomocniczej wska*nikowej, gdy* po utworzeniu elementu nr.2 tracimy mo*liwo** operowania elementem nr. 1 i jego identyfikacji w pami*ci operacyjnej.

Nale*y zwr*ci* tu uwag*, *e zmienna ElementBiezacy jest typu wska*nikowego a nie rekordowego (zatem nie ma tu niezgodno*ci typu). Zmienna ElementBiezacy zawiera wy**cznie adres zmiennej wskazywanej w pami*ci operacyjnej, tj. w tym przypadku zmiennej RekordStosowy kt*ra jest typu rekordowego. Dlatego instrukcja powy*sza realizuje wy**cznie operacj* przepisania adresu pomi*dzy dwiema zmiennymi typu wska*nikowego.

{5} AdresWierzcholkaStosu:=ElementBiezacy;

Tworz*c kolejny element stosu nale*y stale aktualizowa* adres wierzcho*ka stosu, czyli adres ostatnio wygenerowanego elementu.

{6} New(ElementBiezacy); {utworzenie elementu nr.2}

{7} ElementBiezacy^.AdresPoprzedniegoElementuNaStosie:=

AdresPomocniczy; {wpisanie w polu wskaznikowym elementu nr.2 adresu elementu nr.1}

{8} AdresWierzcholkaStosu:=ElementBiezacy;

Aktualizacja adresu wierzcho*ka stosu.

Przy likwidacji stosu ci*g instrukcji przedstawia si* nast*pujaco:

{1} ElementBiezacy:=AdresWierzcholkaStosu; {lokalizacja ostatniego

elementu czyli wierzcholka stosu}

{2}AdresPomocniczy:=ElementBiezacy^.AdresPoprzedniegoElementuNaStosie;

{ustalenie adresu poprzedniego elementu na stosie i jego zapamietanie

w komorce pomocniczej}

Gdyby*my zlikwidowali ostatni element bez powy*szej operacji to utraciliby*my zdolno** dotarcia do elementu poprzedniego.

{3} Dispose(ElementBiezacy); {likwidacja elementu ostatniego}

{4} ElementBiezacy:=AdresPomocniczy; {lokalizacja elementu

poprzedniego}

{5} AdresWierzcholkaStosu:=ElementBiezacy; {aktualizacja adresu

wierzcholka stosu}

Itd. a* do podstawy stosu, tj. tak d*ugo a* zostanie spe*niony warunek ElementBiezacy^.AdresPoprzedniegoElementuNaStosie=nil

Operowanie innymi formami dynamicznych struktur danych dynamicznych realizuje si* podobnie; zatem procedury te nie bed* tu szczego*owo przytaczane. Zostanie dokonana jedynie og*lna charakterystyka tych struktur.

3. Kolejka

Kolejka jest struktur* do kt*rej zapis nowego elementu mo*e nast*powa* wy**cznie przy ko*cu kolejki, natomiast identyfikacja/odczytanie kolejki oraz ewentualne usuni*cie elementu nast*puje od pocz*tku kolejki.

Zgodnie z powy*szym kolejk* organizujemy za pomoc* poni*szych deklaracji (u*ywajac nazw jak dla w przyk*adzie wy*ej dla stosu):

type

TypElementuKolejki= ^RekordKolejkowy;

RekordKolejkowy= record

ObiektRoboczy: DanePracownika;

AdresNastepnegoElementuWKolejce: pointer

end;

var

ElementBiezacy,ElementPoprzedni: TypElementuKolejki;

AdresPoczatkuKolejki,AdresPomocniczy: pointer;

Jak wida* nast*puje tu zmiana adres*w - w polu wska*nikowym rekordu podaje si* nie adres poprzedniego elementu, jak to by*o w przypadku stosu, lecz nast*pnego. Podobnie, celem identyfikacji kolejki trzeba zapami*ta* adres pierwszego elementu czyli adres pocz*tku kolejki. Przetwarzanie kolejki wymaga te* wi*kszej liczby zmiennych pomocniczych.

4. Lista jednokierunkowa

Lista jednokierunkowa jest struktur* podobn* do stosu (je*li identyfikujemy list* od ko*ca) lub do kolejki (je*li identyfikujemy list* od pocz*tku).

Lista tym si* jednak r**ni od tych dwu struktur, *e zapis nowego elementu lub likwidacja elementu mo*e nast*powa* w dowolnym miejscu listy, tak*e w *rodku listy.

Je*li ostatni element listy pokrywa si* z pierwszym to taka lista nazywa si* list* cykliczn*, w przeciwnym razie jest to lista liniowa. Deklaracje dla listy jednokierunkowej wygladaj* podobnie jak dla stosu lub kolejki, i nie bed* tu przytaczane.

5. Lista dwukierunkowa

Lista dwukierunkowa ma wszystkie cechy listy jednokierunkowej, a ponadto identyfikacja mo*e nast*powa* zar*wno od strony pocz*tku jak i ko*ca listy. Odpowiednio, list* dwukierunkow* organizujemy za pomoc* poni*szych deklaracji (u*ywajac nazw jak dla w przyk*adzie dla stosu):

type

TypElementuListy= ^RekordListowy;

RekordListowy= record

ObiektRoboczy: DanePracownika;

AdresPoprzedniegoElementuNaLiscie: pointer

AdresNastepnegoElementuNaLiscie: pointer

end;

var

ElementBiezacy,ElementPoprzedni,ElementNastepny: TypElementuListy;

AdresPoczatkuListy,AdresKoncaListy,AdresPomocniczy1,AdresPomocniczy2,

AdresPomocniczy3: pointer;

Jak wida* nast*puje tu dalsza zmiana adres*w - w polu wska*nikowym rekordu podaje si* adres i poprzedzaj*cego elementu i nast*puj*cego elementu.

Podobnie, celem identyfikacji kolejki trzeba zapami*ta* adres zar*wno pierwszego jak i ostatniego elementu. Przetwarzanie listy dwukierunkowej wymaga jeszcze wi*kszej liczby zmiennych pomocniczych.

6. Drzewo

Drzewo jest struktur* w kt*rej za ka*dym elementem mo*na dopisa* nie jeden, lecz dwa (je*li jest to drzewo binarne) lub wi*cej (je*li jest to drzewo wielokierunkowe) element*w. Odpowiednio, w polu wska*nikowym ka*dego elementu nale*y zapisa* liczb* element*w nast*puj*cych oraz adresy wszystkich element*w nast*puj*cych (w postaci tablicy zmiennych wska*nikowych). Nale*y te* zapami*ta* adres pierwszego elementu drzewa.

7. Przyk*adowe programy dydaktyczne ilustruj*ce dynamiczne struktury danych (stos.pas, kolejka.pas, listadwu.pas)

{plik stos.pas}

{$A+,B-,D+,E+,F-,I+,L+,N-,O-,R-,S+,V+}

{$M 16384,0,655360}

program Stos;

{Program dydaktyczny przedstawiajacy sposob generowania i czytania

dynamicznej struktury danych typu stos. Stos jest struktura do

ktorej zapis i z ktorej usuniecie moze nastepowac jedynie od konca

nazwanego wierzcholkiem stosu, tj. od ostatnio wprowadzonego

obiektu na stos. Obiektem zapisywanym na stos moze byc dowolna

zmienna prosta lub strukturalna. W przypadku niniejszego programu

obiektem jest tablica 5 liczb typu integer, ktorymi sa kolejne

liczby naturalne, tj. dla pierwszego obiektu na stosie 1,1,1,1,1,

dla drugiego 2,2,2,2,2 itd.}

uses Crt;

type

AdresObiektu = ^TypRekorduZObiektem;

TypRekorduZObiektem = record

Obiekt : array [1..5] of integer;

AdresPoprzedniegoObiektu: AdresObiektu

end;

var

BiezacyObiekt: AdresObiektu;

AdresPomocniczy: Pointer;

I,J,LiczbaObiektowDoZapisu: integer;

Znak: char;

label

ZapisNaStos,OdczytStosu,Menu;

begin

{naglowek}

ClrScr;

WriteLn('Program dydaktyczny Stos przedstawiajacy sposob generowania');

WriteLn('i odczytu dynamicznej struktury danych typu stos.');

WriteLn('Program zapisuje na stosie, a nastepnie odczytuje obiekt,');

WriteLn('ktorym jest tablica 5 liczb typu integer. Liczbami tymi sa');

WriteLn('kolejne liczby naturalne.');

{menu}

Menu:

while KeyPressed do Znak:=ReadKey;

Writeln;

Write('Wybierz: zapis (Z), odczyt (O), koniec (K): ? ');

ReadLn(Znak);

if Znak='K'

then

Halt;

if Znak='Z'

then

goto ZapisNaStos

else

goto OdczytStosu;

{zapis}

ZapisNaStos:

{okreslenie parametrow wyjsciowych}

{adres pusty obiektu zerowego - poprzedniego w stosunku do pierwszego

na stosie}

AdresPomocniczy:=nil;

{ustalenie liczby obiektow zapisywanych na stos}

while KeyPressed do Znak:=ReadKey;

Write('Podaj liczbe obiektow ktore chcesz zapisac na stos: ? ');

ReadLn(LiczbaObiektowDoZapisu);

{petla glowna zapisu}

for I:=1 to LiczbaObiektowDoZapisu do

begin

{utworzenie nowego obiektu dynamicznego na stosie}

New(BiezacyObiekt);

{wygenerowanie wartosci aktualnie zapisywanego obiektu}

for J:=1 to 5 do

BiezacyObiekt^.Obiekt[J]:=I;

{wizualizacja obiektu zapisywanego oraz adresu nowo utworzonego

obiektu dynamicznego}

Write('Num.obiektu: ',I:1,' Obiekt: ');

for J:=1 to 5 do

Write(BiezacyObiekt^.Obiekt[J]:4);

Writeln(' Adres obiektu: ',Seg(BiezacyObiekt^):5,':',

Ofs(BiezacyObiekt^):4);

{wygenerowanie aktualnie zapisywanego adresu ktorym jest adres

poprzedniego obiektu na stosie}

BiezacyObiekt^.AdresPoprzedniegoObiektu:=AdresPomocniczy;

{zapamietanie adresu nowo utworzonego obiektu dynamicznego}

AdresPomocniczy:=BiezacyObiekt

{koniec petli glownej zapisu}

end; {for I:=1 to LiczbaObiektowDoZapisu do}

{powrot do menu}

goto Menu;

{odczyt}

OdczytStosu:

{ustalenie adresu ostatniego obiektu na stosie tj. wierzcholka stosu}

AdresPomocniczy:=BiezacyObiekt;

{wizualizacja stosu}

WriteLn;

Writeln('Zawartosc stosu:');

{instrukcja iteracyjna wizualizacji i likwidacji stosu}

while AdresPomocniczy<>nil do

begin

{odczyt i wizualizacja biezacego obiektu}

for J:=1 to 5 do

Write(BiezacyObiekt^.Obiekt[J]:4);

Writeln(' Adres obiektu: ',Seg(BiezacyObiekt^):5,':',

Ofs(BiezacyObiekt^):4);

{zapamietanie adresu poprzedniego obiektu na stosie}

AdresPomocniczy:=BiezacyObiekt^.AdresPoprzedniegoObiektu;

{likwidacja biezacego obiektu na stosie}

Dispose(BiezacyObiekt);

{wskazanie adresu nowego obiektu}

BiezacyObiekt:=AdresPomocniczy

{koniec iteracji}

end; {while AdresPomocniczy<>nil do}

{powrot do menu}

goto Menu;

end. {program Stos}

{plik kolejka.pas}

{$A+,B-,D+,E+,F-,I+,L+,N-,O-,R-,S+,V+}

{$M 16384,0,655360}

program Kolejka;

{Program dydaktyczny przedstawiajacy sposob generowania, czytania i

likwidacji obiektow dynamicznej struktury danych typu kolejka.

Kolejka jest struktura do ktorej zapis moze nastepowac jedynie na koncu

natomiast usuniecie obiektu jedynie na poczatku kolejki. Obiektem

zapisywanym do listy moze byc dowolna zmienna prosta lub strukturalna.

W przypadku niniejszego programu obiektem jest tablica 5 liczb typu

integer, ktorymi sa kolejne liczby naturalne, tj. dla np. dla pewnego

obiektu na liscie 1,1,1,1,1, dla innego 2,2,2,2,2 itd.}

uses Crt;

type

AdresObiektu = ^TypRekorduZObiektem;

TypRekorduZObiektem = record

Obiekt : array [1..5] of integer;

AdresNastepnegoObiektu: AdresObiektu

end;

var

BiezacyObiekt,PoprzedniObiekt: AdresObiektu;

AdresPomocniczy,AdresPierwszegoObiektu: Pointer;

I,J,LiczbaObiektowDoZapisu: integer;

Znak: char;

label

ZapisDoKolejki,OdczytIUsuniecieZKolejki,Menu;

begin

{naglowek}

ClrScr;

WriteLn('Program dydaktyczny Kolejka przedstawiajacy sposob generowania');

WriteLn('i odczytu dynamicznej struktury danych typu kolejka.');

WriteLn('Program zapisuje do kolejki, a nastepnie odczytuje i usuwa');

WriteLn('obiekt ktorym jest tablica 5 liczb typu integer. Liczbami tymi');

WriteLn('sa kolejne liczby naturalne.');

{menu}

Menu:

while KeyPressed do Znak:=ReadKey;

Writeln;

Write('Wybierz: zapis (Z), odczyt i usuniecie (O), koniec (K): ? ');

ReadLn(Znak);

if Znak='K'

then

Halt;

if Znak='Z'

then

goto ZapisDoKolejki

else

goto OdczytiUsuniecieZKolejki;

{zapis}

ZapisDoKolejki:

{ustalenie liczby obiektow zapisywanych do kolejki}

while KeyPressed do Znak:=ReadKey;

Write('Podaj liczbe obiektow ktore chcesz zapisac do kolejki: ? ');

ReadLn(LiczbaObiektowDoZapisu);

{petla glowna zapisu}

for I:=1 to LiczbaObiektowDoZapisu do

begin

{utworzenie nowego obiektu dynamicznego w kolejce}

New(BiezacyObiekt);

{wygenerowanie wartosci aktualnie zapisywanego obiektu}

for J:=1 to 5 do

BiezacyObiekt^.Obiekt[J]:=I;

{wizualizacja obiektu zapisywanego oraz adresu nowo utworzonego

obiektu dynamicznego}

Write('Num.obiektu: ',I:1,' Obiekt: ');

for J:=1 to 5 do

Write(BiezacyObiekt^.Obiekt[J]:4);

Writeln(' Adres obiektu: ',Seg(BiezacyObiekt^):5,':',

Ofs(BiezacyObiekt^):4);

{wygenerowanie adresu pustego jako adresu nastepnego obiektu

w kolejce}

BiezacyObiekt^.AdresNastepnegoObiektu:=nil;

{zapisanie adresu biezacego obiektu dynamicznego do rekordu obiektu

poprzedniego}

if I>1

then

begin

PoprzedniObiekt:=AdresPomocniczy;

PoprzedniObiekt^.AdresNastepnegoObiektu:=BiezacyObiekt;

end; {if I>1}

{zapamietanie adresu biezacego obiektu dynamicznego}

AdresPomocniczy:=BiezacyObiekt;

if I=1

then

AdresPierwszegoObiektu:=BiezacyObiekt;

{koniec petli glownej zapisu}

end; {for I:=1 to LiczbaObiektowDoZapisu do}

{powrot do menu}

goto Menu;

{odczyt i usuniecie obiektow z kolejki}

OdczytIUsuniecieZKolejki:

{ustalenie adresu pierwszego obiektu w kolejce}

AdresPomocniczy:=AdresPierwszegoObiektu;

{wizualizacja kolejki}

WriteLn;

Writeln('Zawartosc kolejki:');

{instrukcja iteracyjna wizualizacji i likwidacji kolejki}

repeat

{ustalenie bieacego adresu}

BiezacyObiekt:=AdresPomocniczy;

{odczyt i wizualizacja biezacego obiektu}

for J:=1 to 5 do

Write(BiezacyObiekt^.Obiekt[J]:4);

Writeln(' Adres obiektu: ',Seg(BiezacyObiekt^):5,':',

Ofs(BiezacyObiekt^):4);

{zapamietanie adresu nastepnego obiektu w kolejce}

AdresPomocniczy:=BiezacyObiekt^.AdresNastepnegoObiektu;

{likwidacja biezacego obiektu w kolejce}

Dispose(BiezacyObiekt);

{koniec iteracji}

until AdresPomocniczy=nil;

{powrot do menu}

goto Menu;

end. {program Kolejka}

{plik listadwu.pas}

{$A+,B-,D+,E+,F-,I+,L+,N-,O-,R-,S+,V+}

{$M 16384,0,655360}

program ListaDwukierunkowa;

{Program dydaktyczny przedstawiajacy sposob generowania, czytania i

likwidacji obiektow dynamicznej struktury danych typu lista

dwukierunkowa. Lista dwukierunkowa jest struktura do ktorej zapis moze

nastepowac zarowno na poczatku, na koncu jak i w srodku listy. To samo

dotyczy likwidacji obiektow na liscie. Obiektem zapisywanym do listy

moze byc dowolna zmienna prosta lub strukturalna.

W przypadku niniejszego programu obiektem jest tablica 5 liczb typu

integer, ktorymi sa kolejne liczby naturalne, tj. dla np. dla pewnego

obiektu na liscie 1,1,1,1,1, dla innego 2,2,2,2,2 itd.}

uses Crt;

type

AdresObiektu = ^TypRekorduZObiektem;

TypRekorduZObiektem = record

Obiekt : array [1..5] of integer;

AdresPoprzedniegoObiektu: AdresObiektu;

AdresNastepnegoObiektu: AdresObiektu

end;

var

BiezacyObiekt,SasiedniObiekt: AdresObiektu;

AdresPomocniczy,AdresPomocniczyDrugi,AdresPomocniczyTrzeci,

AdresPierwszegoObiektu: Pointer;

I,J,LiczbyWObiekcie,AktualnaLiczbaObiektow,NumerObiektuDoZapisu,

NumerObiektuDoUsuniecia: integer;

Znak: char;

WyskokDoMenu: boolean;

label

Menu,UstalenieNumeruObiektuDoZapisu,UstalenieNumeruObiektuDoUsuniecia;

procedure OdczytLiczbyObiektow(var LiczbaObiektow: integer);

var

AdresRoboczy: Pointer;

begin

LiczbaObiektow:=0;

AdresRoboczy:=AdresPierwszegoObiektu;

while AdresRoboczy<>nil do

begin

LiczbaObiektow:=LiczbaObiektow+1;

{wskazanie adresu nowego obiektu}

BiezacyObiekt:=AdresRoboczy;

{odczytanie adresu nastepnego obiektu na liscie}

AdresRoboczy:=BiezacyObiekt^.AdresNastepnegoObiektu

end {while AdresRoboczy<>nil do}

end; {procedure OdczytLiczbyObiektow}

procedure UstalenieAdresuObiektu(NumerObiektu: integer;

var AdresObiektu: Pointer);

var

LiczbaObiektow: integer;

AdresRoboczy: Pointer;

begin

AdresObiektu:=nil;

LiczbaObiektow:=0;

AdresRoboczy:=AdresPierwszegoObiektu;

while AdresRoboczy<>nil do

begin

LiczbaObiektow:=LiczbaObiektow+1;

if LiczbaObiektow=NumerObiektu

then

begin

AdresObiektu:=AdresRoboczy;

Exit

end; {if LiczbaObiektow=NumerObiektu}

{wskazanie adresu nowego obiektu}

BiezacyObiekt:=AdresRoboczy;

{odczytanie adresu nastepnego obiektu na liscie}

AdresRoboczy:=BiezacyObiekt^.AdresNastepnegoObiektu

end {while AdresRoboczy<>nil do}

end; {procedure OdczytLiczbyObiektow}

procedure WizualizacjaListy;

var

LiczbaObiektow: integer;

AdresRoboczy: Pointer;

begin

Writeln;

Writeln('Zawartosc listy:');

LiczbaObiektow:=0;

AdresRoboczy:=AdresPierwszegoObiektu;

while AdresRoboczy<>nil do

begin

LiczbaObiektow:=LiczbaObiektow+1;

{wskazanie adresu nowego obiektu}

BiezacyObiekt:=AdresRoboczy;

{odczyt i wizualizacja danych biezacego obiektu}

for J:=1 to 5 do

Write(BiezacyObiekt^.Obiekt[J]:4);

Writeln(' Adres obiektu: ',Seg(BiezacyObiekt^):5,':',

Ofs(BiezacyObiekt^):4);

{odczytanie adresu nastepnego obiektu na liscie}

AdresRoboczy:=BiezacyObiekt^.AdresNastepnegoObiektu

end {while AdresRoboczy<>nil do}

end; {procedure OdczytLiczbyObiektow}

procedure ZapisPierwszego;

begin

{utworzenie nowego obiektu dynamicznego na liscie}

New(BiezacyObiekt);

{zapis, do rekordu nowego obiektu, danych obiektu tj. kolejnych

5 liczb naturalnych}

LiczbyWObiekcie:=LiczbyWObiekcie+1;

for I:=1 to 5 do

BiezacyObiekt^.Obiekt[I]:=LiczbyWObiekcie;

{zapis, do rekordu nowego obiektu, adresu obiektu nastepnego

ktorym jest adres dotychczas pierwszego obiektu}

BiezacyObiekt^.AdresNastepnegoObiektu:=AdresPierwszegoObiektu;

{zapis, do rekordu nowego obiektu, adresu obiektu poprzedniego

ktorym jest adres pusty}

BiezacyObiekt^.AdresPoprzedniegoObiektu:=nil;

{modyfikacja zapisu - w rekordzie poprzednio pierwszego obiektu

na liscie - adresu obiektu poprzedniego ktorym jest adres

aktualnie pierwszego obiektu na liscie}

SasiedniObiekt:=AdresPierwszegoObiektu;

SasiedniObiekt^.AdresPoprzedniegoObiektu:=BiezacyObiekt;

{uaktualnienie adresu pierwszego obiektu na liscie}

AdresPierwszegoObiektu:=BiezacyObiekt;

{informacja pomocnicza}

Writeln('Nowy obiekt zapisano.');

end; {procedure ZapisPierwszego}

procedure ZapisOstatniego;

begin

{odczyt aktualnej liczby obiektow na liscie}

OdczytLiczbyObiektow(AktualnaLiczbaObiektow);

if AktualnaLiczbaObiektow=0

then

begin

{procedura jak przy zapisie pierwszego obiektu}

ZapisPierwszego;

{powrot do menu}

Exit;

end; {if AktualnaLiczbaObiektow=0}

{ustalenie adresu ostatniego obiektu na liscie tj. obiektu

o numerze porzadkowym AktualnaLiczbaObiektow i podstawienie

tego adresu pod zmienna AdresPomocniczy}

UstalenieAdresuObiektu(AktualnaLiczbaObiektow,AdresPomocniczy);

{utworzenie nowego obiektu dynamicznego na liscie}

New(BiezacyObiekt);

{zapis, do rekordu nowego obiektu, danych obiektu tj. kolejnych

5 liczb naturalnych}

LiczbyWObiekcie:=LiczbyWObiekcie+1;

for I:=1 to 5 do

BiezacyObiekt^.Obiekt[I]:=LiczbyWObiekcie;

{zapis, do rekordu nowego obiektu, adresu obiektu nastepnego

ktorym jest adres pusty}

BiezacyObiekt^.AdresNastepnegoObiektu:=nil;

{zapis, do rekordu nowego obiektu, adresu obiektu poprzedniego

ktorym jest adres dotychczas ostatniego obiektu}

BiezacyObiekt^.AdresPoprzedniegoObiektu:=AdresPomocniczy;

{modyfikacja zapisu - w rekordzie poprzednio ostatniego obiektu

na liscie - adresu obiektu nastepnego ktorym jest adres

aktualnie ostatniego obiektu na liscie}

SasiedniObiekt:=AdresPomocniczy;

SasiedniObiekt^.AdresNastepnegoObiektu:=BiezacyObiekt;

{informacja pomocnicza}

Writeln('Nowy obiekt zapisano.');

end; {ZapisOstatniego}

procedure LiczbaObiektow0Lub1;

begin

WyskokDoMenu:=False;

{odczyt aktualnej liczby obiektow na liscie}

OdczytLiczbyObiektow(AktualnaLiczbaObiektow);

{jesli aktualna liczba obiektow jest rowna 0 to wyjscie z opcji

i powrot do menu;

jesli 1 - to likwidacja tego obiektu i ustalenie adresu aktualnie

(tj. po likwidacji) pierwszego obiektu jako adresu pustego}

if AktualnaLiczbaObiektow=0

then

begin

Writeln('Lista pusta. Nie usunieto zadnego obiektu.');

WyskokDoMenu:=True;

Exit

end; {if AktualnaLiczbaObiektow=0}

if AktualnaLiczbaObiektow=1

then

begin

{lokalizacja i likwidacja obiektu dynamicznego na liscie}

BiezacyObiekt:=AdresPierwszegoObiektu;

Dispose(BiezacyObiekt);

AdresPierwszegoObiektu:=nil;

Writeln('Lista zawierala jeden obiekt. Obiekt usunieto.');

AktualnaLiczbaObiektow:=0;

WyskokDoMenu:=True;

Exit

end; {if AktualnaLiczbaObiektow=0}

end; {procedure LiczbaObiektow0Lub1}

procedure UsunieciePierwszego;

begin

{jesli aktualna liczba obiektow > 1 to lokalizacja drugiego obiektu

na liscie i podstawienie jego adresu pod zmienna AdresPomocniczy}

UstalenieAdresuObiektu(2,AdresPomocniczy);

{lokalizacja i likwidacja pierwszego obiektu dynamicznego na liscie}

BiezacyObiekt:=AdresPierwszegoObiektu;

Dispose(BiezacyObiekt);

{modyfikacja zapisu - w rekordzie poprzednio drugiego obiektu

na liscie - adresu obiektu poprzedniego ktorym jest teraz adres

pusty}

BiezacyObiekt:=AdresPomocniczy;

BiezacyObiekt^.AdresPoprzedniegoObiektu:=nil;

{uaktualnienie adresu pierwszego obiektu na liscie}

AdresPierwszegoObiektu:=BiezacyObiekt;

{informacja pomocnicza}

Writeln('Obiekt usunieto.');

end; {procedure UsunieciePierwszego}

procedure UsuniecieOstatniego;

begin

WyskokDoMenu:=False;

{kontrola liczby obiektow, procedury specjalne gdy liczba = 0 lub 1}

LiczbaObiektow0Lub1;

if WyskokDoMenu=True

then

Exit;

{ustalenie adresu ostatniego obiektu na liscie tj. obiektu

o numerze porzadkowym AktualnaLiczbaObiektow i podstawienie

tego adresu pod zmienna AdresPomocniczy}

UstalenieAdresuObiektu(AktualnaLiczbaObiektow,AdresPomocniczy);

{ustalenie adresu przedostatniego obiektu na liscie tj. obiektu

o numerze porzadkowym AktualnaLiczbaObiektow-1 i podstawienie

tego adresu pod zmienna AdresPomocniczyDrugi}

UstalenieAdresuObiektu(AktualnaLiczbaObiektow-1,AdresPomocniczyDrugi);

{lokalizacja i likwidacja ostatniego obiektu dynamicznego na liscie}

BiezacyObiekt:=AdresPomocniczy;

Dispose(BiezacyObiekt);

{modyfikacja zapisu - w rekordzie poprzednio przedostatniego

obiektu na liscie - adresu obiektu nastepnego ktorym jest teraz

adres pusty}

BiezacyObiekt:=AdresPomocniczyDrugi;

BiezacyObiekt^.AdresNastepnegoObiektu:=nil;

{informacja pomocnicza}

Writeln('Obiekt usunieto.');

end; {procedure UsuniecieOstatniego}

begin

{naglowek}

ClrScr;

WriteLn('Program dydaktyczny ListaDwukierunkowa przedstawiajacy sposob');

WriteLn('generowania, odczytu i likwidacji obiektow w dynamicznej ');

WriteLn('strukturze danych typu lista dwukierunkowa. Program zapisuje');

WriteLn('na liste, a nastepnie odczytuje i usuwa obiekt ktorym jest');

WriteLn('tablica 5 liczb typu integer. Liczbami tymi sa kolejne liczby');

Writeln('naturalne.');

{wartosci wyjsciowe}

AdresPierwszegoObiektu:=nil;

LiczbyWObiekcie:=0;

{menu}

Menu:

while KeyPressed do Znak:=ReadKey;

Write('Wybierz: zapis (Z), odczyt listy (O), usuniecie (U), koniec (K): ? ');

ReadLn(Znak);

case Znak of

{zapis okreslonego obiektu do listy}

'Z','z': begin {zapis}

while KeyPressed do Znak:=ReadKey;

Write('Zapis obiektu: pierwszego (P), ostatniego (O), innego (I), koniec (K): ? ');

ReadLn(Znak);

case Znak of

'P','p': begin {zapis obiektu jako pierwszego na liscie}

{wywolanie procedury zapisu}

ZapisPierwszego;

{powrot do menu}

goto Menu

{koniec opcji zapisu pierwszego obiektu na liscie}

end; {'P','p'}

'O','o': begin {zapis obiektu jako ostatniego na liscie}

{wywolanie procedury}

ZapisOstatniego;

{powrot do menu}

goto Menu

{koniec opcji zapisu ostatniego obiektu na liscie}

end; {'O','o'}

'I','i': begin {zapis obiektu jako posredniego na liscie}

{odczyt aktualnej liczby obiektow na liscie}

OdczytLiczbyObiektow(AktualnaLiczbaObiektow);

{okreslenie przez uzytkownika numeru porzadkowego nowego

obiektu na liscie}

UstalenieNumeruObiektuDoZapisu:

Write('Podaj numer obiektu do zapisu na liscie: ? ');

Readln(NumerObiektuDoZapisu);

if NumerObiektuDoZapisu>AktualnaLiczbaObiektow+1

then

begin

Writeln('Numer obiektu zbyt duzy. Aktualna liczba obiektow ',

AktualnaLiczbaObiektow:4,'. Podaj nowy numer.');

goto UstalenieNumeruObiektuDoZapisu

end; {if NumerObiektuDoZapisu>AktualnaLiczbaObiektow+1}

if NumerObiektuDoZapisu=1 {wariant rownowazny z zapisem obiektu

jako pierwszego}

then

begin

{wywolanie procedury zapisu}

ZapisPierwszego;

{powrot do menu}

goto Menu

end; {if NumerObiektuDoZapisu=1}

if NumerObiektuDoZapisu>AktualnaLiczbaObiektow

then

begin

{procedura jak dla ostatniego obiektu}

ZapisOstatniego;

{powrot do menu}

goto Menu

end; {if NumerObiektuDoZapisu>AktualnaLiczbaObiektow}

{numer nowego obiektu nie przekracza liczby obiektow}

{ustalenie adresu obiektu dotychczas figurujacego na pozycji

NumerObiektuDoZapisu-1 i podstawienie go pod zmienna

AdresPomocniczy - bedzie to poprzednik nowego obiektu}

UstalenieAdresuObiektu(NumerObiektuDoZapisu-1,AdresPomocniczy);

{ustalenie adresu obiektu dotychczas figurujacego na pozycji

NumerObiektuDoZapisu i podstawienie go pod zmienna

AdresPomocniczyDrugi - bedzie to nastepnik nowego obiektu}

UstalenieAdresuObiektu(NumerObiektuDoZapisu,AdresPomocniczyDrugi);

{utworzenie nowego obiektu dynamicznego na liscie}

New(BiezacyObiekt);

{zapis, do rekordu nowego obiektu, danych obiektu tj. kolejnych

5 liczb naturalnych}

LiczbyWObiekcie:=LiczbyWObiekcie+1;

for I:=1 to 5 do

BiezacyObiekt^.Obiekt[I]:=LiczbyWObiekcie;

{zapis, do rekordu nowego obiektu, adresu obiektu poprzedniego}

BiezacyObiekt^.AdresPoprzedniegoObiektu:=AdresPomocniczy;

{zapis, do rekordu nowego obiektu, adresu obiektu nastepnego}

BiezacyObiekt^.AdresNastepnegoObiektu:=AdresPomocniczyDrugi;

{modyfikacja zapisu - w rekordzie poprzednika - adresu obiektu

nastepnego ktorym jest adres nowego obiektu na liscie}

SasiedniObiekt:=AdresPomocniczy;

SasiedniObiekt^.AdresNastepnegoObiektu:=BiezacyObiekt;

{modyfikacja zapisu - w rekordzie nastepnika - adresu obiektu

poprzedniego ktorym jest adres nowego obiektu na liscie}

SasiedniObiekt:=AdresPomocniczyDrugi;

SasiedniObiekt^.AdresPoprzedniegoObiektu:=BiezacyObiekt;

{informacja pomocnicza}

Writeln('Nowy obiekt zapisano.');

{powrot do menu}

goto Menu

{koniec opcji zapis posredniego obiektu na liscie}

end; {'I','i'}

'K','k': goto Menu {koniec zapisow, powrot do menu glownego}

end {case Znak of}

{koniec opcji zapis w menu glownym}

end; {'Z','z'}

{wizualizacja na monitorze obiektow listy - wartosci oraz adresow obiektow}

'O','o': begin {odczyt i wizualizacja calosci listy}

WizualizacjaListy;

goto Menu

end; {'O','o'}

{usuniecie okreslonego obiektu z listy}

'U','u': begin {usuniecie}

while KeyPressed do Znak:=ReadKey;

Write('Usuniecie obiektu: pierwszego (P), ostatniego (O), innego (I), koniec (K): ? ');

ReadLn(Znak);

case Znak of

'P','p': begin {usuniecie obiektu pierwszego na liscie}

{kontrola liczby obiektow, procedury specjalne gdy liczba = 0 lub 1}

LiczbaObiektow0Lub1;

if WyskokDoMenu=True

then

goto Menu;

{wywolanie procedury usuniecia jesli liczba >1}

UsunieciePierwszego;

{powrot do menu}

goto Menu

{koniec opcji usuniecie pierwszego obiektu na liscie}

end; {'P','p'}

'O','o': begin {usuniecie obiektu ostatniego na liscie}

{wywolanie procedury usuniecia}

UsuniecieOstatniego;

{powrot do menu}

goto Menu

{koniec opcji usuniecia ostatniego obiektu na liscie}

end; {'O','o'}

'I','i': begin {usuniecie obiektu posredniego na liscie}

{kontrola liczby obiektow, procedury specjalne gdy liczba = 0 lub 1}

LiczbaObiektow0Lub1;

if WyskokDoMenu=True

then

goto Menu;

{okreslenie przez uzytkownika numeru porzadkowego obiektu na liscie

do usuniecia}

UstalenieNumeruObiektuDoUsuniecia:

Write('Podaj numer obiektu na liscie do usuniecia: ? ');

Readln(NumerObiektuDoUsuniecia);

if NumerObiektuDoUsuniecia>AktualnaLiczbaObiektow

then

begin

Writeln('Numer obiektu zbyt duzy. Aktualna liczba obiektow ',

AktualnaLiczbaObiektow:4,'. Podaj nowy numer.');

goto UstalenieNumeruObiektuDoUsuniecia

end; {if NumerObiektuDoUsuniecia>AktualnaLiczbaObiektow}

if NumerObiektuDoUsuniecia=1

{podany numer jest numerem pierwszego obiektu}

then

begin

{procedura jak dla usuniecia pierwszego obiektu}

UsunieciePierwszego;

{powrot do menu}

goto Menu

end; {if NumerObiektuDoUsuniecia=1}

if NumerObiektuDoUsuniecia=AktualnaLiczbaObiektow

{podany numer jest numerem ostatniego obiektu}

then

begin

{procedura jak dla usuniecia ostatniego obiektu}

UsuniecieOstatniego;

{powrot do menu}

goto Menu

end; {if NumerObiektuDoUsuniecia=AktualnaLiczbaObiektow}

{numer obiektu do usuniecia mniejszy niz liczba obiektow}

{ustalenie adresu poprzednika obiektu do usuniecia tj. figurujacego

na pozycji NumerObiektuDoUsuniecia-1 i podstawienie go pod zmienna

AdresPomocniczy}

UstalenieAdresuObiektu(NumerObiektuDoUsuniecia-1,AdresPomocniczy);

{ustalenie adresu nastepnika obiektu do usuniecia tj. figurujacego

na pozycji NumerObiektuDoUsuniecia+1 i podstawienie go pod zmienna

AdresPomocniczyDrugi}

UstalenieAdresuObiektu(NumerObiektuDoUsuniecia+1,AdresPomocniczyDrugi);

{ustalenie adresu obiektu do usuniecia tj. figurujacego na pozycji

NumerObiektuDoUsuniecia i podstawienie go pod zmienna

AdresPomocniczyTrzeci}

UstalenieAdresuObiektu(NumerObiektuDoUsuniecia,AdresPomocniczyTrzeci);

{likwidacja obiektu}

BiezacyObiekt:=AdresPomocniczyTrzeci;

Dispose(BiezacyObiekt);

{modyfikacja zapisu - w rekordzie poprzednika obiektu do usuniecia

- adresu obiektu nastepnego ktorym jest teraz adres nastepnika}

BiezacyObiekt:=AdresPomocniczy;

BiezacyObiekt^.AdresNastepnegoObiektu:=AdresPomocniczyDrugi;

{modyfikacja zapisu - w rekordzie nastepnika obiektu do usuniecia

- adresu obiektu poprzedniego ktorym jest teraz adres poprzednika}

BiezacyObiekt:=AdresPomocniczyDrugi;

BiezacyObiekt^.AdresPoprzedniegoObiektu:=AdresPomocniczy;

{informacja pomocnicza}

Writeln('Obiekt usunieto.');

{powrot do menu}

goto Menu

{koniec opcji usuniecie posredniego obiektu na liscie}

end; {'I','i'}

{koniec opcji usuniecie}

'K','k': goto Menu {koniec usuniec, powrot do menu glownego}

end; {case Znak of}

{koniec opcji usuniecie w menu glownym - powrot do menu glownego}

goto Menu

end; {'U','u'}

{koniec przebiegu}

'K','k': Halt;

end; {case Znak of}

end. {program ListaDwukierunkowa}


Wyszukiwarka