Теоретический материал: стеки, очереди, кольца (Паскаль)

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

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, d : integer;
Begin
  write('Введите количество звеньев кольца: ');
  readln(N);
  for i := 1 to N do
    begin
      new(x); {выделяем память для хранения нового элемента кольца}
      write('Введите данные в звено: ');
      readln(d);
      x^.Data := d; {заносим информацию в поле данных}
      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;

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