Структура данных и управления

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

Входные и выходные данные всегда расположены вне тела данного программного компонента [в оперативной (ОП) или внешней (ВП) памяти].

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

Если какие-либо данные являются одновременно и входными, и выходными, то их называют модифицируе­мыми данными (рис. 1.1). В общем случае входные данные 1 подготавлива­ются пользователем или, являются результатом ра­боты раннее выполненных программных единиц. Вы­ходные данные 2 могут предназначаться пользо­вателю или (и) для после­дующей программной об­работки.

Простые типы данных. Структуры данных, обра­батываемых ПО САПР, чрезвычайно разнообраз­ны. Поэтому эффективная

реализация методов и алгоритмов автоматизированного проектирования (АП) требует глубокого знания основ­ных способов представления данных в ЭВМ.

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

Простыми типами данных, представленными в совре­менных языках программирования, являются: 1) ЦЕ­ЛОЕ, 2) ВЕЩЕСТВЕННОЕ, 3) БУЛЕВО (ЛОГИЧЕ­СКОЕ), 4) СТРОКА, 5) УКАЗАТЕЛЬ. В большинстве ЭВМ эти типы данных — «встроенные», т. е. имеются ма­шинные команды, непосредственно их обрабатывающие.

Данные типа ЦЕЛОЕ и ВЕЩЕСТВЕННОЕ опи­сывают десятичные числа (как положительные, так и отрицательные) и различаются способом представления в ЭВМ.

Примечание. В большинстве современных ЭВМ операции над данными типа ЦЕЛОЕ выполняются значительно быстрее, чем над данными типа ВЕЩЕСТВЕННОЕ. Особенно существен­на разница в быстродействии для тех микро- и мини-ЭВМ, у ко­торых отсутствуют машинные команды арифметики с плавающей точкой.

Диапазоны представления чисел данными этих типов ограничены; кроме того, конечная длина разрядной сетки ЭВМ обусловливает наличие погрешности отображения вещественных чисел. Эти обстоятельства необходимо всегда учитывать при программировании обработки дан­ных вещественного типа с большим разбросом порядков.

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

Данные типа БУЛЕВО (ЛОГИЧЕСКОЕ) пред­назначены для описания двоичных (булевых) величин. Это могут быть либо одиночные биты (разряды) с воз­можными значениями «истина» или «ложь», либо цепоч­ки битов. Данные этого типа обычно используются для управления ходом вычислительного процесса в програм­мах и в качестве значений логических выражений флаж­ков условий. В ПО структурного синтеза данными этого типа описываются многие свойства проектируемых объектов. Операции над данными типа БУЛЕВО (И, ИЛИ, НЕ и др.) — наиболее быстрые.

К данным типа СТРОКА относятся любые тексты, составленные из допустимого для данной ЭВМ набора литер. В этот набор обычно входят символы есте­ственных языков, десятичные цифры и ряд специальных символов. Каждая литера данных типа СТРОКА пред­ставляется в ЭВМ последовательностью битов, опреде­ляемой принятым для данной ЭВМ стандартом. Литеры, составляющие текст, обычно располагаются в смежных участках памяти в прямом порядке. Данные типа СТРО­КА могут иметь фиксированную или переменную длину (ограниченную некоторым пределом).

Данные типа УКАЗАТЕЛЬ (ССЫЛКА) пред­назначены для ссылки на элементы данных в тех слу­чаях, когда невозможно использование имен элементов данных. Физически они представляют собой адрес ука­зываемых данных или содержат информацию, позволяю­щую этот адрес вычислить. Основное назначение данных типа УКАЗАТЕЛЬ — предоставление программисту на алгоритмических языках высокого уровня средств для создания сложных структур данных.

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

Элементарными (вырожденными) структурами дан­ных являются константа и переменная.

Константа характеризуется фиксированными име­нем, типом и значением.

Переменная имеет фиксированные имя и тип, но переменное значение.

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

Примечание. Одно- и двумерные массивы позволяют непо­средственно отобразить в ЭВМ вектора и матрицы. Однако представление больших разреженных матриц в виде двумерных массивов влечет

за собой неоправданные потери памяти и ма­шинного времени из-за необходимости хранения и обработки большого количества нулевых элементов. Поэтому для пред­ставления разреженных матриц в ЭВМ необходимо использо­вать иные структуры данных.

Требование обязательной однородности всех элемен­тов массива (т. е. одинаковости типа всех переменных, составляющих массив) часто неудобно для представле­ния данных, обрабатываемых ПО САПР.

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

