Лабораторная работа № 2 Организация и обработка списков

Лабораторная работа посвящена рекурсивным структурам данных и реализации хранения динамической последовательности данных при помощи связанных структур. Используется такие понятия, как стек, очередь, одно- и двусвязный список, циклический список.

139

ОБРАЗЕЦ ОТЧЁТА ПО ЛАБОРАТОРНОЙ РАБОТЕ

140

Задачи

1.Описать функцию, которая подсчитывает количество элементов списка l, у которых равные соседи. Первый и последний элемент считать

соседями.

2.Описать логическую функцию equal(l1, l2), проверяющую на равенство списки l1 и l2.

3.Описать логическую функцию member(a, l), проверяющую, входит ли элемент a в список l.

4.Описать функцию, которая удаляет из списка l первый отрицательный элемент, если такой есть.

5.Дан непустой стек. Создать два новых стека, переместив в первый из них все элементы исходного стека с чётными значениями, а во второй — с нечётными (элементы в новых стеках будут располагаться в порядке, обратном исходному; один из этих стеков может оказаться пустым). Вывести адреса p2 и p3 вершин полученных стеков (для пустого стека вывести NULL).

6.Описать функцию, которая в списке l из каждой группы подряд идущих равных элементов оставляет только один.

7.Дана непустая очереди. Извлекать из очереди элементы, пока значение начального элемента очереди не станет чётным, и выводить значения извлечённых элементов (если очередь не содержит элементов с чётными значениями, то извлечь все её элементы). Вывести также новые адреса начала и конца очереди (для пустой очереди положить p3 = p4 = NULL). После извлечения элементов из очереди освобождать память, занимаемую этими элементами.

8.Дано число d и очередь, содержащая не менее двух элементов. Добавить элемент со значением d в конец очереди и извлечь из очереди первый (начальный) элемент. Вывести значение извлеченного элемента и новые адреса начала и конца очереди. После извлечения элемента из очереди

160

освободить память, занимаемую этим элементом.

9.Дано число n (> 0) и две непустые очереди; Переместить n начальных элементов первой очереди в конец второй очереди. Если первая очередь содержит менее n элементов, то переместить из первой очереди во вторую все элементы. Вывести новые адреса начала и конца обеих очередей (для пустой очереди вывести две константы NULL).

10.Дан непустой двусвязный список. Удалить из списка все элементы с нечётными значениями и вывести указатель p2 на начало преобразованного списка. Если в результате удаления элементов список окажется пустым, то положить p2 = NULL. После удаления элементов из списка освобождать память, занимаемую этими элементами.

11.Дан набор из 10 чисел. Создать очередь, содержащую данные числа в указанном порядке (первое число будет размещаться в начале очереди, последнее — в конце), и вывести указатели p1 и p2 на начало и конец очереди.

12.Даны два непустых стека. Перемещать элементы из первого стека во второй, пока значение вершины первого стека не станет чётным (перемещенные элементы первого стека будут располагаться во втором стеке в порядке, обратном исходному). Если в первом стеке нет элементов с чётными значениями, то переместить из первого стека во второй все элементы. Вывести адреса p1 и p2 новых вершин первого и второго стека (если первый стек окажется пустым, то положить p2 = NULL).

13.Описать функцию, которая проверяет, входит ли список l1 в список l2.

14.Описать функцию, которая объединяет два упорядоченных по возрастанию списка в один.

15.Дан непустой стека. Извлечь из стека первый (верхний) элемент и вывести его значение d и адрес p2 новой вершины. Если после извлечения элемента стек окажется пустым, то положить p2 = NULL.

161

После извлечения элемента из стека освободить память, занимаемую этим элементом.

16.Описать функцию, значением которой является список, построенный из элементов двумерного массива X (список строить от последнего элемента массива).

17.Дано неотрицательное число n и набор из n чисел. Создать стек, содержащий исходные числа (последнее число будет вершиной стека), и вывести указатель p1 на его вершину. Если n = 0, то положить p1 = NULL.

