Занятие 5. Кольцо. Формирование кольца. Основные операции над кольцом.

Koльцо - это вид связанного списка, в котором указатель последнего элемента ссылается на первый элемент.

Рассмотрите его графическое представление.

При программировании на Паскале считается, что для кольца существует обход элементов. Доступ возможен к любому элементу структуры.

Кольцо является динамической структурой – в зависимости от пользователя программы может изменяется длина и набор составляющих его элементов.

Опишем кольцо на языке программирования:

Type

TypeCircle = ^K;

K = record

Data: integer;

Next: TypeCircle;

End;

Var

Circle1: TypeCircle;

Формирование кольца

Рассмотрите процедуру формирования кольца. Для работы этой процедуры заводятся две локальные переменные типа TypeCircle для хранения адресов промежуточного и завершающего звена списка, последним оператором преобразуемого в кольцо.

Procedure FofmK(Var u: TypeCircle);

Var

x, y: TypeCircle;

i, N: integer;

Begin

write('Введите количество звеньев кольца: ');

readln(N);

for i:= 1 to N do

begin

new(x); {выделяем память для хранения нового элемента кольца}

write('Введите данные в звено: ');

readln(i);

x^.Data:= i; {заносим информацию в поле данных}

if u=nil {если кольцо еще не создано}

then

u:= x {то указатель первого элемента ставим на новый элемент}

else

y^.Next:= x; {присоединяем новый элемент к последнему элементу}

y:= x; {переносим указатель у на последний элемент}

end;

x^.Next:= u; {преобразуем получившийся список в кольцо}

End;

Над кольцом определены три операции: занесение элемента в кольцо, извлечение элемента из кольца и обход кольца.

Задание. Составьте программу, содержащую две процедуры: процедуру занесения элемента в кольцо и процедуру извлечения элемента из кольца по какому-либо условию. (Можно воспользоваться предыдущим текстом программы.)

Обход кольца

Для того чтобы обойти кольцо и вывести на экран содержащуюся в нем информацию, необходимо в локальной переменной типа TypeCircle запомнить адрес первого выводимого элемента. В этом случае можно избежать повторения и зацикливания программы. Вывод данных можно начинать с любого элемента кольца; это зависит от адреса первого элемента, переданного в процедуру обхода.

Рассмотрите процедуру обхода кольца.

Procedure PrintК(u: TypeCircle);

Var

x: TypeCircle;

Begin

x:= u;

repeat

write(x^.Data,' ');

x:= x^.Next;

until x=u;

readln;

End;

Задание. Дополните предыдущую программу процедурой обхода кольца.

Занятие 6. Примеры решения задач с применением динамической структуры кольцо. Творческая работа.

Задание. Рассмотрите приведенные примеры задач, решенные с помощью динамической структуры – кольцо. Наберите их на компьютере, проверьте их действие, вставьте комментарий.

Задача 1. N ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k-го, смыкая при этом круг. Определить порядок удаления ребят из круга.

Для хранения данных об участниках игры используется список.

Наберите предложенный ниже текст программы, проверьте его работу, дополните комментариями.

Program Schitalka;

Type

Children = ^Child;

Child = record

Data: integer;

Next: Children;

end;

Var

Circl, p, Temp: Children;

i, j, NumName: integer;

text: string;

Function NumSlov(Var S: string): integer;

Var

i, d: integer;

Begin

d:= 0;

i:= 1;

while i < Length(S) do

begin

while S[i] = ' ' do

Inc(i);

while S[i] <> ' ' do

Inc(i);

d:= d+1;

end;

if S[Length(S)] = ''

then

d:= d-1;

NumSlov:= d;

End;

Procedure AddName(Var Old, Young: Children);

Begin

Young^.Next:= Old;

Young^.Prev:= Old^.Prev;

Old^.Prev^.Next:= Young;

Old^.Prev:= Young;

End;

Procedure DeleteName(Var Old: Children);

Begin

Old^.Next^.Prev:= Old^.Prev;

Old^.Prev^.Next:= Old^.Next;

End;

Begin

new(Circl);

