Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 53
Текст из файла (страница 53)
бы процедура (4.63) выполняла каждое из четырех действий балан. снровки (!(., )?)?, йь, Ы)?) по крайней мере один раз. Какова мннчмальиая длина и такой последовательности? 4.21. Найдите сбалансированное дерево с ключами 1 ... л и перестановку этих ключей, таяне, чтобы прп работе процедуры удаления (4.64) опа выполняла каждую из четырех подпрограмм балансировки по крайней мере один раз, Какова последовательность с минимальной длиной и? 4.22. Какова средина длина пути в дереве Фибопаччи Т,? Упражнения 817 4.23. Напишите программу, которая форма)г>сг дсрчзо, близкое к оппы мальиому в соответствии с алгоритмом, основанным па сыборе цеитройда в качестве корин (4.78].
4.24. Прелположим, что ключи 1, 2, 3 ... вставляются в п>стас Б-дерево порядка 2 (програмяв 4.7). Какие;лючи вызывают расщепление страниц? Какие ключи вызывают увеличешю высоты дерева? Если ключи удалвются в ~ом же порядке, то какие ключи вызывают слияние (и освобождение) страниц и какие кл>очи вызывают уменьшение высоты? Ответьте па этот вопрос для сл>чаев (а) схемы удаления, использующей балансировку (как в программе 4.7), и (8) схемы без балансировки (прк недостаче берется один элемент с соседней страницы) 4.23.
Напишите прогрзьыгу поиска, включения и удаления ктючей в бинарном Б-дереве. Используйте определение типа узла (4.84). Схема включения показана ва рис. 4.51. 4.26. Найдите последовательность вставляемых ключей, которая, начипая с пустого симметричного бинарного Б-дерева, заставляет процедуру (4 87) выполнить все четыре действия балансировки ((.(., )?)?, Щ Я(.) по крайней мере одии раз. Какова самая короткая последовательность? 4.27. Напишите процедуру удалении элементов в симметричном бинарном Б-дереве.
Затем найдите дерево и коротк>ю последовательность удалений, вызывагощую появление всех четырех ситуаций балансировки хотя бы по одному разу. 4.28. Сравните работу алгоритма включения и удаления для бинарных деревьев, АВЗБсбалаисироваииых деревьев и для симметричных бинарных Б-деревьев на вычислительной машине. В частности, исследуйте влияние упаковки данных, т. е. зкоиомяого представления данных с использованием только двух разрядов для хранения информация о сбалаисзроззниости каждого узла. 4.29. Модифпцируйте алгоритм печати в программе 4.6 таким образом, чтобы его можно было зспальзовать для изображения симметричных бинарных Б-деревьев с горизонтальными и вертикальными ветвями. 4.30. Если количество ииформацяи, связанной с каждым ключом, относчтельяо велико (по сраввеишо с самим ключом), зту информацию пе рекомендуется помещать в рассеянную таблицу.
Объясните почему и предложите схему для представления такого миозксства данных. 4.31. Рассмотрите предложения о решении проблемы скопления с помощью деревьев переполиеиия вместо списков переполкеиия, т. е оргазиза. ции тех кл>очей, которые вступают в кояфлякт, в аиде дерева.
Следовательно, каждый вход в рассеянную таблицу можно рассматривать как корень (возможио, пустого) дерева (древовидная расстановка). 4.32. Предложите схему выполнения вклгочеиий и удалений в рассеянной таблице с использованием квадратичных приращений для разрешения конфликтов. Сравните эксперямеитальио зту схему с простой оргзиизац >ей бинарного дерева, задавая случайные последовательности ключей для включения и удаления.
4.33. Основной недостаток метода расстановки состоит в том, что размер таблицы догпкеи быть фиксированным, тогда как число элементов веизвестно. Предположим, что ваша вычислительная система содержит механизм динамического распределения памяти, который позволяет в любой момент выделять память.
Следовательио, когда рассеянная 3!8 4, Динамические информационные структуры таблица П заполнена (или почти зааолнена), то формируется ббльшан таблица Н', и все ключи нз Н пересылаются в Н', после чего память, запятаи Н, возвращается в распоряжение системй. Этот процесс можно назвать повторной расстановкой. Напишите программу, нагорая выполняет повторную расстановку для таблицы П размером и. 4.34, Очень часто ключи являются ие целыми числами, а последовательностями букв. Эти слона могут сильно различатьсн по длине и позтому не могут удобно и зкономво размещаться в полив фиксированного размера. Напишите программу, нагорав работает с рассеянной таолицей н ключами неременногт длани. ЛИТЕРАТУРА 4.1.
Адсльсон-Вельский Г. М., Лавдис Е, М. Один алгоритм организации информации, — 27оклады АН СССР, 14, 1962, с. 263 — 266. 4.2. ВАТЕК К., МсСКЕ16НТ Е. Огбап!га1юп апб Ма!п1епапсе о1 Еагбе г)гбегеб 1пбехез. — Ас1а 1пгогтайса, 1, Хо. 3, 1972, Г73 — 189.
4.3. ВАУЕК й. В!пату В-1геез 1ог ТГ!г)па! Метогу.— Ргос. 1971 АСМ 516Р)НЕТ бтог)ге!гор, бап В!ебо, Хоч. 1971, 219 — 235. 4.4. ВЛТЕй й. 5уппне1г!с В!лагу В !геев; Ва1а Ягпс1пге апд Ма!о1епапсе А!Кот!!Ешз. — Ас1а 1пгогтайса, 1, Но, 4, 1972, 290 — 306. 4.6. НЬ Т. С., Т1)СКЕК А. С.— 3!АМ 1.
Аррйед Майи 21, Но. 4, 1971, Ы4 — 532. 4.6. КНОТН О. Е. Ор)ппшп В!пату 5еагсб Тгеез.— Асга 1н)огнгайса, 1, Хо. 1, 1971, !4 — 25. 4.7. МАШ1ЕК %. В. Ап 1шргочеб Назб Собс 1ог 5са1!ег ЯогаКе. — Сотт. АСМ, 11, 1968, Но. 1, 35 — 38. 4.8. МОКГН5 К. 5сайег 5!огаКе Тесбп!цпез. — Сотт, АСМ, 11, Хо 1, 1968, 38 — 43. 4.9.
РЕТЕК56!Ч %. %. АббгезюпК 1ог йапбош-ассеш Яогабе.— !ВМ 1. Кез, анд Рео., 1, 1957, 130 — 146. 4,10, 5СНАТ 6., БРАТ)ТН %. Апа!уюз о1 а Г11е Аббгеззшб Ме)боб.— Сотт. АСМ, 5, Но. 8, 1962, 459 — 462. 4.11. %А1.КЕй %, Л., 60ТЕ!ЕВ С. С. А Тор-боып А!бог!Поп 1ог Сопз1гнс- 1!пп Неаг)у Орйша1 Еек!содгарб!с Тгеез.
— беаром Гбеогу апд Сотрийпу, Хеы Тогу. Асабеш!с Ргеш, 1972, рр. 303 — 323. СТРУКТУРА ЯЗЫКОВ И ТРАНСЛЯТОРЫ В этой главе мы постараемся разработать транслятор для простого, «рудиментарного» языка программирования. Такая разработка может послужить примером систематического, хорошо структурированного подхода при написании программы нетривиальной сложности и размера. При этом можно продемонстрировать практическое применение методов, рассчотреипых в предыдущих главах, Кроме того, мы постараемся дать общее представление о структуре трансляторов и принципах их работы. Знание этого предмета позволит лучше разобраться в искусстве программирования на языках высокого уровня, а также облегчит программисту разработку собственных систем, предназначенных для конкретных целей и областей применения.
Но, поскольку, как известно, теория трансляторов — сложный и обшнрнын предмет, в этом отношении данная глава будет носить лишь вводный н обзорный характер. По-видимомч, главное, что следует уяснить,— это что структура транслятора отражает структуру языка и сложи алеть — или простота — языка решающим образом влияет на с,шжность его транслятора. Поэтому мы начнем с описания строения языка, а затсм сосредоточим внимание исключительно на простых структурах, для которых можно построить простые, модульные трансляторы. Такие простые языковые конструкции оказываются достаточнымп для удовлетворения практически всех потребностей, возникающих при использовании языков программирования. ТЛ.
ОПРЕДЕПЕИИЕ И СТРУКТУРА ЯЗЫКА В основе каждого языка лежит словарь. Вго элементы обычно называют словами, но в теории формальных языков их называют символами. Языки характеризуются тем, что некоторые последовательности слов считаются правильными предложениями языка, а другие — неправильными, или пе принадлежащими данному языку. Чем же определяется, является ли некоторая последовательность слов правильным предложением? Обычно это определяется грамматикой, синтаксисом (можно сказать — структурой) языка. Синтаксис б. Структура языков и трансляторы определяется как множество правил или формул, которые задают множество (формально правильных) предложений.
Такое множество синтаксических правил не только позволяет установить, принадлежит лп некоторая заданная последовательность слов множеству предпожений языка, но при этом определяет структуру предложения, которая устанавливает его смысл. Поэтому ясно, что синтаксис и семантика (=смысл) тесно св..заны между собой. Следовательно, определения, связанные со структурой, всегда следует рассма>- ривать как средство распознавания смысла. Но это не помешает нам изучить вначале исключительно структурные аспекты языка, отвлекаясь от их связи со смыслом, т.
е. от их интерпретации. Рассмотрим, например, предложение «Кошки спят». Слово «кошки» вЂ” подлежащсе, а «спят» — сказуемое. Это предложение принадлежит языку, который можно описать, например, при помощи следующих синтаксических правил: (предложение)::.=.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
