sprawozdanie programowanie lab3

Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki, Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 1
Data wykonania ćwiczenia : 15.03.2012
1.Przemysław Wolski

Wstęp teoretyczny

Kolejka jest, podobnie jak stos abstrakcyjną strukturą danych opartą na liście liniowej. Elementy kolejki też są połączone w listę, ale inaczej niż w stosie przebiegają operacje dodawania i usuwania elementów z tej listy. Istnieje kilka odmian kolejek. W najprostszej dodawanie i usuwanie elementów jest zorganizowane według zasady FIFO (ang. First In First Out) – pierwszy nadszedł, pierwszy wychodzi. Elementy dodawane są do kolejki na jej końcu, natomiast usuwane są z jej początku. Mówiąc lub pisząc „kolejka” mamy na myśli opisaną wyżej strukturę. Oprócz niej istnieją również kolejki dwustronne, w których elementy możemy dodawać i usuwać po obu stronach kolejki. Wśród tych kolejek możemy wyróżnić kolejki o ograniczonym wejściu, w których operacja dodawania dotyczy tylko jednego końca kolejki, a operacja usuwania obu, oraz kolejki o ograniczonym wyjściu, w których operacja usuwania dotyczy tylko jednego końca kolejki, a operacja dodawania obu końców. Dalsze rozważania będą dotyczyły tylko kolejki FIFO.

Typ pojedynczego elementu kolejki (typ bazowy kolejki) będzie określony tak samo jak typ bazowy stosu.

Przebieg Laboratorium.

Zadanie 1.

Napisz funkcje, które rozszerzą działanie standardowych funkcji dostępu do stosu push i pop w ten sposób, że na stosie zawsze pozostawać będzie określona stała minimalna ilość elementów, oraz wielkość stosu nie przekroczy maksymalnej liczby elementów. Przedstaw rozwiązanie w którym użyjesz zmiennej globalnej do przechowywania ilości elementów na stosie oraz rozwiązanie bez użycia zmiennej globalnej. Funkcje powinny zwracać wartość: true jeśli odłoży element na stos i zdejmie element ze stosu;

false jeśli nie odłoży lub nie zdejmie elementu ze stosu.

program zadanie1;

uses crt;

type

wskaznik=^element;

element=record

dana:integer;

wsk:wskaznik;

end;

const

max=5;

min=1;

var

p:wskaznik;

nu,ne,li:integer;

procedure push(var a:wskaznik; y:integer);

var

top:wskaznik;

begin

new(top);

top^.dana:=y;

top^.wsk:=a;

a:=top;

end;

procedure pop(var a:wskaznik; var y:integer);

var

bottom:wskaznik;

begin

y:=a^.dana;

bottom:=a^.wsk;

dispose(a);

a:=bottom;

end;

function nowy_push(var a:wskaznik; y:integer):boolean;

begin

if li<max then begin

push(a,y);

nowy_push:=true;

li:=li+1;

end

else

nowy_push:=false;

end;

function nowy_pop(var a:wskaznik; var y:integer):boolean;

begin

if li>min then begin

pop(a,y);

nowy_pop:=true;

dec(li);

end

else nowy_pop:=false;

end;

begin

clrscr;

li:=0;

writeln('Dostepna pamiec: ',MemAvail);

while nowy_push(p,nu)=true do begin

writeln('Wpisz wartosc');

readln(nu);

push(p,nu);

dec(ne);

end;

while nowy_pop(p,nu)=true do begin

pop(p,nu);

writeln(nu);

end;

readln;

end.

writeln('Dostepna pamiec: ',MemAvail);

readln;

end.

Posłużenie się typem rekordowym służącym do zdefiniowania typu pojedynczego elementu stosu.

(poszczególne procedury opisane są w stępie teoretycznym)

Procedura umieszczająca nowy element na stosie.

Procedura usuwająca element znajdujący się na szczycie stosu

Zdefiniowanie nowej procedury push.

Przyjęcie wartości „true” jeśli li (licznik) jest mniejszy od maksymalnej liczby elementów.

Przyjęcie wartości „false” jeśli li (licznik) przekroczy maksymalną liczbę elementów.

Zdefiniowanie nowej procedury pop.

Przyjęcie wartości „true” jeśli li (licznik) jest większy od minimalnej liczby elementów.

Przyjęcie wartości „false” jeśli li (licznik) jest mniejszy od minimalnej liczby elementów

Początek programu głównego.

Sprawdzenie dostępnej pamięci.

Wprowadzanie wartości na stos.

Wypisanie elementów odłożonych na stos.

Sprawdzenie wycieków pamięci.

Zrzut ekranu przedstawiający wynik działania programu nr 1.

Wnioski

Aby wygodnie korzystać z kolejki wprowadza się dwie zmienne wskaźnikowe „head” (po polsku – głowa) i „tali” (po polsku – ogon), które wskazują odpowiednio na pierwszy i na ostatni element kolejki. Mając określony typ elementu i obie zmienne wskaźnikowe należy jeszcze określić operacje, które będą na tej kolejce wykonywane. Podobnie jak w przypadku stosu tych operacji może być kilka, jednak tutaj zostaną omówione trzy najważniejsze – wstawienia elementu do kolejki (ang. enqueue) i usunięcia elementu z kolejki (ang. dequeue) oraz dodatkowo wyświetlenia wartości pola „dane” wszystkich elementów należących do kolejki.