AOP_Tom1 (1021736), страница 68
Текст из файла (страница 68)
Термины "11ГО" и "Г1ГОе многие годы употреблялись бухгалтерами для обозначения метода оценки и продажи товаров. Еще один термин, "стеллаж" !еЬе!1), применялся для деков с ограниченным выводом. Аналогично деки с ограниченным вводом назывались также свитками !всго!!в или го11з).
Такое разнообразие имен само по себе интересно уже тем, что оно свидетельствует о важности этих концепций. Постепенно слова "стек" и "очередь" вошли в стандартную терминологию, и только термин "магазинный списоке все еще остается сравнительно популярным, особенно в теории автоматов. На практике довольно часто приходится иметь дело со стеками. Например, анализируя набор данных, часто требуется составить список возникающих исключительных ситуаций или действий, которые необходимо выполнить впоследствии.
После анализа исходного набора данных можно перейти к выполнению этих действий с помощью списка, удаляя его элементы до полного опустошения списка. !Примером такой ситуации является задача о "точке перевала", которая описана в упр. !.3.2-10.) Для организации подобною списка удобно использовать стек или очередь !хотя стек гораздо удобнее). При решении задач мы практически всегда мысленно организуем некое подобие "стека", в котором одна задача порождает другую, а другая, в свою очередь,— следующую. Так задачи накапливаются и соответственно разрешаются одна за другой. Аналогично процесс входа в подпрограммы и выхода из них во время выполнения компьютерной программы осуществляется подобно стеку.
Стеки особенно полезны при обработке языков с вложенной структурой, например для языков программирования, арифметических выражений и конструкций кЯсЬасЬсе1еагхе" немецкого языка. Вообще, стеки чаще всего встречаются при работе с явными и неявными рекурсивными алгоритмами, которые более подробно рассматриваются в главе 8. Удалить Вставить Верх В (>рой сверху Начало Второй Третий Конец (Ь) Очередь Третий сверху Крайний Второй Второй Крайний слева слева справа справа Четвертый сверху Низ Вставить нли удалить Вставить нлн удалить (с) Дек (а) Стек Рис, 3. Три наиболее важных класса линейных списков. Для описания алгоритмов обработки этих структур обычно используется специальная терминологИя.
Например, объект кладут на верх стека или снимают верхний элемент стека (рис. 3, (а)). Доступ к элементу, находящемуся внизу стека, наиболее затруднителен'; и его нельзя удалить до тех пор, пока не будут удалены все остальные элементы стека. (Часто говорят, что объект проталкивается (риза) вниз стека и вмталкиваетсл (рор) на верх стека при удалении самого верхнего элемента. Эта терминология возникла от аналогии со стопкой тарелок в кафе.
Краткость английского написания слов "протолкнуть" (риеЬ) и "вытолкнуть" (рор) обладает определенными преимуществами, но эти термины часто неверно трактуются, как движение всего списка целиком в памяти компьютера. На самом деле физически ничто никуда не проталкивается, а объекты всего лишь добавляются сверху стека точно так, как при укладке сена в стоге или коробок в стопке.) По отношению к очередям применяют понятия начало (угон!) и конец (геаг) очереди.
Объекты вставляются в конце очереди и проталкиваются по ней до тех пор, пока не достигнут начала очереди (рис. 3, (Ь)). При работе с деками используют понятия левый ((еус) и правый (г1дЫ) концы (рис. 3, (с)). Концепции верха, низа, начала и конца иногда применяют по отношению к декам, которые используются в качестве стеков или очередей, но нет никаких стандартных соглашений в отношении того конца, с которого они должны располагаться: с правого или левого. Таким образом, мы выяснили, что при создании алгоритмов достаточно удобно применять все богатое разнообразие языка; "верх-низ" (ир-доки) — для стеков, "ожидание в очереди" (пай!пй ш!!пе) — для очередей и "слева-справа" (!ей-г!3Ь1)— для деков.
При работе со стеками и очередями удобно использовать некоторые дополнительные обозначения. Например, обозначение А ч= х указывает, что элемент х вставлен сверху стека А (если А — это стек) или элемент х вставлен в конце очереди (если А — это очередь). Аналогично (2) хсА используется для обозначения того, что переменная х приравнивается к значению верхнего элемента стека А или начального элемента очереди А, т. е. это значение, которое удаллетса из А. Обозначение (2) не имеет смысла, если А пусто, т.
е. когда А не содержит значений. Если А — непустой стек, то (3) 1ор(А) можно использовать для обозначения самого верхнего его элемента. УПРАЖНЕНИЯ 1. [06) Дек с ограниченным вводом является линейным списком, в котором элементы могут вставляться на одном конце, а удаляться — с любого конца. Очевидно, что дек может функционировать, как стек яли очередь, если его элементы всегда будут удаляться с одного из двух его концов.
Может ли дек с ограниченным выводом функционировать, как стек или очередь? 2. [!5] Допустим, что четыре вагона с номерами 1, 2, 3 и 4 (слева направо) расположены со стороны ввода. вагонов железнодорожных путей (см. рис. 1). Предположим, что выполняется такая последовательность действий (которая совпадает с направлением стрелок на этой схеме и не дбпускает "перепрыгивания" через вагоны): (!) поместить вагон 1 в стек. (!!) поместить вагон 2 в стек; (ш) вывести вагон 2 из стека; (!г) поместить вагон 3 в стек; (г) поместить вагон 4 в стек;(г!)вывести вагон 4 из стека;(гй)вывести вагон 3 из стека; (г!й) вывести вагон 1 из стека.
После выполнения этих действий исходный порядок вагонов, 1234, станет иным, 2431. Целью этого и следующих упражнений является выяснение, какие гтерестаяовклдопустямы в стеках, очередях и деках. Можно ли выполнить такую перестановку шести пронумерованных вагонов, чтобы из исходного порядка 123456 получить порядок 325641? Можно ли поменять порядок вагонов так, чтобы он был равен 154623? (Если можно, то как именно?) 3. [25] Действия (!) — (г!й) в предыдущем упражнении можно записать в более кратком виде с помощью кода ЯБХЯЯХХХ, где Б обозначает "ввести вагон в стек", а Х вЂ” "вывести вагон из стека".
Некоторые последовательности действий Я и Х бессмысленны, поскольку на соответствующих путях может совсем не быть вагонов. Например, последовательность действий БХХББХХБ не может быть выполнена, так как предполагается, что в исходном состоянии стек пуст. Назовем последовательность действий Б и Х дапусшимой, если она содержит и действий Б и и действий Х и если в ней нет никаких бессыысленных действий. Сформулируйте правило, с помощью которого было бы легко различать допустимые и недопустимые последовательности действий, Покажите, что различные допустимые последовательности действий приводят к разным перестановкам 4. [МУ4] Найдите простую формулу для а„, т.
е. для количества перестановок среди и элементов, которые могут быть получены с помощью стека из упр. 2. 5. [?яв8] Покажите, что с помощью стека можно получить перестановку р~рз... р„исходной последовательности 12... и только в случае, если ие существует таких индексов !<7<5,чтор <рь<р,. 6.
[00] Рассмотрим задачу из упр. 2, в которой очередь используется вместо стека. Какие перестановки 12... и можно получить с помощью очереди? 7. [25] Рассмотрим задачу из упр. 2, в которой вместо стека используется дек. (а) Найдите такую перестановку последовательности 1234, которая может быть получена с помощью дека с ограниченным вводом, но не может быть получена с помощью дека с ограниченным выводом. (Ь) Найдите такую перестановку последовательности 1234, которая может быть получена с помощью дека с ограниченным выводом, но не может быть получена с помощью дека с ограниченным вводом.
[Как следствие из (а) и (Ъ) между деками с ограниченным вводом и выводом существует определенная разиица.] (с) Найдите такую перестановку последовательности 1234, которая не может быть получена ни с помощью дека с ограниченным вводом, ни с помощью дека с ограниченным выводом. 8. [28] Существуют ли какие-либо перестановки 12... и, которые не могут быть получены с помощью дека, не имеющего ни ограниченного ввода, ни ограниченного вывода? 9. [М20] Пусть ܄— количество перестановок среди и элементов, которые могут быть получены с помощью дека с ограниченным вводом. (Обратите внимание, что 54 = 22, как показано в упр.
7.) Покажите, что Ь„также является количеством перестановок среди и элементов, которые могут быть получены с помощью дека с ограниченным выводам. 10. [Изб] (См, упр. 3.) Пусть Б, 5) и Х обозначают соответственно операции ввода элемента слева, ввода элемента справа и вывода элемента слева в деке с ограниченным выводом.
Например, применив последовательность действий т:)С)ХБХБХХ к исходной последовательности символов 1234, Получим 1342. Последовательность действий ЯХЯБХЯХХ приведет к такому же результату. Найдите такое определение понятия ттаиустиимэа последовательности символов Я, с) и Х, чтобы выполнялось следующее требование: каждая перестановка и элементов, которую можно получить с помощью дека с ограниченным выводом, должна соответствовать только одной допустимой последовательности. э 11. [М40] Из упр. 9 и 10 получаем, что б„является количеством допустимых последовательностей длины 2и.
Найдите пРоизводЯшУю фУнкцию 2 юао 6 э" в "замкнУтом виде". 12. [НИХ] Вычислите асимптотические значения величин а„и 6„иэ упр. 4 и 11. 13. [М48] Сколько перестановок среди и элементов можн8 получить с помощью декау [В статье Розенстиля и Таржана, у. А!8от!тбтэ 5 (1984), 389 — 390, приводится алгоритм, в котором за 0(и) шагов выясняется допустимость данной перестановки.) э 14.
[8э] Предположим, что в качестве структур данных используются только стеки. Как наиболее эффективным образом воплотить очередь с помощью двух стекову 2.2.2. Последовательное распределение Наиболее простой и естественный способ хранения линейного списка в памяти компьютера заключается в расположении элементов в последовательных ячейках, при котором один узел списка следует сразу же за другим. Тогда ЬОС(Х[!'+ 1) ) = 1ОС(Х[т') ) + с, где с — количество слов в одном узле. (Обычно с = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
