Все числа, упоминаемые в заданиях данной группы, являются целыми. Все указатели имеют тип PNode и указывают на записи типа TNode. На языке Pascal типы PNode и TNode описываются следующим образом:

Приведем также описание этих типов на языке C++:

В заданиях на стеки и очереди (Pointer1-Pointer28) при работе с записями типа TNode используются только поля Data и Next (см. задание Pointer1); в заданиях на двусвязные списки (Pointer29-Pointer80) используются все поля записи TNode (см. задание Pointer29). Так как переменные типа «указатель» предназначены для хранения адресов, в формулировках заданий слова «указатель» (на элемент данных) и «адрес» (элемента данных) используются как синонимы. Имя $$nil$$ для нулевого указателя в формулировках заданий заимствовано из языка Pascal. В языке C++ в качестве нулевого указателя можно использовать обычное число $$0$$ или макроопределение NULL.

Стеки

Pointer1. Дан адрес $$P_1$$ записи типа TNode, содержащей поле Data (целого типа) и поле Next (типа PNode — указателя на TNode). Эта запись связана полем Next со следующей записью того же типа. Вывести значения полей Data обеих записей, а также адрес $$P_2$$ следующей записи.

Решение задачи, на языке: Паскаль

Pointer2. Дан адрес $$P_1$$ записи типа TNode. Эта запись связана полем Next со следующей записью того же типа, она, в свою очередь, — со следующей, и так далее до записи, поле Next которой равно $$nil$$ (таким образом, возникает цепочка связанных записей). Вывести значения полей Data для всех элементов цепочки, длину цепочки (то есть число ее элементов) и адрес ее последнего элемента.

Решение задачи, на языке: Паскаль

В заданиях Pointer3-Pointer13 структура «стек» (stack) моделируется цепочкой связанных узлов-записей типа TNode (см. задание Pointer2). Поле Next последнего элемента цепочки равно $$nil$$. Вершиной стека (top) считается первый элемент цепочки. Для доступа к стеку используется указатель на его вершину (для пустого стека данный указатель полагается равным $$nil$$). Значением элемента стека считается значение его поля Data.

Pointer3. Дано число $$D$$ и указатель $$P_1$$ на вершину непустого стека. Добавить элемент со значением $$D$$ в стек и вывести адрес $$P_2$$ новой вершины стека.

Решение задачи, на языке: Паскаль

Pointer4. Дано число $$N$$ $$(>0)$$ и набор из $$N$$ чисел. Создать стек, содержащий исходные числа (последнее число будет вершиной стека), и вывести указатель на его вершину.

Решение задачи, на языке: Паскаль

Pointer5. Дан указатель $$P_1$$ на вершину непустого стека. Извлечь из стека первый (верхний) элемент и вывести его значение $$D$$, а также адрес $$P_2$$ новой вершины стека. Если после извлечения элемента стек окажется пустым, то положить $$P_2=nil$$. После извлечения элемента из стека освободить память, занимаемую этим элементом.

Решение задачи, на языке: Паскаль

Pointer6. Дан указатель $$P_1$$ на вершину стека, содержащего не менее десяти элементов. Извлечь из стека первые девять элементов и вывести их значения. Вывести также адрес новой вершины стека. После извлечения элементов из стека освобождать память, которую они занимали.

Решение задачи, на языке: Паскаль

Pointer7. Дан указатель $$P_1$$ на вершину стека (если стек пуст, то $$P_1=nil$$). Извлечь из стека все элементы и вывести их значения. Вывести также количество извлеченных элементов $$N$$ (для пустого стека вывести $$0$$). После извлечения элементов из стека освобождать память, которую они занимали.

Решение задачи, на языке: Паскаль

Pointer8. Даны указатели $$P_1$$ и $$P_2$$ на вершины двух непустых стеков. Переместить все элементы из первого стека во второй (в результате элементы первого стека будут располагаться во втором стеке в порядке, обратном исходному) и вывести адрес новой вершины второго стека. Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer9. Даны указатели $$P_1$$ и $$P_2$$ на вершины двух непустых стеков. Перемещать элементы из первого стека во второй, пока значение вершины первого стека не станет четным (перемещенные элементы первого стека будут располагаться во втором стеке в порядке, обратном исходному). Если в первом стеке нет элементов с четными значениями, то переместить из первого стека во второй все элементы. Вывести адреса новых вершин первого и второго стека (если первый стек окажется пустым, то вывести для него константу $$nil$$). Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer10. Дан указатель $$P_1$$ на вершину непустого стека. Создать два новых стека, переместив в первый из них все элементы исходного стека с четными значениями, а во второй — с нечетными (элементы в новых стеках будут располагаться в порядке, обратном исходному; один из этих стеков может оказаться пустым). Вывести адреса вершин полученных стеков (для пустого стека вывести $$nil$$). Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer11. Дан указатель $$P_1$$ на вершину стека (если стек пуст, то $$P_1=nil$$). Также дано число $$N$$ $$(>0)$$ и набор из $$N$$ чисел. Описать тип TStack — запись с одним полем Top типа PNode (поле указывает на вершину стека) — и процедуру Push($$S$$, $$D$$), которая добавляет в стек $$S$$ новый элемент со значением $$D$$ ($$S$$ — входной и выходной параметр типа TStack, $$D$$ — входной параметр целого типа). С помощью процедуры Push добавить в исходный стек данный набор чисел (последнее число будет вершиной стека) и вывести адрес новой вершины стека.

