Аверянов Современная информатика 2011

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

Рис. 8.4. Деревья: а – дерево; б – растущее дерево с корнем v0; 1, 2, …, 6 – уровнивершин; в– поддереворастущегодерева

В структурах данных типа графов и деревьев вершинам отве-

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

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

Однако кроме уровня фреймов, назначение которого – указание понятий предметной области и их связей, фрейм имеет более глу-

291

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

На рис. 8.5 показана типичная структура фрейма с пятью уровнями. За уровнем фреймов (1) следует уровень слотов (2).

Рис. 8.5. Структура фрейма: 1 – уровень фреймов; 2 – уровень слотов; 3 – уровень фасетов; 4 – уровень данных; 5 – уровень комментариев

В вершинах этого уровня фиксируются имена слотов. Обычно это названия свойств, характеристик того понятия, которое описывает данный фрейм. Например, если имя фрейма – «болт», то именами слотов могут быть «тип», «материал», «покрытие», «резьба», «размеры», «головка», «применение», «цена» и т.п. Каждый слот, как и фрейм, представляет собой иерархическую структуру, но с четырьмя уровнями.

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

1)явное задание характеристики;

2)задание характеристики по умолчанию;

3)действия при добавлении данных;

4)действия при удалении данных.

292

Из этих четырех фасетов, показанных на рис. 8.5, первые два фасета указывают способ задания описательной части слота.

Например, для фрейма «болт» характеристика «тип» по умолчанию может иметь значение «крепежный», а явно заданная – «установочный»; характеристика «материал» по умолчанию – «сталь», а явно заданная – «бронза» и т.д. Третий и четвертый фасеты составляют процедурную часть слота: они указывают, какие действия и где следует выполнить при изменениях описательной части слота для сохранения непротиворечивости всей сети данных.

Под уровнем фасетов размещается уровень собственно данных (4), на котором хранятся фактические данные, идентификаторы процедур и т.п. В качестве иллюстрации рассмотрим два примера:

1) имя фрейма – болт;	2) имя фрейма – болт;
имя слота – материал;	имя слота – покрытие;
фасет – значение по умолчанию;	фасет – явное задание;
значение данного – сталь.	значениеданного – хромированный.

Наконец, самый нижний уровень – уровень комментариев (5), имеющих фиксированную структуру и помогающих при обработке фреймов. Как показывает опыт, гибкая структура сетей фреймов удобна для хранения динамически изменяемых систем данных, но для работы с ними требуются более сложные программные средства.

8.2. Типичные виды работ с данными

Основными операциями со строками являются:

последовательный перебор символов строки;

включение нового символа (группы символов) в заданное место строки;

исключение символа (группы символов) из заданного места;

сцепление строк; разделение строки на несколько строк;

поиск вхождения заданной подстроки в строку и определение места этого вхождения.

Такие языки, как Алгол и Фортран, плохо подходят для выполнения этих операций, поэтому используют специальные языки: Лисп, Снобол и др. Строки часто хранятся в памяти компьютера в

293

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

Основной операцией с таблицами является выбор из таблиц. Ограничимся случаем таблиц функций у = y(х) одной действительной переменной x, полагая, что значения функции

y j = y(x j ) , j = 0, 1,…, n,	(8.1)
упорядочены по возрастанию аргумента (ключа), т.е.
x j+1 > x j , h j = x j+1 − x j > 0 , j = 0, 1, …, n – 1,	(8.2)

где h j – шаг аргумента x. Выбором из таблицы будем называть

нахождение такого промежутка, для которого
x j ≤ x < x j+1	(8.3)

или, что то же самое, нахождение такого значения индекса j, для которого выполняется неравенство (8.3).

В случае таблиц с постоянным шагом, когда h j = h = const , ин-

декс j легко находится по формуле
j =[(x − x0 ) / h] ,	(8.4)

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

j = f (x j ) ,

(8.5)

где f(x) – монотонно возрастающая функция х. Для регулярных таблиц также несложно найти

					j = [f(x)].					(8.6)
Пусть, например,
				eqj , j =	1	x j
x	j	= x	0			ln			( j = 0, 1, 2, …).	(8.7)
					q
						x0

294

