М.Э. Абрамян - Programming Taskbook, страница 25

Вывести также адрес новой вершины стека. После извлеченияэлементов из стека освобождать память, которую они занимали.Dynamic7. Дан указатель P1 на вершину стека (если стек пуст, то P1 = nil).Извлечь из стека все элементы и вывести их значения. Вывести также количество извлеченных элементов N (для пустого стека вывести 0). Послеизвлечения элементов из стека освобождать память, которую они занимали.Dynamic8◦ . Даны указатели P1 и P2 на вершины двух непустых стеков. Переместить все элементы из первого стека во второй (в результате элементыпервого стека будут располагаться во втором стеке в порядке, обратномисходному) и вывести адрес новой вершины второго стека. Операции выделения и освобождения памяти не использовать.Dynamic9◦ . Даны указатели P1 и P2 на вершины двух непустых стеков.

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

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

С помощью процедуры Push добавитьв исходный стек данный набор чисел (последнее число будет вершинойстека) и вывести адрес новой вершины стека.Динамические структуры данных119Dynamic12◦ . Дан указатель P1 на вершину стека, содержащего не менее пятиэлементов. Используя тип 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 чисел. Создать очередь, содержащую данныечисла в указанном порядке (первое число будет размещаться в началеочереди, последнее — в конце), и вывести указатели P1 и P2 на начало иконец очереди.120М.

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

Вывести указатели на начало и конец первой, а затемвторой очереди (одна из очередей может оказаться пустой; в этом случаевывести для нее две константы nil).Dynamic17. Дано число D и указатели P1 и P2 на начало и конец очереди(если очередь является пустой, то P1 = P2 = nil). Добавить элемент созначением D в конец очереди и вывести новые адреса начала и концаочереди.Dynamic18. Дано число D и указатели P1 и P2 на начало и конец очереди,содержащей не менее двух элементов. Добавить элемент со значением D вконец очереди и извлечь из очереди первый (начальный) элемент.

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

Извлекать из очереди элементы, пока значение начального элемента очередине станет четным, и выводить значения извлеченных элементов (еслиочередь не содержит элементов с четными значениями, то извлечь всеее элементы). Вывести также новые адреса начала и конца очереди (дляпустой очереди дважды вывести nil). После извлечения элементов из очереди освобождать память, которую они занимали.Dynamic21. Даны две очереди; адреса начала и конца первой равны P1 и P2 ,а второй — P3 и P4 (если очередь является пустой, то соответствующиеДинамические структуры данных121адреса равны nil). Переместить все элементы первой очереди (в порядкеот начала к концу) в конец второй очереди и вывести новые адреса началаи конца второй очереди. Операции выделения и освобождения памяти неиспользовать.Dynamic22.

Дано число N (> 0) и две непустые очереди; адреса начала иконца первой равны P1 и P2 , а второй — P3 и P4 . Переместить N начальных элементов первой очереди в конец второй очереди. Если перваяочередь содержит менее N элементов, то переместить из первой очередиво вторую все элементы. Вывести новые адреса начала и конца первой, азатем второй очереди (для пустой очереди дважды вывести nil). Операциивыделения и освобождения памяти не использовать.Dynamic23. Даны две непустые очереди; адреса начала и конца первой равны P1 и P2 , а второй — P3 и P4 .

Перемещать элементы из начала первойочереди в конец второй, пока значение начального элемента первой очереди не станет четным (если первая очередь не содержит четных элементов,то переместить из первой очереди во вторую все элементы). Вывести новые адреса начала и конца первой, а затем второй очереди (для пустойочереди дважды вывести nil). Операции выделения и освобождения памяти не использовать.Dynamic24. Даны две непустые очереди; адреса начала и конца первой равны P1 и P2 , а второй — P3 и P4 . Очереди содержат одинаковое количествоэлементов.

Объединить очереди в одну, в которой элементы исходных очередей чередуются (начиная с первого элемента первой очереди). Вывестиуказатели на начало и конец полученной очереди. Операции выделения иосвобождения памяти не использовать.Dynamic25◦ . Даны две непустые очереди; адреса начала и конца первой равны P1 и P2 , а второй — P3 и P4 . Элементы каждой из очередей упорядоченыпо возрастанию (в направлении от начала очереди к концу). Объединитьочереди в одну с сохранением упорядоченности элементов. Вывести указатели на начало и конец полученной очереди.

Операции выделения иосвобождения памяти не использовать, поля 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. Даны указатели P1 и P2 на начало и конец очереди, содержащейне менее пяти элементов. Используя тип TQueue (см. задание Dynamic26),описать функцию Dequeue(Q) целого типа, которая извлекает из очередипервый (начальный) элемент, возвращает его значение и освобождает память, занимаемую извлеченным элементом (Q — входной и выходной параметр типа TQueue). С помощью функции Dequeue извлечь из исходнойочереди пять начальных элементов и вывести их значения. Вывести такжеадреса начала и конца результирующей очереди (если очередь окажетсяпустой, то эти адреса должны быть равны nil).Dynamic28. Даны указатели P1 и P2 на начало и конец очереди. Используятип TQueue (см. задание Dynamic26), описать функцию QueueIsEmpty(Q)логического типа, которая возвращает TRUE, если очередь Q пуста, и FALSEв противном случае (Q — входной параметр типа TQueue).