Решение задачи, на языке: Паскаль

Pointer12. Дан указатель $$P_1$$ на вершину стека, содержащего не менее пяти элементов. Используя тип TStack (см. задание Pointer11), описать функцию Pop ($$S$$) целого типа, которая извлекает из стека $$S$$ первый (верхний) элемент, возвращает его значение и освобождает память, которую занимал извлеченный элемент ($$S$$ — входной и выходной параметр типа TStack) . С помощью функции Pop извлечь из исходного стека пять элементов и вывести их значения. Вывести также указатель на новую вершину стека (если результирующий стек окажется пустым, то этот указатель должен быть равен $$nil$$).

Решение задачи, на языке: Паскаль

Pointer13. Дан указатель $$P_1$$ на вершину стека. Используя тип TStack (см. задание Pointer11), описать функции StackIsEmpty($$S$$) логического типа (возвращает True, если стек $$S$$ пуст, и False в противном случае) и Peek($$S$$) целого типа (возвращает значение вершины непустого стека $$S$$, не удаляя ее из стека). В обеих функциях переменная $$S$$ является входным параметром типа TStack. С помощью этих функций, а также функции Pop из задания Pointer12, извлечь из исходного стека пять элементов (или все содержащиеся в нем элементы, если их менее пяти) и вывести их значения. Вывести также значение функции StackIsEmpty для результирующего стека и, если результирующий стек не является пустым, значение и адрес его новой вершины.

Решение задачи, на языке: Паскаль

Очереди

В заданиях Pointer14-Pointer28 структура «очередь» (queue) моделируется цепочкой связанных узлов-записей типа TNode (см. задание Pointer2). Поле Next последнего элемента цепочки равно $$nil$$. Началом очереди («головой», head) считается первый элемент цепочки, концом («хвостом», tA_Il) — ее последний элемент. Для возможности быстрого добавления в конец очереди нового элемента удобно хранить, помимо указателя на начало очереди, также и указатель на ее конец. В случае пустой очереди указатели на ее начало и конец полагаются равными $$nil$$. Как и для стека, значением элемента очереди считается значение его поля Data.

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

Решение задачи, на языке: Паскаль

Pointer15. Дан набор из $$10$$ чисел. Создать две очереди: первая должна содержать числа из исходного набора с нечетными номерами $$(1, 3,…, 9)$$, а вторая — с четными $$(2, 4,…, 10)$$; порядок чисел в каждой очереди должен совпадать с порядком чисел в исходном наборе. Вывести указатели на начало и конец первой, а затем второй очереди.

Решение задачи, на языке: Паскаль

Pointer16. Дан набор из $$10$$ чисел. Создать две очереди: первая должна содержать все нечетные, а вторая — все четные числа из исходного набора (порядок чисел в каждой очереди должен совпадать с порядком чисел в исходном наборе). Вывести указатели на начало и конец первой, а затем второй очереди (одна из очередей может оказаться пустой; в этом случае вывести для нее две константы $$nil$$).

Решение задачи, на языке: Паскаль

Pointer17. Дано число $$D$$ и указатели $$P_1$$ и $$P_2$$ на начало и конец очереди (если очередь является пустой, то $$P_1=P_2=nil$$). Добавить элемент со значением $$D$$ в конец очереди и вывести новые адреса начала и конца очереди.

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

Pointer19. Дано число $$N$$ $$(>0)$$ и указатели $$P_1$$ и $$P_2$$ на начало и конец непустой очереди. Извлечь из очереди $$N$$ начальных элементов и вывести их значения (если очередь содержит менее $$N$$ элементов, то извлечь все ее элементы). Вывести также новые адреса начала и конца очереди (для пустой очереди дважды вывести $$nil$$). После извлечения элементов из очереди освобождать память, которую они занимали.

Решение задачи, на языке: Паскаль

Pointer20. Даны указатели $$P_1$$ и $$P_2$$ на начало и конец непустой очереди. Извлекать из очереди элементы, пока значение начального элемента очереди не станет четным, и выводить значения извлеченных элементов (если очередь не содержит элементов с четными значениями, то извлечь все ее элементы). Вывести также новые адреса начала и конца очереди (для пустой очереди дважды вывести $$nil$$). После извлечения элементов из очереди освобождать память, которую они занимали.

Решение задачи, на языке: Паскаль

