Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 48

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 48)

$ Ы 1 СТРУКТУРЫ ДАННЫХ И СТРУКТУРЫ ПАМЯТИ Прн построении информационного обеспечения автоматизированного проектирования важное значение имеет организация данных. Под структурой данных понимают совокупность содержательных связей, которые существуют между отдельными частями данных. Отображение данных в память приводит к необходимости реализации этих связей в виде структуры памяти. Реализация связей должна обеспечить эффективную обработку данных. Таким образом, структура памяти данных — это упорядоченное представление информации, необходимое для эффективной обработки ее прн работе программ решения задач конструкторского проектирования. ,т(ля задач автоматизированного проектирования характерно мно.гообразие видов действий над данными.

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

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

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

Поэтому вектор обеспечивает возможность перебора элементов памяти и прямого доступа к определенному элементу. Вектор Падается названием, длиной или верхней и нижней границей изменения индекса и размером элемента. Адрес произвольного элемента вектора определяется выражением: адрес злемента= базовый адрес+смещение относительно базы„ где базовый адрес — результат операции ссылки на название вектора, а смещение определяется по индексу элемента и границам. Разбиение вектора памяти на части перем е н н о й д л и н ы.

Для обеспечения эффективности обращения к областям векторной памяти ее можно разделить на части различной длины. Границы каждой области задаются указателями, которые обычно сводят в специальный справочный массив с последовательной и) В) В) з)в „, Ввюпор Вектаркая Векпьор Вокторяая Воепор Векторпоя указотопей Векторкая уяазаптояой памятпь уяазатьпоо память укааатопей памямь и разпорой паттяпть Г/ Гг ) > ь Рис. 1!.2. Способы организации ссылок иа области векторной памяти структурой. На рис. 11.2, н — г показаны различные способы организации ссылок иа области векторной памяти.

Для способа, показанного на рис. 11.2, а, указателем является адрес конца соответствующей области вектора памяти. Начальный н конечный адреса т'-й области вектор«ой памяти определяются так: начальный адрес=Гр(1 — !)+1, конечный адрес=ГВЯ. При способе, представленном на рис. 11.2, б, указатель определяет адрес первого элемента области, конец области задается специальным признаком. Для другого способа (рис. 11.2, в) в векторе Грд для каждой области задается пара указателей (начало и конец области).

Для варианта, изображенного на рнс. ! 1.2, г, задается адрес начала области векторной памяти и ее размер (Кь). Очевидно, что на рис.! 1.2, б, в иг области векторной памяти могут располагаться и не последовательно, что расширяет возможности данного способа. Связанная организация элементов памят и. При связанной организации в каждом элементе памяти имеется один или несколько указателей на местоположение другого или других элементов памяти (здесь элементом памяти может быть звено или последовательность звеньев).

Простейшей формой является однонаправленная связь, при которой каждый элемент памяти имеет ссылку на следующий. Здесь в составе элемента памяти существуют два 330 Номер «о«те«те Имя ьиемеитз тип ильме«те Атрибут цепи Имя цепи ХЗ Х4 Х! Има поля звена С524 025 ТЯ20 Элемент данных Длина поля звена, байт 233 поля: А — поле значения или указателя на элемент памяти, хранящий это значение, и  — поле указателя на следующий элемент памяти.

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

Структуры данных н нх организация в памяти ЭВйй. С и м в ол ьь Символ — это элемент некоторого конечного алфавита. Иногда символы (литеры) образуют отдельный тип данных. В общем случае символы используют для построения структурированных элементов данных. В памяти символ представляется квантом, длина которого У = — 1ойзп, где и — количество символов алфавита. Простой элемент данных. Простой элемент данных соответствует единичному данному определенного вида н представляет собой последовательность символов, принадлежащих некоторому алфавиту. Операция доступа н изменение выполняется над всем элементом целиком. Примером могут служить числа, литерные строки, указатели.

В памяти ЭВМ простой элемент отображается в квант или звено. Литерная строка может быть фиксированной и переменной длины. Для литерной строки используют последовательное и связанное представление в памяти. 3 а п и с ь. Запись — это совокупность простых элементов данных, каждый из которых содержит информацию определенного вида. Примером записи служит словосочетание входного языка описания схем. В памяти ЭВМ запись представляется звеном. Так как простые элементы данных могут требовать не одинаковое количество битов для их кодирования, то размеры полей памяти могут быть различными.

По отношению к записи возможны операции последовательного просмотра и непосредственного выбора элемента данных. В табл. 1!.1 показана структура словосочетания входного языка описания схем Таблица !1.1 казано в табл. 11.2. Неоднородные одномерные массивы, элементы которых имеют разную длину и тип. Такие массивы могут быть отображены в память, организованную, как показано на рис.

! 1.2, г. Каждую область (цепочку квантов) сопоставим элементу массива. Области могут располагаться в произвольных местах памяти. Указатель может представлять собой звено, поля которого определяют адрес элемента, его тип и длину, Для доступа к 1-му элементу вычисляется позиция 1-го указателя. Одно из его полей Массив граничыых указателей Мвссав массив Рх Х2 4з И Ха 8 х, к, х, И !О к< в виде списка цепей, определяемая синтаксисом этого языка. В этой таблице )г — имя звена, Х! — имя поля звена.

Выполняя операцию )( [Х[, можно просматривать атрибуты цепи, описанные в звене. Записав Х! [И, выделяем определенный элемент данных в звене. Например, Х2 [И дает информацию об имени элемента схемы, принадлежащего цепи, имя которой хранится в поле Х! И[. Однородные линейные массивы фиксиров а н н о й д л и н ы. Это одномерная последовательность элементов данных одного типа и размера, к каждому нз которых возможен индивидуальный доступ с помощью целого индекса, определяющего позицию элемента.

Такие массивы целесообразно отображать в последовательную память. При последовательном хранении данных включение и исключение элементов требуют переформирования вектора памяти. Неоднородные линейные массивы фнксир о в а н н о й д л и н ы. Нередко приходится оперировать сданными, элементы которых могут иметь разную длину. Например, элементами неоднородного массива в свою очередь являются однородные массивы различной длины. Если операции включения и исключения для таких данных не характерны, то можно использовать векторную память с указателями. Например, ориентированный граф аналитическим способом может быть задан множеством вершин Х = (х„х,, х,, х,) и множеством прямых отображений: РХ вЂ” (Ех„Ех„Рх„Ех,), где Рх, = (х„ха), Ех, ==- (хз), Ехз =- (х,, х„х,), Ех4 = (х,).

Массив ЕХ, определяя связи, которые существуют между вершинами графа, является неоднородным линейным массивом и может быть отображен в память в виде векторов переменной длины с граничными указателями, например как на рис. 1!.2, б. Отображение в память аналитического задания ориентированного графа по- (в простейшем случае он сам) определяет адрес элемента. Таким же образом представляются в памяти ЭВМ неоднородные линейные массивы, длина элементов которых может меняться динамически. Более сложные структуры данных и памяти (иерархические и т. и.) получаются, если элементы являются структурами.

Характеристики

Список файлов книги