Структуры данных.

Первое, о чем необходимо позаботиться при работе со ссылочными структурами, — как построить звено, т.е. сколько компьютерных слов используется для одного звена, сколько полей данных мы собираемся иметь в звене и каков должен быть размер этих полей. На рис. 1.2.1 эти характеристики звена опущены, однако разумный выбор может состоять в использовании двух слов для звена (или ячейки), разделенного на три поля, функции которых будут разъяснены ниже: поле типа Т, поле элемента Е и поле ссылки S, как это показано на рис. 1.2.2.

Рис. 1.2.2. Внутреннее представление ячейки, или звена.

Рассмотрим список общего вида . Компьютерное представление этого списка состоит из ячеек, связанных через их ноля ссылок, вместе с предполагаемыми уже данными

представлениями каждого из значений являющихся в свою очередь списками. Поле ссылки ячейки содержит адрес ячейки а поле ссылки ячейки содержит 0. (Разумеется, предполагается, что 0 не является адресом никакой ячейки.) Поле типа i-й ячейки содержит нуль или единицу в зависимости от того, является атомом или списком. Если является атомом, то поле элемента i-й ячейки содержит если список, то поле элемента i-й ячейки содержит координаты некоторого представления списка Координаты списка это адрес первой ячейки его представления. В соответствии с этим внутреннее представление целого числа изображенного на рис. 1.2.1, является таким, как показано на рис. 1.2.3.

Рис. 1.2.3. Полное внутреннее списочное представление целого числа на рис. 1.2.1.

Раз такое решение принято, то во время вычислений все неиспользуемые звенья связаны вместе в произвольном порядке и образуют список свободного места. Когда требуется новое звено, первое звено списка свободного места отщепляется и присоединяется к соответствующему списку данных. Когда список данных становится не нужным в дальнейших вычислениях, его звенья присоединяются к голове списка свободного места. В упражнениях по программированию 1 и 2 к этому параграфу (в конце главы, перед библиографией) читателю поручается написать некоторые из этих процедур. Как для новичка, так и для опытного программиста представляет интерес техника, позволяющая на языках высокого уровня проверить значение данного поля и/или обновить его, не разрушая имеющейся в данном слове информации. Мы разъясним это на следующем примере, использующем десятичную систему счисления.

Пример. Предположим, что число хранится в машинном слове, разделенном на три поля, содержащих 1, 3 и 5 десятичных цифр соответственно, т.е. это число можно представлять себе как 1-234-56789, хотя компьютер воспринимает это девятизначное число как единое целое. Для того чтобы изменить

значение центрального трехсимвольного поля с 234, например, на 432, мы должны сделать следующее:

Разделить число на , получив частное и остаток

Затем разделить на , получив (в этот момент значение несущественно).

Затем умножить на 1000 и прибавить число 432 (которое должно заменить число 234), чтобы получить промежуточный результат

Наконец, умножить на и прибавить чтобы получить число 143256789 в требуемом измененном виде.

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