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

1. Wstęp teoretyczny

Jednokierunkowa lista liniowa (ang. singly linked list) jest abstrakcyjną strukturą danych, która może przechowywać elementy zarówno w sposób uporządkowany, jak

i nieuporządkowany. Elementy można dodawać i usuwać z listy w dowolnym jej miejscu. Czas wykonania tych operacji jest stały i niezależny od liczby elementów

w liście1, natomiast czas wyszukania elementu jest proporcjonalny do liczby elementów w niej umieszczonych.

Wyżej została przedstawiona procedura wstawiająca element do listy.

A poniżej procedura usuwająca element z listy. A pod nią kolejno procedury tworzącą, usuwającą i wyświetlającą.

2. Wstęp teoretyczny

Zadanie 1.

Zaprojektuj słownik, czyli dynamiczną strukturę danych, która podczas dopisywania elementów organizuje je od razu w porządku alfabetycznym. Elementami słownika niech będą słowa.

program lab5zad1; uses crt; type wskaznik=^element; element=record dana:string; nast:wskaznik; end; var qw:wskaznik; s:string; i,n:integer; procedure insert_node(var f:wskaznik; a:string); var prev,p,nowy:wskaznik; begin new(nowy); nowy^.dana:=a; nowy^.nast:=nil; if f^.dana > a then begin nowy^.nast:=f; f:=nowy; exit; end; p:=f; while (p^.dana <= a) do begin prev:=p; p:=p^.nast; if p=nil then begin prev^.nast:=nowy; exit; end; end; nowy^.nast:=prev^.nast; prev^.nast:=nowy; end; procedure delete_node(var f:wskaznik; a:string); var x,poprz,pom:wskaznik; begin if f^.dana=a then begin pom:=f^.nast; dispose(f); f:=pom; exit; end; x:=f; repeat poprz:=x; x:=x^.nast; until (x=nil) or (x^.dana=a); if x=nil then exit; poprz^.nast:=x^.nast; dispose(x); end; procedure create(var f:wskaznik; a:string); var nowy:wskaznik; begin if f=nil then begin new(nowy); nowy^.nast:=nil; nowy^.dana:=a; f:=nowy; end else insert_node(f,a); end; procedure remove(var f:wskaznik); var pom:wskaznik; begin while f<> nil do begin pom:=f^.nast; dispose(f); f:=pom; end; end; procedure show(f:wskaznik); begin while f <> nil do begin write(f^.dana:3,' '); f:=f^.nast; end; writeln; end; begin clrscr; create(qw,s); show(qw); writeln('Ile slow chcesz dodac ?'); readln(n); for i:=1 to n do begin writeln('Wpisz liczbe'); readln(s); insert_node(qw,s); show(qw); end; writeln('Efekt:'); for i:=1 to n do begin show(qw); remove(qw); end; readln; end.

Posłużenie się typem rekordowym do zdefiniowania typu pojedynczego elementu listy. Procedura umieszczająca nowy element w liście jednokierunkowej. Procedura usuwająca element z listy jednokierunkowej. Procedura tworząca listę jednokierunkową, tylko wtedy jeśli nie istnieje pierwszy element. Procedura usuwająca cała listę jednokierunkową. Procedura wyświetlająca listę jednokierunkową na ekranie. Stworzenie listy. Wyświetlenie jej. Wprowadzamy ile mamy zamiar wprowadzić słów do listy. Podajemy poszczególne elementy. Dodawanie do listy poszczególnych elementów. Wypisywanie ich na bierząco. Wyświetlenie efekty działania programu Usuniecie listy.

Zadanie 2.

Napisz procedurę Odwroc(var l:lista) odwracającą listę l.

program lab5zad2; type wskaznik=^element; element=record liczba:Integer; nast:wskaznik; end; var poczatek:wskaznik; kolejny:wskaznik; poprzedni:wskaznik; tmp:wskaznik; p:pointer; i:Integer; procedure wypeln; begin mark(p); poczatek:=nil; new(poczatek); poczatek^.liczba:=1; poczatek^.nast:=nil; kolejny:=poczatek; for i:=2 to 10 do begin new(kolejny^.nast); kolejny:=kolejny^.nast; kolejny^.liczba:=i; kolejny^.nast:=nil; end; end; procedure przed_odwroc; begin writeln('Przed odwroceniem:'); kolejny:=poczatek; while kolejny <> nil do begin write(kolejny^.liczba:3); kolejny:=kolejny^.nast end; writeln; poprzedni:=nil; kolejny:=poczatek; while kolejny <> nil do begin tmp:=kolejny^.nast; kolejny^.nast:=poprzedni; poprzedni:=kolejny; kolejny:=tmp; end; poczatek:=poprzedni; end; procedure odwroc; begin writeln('Po odwroceniu:'); kolejny:=poczatek; while kolejny <> nil do begin write(kolejny^.liczba:3); kolejny:=kolejny^.nast end; writeln; release(p); readln; end; begin writeln('Dostepna pamiec: ',MemAvail); wypeln; przed_odwroc; odwroc; writeln('Dostepna pamiec: ',MemAvail); readln; end.

