Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki, Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 7
Data wykonania ćwiczenia : 20.04.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

wskaź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 wskaź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ą wskaź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. Wskaź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 osoba=record name:integer; workTime:byte; position:byte; end; type wskaznik=^element; element=record dana:osoba; next:wskaznik; prev:wskaznik; end; var quantity:integer; exerciseTime:byte; procedure create(var wsk:wskaznik); 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; var 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; a:integer):wskaznik; 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); var 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); var 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); var 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); 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); 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; var work:wskaznik; sign:char; begin work:=nil; repeat clrscr; writeln(' =*=MENU=*= '); writeln('1. Dodaj nowe zadanie !'); writeln('2. Dodaj nmowego pracownika !'); writeln('3. Dodaj nowa godzine pracy !'); writeln('4. Wyjscie z programu !'); writeln; textcolor(yellow); writeln('Jesli dodasz nowe zadanie liczba godzin zostanie zsumowana !'); textcolor(7); writeln('Godziny pozostale do konca zadania: ',exerciseTime); writeln; textcolor(yellow); writeln('Pracownicy zostana posortowani wedlug najwyzszego stanowiska !'); textcolor(7); writeln('Dane wprowadzonych pracowników: '); if (work<>nil) then say(work) else if (exerciseTime>0) then begin writeln; writeln('Aby kontynuować musisz dodać pracownika !'); end; sign:=readkey; 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 randomize; mainProgram; end.

Zdefiniowanie typu rekordowego zawierającego dane pojedynczej osoby. Zdefiniowanie głównego typu rekordowego. Zmienne globalne. Procedura tworząca nowego pracownika. Funkcja wyszukująca pracownika o najwyższym priorytecie, a wiec najwyższym stanowisku. Funkcja wyszukująca kolejnego pracownika z jak najwyższym priorytetem. Procedura wstawiająca pracowników do listy cyklicznej. Procedura usuwająca pracownika z listy kiedy jego czas pracy zmaleje do 0. Procedura wyświetlająca listę na ekranie monitora. Procedura usuwająca listę. Procedura dodająca nową godzinę pracy. Procedura "program główny" ... Menu z poszczególnymi opcjami. Wszelkiego rodzaju komunikaty. Wyświetlenie informacji o godzinach pozostałych do zakończenia sie zadania, są one na bieżąco dekrementowane. Sortowania za pomocą procedury find_min. Menu wyboru. Początek programu głównego. Wywołanie głównej procedury. 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ądź 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.