Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной техники Кафедра вычислительной техники (специальность 220100). учебное пособие

Вид материала

Подобный материал:

1 ... 18 19 20 21 22 23 24 25 ... 44

0.8.3 Линейные списки

Линейный список - множество элементов с помощью которых свойства структуры задаются посредством линейного (одномерного) относительного расположения элементов. При этом k-й указатель непосредственно находится после (k-1)-го.

С таким списком возможны следующие операции:

Определение числа элементов в списке.
Доступ к k-му элементу для использования и/или изменения его содержимого.
Вставка нового элемента.
Удаление элемента.
Комбинация нескольких списков в один общий список.
Разделение списка на части.
Поиск.
Сортировка.

Пример линейного списка показан на рис. 0.4.39.

Рис. 0.1.8: Линейный список

0.8.4 Комбинированные списки

Очевидно, что процесс удаления может приводить к большим перемещениям данных. Пусть, например, надо удалить запись номер 1 (см. рис. 0.4.39). Это потребует удаления указателя p₁ и переписи всех далее расположенных указателей на освобождаемое место списка. Аналогичные проблемы возникают и при вставке в требуемое место.

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

Рис. 0.1.9: Комбинированный список

Достоинства таких списков:

 много проще вставка в требуемое место, например, вставка нового элемента между (n-1)-м и n-м сводится к перестройке двух указателей (рис. 0.4.41)

Рис. 0.1.10: Вставка элемента p_i в комбинированный список

 много проще удаление (рис. 0.4.42), которое сводится к перестройке трех указателей - одного указателя для собственно удаления и перестройке двух указателей для включения удаляемого элемента в список свободной памяти.

Рис. 0.1.11: Удаление элемента p₃ из комбинированного списка

 разделение и соединение списков упрощается,

 возможно формирование сложных структур данных,

 можно надстраивать переменное число списков различных длин,

 любой из элементов списка может быть заголовком некоторого другого списка, когда указатель на данные указывает на некоторый другой список,

 за счет использования нескольких указателей возможно формирование подсписков.

Недостатки:

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

 обычно требуемая последовательная обработка замедляется,

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

0.8.5 Циклические списки

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

Рис. 0.1.12: Циклический список

Ясно, что удаление или вставка элемента в таком списке также упрощаются.

0.9 ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ

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

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

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

При решении второй задачи, выполняемой чаще всего в интерактивном режиме, основное требование к средствам формирования и представления модели - удобство манипулирования.

Используются три основных типа 3D моделей:

 каркасное представление, когда тело описывается набором ребер,

 поверхностное, когда тело описывается набором ограничивающих его поверхностей,

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

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

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

Blog

0.8.3 Линейные списки

0.8.4 Комбинированные списки

0.8.5 Циклические списки

0.9 ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