Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki,
Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 5
Lista jednokierunkowa
Data wykonania Data oddania Ocena :
dwiczenia :
sprawozdania :
11.04.2012
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.
procedure insert_node(var f:wskaznik; a:integer);
var
prev,p,nowy:wskaznik;
begin
new(nowy);
nowy^.dana:=a;
nowy^.next:=nil;
if f^.dana > a then
begin
nowy^.next:=f;
f:=nowy;
exit;
end;
p:=f;
while (p^.dana <= a) do
begin
prev:=p;
p:=p^.next;
if p=nil then
begin
prev^.next:=nowy;
exit;
end;
end;
nowy^.next:=prev^.next;
prev^.next:=nowy;
end;
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ą.
procedure delete_node(var f:wskaznik; a:integer);
var
p,prev,tmp:wskaznik;
begin
if f^.dana=a then
begin
tmp:=f^.next;
dispose(f);
f:=tmp;
exit;
end;
p:=f;
repeat
prev:=p;
p:=p^.next;
until (p=nil) or (p^.dana=a);
if p=nil then exit;
prev^.next:=p^.next;
dispose(p);
end;
procedure create(var f:wskaznik; a:integer); procedure remove(var f:wskaznik); procedure show(f:wskaznik);
var var begin
nowy:wskaznik;
while f <> nil do
tmp:wskaznik;
begin
begin
begin
if f=nil then write(f^.dana:3);
while f <> nil do
begin f:=f^.next;
begin
new(nowy); end;
tmp:=f^.next;
nowy^.next:=nil; writeln;
dispose(f);
nowy^.dana:=a;
end;
f:=tmp;
f:=nowy;
end;
end
end;
else
insert_node(f,a);
end;
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 Posłużenie się typem rekordowym do
wskaznik=^element; zdefiniowania typu pojedynczego elementu listy.
element=record
dana:string;
nast:wskaznik;
end;
var
qw:wskaznik;
s:string;
i,n:integer;
procedure insert_node(var f:wskaznik; a:string); Procedura umieszczająca nowy element w liście
var jednokierunkowej.
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); Procedura usuwająca element z listy
var jednokierunkowej.
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); Procedura tworząca listę jednokierunkową, tylko
var wtedy jeśli nie istnieje pierwszy element.
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); Procedura usuwająca cała listę jednokierunkową.
var
pom:wskaznik;
begin
while f<> nil do
begin
pom:=f^.nast;
dispose(f);
f:=pom;
end;
end;
procedure show(f:wskaznik); Procedura wyświetlająca listę jednokierunkową
begin na ekranie.
while f <> nil do
begin
write(f^.dana:3,' ');
f:=f^.nast;
end;
writeln;
end;
begin
clrscr;
create(qw,s); Stworzenie listy.
show(qw); Wyświetlenie jej.
writeln('Ile slow chcesz dodac ?');
readln(n); Wprowadzamy ile mamy zamiar wprowadzid
for i:=1 to n do begin słów do listy.
writeln('Wpisz liczbe');
readln(s); Podajemy poszczególne elementy.
insert_node(qw,s); Dodawanie do listy poszczególnych elementów.
show(qw); Wypisywanie ich na bierząco.
end;
writeln('Efekt:'); Wyświetlenie efekty działania programu
for i:=1 to n do begin
show(qw);
remove(qw);
end; Usuniecie listy.
readln;
end.
Zadanie 2.
Napisz procedurę Odwroc(var l:lista) odwracającą listę l.
program lab5zad2;
type Posłuzenie się typem rekordowym do zdefiniowania
wskaznik=^element; typu pojedynczego elementy listy jednokierunkowej.
element=record
liczba:Integer;
nast:wskaznik;
end;
var
poczatek:wskaznik;
kolejny:wskaznik;
poprzedni:wskaznik;
tmp:wskaznik;
p:pointer;
i:Integer;
procedure wypeln; Procedura wypełniająca listę kolejnymi wartościami
begin od 1 do 10.
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; Procedura prezentująca listę przed odwróceniem
begin znajdujących się w niej wartości.
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; Procedura odwracająca wartości w liście
begin jednokierunkowej.
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); Sprawdzenie dostępnej pamięci.
wypeln; Wywołanie procedur...
przed_odwroc;
odwroc;
writeln('Dostepna pamiec: ',MemAvail); Sprawdzenie dostępnej pamięci.
readln;
end.
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 Posłużenie się typem rekordowym służącym do
wskaznik=^element; zdefiniowania typu pojedynczego elementu kolejki.
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); Procedura dodająca element do listy
var jednokierunkowej.
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); Procedura tworząca pierwszy element listy , ale tylko
var wtedy kiedy go nie ma.
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); Procedura usuwająca całą listę.
var
pom:wskaznik;
begin
while f<> nil do
begin
pom:=f^.nast;
dispose(f);
f:=pom;
end;
end;
procedure show(f:wskaznik); Procedura wypisująca na ekran cała listę.
begin
while f <> nil do
begin
write(f^.dana:3,' ');
f:=f^.nast;
end;
writeln;
end;
function scalenie(l1,l2:wskaznik):wskaznik; Funkcja scalająca 2 listy .
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 Zapisanie wyniku w 1 lub w 2 liscie.
else ac^.nast:=l1;
scalenie:=tmp^.nast;
dispose(tmp);
end;
begin
clrscr;
create(qw,s); Stworzenie 1 listy.
create(qw2,d); Stworzenie 2 listy
show(qw); Wypisanie na ekran elementów 1 listy.
show(qw2); Wypisanie na ekran elementów 2 listy.
writeln('Ile slow chcesz dodac do 1 listy ?');
readln(n); Podajemy ilośc słów które chcemy podad do 1 listy.
for i:=1 to n do begin
writeln('Wpisz slowo'); Wpisujemy poszczególne słowa.
readln(s);
insert_node(qw,s); Dodajemy do kolejki.
show(qw); Wypisujemy na ekran na bierząco.
end;
writeln('Ile slow chcesz dodac do 2 listy ?'); Podajemy ilośc słów które chcemy podad do 2 listy.
readln(m);
for i:=1 to m do begin Wpisujemy poszczególne słowa.
writeln('Wpisz slowo');
readln(d); Dodajemy do kolejki.
insert_node(qw2,d); Wypisujemy na ekran na bierząco.
show(qw2);
end;
writeln('Efekt:'); Wypisanie efektu pracy programu.
writeln('Poszczegolne listy przed operacja: ');
show(qw); Wypisanie listy 1 i 2 przed scaleniem.
show(qw2);
scalenie(qw,qw2); Scalnie.
writeln('Po operacji '); Wypisanie scalonych juz list 1 i 2.
show(qw);
remove(qw); Usuniecie listy 1.
remove(qw2); Usuniecie listy 2.
readln;
end.
3. Wnioski
No więc lista jednokierunkowa to lista "struktur danych typu record" przy czym każda zawiera wskaz
nik do
następnego elementu. W liście jednokierunkowej poruszamy się od początku do kooca lub od kooca do
początku listy.