Динамические структуры данных

Данный раздел содержит описание варианта группы Dynamic, предназна-

ченного для языков программирования Pascal и C++.

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

Все указатели имеют тип PNode и указывают на записи типа TNode. Типы

PNode и TNode описаны в варианте задачника для языка Pascal следующим

образом:

type

PNode = ^TNode;

TNode = record

Data: integer;

Next: PNode;

Prev: PNode;

end;

Аналогично описываются эти типы в варианте задачника для языка С++:

struct TNode

{

int Data;

TNode* Next;

TNode* Prev;

};

typedef TNode* PNode;

Во вводных заданиях Dynamic1–Dynamic2, а также в заданиях на стек и

очередь (Dynamic3–Dynamic28) при работе с записями типа TNode использу-

ются только поля Data и Next (см. задание Dynamic1); в заданиях на списки

(Dynamic29–Dynamic80) используются все поля записи TNode (см. задание

Dynamic29).

Так как переменные типа «указатель» предназначены для хранения ад-

ресов, в формулировках заданий слова «указатель» (на элемент данных) и

«адрес» (элемента данных) используются как синонимы.

Динамические структуры данных

В заданиях, в которых идет речь о номерах элементов списка, предпола-

гается, что элементы списка нумеруются от 1.

Для обозначения нулевого указателя в формулировках заданий использу-

ется имя nil (как в языке Pascal).

Dynamic1. Дан адрес P1 записи типа TNode, содержащей поле Data (целого

типа) и поле Next (типа PNode — указателя на TNode). Эта запись связана

полем Next со следующей записью того же типа. Вывести значения полей

Data обеих записей, а также адрес P₂следующей записи.

Dynamic2◦. Дан адрес P1 записи типа TNode. Эта запись связана полем Next

со следующей записью того же типа, она, в свою очередь, — со следую-

щей, и так далее до записи, поле Next которой равно nil (таким образом,

возникает цепочка связанных записей). Вывести значения полей Data для

всех элементов цепочки, длину цепочки (то есть число ее элементов) и

адрес ее последнего элемента.

Стек

В заданиях Dynamic3–Dynamic13 структура «стек» (stack) моделируется

цепочкой связанных узлов-записей типа TNode (см. задание Dynamic2). Поле

Next последнего элемента цепочки равно nil. Вершиной стека (top) считается

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

вершину (для пустого стека данный указатель полагается равным nil). Значе-

нием элемента стека считается значение его поля Data.

Dynamic3◦. Дано число D и указатель P₁на вершину непустого стека. Доба-

вить элемент со значением D в стек и вывести адрес P₂новой вершины

стека.

Dynamic4. Дано число N (> 0) и набор из N чисел. Создать стек, содержа-

щий исходные числа (последнее число будет вершиной стека), и вывести

указатель на его вершину.

Dynamic5◦. Дан указатель P₁на вершину непустого стека. Извлечь из стека

первый (верхний) элемент и вывести его значение D, а также адрес P₂

новой вершины стека. Если после извлечения элемента стек окажется

пустым, то положить P₂= nil. После извлечения элемента из стека осво-

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

Dynamic6. Дан указатель P₁на вершину стека, содержащего не менее деся-

ти элементов. Извлечь из стека первые девять элементов и вывести их

118

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

значения. Вывести также адрес новой вершины стека. После извлечения

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

Dynamic7. Дан указатель P₁на вершину стека (если стек пуст, то P₁= nil).

Извлечь из стека все элементы и вывести их значения. Вывести также ко-

личество извлеченных элементов N (для пустого стека вывести 0). После

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

ли.

Dynamic8◦ . Даны указатели P₁и P₂на вершины двух непустых стеков. Пере-

местить все элементы из первого стека во второй (в результате элементы

первого стека будут располагаться во втором стеке в порядке, обратном

исходному) и вывести адрес новой вершины второго стека. Операции вы-

деления и освобождения памяти не использовать.

Dynamic9◦ . Даны указатели P₁и P₂на вершины двух непустых стеков. Пе-

ремещать элементы из первого стека во второй, пока значение вершины

