В Камаев - Технологии программирования

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

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

Биранрное дерево — дерево, в каждом узле которого происходит разветвление только на два поддерева (ветви): левое и правое.

Лесом называют конечное множество непересекающихся деревьев.

Граф — сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта, обладает следующими свойствами:

• на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

• каждый элемент может иметь связь с любым количеством других элементов;

• каждая связка (ребро, дуга) может иметь направление и вес.

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

Граф, все связи которого ориентированные, называют ориентированным графом, или орграфом; со всеми неориентированными связями — неориентированным графом; со связями обоих типов — смешанным графом.

Конкретные организации структур данных и алгоритмы реализации операций с ними рассмотрены в [21, 23, 25].

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

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

Пусть требуется спроектировать программу электронной таблицы. Такой проект выполнила фирма "Borland Inc", когда ей понадобилась демонстрационная программа. Обоснование потребности и цели разработки этого проекта были рассмотрены в гл. 2.

Что видит пользователь при работе с электронной таблицей? — Огромный двухмерный массив клеток.

Что пользователь может записать в клетки? — Числовые значения, строки текстов и формулы. Каждая клетка также должна хранить информацию о формате вывода числовых значений (форматы: целый, денежный, научный и т. д.). Значит, каждая клетка должна содержать атрибут того, что находится в клетке: пустая клетка, числовое значение в клетке, строка текста, корректная формула, некорректная формула. Пусть информация о значении числа имеет тип расширенный, вещественный (10 байт); строки текста содержат до 79 символов; информация формулы состоит из поля со значением, рассчитанного по формуле (10 байт), а также поля текста формулы (79 байт). Самая длинная информация у клетки с формулой: информация формата (2 байта), значение, рассчитанное по формуле (10 байт), поле текста формулы (79 байт). Итого длина информации клетки составляет 91 байт.

Пусть программа будет работать с электронной таблицей размером 100 × 100 клеток. Тогда информация электронной таблицы в случае использования структуры данных в виде статической матрицы занимает 91 × 100 × 100 байт = 910 000 байт ≈ 889 кбайт.

Требуемый объем для размещения структуры превышает стандартную память компьютера класса IBM PC XT — 640 кбайт, поэтому надо отказаться от использования структуры данных в виде статической матрицы.

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