сортировка, арифметику многочленов, моделирование дискретных систем, работа с разреженными матрицами, манипулирование алгебраическими формулами, а также создание компиляторовоперационных систем. Основное внимание здесь будет уделено представлению структуры внутри компьютера; ее преобразование между внешними и внутренними представлениями будет подробно рассмотрено в главах 9 и 10.

Большая часть представленного здесь материала часто называется обработкой списков, особенно с тех пор как было создано достаточно систем программирования, например LISP , предназначенных специально для работы со структурами общего типа под названием Списки. (Далее в этой главе слово "Список" с прописной начальной буквой будет использоваться для обозначения отдельного типа структуры, которая более подобно рассматривается в разделе 2.3.5.) Хотя в большинстве случаев системы обработки Списков очень полезны, они часто накладывают на работу программиста не всегда оправданные ограничения. В собственных программах обычно эффективнее непосредственно использовать предлагаемые в этой главе методы, подгоняя для конкретного приложения формат данных и алгоритмы их обработки. Многие разработчики программного обеспечения все еще считают, что методы обработки Списков очень сложны (и потому вынуждены использовать интерпретаторы сторонних разработчиков или уже готовые наборы процедур) и что обработка Списков может выполняться лишь некоторым строго определенным способом. Как будет показано ниже, ничего сверхъестественного, загадочного или трудного Б работе со сложными структурами нет. Приведенные здесь методы являются частью арсенала каждого программиста, и их можно использовать при создании программ на языке ассемблера или на таких алгебраических языках, как FORTRAN, С и Java.

Методы работы с информационными структурами будут проиллюстрированы здесь на примере компьютера MIX. Читателю, которого не интересует подробная структура программ для компьютера MIX, следует изучить хотя бы способы, с помощью которых информация о структуре представляется в памяти компьютера MIX.

Здесь важно определиться с терминами и обозначениями, которые будут довольно часто использоваться. Информация в таблице состоит из набора узлов (nodes); некоторые авторы называют их записями (records) , объектами (entities) или цепочками (beads) . Иногда вместо термина "узел" будут использоваться термины "предмет" и "элемент". Каждый узел состоит из одного или нескольких последовательных слов в памяти компьютера, которые могут быть разделены на именованные части - поля. В простейшем случае узел представляет собой только одно слово и содержит только одно поле, охватывающее это слово целиком. В качестве другого и более интересного примера рассмотрим элементы таблицы, которая предназначена для представления игральных карт. Предположим, что узлы в ней состоят из двух слов, которые делятся на пять полей - TAG, SUIT, RANK, NEXT и TITLE:

(Так выглядит формат содержимого двух слов в компьютере MIX. Следует напомнить, что слово Б компьютере MIX состоит из пяти байтов и знака (см. раздел 1.3.1).)

в этом примере предполагается, что каждое слово имеет знак "+" (плюс). Адрес (address) узла, который также называется связью (link), указателем (pointer) или ссылкой (reference) на этщт узел, является адресом его первого слова. Адрес часто указывается относительно некоторой базовой ячейки памяти, но в этой главе для простоты предполагается, что адрес является абсолютным.

Любое поле внутри узла может содержать числа, буквы, ссылки или нечто другое, заданное программистом. В приведенном выше примере колода карт для раскладывания пасьянса может быть представлена следующим образом: TAG = 1 означает, что карта обращена лицевой стороной вниз, TAG = О - лицевой стороной вверх; SUIT = 1, 2, 3 или 4 означает масть карты, т. е. трефы, бубны, черви или пики соответственно; RANK = 1, 2, ..., 13 означает ранг карты, т. е. туз, двойка, ..., король; NEXT является связью с картой, расположенной под данной картой в этой же колоде; TITLE представляет предназначенное для печати имя карты из пяти символов. Типичная колода карт может выглядеть так, как показано ниже.

Карты

Представление в компьютере

2 ♦

♦ ♦

Адреса карт в компьютерном представлении показаны здесь в виде чисел 100, 386 и 242, хотя в данном примере они могли бы быть любыми, поскольку каждая карта связана со следующей картой, расположенной под ней. Обратите внимание на особую связь "Л" в узле 100. Здесь прописная греческая буква "лямбда" обозначает пустую связь, т. е. связь с несуществующим узлом. Пустая ссылка А используется в узле 100, так как десятка треф является самой нижней картой в колоде. В компьютере ссылка Л представлена легко распознаваемым значением, которое не может быть адресом узла. Вообще, предположим, что по адресу О никаких узлов нет, тогда Л практически всегда в программах для компьютера MIX может быть представлена как связь с нулевым значением адреса.

Введение понятия связи с другими элементами данных является чрезвычайно важной идеей в компьютерном программировании и ключевым способом представления сложных структур. При создании схемы представления узлов в компьютере связи обычно изображаются в виде стрелок. Тогда схема примера (2) будет выглядеть следующим образом:

ТОР •

При этом фактические адреса 242, 386 и 100 (которые в данном примере все равно не имеют большого значения) в схеме (3) не представлены. Используемое в электротехнике обозначение заземления здесь применяется для обозначения пустой связи в правой части схемы. Обратите внимание также, что в схеме (3) на самую верхнюю карту указывает стрелка ТОР. Здесь ТОР представляет собой переменную связи (link variable), которая часто называется указателем (pointer variable), т. е. переменной, значением которой является связь. Все ссылки на узлы в программе определяются непосредственно с помощью переменных связи (или констант связи) либо косвенно с помощью полей связи в других узлах.

Теперь рассмотрим самую важную часть системы обозначений - обозначение ссылки на поле внутри некоторого узла. Оно выглядит достаточно просто, поскольку для этого нужно лишь привести имя данного поля и указать вслед за ним в скобках связь с нужным узлом. Например, для случаев (1)-(3) это можно сделать так, как показано ниже:

RANK(IOO) = 10; SUIT(TOP) =2;

TITLE (TOP) = "uu2uD"; RANK (NEXT (TOP) )= 3. Читателю следует внимательно изучить эти примеры, поскольку такие обозначения полей будут применяться во многих других алгоритмах в настоящей и последующих главах. Чтобы пояснить смысл этой идеи, рассмотрим простой алгоритм, предназначенный для размещения с верхней стороны колоды новой карты с лицевой стороной, обращенной вверх. При этом допустим, что значение переменной связи NEWCARD содержит связь с новой картой.

А1. Установить NEXT(NEWCARD) Ч- ТОР. (Таким образом, значение поля связи в

новой карте будет указывать на верхнюю карту колоды.) А2. Установить ТОР <- NEWCARD. (ТОР по-прежнему будет указывать на верхнюю

карту колоды.)

A3. Установить TAG (ТОР) <- 0. (Карта обращена лицевой стороной вверх.)

В другом примере рассмотрим алгоритм для вычисления текущего количества карт в колоде.

81. Установить N ч- О, X <- ТОР. (Здесь N является целочисленной переменной, а X - переменной связи.)

82. Если X = Л, прекратить выполнение алгоритма; при этом значение N будет равно количеству карт в колоде.

83. Установить N f- N -I-1, X f- NEXT(X) и вернуться к шагу В2.

Обратите внимание на то, что в этих алгоритмах символьные имена используются для двух совершенно разных объектов: как имена переменных (ТОР, NEWCARD, N, X) и как имена полей (TAG, NEXT). Их не следует путать. Если F -это имя поля тлЬф Л - связь, то F(L)-это переменная. Но сам по себе символ F не является переменной, поскольку не обладает никаким значением, если только оно не является непустой связью.

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