первого стека не станет четным (перемещенные элементы первого стека

будут располагаться во втором стеке в порядке, обратном исходному). Ес-

ли в первом стеке нет элементов с четными значениями, то переместить

из первого стека во второй все элементы. Вывести адреса новых вершин

первого и второго стека (если первый стек окажется пустым, то вывести

для него константу nil). Операции выделения и освобождения памяти не

использовать.

Dynamic10◦ . Дан указатель P₁на вершину непустого стека. Создать два но-

вых стека, переместив в первый из них все элементы исходного стека

с четными значениями, а во второй — с нечетными (элементы в новых

стеках будут располагаться в порядке, обратном исходному; один из этих

стеков может оказаться пустым). Вывести адреса вершин полученных сте-

ков (для пустого стека вывести nil). Операции выделения и освобождения

памяти не использовать.

Dynamic11◦ . Дан указатель P₁на вершину стека (если стек пуст, то P₁= nil).

Также дано число N (> 0) и набор из N чисел. Описать тип TStack —

запись с одним полем Top типа PNode (поле указывает на вершину стека)

— и процедуру Push(S, D), которая добавляет в стек S новый элемент

со значением D (S — входной и выходной параметр типа TStack, D —

входной параметр целого типа). С помощью процедуры Push добавить

в исходный стек данный набор чисел (последнее число будет вершиной

стека) и вывести адрес новой вершины стека.

Динамические структуры данных

Dynamic12◦. Дан указатель P₁на вершину стека, содержащего не менее пяти

элементов. Используя тип TStack (см. задание Dynamic11), описать функ-

цию Pop(S) целого типа, которая извлекает из стека S первый (верхний)

элемент, возвращает его значение и освобождает память, которую занимал

извлеченный элемент (S — входной и выходной параметр типа TStack). С

помощью функции Pop извлечь из исходного стека пять элементов и выве-

сти их значения. Вывести также указатель на новую вершину стека (если

результирующий стек окажется пустым, то этот указатель должен быть

равен nil).

Dynamic13. Дан указатель P1 на вершину стека. Используя тип TStack (см.

задание Dynamic11), описать функции StackIsEmpty(S) логического типа

(возвращает TRUE, если стек S пуст, и FALSE в противном случае) и Peek(S)

целого типа (возвращает значение вершины непустого стека S, не удаляя

ее из стека). В обеих функциях переменная S является входным пара-

метром типа TStack. С помощью этих функций, а также функции Pop из

задания Dynamic12, извлечь из исходного стека пять элементов (или все

содержащиеся в нем элементы, если их менее пяти) и вывести их значе-

ния. Вывести также значение функции StackIsEmpty для результирующего

стека и, если результирующий стек не является пустым, значение и адрес

его новой вершины.

Очередь

В заданиях Dynamic14–Dynamic28 структура «очередь» (queue) модели-

руется цепочкой связанных узлов-записей типа TNode (см. задание Dynamic2).

Поле Next последнего элемента цепочки равно nil. Началом очереди («голо-

вой», head) считается первый элемент цепочки, концом («хвостом», tail) — ее

последний элемент. Для возможности быстрого добавления в конец очереди

нового элемента удобно хранить, помимо указателя на начало очереди, также

и указатель на ее конец. В случае пустой очереди указатели на ее начало и

конец полагаются равными nil. Как и для стека, значением элемента очереди

считается значение его поля Data.

Dynamic14. Дан набор из 10 чисел. Создать очередь, содержащую данные

числа в указанном порядке (первое число будет размещаться в начале

очереди, последнее — в конце), и вывести указатели P₁и P₂на начало и

конец очереди.

120

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

Dynamic15. Дан набор из 10 чисел. Создать две очереди: первая должна со-

держать числа из исходного набора с нечетными номерами (1, 3, . . ., 9), а

вторая — с четными (2, 4, . . ., 10); порядок чисел в каждой очереди дол-

жен совпадать с порядком чисел в исходном наборе. Вывести указатели

на начало и конец первой, а затем второй очереди.