Pointer21. Даны две очереди; адреса начала и конца первой равны $$P_1$$ и $$P_2$$, а второй — $$P_3$$ и $$P_4$$ (если очередь является пустой, то соответствующие адреса равны $$nil$$). Переместить все элементы первой очереди (в порядке от начала к концу) в конец второй очереди и вывести новые адреса начала и конца второй очереди. Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer22. Дано число $$N$$ $$(>0)$$ и две непустые очереди; адреса начала и конца первой равны $$P_1$$ и $$P_2$$, а второй — $$P_3$$ и $$P_4$$. Переместить $$N$$ начальных элементов первой очереди в конец второй очереди. Если первая очередь содержит менее $$N$$ элементов, то переместить из первой очереди во вторую все элементы. Вывести новые адреса начала и конца первой, а затем второй очереди (для пустой очереди дважды вывести $$nil$$). Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer23. Даны две непустые очереди; адреса начала и конца первой равны $$P_1$$ и $$P_2$$, а второй — $$P_3$$ и $$P_4$$. Перемещать элементы из начала первой очереди в конец второй, пока значение начального элемента первой очереди не станет четным (если первая очередь не содержит четных элементов, то переместить из первой очереди во вторую все элементы). Вывести новые адреса начала и конца первой, а затем второй очереди (для пустой очереди дважды вывести $$nil$$). Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

Pointer25. Даны две непустые очереди; адреса начала и конца первой равны $$P_1$$ и $$P_2$$, а второй — $$P_3$$ и $$P_4$$. Элементы каждой из очередей упорядочены по возрастанию (в направлении от начала очереди к концу). Объединить очереди в одну с сохранением упорядоченности элементов. Вывести указатели на начало и конец полученной очереди. Операции выделения и освобождения памяти не использовать, поля Data не изменять.

Решение задачи, на языке: Паскаль

Pointer26. Даны указатели $$P_1$$ и $$P_2$$ на начало и конец очереди (если очередь является пустой, то $$P_1=P_2=nil$$). Также дано число $$N$$ $$(>0)$$ и набор из $$N$$ чисел. Описать тип TQueue — запись с двумя полями типа PNode: Head (начало очереди) и TAil (конец очереди) — и процедуру Enqueue($$Q$$, $$D$$), которая добавляет в конец очереди $$Q$$ новый элемент со значением $$D$$ ($$Q$$ — входной и выходной параметр типа TQueue, $$D$$ — входной параметр целого типа). С помощью процедуры Enqueue добавить в исходную очередь данный набор чисел и вывести новые адреса ее начала и конца.

Решение задачи, на языке: Паскаль

Pointer27. Даны указатели $$P_1$$ и $$P_2$$ на начало и конец очереди, содержащей не менее пяти элементов. Используя тип TQueue (см. задание Pointer26), описать функцию Dequeue(Q) целого типа, которая извлекает из очереди первый (начальный) элемент, возвращает его значение и освобождает память, занимаемую извлеченным элементом ($$Q$$ — входной и выходной параметр типа TQueue). С помощью функции Dequeue извлечь из исходной очереди пять начальных элементов и вывести их значения. Вывести также адреса начала и конца результирующей очереди (если очередь окажется пустой, то эти адреса должны быть равны $$nil$$).

Решение задачи, на языке: Паскаль

Pointer28. Даны указатели $$P_1$$ и $$P_2$$ на начало и конец очереди. Используя тип TQueue (см. задание Pointer26), описать функцию QueueIsEmpty(Q) логического типа, которая возвращает True, если очередь $$Q$$ пуста, и False в противном случае ($$Q$$ — входной параметр типа TQueue). Используя эту функцию для проверки состояния очереди, а также функцию Dequeue из задания Pointer27, извлечь из исходной очереди пять начальных элементов (или все содержащиеся в ней элементы, если их менее пяти) и вывести их значения. Вывести также значение функции QueueIsEmpty для полученной очереди и новые адреса ее начала и конца.

Решение задачи, на языке: Паскаль

Двусвязные списки

Pointer29. Дан адрес $$P_2$$ записи типа TNode, содержащей поле Data (целого типа) и поля Prev и Next (типа PNode — указателя на TNode). Эта запись связана полями Prev и Next соответственно с предыдущей и последующей записью того же типа. Вывести значения полей Data предыдущей и последующей записи, а также адреса $$P_1$$ и $$P_3$$ предыдущей и последующей записи.

Решение задачи, на языке: Паскаль

Pointer30. Дан указатель $$P_1$$ на начало непустой цепочки элементов-записей типа TNode, связанных между собой с помощью поля Next. Используя поле Prev записи TNode, преобразовать исходную (односвязную) цепочку в двусвязную, в которой каждый элемент связан не только с последующим элементом (с помощью поля Next), но и с предыдущим (с помощью поля Prev). Поле Prev первого элемента положить равным $$nil$$. Вывести указатель на последний элемент преобразованной цепочки.

Решение задачи, на языке: Паскаль

В заданиях Pointer31-Pointer69 структура «двусвязный список» (doubly linked list) моделируется цепочкой узлов-записей типа TNode, связанных как с предыдущим, так и с последующим узлом (см. задание Pointer30). Поле Next последнего элемента цепочки и поле Prev первого элемента цепочки равны $$nil$$. Для доступа к любому элементу двусвязного списка достаточно иметь указатель на один из его элементов, однако для ускорения операций со списком обычно хранят три указателя: на первый элемент списка (first), на его последний элемент (last) и на текущий элемент (current). Для пустого списка все эти указатели полагаются равными $$nil$$. Как в случае стека и очереди, значением элемента списка считается значение его поля Data.

