ЗНАЙОМСТВО З СОРТУВАННЯМ ФАЙЛІВ

end

Із зазначених вище підпрограм уточнимо лише процедуру outtree, решта залишаються вправами (див.підр.17.4.2).

procedure outtree(var f : FoT; var A : ArrT; m : Longint);

begin

while m>3 do

begin

write(g, A[P[1]]); indswap(1, m);

m:=m-1; indreorg(1, m);

end;

write(g, A[P[1]]);

if m=3 then

if A[P[2]] > A[P[3]] then indswap(2, 3);

if m > 1 then write(g, A[P[2]]);

if m=3 then write(g, A[P[3]])

end

Задача

18.1. Написати програму сортування файла на основі ідей, описаних у підр.18.1–18.2.

3. Індексові файли

Почнемо з прикладу. Дані про абонента телефонної мережі включають в себе його номер, прізвище, адресу та багато іншої інформації. Шукати дані про абонента доводиться, наприклад, як за його номером, так і за прізвищем. А пошуки у відсортованому файлі значно швидші, ніж у невідсортованому. Отже, за значеннями якого з полів – номера чи прізвища – слід сортувати файл?

Відповідь на це питання дає застосування так званих індексових файлів. Розглянемо послідовність пар із рядків і чисел:

<("qw", 31), ("er", 86), ("ty", 12), ("io", 24)>.

Якщо замінити пари їх номерами (індексами) у послідовності, то упорядкування пар за алфавітним зростанням їх рядків має вигляд <2, 4, 1, 3>, тобто найменшим є "er" із пари 2, наступним – "io" із 4 тощо. Така послідовність номерів і є змістом індексового файла, відповідного цій послідовності пар за упорядкуванням рядків. Водночас, можна так само упорядкувати пари за зростанням чисел: <3, 4, 1, 2>, і це буде змістом іншого індексового файла.Отже, значеннями елементів індексового файла є номери (або інші позначення) елементів основного файла. Перший елемент індексового файла вказує на найменший із елементів основного файла за деяким їх упорядкуванням, другий – на наступний тощо, останній – на найбільший. Якщо елементи основного файла мають багато полів, то для нього можна створити кілька різних індексових файлів.