Dynamic16. Дан набор из 10 чисел. Создать две очереди: первая должна со-

держать все нечетные, а вторая — все четные числа из исходного набора

(порядок чисел в каждой очереди должен совпадать с порядком чисел в

исходном наборе). Вывести указатели на начало и конец первой, а затем

второй очереди (одна из очередей может оказаться пустой; в этом случае

вывести для нее две константы nil).

Dynamic17. Дано число D и указатели P₁и P₂на начало и конец очереди

(если очередь является пустой, то P₁= P₂= nil). Добавить элемент со

значением D в конец очереди и вывести новые адреса начала и конца

очереди.

Dynamic18. Дано число D и указатели P₁и P₂на начало и конец очереди,

содержащей не менее двух элементов. Добавить элемент со значением D в

конец очереди и извлечь из очереди первый (начальный) элемент. Вывести

значение извлеченного элемента и новые адреса начала и конца очереди.

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

этим элементом.

Dynamic19. Дано число N (> 0) и указатели P₁и P₂на начало и конец непу-

стой очереди. Извлечь из очереди N начальных элементов и вывести их

значения (если очередь содержит менее N элементов, то извлечь все ее

элементы). Вывести также новые адреса начала и конца очереди (для

пустой очереди дважды вывести nil). После извлечения элементов из оче-

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

Dynamic20. Даны указатели P₁и P₂на начало и конец непустой очереди. Из-

влекать из очереди элементы, пока значение начального элемента очереди

не станет четным, и выводить значения извлеченных элементов (если

очередь не содержит элементов с четными значениями, то извлечь все

ее элементы). Вывести также новые адреса начала и конца очереди (для

пустой очереди дважды вывести nil). После извлечения элементов из оче-

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

Dynamic21. Даны две очереди; адреса начала и конца первой равны P₁и P₂,

а второй — P₃и P₄(если очередь является пустой, то соответствующие

Динамические структуры данных

адреса равны nil). Переместить все элементы первой очереди (в порядке

от начала к концу) в конец второй очереди и вывести новые адреса начала

и конца второй очереди. Операции выделения и освобождения памяти не

использовать.

Dynamic22. Дано число N (> 0) и две непустые очереди; адреса начала и

конца первой равны P₁и P₂, а второй — P₃и P₄. Переместить N на-

чальных элементов первой очереди в конец второй очереди. Если первая

очередь содержит менее N элементов, то переместить из первой очереди

во вторую все элементы. Вывести новые адреса начала и конца первой, а

затем второй очереди (для пустой очереди дважды вывести nil). Операции

выделения и освобождения памяти не использовать.

Dynamic23. Даны две непустые очереди; адреса начала и конца первой рав-

ны P₁и P₂, а второй — P₃и P₄. Перемещать элементы из начала первой

очереди в конец второй, пока значение начального элемента первой очере-

ди не станет четным (если первая очередь не содержит четных элементов,

то переместить из первой очереди во вторую все элементы). Вывести но-

вые адреса начала и конца первой, а затем второй очереди (для пустой

очереди дважды вывести nil). Операции выделения и освобождения па-

мяти не использовать.

Dynamic24. Даны две непустые очереди; адреса начала и конца первой рав-

ны P₁и P₂, а второй — P₃и P₄. Очереди содержат одинаковое количество

элементов. Объединить очереди в одну, в которой элементы исходных оче-

редей чередуются (начиная с первого элемента первой очереди). Вывести

указатели на начало и конец полученной очереди. Операции выделения и

освобождения памяти не использовать.

Dynamic25◦. Даны две непустые очереди; адреса начала и конца первой рав-

ны P₁и P₂, а второй — P₃и P₄. Элементы каждой из очередей упорядочены

по возрастанию (в направлении от начала очереди к концу). Объединить

очереди в одну с сохранением упорядоченности элементов. Вывести ука-

затели на начало и конец полученной очереди. Операции выделения и

освобождения памяти не использовать, поля Data не изменять.

Dynamic26. Даны указатели P1 и P2 на начало и конец очереди (если очередь

является пустой, то P1 = P2 = nil). Также дано число N (> 0) и набор