Pointer31. Дан указатель $$P_0$$ на один из элементов непустого двусвязного списка. Вывести число $$N$$ — количество элементов в списке, а также указатели $$P_1$$ и $$P_2$$ на первый и последний элементы списка.

Решение задачи, на языке: Паскаль

Pointer32. Даны числа $$D_1$$ и $$D_2$$ и указатель $$P_0$$ на один из элементов непустого двусвязного списка. Добавить в начало списка новый элемент со значением $$D_1$$, а в конец — новый элемент со значением $$D_2$$. Вывести адреса первого и последнего элементов полученного списка.

Решение задачи, на языке: Паскаль

Pointer33. Дано число $$D$$ и указатель $$P_0$$ на один из элементов непустого двусвязного списка. Вставить перед данным элементом списка новый элемент со значением $$D$$ и вывести указатель на добавленный элемент списка.

Решение задачи, на языке: Паскаль

Pointer34. Дано число $$D$$ и указатель $$P_0$$ на один из элементов непустого двусвязного списка. Вставить после данного элемента списка новый элемент со значением $$D$$ и вывести указатель на добавленный элемент списка.

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

Pointer37. Дан указатель $$P_1$$ на первый элемент непустого двусвязного списка. Продублировать в списке все элементы с нечетными номерами (новые элементы добавлять перед существующими элементами с такими же значениями) и вывести указатель на первый элемент преобразованного списка.

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

Pointer39. Дан указатель $$P_1$$ на первый элемент непустого двусвязного списка. Продублировать в списке все элементы с нечетными значениями (новые элементы добавлять перед существующими элементами с такими же значениями) и вывести указатель на первый элемент преобразованного списка.

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

Pointer41. Дан указатель $$P_0$$ на один из элементов непустого двусвязного списка. Удалить из списка данный элемент и вывести два указателя: на элемент, предшествующий удаленному, и на элемент, следующий за удаленным (один или оба этих элемента могут отсутствовать; для отсутствующих элементов выводить $$nil$$). После удаления элемента из списка освободить память, занимаемую этим элементом.

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

Pointer43. Дан указатель $$P_1$$ на первый элемент непустого двусвязного списка. Удалить из списка все элементы с нечетными значениями и вывести указатель на первый элемент преобразованного списка (если в результате удаления элементов список окажется пустым, то вывести $$nil$$). После удаления элементов из списка освобождать память, которую они занимали.

Решение задачи, на языке: Паскаль

Pointer44. Дан указатель $$P_0$$ на один из элементов непустого двусвязного списка. Переместить данный элемент в конец списка и вывести указатели на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изменять.

Решение задачи, на языке: Паскаль

Pointer45. Дан указатель $$P_0$$ на один из элементов непустого двусвязного списка. Переместить данный элемент в начало списка и вывести указатели на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изменять.

Решение задачи, на языке: Паскаль

Pointer46. Дано число $$K$$ $$(>0)$$ и указатель $$P_0$$ на один из элементов непустого двусвязного списка. Переместить в списке данный элемент на $$K$$ позиций вперед (если после данного элемента находится менее $$K$$ элементов, то переместить его в конец списка). Вывести указатели на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изменять.

Решение задачи, на языке: Паскаль

Pointer47. Дано число $$K$$ $$(>0)$$ и указатель $$P_0$$ на один из элементов непустого двусвязного списка. Переместить в списке данный элемент на $$K$$ позиций назад (если перед данным элементом находится менее $$K$$ элементов, то переместить его в начало списка). Вывести указатели на первый и последний элементы преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изменять.

Решение задачи, на языке: Паскаль

Pointer48. Даны указатели $$P_X$$ и $$P_Y$$ на два различных элемента двусвязного списка (элемент с адресом $$P_X$$ находится в списке перед элементом с адресом $$P_Y$$, но не обязательно рядом с ним). Поменять местами данные элементы и вывести указатель на первый элемент преобразованного списка. Операции выделения и освобождения памяти не использовать, поля Data не изменять.

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

