Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

дыи элемент вторую ссылку — на предыдущий элемент, то получится

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

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

Над списками можно выполнять различные операции. Список операций над однонаправленным линейным списком и их реализа­ ция были рассмотрены в разд. 8.

14.2. Бинарные деревья

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

На рис. 57 приведен алгоритм построения и пример бинарного дерева (его корень обычно располагается сверху).

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

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

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

220

Корень

J1=2*i

_Z^X J

		2, 3, 4, 5	- вершины
8	10	6, 7, 8, 9,	10-листья

Пример двоичного дерева для size =10

Рис. 57. Алгоритм построения и пример бинарного дерева

14.3. Очереди и их частные разновидности

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

На практике часто используются более простые, частные слу­ чаи универсальной очереди - очереди типа FIFO и L1FO (стек). Оче­ редь типа FIFO (First Input - First Output : первым занесен ~ первым извлечен) получается, если операция добавления элемента в очередь разрешена только для одного конца очереди, а операция выборки элемента - только для другого конца очереди.

Стек - это частный случай однонаправленного линейного спи­ ска, добавление элементов в который и выборка выполняются только с одного конца, называемого вершиной стека. Говорят, что стек реализует дисциплину обслуживания LIFO (Last Input - First Output : последним занесен — первым извлечен). Стеки широко при­ меняются в программировании, компиляторах, рекурсивных алго­ ритмах и т.п.

221

14.4.Реализация динамических структур

спомощью массивов

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

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

Для реализации очереди требуются две переменных целого ти­ па - для хранения индексов элементов массива, являющихся нача­

лом и концом очереди.
	Для		реализации			линейного			списка на базе массива	требуется
вспомогательный					массив целых чисел и еще одна переменная (мас­
сив данных, вспомогательный								массив и вспомогательную		перемен­
ную можно оформить в виде полей структуры), например:
10	25	20	6	21	8	1	30	- массив данных
1	2	3	4	5	6	7	-1	-	вспомогательный массив
0								-	индекс первого элемента в списке

/-ЫЙ элемент вспомогательного массива содержит для каждого /-го элемента массива данных индекс следующего за ним элемента. От­ рицательное число используется как признак конца списка. Тот же массив после сортировки будет иметь следующий вид:

10	25	20	6	21	8	1	30	- массив данных
2	7	4	5	1	0	3	-1	- вспомогательный массив
6								~ индекс первого элемента в списке

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

отсутствие соответствующего поддерева. Как и в предыдущем случае, массив данных и вспомогательные массивы можно офор-

222

мить как поля структуры. В качестве упражнения можно предлага­ ется самостоятельно и для этого случая составить иллюстрирующий пример.

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

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

15. СОРТИРОВКА

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

Зависимость выбора алгоритмов решения задачи от структуры данных - явление довольно частое. В случае сортировки эта зависи­ мость настолько сильна, что методы сортировки обычно разделяют на две категории:

•сортировка массивов;

•сортировка последовательных файлов.

Эти две разновидности сортировок часто называют соответст­ венно внутренней (сортировка массивов) и внешней (сортировка файлов) сортировками. Это объясняется тем, что массивы распола­ гаются во "внутренней" (оперативной) памяти ЭВМ и для нее харак­ терен быстрый произвольный доступ (прямой доступ). Файлы же хранятся в более медленной, но более вместительной "внешней" па­ мяти, т.е. на запоминающих устройствах с механическим передви­ жением (магнитных дисках и лентах). Указанное существенное раз­ личие можно наглядно продемонстрировать на примере сортировки пронумерованных карточек.

1. Представление карточек в виде массива с прямым доступом (рис. 58) означает, что все карточки одновременно видны и равно­ доступны.

0	8	9	1
2	6	4	5

Рис. 58. Произвольный (прямой) доступ

2. Представление карточек в виде последовательного файла (рис. 59) предполагает, что видна и доступна только верхняя кар­ точка. Чтобы добраться до остальных карточек необходимо, напри­ мер, перекладывать карточки в колоде по одной спереди назад.

Очевидно, что такое ограничение приведет к существенному изменению методов сортировки.

224

ir

Рис. 59. Последовательный доступ

Терминология и обозначения. Будем считать, что нам даны элементы

Сортировка означает перестановку этих	элементов в таком порядке
что при заданной функции упорядочения	f справедливо отношение
f(a,,)<f(a,,)<...<f(a,J

Вчастном случае, функция упорядочения может не вычис­ ляться по какому-либо специальному правилу, а может содержаться

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

Всоответствии со сказанным, определим структурный тип ELEMENT, который будем использовать в последующих алгоритмах сортировки, следующим образом:

/ / Структурный		тип для	элемента	массива
struct	ELEMENT
Int		key;	//	Ключ	сортировки
//	Описание	других	компонентов		элемента
};

Здесь "другие компоненты" - это все существенные данные об эле­ менте, а поле key - ключ служит лишь для идентификации элементов при сортировке.

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

225

рядоченный тип).

Метод сортировки называется устойчивым, если относитель­ ный порядок элементов с одинаковыми ключами не меняется при сортировке. Устойчивость сортировки часто бывает желательной, если элементы упорядочены по каким-то вторичным ключам, т.е. по свойствам, не отраженным в первичном ключе.