из N чисел. Описать тип TQueue — запись с двумя полями Head и Tail

типа PNode (поля указывают на начало и конец очереди) — и процедуру

Enqueue(Q, D), которая добавляет в конец очереди Q новый элемент со

122

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

значением D (Q — входной и выходной параметр типа TQueue, D — вход-

ной параметр целого типа). С помощью процедуры Enqueue добавить в

исходную очередь данный набор чисел и вывести новые адреса ее начала

и конца.

Dynamic27. Даны указатели P₁и P₂на начало и конец очереди, содержащей

не менее пяти элементов. Используя тип TQueue (см. задание Dynamic26),

описать функцию Dequeue(Q) целого типа, которая извлекает из очереди

первый (начальный) элемент, возвращает его значение и освобождает па-

мять, занимаемую извлеченным элементом (Q — входной и выходной па-

раметр типа TQueue). С помощью функции Dequeue извлечь из исходной

очереди пять начальных элементов и вывести их значения. Вывести также

адреса начала и конца результирующей очереди (если очередь окажется

пустой, то эти адреса должны быть равны nil).

Dynamic28. Даны указатели P₁и P₂на начало и конец очереди. Используя

тип TQueue (см. задание Dynamic26), описать функцию QueueIsEmpty(Q)

логического типа, которая возвращает TRUE, если очередь Q пуста, и FALSE

в противном случае (Q — входной параметр типа TQueue). Используя эту

функцию для проверки состояния очереди, а также функцию Dequeue из

задания Dynamic27, извлечь из исходной очереди пять начальных эле-

ментов (или все содержащиеся в ней элементы, если их менее пяти) и

вывести их значения. Вывести также значение функции QueueIsEmpty

для полученной очереди и новые адреса ее начала и конца.

Двусвязный список

Dynamic29. Дан адрес P₂записи типа TNode, содержащей поле Data (целого

типа) и поля Prev и Next (типа PNode — указателя на TNode). Эта запись

связана полями Prev и Next соответственно с предыдущей и последую-

щей записью того же типа. Вывести значения полей Data предыдущей и

последующей записи, а также адреса P₁и P₃предыдущей и последующей

записи.

Dynamic30◦ . Дан указатель P₁на начало непустой цепочки элементов-записей

типа TNode, связанных между собой с помощью поля Next. Используя по-

ле Prev записи TNode, преобразовать исходную (односвязную) цепочку в

двусвязную, в которой каждый элемент связан не только с последующим

элементом (с помощью поля Next), но и с предыдущим (с помощью поля

Prev). Поле Prev первого элемента положить равным nil. Вывести указа-

Динамические структуры данных

тель на последний элемент преобразованной цепочки.

В заданиях Dynamic31–Dynamic69 структура «двусвязный список» (doubly

linked list) моделируется цепочкой узлов-записей типа TNode, связанных как

с предыдущим, так и с последующим узлом (см. задание Dynamic30). Поле

Next последнего элемента цепочки и поле Prev первого элемента цепочки

равны nil. Для доступа к любому элементу двусвязного списка достаточно

иметь указатель на один из его элементов, однако для ускорения операций со

списком удобно хранить три указателя: на первый элемент списка (first), на его

последний элемент (last) и на текущий элемент (current). Для пустого списка

все эти указатели полагаются равными nil. Как в случае стека и очереди,

значением элемента списка считается значение его поля Data.

Dynamic31. Дан указатель P₀на один из элементов непустого двусвязного

списка. Вывести число N — количество элементов в списке, а также ука-

затели P₁и P₂на первый и последний элементы списка.

Dynamic32. Даны числа D₁и D₂и указатель P₀на один из элементов непу-

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

значением D₁, а в конец — новый элемент со значением D₂. Вывести

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

Dynamic33. Дано число D и указатель P₀на один из элементов непустого дву-

связного списка. Вставить перед данным элементом списка новый элемент

со значением D и вывести указатель на добавленный элемент списка.

Dynamic34. Дано число D и указатель P0 на один из элементов непустого дву-

