Лабораторная работа № 3. "КОЛЬЦЕВЫЕ СПИСКИ"

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

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


Задача работы: овладеть навыками написания программ по исследованию основных процедур списковых структур на языке программирования ПАСКАЛЬ .


Порядок работы :

• 
  изучить описание лабораторной работы;

• 
  по заданию, данному преподавателем, разработать алгоритм программы решения задачи;

• 
  написать программу на языке ПАСКАЛЬ;

• 
  отладить программу;

• 
  решить задачу;

• 
  оформить отчет.

Краткая теория

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





Как видно на рисунке, список замыкается в своеобразное "кольцо": двигаясь по ссылкам, можно от последнего элемента списка переходить к заглавному элементу. В связи с этим списки подобного рода называют кольцевыми списками.

Чтобы закольцевать список необходимо присвоить указателю последнего элемента указатель начала списка (Ptr(p)=lst).

Ptr(p) - указатель последнего элемента;

Lst - указатель начала списка.

Алгоритм

Операции с кольцевыми списками:

Вставка элемента в кольцевой список

Чтобы это осуществить необходимо произвести следующие действия:





a) Создать пустой элемент на который указывает указатель q

q=getnode

b) Внести х в информационное поле созданного элемента

info(q)=x

c) Связать элемент Х с элементом В

ptr(q)=ptr(p) - это означает, что указателю 

созданного элемента присваивается значение указателя элемента p.

d) Связать элемент А с элементом Х

ptr(p)=q - это означает, что следующим за элементом

А будет элемент на который указывает указатель q.

Окончательно:





Детально процесс вставки был проиллюстрирован в предыдущей работе.

Удаление элемента из кольцевого списка

Удалим из списка элемент, который следует за элементом с рабочим указателем р.





Чтобы это осуществить, необходимо произвести следующие действия:

a) Ввести указатель q, который будет указывать на удаляемый элемент.

q=ptr(p)

b) Поставить за элементом А элемент В

ptr(p)=ptr(q)

c) Запомнить информацию, которая содержится в поле info удаляемого элемента.

k=info(q)

d) Удалить элемент с указателем q.

Freenode(q)

Окончательно:

Задания

Варианты:

1) Дан кольцевой список, содержащий 20 фамилий игроков футбольной команды. Об этом говорит сайт https://intellect.icu . Разбить игроков на 2 группы по 10 человек. Во вторую группу попадает каждый 12-й человек.


2) Даны 2 кольцевых списка, содержащие фамилии спортсменов 2-х фехтовальных команд. Произвести жеребьевку. В первой команде выбирается каждый n-й игрок, а во второй - каждый m-й.


3) Задача Джозефуса.


4) Даны 2 кольцевых списка, содержащие фамилии участников лотереи и наименования призов. Выиграет N человек (каждый К-й). Число для пересчета призов - t.


5) Даны 2 списка, содержащих фамилии учащихся и номера экзаменационных билетов. Число пересчета для билетов - Е, для учащихся - К. Определить номера билетов, вытащенных учащимися.


6) Дан список содержащий перечень товаров. Из элементов 1-го списка (товары изготовленные фирмой SONY) создать новый список.


7) Даны 2 списка, содержащие фамилии студентов 2-х групп. Перевести L студентов из 1-й группы во вторую. Число пересчета -К.


8) Даны 2 списка, содержащие перечень товаров, производимых Концернами BOSH и FILIPS. Создать список товаров, выпускаемых как одной так и другой фирмой.


9) Даны 2 списка, содержащие фамилии футболистов основного состава команды и запасного. Произвести К замен.


10) Даны 2 списка, содержащие фамилии солдат 1-го и 2-го взводов. Во время атаки М человек из 1-го взвода погибли. Произвести пополнение солдатами 2-го взвода.


11) Даны 2 списка, содержащие перечень товаров и фамилии покупателей. Каждый N-й покупатель покупает М-й товар. Вывести список покупок.


12) Даны 2 списка, содержащие наименования товаров, выпускаемых фирмами SONY и SHARP. Создать список товаров, конкурирующих между собой товаров.

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

Из статьи мы узнали кратко, но содержательно про кольцевые списки