ПОИСК Статьи Чертежи Таблицы Структуры данных из "Машинная графика и автоматизация проектирования " Одним из наиболее важных вопросов программирования, связанных с автоматическим проектированием, является описание соотношений между -объектами, определенными в программе. В предыдущих разделах, описывающих блоки данных, было показано, -как можно представить объекты в памяти ЭВМ, а также как анализирующая программа последовательным просмотром всех блоков данных способна выявить объекты одного класса. Однако для сложных графических архивов, содержащих сотни и даже тысячи объектов, такой просмотр из-за недопустимого возрастания времени анализа становится практически невозможным. Процедуры просмотра усложняются еще больше, когда блоки данных записаны в памяти не подряд. Поэтому оказалось необходимым дополнить метод основных блоков данных идеей указателей , что привело к созданию связанных структур данных. При использовании таких структур данных имеющиеся в каждом блоке указатели связывают этот блок с другими, описывающими объекты с подобными характеристиками. Так ЭВМ становятся понятны связи между объектами, заданные своими блоками данных, а также между объектами и вычислительными программами. Рассмотрим подробнее, как структуры данных описывают подобные связи. [c.100] Начнем рассмотрение с основных аспектов автоматизированного проектирования. Это позволит сформулировать требования к программированию для такого проектирования, которое существенно отличается от тре1бований для задач, соответствующих пакетной обработке данных. [c.100] В автоматическое или машинное проектирование входят следующие основные работы и операции представление исследуемой физической системы в виде модели, ее анализ, изображение в некотором представлении этой модели и результатов вычислений, связанных с ней, а также формирование, аннулирование и изменение ее отдельных элементов. При этом физическая система может моделироваться с любой степенью глубины и точности. Например, при анализе электронных схем может удовлетворять модель с сосредоточенными постоянными, соответствующая функционально-электрической схеме. В свою очередь можно представить характеристики поведения каждого элемента схемы уравнениями или эмпирическими зависимостями с любой степенью точности. Очевидно, что моделировать следует лишь существенные характеристики системы. Например, если в форме аналитических уравнений накапливается информация о форме корпуса корабля, то вряд ли имеет смысл хранить данные о материале, из которого этот корпус сделан, удельном весе этого материала или его цвете. Концепции моделирования с помощью ЭВМ в этом плане ничем не отличаются от общих концепций моделирования, повседневно используемых при проектировании и инженерных исследованиях. [c.100] Способность анализировать модель является важной, фундаментальной особенностью, отличающей действительно автоматизированную систему проектирования от обычной системы, в которой ЭВМ использу--ется лишь для вывода графических данных. Эта способность требует, чтобы ЭВМ понимала математическое описание модели и могла анали-j зировать модель в терминах уравнений или алгоритмов. Бывают, конечно, случаи, когда графическая система человек—машина попользуется в проектировании, основанном исключительно на эстетических оценках проектировщика. Однако гораздо чаще при автоматизированном проектировании требуется, чтобы сама ЭВМ по запросу проектировщика могла анализировать характеристики модели. [c.101] Возможность изображать исследуемую модель является, конечно, основанием для использования графических систем. Изображение, выведенное на экран, может быть существенно проще самой модели. Например, ЭВМ может изобразить трехмерный корпус корабля как наложение простых сечений. Аналогично электронная схема может быть изображена набором простых символов, тогда как работа каждого элемента, опи-. сывается точными уравнениями, хранящимися в памяти ЭВМ. [c.101] Необходимо также, чтобы ЭВМ по желанию оператора могла создавать новые, устранять или изменять существующие элементы модели. Эта способность затрагивает коренные особенности процесса проектирования, включающие постепенное улучшение и уточнение модели по мере исследования различных ее вариантов. [c.101] Из главных особенностей автоматизированной системы проектирования, часть которых была описана в предыдущем разделе, вытекает множество требований к программированию. Эти требования существенно отличаются от требований к программированию задач при пакетной обработке данных. Именно они привели к новым идеям в развитии программного обеспечения, таким, как сложные структуры данных и работа со списочными структурами. Традиционное программирование характеризует значительная жесткость требований к формату, структурам и размеру элементов в памяти. Как правило, различные части программ обрабатываются в указанном порядке. Для реализации заранее запланированного выбора вариантов в программу необходимо ввести точки ветвления. Число переменных должно быть оговорено заранее я его нельзя изменять по ходу выполнения программы. Более того, необходимо заранее предвидеть объем памяти для каждой переменной и объявить его специальным оператором размерности. Если реальные требования по памяти заранее не известны, то приходится выделять такой объем памяти, которого должно хватить при максимальных требованиях в рамках решения данной задачи. При этом значительная часть запрошенного объема памяти может оказаться не использованной. [c.101] Оператор в начале не знает даже размеров самой модели — эта характеристика появляется также в процессе проектирования. Например, при моделировании моста или каркаса какого-нибудь сооружения в проектируемую конструкцию может быть введено любое количество ргэстяжек и распорок. [c.102] После всего сказанного рассмотрим, как сложные структуры данных обеспечивают гибкость при формировании модели и ее анализе. [c.102] Сами физические объекты — основной предмет моделирования структурами данных — представляются уже описанными блоками данных, а основные соотношения между объектами задаются с помощью указателей. Указатель — это слово, находящееся в специальном мёсте блока данных. Указатель содержит адрес другого блока, связанного с этим блоком (рис. 77). Если использовать подпрограммный аппарат анализа, основная программа может в этом случае перейти от одного блока к другому, следуя указателю, содержащемуся в шестой строке блока. [c.102] Другой, в некоторых случаях полезной структурой, оказываются блоки с двусторонними указателями (рис. 81). В таком случае каждому указателю от одного блока к другому соответствует указатель противоположного направления. При этом анализирующая программа может проходить блоки данных последовательно в любом из двух направлений. Так, если от объекта С есть ссылка на объект В, то от объекта В должна быть ссылка на объект С. Как и в предыдущем случае, строка блока, в которой находится указатель, сигнализирует о типе указателя каково его направление — прямое или противоположное. [c.104] На рис. 82 показан еще один вариант использования указателя так называемая кольцевая структура. Она получается, если в последний бло1К данных поместить указатель, адресующий вновь первый блок последовательности. В этом случае анализирующая программа, переходя от блока к блоку по указателям лишь одного направления, может достигнуть любого блока в кольце, с какого бы блока она ни начала. Программа запоминает адрес или идентификатор того блока, с кото-рего она начала работу, и таким образом узнает, когда все объекты обработаны. [c.104] Двумя наиболее распространенными формами организации данных являются ассоциативная и иерархическая. Рассмотрим теперь, как структуры данных помогают работать с этими двумя типами организации. [c.105] Используя такого рода структуры данных, программа способна, например, после указания световым пером на изображение какого-то автомобиля воспроизвести все автомобили на экране. Для нахождения блоков данных остальных автомобилей ей достаточно следовать по указателям. Аналогично на экране можно изобразить только транспортные средства зеленого цвета и т. д. [c.106] Третья строка в каждом блоке данных (рис. 86) содержит указатель объекта следующего яруса вниз (более младшего), четвертая строка — указатель объекта следующего яруса вверх более старшего), а последняя строка — указатель- соседнего объекта этого же яруса. Так, если нео1бходимо найти все части крыла, то программа проследует по указателю в третьей строке на блок лонжероны , а затем по указателям в последних строках блоков на блоки остальных компонентов крыла. [c.106] Если же надо найти в самолете какого типа и в каком узле содержится данное ребро жесткости, то программа проследует по указателю в четвертой строке блока ребро жесткости на блок крыло , а по указателю в четвертой строке этого блока яа блок самолет D -3. [c.106] Иа рис. 86 показана не единственная возможная реализация иерархической схемы рис. 85, а лишь одна, удобная для иллюстрации. [c.106] ВИИ с заданным числом указателей в каждом блоке. Более того, должна иметься возможность изменения длины блоков во время решения задачи, так как подчиненные объекты могут добавляться и устраняться. [c.108] Динамическая гибкость метода списковых структур наглядно демонстрируется иерархической структурой данных (рис. 86). По ходу работы шрограммы в режиме взаимодействия можно по желанию добавлять новые блоки данных до тех пор, пока системные программы не исчерпают все ресурсы свободной памяти. Пользователь связывает каждый новый блок с уже существующей структурой данных. Если добавляемый объект ниже по иерархии, то указатель связи помещается в четвертой строке нового блока. Кроме того, новый блок включается в кольцо объектов того же уровня с помощью указателей в последних строках. В значительной степени аналогично может быть аннулирован уже существующий блок данных. В этом случае кольцо объектов одного уровня замыкается для сохранения непрерывности. Программа может также автоматически аннулировать все подчиненные объекты, не следуя вниз по указателям в третьей строке блока. Обратим внимание на то, что устранение узлового блока, например блока крыло (рис. 86), разрывает связь вверх для его соседей по уровню. Этого можно избежать, если на месте устраненного узлового блока сохранить фиктивный или нулевой блок вместе со тасеми связанными с ним указателями. [c.108] Для введения нового и устранения уже существующего блока в структуре данных, как это было только что описано, требуются специальные алгоритмы. Помимо таких операций, часто требуется изменить содержимое существующего блока или просто считать данные из некоторых блоков. В основе этих функций лежат подпрограммы слежения по уровням, а также внутри одного уровня и подпрограммы опознавания нужного блока. Алгоритмы этой группы аналогичны алгоритмам, описанным в разделах о блоках данных, и выполняются точно так же под управлением человека-оператора. [c.108] Вернуться к основной статье