связного списка. Вставить после данного элемента списка новый элемент

со значением D и вывести указатель на добавленный элемент списка.

Dynamic35. Даны указатели P₁и P₂на первый и последний элементы дву-

связного списка, содержащего не менее двух элементов. Продублировать

в списке первый и последний элементы (новые элементы добавлять перед

существующими элементами с такими же значениями) и вывести указа-

тель на первый элемент преобразованного списка.

Dynamic36. Даны указатели P₁и P₂на первый и последний элементы дву-

связного списка, содержащего не менее двух элементов. Продублировать

в списке первый и последний элементы (новые элементы добавлять после

существующих элементов с такими же значениями) и вывести указатель

на последний элемент преобразованного списка.

124

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

Dynamic37. Дан указатель P₁на первый элемент непустого двусвязного спис-

ка. Продублировать в списке все элементы с нечетными номерами (но-

вые элементы добавлять перед существующими элементами с такими же

значениями) и вывести указатель на первый элемент преобразованного

списка.

Dynamic38. Дан указатель P₁на первый элемент непустого двусвязного спис-

ка. Продублировать в списке все элементы с нечетными номерами (новые

элементы добавлять после существующих элементов с такими же зна-

чениями) и вывести указатель на последний элемент преобразованного

списка.

Dynamic39. Дан указатель P₁на первый элемент непустого двусвязного спис-

ка. Продублировать в списке все элементы с нечетными значениями (но-

вые элементы добавлять перед существующими элементами с такими же

значениями) и вывести указатель на первый элемент преобразованного

списка.

Dynamic40. Дан указатель P1 на первый элемент непустого двусвязного спис-

ка. Продублировать в списке все элементы с нечетными значениями (но-

вые элементы добавлять после существующих элементов с такими же

значениями) и вывести указатель на последний элемент преобразованно-

го списка.

Dynamic41. Дан указатель P₀на один из элементов непустого двусвязно-

го списка. Удалить из списка данный элемент и вывести два указателя:

на элемент, предшествующий удаленному, и на элемент, следующий за

удаленным (один или оба этих элемента могут отсутствовать; для отсут-

ствующих элементов выводить nil). После удаления элемента из списка

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

Dynamic42. Дан указатель P₁на первый элемент двусвязного списка, содержа-

щего не менее двух элементов. Удалить из списка все элементы с нечетны-

ми номерами и вывести указатель на первый элемент преобразованного

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

рую они занимали.

Dynamic43. Дан указатель P₁на первый элемент непустого двусвязного спис-

ка. Удалить из списка все элементы с нечетными значениями и вывести

указатель на первый элемент преобразованного списка (если в результате

удаления элементов список окажется пустым, то вывести nil). После уда-

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

Динамические структуры данных

Dynamic44. Дан указатель P₀на один из элементов непустого двусвязного

списка. Переместить данный элемент в конец списка и вывести указате-

ли на первый и последний элементы преобразованного списка. Операции

выделения и освобождения памяти не использовать, поля Data не изме-

нять.

Dynamic45. Дан указатель P₀на один из элементов непустого двусвязного

списка. Переместить данный элемент в начало списка и вывести указате-

ли на первый и последний элементы преобразованного списка. Операции

выделения и освобождения памяти не использовать, поля Data не изме-

нять.

Dynamic46. Дано число K (> 0) и указатель P₀на один из элементов непустого

двусвязного списка. Переместить в списке данный элемент на K позиций

вперед (если после данного элемента находится менее K элементов, то пе-

реместить его в конец списка). Вывести указатели на первый и последний

элементы преобразованного списка. Операции выделения и освобождения

памяти не использовать, поля Data не изменять.

Dynamic47. Дано число K (> 0) и указатель P₀на один из элементов непустого

двусвязного списка. Переместить в списке данный элемент на K позиций

назад (если перед данным элементом находится менее K элементов, то пе-

реместить его в начало списка). Вывести указатели на первый и последний

элементы преобразованного списка. Операции выделения и освобождения

памяти не использовать, поля Data не изменять.

Dynamic48. Даны указатели P_Xи P_Yна два различных элемента двусвязно-