Pointer51. Даны два непустых двусвязных списка и связанные с ними указатели: $$P_A$$ и $$P_B$$ указывают на первый и последний элементы первого списка, $$P_C$$ — на один из элементов второго. Объединить исходные списки, поместив все элементы первого списка (в том же порядке) перед данным элементом второго списка, и вывести указатели на первый и последний элементы объединенного списка. Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer52. Даны два непустых двусвязных списка и связанные с ними указатели: $$P_A$$ и $$P_B$$ указывают на первый и последний элементы первого списка, $$P_C$$ — на один из элементов второго. Объединить исходные списки, поместив все элементы первого списка (в том же порядке) после данного элемента второго списка, и вывести указатели на первый и последний элементы объединенного списка. Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer53. Даны указатели $$P_X$$ и $$P_Y$$ на два различных элемента двусвязного списка; элемент с адресом $$P_X$$ находится в списке перед элементом с адресом $$P_Y$$, но не обязательно рядом с ним. Переместить элементы, расположенные между данными элементами (включая данные элементы) в новый список (в том же порядке). Вывести указатели на первые элементы преобразованного и нового списков. Если преобразованный список окажется пустым, то связанный с ним указатель положить равным $$nil$$. Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer54. Даны указатели $$P_X$$ и $$P_Y$$ на два различных элемента двусвязного списка; элемент с адресом $$P_X$$ находится в списке перед элементом с адресом $$P_Y$$, но не обязательно рядом с ним. Переместить элементы, расположенные между данными элементами (не включая данные элементы) в новый список (в том же порядке). Вывести указатели на первые элементы преобразованного и нового списков. Если новый список окажется пустым, то связанный с ним указатель положить равным $$nil$$. Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer55. Дан указатель $$P_1$$ на первый элемент непустого двусвязного списка. Преобразовать список в циклический, связав его последний элемент с помощью поля Next с первым, а первый элемент с помощью поля Prev — с последним, и вывести указатель на элемент, который был последним элементом исходного списка.

Решение задачи, на языке: Паскаль

Pointer56. Даны указатели $$P_1$$ и $$P_2$$ на первый и последний элементы непустого двусвязного списка, содержащего четное количество элементов. Преобразовать список в два циклических списка (см. задание Pointer55), первый из которых содержит первую половину элементов исходного списка, а второй — вторую половину. Вывести указатели $$P_A$$ и $$P_B$$ на два средних элемента исходного списка (элемент с адресом $$P_A$$ должен входить в первый циклический список, а элемент с адресом $$P_B$$ — во второй). Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer57. Дано число $$K$$ $$(>0)$$ и указатели $$P_1$$ и $$P_2$$ на первый и последний элементы непустого двусвязного списка. Осуществить циклический сдвиг элементов списка на $$K$$ позиций вперед (то есть в направлении от начала к концу списка) и вывести указатели на первый и последний элементы полученного списка. Для выполнения циклического сдвига преобразовать исходный список в циклический (см. задание Pointer55), после чего «разорвать» его в позиции, соответствующей данному значению $$K$$. Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer58. Дано число $$K$$ $$(>0)$$ и указатели $$P_1$$ и $$P_2$$ на первый и последний элементы непустого двусвязного списка. Осуществить циклический сдвиг элементов списка на $$K$$ позиций назад (то есть в направлении от конца к началу списка) и вывести указатели на первый и последний элементы полученного списка. Для выполнения циклического сдвига преобразовать исходный список в циклический (см. задание Pointer55), после чего «разорвать» его в позиции, соответствующей данному значению $$K$$. Операции выделения и освобождения памяти не использовать.

Решение задачи, на языке: Паскаль

Pointer59. Даны указатели $$P_1$$, $$P_2$$ и $$P_3$$ на первый, последний и текущий элементы двусвязного списка (если список является пустым, то $$P_1=P_2=P_3=nil$$). Также дано число $$N$$ $$(>0)$$ и набор из $$N$$ чисел. Описать тип TList — запись с полями First, Last и Current типа PNode (поля указывают соответственно на первый, последний и текущий элементы списка) — и процедуру InsertLast($$L$$, $$D$$), которая добавляет новый элемент со значением $$D$$ в конец списка $$L$$ ($$L$$ — входной и выходной параметр типа TList, $$D$$ — входной параметр целого типа). Добавленный элемент становится текущим. С помощью этой процедуры добавить в конец исходного списка данный набор чисел (в том же порядке) и вывести новые адреса его первого, последнего и текущего элементов.

Решение задачи, на языке: Паскаль

Pointer60. Даны указатели $$P_1$$, $$P_2$$ и $$P_3$$ на первый, последний и текущий элементы двусвязного списка (если список является пустым, то $$P_1=P_2=P_3=nil$$). Также дано число $$N$$ $$(>0)$$ и набор из $$N$$ чисел. Используя тип TList (см. задание Pointer59), описать процедуру InsertFirst($$L$$, $$D$$), которая добавляет новый элемент со значением $$D$$ в начало списка $$L$$ ($$L$$ — входной и выходной параметр типа TList, $$D$$ — входной параметр целого типа). Добавленный элемент становится текущим. С помощью этой процедуры добавить в начало исходного списка данный набор чисел (добавленные числа будут располагаться в списке в обратном порядке) и вывести новые адреса его первого, последнего и текущего элементов.

Решение задачи, на языке: Паскаль

Pointer61. Дан непустой двусвязный список, первый, последний и текущий элементы которого имеют адреса $$P_1$$, $$P_2$$ и $$P_3$$. Также даны пять чисел. Используя тип TList (см. задание Pointer59), описать процедуру InsertBefore($$L$$, $$D$$), которая вставляет новый элемент со значением $$D$$ перед текущим элементом списка $$L$$ ($$L$$ — входной и выходной параметр типа TList, $$D$$ — входной параметр целого типа). Вставленный элемент становится текущим. С помощью этой процедуры вставить пять данных чисел в исходный список и вывести новые адреса его первого, последнего и текущего элементов.