Posłuzenie się typem rekordowym do zdefiniowania typu pojedynczego elementy listy jednokierunkowej. Procedura wypełniająca listę kolejnymi wartościami od 1 do 10. Procedura prezentująca listę przed odwróceniem znajdujących się w niej wartości. Procedura odwracająca wartości w liście jednokierunkowej. Sprawdzenie dostępnej pamięci. Wywołanie procedur... Sprawdzenie dostępnej pamięci.

Zadanie 3.

Napisz funkcję Scal(l1,l2:lista):lista scalającą dwie posortowane niemalejąco listy l1 i l2, tak aby wynikowa lista również była posortowana niemalejąco.

program lab5zad1; uses crt; type wskaznik=^element; element=record dana:string; nast:wskaznik; end; var qw,qw2:wskaznik; s,d:string; i,n,m:integer; procedure insert_node(var f:wskaznik; a:string); var prev,p,nowy:wskaznik; begin new(nowy); nowy^.dana:=a; nowy^.nast:=nil; if f^.dana > a then begin nowy^.nast:=f; f:=nowy; exit; end; p:=f; while (p^.dana <= a) do begin prev:=p; p:=p^.nast; if p=nil then begin prev^.nast:=nowy; exit; end; end; nowy^.nast:=prev^.nast; prev^.nast:=nowy; end; procedure create(var f:wskaznik; a:string); var nowy:wskaznik; begin if f=nil then begin new(nowy); nowy^.nast:=nil; nowy^.dana:=a; f:=nowy; end else insert_node(f,a); end; procedure remove(var f:wskaznik); var pom:wskaznik; begin while f<> nil do begin pom:=f^.nast; dispose(f); f:=pom; end; end; procedure show(f:wskaznik); begin while f <> nil do begin write(f^.dana:3,' '); f:=f^.nast; end; writeln; end; function scalenie(l1,l2:wskaznik):wskaznik; var tmp,ac:wskaznik; begin new(tmp); tmp^.nast:=nil; ac:=tmp; while (l1 <> nil) and (l2 <> nil) do if l1^.dana < l2^.dana then begin ac^.nast:=l1; ac:=ac^.nast; l1:=l1^.nast; end else if l1^.dana > l2^.dana then begin ac^.nast:=l2; ac:=ac^.nast; l2:=l2^.nast; end else begin ac^.nast:=l1; ac:=ac^.nast; l1:=l1^.nast; ac^.nast:=l2; ac:=ac^.nast; l2:=l2^.nast; end; if l1 = nil then ac^.nast:=l2 else ac^.nast:=l1; scalenie:=tmp^.nast; dispose(tmp); end; begin clrscr; create(qw,s); create(qw2,d); show(qw); show(qw2); writeln('Ile slow chcesz dodac do 1 listy ?'); readln(n); for i:=1 to n do begin writeln('Wpisz slowo'); readln(s); insert_node(qw,s); show(qw); end; writeln('Ile slow chcesz dodac do 2 listy ?'); readln(m); for i:=1 to m do begin writeln('Wpisz slowo'); readln(d); insert_node(qw2,d); show(qw2); end; writeln('Efekt:'); writeln('Poszczegolne listy przed operacja: '); show(qw); show(qw2); scalenie(qw,qw2); writeln('Po operacji '); show(qw); remove(qw); remove(qw2); readln; end.

Posłużenie się typem rekordowym służącym do zdefiniowania typu pojedynczego elementu kolejki. Procedura dodająca element do listy jednokierunkowej. Procedura tworząca pierwszy element listy , ale tylko wtedy kiedy go nie ma. Procedura usuwająca całą listę. Procedura wypisująca na ekran cała listę. Funkcja scalająca 2 listy . Zapisanie wyniku w 1 lub w 2 liscie. Stworzenie 1 listy. Stworzenie 2 listy Wypisanie na ekran elementów 1 listy. Wypisanie na ekran elementów 2 listy. Podajemy ilośc słów które chcemy podać do 1 listy. Wpisujemy poszczególne słowa. Dodajemy do kolejki. Wypisujemy na ekran na bierząco. Podajemy ilośc słów które chcemy podać do 2 listy. Wpisujemy poszczególne słowa. Dodajemy do kolejki. Wypisujemy na ekran na bierząco. Wypisanie efektu pracy programu. Wypisanie listy 1 i 2 przed scaleniem. Scalnie. Wypisanie scalonych juz list 1 i 2. Usuniecie listy 1. Usuniecie listy 2.

3. Wnioski

No więc lista jednokierunkowa to lista "struktur danych typu record" przy czym każda zawiera wskaźnik do następnego elementu. W liście jednokierunkowej poruszamy się od początku do końca lub od końca do początku listy.