го списка (элемент с адресом P_Xнаходится в списке перед элементом с

адресом P_Y, но не обязательно рядом с ним). Поменять местами данные

элементы и вывести указатель на первый элемент преобразованного спис-

ка. Операции выделения и освобождения памяти не использовать, поля

Data не изменять.

Dynamic49◦. Дан указатель P₁на первый элемент непустого двусвязного спис-

ка. Перегруппировать его элементы, переместив все элементы с нечетны-

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

первый элемент преобразованного списка. Операции выделения и осво-

бождения памяти не использовать, поля Data не изменять.

Dynamic50. Дан указатель P₁на первый элемент непустого двусвязного спис-

ка. Перегруппировать его элементы, переместив все элементы с нечетны-

ми значениями в конец списка (в том же порядке) и вывести указатель на

126

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

первый элемент преобразованного списка. Операции выделения и осво-

бождения памяти не использовать, поля Data не изменять.

Dynamic51. Даны два непустых двусвязных списка и связанные с ними ука-

затели: P1 и P2 указывают на первый и последний элементы первого

списка, P0 — на один из элементов второго. Объединить исходные списки,

поместив все элементы первого списка (в том же порядке) перед данным

элементом второго списка, и вывести указатели на первый и последний

элементы объединенного списка. Операции выделения и освобождения

памяти не использовать.

Dynamic52. Даны два непустых двусвязных списка и связанные с ними ука-

затели: P1 и P2 указывают на первый и последний элементы первого

списка, P0 — на один из элементов второго. Объединить исходные списки,

поместив все элементы первого списка (в том же порядке) после данного

элемента второго списка, и вывести указатели на первый и последний

элементы объединенного списка. Операции выделения и освобождения

памяти не использовать.

Dynamic53. Даны указатели P_Xи P_Yна два различных элемента двусвязно-

го списка; элемент с адресом PX находится в списке перед элементом с

адресом PY , но не обязательно рядом с ним. Переместить элементы, рас-

положенные между данными элементами (включая данные элементы), в

новый список (в том же порядке). Вывести указатели на первые элемен-

ты преобразованного и нового списков. Если преобразованный список

окажется пустым, то связанный с ним указатель положить равным nil.

Операции выделения и освобождения памяти не использовать.

Dynamic54. Даны указатели PX и PY на два различных элемента двусвязно-

го списка; элемент с адресом PX находится в списке перед элементом с

адресом P_Y, но не обязательно рядом с ним. Переместить элементы, рас-

положенные между данными элементами (не включая данные элементы),

в новый список (в том же порядке). Вывести указатели на первые эле-

менты преобразованного и нового списков. Если новый список окажется

пустым, то связанный с ним указатель положить равным nil. Операции

выделения и освобождения памяти не использовать.

Dynamic55◦ . Дан указатель P1 на первый элемент непустого двусвязного спис-

ка. Преобразовать список в циклический, записав в поле Next последнего

элемента списка адрес его первого элемента, а в поле Prev первого элемен-

та — адрес последнего элемента. Вывести указатель на элемент, который

Динамические структуры данных

был последним элементом исходного списка.

Dynamic56. Даны указатели P1 и P2 на первый и последний элементы непусто-

го двусвязного списка, содержащего четное количество элементов. Пре-

образовать список в два циклических списка (см. задание Dynamic55), пер-

вый из которых содержит первую половину элементов исходного списка,

а второй — вторую половину. Вывести указатели P₃и P₄на два средних

элемента исходного списка (элемент с адресом P₃должен входить в пер-

вый циклический список, а элемент с адресом P₄— во второй). Операции

выделения и освобождения памяти не использовать.

Dynamic57. Дано число K (> 0) и указатели P₁и P₂на первый и последний

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

элементов списка на K позиций вперед (то есть в направлении от начала

к концу списка) и вывести указатели на первый и последний элементы

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

исходный список в циклический (см. задание Dynamic55), после чего

«разорвать» его в позиции, соответствующей данному значению K. Опе-

рации выделения и освобождения памяти не использовать.