18.Дан набор из 10 чисел. Создать две очереди: первая должна содержать числа из исходного набора с нечётными номерами (1, 3, ..., 9), а вторая —

с чётными (2, 4, ..., 10); порядок чисел в каждой очереди должен совпадать с порядком чисел в исходном наборе. Вывести указатели на начало и конец каждой из полученных очередей.

19.Используя представление текста в виде списка, описать функцию, заменяющую i-ю строку на j-ю и наоборот.

20.Даны две очереди. Переместить все элементы первой очереди (в порядке от начала к концу) в конец второй очереди и вывести новые адреса p1 и p2 начала и конца второй очереди.

21.Дано число d непустой стек. Добавить элемент со значением d в стек и вывести адрес новой вершины стека.

22.Даны два непустых стека. Переместить все элементы из первого стека во второй (в результате элементы первого стека будут располагаться во втором стеке в порядке, обратном исходному) и вывести адрес p3 новой вершины второго стека.

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

162

Вывести новые адреса начала и конца обеих очередей (для пустой очереди вывести две константы NULL).

24.Описать функцию, которая из списка l, содержащего не менее 2-х элементов, удаляет все элементы, у которых одинаковые соседи. Первый

ипоследний элемент считать соседями.

25.Даны две непустые очереди. Очереди содержат одинаковое количество элементов. Объединить очереди в одну, в которой элементы исходных очередей чередуются (начиная с первого элемента первой очереди). Вывести указатели на начало и конец полученной очереди.

26.Дан указатель pc на один из элементов непустого двусвязного списка. Вывести число n — количество элементов в списке, а также указатели p1

иp2 на начало и конец списка.

27.Описать функцию, которая строит l2 – копию списка l1.

28.Даны числа d1 и d2 и указатель pc на один из элементов непустого двусвязного списка. Добавить в начало списка новый элемент со значением d1, а в конец — новый элемент со значением d2. Вывести адреса p1 и p2 начала и конца полученного списка.

29.Дано число d и указатель pc на один из элементов непустого двусвязного списка. Вставить перед и после данного элемента списка новый элемент со значением d и вывести указатели p1 и p2 на начало и конец списка.

30.Дан указатель pa на начало непустого двусвязного списка. Продублировать в списке все элементы с нечётными номерами (новые элементы добавлять перед существующими элементами с такими же значениями) и вывести указатели p1 и p2 на начало и конец преобразованного списка.

31.Дан указатель pc на один из элементов непустого двусвязного списка. Удалить из списка данный элемент и вывести указатели p1 и p2 на начало и конец списка. Если в результате удаления элемента список окажется пустым, то положить p1 = p2 = NULL. После удаления

163

элемента из списка освободить память, занимаемую этим элементом.

32.Дан двусвязный список, содержащий не менее двух элементов. Удалить из списка все элементы с нечётными номерами (1, 3, ...) и вывести указатель p2 на начало преобразованного списка. После удаления элементов из списка освобождать память, занимаемую этими элементами.

33.Дан указатель pc на один из элементов непустого двусвязного списка. Переместить данный элемент в конец списка и вывести указатели p1 и p2 на начало и конец преобразованного списка. Операции выделения и освобождения памяти не использовать, поля с данными не изменять.

34.Даны указатели px и py на два различных элемента двусвязного списка (элемент с адресом px находится в списке перед элементом с адресом py, но не обязательно рядом с ним). Поменять местами данные элементы и вывести указатель p1 на начало преобразованного списка. Операции выделения и освобождения памяти не использовать, поля с данными не изменять.

35.Дан указатель на непустой двусвязный список. Перегруппировать его элементы, переместив все элементы с нечётными номерами в конец списка (в том же порядке) и вывести указатель p2 на начало преобразованного списка. Операции выделения и освобождения памяти не использовать, поля с данными не изменять.

164