Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki,
Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 7
Lista cykliczna
Data wykonania Data oddania Ocena :
dwiczenia : sprawozdania :
20.04.2012 03.05.2012
1.Przemysław Wolski
1. Wstęp teoretyczny.
Lista cykliczna jest listą, której elementy tworzą pętlę, a więc nie można wyróżnić w niej elementu
początkowego, ani końcowego. Listę tę można utworzyć z listy
jednokierunkowej lub dwukierunkowej. Na jej bazie można tworzyć stosy i kolejki. Ze
względu na strukturę tej listy żaden z jej elementów nie zawiera pola
wskaz
nikowego, którego wartość wynosiłaby  nil . Schematycznie można ją przedstawić następująco:
Lista cykliczna, podobnie, jak dwie poprzednie listy zostanie przedstawiona na przykładzie programu,
który tworzy listę i umieszcza w niej elementy, tak aby wartości
w nich przechowywane były posortowane niemalejąco. Pojedynczy element tej listy będzie miał taką
samą strukturę wewnętrzną jak element listy dwukierunkowej
(wiersze 10  14), choć można do budowy tej listy użyć elementów znanych z listy
jednokierunkowej. Wybór elementu z dwoma polami wskaz
nikowymi,
przechowującymi adresy poprzedniego i następnego elementu w liście, pozwala poruszać się po niej
w obu kierunkach, ale ta własność nie będzie wykorzystywana, ani
prezentowana w programie. Musimy również zadeklarować zmienną wskaz
nikową, która będzie
 pamiętała adres jednego z elementów listy. Ponieważ lista jest
cykliczna nie ma znaczenia, który z elementów to będzie.
2. Przebieg ćwiczenia.
Zad 1
Napisać program, symulujący przydzielanie pracowników do pracy w taki
sposób, że:
Rekord  Osoba ma następujące pola:
" Nazwa (liczba naturalna cały czas zwiększana  nie ma 2 pracownikow o
tej samej nazwie)
" Czas pracy (liczba naturalna, z zakresu 2-8)
" Stanowisko (liczba naturalna z zakresu 1-5)
Rekordy z osobami powinny być uszeregowane w liście cyklicznej, sortując po
polu: Stanowisko (najwyższy priorytet ma pracownik na stanowisku 1, a najniższy na
stanowisku 5).
Program działa w następujący sposób:

Mamy do dyspozycji MENU z następującymi polami: (dodaj zadanie, dodaj
pracownika, nowa godzina pracy, koniec).

Dodaj zadanie  zadanie to liczba godzin potrzebnych na jego wykonanie
(najlepiej generowana losowo z zakresu: 10  30)

Dodaj pracownika  Dodajemy element osoba do listy cyklicznej w taki
sposób, że stanowisko i czas pracy jest generowany losowo z podanych
przedziałów. Elementy są ułożone pod względem Stanowiska w porządku
rosnącym.

Nowa godzina pracy  Aktualnemu pracownikowi odejmujemy z czasu pracy i
z czasu Zadania 1. Jeżeli czas pracy pracownika spadnie do 0 to powinien być
usunięty z listy. Wskaz
nik aktualnego pracownika jest przesuwany na
kolejnego pracownika. Jeżeli braknie pracowników, a zadanie nie będzie
zakończone to wyświetlany jest komunikat:  Dodaj pracownika i nie
dekrementujemy czasu zadania. Jeżeli zadanie będzie wykonane to
wyświetlany jest komunikat, a czas pracy pracownika NIE jest
dekrementowany.

Koniec  Usuwamy wszystkie struktury dynamiczne utworzone w trakcie
działania programu i kończymy program