Dynamic58. Дано число K (> 0) и указатели P₁и P₂на первый и последний

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

элементов списка на K позиций назад (то есть в направлении от конца

к началу списка) и вывести указатели на первый и последний элемен-

ты полученного списка. Для выполнения циклического сдвига преобра-

зовать исходный список в циклический (см. задание Dynamic55), после

чего «разорвать» его в позиции, соответствующей данному значению K.

Операции выделения и освобождения памяти не использовать.

Dynamic59◦. Даны указатели P1 , P2 и P3 на первый, последний и теку-

щий элементы двусвязного списка (если список является пустым, то

P₁= P₂= P₃= nil). Также дано число N (> 0) и набор из N чисел. Описать

тип TList — запись с полями First, Last и Current типа PNode (поля указы-

вают соответственно на первый, последний и текущий элементы списка)

— и процедуру InsertLast(L, D), которая добавляет новый элемент со зна-

чением D в конец списка L (L — входной и выходной параметр типа TList,

D — входной параметр целого типа). Добавленный элемент становится

текущим. С помощью этой процедуры добавить в конец исходного спис-

ка данный набор чисел (в том же порядке) и вывести новые адреса его

первого, последнего и текущего элементов.

128

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

Dynamic60. Даны указатели P₁, P₂и P₃на первый, последний и теку-

щий элементы двусвязного списка (если список является пустым, то

P₁= P₂= P₃= nil). Также дано число N (> 0) и набор из N чисел. Исполь-

зуя тип TList (см. задание Dynamic59), описать процедуру InsertFirst(L, D),

которая добавляет новый элемент со значением D в начало списка L (L

— входной и выходной параметр типа TList, D — входной параметр це-

лого типа). Добавленный элемент становится текущим. С помощью этой

процедуры добавить в начало исходного списка данный набор чисел (до-

бавленные числа будут располагаться в списке в обратном порядке) и

вывести новые адреса его первого, последнего и текущего элементов.

Dynamic61. Дан непустой двусвязный список, первый, последний и теку-

щий элементы которого имеют адреса P₁, P₂и P₃. Также даны пять

чисел. Используя тип TList (см. задание Dynamic59), описать процеду-

ру InsertBefore(L, D), которая вставляет новый элемент со значением D

перед текущим элементом списка L (L — входной и выходной параметр

типа TList, D — входной параметр целого типа). Вставленный элемент

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

чисел в исходный список и вывести новые адреса его первого, последнего

и текущего элементов.

Dynamic62. Дан непустой двусвязный список, первый, последний и теку-

щий элементы которого имеют адреса P1, P2 и P3. Также даны пять чи-

сел. Используя тип TList (см. задание Dynamic59), описать процедуру

InsertAfter(L, D), которая вставляет новый элемент со значением D по-

сле текущего элемента списка L (L — входной и выходной параметр типа

TList, D — входной параметр целого типа). Вставленный элемент стано-

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

в исходный список и вывести новые адреса его первого, последнего и

текущего элементов.

Dynamic63◦ . Дан непустой двусвязный список, первый, последний и текущий

элементы которого имеют адреса P₁, P₂и P₃. Используя тип TList (см. за-

дание Dynamic59), описать процедуры ToFirst(L) (делает текущим первый

элемент списка L), ToNext(L) (делает текущим в списке L следующий эле-

мент, если он существует), SetData(L, D) (присваивает текущему элементу

списка L значение D целого типа) и функцию IsLast(L) логического типа

(возвращает TRUE, если текущий элемент списка L является его послед-

ним элементом, и FALSE в противном случае). Параметр L имеет тип TList;

Динамические структуры данных

в процедурах ToFirst и ToNext он является входным и выходным. С по-

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

исходного списка с нечетными номерами и вывести количество элемен-

тов в списке, а также новые адреса его первого, последнего и текущего

элементов.

Dynamic64. Дан непустой двусвязный список, первый, последний и теку-

щий элементы которого имеют адреса P₁, P₂и P₃. Используя тип TList

