Сторінка
2

Знайомство з сортуванням файлів

indbld(n); end else {A[1] ³ last}indreorg(1, n) end; if n > 0 then outtree(g, A, n); if ch > 0 then begin copyfa(h, A, n); ch:=0; indbld(n); outtree(g, A, n) 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>, і це буде змістом іншого індексового файла. Отже, значеннями елементів індексового файла є номери (або інші позначення) елементів основного файла. Перший елемент індексового файла вказує на найменший із елементів основного файла за деяким їх упорядкуванням, другий – на наступний тощо, останній – на найбільший. Якщо елементи основного файла мають багато полів, то для нього можна створити кілька різних індексових файлів. Індексові файли дозволяють взагалі не сортувати основний файл. У випадку, коли його елементи складаються сотнями й тисячами байтів, таке сортування надто дороге. Індексові ж файли складаються з цілих, і їх сортування, як правило, можна здійснити, представивши їх зміст у масиві. Отже, використання індексових файлів дозволяє одночасно розглядати той самий файл як упорядкований за значеннями кількох різних полів його записів. Саме це дозволяє вести швидкий пошук у ньому за кількома різними ключами. Задачі 2. Написати пpоцедуpу побудови індексового файла за файлом записів. 3. Написати пpоцедуpу виведення записів типізованого файла за зростанням значень указаного поля (з використанням індексового файла). 4. Написати процедуру зміни індексового файла при а) додаванні б) вилученні записів основного файла.