Д. Кнут - Искусство программирования том 1 (1119450), страница 100
Текст из файла (страница 100)
[24] (Обвяоления зкоиволгнгпносгли ) В некоторых компилируемых языках программирования, особенно в языке РОНТНАу1, предусмотрена возможность перекрытия ячеек памяти, которые выделены для таблиц, последовательно размещенных в памяти Программист предлагает компилятору набор отношений вида "Х[1] гя Т[й]", который означает, чго для переменной Х[1+ г] выделяется та же ячейка памяти, что и для переменной 1[А+ г] при всех г Кроме того, для каждой переменной определен диапазон допустимых индексов Например, 'АННАТ ХП и]" означает, что нужно выделить некоторую область памяти для элементов таблицы Х[(], Х[(+ 1], ..., Х[в3. Для каждого класса эквивалентности переменных компилятор резервирует минимально возможный блок последовательно расположенных ячеек ламяти, чтобы в нем люжно было хранить все элементы таблицы для допустимых значенйй индексов.
Например, предположим, что имеются таблицы АВВАТ Х [О: 103, АВВАТ Т [3: 103, АВИАТ АП:13 и АИИАТ 2[ — 2:0], а также пары эквивалентных элелзентов 1[73 = Т[33, 2[03 = А[03 и Т[1] = А[8]. Для этих переменных необходимо выделить 20 последовательных ячеек памяти: Хо Хз Хз Хз Х4 Хз Хв Хг Хв Хв Хзо ° ° ° ° ° ° ° ° ° ° ° ° ° Ф ° ° ° ° ° Ф 2-з 2-з Хо Аз Тз Тв 'Тв Тв Тг Тв Тв Тзо (Адрес расположенной за элементом А Ш ячейки памяти не соответствует ни одному диапазону допустимых значений индексов для любого массива, но эту ячейку все равно придется зарезервировать.) Назначение этого упражнения заключается в модификации алгоритма Е таким образом, чтобы его люжно было применять в более общем случае, который только что был описан.
Допустим, необходимо создать компилятор такого языка, а таблицы внутри самого компилятора имеют по одному узлу в каждом массиве с полямн ИАие, РАВемТ, ОеьтА, 1ЗО н ОВО. Допустим также. что компилятор предварительно обработал все объявления АВВАТ таким образом, что при наличии объявления "АИВАТ Х[(:и3" и Р, указывающего на узел Х, МАМЕ(Р) = "Х", РАВЕМТ(Р) = Л, ОЕ(.ТА(Р) = О, 1.80(Р) = (, ОВО(Р) = и, Задача заключается в создании алгоритма, который обрабатывал бы объявления эквивалентности так, чтобы после выполнения алгоритма получалось следующее: РАИЕМТ(Р) = Л означает, что ячейки палзяти ХП.ВО(Р)],...,Х[ОВО(Р)3 должны быть зарезервированы в памяти для этого класса эквивалентности; РАИЕМТ(Р) = О ф Л означает, что ячейка памяти Х[А] эквивалентна ячейке Т[)с + ОЕЕТА(РП, где МАМЕ(0) = "Т'.
Например, до обработки перечисленных выше пар эквивалентных элементов узлы могли выглядеть так. А после обработки онн могут иметь следующий вид. 14 Х Т А 2 4 0 — 3 (Здесь "*" обозначает данные, которые не имеют никакого отношения к рассматриваемой задаче.) Создайте алгоритм, который выполняет это преобразование.
Предположите, что данные из входного потока поступают в виде (Р,], О,)с), а это означает, что 'Х[]3 = Т[)в]', где МАМЕ(Р) = "Х" и МАМЕ(0) = "Т". Непременно убедитесь в том, что эти нары эквивалентных ИАИЕ (Р) Х Т А 2 РАВЕМТ(Р) Л Л Л Л ОЕЕТА(Р) 0 0 0 0 1.ВО(Р) 0 3 1 -2 ОВО(Р) 10 1О 1 0 отношений не противоречат одна другой. Например, 1[1) гя Т[2) будет противоречить 1[2) = Т[1].
1 1ИР01[э) ЕЪТИК[7) 1 2 3 4 5 б 7 8 А В С К Р Е Н Е 5 3 0 0 0 8 О 10 9 10 .У С 0 О к следующему виду: 1ИР02[)) В К С А Н Е .У Г С Р ОЕОЕЕЕ[Я 0 0 1 2 0 1 0 1 0 3 19. [М27] Вместо использования связей ЕСОРЕ в (5) можно было бы просто указать коли- чество наследников для каждого узла в прямом порядке; ОЕЯС 3 0 1 0 5 1 0 1 0 0 1ИРОА ВСКРЕНЕзС Пусть 01 Иг... ۄ— последовательность чисел, указывающих количество наследников для узлов одного леса, полученная таким образом. а) Покажите, что й+ Иь < п для 1 < 1 < п и что из 1 < ) < 1+ Аь следует )'+ 0, < й+ бы Ъ) И наоборот, докажите, что если Абэ... 0 является последовательностью неотрицательных целых чисел, которые удовлетворяют условиям (а), то она является пес "товательностью количеств узлов-наследников для данного леса.
12. [21] В начале алгоритма А церемонные Р и Ц указывают на корни двух деревьев. Пусть Ре и Цэ.— значения переменных Р и Ц до выполнения алгоритма А. (а) Всегда ли по завершении выполнения этого алгоритма Це будет содержа~в адрес корня дерева, представляющего результат суммирования двух заданных папиномов? (Ъ) Будут ли переменным Р и Ц возвращены нх исходные значения Ре и Ц„по окончании выполнения этого алгоритма? э 13.
[М20] Предложите неформальное доказательство того, что в алгоритме А и начале шага А8 всегда справедливы равенства ЕХР(Р) = ЕКР(Ц) и СТ(ОР(Р)) = СТЯР(Ц)). (Это очень важно для понимания принципа работы алгоритма.) 14. [40] Предложите формальное доказательство (или опровержение) справедливости алгоритма А. 15. [.(О] Создайте алгоритм для вычисления произведения двух полиномов, показанных на рис. 28.
16. [ЛЩ] Докажите корректность алгоритма Р. ь 17. [25] Алгоритм Р позволяет вычислить локально определенную функцию по направлению "снизу вверх", которая сначала вычисляется для детей некоторого узла, а затеяв и для самого узла, тогда как локально определенной функцией для узла х по направлению "сверху вниз" 7' называется функция, которая зависит только от узла х и значения функции У для родишеля узла ж С помощью вспомогательного стека создайте алгоритм, анююгичный алгоритму Е, который оценивает локально определенную функцию по направлению "сверху вниз" 7" для каждого узла этого дерева.
(Подобно алгоритму Г данный алгоритм должен эффективно обрабатывать деревья, которые хранятся в обратном порядке со степенями узлов, как в (9),) э 18. [28] Создайте алгоритм, который на основе двух таблиц 1ИР01[)) и ЕЪ1ИК[Я для 1 < ) < и, соогветствующих последовательному представлению в прямом порядке обхода, позволяет создать таблицы 1ИР02 [)) и ОЕОЕЕЕ[Я для 1 < э' < и, соответствующие последовательному представлению в обратном порядке обхода с указанием степеней. Например, согласно (3) и (9) этот алгоритм должен привести таблицы с) Предположим, что тттат...Ы„и 4ттт...ст"„— последовательности количеств узлов- наследников для двух лесов. Докажите, что существует третий лес с такой последовательностью количеств узлов-наследников: пил(4т, 4т) штп(4т,4т)... щтв(Ы„,И'„).
2.3.4. Основные математические свойства деревьев Древовидные структуры еще задолго до изобретения компьютеров были объектом обширных математических исследований, а потому в течение многих лет было накоплено большое количество интересных фактов об их свойствах. В настоящем разделе предложен краткий обзор математической теории деревьств, который позволяет не только глубже понять их природу, но и применить эти результаты на практике в компьютерных алгоритмах. Читателям, которым не интересна чисто математическая сторона обсуждаемых вопросов, рекомендуется сразу же перейти к подразделу 2.3.4.5, в котором с практической точки зрения рассматривается несколько вопросов, наиболее часто возникающих при использовании описываемых ниже приложений. Приведенный ниже материал, в основном, относится к большому разделу математики, а именно — к теории графов.
К сожалению, в этой области не существует устоявшейся терминологии, и автор придерживается обычной практики при написании современных книг по теории графов. Иначе говоря, здесь используются термины, аналогичные, но не идентичные тем терминам, которые применяются в других книгах по теории графов. В следующих подразделах (и далее во всей книге) будет предпринята попытка выбрать короткие, но емкие термины для наиболее важных понятий. Они будут выбраны среди общеупотребительных слов так, чтобы в то жс время они не противоречили общепринятой терминологии.
Следует учесть, что здесь эта терминология имеет непосредственное отношение к компьютерным приложениям. Поэтому инженер-электрик может назвать деревом то, что здесь называется свободным деревом, так как более краткий термин "дерево" обозначает более широкое понятие, которое часто используется в компьютерной литературе, а потому оно гораздо важнее в компьютерных приложениях. Если следовать терминологии, предлагаемой некоторыми авторами работ по теории графов, то следовало бы вместо термина "дерево" использовать термин "конечное упорядоченное дерево с указанным корнем", а вместо термина "бинарное дерево" — "топологическая раздвоенная древовидность'Чт 2.3.4.1.
Свободные деревья. Граф (дгартт) обычно определяется как множество точек (называемых вершинами (вегттсеэ)) вместе с набором линий (называемых ребрами (ет(дел)), которые соединяют определенные пары вершин. Каждая пара вершин соединяется не более чем одним ребром. Две вершины называются смежными (а4асеиг), если их соединяет ребро. Если И и )т' являются вершинами и и ) О, то (~ о, т'м..., тт„) называется путаем длины и от вершины 1т к вершине 1", если 'тт = )а, вершина 1тр, .является смежной для вершины )тг+т для О ( к < и, а 1т„= 1т'. Путь называется иростамм (гтпирте), если различны вершины Уе, Ъ~,..., $'„т и если различны вершины 1'ы...,1'„т,$'„. Граф называется связным (саииесге4), если существует путь между любыми двумя его вершинами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