(см. задание Dynamic59), описать процедуры ToLast(L) (делает текущим

последний элемент списка L), ToPrev(L) (делает текущим в списке L пре-

дыдущий элемент, если он существует) и функции GetData(L) целого типа

(возвращает значение текущего элемента списка L), IsFirst(L) логическо-

го типа (возвращает TRUE, если текущий элемент списка L является его

первым элементом, и FALSE в противном случае). Параметр L имеет тип

TList; в процедурах ToLast и ToPrev он является входным и выходным.

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

ментов исходного списка, просматривая список с конца. Вывести также

количество элементов в списке.

Dynamic65. Даны указатели P₁, P₂и P₃на первый, последний и теку-

щий элементы двусвязного списка, содержащего не менее пяти элемен-

тов. Используя тип TList (см. задание Dynamic59), описать функцию

DeleteCurrent(L) целого типа, удаляющую из списка L текущий элемент

и возвращающую его значение (L — входной и выходной параметр типа

TList). После удаления элемента текущим становится следующий элемент

или, если следующего элемента не существует, последний элемент списка.

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

С помощью этой функции удалить из исходного списка пять элементов и

вывести их значения. Вывести также новые адреса первого, последнего

и текущего элементов списка (для пустого списка вывести три констан-

ты nil).

Dynamic66. Даны указатели P₁, P₂и P₃на первый, последний и текущий

элементы непустого двусвязного списка. Используя тип TList (см. зада-

ние Dynamic59), описать процедуру SplitList(L1, L2), которая переносит

элементы списка L1 от текущего до последнего в новый список L2 (таким

образом, список L₁делится на две части, причем первая часть может ока-

заться пустой). Параметры процедуры имеют тип TList; первый параметр

является входным и выходным, второй — выходным. Текущими элемен-

130

М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6

тами непустых результирующих списков становятся их первые элементы.

Операции выделения и освобождения памяти в процедуре не исполь-

зовать. С помощью этой процедуры разбить исходный список на два и

вывести адреса первого, последнего и текущего элементов полученных

списков.

Dynamic67. Даны указатели на первый, последний и текущий элементы

двух непустых двусвязных списков. Используя тип TList (см. задание

Dynamic59), описать процедуру AddList(L1, L2), которая добавляет все

элементы из списка L1 (в том же порядке) в конец списка L2 ; в результате

список L₁становится пустым. Текущим элементом списка L₂становится

первый из добавленных элементов. Оба параметра процедуры имеют тип

TList и являются входными и выходными. Операции выделения и освобо-

ждения памяти в процедуре не использовать. С помощью этой процедуры

добавить первый из исходных списков в конец второго и вывести адреса

первого, последнего и текущего элементов объединенного списка.

Dynamic68. Даны указатели на первый, последний и текущий элементы

двух непустых двусвязных списков. Используя тип TList (см. задание

Dynamic59), описать процедуру InsertList(L₁, L₂), которая вставляет все

элементы из списка L₁(в том же порядке) в список L₂перед его текущим

элементом; в результате список L1 становится пустым. Текущим элемен-

том списка L2 становится первый из вставленных элементов. Оба пара-

метра процедуры имеют тип TList и являются входными и выходными.

Операции выделения и освобождения памяти в процедуре не использо-

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

в текущую позицию второго и вывести адреса первого, последнего и те-

кущего элементов объединенного списка.

Dynamic69. Даны указатели на первый, последний и текущий элементы двух

двусвязных списков (второй список может быть пустым). Используя тип

TList (см. задание Dynamic59), описать процедуру MoveCurrent(L₁, L₂),

которая перемещает текущий элемент списка L₁в список L₂(элемент

вставляется после текущего элемента списка L₂и сам становится теку-

щим; в списке L1 текущим становится следующий элемент или, если

следующего элемента не существует, последний элемент). Оба параметра

процедуры имеют тип TList и являются входными и выходными. Опера-

ции выделения и освобождения памяти в процедуре не использовать. С

помощью этой процедуры переместить текущий элемент первого списка

Динамические структуры данных

во второй и вывести адреса первого, последнего и текущего элементов

полученных списков.