Решение задачи, на языке: Паскаль

Pointer62. Дан непустой двусвязный список, первый, последний и текущий элементы которого имеют адреса $$P_1$$, $$P_2$$ и $$P_3$$. Также даны пять чисел. Используя тип TList (см. задание Pointer59), описать процедуру InsertAfter($$L$$, $$D$$), которая вставляет новый элемент со значением $$D$$ после текущего элемента списка $$L$$ ($$L$$ — входной и выходной параметр типа TList, $$D$$ — входной параметр целого типа). Вставленный элемент становится текущим. С помощью этой процедуры вставить пять данных чисел в исходный список и вывести новые адреса его первого, последнего и текущего элементов.

Решение задачи, на языке: Паскаль

Pointer63. Дан непустой двусвязный список, первый, последний и текущий элементы которого имеют адреса $$P_1$$, $$P_2$$ и $$P_3$$. Используя тип TList (см. задание Pointer59), описать процедуры ToFirst($$L$$) (делает текущим первый элемент списка $$L$$), ToNext($$L$$) (делает текущим в списке $$L$$ следующий элемент, если он существует), SetData($$L$$, $$D$$) (присваивает текущему элементу списка $$L$$ значение $$D$$ целого типа) и функцию IsLast($$L$$) логического типа (возвращает True, если текущий элемент списка $$L$$ является его последним элементом, и False в противном случае). Параметр $$L$$ имеет тип TList; в процедурах ToFirst и ToNext он является входным и выходным. С помощью этих процедур и функций присвоить нулевые значения элементам исходного списка с нечетными номерами и вывести количество элементов в списке, а также новый адрес текущего элемента списка.

Решение задачи, на языке: Паскаль

Pointer64. Дан непустой двусвязный список, первый, последний и текущий элементы которого имеют адреса $$P_1$$, $$P_2$$ и $$P_3$$. Используя тип TList (см. задание Pointer59), описать процедуры ToLast($$L$$) (делает текущим последний элемент списка $$L$$), ToPrev($$L$$) (делает текущим в списке $$L$$ предыдущий элемент, если он существует) и функции GetData($$L$$) целого типа (возвращает значение текущего элемента списка $$L$$), IsFirst($$L$$) логического типа (возвращает True, если текущий элемент списка $$L$$ является его первым элементом, и False в противном случае). Параметр $$L$$ имеет тип TList; в процедурах ToLast и ToPrev он является входным и выходным. С помощью этих процедур и функций вывести все четные значения элементов исходного списка, просматривая список с конца. Вывести также количество элементов в списке.

Решение задачи, на языке: Паскаль

Pointer65. Даны указатели $$P_1$$, $$P_2$$ и $$P_3$$ на первый, последний и текущий элементы двусвязного списка, содержащего не менее пяти элементов. Используя тип TList (см. задание Pointer59), описать функцию DeleteCurrent($$L$$) целого типа, удаляющую из списка $$L$$ текущий элемент и возвращающую его значение ($$L$$ — входной и выходной параметр типа TList). После удаления элемента текущим становится следующий элемент или, если следующего элемента не существует, последний элемент списка. Функция также освобождает память, занимаемую удаленным элементом. С помощью этой функции удалить из исходного списка пять элементов и вывести их значения. Вывести также новые адреса первого, последнего и текущего элементов списка.

Решение задачи, на языке: Паскаль

Pointer66. Даны указатели $$P_1$$, $$P_2$$ и $$P_3$$ на первый, последний и текущий элементы непустого двусвязного списка. Используя тип TList (см. задание Pointer59), описать процедуру SpliTList($$L_1$$, $$L_2$$), которая переносит элементы списка $$L_1$$ от текущего до последнего в новый список $$L_2$$ (таким образом, список $$L_1$$ делится на две части, причем первая часть может оказаться пустой). Параметры процедуры имеют тип TList; первый параметр является входным и выходным, второй — выходным. Текущими элементами непустых результирующих списков становятся их первые элементы. Операции выделения и освобождения памяти в процедуре не использовать. С помощью этой процедуры разбить исходный список на два и вывести адреса первого, последнего и текущего элементов полученных списков.

Решение задачи, на языке: Паскаль

Pointer67. Даны указатели на первый, последний и текущий элементы двух непустых двусвязных списков. Используя тип TList (см. задание Pointer59), описать процедуру AddList($$L_1$$, $$L_2$$), которая добавляет все элементы из списка $$L_2$$ (в том же порядке) в конец списка $$L_1$$; в результате список $$L_2$$ становится пустым. Текущим элементом списка $$L_1$$ становится первый из добавленных элементов. Оба параметра процедуры имеют тип TList и являются входными и выходными. Операции выделения и освобождения памяти в процедуре не использовать. С помощью этой процедуры добавить второй из исходных списков в конец первого и вывести адреса первого, последнего и текущего элементов объединенного списка.

