a) CONTENTS всегда рбозначает поле длиной в одно слово в узле длиной в одно слово. Таким образом, CONTENTS (1000)-это значение, хранимое в памяти по адресу 1000, т. е. переменная с таким значением. Если V является переменной связи, то CONTENTS (V) -значение, на которое указывает V (а не само значение переменной связи V).

b) Если V является именем переменной, значение которой хранится в некоторой ячейке памяти, то LOC(V) обозначает адрес этой ячейки. Соответственно, если V является переменной, значение которой хранится в памяти в виде полного слова, то C0NTENTS(L0C(V)) = V.

Эти обозначения можно легко преобразовать в код языка ассемблера MIXAL, хотя обозначения MIXAL выглядят несколько иначе. Значения переменных связи по.мещаются в индексные регистры, и, чтобы сослаться на нужное поле, необходимо использовать средства MIX для доступа к части поля. Например, приведенный выше алгоритм А можно записать следующим образо.м.

NEXT EQU 4:5 Определение полей NEXT

TAG EQU 1:1 и TAG для ассемблера.

LDI NEWCARD AL ill <- NEWCARD.

LDA TOP rA <- TOP. (5)

STA O.KNEXT) NEXT (ill) +-гА.

STl TOP AZ TOP <- rll.

STZ 0,1 (TAG) Aa TAG(rll) <-0.

Простота и эффективность вьтолнения этих операций на компьютере - вот основные причины использования концепции "связанной памяти".

Иногда приходится иметь дело с простой переменной, которая обозначает целый узел, а потому ее значение представляет не одно поле, а последовательность полей. В таком случае можно записать

CARD <- NODE(ТОР), (6)

где NODE - такая же спецификация поля, как и CONTENTS, но относится она к целому узлу, а CARD является переменной, которая имеет структуру наподобие (1). Если узел имеет размер с слов, то обозначение (6) является сокращенной записью для с операций присвоения, выполняемых на низком уровне:

CONTENTS (LOC (CARD)-l-j) CONTENTS (ТОР-Н Л, О < i < с. (7)

Между языком ассемблера и обозначениями, используемыми в алгоритмах, есть важное отличие. Так как язык ассемблера близок к внутреннему языку компьютера, то используемые в программах MIXAL символы обозначают адреса, а не значения. Поэтому в левых столбцах кода (5) символ ТОР на самом деле обозначает адрес в памяти, по которому находится указатель на самую верхнюю карту в колоде, а в выражениях (6) и (7) и комментариях в (5) справа он является значением ТОР, а именно - адресом узла самой верхней карты. Такое различие между языком ассемблера и языком высокого уровня часто является источником ошибок в работе начинающих программистов, поэтому читателю настоятельно рекомендуется выполнить упр. 7, а также другие упражнения из данного раздела для закрепления навыков работы с введенными здесь обозначениями.

УПРАЖНЕНИЯ

1. [04] в ситуации, показанной на схеме (3), каким будет значение выражения (а) SUIT(NEXT(ТОР)); (b) NEXT(NEXT(NEXT(TOP)))?

2. [10] В приведенном выше разделе сказано, что во многих случаях CONTENTS (LOC(V)) = V. При каких условиях LOC (CONTENTS (V)) = V?

3. [11] Предложите алгоритм, обратный алгоритму А: он должен удалить самую верхнюю карту колоды (если колода не пуста) и задать ссылку NEWCARD для адреса этой карты.

4. [18] Предложите алгоритм, аналогичный алгоритму А, но новая карта должна располагаться лицевой стороной вниз в нижней части колоды. (Колода может быть пустой,)

► 5. [21] Предложите алгоритм, обратный алгоритму из упр. 4. Допустим, что колода не пуста и самая нижняя карта в ней расположена лицевой стороной вниз. Предложенный вами алгоритм должен удалить эту карту и указать ее адрес в переменной связи NEWCARD. (Данный алгоритм при раскладывании пасьянсов иногда называется мошенничеством.)

6. [06] В примере с игральными картами предположим, что CARD - это имя переменной, значением которой является весь узел, как показано в (6). Операция CARD NODE (ТОР) устанавливает поля CARD равными соответствующим полям самой верхней карты колоды. Какое из перечисленных ниже обозначений будет соответствовать масти самой верхней карты после выполнения этой операции:

(а) SUIT (CARD); (b) SUIT (LOC (CARD) ) ; (c) SUIT (CONTENTS (CARD) ) ; (d) SUIT (TOP) ?

► 7. [04] в приведенном выше примере программы (5) для компьютера MIX переменная связи с верхней картой хранится в слове компьютера MIX, которое на языке ассемблера называется ТОР. Какой из приведенных вариантов кода для заданной структуры поля (1) позволит занести значение NEXT (ТОР) в регистр А? Объясните, почему другой вариант неверен.

а) LDA ТОР (NEXT) Ь) LD1 ТОР

