Структуры данных и алгоритмы (1021739), страница 19
Текст из файла (страница 19)
Данныйi=iсписок, в свою очередь, представим как связанный список ячеек типа celltype,определенного выше. Напишите процедуру increment(bnumber), которая прибавляет 1 к двоичному числу bnumber. Совет: сделайте процедуру incrementрекурсивной.Напишите процедуру обмена элементами в позициях р H.NEXT(p) для простогосвязанного списка.Следующая процедура предназначена для удаления всех вхождений элементах в списке L.
Найдите причину, по которой эта процедура будет выполнятьсяне всегда, и устраните ее.procedure delete ( х: elementtype; var L: LIST };varp: position;beginp: = FIRST (i);while p <> END(L) do beginif RETRIEVE(p, L) = x thenDELETE (p, L} ;p: = NEXT(p, L)endend; { delete }2.10. Необходимо сохранить список в массиве А, чьи ячейки содержат два поля:data — для элементов и поле position — для позиций (целых чисел) элементов.Целочисленная переменная last (последний) используется для указания того,что список содержится в ячейках от А[1] до A[last] массива А. Тип LIST определен следующим образом:typeLIST = recordlast: integer;elements: array[1..maxlength] of recorddata: elementtype;position: integer;endend;Напишите процедуру DELETE(p, L) для удаления элемента в позиции р.
Включите в процедуру все необходимые проверки на "внештатные" ситуации.2.11. Пусть L — это список типа LIST, p, q и г — позиции. Определите как функцию от п (длины списка L) количество выполнений функций FIRST, END иNEXT в следующей программеУПРАЖНЕНИЯ732.12.2.13.2.14.2.15.2.16.2.17.2.18.2.19.2.20.2.21.74p: = FIRST(L);while p <> END(L) do begin<?:= P;while gr <> END(L) do beging:= NEXT(g, L) ;r:= FIRST(1);while r <> q dor:= NEXTfr, L)end;p:= NEXT(p, L)end;Перепишите код операторов, выполняемых над списками LIST, в предположении, что реализуются однонаправленные списки.Добавьте необходимые проверки на ошибки в процедуры листинга 2.6.Еще одна реализация списков посредством массивов совпадает с описанной вразделе 2.2 за исключением того, что при удалении элемента он заменяетсязначением "удален", которое другим способом в списке появиться не может.Перепишите операторы списка для этой реализации.
Какие достоинства и недостатки этой реализации списков по сравнению с исходной?Предположим, что мы хотим использовать логическую переменную при реализации очереди для указания того, что очередь пуста. Измените объявления иоператоры в реализации очередей Посредством циклических массивов для использования этой переменной. Что можно ожидать от такой рационализации?Очередь с двусторонним доступом — это список, в котором добавлять и удалять элементы можно с обоих концов. Разработайте реализации для такихочередей с использованием массивов, указателей и курсоров.Определите АТД, поддерживающие операторы ENQUEUE, DEQUEUE (см. раздел 2.4) и ONQUEUE. ONQUEUE(or) — функция, возвращающая значения trueили false в зависимости от того, присутствует или нет элемент х в очереди.Как реализовать очередь, если элементами являются символьные строки произвольной длины? Сколько времени необходимо для операции вставки такогоэлемента в очередь?В одной возможной реализации очередей посредством связанных списков неиспользуется ячейка заголовка, а указатель front указывает непосредственнона первую ячейку.
Если очередь пуста, тогда front = rear = nil. Напишите необходимые операторы для этой реализации очередей. Сравните эту реализациюс реализацией, описанной в разделе 2.4, по критериям времени выполнения,требуемого объема памяти и лаконичности (краткости и понятности) кода.В одном варианте реализации очередей посредством циклических массивов записываются позиция первого элемента и длина очереди.а) необходимо ли в этой реализации ограничивать длину очереди числомmaxlength - 1?б) напишите пять операторов, выполняемых над очередями, для этой реализации;в) сравните эту реализацию с реализацией посредством циклических массивов, описанной в разделе 2.4.Возможно хранение двух стеков в одном массиве, если один располагается вначале массива и растет к концу массива, а второй располагается в конце массива и растет к началу.
Напишите процедуру PUSH(x, S) вставки элемента х встек S, где S — один или другой стек из этих двух стеков. Включите все необходимые проверки в эту процедуру.ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХ2.22. Можно хранить k стеков в одном массиве, если используется структура данных, показанная на рис.
2.12 для случая k = 3. В этом случае можно организовать вставку и удаление элементов для каждого стека так же, как описано вразделе 2.3. Но если случится, что при вставке элемента в стек i вершинаTOP(i) совпадет с "дном" предыдущего стека BOTTOM(i-l), то возникает необходимость переместить все стеки так, чтобы между каждой парой смежныхстеков был зазор из пустых ячеек массива. В этом случае мы можем сделатьвсе зазоры одинаковыми или пропорциональными длине соседнего с зазоромстека (из теории следует: чем больше стек, тем вероятнее в ближайшем будущем его рост, а мы, естественно, хотим отсрочить следующую реорганизациюмассива).а) в предположении, что есть процедура reorganize (реорганизация), вызываемаяпри возникновении "конфликтов" между стеками, напишите код для пятиоператоров стека;б) напишите процедуру reorganize в предположении, что уже существует процедура makenewtops (сделать новые вершины), которая вычисляет neu>top[i], —новую позицию вершины стека i для всех i, I < i < k.
Совет: отметим, чтостек i может перемещаться как вверх, так и вниз по массиву. Если новая позиция стека / захватывает старую позицию стека i, то стек i надо переместитьраньше стека /. Рассматривая стеки в порядке 1, 2, ..., k, создадим еще стек"целей", каждая "цель" будет перемещать отдельный конкретный стек. Еслистек i можно безопасно переместить, то перемещение выполняется и повторнорассматривается стек, чей номер находится в вершине стека целей. Если стекi нельзя переместить, не затрагивая других стеков, то его номер помещается встек целей;в) какая подходящая реализация для стека целей? Необходимо ли для этого использовать список из целых чисел или можно воспользоваться более простойреализацией?г) реализуйте процедуру makenewtops так, чтобы пространство перед каждымстеком было пропорционально его текущей длине;д) какие изменения надо сделать в схеме рис.
2.12, чтобы ее можно было применить для очередей? А для произвольных списков?вершинымассивРис. 2.12. Расположение нескольких стеков в одном массиве2.23. Измените реализации операторов POP и ENQUEUE из разделов 2.3 и 2.4 так,чтобы они возвращали элементы, удаленные соответственно из стека и очере-УПРАЖНЕНИЯ75ди. Что необходимо сделать, если элемент имеет тип данных, который функция не может вернуть?2.24. Используйте стек для исключения рекурсивных вызовов из следующих процедур:•а)function comb ( п, т: integer ): integer;{вычисление биномиальных коэффициентов С™ при 0<m<n и п>1}beginif (n = 1) or (т = 0) or (т = л) thenreturn(1)elsereturn(comb(n - 1, m) + comb(л - 1, т - 1))end; { comb }6)procedure reverse ( var L: LIST );{ о_бращение списка L }varx: elementtype;beginif not EMPTY(i) then beginx: = RETRIEVE(FIRST(£), L) ;DELETE (FIRST (L) , L) ;reverse(L);INSERT(x, END(L), L)iendend; { reverse }*2.25. Можно ли исключить последние рекурсивные вызовы из программ примера2.24? Если можно, то как?Библиографические примечанияКнига [63] содержит дополнительный материал по реализациям списков, стеков иочередей.
Многие языки программирования, например LISP и SNOBOL, поддерживают списки в удобной форме. См. работы [80], [86], [94] и [117], содержащие исторические справки и описания таких языков.76ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХГЛАВА 3ДеревьяДеревья представляют собой иерархическую структуру некой совокупности элементов.Знакомыми вам примерами деревьев могут служить генеалогические и организационные диаграммы. Деревья используются при анализе электрических цепей, при представлении структур математических формул. Они также естественным путем возникают во многих областях компьютерных наук. Например, деревья используются для организации информации в системах управления базами данных и для представлениясинтаксических структур в компиляторах программ.
В главе 5 описано применение деревьев для представления данных. В этой книге вы встретитесь со многими примерамидеревьев. В этой главе мы введем основные определения (терминологию) и представимосновные операторы, выполняемые над деревьями. Затем опишем некоторые наиболеечасто используемые структуры данных, представляющих деревья, и покажем, какнаиболее эффективно реализовать операторы деревьев.3.1. Основная терминологияДерево — это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений ("родительских"), образующих иерархическуюструктуру узлов.
Узлы, так же, как и элементы списков, могут быть элементами любого типа. Мы часто будем изображать узлы буквами, строками или числами. Формально дерево можно рекуррентно определить следующим образом.1.2.Один узел является деревом. Этот же узел также является корнем этого дерева.Пусть п — это узел, а Т\, Т2Tk — деревья с корнями п\, п2, ..., п/, соответственно. Можно построить новое дерево, сделав га родителем узлов пь гаг, ..., nk.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
