Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

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

Лекция



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



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


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


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

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

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

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

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

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

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



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



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


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


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

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

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

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

Алгоритм



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

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



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


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


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


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

q=getnode

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

info(q)=x

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

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

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

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

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

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

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


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


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

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



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


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


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

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

q=ptr(p)

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

ptr(p)=ptr(q)

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

k=info(q)

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

Freenode(q)

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


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

Задания



Варианты:

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. Создать список товаров, конкурирующих между собой товаров.

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

Из статьи мы узнали кратко, но содержательно про кольцевые списки
создано: 2014-12-05
обновлено: 2021-03-13
132580



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Структуры данных

Термины: Структуры данных