sprawozdanie programowanie lab2

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

Wstęp teoretyczny

Stos jest przypadkiem szczególnym listy liniowej. Elementy stosu, w których zapisane są dane powiązane ze sobą tworząc listę . Operacje dodawania i usuwania dotyczą tylko jednego końca tej listy. Działanie stosu określa się angielskim skrótem LIFO (ang. Last In First Out – ostatni nadszedł, pierwszy wychodzi).

Do zdefiniowania typu pojedynczego elementu stosu (nazywanego również typem bazowym stosu) posługujemy się typem rekordowym. Pole dana może mieć oczywiście inny typ, niż ten który został zaprezentowany. W zapisie możemy dostrzec dwa ciekawe elementy składniowe. Typ wskaźnikowy na zmienną typu „element” jest zdefiniowany wcześniej niż sam typ „element”. Rekord zawiera pole

(„wsk”), które jest wskaźnikiem na rekord tego samego typu co on. Z tego względu stos nazwany jest też strukturą rekurencyjną. Mając określony typ elementu stosu musimy jeszcze określić procedury, które na elementach tego typu będą wykonywały operacje. Tych procedur może być kilka, jednak najważniejsze z nich to „push” i „pop”.

Procedura „push” umieszcza nowy element na stosie. Przez parametry pobiera wskaźnik na element, który znajduje się na szczycie stosu („x”) oraz wartość, która ma być zapisana w elemencie („y”). Należy zwrócić uwagę, że wskaźnik jest przekazany przez zmienną, gdyż procedura będzie modyfikowała jego zawartość. Procedura posiada również zmienną lokalną, która jest typu „wskaźnik na element stosu”. W wierszu szóstym za pomocą procedury „new” zostaje przydzielona pamięć na nowy element stosu, którego adres zostaje zapisany w zmiennej „top”. W wierszu siódmym w tym elemencie zostaje zapisana informacja, którą ma przechowywać. Teraz należy już tylko umieścić nowy element na szczycie stosu. Najpierw musimy „połączyć” go z resztą stosu. Adres elementu, który jest bieżącym wierzchołkiem stosu jest zapisany w parametrze „x”. Należy więc zawartość tej zmiennej przepisać do pola „wsk” nowego elementu, co też czynimy w wierszu ósmym. Po wykonaniu instrukcji zawartej w tym wierszu nowy element staje się pierwszym6 elementem stosu, jednakże parametr „x” nie zawiera jeszcze jego adresu, lecz adres elementu

poprzedniego. Należy więc zmodyfikować zawartość zmiennej „x” i zapisać w niej adres nowego wierzchołka stosu, co zrealizowane jest w wierszu dziewiątym procedury „push”

Procedura „pop” ma natomiast działanie odwrotne do procedury „push”

Przebieg Laboratorium.

Zadanie 1.

Napisz program, który zapisuje liczby, które wprowadza użytkownik na stos, a następnie odczytuje je ze stosu. W programie należy sprawdzić, czy nie dochodzi do „wycieku” pamięci.

program zad1;

uses crt;

type

wskaznik=^element;

element=record

dana:integer;

wsk:wskaznik;

end;

var

p:wskaznik;

nu,ne:integer;

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

var

top:wskaznik;

begin

new(top);

top^.dana:=y;

top^.wsk:=x;

x:=top;

end;

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

var

bottom:wskaznik;

begin

y:=x^.dana;

bottom:=x^.wsk;

dispose(x);

x:=bottom;

end;

begin

clrscr;

writeln('Dostepna pamiec: ',MemAvail);

writeln('Ile elementow odlozyc na stos ?');

readln(ne);

while ne>0 do

begin

writeln('podaj wartosc elementu ');

readln(nu);

push(p,nu);

dec(ne);

end;

writeln('Dostepna pamiec: ',MemAvail);

writeln('Na stos odlozono nastepujace elementy');

while p<>nil do begin

pop(p,nu);

writeln(nu);

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

Poczatek programu głównego.

Sprawdzenie dostępnej pamięci.

Sprawdzenie dostępnej pamięci w trakcie działania programu.

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

Sprawdzenie wycieków pamięci.

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

Zadanie 2.

Napisz program, który przekonwertuje liczbę podaną w systemie dziesiętnym na postać binarną i ósemkową, wybieraną przez użytkownika. Należy wykorzystać algorytm dzielenia przez podstawę systemu i zapisywać na stosie reszty z dzielenia. Oczywiście wynik należy sczytywać odwrotnie do kolejności generowania kolejnych liczb wyniku (dlatego wykorzystujemy właśnie stos). W programie należy sprawdzić, czy nie dochodzi do „wycieku” pamięci.

program zadanie2;