W każdym kroku wyświetlamy dane pracowników w liście, oraz informacje o
zadaniu.
program untitled;
uses crt;
type Zdefiniowanie typu rekordowego zawierającego
osoba=record dane pojedynczej osoby.
name:integer;
workTime:byte;
position:byte;
end;
type Zdefiniowanie głównego typu rekordowego.
wskaznik=^element;
element=record
dana:osoba;
next:wskaznik;
prev:wskaznik;
end;
var Zmienne globalne.
quantity:integer;
exerciseTime:byte;
procedure create(var wsk:wskaznik); Procedura tworząca nowego pracownika.
begin
new(wsk);
inc(quantity);
wsk^.dana.name:=quantity;
wsk^.dana.workTime:=Random(7)+2;
wsk^.dana.position:=Random(5)+1;
wsk^.next:=wsk;
wsk^.prev:=wsk;
end;
function find_min(wsk:wskaznik):wskaznik; Funkcja wyszukująca pracownika o najwyższym
var priorytecie, a wiec najwyższym stanowisku.
go,res:wskaznik;
minimum:integer;
begin
go:=wsk;
minimum:=wsk^.dana.position;
res:=wsk;
repeat
if minimum>wsk^.dana.position then
begin
minimum:=wsk^.dana.position;
res:=wsk;
end;
wsk:=wsk^.next;
until wsk=go;
find_min:=res;
end;
function find_next(wsk:wskaznik; Funkcja wyszukująca kolejnego pracownika z jak
a:integer):wskaznik; najwyższym priorytetem.
var
go:wskaznik;
begin
wsk:=find_min(wsk);
go:=wsk;
repeat
if wsk^.dana.position>a then break;
wsk:=wsk^.next;
until wsk=go;
find_next:=wsk;
end;
procedure insert(wsk:wskaznik); Procedura wstawiająca pracowników do listy
var cyklicznej.
nowy:wskaznik;
begin
new(nowy);
inc(quantity);
nowy^.dana.name:=quantity;
nowy^.dana.workTime:=Random(7)+2;
nowy^.dana.position:=Random(5)+1;
wsk:=find_next(wsk,nowy^.dana.position);
nowy^.next:=wsk;
nowy^.prev:=wsk^.prev;
wsk^.prev^.next:=nowy;
wsk^.prev:=nowy;
end;
procedure delete(var wsk:wskaznik); Procedura usuwająca pracownika z listy kiedy
var jego czas pracy zmaleje do 0.
tmp:wskaznik;
begin
if wsk=wsk^.next then
tmp:=nil else begin
tmp:=wsk^.next;
wsk^.prev^.next:=wsk^.next;
wsk^.next^.prev:=wsk^.prev;
end;
dispose(wsk);
wsk:=tmp;
end;
procedure say(wsk:wskaznik); Procedura wyświetlająca listę na ekranie
var monitora.
go:wskaznik;
begin
go:=wsk;
writeln;
writeln('=*=NAME=*= =*=TIME=*=
=*=POSITION=*=');
repeat
writeln(wsk^.dana.name:4,
wsk^.dana.workTime:12,wsk^.dana.position:12);
wsk:=wsk^.next;
until wsk=go;
end;
procedure remove(var wsk:wskaznik); Procedura usuwająca listę.
var
go,pom:wskaznik;
begin
if (wsk<>nil) then begin
go:=wsk;
repeat
pom:=wsk^.next;
dispose(wsk);
wsk:=pom;
until wsk=go;
end;
end;
procedure newHour(var wsk:wskaznik); Procedura dodająca nową godzinę pracy.
begin
if (wsk<>nil) and (exerciseTime>0) then begin
dec(exerciseTime);
dec(wsk^.dana.workTime);
if (wsk^.dana.workTime=0) then delete(wsk);
end;
end;
procedure mainProgram; Procedura "program główny" ...
var
work:wskaznik;
sign:char;
begin
work:=nil;
repeat
clrscr;
writeln(' =*=MENU=*= '); Menu z poszczególnymi opcjami.
writeln('1. Dodaj nowe zadanie !');
writeln('2. Dodaj nmowego pracownika !');
writeln('3. Dodaj nowa godzine pracy !');
writeln('4. Wyjscie z programu !');
writeln;
textcolor(yellow); Wszelkiego rodzaju komunikaty.
writeln('Jesli dodasz nowe zadanie liczba godzin
zostanie zsumowana !');
textcolor(7);
writeln('Godziny pozostale do konca zadania: Wyświetlenie informacji o godzinach
',exerciseTime); pozostałych do zakooczenia sie zadania, są one
writeln; na bieżąco dekrementowane.
textcolor(yellow);
writeln('Pracownicy zostana posortowani wedlug Sortowania za pomocą procedury find_min.
najwyzszego stanowiska !');
textcolor(7);
writeln('Dane wprowadzonych pracowników: ');
if (work<>nil) then say(work) else
if (exerciseTime>0) then begin
writeln;
writeln('Aby kontynuowad musisz dodad
pracownika !');
end;
sign:=readkey; Menu wyboru.
if sign='1' then
exerciseTime:=exerciseTime+Random(21)+10;
if sign='2' then begin
if (work=nil) then create(work) else
insert(work);
work:=find_min(work); end;
if sign='3' then newHour(work);
if sign='4' then remove(work);
until sign='4';
end;
begin Początek programu głównego.
randomize;
mainProgram; Wywołanie głównej procedury.
end. Koniec programu głównego.
Screen z uruchomienia programu.
3. Wnioski
Jak wspomniano wy ej lista cykliczna mo e pos u y do budowy stosu lub kolejki. Wymaga to
zadeklarowania dodatkowych zmiennychż ż ł ż ć pamiętających element
znajdujący się na szczycie stosu, bądz
pierwszy i ostatni element kolejki. Można również napisać
implementację tej listy opartą na tablicy, na wzór implementacji
kolejki, która była opisywana w materiałach do drugiego wykładu. Listy cykliczne są stosowane w
postaci zarówno sprzętowej, jak i programowej. Korzystają z nich np.:
niektóre algorytmy szeregowania zadań oraz buforowania i wymiany stron w systemach operacyjnych.
W książce Donalda Edwina Knutha  Sztuka programowania
tom pierwszy, znajduje się opis algorytmu wykonującego operacje na wielomianach, które są
reprezentowane za pomocą listy cyklicznej. W opisywanej tam liście
cyklicznej umieszczony jest element  atrapa, którego zadaniem jest oznaczenie  punktu startowego
listy.