Пример записи. Одной из основных конструкций входного языка ПО схемотехнического проектирования является описание эле­мента эквивалентной схемы. Такая конструкция может иметь следующий вид [1]: С15 (6, 8) = 1. 5 МКФ,

С — имя элемента (емкость), 15 — его номер, 6 и 8—номера узлов подключения, 1.5 — параметр элемента; символы МКФ указывают единицу измерения параметра.

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

1 элемент — схемы

2 идентификатор

3 имя СТРОКА (3)

3 номер ЦЕЛОЕ

2 узлы

3 нач — узел ЦЕЛОЕ

3 кон—узел ЦЕЛОЕ

2 параметр

3 значение ВЕЩЕСТВЕННОЕ

3 размерность СТРОКА (3)

Доступ к информации, содержащейся в записи, осу­ществляется с помощью составных имен. Так, составное имя «элемент — схемы, идентификатор» позволяет ссы­латься на запись, состоящую из полей имени и номера элемента. Имя «элемент — схемы, параметр, значение» идентифицирует переменную типа ВЕЩЕСТВЕННОЕ. На рис. 1.2 показано размещение записи в памяти ЭВМ. (она занимает там сплошной участок).

Т а б л и ц а — объединение структур данных типа за­пись. Таблица аналогична двумерному массиву, но ее столбцы могут иметь различные типы.

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

Пример фрейма. Для представления знаний о витой пружине в САПР машиностро­ения может использоваться фрейм ПРУЖИНА. Поля этого фрейма — диаметр и шаг на­мотки пружины, диаметр прово­локи, количество витков, свой­ства материала проволоки и др. Отношениями в этом фрейме будут уравнения, составляющие математическую модель пружи­ны. Фреймы ПРУЖИНА, ШТОК, РЫЧАГ и др., объеди­ненные в сеть, составляют мо­дель предметной области САПР машиностроения.

В теории программирования фрейм называют абст­рактным типом данных.

Все рассмотренные выше структуры данных характе­ризуются сплошным расположением в памяти ЭВМ. Это часто неудобно из-за необходимости заранее фиксировать размер области оперативной памяти, отводимой под размещение этих структур. В большинстве случаев этот , размер априорно неизвестен и определяется только в процессе выполнения программ. Поэтому более универ­сальны структуры данных, ориентированные на цепное представление в памяти ЭВМ. К ним относятся стек, очередь, линейный список, дерево и др. Объединение записей в эти структуры осуществляется с помощью пе­ременных типа УКАЗАТЕЛЬ, размещаемых в полях за­писей.

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

Рис. 1.3

в последней записи пуст. Основными операциями над стеком являются ЧИТАТЬ ВЕРШИНУ, ДОБАВИТЬ (рис. 1.3,6) и УДАЛИТЬ (рис. 1.3, в). В стеке реали­зуется принцип обработки «последним пришел — пер­вым ушел». Наиболее широко в ПО САПР стековая ор­ганизация данных используется при трансляции входных языков и при управлении ОП.

Очередь — линейная последовательность записей, связанных указателями, но доступ к ее записям осущест­вляется с начала и конца (рис. 1.4, а). Добавлять записи можно только в конец очереди (рис. 1,4,6), а читать и удалять записи — только с начала очереди (удаляют самую старую запись) (рис. 1.4,в). Обработка данных

Рис. 1.4. Представление очереди (а) и операции над очередью ДОБАВИТЬ (б) и УДАЛИТЬ (в)

в очереди строится по принципу «первым пришел — пер­вым ушел». Эта структура часто используется для об­мена данными между программными компонентами про­цессоров входных языков САПР. Объединение отдельных записей в очередь — это один из самых распространен­ных способов организации данных во внешней памяти ЭВМ.

Линейный список — наиболее универсальная структура данных, в нем доступна для чтения и удале­ния любая запись, более того, новая запись может быть включена между двумя любыми соседними записями списка. На рис. 1.5, а показана физическая реализация двунаправленного линейного списка. Встречное направ­ление указателей позволяет осуществить в таком списке поиск записей с обеих сторон.

Во многих алгоритмах САПР требуется упорядочение записей по какому-либо параметру. Линейный список дает возможность реализовывать алгоритмы сортировки (упорядочения) без физического перемещения записей в ОП только путем соответствующей корректировки ука­зателей. В этой структуре легко осуществляются опера­ции удаления и включения новых записей без нарушения упорядоченности списка (рис. 1.5,6, в). В отдельных при­ложениях для повышения скорости обработки необходи­мо упорядочение записей более чем по одному парамет­ру (в этом случае возможно, не перемещая и не дубли­руя записи, организовать еще несколько списков, добав­ляя в записи новые поля с соответствующими указате­лями) .