- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
3 Последовательный файл
3.1 Основные свойства последовательных файлов
Рассмотрим кратко файл в контексте нашего предмета, не повторяясь в части описания операций над файлами.
Общее свойство ранее рассмотренных структур данных состоит в том, что число их компонент конечно (т.е. конечно кардинальное число).
В усложненных структурах - последовательности, деревья, графы и т.д. – мы можем не знать число компонент (т.е. кардинальные числа бесконечны).
Наиболее простой из таких структур является последовательность (последовательный файл). Последовательность состоит из компонент одного типа. Порядок следования компонент - естественный, т.е. друг за другом. В отличие от массива, где реализован произвольный доступ к элементам, в последовательном файле в любой момент времени доступен только один элемент файла. Другие элементы доступны только путем последовательного продвижения по файлу.
Формально (логически) определить структуру типа "последовательный файл" можно следующим образом.
Последовательность с базовым типом Т0 – это либо пустая последовательность, либо конкатенация последовательности элементов (базового типа Т0) и элемента типа Т0.
Определенный таким образом тип Т логической структуры содержит бесконечное число значений. Хотя, конечно, каждое конкретное значение состоит из конечного числа компонент, но это число не ограничено. К любой сколь угодно длинной последовательности можно приписать еще один элемент, но только в конец.
Что же касается последовательности, то эта структура, хотя и является усложненной, но так широко используется, что включена в состав фундаментальных структур. Последовательности располагаются во внешней памяти – в этом еще одно отличие от рассмотренных ранее структур: последовательность не является оперативной структурой.
В качестве Т0 может быть любой простой или структурированный тип, но не файл.
Вспомним, что над файлом можно выполнить два явных типа действий:
просмотр файла. Он выполняется в результате последовательного продвижения по файлу, начиная с начала;
создание файла. Оно выполняется в результате добавления новых компонент в конец первоначально пустого файла.
Кроме того, некоторые запоминающие устройства на самом деле допускают только последовательный доступ к находящейся на них информации. Это, прежде всего, магнитные ленты. Но даже на магнитных дисках каждая отдельная дорожка представляет собой запоминающее устройство с последовательным доступом. Строго говоря, последовательный доступ – основное свойство всех устройств с механическим перемещением, а также некоторых других.
3.2 Сортировка последовательных файлов
Вспомним задачу сортировки в общем виде. Даны элементы
a1, a2 ,..., an .
Сортировка означает перестановку этих элементов в порядке
ak1, ak2 ,...,akn , так что при заданной функции упорядочения ƒ справедливо отношение
f (ak1) ≤ f (ak2 ) ≤...≤ f (akn ) .
Обычно функция упорядочения хранится в самом элементе в виде явной компоненты (поля), и ее значение
называют ключом элемента. Следовательно, для представления элемента ai хорошо подходит тип записи:
TYPE ITEM = RECORD
KEY : INTEGER; {другие компоненты} END "Другие компоненты" содержат все существенные данные об элементе. Для задач же сортировки единственной существенной компонентой является ключ.
Рассмотрим некоторые методы сортировки в массивах. К сожалению, они неприемлемы, если сортируемые данные находятся не в оперативной памяти, а на внешнем ЗУ последовательного доступа (последовательные файлы). В этом случае в каждый момент времени имеется доступ только к одному элементу. Это ограничение и приводит к тому, что для последовательных файлов приходится применять другие методы сортировки.
Основной метод – сортировка слиянием. Под слиянием здесь понимаем объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Слияние – намного более простая операция, чем сортировка.
Один из методов такой сортировки называется простым слиянием и состоит в следующем.
Последовательность a разбивается на две половины b и c.
Последовательности b и c сливаются при помощи объединения отдельных элементов в упорядоченные пары.
Полученной последовательности присваивается имя a, после чего повторяются шаги 1 и 2; при этом упорядоченные пары сливаются в упорядоченные четверки.
Предыдущие шаги повторяются, при этом четверки сливаются в восьмерки и т.д., пока не будет упорядочена вся последовательность, т.к. длины последовательностей каждый раз удваиваются.
Пример. Последовательность
Исходная после- |
а= |
44 55 12 42 94 18 06 6 |
довательность |
|
|
1 |
b= |
44 55 12 42 |
|
с= |
94 18 06 67 |
|
а= |
44 94' 18 55' 06 12' 42 67 |
2 |
Ь= |
44 94' 18 55' |
|
с= |
06 12' 42 67 |
|
а= |
06 12 44 94' 18 42 55 67' |
3 |
Ь= |
06 12 44 94' |
|
с= |
18 42 55 67' |
|
а= |
06 12 18 42 44 55 67 94 |
Операция, которая однократно обрабатывает всё множество данных, называется фазой. Наименьший подпроцесс, который, повторяясь, образует процесс сортировки, называется проходом или этапом. В нашем примере сортировка производится за три прохода. Каждый проход состоит из фазы разбиения и фазы слияния. Для сортировки требуется три файла (ленты), поэтому этот метод еще называется трехленточным слиянием.
Вообще говоря, фазы разбиения не относятся к сортировке, т.к. они никак не переставляют элементы. В этом смысле они непродуктивны. Их можно удалить, объединив фазы разбиения и слияния: вместо того, чтобы сливать элементы в одну последовательность, результат слияния сразу распределяют на две последовательности (ленты), которые на следующем проходе будут входными. При этом экономим на операциях переписывания (вдвое меньше), но это достигается ценой использования дополнительной (внешней) памяти (использования четвертой ленты).
Такой метод, в отличие от двухфазного, называется однофазным или сбалансированным слиянием.
Разберем программу слияния подробнее. Вначале предположим, что данные расположены в виде массива (для простоты), который однако можно просматривать только строго последовательно. Другую версию программы рассмотрим на файлах, а затем сравним.
Вместо двух файлов можно использовать один массив, рассматривая его как последовательность с двумя концами. И вместо того, чтобы сливать элементы из двух файлов, можно брать их с двух концов массива. Таким образом общий вид объединения фазы слияния – разбиения можно изобразить, как показано на рис. 3.
Входной массив
Выходной массив
rV
К^
h
/
Слияние
/
J ч.
/
j
Разбиение
Рис. 3 Сортировка двух массивов методом простого слияния
Направление пересылки сливаемых элементов меняется (переключается) после каждой упорядоченной пары (на первом проходе), четверки (на втором проходе) и т.д. Таким образом равномерно заполняются две выходные последовательности – два конца выходного массива. После каждого прохода массивы меняются местами: выходной становится входным и наоборот.
Процедуру можно упростить, объединив оба массива в один – двойной длины:
A : array [1..2*N] of item;
Пусть индексы i, j указывают два исходных элемента, k, l – два места пересылки. Исходные данные – элементы A[1], ... , A[N]. Введем булеву переменную up для указания направления пересылки данных:
up = true – на текущем проходе компоненты A[1], ..., A[N] пересылаются "вверх" – в переменные A[N+1], ..., A[2*N] (A[1], ..., A[N] → A[N+1], ..., A[2*N])
up = false – пересылка "вниз" – A[N+1], ..., A[2*N] пересылаются в A[1], ..., A[N]. (A[N+1], ..., A[2*N] → A[1], ..., A[N])
Значение up меняется после каждого прохода.
Кроме того, введем переменную P для длины сливаемых подпоследовательностей. Ее начальное значение
P = 1 и удваивается перед каждым очередным проходом. Для простоты считаем, что N всегда степень двойки. Тогда первая версия программы простого слияния:
PROCEDURE MERGESORT; VAR I, J, K, L, P: INTEGER;
UP: BOOLEAN; BEGIN
UP := TRUE; P := 1;
REPEAT { инициализация индексов }
IF UP THEN
BEGIN I :=1; J :=N; K :=N+1; L :=2*N END ELSE BEGIN K :=1; L :=N; I :=N+1; J:=2*N END; { П.1 - слияние Р-наборов последовательностей I, J в последовательности K, L } UP := NOT UP; P := 2 * P UNTIL P = N; END;
Уточним П.1. Этот проход, обрабатывающий N элементов, состоит из последовательных слияний Р-наборов. После каждого слияния направление пересылки переключается из нижнего в верхний конец выходного массива или наоборот (для обеспечения одинакового распределения в обоих направлениях).
Если сливаемые элементы посылаются в нижний конец массива, то индексом пересылки служит k, и k увеличивается на 1 после каждой пересылки, если в верхний конец массива, то l уменьшается на 1 после каждой пересылки.
Можно упростить операцию слияния, если считать, что место пересылки всегда обозначается через k и будем менять местами k и l после слияния каждого Р-набора. Приращение индекса обозначим через h, где h = 1 или h = -1.
Теперь получим П.1:
H :=1; M := N; REPEAT
Q := P; R := P; M := M - 2 * P;
{ П. 1.1 слияние Q элементов из I и R элементов из J, индекс засылки есть К с приращением H }
H := -H;
{ П. 1.2 обмен значениями K и L; } UNTIL M = 0;
Детализируем П.1.1. Нужно учесть, что остаток последовательности, которая остается непустой после слияния, добавляется к выходной последовательности с помощью простого копирования.
WHILE ( Q <> 0 ) AND ( R <> 0 ) DO BEGIN { выбор элемента из I или J }
IF A[I].KEY < A[J].KEY THEN BEGIN { п. 1.1.1 -пересылка элемента из I в K, увеличение I и K; }
Q := Q - 1 END ELSE BEGIN
{ п. 1.1.2 - пересылка элемента из J в K, увеличение J и K; }
R := R - 1; END END;
{ п. 1.1.3. копирование остатка последовательности I; } { п. 1.1.4. копирование остатка последовательности J; }
Детализация пп.1.1.1 и 1.1.2 не требуется; пп. 1.1.3 и 1.1.4 детализируем в процессе записи всей программы; п. 1.2 - тоже.
Перед записью попытаемся устранить ограничение на N (степень двойки). В общем случае будем продолжать слияние Р-наборов, пока длина остатков входных последовательностей не станет меньше Р. Это влияет на ту часть алгоритма, где определяются значения Q и R - длины последовательностей, которые предстоит слить. Тогда вместо трех операторов
Q := Р; R := Р; М :=М - 2 * Р; используем четыре оператора
IF М >= Р THEN Q := Р ELSE Q := М; М := М - Q;
IF М >= Р THEN R := Р ELSE R := М; М := М - R; М обозначает общее число элементов в двух входных последовательностях, которые сливаются.
Наконец, чтобы обеспечить окончание работы программы, нужно заменить условие Р = N, управляющее внешним циклом, на Р >= N.
Теперь запишем весь алгоритм.
PROCEDURE MERGESORT;
VAR I, J, К, L, Т, Н, М, Р, Q, R: INTEGER;
UP: BOOLEAN; BEGIN UP := TRUE; P := 1; REPEAT H := 1; M := N;
IF UP THEN
BEGIN I := 1; J := N; К := N + 1; L := 2 * N END
ELSE К := 1; L := N; I := N + 1; J := 2 * N END;
REPEAT {}
{}
IF M >= P THEN Q := P ELSE Q := M; M := M - Q;
IF M >= P THEN R := P ELSE R := M; M := M - R;
WHILE ( Q <> 0 ) AND ( R <> 0 ) DO
BEGIN
IF A[I].KEY < A[J].KEY THEN BEGIN
A[K] := A[I]; К := К + H; I := I + 1; Q := Q - 1
END ELSE BEGIN
A[K] := A[J]; К := К + H; J := J + 1; R := R - 1 END
END;
{ копирование остатка серии из j }
WHILE R <> 0 DO BEGIN
A[K] := A[J]; К := К + H; J := J - 1; R := R - 1
END;
{ копирование остатка серии из I }
WHILE Q <> 0 DO BEGIN
A[K] := A[I]; К := К + H; I := I - 1; Q := Q - 1
END;
H := -H; T := К; К := L; L := T
UNTIL M = 0;
UP := NOT UP; P := 2 * P; UNTIL P >= N; IF NOT UP THEN
FOR I := 1 TO N DO A[I] := A[I+N]; END;
Анализ сортировки слиянием
Поскольку на каждом проходе длина подпоследовательности Р удваивается и сортировка заканчивается, как только Р >= N, она требует \\og2 Nl проходов. При каждом проходе (по определению) все множество из N элементов копируется ровно один раз. Следовательно, общее число пересылок равно М = N * \\og2 N~|. Число сравнений С ключей еще меньше, т.к. при копировании остатка последовательности сравнения не производятся. Но это не слишком важно, поскольку основное время при работе с внешними устройствами тратится на пересылки (оно на несколько порядков выше, чем время, затрачиваемое на сравнения).
По количеству пересылок алгоритм сравним с усовершенствованными методами сортировки массивов. Однако затраты на управление индексами достаточно высоки, а также существенным недостатком является использование памяти размером 2N элементов. Поэтому сортировка слиянием редко применяется при работе с массивами.
Естественное слияние
Алгоритм простого слияния никак не реагирует на то обстоятельство, что данные могут быть уже частично упорядочены. На k-м проходе длина всех сливаемых подпоследовательностей меньше или равна 2к без учета того, что более длинные подпоследовательности уже могут быть упорядочены и их можно было бы сливать. Т.е. можно было бы сразу сливать последовательности длиной да и п в одну последовательность из да + и элементов.
Метод сортировки, при котором каждый раз сливаются две самые длинные возможные подпоследовательности, называется естественным слиянием.
Будем называть подпоследовательность G., ..., G ., такую, что Gk < й^+1 для к = i,...,J—\,
Я._! > Cli, а . > aJ+1, максимальной серией или просто серией. Таким образом сортировка естественным
слиянием сливает не последовательности заранее заданной длины, а максимальные серии. При слиянии двух последовательностей, каждая из которых содержит N серий, возникает одна последовательность, содержащая ровно N серий. Таким образом на каждом проходе общее число серий уменьшается вдвое, и число необходимых пересылок элементов в худшем случае равно N * l~log2 N~|, а в обычном случае даже меньше. Число сравнений, однако, намного больше, т.к. кроме сравнений, необходимых для упорядочения элементов, требуются еще сравнения соседних элементов каждого файла для определения концов серии.
Рассмотрим теперь алгоритм естественного слияния применительно к последовательному файлу.
Пусть исходная последовательность задана в виде файла С, который в конце работы должен содержать результат сортировки. Используются два вспомогательных файла А и В. Каждый проход состоит из фазы распределения, которая распределяет серии поровну из С в А и В, и фазы слияния, которая сливает серии из А и В в С (рис. 4).
AA A
1-й проход 2-й проход n-й проход
Рис. 4 Фазы сортировки и проходы сортировки
Поэтому алгоритм представляет собой несбалансированную двухфазную трехленточную (трехфайло-вую) сортировку слиянием.
Пример. Файл из 20 чисел.
Исходный файл |
17 31' 5 59' 13 41 43 67' 11 23 29 47' 3 7 71' 2 19 57' 37 61 |
после 1-го |
5 17 31' 59' 11 13 23 29 41 43 47 67' 2 3 7 19 57 71' 37 61 |
после 2-го |
5 11 13 17 23 29 31 41 43 47 59 67' 2 3 7 19 37 57 61 71 |
после 3-го проходов |
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 57 59 61 67 71 |
Сортировка заканчивается, как только число серий С будет равно единице. (Предполагается, что в исходном файле имеется хотя бы одна непустая серия).
Пусть L - переменная для подсчета количества серий в С. Определим глобальные объекты:
TYPE TAPE = FILE OF ITEM; VAR C : TAPE;
Тогда программу можно оформить следующим образом:
PROCEDURE NATURALMERGE; VAR L : INTEGER;
A, B : TAPE; BEGIN REPEAT
REWRITE (A); REWRITE (B); RESET (C);
DISTRIBUTE; { распределение }
RESET (A); RESET (B); REWRITE (C);
L := 0;
MERGE; { слияние }
UNIT L = 1 END;
Проведем пошаговую детализацию, конкретизируя последовательно процедуры, входящие в naturalmerge.
PROCEDURE DISTRIBUTE; { из с в а и в }
BEGIN
REPEAT
COPYRUN (C, A); { переписывание серии }
IF NOT EOF ( C ) THEN COPYRUN (C, B) UNTIL EOF ( C ) END;
PROCEDURE MERGE; { из а и в в с }
BEGIN
REPEAT
MERGERUN; { слияние двух серий }
L := L + 1 UNTIL EOF (B); IF NOT EOF (A) THEN BEGIN
COPYRUN (A, C); L := L + 1 END END;
Предполагается, что при таком способе распределения в файлах А и В оказывается либо равное число серий, либо файл А содержит на одну серию больше, чем В. Соответствующие пары серий сливаем, а лишнюю просто переписываем.
Подчиненные процедуры mergerun и copyrun требуют введения глобальной булевой переменной EOR (end of the run), значение которой показывает, достигнут ли конец серии.
PROCEDURE COPYRUN (VAR X, Y : TAPE);
BEGIN { перепись одной серии из х в y }
REPEAT
COPY(X, Y) { перепись одного элемента }
UNTIL EOR { конец серии }
END;
Вторая подчиненная процедура
PROCEDURE MERGERUN;
BEGIN { слияние двух серий из а и в в с }
REPEAT
IF A^.KEY < B^.KEY THEN BEGIN COPY (A, C);
IF EOR THEN COPYRUN (B, C) END ELSE BEGIN COPY (B, C);
IF EOR THEN COPYRUN (A, C) END UNTIL EOR END;
Процесс сравнения и выбора по ключу при слиянии серий завершается, как только будет исчерпана одна из двух серий. После этого остаток другой серии нужно переписать в выходную серию, с помощью простого копирования. Это осуществляется вызовом процедуры copyrun.
Подчиненная процедура copy пересылает элемент файла Х в файл Y и определяет, достигнут ли конец серии. Для этого нужно сохранить ключ последнего прочитанного (переписанного) элемента, чтобы сравнить его со следующим. Это "заглядывание вперед" достигается использованием буферной переменной файла X↑.
PROCEDURE COPY (VAR X, Y : TAPE);
VAR BUF : ITEM;
BEGIN
READ (X, BUF); WRITE (Y, BUF);
IF EOF (X) THEN EOF := TRUE
ELSE EOF := BUF.KEY > X↑.KEY END;
На этом построение процедуры сортировки естественным слиянием закончено.
К сожалению, в некоторых случаях программа производит сортировку неправильно. Например, пусть исходная последовательность:
3 2 5 11 7 13 19 17 32 31 29 37 43 41 47 59 57 61 71 67
Распределяя последовательные серии в А и В, получим:
А = 3' 7 13 19' 29 37 43' 57 61 71'
B = 2 5 11' 17 23 31' 41 47 59' 67
Эти последовательности легко сливаются в одну, после чего сортировка заканчивается. Пример показывает, что простое распределение серий в два файла может дать меньшее число выходных серий, чем входных. Это происходит, когда первый элемент (i+2)-й серии больше последнего элемента i-й серии, что приведет к автоматическому слиянию двух серий в одну. Поэтому действительные количества выходных серий в А и В могут сильно различаться. Однако наша процедура будет сливать пары серий и заканчиваться, как только будет прочитан один из файлов, теряя при этом остаток другого, например 17 19' 13 57' 23 29' 11 59' 31 37' 7 61' 41 43' 5 67' 47 71' 2 3 13 17 19 23 29 31 37 41 43 47 57 71' 11 59 11 13 17 19 23 29 31 37 41 43 47 57 59 71
Таким образом исходные данные сортируются (и усекаются) за два прохода.
Один из способов исправления - скорректировать операцию распределения так, чтобы число серий на лентах было одинаковым.
Второй - отказаться от распределения поровну, а изменить процедуру слияния таким образом, чтобы по достижении конца одного из файлов копировался весь остаток другого, а не только одна серия.
Во втором случае слияние:
PROCEDURE MERGE;
BEGIN
WHILE NOT EOF (A) AND NOT EOF (B) DO
BEGIN MERGERUN; L := L + 1;
END; WHILE NOT EOF (A) DO
BEGIN COPYRUN (A, C); L := L + 1;
END; WHILE NOT EOF (B) DO
BEGIN COPYRUN (B, C); L := L + 1;
END; END; Теперь объединить процедуры и написать вызывающую программу. Добавить печать.
Контрольные вопросы
Основные операции при работе с последовательными файлами.
Основное отличие сортировки на файле и в ОЗУ.
Сортировка последовательных файлов.
Сортировка последовательных файлов методом простого слияния.
Что такое фаза обработки данных?
Трудоемкость сортировки слиянием.
Сортировка последовательных файлов методом естественного слияния.
Отличие сбалансированного от несбалансированного слияния.