Д. Кнут - Искусство программирования том 1 (1119450), страница 64
Текст из файла (страница 64)
Обратите внимание на особую связь "Л" в узле 100. Здесь прописная греческая буква "лямбда' обозначает пустую связь, т. е. связь с несуществующим узлом. Пустая ссылка Л используется в узле 100, так как десятка треф является самой нижней картой в колоде. В компьютере ссылка Л представлена легко распознаваемым значением, которое не может быть адресом узла. Вообще, предположим, что по адресу 0 никаких узлов нет, тогда Л практически всегда в программах для компьютера М1Х может быть представлена как связь с нулевым значением адреса. Введение понятия связи с другими элементами данных является чрезвычайно важной идеей в компьютерном программировании и ключевым способом представления сложных структур.
При создании схемы представления узлов в компьютере связи обычно изображаются в виде стрелок. Тогда схема примера (2) будет выглядеть следующим образом: твг При этом фактические адреса 242, 386 и 100 (которые в данном примере все равно не имеют большого значения) в схеме (3) не представлены. Используемое в электротехнике обозначение заземления здесь применяется для обозначения пустой связи в правой части схемы.
Обратите внимание также, что в схеме (3) на самую верхнюю карту указывает стрелка ТОР. Здесь ТОР представляет собой переменную связи (ЪпА иагюйе), которая часто называется указателем (ро)п1ег вапаЫе), т. е. переменной, значением которой является связь. Все ссылки на узлы в программе определяются непосредственно с помощью переменных связи (или констант связи) либо косвенно с помощью полей связи в других узлах.
Теперь рассмотрим самую важную часть системы обозначений — обозначение ссылки на поле внутри некоторого узла. Оно выглядит достаточно просто, поскольку для этого нужно лишь привести имя данного поля и указать вслед за ним в скобках связь с нужным узлом. Например, для случаев (1) — (3) это можно сделать так, как показано ниже: ЗАИК(100) = 10; 801Т(ТОР) = 2; Т1Т1Е(ТОР) = "ои2оР"; ЕАИК(ИЕХТ(ТОР)) = 3. (4) Читателю следует внимательно изучить зти примеры, поскольку такие обозначения полей будут применяться во многих других алгоритмах в настоящей и последующих главах. Чтобы пояснить смысл этой идеи, рассмотрим простой алгоритм, предназначенный для размещения с верхней стороны колоды новой карты с лицевой стороной, обращенной вверх.
При этом допустим, что значение переменной связи ИЕУСАИО содержит связь с новой картой. А1. Установить ИЕХТ(ИЕИСАИ)) +- ТОР. (Таким образом, значение поля связи в новой карте будет указывать на верхнюю карту колоды.) А2. Установить ТОР е — ИЕЫСАИО. (ТОР по-прежнему будет указывать на верхнюю карту колоды.) АЗ.
Установить ТАО(ТОР) +- О. (Карта обращена лицевой стороной вверх.) 1 В другом примере рассмотрим алгоритм для вычисления текущего количества карт в колоде. В1. Установить И '- О, Х +- ТОР. (Здесь И является целочисленной переменной, а Х вЂ переменн связи.) В2. Если Х = Л, прекратить выполнение алгоритма; при этом значение И будет равно количеству карт в колоде. ВЗ.
Установить И +- И + 1, Х +- ИЕХТ(Х) и вернуться к шагу В2. $ Обратите внимание на то, что в этих алгоритмах символьные имена используются для двух совершенно разных объектов: как имена переменных (ТОР, ИЕЫСАЕО, И, Х) и как имена полей (ТАО, ИЕХТ). Их не следует путать. Если Р†э имя поля и Е ф Л вЂ свя, то Р(1) †э переменная. Но сам по себе символ Р не является переменной, поскольку не обладает никаким значением, если только оно не является непустой связью. При обсуждении подробностей работы компьютера на низком уровне будут использоваться приведенные далее обозначения, которые применяются для преобразования хранимых значений и их адресов. а) СОИТЕМТЯ всегда Обозначает поле длиной в одно слово в узле длиной в одно слово. Такилг образом, СОИТЕИТЯ(1000) †э значение, хранимое в памяти по адресу 1000,т. е.переменийя с таким значением.
Если Ч является переменной связи, то СОМТЕМТЯ (Ч) — значение, на которое указывает Ч (а не само значение переменной связи Ч). Ь) Если Ч является именем переменной, значение которой хранится в некоторой ячейке памяти, то 10С(Ч) обозначает адрес этой ячейки. Соответственно, если У является переменной, значение которой хранится в памяти в виде полного слова, то СОМТЕМТЯ(1.0С(Ч) ) = Ч. Эти обозначения можно легко преобразовать в код языка ассемблера М1ХА1., хотя обозначения М1ХА1 выглядят несколько иначе.
Значения переменных связи помещаются в индексные регистры, и, чтобы сослаться на нужное поле, необходимо использовать средства М1Х для доступа к части поля. Например, приведенный выше алгоритм А можно записать следующим образом. (5) Простота и эффективность выполнения этих операций на компьютере — вот основные причины использования концепции "связанной памяти".
Иногда приходится иметь дело с простой переменной, которая обозначает целый узел, а потому ее значение представляет не одно поле, а последовательность полей. В таком случае можно записать (6) САЕВ г- МОВЕ(ТОР), где МОВŠ— такая же спецификация поля, как и СОМТЕИТЯ, но относится она к целому узлу, а САЕВ является переменной, которая имеет структуру наподобие (1). Если узел имеет размер с слов, то обозначение (б) является сокращенной записью для с операций присвоения, выполняемых на низком уровне: СОМТЕМТЯИ.ОС(САЕВ) + г) г- СОИТЕИТЯ(ТОР+)), 0 ( 1' < с. (7) Между языком ассемблера и обозначениями, используемыми в алгоритмах, есть важное отличие. Так как язык ассемблера близок к внутреннему языку компьютера, то используемые в программах М1ХА1. символы обозначают адреса, а не значения. Поэтому в левых столбцах кода (5) символ ТОР на самом деле обозначает адрес в памяти, по которому находится указатель на самую верхнюю карту в колоде, а в выражениях (б) и (7) и комментариях в (5) справа он является значением ТОР, а именно — адресом узла самой верхней карты.
Такое различие между языком ассемблера и языком высокого уровня часто является источником ошибок в работе начинающих программистов, поэтому читателю настоятельно рекомендуется выполнить упр. 7, а также другие упражнения из данного раздела для закрепления навыков работы с введенными здесь обозначениями. МЕХТ ЕОО ТАС ЕЦО 101 ЮА ЯТА ЯТ1 ЯТХ 4:5 1:1 ИЕИСАЕВ ТОР 0,1(ИЕХТ) ТОР 0,1(ТАО) Определение полей ИЕХТ и ТАС лля ассемблера. А1, гП +- ИЕЧСАЕВ. гА +- ТОР. МЕХТ(г11) э- гА. АЗ.
ТОР+- г11, АЗ. ТАС(г11) +- О. ! а) 10А ТОР (МЕХТ) Ъ) 001 ТОР АВА 0,1(МЕХТ) 8. [18] Напишите программу для компьютера М11, соответствующую алгоритму В. 9. [ЕЗ] Напишите программу для компьютера М11, которая печатает названия карт из данной колоды, начиная с самой верхней карты и размещая их по одной в каждой строке со скобками вокруг карт, повернутых лицевой стороной вниз. УПРАЖНЕНИЯ 1. [04] В ситуапии, показанной на схеме (3), каким будет значение выражения (а) 501Т(МЕХТ(ТОР)), (Ь) ИЕХТ(ИЕХТ(ИЕХТ(ТОР))) ? 2. [10] В приведенном выше разделе сказано, что во многих случаях СОМТЕМТ5(ЕОС(Ч)) = 7.
При каких условиях ВОС(СОИТЕМТЕ(Ч)) = у? 3. [11] Предложите алгоритм, обратный алгоритму А: он должен удалить самую верхнюю карту колоды (если колода не пуста) и задать ссылку МЕИСАЕВ для адреса этой карты. 4. [18] Предложите алгоритм, аналогичный алгоритму А, но новая карта должна располагаться лицевой стороной вниз в нижней части колоды. (Колода может быть пустой,) 5. [21] Предложите алгоритм, обратный алгоритму из упр.
4. Допустим, что колода не пуста и самая нижняя карта в ней расположена лицевой стороной вниз. Предложенный вами алгоритм должен удалить эту карту и указать ее адрес в переменной связи ИЕИСАЕВ. (Данный алгоритм при раскладывании пасьянсов иногда называется мошенничеством.) 6. [06] В примере с игральными картами предположим, что САЕ — это имя переменной, значением которой является весь узел, как показано в (6). Операция САВВ < — ИОВЕ(ТОР) устанавливает поля САИВ равными соответствующим полям самой верхней карты кололы. Какое из перечисленных ниже обозначений будет соответствовать масти самой верхней карты после выполнения этой операции: (а) 501Т(САЕЗ); (Ь) 5011(ЕОС(САЕВ)); (с) 5011(СОИТЕИТ5(САЕВ)); (й) 501Т(ТОР)? 7. [04] В приведенном выше примере программы (5) для компьютера М11 переменная связи с верхней картой хранится в слове компьютера М11, которое на языке ассемблера называется ТОР.
Какой из приведенных вариантов кода для заданной структуры поля (1) позволит занести значение МЕХТ(ТОР) в регистр А? Объясните, почему другой вариант неверен. 2.2. ЛИНЕЙНЫЕ СПИСКИ 2.2.1. Стеки, очереди и деки Структурна данных обычно гораздо богаче структуры, действительно необходимой для их представления в компьютере.
Например, каждый узел игральной карты из предыдущего раздела имеет поле МЕХТ для указания карты, расположенной в колоде под ней. Однако до сих пор не было указано ни одного способа определения карты, которая расположена над данной картой (если таковая вообще имеется), или определения колоды, в которой находится данная карта. И, конечно же, совсем не были учтены характерные черты реальных игральных карт: детали оформления рубашки, расположение по отношению к другим объектам в данной комнате, молекулярное строение карт и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
