Pascaler
О проекте Теоретический материал Тестирование Архив задач
Войти в личный кабинет



О проекте


Преподавателям


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

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;

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

Вернуться назад
2003—2012 © Группа «Vimedia»
Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.