Д. Кнут - Искусство программирования том 1 (1119450), страница 65
Текст из файла (страница 65)
д. Вполне вероятно, что такая информация очень важна для некоторых компьютерных приложений, но совершенно очевидно, что неразумно сохранять абсолютно всю информацию о структуре в каждой ситуации. Действительно, в большинстве случаев для использовании игральных «арт достаточно лишь некоторых сведений из приведенных в первом примере.
Например, поле ТАС, в котором содержится информация о том, как ориентирована лицевая поверхность карты (вверх или вниз), часто является избыточным. В каждом конкретном случае следует принять отдельное решение о том, насколько полно информация о структуре данных должна быть представлена в таблицах и как получить доступ к каждому элементу информации. Для принятия подобных решений необходимо знать операции, которые нужно выполнить над этими данными. Поэтому для решения каждой задачи в настоящей главе будут рассмотрены структура данных н набор операция, которые вьтолняются над дюгнымп. Способ представления данных в компьютере зависит не только от способа их функционирования, но и от присущих им свойств. Действительно, при решении общих задач проектирования в основном учитываются способ функционирования и форма данных.
Для иллюстрации этой идеи рассмотрим задачу проектирования аппаратного обеспечения. Память компьютера подразделяется на память с произвольным доступом (гаврош ассеэв шешогу), подобную оперативной памяти компьютера И1Х; память с доступом только для чтения (гоаб-оп1у шепюгу), которая предназначается для «ранения неизменяемых данных, вторичную память большого объема (эесопбагу Ьп1к гпепюгу), подобную дисковым накопителям компьютера М11, которые позволяют хранить огромный объем информации но с малой скоростью доступа к ней; ассоциативную память (ввэос1ас1хе шепюгу или, точнее, сопФепыасЫгеэвеп шепюгу), в которой доступ к информации осуществляется по значению, а не по адресу, и т.
д. Назначение каждого типа памяти столь велико, что оно указано в ее названии. Хотя все эти устройства являются компонентами "памяти", их функции в значительной степени влияют на их структуру и стоимость. Линейный список представляет собой последовательность и > О узлов ХШ, х[21, ..., Х[п), важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии.
Иначе говоря, в такой структуре должно соблюдаться следующее условие: если и ) О и 1 [13 является первым узлом, а 1 [п3 — последним, то 1с-й узел Х [х) следует за Х [1с — Ц и предшествует узлу Х [х + 1] для всех 1 < 1с < и. С линейными списками могут вьпюлняться следующие операции. !) Получение доступа к )г-му узлу списка для проверки и/ллли изменения содержимого его полей.
й) Вставка нового узла сразу после или до к-го узла. й!) Удаление !г-го узла. !г) Объединение в одном списке двух (или более) линейных списков. ь) Разбиение линейного списка на два (или более) списка. г!) Создание копии линейного списка. чй) Определение количества узлов в списке. хй!) Сортировка узлов в порядке возрастания значений в определенных полях этих узлов. !х) Поиск узла с заданным значением в некотором поле. В операциях (!) — (ш) очень важны особые случаи, когда /с = ! и !г = и, поскольку доступ к первому и последнему элементам линейного списка можно организовать гораздо проще, чем к любому другому элементу списка.
Операции (чш) и (!х) в данной главе рассматриваться не будут, так как они обсуждаются в главах 5 и 6 соответственно. В одном компьютерном приложении редко используются сразу все девять типов операций в общей их формулировке. Поэтому линейные списки могут иметь самые разные представления в зависимости от класса операций, которые наиболее часто должны с ними выполняться. Достаточно трудно создать единое представление линейных списков, при котором эффективно выполнялись бы все эти операции. Например, сравнительно сложно организовать доступ к !с-му узлу длинного списка для произвольно выбранного !с, если одновременно необходимо выполнять вставку и удаление элементов в середине списка. Поэтому нужно различать разные типы линейных списков в зависимости от выполняемых с ними основных операций так же, как следует различать типы памяти компьютера, которые опрццеляются ее конкретным назначением.
Линейные списки, в которых операции вставки, удаления и доступа к значениям чаще всего выполняются в первом или последнем узле, получили следующие специальные названия. Сплек †э линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются только на одном из концов списка. Очередь или односторонняя очередь — это линейный список, в котором все операции вставки выполняются на одном яз концов списка, а все операции удаления (и, как правило, операции доступа к данным) — на другом.
Дек или двусторонняя очередь (ооий!е-епдео цпеие) это линейный список, в котором все операции вставки и удаления (и, как правило„операции доступа к данным) выполняются на обоих концах списка. Дек, следовательно, является более общим вариантом стека или очереди. Он обладает некоторыми общими свойствами с рассмотренной выше колодой карт, к тому же на английском языке эти термины созвучны. Кроме того, следует различать деки с ограниченным выводом (ои!ри!гсгСг!с!ед дедие) и с ограниченным вводом (!при! гев!твердея дедие), в которых операции удаления и вставки элементов соответственно выполняются только на одном из концов. В некоторых дисциплинах слово "очередь" используется в более широком смысле, например, при описании любого типа списка, для которого выполняются операции вставки и удаления, Тогда упомянутые выше особые случаи следует характеризовать как разные "правила упорядочения" (или "очередности обслуживания" ).
В этой книге термин "очередь" предполагается использовать только в узком смысле, по аналогии с обычной упорядоченной очередью людей, ожидающих обслуживания. Механизм работы стека можно представить проще, если воспользоваться аналогией с железнодорожным разъездом, которая предложена Э. В. Дейкстрой (рис. 1). Соответствующая схема для дека показана на рис. 2. Ввод в стек Вывод вз стека Рис. 1. Схема стека в виде железнодорожного разъезда. В деке с ограниченным вводом этот путь закрыт В деке с ограниченным выводом этот путь закрыт Рнс.
2. Схема дека в виде железнодорожного разъезда. При выполнении операции удаления в стеке прежде всех удаляется "младший" объект списка, т. е. объект., который был вставлен в список позже других, В очереди удаление выполняется наоборот: раньше всех удаляется "старший" объект, поскольку узлы покидают очередь в том же порядке, в котором они вставлялись. Многие исследователи независимо пришли к выводу о важности стеков и очередей, а потому присвоили им иные собственные имена. Так, стеки часто называют магазинными списками (рпэ!э-Йоввп 1!зФэ), реверсивными хранилищами (гетега!оп зсогайез), магазинами (се11агэ), вложенными хранилищами (пез11пк зсогез), кучами (р1!ез), дисциплинами обслуживания в обратном порядке (1аем1п-Ягзс-оиг 1!з1в— ЫгО !!все) и даже флюгерными списками (уо-уо 1!эсв).
Очереди часто называют Удалить Вставить Верх Вто у» Начало Второй Третий Конец (Ь) Очередь Третий сверху Крайний справа Второй справа Второй слева Крайний Четвертый сверху Няз Вставить яля удалить Вставить яля удалить (а) Стек (с) Дек Рнс. 3. Три наиболее важных класса линейных списков. циклическими хранилищами (с!гсц!аг э!огеэ) или дисциплинами обслуживания в порядке поступления (бгз1-!и-бгзс-оц! 1!э!э — Р1РО 1!э!э). Термины "ЫРО" и "Р1РОь многие годы употреблялись бухгалтерами для обозначения метода оценки и продажи товаров. Еще один термин, "стеллаж" (вЬе1(), применялся для деков с ограниченным выводом.
Аналогично деки с ограниченным вводом назывались также свитками (эсго!1э или го11з). Такое разнообразие имен само по себе интересно уже тем, что оно свидетельствует о важности этих концепций. Постепенно слова "стек" и "очередь" вошли в стандартную терминологию, и только термин "магазинный список" все еще остается сравнительно популярным, особенно в теории автоматов. На практике довольно часто приходится иметь дело со стеками. Например, анализируя набор данных, часто требуется составить список возникающих исключительных ситуаций или действий, которые необходимо выполнить впоследствии. После анализа исходного набора данных можно перейти к выполнению этих действий с помощью списка, удаляя его элементы до полного опустошения списка.
(Примером такой ситуации является задача о "точке перевала", которая описана в упр. 1.3.2 — 10.) Для организации подобною списка удобно использовать стек или очередь (хотя стек гораздо удобнее). При решении задач мы практически всегда мысленно организуем некое подобие "стека", в котором одна задача порождает другую, а другая, в свою очередь,— следующую. Так задачи накапливаются и соответственно разрешаются одна за другой. Аналогично процесс входа в подпрограммы и выхода из них во время выполнения компьютерной программы осуществляется подобно стеку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