Решение задачи, на языке: Паскаль

Pointer68. Даны указатели на первый, последний и текущий элементы двух непустых двусвязных списков. Используя тип TList (см. задание Pointer59), описать процедуру InserTList($$L_1$$, $$L_2$$), которая вставляет все элементы из списка $$L_2$$ (в том же порядке) в список $$L_1$$ перед его текущим элементом; в результате список $$L_2$$ становится пустым. Текущим элементом списка $$L_1$$ становится первый из вставленных элементов. Оба параметра процедуры имеют тип TList и являются входными и выходными. Операции выделения и освобождения памяти в процедуре не использовать. С помощью этой процедуры вставить второй из исходных списков в текущую позицию первого и вывести адреса первого, последнего и текущего элементов объединенного списка.

Решение задачи, на языке: Паскаль

Pointer69. Даны указатели на первый, последний и текущий элементы двух двусвязных списков (второй список может быть пустым). Используя тип TList (см. задание Pointer59), описать процедуру MoveCurrent($$L_1$$, $$L_2$$), которая перемещает текущий элемент списка $$L_1$$ в список $$L_2$$ (элемент вставляется после текущего элемента списка $$L_2$$ и сам становится текущим; в списке $$L_1$$ текущим становится следующий элемент или, если следующего элемента не существует, последний элемент). Оба параметра процедуры имеют тип TList и являются входными и выходными. Операции выделения и освобождения памяти в процедуре не использовать. С помощью этой процедуры переместить текущий элемент первого списка во второй и вывести адреса первого, последнего и текущего элементов полученных спиcков.

Решение задачи, на языке: Паскаль

Использованная в заданиях Pointer31-Pointer69 реализация двусвязного списка в виде цепочки узлов, ограниченной по краям нулевыми указателями, не является единственно возможной. Двусвязный список можно также реализовать в виде замкнутой цепочки узлов с дополнительным фиктивным, или барьерным, элементом. Этот барьерный элемент связан своими полями Next и Prev с первым и последним элементом списка соответственно, поэтому, имея указатель на барьерный элемент, можно сразу перейти как к первому, так и к последнему элементу списка (естественно, первый и последний элементы также связаны с барьерным элементом своими полями Prev и Next соответственно). Для работы с двусвязным списком, снабженным барьерным элементом, достаточно хранить два указателя: Barrier, указывающий на барьерный элемент, и Current, указывающий на текущий элемент (который может быть как «настоящим», так и барьерным элементом). Поле Data барьерного элемента может быть произвольным; для определенности будем полагать его равным $$0$$. Пустой список в данный реализации представляет собой единственный барьерный элемент, «замкнутый на себя»; это означает, что для пустого списка поля Next и Prev барьерного элемента равны адресу барьерного элемента, то есть значению указателя Barrier. Задания Pointer70-Pointer80 посвящены двусвязным спискам с барьерным элементом.

Pointer70. Даны указатели $$P_1$$ и $$P_2$$ на первый и последний элементы двусвязного списка, реализованного в виде цепочки узлов, ограниченной по краям нулевыми указателями (если список пуст, то $$P_1=P_2=nil$$). Преобразовать исходный список в циклический список (см. задание Pointer55), снабженный барьерным элементом. Барьерный элемент должен иметь значение $$0$$ и быть связан своими полями Next и Prev с первым и последним элементом исходного списка (в случае пустого исходного списка поля Next и Prev барьерного элемента должны указывать на сам барьерный элемент). Вывести указатель на барьерный элемент полученного списка. Операцию выделения памяти использовать только для создания барьерного элемента.

Решение задачи, на языке: Паскаль

Pointer71. Даны указатели $$P_1$$ и $$P_2$$ на барьерный и текущий элементы двусвязного списка (о списке с барьерным элементом см. задание Pointer70). Разбить список на два, перенеся во второй список все элементы от текущего до последнего и добавив ко второму списку барьерный элемент. Если текущий элемент исходного списка является барьерным элементом, то второй список должен быть пустым (то есть состоять только из барьерного элемента). Вывести указатель на барьерный элемент второго списка. Операцию выделения памяти использовать только для создания барьерного элемента второго списка.

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

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

Решение задачи, на языке: Паскаль

Pointer74. Даны указатели $$P_1$$ и $$P_2$$ на барьерный и текущий элементы двусвязного списка (о списке с барьерным элементом см. задание Pointer70). Также дано число $$N$$ $$(>0)$$ и набор из $$N$$ чисел. Описать тип TListB — запись с полями Barrier и Current типа PNode (поля указывают соответственно на барьерный и текущий элементы списка) — и процедуру LBInsertLast($$L$$, $$D$$), которая добавляет новый элемент со значением $$D$$ в конец списка $$L$$ ($$L$$ — входной и выходной параметр типа TListB, $$D$$ — входной параметр целого типа). Добавленный элемент становится текущим. С помощью этой процедуры добавить в конец исходного списка данный набор чисел (в том же порядке) и вывести адрес текущего элемента полученного списка.

Решение задачи, на языке: Паскаль

