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