sprawozdanie programowanie lab4 fin

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

Wstęp teoretyczny

Kolejki FIFO (first in first out) – składa się z ciągu elementów tego samego typu z

możliwością wkładania elementów na jej końcu i wyciągania elementów z jej początku.

Deklaracja dynamicznej struktury kolejki:

Pusta kolejka:

Wstawianie nowego elementu (recordu) na koniec kolejki:

Usuwanie elementu (recordu) z przodu kolejki:

Przebieg Laboratorium

Zadanie 1.

Napisz program, który będzie sprawdzał, czy wpisane przez użytkownika słowo jest palindromem. W tym celu program powinien wczytać poszczególne znaki wyrazu na stos i do kolejki FIFO, a następnie zdejmując je ze stosu i z kolejki i porównywać ze sobą znaki. Należy sprawdzać, czy nie występuje „wyciek” pamięci.

program lab4zad1;

uses crt;

type

wskaznik=^element;

element=record

litera:char;

next:wskaznik;

end;

var

head,tail,p:wskaznik;

check:byte;

zn,zn2:char;

procedure push(var x:wskaznik; y:char);

var

top:wskaznik;

begin

new(top);

top^.litera:=y;

top^.next:=x;

x:=top;

end;

procedure pop(var x:wskaznik; var y:char);

var

bottom:wskaznik;

begin

y:=x^.litera;

bottom:=x^.next;

dispose(x);

x:=bottom;

end;

procedure enque(var h,t:wskaznik; a:char);

var

nowy:wskaznik;

begin new(nowy);

nowy^.litera:=a;

nowy^.next:=nil;

if h=nil then

begin

h:=nowy;

t:=h;

end

else begin

t^.next:=nowy;

t:=t^.next;

end;

procedure dequeue(var h:wskaznik; var a:char);

var

temp:wskaznik;

begin

temp:=h^.next;

a:=h^.litera;

dispose(h);

h:=temp;

end;

function check2(var h,t,x:wskaznik; ch:integer):boolean;

var

z,z2:char;

begin

while h<>nil do begin

dequeue(h,z);

pop(x,z2);

if z=z2 then dec(ch);

end;

if ch=0 then check2:=TRUE

else check2:=FALSE;

end;

begin

clrscr;

writeln('Dostepna pamiec: ',MemAvail);

writeln;

writeln('Wpisz wyraz: ');

repeat

zn:=readkey;

write(zn);

if zn<>#13 then

begin

enque(Head,Tail,zn);

push(p,zn);

inc(check);

end;

until zn=#13;{#13=enter}

writeln;

if check2(Head,Tail,P,check)=TRUE then writeln('Palindrom')

Else writeln('Nie Palindrom');

Writeln;

writeln('Dostepna pamiec: ',MemAvail);

readln;

end.

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

Procedura umieszczająca nowy element na stosie.

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

Procedura „enqueue” dodaje element do kolejki.

Procedura „dequeque” usuwa element z kolejki.

Funkcja zwracajaca wartość logiczną „true” lub „false”.

Sprawdzenie dostępnej pamięci przez wykonaniem się programu.

Wypisanie kolejnych znaków wprowadzanych z klawiatury na ekran.

Sprawdzenie dostępnej pamięci po wykonaniu się programu.

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

Zadanie 2.

Wyznacz wartość wyrażenia zapisanego w odwrotnej notacji polskiej.

(3+5)*4=3 5 + 4 *

Wskazówki:

Dane (3 5 + 4 *) są przechowywane w kolejce

Jeśli kolejka danych nie jest pusty, pobieramy kolejną daną:

o Jeśli to liczba, to odkładamy ja na stos

o Jeśli to operator, to zdejmujemy dwie liczby ze stosu, wykonujemy działanie i odkładamy wynik na stos

Jeśli kolejka danych jest pusty, zwracamy jako wynik liczbę ze stosu

USES

Crt;

TYPE

pElKolejki=^elKolejki;

elKolejki=record

znak : boolean;

wart : integer;

next : pElKolejki;

end;

pElStosu=^elStosu;

elStosu = record

wart : integer;

tenNizej : pElStosu;

end;

VAR

glowa, ogon : pElKolejki;

stos : pElStosu;

Procedure push(var stos:pElStosu; w:integer);

Var

nowy : pElStosu;

Begin

new(nowy);

nowy^.wart := w;

nowy^.tenNizej := stos;

stos := nowy;

End;

Function pop(var stos:pElStosu) : integer;

Var

temp : pElStosu;

w : integer;

Begin

w := stos^.wart;

temp := stos;

stos := stos^.tenNizej;

dispose(temp);

pop := w;

End;

Procedure doloz(var glowa, ogon:pElKolejki; z:boolean; w:integer);

Var

nowy : pElKolejki;

Begin

new(nowy);

nowy^.znak := z;

nowy^.wart := w;

nowy^.next := nil;

if (glowa=nil) then

begin

glowa := nowy;

ogon := glowa;

end

else

begin

ogon^.next := nowy;

ogon := ogon^.next;

end;

End;

Procedure usun(var glowa:pElKolejki; var z:boolean; var w:integer);

Var

temp : pElKolejki;

Begin

w := glowa^.wart;

z := glowa^.znak;

temp := glowa;

glowa := glowa^.next;

dispose(temp);

End;

Procedure wyswietl(temp:pElKolejki);

Begin

while (temp<>nil) do

begin

if (temp^.znak=true)

then

write( chr(temp^.wart), ' ')

else

write(temp^.wart, ' ');

temp:=temp^.next;

end;

writeln;

End;

Procedure oblicz(var stos:pElStosu; var glowa:pElKolejki);

Var

w : integer;

znak : boolean;

Begin

while (glowa<>nil) do

begin

usun(glowa, znak, w);

if (znak=true)

then

case chr(w) of

'+': push(stos, pop(stos)+pop(stos) );

'-': push(stos, pop(stos)-pop(stos) );

'*': push(stos, pop(stos)*pop(stos) );

end

else

push(stos, w);

end;

write('Wynik dzialania: ');

write( pop(stos) );

End;

BEGIN

ogon := nil;

glowa := nil;

stos := nil;

ClrScr;

doloz(glowa, ogon, false, 3);

doloz(glowa, ogon, false, 5);

doloz(glowa, ogon, true, ord('+') );

doloz(glowa, ogon, false, 4);

doloz(glowa, ogon, true, ord('*') );

wyswietl(glowa);

oblicz(stos, glowa);

readln;

END.

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

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

Procedura umieszczająca nowy element na stosie.

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

Procedura „enqueue” dodaje element do kolejki.

Procedura „dequeque” usuwa element z kolejki.

Procedura „printqueue” drukuje zawartość kolejki na ekran monitora.

Procedura obsługująca wyrażenia zapisane w odwrotnej notacji polskiej

Suma.

Róznica

Iloczyn

Wypisanie na ekran wyniku.

Tworzenie kolejki.

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.