AOP_Tom1 (1021736), страница 67
Текст из файла (страница 67)
Предложенный вами алгоритм должен удалить эту карту н указать ее адрес в переменной связи МЕИСАЕО. (Данный алгоритм при раскладыванин пасьянсов иногда называется мошенничеством.) 6. [00[ В примере с игральными картами предположим, что САМΠ— это имя переменной, значением которой является весь узел, как показано в (б). Операция САМО +- ИООЕ(ТОР) устанавливает поля САМО равными соответствующим полям самой верхней карты колоды. Какое из перечисленных ниже обозначений будет соответствовать масти самой верхней карты после выполнения этой операции: (а) 5ОТТ(САМО); (Ъ) 501таЛС(САМО) ); (с) 5ОТТ(СОИТЕМТ5(САМО) ); (б) 50ТТ(ТОР) т 7. [04[ В приведенном выше примере программы (5) для компьютера ИТХ переменная связи с верхней картой хранится в слове компьютера ИТХ, которое на языке ассемблера называется ТОР. Какой из приведенных вариантов кода для заданной структуры поля (1) похитит занести значение ИЕХТ(ТОР) в регистр А? Объясните, почему другой вариант неверен.
а) ЪОА ТОР(МЕХТ) Ъ) 001 ТОР 1ЮА 0,1(ИЕХТ) 8. [10[ Напишите программу для компьютера ИТХ, соответствующую алгоритму В. 9. [28[ Напишите программу для компьютера ИТХ, которая печатает названия карт из данной колоды, начиная с самой верхней карты н размещая их по одной в каждой строке со скобками вокруг карт, повернутых лицевой стороной вниз. 2.2. ЛИНЕЙНЫЕ СПИСКИ 2.2.1.
Стеки, очереди и деки Структурна данных обычно гораздо богаче структуры, действительно необходимой для их представления в компьютере. Например, каждый узел игральной карты из предыдущего раздела имеет поле МЕХТ для указания карты, расположенной в колоде под ней. Однако до сих пор не было указано ни одного способа определения карты, которая расположена пад данной картой (если таковая вообще имеется), или определения колоды, в которой находится данная карта. И, конечно же, совсем не были учтены характерные черты реальных игральных карт: детали оформления рубашки, расположение по отношению к другим объектам в данной комнате, молекулярное строение карт и т. д. Вполне вероятно, что такая информация очень важна для некоторых компьютерных приложений, но совершенно очевидно, что неразумно сохранять абсолютно есю информацию о структуре в каждой ситуации.
Действительно, в большинстве случаев для использования игральных карт достаточно лишь некоторых сведений из приведенных в первом примере. Например, поле ТАО, в котором содержится информация о том, квк ориентирована лицевая поверхность карты (вверх или вниз), часто является избыточным. В каждом конкретном случае следует принять отдельное решение о том, насколько полно информация о структуре данных должна быть представлена в таблицах и как получить доступ к каждому элементу информации. Для принятия подобных решений необходимо знать операции, которые нужно выполнить над этими данными.
Поэтому для решения каждой задачи в настоящей главе будут рассмотрены структура двлных п набор операций, которые выполняются нвд даннымп. Способ представления данных в компьютере зависит не только от способа их функционирования, но и от присущих им свойств. Действительно, при решении общих задач проектирования в основном учитываются способ функционирования и форма данных. Для иллюстрации этой идеи рассмотрим задачу проектирования аппаратного обеспечения.
Память компьютера подразделяется на память с произвольным доступом (гаврош ассов гпешогу), подобную оперативной памяти компьютера М1Х; память с доступом только для чтения (геай-оп!у шешогу), которая предназначается для хранения неизменяемых данных; вторичную память большого объема (эесопг]агу !эц!)г шепюгу), подобную дисковым накопителям компьютера М1Х, которые позволяют хранить огромный объем информации но с малой скоростью доступа к ней; ассоциативную память (аээос!анте шешогу или, точнее, соп1епс-аИгеззег! шешогу), в которой доступ к информации осуществляется по значению, а не по адресу, и т.
д. Назначение каждого типа памяти столь велико, что оно указано в ее названии. Хотя все зтн устройства являются компонентами "памяти", их функции в значительной степени влияют на их структуру и стоимость. У1инеймый список представляет собой последовательность и > О узлов Х[1], Х[2],, Х[в], важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре должно соблюдаться следующее условие: если п > О и Х [1] является первым узлом, а Х [и] — последним, то А-й узел Х [А] следует за Х [А — 1] и предшествует узлу Х [А + 1] для всех 1 < А < и.
С линейными списками могут выполняться следующие операции. ~) Получение доступа к й-му узлу списка для проверки и/или изменения содержимого его полей. й) Вставка нового узла сразу после или до й-го узла. ш) Удаление й-го узла. гг) Объединение в одном списке двух (или более) линейных списков. ч) Разбиение линейного списка на два (или более) списка. ч1) Создание копии линейного списка. чй) Определение количества узлов в списке. хш) Сортировка узлов в порядке возрастания значений в определенных полях этих узлов.
1х) Поиск узла с заданным значением в некотором поле. В операциях Д) — (гй) очень важны особые случаи, когда й = 1 и й = и, поскольку доступ к первому и последнему элементам линейного списка можно организовать гораздо проще, чем к любому другому элементу списка. Операции (чгй) и (1х) в данной главе рассматриваться не будут, так как они обсуждаются в главах 5 и б соответственно. В одном компьютерном приложении редко используются сразу все девять типов операций в общей их формулировке.
Поэтому линейные списки могут иметь самые разные представления в зависимости от класса операций, которые наиболее часто должны с ними выполняться. Достаточно трудно создать единое представление линейных списков, при котором эффективно выполнялись бы все эти операции. Например, сравнительно сложно организовать доступ к й-му узлу длинного списка для произвольно выбранного й, если одновременно необходимо выполнять вставку и удаление элементов в середине списка. Поэтому нужно различать разные типы линейных списков в зависимости от выполняемых с ними основных операций так же, как следует различать типы памяти компьютера, которые определяются ее конкретным назначением.
Линейные списки, в которых операции вставки, удаления и доступа к значениям чаще всего выполняются в первом или последнем узле, получили следующие специальные названия. Стек — это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются только на одном из концов списка. Очередь или одиосшороннлл очередь — это линейный список, в котором все операции вставки выполняются на одном из концов списка, а все операции удаления (и, как правило, операции доступа к данным) — на другом. Дек или двусторонняя очередь (допЫе-епдед циеие) это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются на обоих концах списка.
Дек, следовательно, является более общим вариантом стека или очереди. Он обладает некоторыми общими свойствами с рассмотренной выше колодой карт, к тому же на английском языке эти термины созвучны. Кроме того, следует различать деки с ограниченным емеодом (ои1рий-геггПсгед дедие) и с ограниченным вводом (впри1 гев1гтс1ей оедие), в которых операции удаления и вставки элементов соответственно выполняются только на одном из концов. В некоторых дисциплинах слово "очередь" используется в более широком смысле, например, при описании любого типа списка, для которого выполняются операции вставки и удаления.
Тогда упомянутые выше особые случаи следует характеризовать как разные "правила упорядочения" (или "очередности обслуживания"). В этой книге термин "очередь" предполагается использовать только в узком смысле, по аналогии с обычной упорядоченной очередью людей, ожидающих обслуживания. Механизм работы стека можно представить проще, если воспользоваться аналогией с железнодорожным разъездом, которая предложена Э, В.
Дейкстрой (рис. 1). Соответствующая схема для дека показана на рис. 2. Ввод в стек Вывод вз стека Рис. 1. Схема стека в виде железнодорожного разъезда. В деке с ограниченным вводом этот путь закрыт В деке с ограниченным выводом этот путь закрыт Рис. 2. Схема дека в виде железнодорожного разъезда. При выполнении операции удаления в стеке прежде всех удаляется "младший" объект списка, т. е.
объект, который был вставлен в список позже других. В очереди удаление выполняется наоборот: раньше всех удаляется "старший" объект, поскольку узлы покидают очередь в том же порядке, в котором они вставлялись. Многие исследователи независимо пришли к выводу о важности стеков и очередей, а потому присвоили им иные собственные имена. Так, стеки часто называют магазинными списками (риэЬ-г(ожп 1!эгз), реверсивными хранилищами (гетега!оп э!огарев), магазинами (се!!агэ), вложенными хранилищами (пезт!пй зсогеа), кучами (рйез), дисциплинами обслуживания в обратном порядке (!аес-ш-бгзг-оп! 11вгэ— 1 !ГО !1зсэ) и даже флюгерными списками (уо-уо 1!ага). Очереди часто называют циклическими хранилищами !с!гоп!аг в!огев) или дисциплинами обслуживания в порядке поступления !Йге1-)п-бгв1-оп! 11зФв — Г1ГО 1!все).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
