Else begin

fHead^.Left: = DisItem^.Left;

DisItem^.Left^.Right: =fHead; // последним становится предпоследний эл-т

end;

Dispose(DisItem);

Dec(fSize); // уменьшение числа элементов на 1

end; // function tDCCircleList.DeleteRear

Исключение элемента из начала двусвязного циклического списка. При реализации этой операции сначала указатель первого элемента списка fHead передвигается на элемент, стоящий справа от него – бывший первый элемент (который и нужно исключить) становится последним. Его можно исключить из списка с использованием метода исключения справа DeleteRear. Метод класса tCDCircleList, реализующий исключение элемента слева, имеет вид:

function tDCCircleList.DeleteHead: tValue;

Begin

fHead: = fHead^.Right;

DeleteHead: = DeleteRear;

end; // function tDCCircleList.DeleteHead

Операции исключения элементов из двусвязного списка DeleteFirst и DeleteLast неприменимы к пустому списку, поэтому перед их выполнением необходимо анализировать значение признака «список пуст».

Лабораторная работа 2.
Односвязные и двусвязные
линейные списки

Задание

Опишите классы-списки, необходимые для решения задачи, указанной в вашем варианте задания, и реализуйте его методы.

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

Варианты заданий

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

2. Сложение длинных чисел. Используя двусвязные циклические списки сложить два числа: x = 134557952499317879 и y = 79349864365110. Числа разбить на группы по девять цифр, которые будут являться элементами списка. Результат сложения занести в циклический список.

3. Задача Джозефуса. По кругу стоит группа людей. С терминала вводятся число n и фамилия человека, с которого начинается счет. Начиная с введенной фамилии по кругу отсчитывается n человек, n-й выбывает из круга и т.д. Выводить фамилии исключенных из круга людей. Задачу решить, используя односвязный циклический список.

4. Создать два односвязных циклических списка с целочисленными элементами. Переписать в односвязный линейный список элементы с совпадающими значениями.

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

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

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

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

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

10 FOR x=a TO b STEP c

…

30 NEXT c

где x – переменная цикла. Для каждого цикла выводить сообщение вида: «Цикл по x открыт», «Цикл по x закрыт».

10. Создать односвязные списки студентов двух групп с полученными на экзаменах оценками. Сформировать в алфавитном порядке односвязный циклический список студентов, получивших отличные оценки.

11. Сформировать двусвязный список строк. Исключить из списка последние три элемента. Скопировать в двусвязный циклический список вторую половину его элементов, начиная с конца.

12. Выполнить задание 9 при условии, что один оператор NEXT, содержащий несколько переменных, может завершать одновременно несколько вложенных циклов (например: NEXT x, y, z).

13. Сформировать два двусвязных циклических списка с элементами – фамилиями клиентов. Удалить из первого списка клиентов, находящихся в двух списках.

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

15. Описать односвязный циклический список, тип значения элемента которого – запись из двух полей: символ и количество его повторений в тексте. Переписать в линейный список элементы с русскими буквами.

16. Сформировать два списка с фамилиями клиентов. Слить оба списка в третий, циклический, расположив клиентов через одного.

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

18. Сформировать два циклических списка целых чисел. Слить их в один список, а затем оставить в нем только отличающиеся элементы.

19. Описать односвязный циклический список, тип значения элемента которого – запись из двух полей: символ русского алфавита и количество его повторений в тексте. С использованием односвязного линейного списка расположить элементы исходного списка в обратном порядке.

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

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

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

23. Решить задачу 3 при счете через одного человека с использованием двусвязного циклического списка.

24. Описать односвязный линейный список, тип значения элемента которого – запись из двух полей: символ и количество его повторений в тексте. Реализовать метод вставки, выполняющий вставку отсутствующего в списке символа в его конец и перемещение на один элемент к началу списка элемента с присутствующим в списке значением.

25. По кругу стоит группа людей. С терминала вводятся число n и фамилия человека, с которого начинается счет. Начиная с введенной фамилии в обратную сторону по кругу отсчитывается N человек, N-й выбывает из круга и т.д. Выводить фамилии исключенных из круга людей. Задачу решить, используя двусвязный циклический список.

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

27. Описать двусвязный список строк и реализовать метод возвращения адреса первого с конца и первого с начала элемента с заданным значением. Исключить второй с начала и второй с конца элемент со значением «дом».

28. С использованием односвязного циклического списка смоделировать работу очереди.

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

30. Реализовать методы возвращения адреса элемента двусвязного циклического списка по его номеру, начиная от начала и от конца списка. С использованием этого метода поменять местами третий с начала элемент списка с третьим с конца.