Здесь q > 0 – некоторая константа. Тогда для произвольного x > x0 находим

		1		x
	j =						(8.8)
		q	ln	x		.
					0

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

	f (x j ) − j	≤ k , 0 < k <<n,	(8.9)
где п – длина таблицы, т.е. узел j отстоит от
~			(8.10)
	j =[ f (x j )]

не более чем на k << n узлов. Считают, что таблица имеет почти постоянный шаг, если

x j − (x0 + jh) ≤ kh , h =(xn − x0 ) / n , 0 ≤ k << n, (8.11)

где h – средний шаг таблицы. Здесь также искомый узел j отстоит от

~	=[(x − x0 ) / h]	(8.12)
j
не более, чем на k узлов.	В обоих случаях сначала находят		~	по
			j

формулам (8.10) или (8.12), а затем – искомый узел j прямым про-

смотром узлов x j с номерами от	~	− k	до	~	+ k .
	j			j

В общем случае таблиц с произвольным шагом скорость выбора определяется числом т просмотренных значений ключа (аргумента). Наиболее медленным является прямой перебор аргументов с начала таблицы (метод шестеренки), требующий в случае равномерно перемешанных значений аргумента в среднем m/2 просмотров. Если требуемые значения х упорядочены монотонно, то ускорение выбора достигается в методе скользящего начала. В этом методе запоминается последнее найденное j и при следующем об-

295

ращении просматривается таблица с началом в узле x j , т.е. просматриваются узлы x j , x j+1 , x j+2 , …, xn .

В более быстром методе двухступенчатого перебора таблица предварительно разбивается на сегменты с граничными узлами x0 ,

xk , x2k , … (k << n). Далее просмотром граничных узлов находится

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

ем таблицы n уменьшается до n / 2k . Процесс деления прекращается, когда остается таблица из одного узла. Можно показать, что число просмотров, а следовательно, и число арифметических операций в этом методе имеет порядок

M =O(log2 n) .

(8.13)

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

min m =an log2 n , а = const,

(8.14)

где п – число сортируемых элементов; a – постоянная, не зависящая от п. Следовательно, идеальный алгоритм должен иметь

M =O(n log2 n) , C = 0.

(8.15)

Практически, однако, для уменьшения М требуется увеличение С. Далее для определенности будем полагать, что массив чисел A(j)

(j = 1, 2, …, n) требуется упорядочить по возрастанию. В простей-

296

шем методе сортировки (иногда называемом «методом пузырька») просматривается массив A(j) и последовательно упорядочиваются пары элементов [A(j), A(j + 1), (j = 1, 2, …, n – 1)]. Сортировка считается завершенной, если при просмотре всего массива не потребовалось ни одного перемещения элементов. В наихудшем случае, когда первоначально массив А(j) упорядочен по убыванию, требу-

ется m = n2 сравнений элементов (ключей); в наилучшем случае, когда A(j) уже упорядочен по возрастанию, значение m ≈n , а в

среднем m ≈ 0,5n2 . Практически метод применим лишь для небольших п или для «почти упорядоченных» массивов с малыми отклонениями от монотонности.