15.1. Сортировка массивов

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

Удобной мерой эффективности алгоритмов сортировки "на месте" является число

с(Compare)

необходимых сравнений ключей и число

М(Move)

необходимых пересылок элементов.

Хотя эффективные алгоритмы сортировки требуют порядка

сравнений, где N - число элементов сортируемого массива, все же сначала обсудим несколько более простых методов сортировки, ко­ торые требуют порядка

С-TV'

сравнений, по следующим трем причинам.

1. Простые методы особенно хорошо подходят для разъясне­ ния свойств большинства принципов сортировки.

2.Программы, основанные на этих методах, легки для пони­ мания и коротки (следует помнить, что программы также занимают память!).

3.Хотя сложные алгоритмы требуют меньшего числа опера­ ций, но эти операции более сложны. Поэтому при достаточно ма­ лых значениях Л^ простые методы работают также быстро, но их не следует использовать при больших N,

Методы сортировки массивов "на месте" можно разбить на три основных класса:

226

•сортировка выбором;

•сортировка вставками;

•сортировка обменом.

Рассматриваемые программы будут работать с указателем агг

на массив, компоненты которого нужно отсортировать "на месте", и структурным типом ELEMENT^ определенным выше.

Указатель агг на массив можно определить так:

±пЬ	/ /	Размер	массива
// Указатель	на сортируемый		массив
ELEMENT	*агг	= new	ELEMENT[ s } ;

В простейшем случае элементы массива

агг[ О ]г	arrf 1 ],	...,	arr[ s-1 ]
будем располагать в порядке не убывания			их ключей:
arr[k^],key	< arr[k2^.key	< ... <	arr[k^]Леу

Сортировка выбором. Выбирается элемент с наибольшим значением ключа и меняется местами с последним. Затем то же са­ мое повторяется для 5-1 первого элемента, найденный элемент с наибольшим значением ключа меняется местами с предпоследним элементом и т.д. (рис. 60).

max	s-1
max	s-2 s-1
и т.д.

Рис. 60. Сортировка простым выбором

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

227

1	1-1			S-1
— \	\	1	г	i= 1,2, ..., s-1

Вставим на подходящее место или оставим на месте

Рис. 61. Сортировка простыми включениями

Сортировка обменом. Основная характеристика процесса - обмен местами двух соседних элементов (перестановка), если они расположены не так, как требует отсортированный массив (рис. 62). На приведенном рисунке изображен только один шаг (просмотр). Сортировка массива гарантируется после s-\ просмотра.

S-2 S-1

и т.д.

Рис. 62. Сортировка простым обменом

15.2. Сортировка массива простым выбором

Метод основан на следующем правиле.

1.Выбирается элемент с наибольшим значением ключа.

2.Он меняется местами с последним элементом агг[ 5-1 ]. Эти операции затем повторяются с оставшимися первыми ^-1 элемента­ ми, затем - с s-2 первыми элементами и т.д. до тех пор, пока не ос­ танется только один первый элемент - наименьший. Пример сорти­ ровки массива простым выбором приведен на рис. 63, в соответст­

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

/ /	Просмотр	неотсортированных	начальных	сегментов	массива	slze-1
//	(вначале	- весь массив,	затем - сегмент из		первых

//элементов и т,д.)

£о1т( L	-= size-1;	L >= 1;		L—	;
{	Присвоить	indmax	и	max	индекс		и	значение	элемента
//
//	массива	с наибольшим			значением			ключа	из
//	агг[ О	]..arrf	L	]
// . . .		местами	агг[		indmax	]	и	агг[ L	]
// Поменять
arrf	indmax	] = arrf		L ];	arrf	L	]	= max;

228

Начальные значения	44	55	12	42	94	18	06	67
ключей элементов	44	55	12	42	67	18	06	1 94
массива
		^			м	«"1
	44		12	42	06		67	94
		55
	44	18	12	42	06 1	55	67	94
	м—	18	12	42 1	44	55	67	94
	Об
			."1	Ф
	06	18		42	44	55	67	94
	06		18	42	44	55	67	94
	06	12	18	42	44	55	67	94

Рис. 63. Сортировка массива простым выбором

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

/*

TestSortArr.срр.

Тестирование

сортировки

динамически

Файл

размещенных

массивов

с

использованием

различных

методов.

файле

Определение

методов

сортировки

приведено

в

SortArr.срр.

Функций

размещения

массива

в

динамической

па­

Определение

мяти и освобождения

занятой

динамической

памяти

находится

в

файле

А1 ocFreeDM. срр,

ввода и печати

значений

элементов

мас­

Определение

функций

сива

дано

в

файле

SortlnOut.срр.

проекта

дан

в файле

Sor­

Заголовочный

файл

программного

tArr.

h.

В.Г.

Консольное

приложение.

Visual

C++ 6

Давыдов

Ч

// Включаемый

файл

программного

проекта

для

сортировки

//массивов

^include "SortArr.h"

int main (	//	Возвращает		О при		успехе
±nt	ArgCr	// ARGument		Counter:		число		строке
		//	аргументов		в	командной
// ARGument Value: массив			указателей		на	аргументы
//	командной строки	(ArgV[ О ]		-	.ехе	файл,	в
//	интегрированной	среде	программирования				известен и не

229