16.3. Сортировка файлов
Главная трудность при сортировке файлов состоит в том, что в данный момент времени программе доступен лишь один элемент данных, записанный в файле. Это и понятно: если файл хранится на магнитном диске (для других устройств ситуация аналогична), магнитные головки не могут одновременно находиться в двух местах и считывать более, чем один элемент файла (Рис. 16 .54).
Рис. 16.54.Считывание файла.
Как же быть? Для сортировки файлов используется особый прием – сортировка слиянием. Сортировка заменяется слиянием двух половинок файла. Последовательность действий такова (Рис. 16 .55):
Делим файл а на две половины: b и c.
Сливаем части b и c с упорядочиванием пар
Повторить, начиная с п.1
Рис. 16.55. Схема сортировки слиянием.
Рассмотрим пример такой сортировки слиянием (Рис. 16 .56). Исходный файл содержит элементы 44, 55, 12, 42, 94, 18, 06, 67. Сначала файл разбивается на два файла, содержащие элементы 44, 55, 12, 42 и 94, 18, 06, 67 соответственно. Далее два файла сливаются в один. При слиянии из каждого файла берется по одному элементу, и они записываются в выходной файл в упорядоченном виде, образуя пары (44 94), (18 55), (06 12), (42 67). Затем процесс повторяется и "двойки" группируются в "четверки" ((06 12 44 94) (18 42 55 67)). Наконец, после еще одного слияния исходный файл оказывается полностью отсортированным.
Неприятная особенность такой сортировки – число элементов в файле должно быть четным. Выход прост: вводим дополнительный фиктивный элемент, если длина фала нечетная, а потом его убираем.
Рис. 16.56. Пример сортировки слиянием.
Сортировка файла естественным слиянием использует тот факт, что файл уже частично упорядочен. Серией называется упорядоченная последовательность элементов файла:
|
( 12.0) |
(математический
символ
называется "квантор всеобщности"
и означает "для каждого". Он
происходит от англ. "all").
Естественное слияние основано
на правиле: любые две серии m
и n можно сразу
сливать в новую серию m+n.
При этом при каждом проходе по файлу
число серий уменьшается вдвое. Поэтому
среднее число операций при такой
сортировке будет
.
Рассмотрим пример сортировки естественным слиянием (Рис. 16 .57). Файл из 20 элементов сортируется всего за три прохода – неплохой результат!
Рис. 16.57. Пример сортировки естественным слиянием.
17.Файлы
Файл данных – последовательность (sequence) элементов одинакового типа. Помимо того очевидного факта, что файлы хранятся во внешней памяти (жесткие диски, CD, дискеты), файл отличается от массива двумя вещами:
- число элементов в фале заранее неизвестно;
одновременно доступен лишь один элемент.
На блок-схемах файловые операции изображаются в виде "бочонка" (Рис. 17 .58). Такое обозначение идет с тех пор, как в вычислительной технике применялись магнитные барабаны, действительно похожие на бочонок.
Рис. 17.58. Обозначение операций с файлом на блок-схемах.
Возможно два способа доступа к файлу: последовательный и параллельный (Рис. 17 .59). Разница между двумя способами доступа такая же, как между магнитофонной кассетой и CD: на кассете (последовательный доступ) что добраться до пятой песни, надо промотать первые четыре, а на СD (прямой доступ) можно "перескочить" сразу на любой нужный трек.
Способ доступа не зависит напрямую от конструкции запоминающего устройства. Разумеется, если информация хранится на кассете с магнитной лентой (такое устройство называется стриммером), то доступ всегда будет последовательным. А вот на жестком диске возможны и последовательный, и параллельный виды доступа.
По содержанию файлы данных делятся на текстовые и двоичные (Рис. 17 .60).
Рис. 17.59. виды доступа к файлу.
Рис. 17.60. Текстовые и двоичные файлы.
Как и следует из названия, текстовые файлы можно прочитать непосредственно, а двоичные при выводе на экран выглядят как бессмысленная мешанина символов. Файл, в котором хранится текст, совершенно не обязан быть текстовым. Файлы текстового процессора Word являются двоичными.