В другом элементарном методе сначала отыскивается минимальный элемент массива {(A(1), A(2), …, A(n)}, который затем обменивается позициями с А(1). После этого процесс повторяется для массива {(A(2), А(3), ..., А(n)}, имеющего n – 1 элементов и т.д.

Число сравнений m ≈ 0,5n2 также достаточно велико.

Метод вставки основан на пополнении уже упорядоченного массива или его части новыми элементами. Пусть, например, часть массива A(1), A(2), …, A( j) уже упорядочена. Для пополнения его новым элементом A(j + 1) отыскивается такая позиция i, что A(i) ≤ ≤ A( j + 1) < A(i + 1); сюда вставляется элемент A( j + 1), а элементы A(i + l), A(i + 2), ..., A( j) сдвигаются на одну позицию вправо (вниз). Для упорядочения всего массива методом вставки требуется в

среднем m ≈ 0,25n2 сравнений и много сдвигов. (Сдвиги можно исключить, используя списковую организацию данных.)

Рассмотрим теперь объединение двух упорядоченных массивов А

и В. Для определенности будем полагать, что каждый массив содержит п элементов. Просматривая массив A, начиная с A(1), находим позицию j, в которую требуется вставить элемент В(1). После вставки В(1) продолжаем просмотр массива А с позиции j + 1 для нахождения позиции вставки В(2) и т.д. Как видно, для объединения массивов потребуется m = n сравнений, т.е. объединение можно выполнить очень быстро. Сдвиги элементов при объединении можно исключить, если дополнительно отвести для объединенного массива рабочую область памяти объемом С = 2n.

297

Метод вставки и объединение массивов используются в сортировке Шелла. В этом методе весь массив А разбивается на сегменты объемом n1 и каждый сегмент упорядочивается методом вставки.

Затем пары сегментов объединяются в сегменты объемом 2n1, 4n1 и т.д. Среднее число сравнений для метода Шелла

m ≈ 0,5n3/ 2 .

(8.16)

Все рассмотренные выше методы сортировки реализуются без дополнительных затрат памяти: С ≈0 . Рассмотрим теперь древовидную сортировку (название связано с тем, что сортировка может быть представлена в виде дерева). В этом алгоритме из массива А случайным образом извлекается некоторый элемент A(i). Затем элементы массива перераспределяются по двум сегментам так, что в первом сегменте оказываются элементы A( j) ≤ A(i) , a во вто-

ром – элементы A( j) > A(i) . Затем аналогично перераспределяются

элементы в каждом сегменте и т.д. Здесь уже C ≠0 , так как требуется запоминать границы образующихся сегментов, но число операций М близко к минимальному (8.15).

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

Наконец, в алгоритме двухступенчатой сортировки при первом просмотре массива находятся границы изменения элементов Amin ,

Amax . Далее диапазон [Amin , Amax ] делится на некоторое число К интервалов с границами

Ai = Amin +(Amax − Amin )i / K , i = 0, 1, 2, …, K, (8.17)

и при втором просмотре массива А находятся числа элементов A( j) в каждом интервале, а следовательно, и границы интервалов

после упорядочения. При третьем просмотре массива все элементы A( j) перераспределяются по своим интервалам. На этом первая

ступень сортировки завершается. На второй ступени каждый интервал упорядочивается методом пузырька. Наибольшая экономия

298

достигается, если элементы A( j) равномерно заполняют диапазон

[Amin , Amax ] , тогда
m ≈ 3n + K (n / K )2 ≈ n(3 + n / K ) , С ≈ K .	(8.18)

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

Рис. 8.6. Последовательность составления списка: 0 – до начала составления списка; 1 – после нахождения первого элемента; 2 – после нахождения второго элемента; 3 – после нахождения третьего элемента (L – заголовок списка, информационные поля заштрихованы)

Рассмотрим теперь алгоритм составления списков, ограничиваясь для простоты однонаправленными списками. Пусть из некоторого множества элементов {С( j); j = 1, 2, …, n} надо составить список элементов с заданным значением ключа: например, по списку персонала некоторого предприятия составить список инженер- но-технических работников. Каждый элемент С( j) , как уже указы-

валось, имеет информационное поле D( j) и адресное поле A( j) .

Перед составлением списка выделяется ячейка памяти L, называемая заголовком списка. Вначале полагают L = 0, а в дальнейшем в L будет храниться адрес j1 первого элемента списка. Просматри-

вая затем множество {A( j)}, последовательно находят элементы,

299

которые должны быть включены в список. После нахождения очередного такого элемента заголовок списка L переносится в адресное поле A( j) элемента, а адрес найденного элемента j – в заголо-

вок L. При таком способе составления первый найденный элемент будет в списке последним, а последний найденный элемент – первым (рис.8.6). Чтение списка начинается с заголовка и продолжается по адресам связи до нулевого адреса; нулевой заголовок означает, что список пуст.

Если же после элемента С( j) списка требуется вставить новый элемент С(i) , достаточно: 1) адресное поле A( j) переместить в адресное поле A(i) , 2) положить A( j) = i (рис. 8.7).

Рис. 8.7. Вставка нового элемента в список

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

8.3. Организация хранения данных

Основными единицами хранения данных в компьютерах считаются файлы, поэтому такую организацию хранения часто именуют файловой. Файловая организация данных обычно обеспечивается лингвистической поддержкой: многие языки программирования имеют операторы работы с файлами.

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

300