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; 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
Program lab4zad2fin; 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. |
Zdefiniowanie rekordu dla kolejki. Zdefiniowanie rekordu dla stosu. Procedura odkładania na stos. Funkcja usuwania ze stosu. Procedura dodawania do kolejki. Procedura usuwajaca z kolejki. Procedura wyswietlająca kolejkę. Procedura obliczająca wynik odwrotnej notacji polskiej. Dodaje 2 liczby znajdujące się na stosie ,usuwa te liczby i wynik odkłada spowrotem na stos. Odejmuje 2 liczby znajdujące się na stosie, usuwa te liczby i wynik spowrotem odklada na stos. Mnozy przez siebie 2 liczby znajdujące się na stosie, usuwa te liczby i wynik odkłada spowrotem na stos. Wypisuje na ekran wynik działania. Wykonanie działania z instrukcji, można to zmodyfikowac aby można było wpisywać własne działania i liczby, aby wykonywać rózne opecracje. Koniec programu. |
---|
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.