Circl^.Next:= Circl;

Circl^.Prev:= Circl;

Circl^.Name:= '';

writeln('Считалка');

writeln('Введите текст считалки >');

readln(text);

writeln('Сколько человек в кругу? >');

readln(NumName);

if NumName>0

then

begin

write('Введите ',i,'-е имя: ');

new(p);

readln(p^.name);

temp:= head^.next;

while temp <> head do

temp:= temp^.next;

AddName(temp, p);

end;

for i:= 1 to NumName-1 do

begin

temp:= head;

for j:= 1 to NumSlov(text) do

begin

temp:= temp^.next;

if temp^.name = ''

then

temp:=temp^.next;

end;

writeln(temp^.name, '- вышел');

deleteName(temp);

end;

writeln(head^.next^.name, '- остался');

End.

Пример 2. Вывести на экран работающий светофор.

Program GrushinK;

Uses

Crt, Graph;

Type

TypeCircle = ^K;

K = record

Data: char;

Next: TypeCircle;

end;

Const

XX = 80;

R = 50;

Var

Svetofor, x: TypeCircle;

FraphDriver, GraphMode, Y: integer;

Procedure Picture;

Begin

SetViewPort(240, 1, 400, 477, ClipOff);

Line(0, 1, 0, 477);

Line(160, 1, 160, 477);

Line(0, 1, 160, 1);

Line(0, 477, 160, 477);

Line(0, 150, 156, 150);

Line(0, 330, 156, 330);

Line(-240, 480, 0, 100);

Line(400, 480, 160, 100);

Line(380, 460, 160, 460);

Line(160, 440, 368, 440);

Line(368, 440, 380, 460);

Line(-220, 460, -208, 440);

SetFillStyle(1, White);

FloodFill(375, 455, White);

FloodFill(-215, 455, White);

SetFillStyle(7, 6);

FloodFill(-230, 200, White);

SetColor(4);

Line(-240, 150, -120, -1);

Line(400, 150, 240, -1);

SetColor(15);

SetFillStyle(9, 4);

FloodFill(-240, 0, 4);

FloodFill(390, 10, 4);

SetFillStyle(1, 8);

FloodFill(-100, 470, White);

Y:= 74;

Circle(XX, Y, R);

Y:= 240;

Circle(XX, Y, R);

Y:= 405;

Circle(XX, Y, R);

SetFillStyle(9, 6);

FloodFill(5, 5, White);

End;

Procedure Yellow(Y: integer);

Begin

Picture;

Y:= 240;

SetFillStyle(1, 14);

FloodFill(XX, Y, 15);

Delay(850);

ClearViewPort;

End;

Procedure Green(Y: integer);

Begin

Picture;

Y:= 405;

SetFillStyle(1, 2);

FloodFill(XX, Y, 15);

Delay(1500);

ClearViewPort;

End;

Procedure Red Yellow(Y: integer);

Begin

Picture;

Y:= 240;

SetFillStyle(1, 14);

FloodFill(XX, Y, 15);

Delay(1500);

ClearViewPort;

End;

Procedure Red(Y: integer);

Begin

Picture;

Y:= 74;

SetFillStyle(1, 4);

FloodFill(XX, Y, 15);

Delay(2000);

ClearViewPort;

End;

Procedure Vibor;

Begin

case x^.Data of

'R': Red(Y);

'2': Red Yellow(Y);

'G': Green(Y);

'Y': Yellow(Y);

End;

Begin

GraphDriver:= Detect;

InitGraph(GraphDriver, GraphMode, '..\BGI');

new(x);

u:= x;

x^.Data:= 'R';

new(x^.Next);

x:= x^.Next;

x^.Data:= '2';

new(x^.Next);

x:= x^.Next;

x^.Data:= 'G';

new(x^.Next);

x:= x^.Next;

x^.Data:= 'Y';

x^.Next:= u;

x:= u;

while not KeyPressed do

begin

Vibor;

x:= x^.Next;

end;

End.

Задание. Придумайте интересную задачу из жизни и решите ее с помощью динамической структуры кольцо.

Список