LDA 0.1(NEXT)

► 8. [18] Напишите программу для компьютера MIX, соответствующую алгоритму В.

9. [23] Напишите программу для компьютера MIX, которая печатает названия карт из данной колоды, начиная с самой верхней карты и размещая их по одной в каждой строке со Скобками вокруг карт, повернутых лицевой стороной вниз.

2.2. ЛИНЕЙНЫЕ СПИСКИ

2.2.1. Стеки, очереди и деки

Структура данных обычно гораздо богаче структуры, действительно необходимой для их представления в компьютере. Например, каждый узел игральной карты из предыдущего раздела имеет поле NEXT для указания карты, расположенной в колоде под ней. Однако до сих пор не было указано ни одного способа определения карты, которая расположена над данной картой (если таковая вообще имеется), или определения колоды, в которой находится данная карта. И, конечно же, совсем не были учтены характерные черты реальных игральных карт: детали оформления рубашки, расположение по отношению к другим объектам в данной комнате, молекулярное строение карт и т. д. Вполне вероятно, что такая информация очень важна для некоторых компьютерных приложений, но совершенно очевидно, что неразумно сохранять абсолютно всю информацию о структуре в каждой ситуации. Действительно, в большинстве случаев для использования игральных карт достаточно лишь некоторых сведений из приведенных в первом примере. Например, поле TAG, в котором содержится информация о том, как ориентирована лицевая поверхность карты (вверх или вниз), часто является избыточным.

В каждом конкретном случае следует принять отдельное решение о том, насколько полно информация о структуре данных должна быть представлена в таблицах и как получить доступ к каждому элементу информации. Для принятия подобных решений необходимо знать операции, которые нужно выполнить над этими данными. Поэтому для решения каждой задачи в настоящей главе будут рассмотрены структура данных и набор операций, которые выполняются над данными. Способ представления данных в компьютере зависит не только от способа их функционирования, но и от присущих им свойств. Действительно, при решении общих задач проектирования в основном учитываются способ функционирования и форма данных.

Для иллюстрации этой идеи рассмотрим задачу проектирования аппаратного обеспечения. Память компьютера подразделяется на память с произвольным доступом (random access memory), подобную оперативной памяти компьютера MIX; память с доступом только для чтения (read-only memory), которая предназначается для сранения неизменяемых данных; вторичную память большого объема (secondary bulk memory), подобную дисковым накопителям компьютера MIX, которые позволяют хранить огромный объем информации но с малой скоростью доступа к ней; ассоциативную память (associative memory или, точнее, content-addressed memory), в которой доступ к информации осуществляется по значению, а не по адресу, и т. д. Назначение каждого типа памяти столь велико, что оно указано в ее названии. Хотя все эти устройства являются компонентами "памяти", их функции в значительной степени влияют на их структуру и стоимость.

Линейный список представляет собой последовательность п > О узлов Х[1], X [2], ..., X [п], важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре должно соблюдаться следующее условие: если п > О и Х[1] является первым узлом, а Х[п] -последним, то fc-й узел Х[А;] следует за X [А; - 1] и предшествует узлу Х[А; -I-1] для всех 1 < А; < п.