Pointer75. Даны указатели $$P_1$$ и $$P_2$$ на барьерный и текущий элементы двусвязного списка. Также дано число $$N$$ $$(>0)$$ и набор из $$N$$ чисел. Используя тип TListB (см. задание Pointer74), описать процедуру LBInsertFirst($$L$$, $$D$$), которая добавляет новый элемент со значением $$D$$ в начало списка $$L$$ ($$L$$ — входной и выходной параметр типа TListB, $$D$$ — входной параметр целого типа). Добавленный элемент становится текущим. С помощью этой процедуры добавить в начало исходного списка данный набор чисел (добавленные числа будут располагаться в списке в обратном порядке) и вывести адрес текущего элемента полученного списка.

Решение задачи, на языке: Паскаль

Pointer76. Даны указатели $$P_1$$ и $$P_2$$ на барьерный и текущий элементы двусвязного списка. Также даны пять чисел. Используя тип TListB (см. задание Pointer74), описать процедуру LBInsertBefore($$L$$, $$D$$), которая вставляет новый элемент со значением $$D$$ перед текущим элементом списка $$L$$ ($$L$$ — входной и выходной параметр типа TListB, $$D$$ — входной параметр целого типа). Вставленный элемент становится текущим. С помощью этой процедуры вставить пять данных чисел в исходный список и вывести новый адрес его текущего элемента.

Решение задачи, на языке: Паскаль

Pointer77. Даны указатели $$P_1$$ и $$P_2$$ на барьерный и текущий элементы двусвязного списка. Также даны пять чисел. Используя тип TListB (см. задание Pointer74), описать процедуру LBInsertAfter($$L$$, $$D$$), которая вставляет новый элемент со значением $$D$$ после текущего элемента списка $$L$$ ($$L$$ — входной и выходной параметр типа TListB, $$D$$ — входной параметр целого типа). Вставленный элемент становится текущим. С помощью этой процедуры вставить пять данных чисел в исходный список и вывести новый адрес его текущего элемента.

Решение задачи, на языке: Паскаль

Pointer78. Даны указатели $$P_1$$ и $$P_2$$ на барьерный и текущий элементы двусвязного списка. Используя тип TListB (см. задание Pointer74), описать процедуры LBToFirst($$L$$) (делает текущим первый элемент списка $$L$$), LBToNext($$L$$) (делает текущим в списке $$L$$ следующий элемент), LBSetData($$L$$, $$D$$) (присваивает текущему элементу списка $$L$$ значение $$D$$ целого типа, если данный элемент не является барьерным) и функцию IsBarrier($$L$$) логического типа (возвращает True, если текущий элемент списка $$L$$ является его барьерным элементом, и False в противном случае). Параметр $$L$$ имеет тип TListB; в процедурах LBToFirst и LBToNext он является входным и выходным. С помощью этих процедур и функций присвоить нулевые значения элементам исходного списка с нечетными номерами и вывести количество элементов в списке, а также новый адрес текущего элемента списка. Барьерный элемент при подсчете элементов не учитывать.

Решение задачи, на языке: Паскаль

Pointer79. Даны указатели $$P_1$$ и $$P_2$$ на барьерный и текущий элементы двусвязного списка. Используя тип TListB (см. задание Pointer74), описать процедуры LBToLast($$L$$) (делает текущим последний элемент списка $$L$$), LBToPrev($$L$$) (делает текущим в списке $$L$$ предыдущий элемент) и функцию LBGetData($$L$$) целого типа (возвращает значение текущего элемента списка $$L$$). Параметр $$L$$ имеет тип TListB; в процедурах LBToLast и LBToPrev он является входным и выходным. С помощью этих процедур и функций, а также с использованием функции IsBarrier из задания Pointer78, вывести все четные значения элементов исходного списка, просматривая список с конца. Вывести также количество элементов в списке. Барьерный элемент при подсчете элементов не учитывать.

Решение задачи, на языке: Паскаль

Pointer80. Даны указатели $$P_1$$ и $$P_2$$ на барьерный и текущий элементы непустого двусвязного списка, причем текущий элемент не совпадает с барьерным.Используя тип TListB (см. задание Pointer74), описать функцию LBDeleteCurrent($$L$$) целого типа, удаляющую из списка $$L$$ текущий элемент и возвращающую его значение ($$L$$ — входной и выходной параметр типа TListB). Текущим становится следующий элемент или, если следующий элемент является барьерным, предыдущий элемент списка. Функция также освобождает память, занимаемую удаленным элементом. Если текущим элементом является барьерный элемент, то функция не выполняет никаких действий и возвращает $$0$$. С помощью этой функции, а также функции IsBarrier из задания Pointer78, удалить из исходного списка пять элементов (или все элементы, если их менее пяти) и вывести их значения. Вывести также новый адрес текущего элемента списка.

Решение задачи, на языке: Паскаль

 

Если вы хотите выложить решение для задач, но нет решения на нужном языке, или вообще к задаче нет решений. Можете разместить его в виде комментария к данной статье.

Другие задачи по программированию, для проверки своих знаний.