uses crt;

type

wskaznik=^element;

element=record

dana:integer;

wsk:wskaznik;

end;

var

p:wskaznik;

nu,ne,i,l:integer;

s:string;

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

var

top:wskaznik;

begin

new(top);

top^.dana:=y;

top^.wsk:=x;

x:=top;

end;

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

var

bottom:wskaznik;

begin

y:=x^.dana;

bottom:=x^.wsk;

dispose(x);

x:=bottom;

end;

procedure dec2bin(var x:wskaznik; var y:integer);

var

r,t:integer;

begin

t:=y;

r:=0;

repeat

r:=t mod 2;

t:=t div 2;

push(x,r);

until t=0;

write('Reprezentacja liczby w postaci binarnej to: ');

r:=0;

while x<>nil do

begin

pop(x,r);

write(r);

end;

procedure dec2oct(var x:wskaznik; var y:integer);

var

r,t:integer;

begin

t:=y;

r:=0;

repeat

r:=t mod 8;

t:=t div 8;

push(x,r);

until t=0;

write('Reprezentacja liczby w systemie osemkowym to: ');

r:=0;

while x<>nil do

begin

pop(x,r);

write(r);

end;

begin

clrscr;

writeln('Dostepna pamiec: ',MemAvail);

writeln;

writeln('Podaj liczbe do zamiany ');

readln(l);

dec2bin(p,l);

writeln;

dec2oct(p,l);

writeln;

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

Procedura zamieniająca wprowadzona liczbę w postaci dziesiętnej do postaci binarnej.

Wypisanie wyniku operacji.

Procedura zamieniająca wprowadzona liczbę w postaci dziesiętnej do systemu ósemkowego..

Wypisanie wyniku operacji.

Sprawdzenie dostępnej pamięci.

Wywołanie procedur konwersji liczby dziesiętnej kolejno na system dwójkowy a następnie na ósemkowy.

Sprawdzenie wycieków pamięci.

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

Zadanie 3.

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, a następnie zdejmując je ze stosu stworzyć słowo „odwrotne”. Jeśli obydwa słowa są identyczne, tzn. że słowo jest palindromem. Należy sprawdzać, czy nie występuje „wyciek” pamięci.

program zadanie3;

uses crt;

type

wskaznik=^element;

element=record

dana:integer;

wsk:wskaznik;

end;

var

p:wskaznik;

nu,ne,i:integer;

wyraz,wyraz2:string[10];

z:string[1];

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

var

top:wskaznik;

begin

new(top);

top^.dana:=y;

top^.wsk:=x;

x:=top;

end;

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

var

bottom:wskaznik;

begin

y:=x^.dana;

bottom:=x^.wsk;

dispose(x);

x:=bottom;

end;

begin

clrscr;

writeln('Dostepna pamiec: ',MemAvail);

writeln('Podaj wyraz');

writeln;

wyraz:=' ';

readln(wyraz);

i:=0;

for i:=1 to length(wyraz) do

begin

ne:=ord(wyraz[i]);

push(p,ne);

end;

writeln('Dostepna pamiec: ',MemAvail);

z:=' ';

while p<>nil do

begin

pop(p,nu);

z[1]:=chr(nu);

wyraz2:=wyraz2+z[1];

end;

writeln;

writeln(wyraz2);

writeln;

if wyraz=wyraz2 then writeln('Wyraz jest palindromem')

else writeln('Wyraz nie jest palindromem');

writeln;

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

Wyświetlenie dostępnej pamieci.

Wczytanie wyrazu który zostanie następnie sprawdzony.

Sprawdzenie dostępnej pamięci w trakcie wykonywania się instrukcji.

Wypisanie na ekran wyrazu wejściowego w odwrotnej kolejności poszczególnych znaków w słowie.

Sprawdzenie wycieków pamięci.

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

Wnioski

Stos to jedna z najprostrzych struktur. Wyobraźmy sobie stos leżących książek jedna na drugiej. Możemy kłaść tylko na wierzch stosu i tylko z wierzchu zdejmować (jeżeli wyciągniemy ze środka, to się nam zawali stos).

Stos jest dobrym rozwiązaniem, gdy gromadząc jakieś dane przeprowadzamy operacje najpierw na tych najnowszych (ostatnio dodanych), a gdy te nie są nam już potrzebne, to zabieramy się za te nieco starsze.

Dobrym przykładem jest tu stos talerzy, ułożonych jeden na drugim, które - załóżmy - przypadło nam zmywać. W pierwszej kolejności zabierzemy się za talerz na samej górze. Gdy już go wyczyścimy to odłożymy na bok i weźmiemy następny - tak do ostatniego który jest na samym dnie stosu.