Структури Даних і Абстракції Даних

Хоча терміни тип даних (або просто тип), структура даних і абстрактний тип даних звучать схоже, але вони мають різний зміст. У мовах програмування тип даних змінної позначає безліч значень, які може приймати ця змінна. Наприклад, мінлива булевого (логічного) типу може приймати тільки два значення: значення true (істина) і значення false (неправда) і ніякі інші. Набір базових типів даних відрізняється в різних мовах: в мові Pascal це типи цілих (integer) і дійсних (real) чисел, булеві (boolean) тип і символьний (char) тип. Правила конструювання складних типів даних

(на основі базових типів) також відрізняються в різних мовах програмування: Pascal легко і швидко будує такі типи.

Абстрактний тип даних (АТД) - це математична модель плюс різні оператори, визначені в рамках цієї моделі. Ми можемо розробляти алгоритм в термінах АТД, але для реалізації алгоритму в конкретній мові програмування необхідно знайти спосіб представлення

АТД в термінах типів даних і операторів, які підтримуються даними мовою програмування. Для подання АТД використовуються структури даних, які являють собою набір змінних, можливо, різних типів даних, об'єднаних певним чином.

Базовим будівельним блоком структури даних є осередок, що призначена для зберігання значення певного базового або складеного типу даних. Структури даних створюються шляхом завдання саме сукупність (агрегатів) осередків та (необов'язково) інтерпретації значення деяких осередків як представників (тобто покажчиків) інших осередків.

Як найпростішого механізму агрегування осередків в Pascal та більшості інших мов програмування можна застосовувати (одновимірний) масив, тобто послідовність комірок певного типу. Масив також можна розглядати як відображення безлічі індексів (таких як цілі числа 1, 2, ..., n) в безліч осередків. Посилання на комірку зазвичай складається з імені масиву і значення з безлічі індексів даного масиву. В

Pascal безліч індексів може бути нечислових типу, наприклад (північ, схід, південь, захід), або інтервального типу як (1 .. 10). Значення всіх осередків масиву повинні мати однаковий тип даних. Оголошення

Ім'я: array [ТіпІндекса] of ТіпЯчеек; задає ім'я для послідовності комірок, тип для елементів множини індексів і тип вмісту осередків.

До речі, Pascal надзвичайно багатий на типи індексів. Багато мов програмування дозволяють використовувати в якості індексів тільки безлічі послідовних цілих чисел. Наприклад, щоб в мові Fortran в якості індексів масиву можна було використовувати букви, треба все одно використовувати цілі індекси, замінюючи «А» на 1, «В» на 2, і т.д.

Іншим загальним механізмом агрегування осередків у мові програмування є структура запису. Запис (record) можна розглядати як комірку, що складається з декількох інших осередків (званих полями), значення в яких можуть бути різних типів. Записи часто групуються в масиви; тип даних визначається сукупністю типів полів запису.

Наприклад, в Pascal оголошення var reclist: array [1 .. 4] of record data: real; next: integer; end задає ім'я reclist (список записів) 4-елементного масиву, значеннями якого є записи з двома полями: data (дані) та next

(наступний).

Третій метод агрегування осередків, який можна знайти в Pascal і деяких інших мовах програмування, - це файл. Файл, як і одновимірний масив, є послідовністю значень певного типу. Однак файл не має індексів: його елементи доступні тільки в тому порядку, в якому вони були записані у файл. На відміну від файлу, масиви і рядки є структурами з «довільним доступом», маючи на увазі під цим, що час доступу до компонентів масиву і записи не залежить від значення індексу масиву або покажчика поля запису. Гідність агрегування за допомогою файлу (частково компенсує описаний недолік) полягає в тому, що файл не має обмеження на кількість складових його елементів і ця кількість може змінюватися під час виконання програми.

Покажчики та курсори На додаток до засобів агрегування осередків в мовах програмування можна використовувати покажчики і курсори. Покажчик

(pointer) - це осередок, чиє значення вказує на іншу клітинку. При графічному представленні структури даних у вигляді схеми той факт, що осередок А є покажчиком на клітинку В, показується за допомогою стрілки від комірки А до осередку В.

У мові Pascal за допомогою наступного оголошення можна створити змінну - покажчик prt, що вказує на комірку певного типу, наприклад ТіпЯчейкі: var prt: ТіпЯчейкі

постфікси у вигляді стрілки, спрямованої вгору, в Pascal використовується як оператор разименованія, тобто вираз prt позначає значення (типу

ТіпЯчейкі) у клітинці, зазначеної prt.

Курсор (cursor) - це комірка із целочисленным значенням, що використовується для вказівки на масив. Як спосіб вказівки курсор працює так само, як і покажчик, але курсор можна використовувати і в мовах (подібних

Fortran), які не мають явного типу покажчика. Інтерпретувавши цілочисельну клітинку як індексне значення для масиву, можна ефективно реалізувати вказівки на комірки масиву. На жаль, цей прийом підходить тільки для осередків масиву і не дозволяє організувати вказівки на комірки, які не є частиною масиву.

У схемах структур даних буде малюватися стрільця з осередку курсор до комірки, на яку вказує курсор. Іноді також буде показуватися ціле число в комірці курсору, нагадуючи тим самим, що це не справжній покажчик. Можна відмітити, що механізм покажчика Pascal дозволяє осередкам масиву тільки «бути зазначеними» за допомогою курсору, але не бути правдивим покажчиком. Інші мови програмування, подібні PL/1 або

С, дозволяють компонентів масивів бути істинними покажчиками і, звичайно, «бути вказаним» за допомогою курсору. На відміну від цих мов, в мовах Fortran і Algol, де немає типу покажчика, можна використовувати тільки курсори.

Прімер1. На мал.1 показана структура даних, що складається з двох частин. Вона має ланцюжок комірок, що містять курсори для масиву reclist

(список записів), визначеного вище. Призначення поля next (наступний) полягає у вказівці на такий запис у масиві reclist. Наприклад, reclist [4]. Next дорівнює 1, тому запис 4 передує запису 1. вважаючи перший запис 4, у відповідності до значень поля next отримаємо наступний порядок записів: 4, 1, 3, 2. Відзначимо, що значення поля next у записі 2, що дорівнює 0, вказує на те, що немає наступного запису.

Доцільно прийняти угоду, що число 0 означатиме нуль-покажчик при використанні курсорів і покажчиків. Але, щоб не виникали проблеми при реалізації цієї угоди, необхідно також домовитися, що масиви, на які вказують курсори, індексуються починаючи з 1, а не з 0.

header

data next

Ріс.1Прімер структури даних. Стовпчики в ланцюжку 1 мають тип

type

recordtype = record

cursor: integer;

prt recordtype

end

На ланцюжок можна посилатися за допомогою змінної header (заголовок), що має тип recordtype, header вказує на анонімну запис типу recordtype 1. Цей запис має 4 значення в полі cursor. Розглядається 4 як індекс масиву reclist. Цей запис має істинний покажчик в поле prt на іншу анонімну запис, який, у свою чергу, вказує на індекс 4 масиву reclist і має нуль-покажчик в поле prt.

Абстрактний тип даних «Список».

Списки є надзвичайно гнучкою структурою, тому що їх легко зробити більшими чи меншими, і їх елементи доступні для вставки або видалення в будь-якій позиції списку. Списки також можна об'єднувати, або розбивати на менші списки. Списки регулярно використовуються в додатках, наприклад в програмах інформаційного пошуку, трансляторах програмних мов або при моделюванні різних процесів. Методи керування пам'яттю широко використовують техніку обробки списків. Далі будуть описані основні операції, що виконуються над списками, і представлені структури даних для списків, які ефективно підтримують різні підмножини таких операцій.

В математиці список являє собою послідовність елементів певного типу, який в загальному випадку буде позначатися як elementtype (тип елементу). Список буде часто представлятися у вигляді послідовності елементів, розділених комами: a1, a2, ..., an, де n> 0 і всі ai мають тип elementtype. Кількість елементів n називатиметься довжиною списку. Якщо n> 1, то а1 називається першим елементом списку. У випадку n = 0 список буде називатися порожнім, тобто який не містить елементів.

Важлива властивість списку полягає в тому, що його елементи можна лінійно порядок у відповідності з їх позицією у списку. Говориться, що елемент АI передує АI 1 для i = 1, 2, ..., n-1 і АI слід за ai-1 для i = 2, 3, ..., n. Говориться також, що елемент АI має позицію i. Крім того, підтверджується існування позиції, наступного за останнім елементом списку. Функція END (L) буде повертати позицію, наступну за позицією n в n-елементному списку L. Слід зазначити, що позиція END (L), що розглядається як відстань від початку списку, може змінюватися при зменшенні або збільшенні списку, у той час як інші позиції мають фіксоване (незмінне) відстань від початку списку.

Для формування абстрактного типу даних на основі математичного визначення списку потрібно поставити безліч операторів, що виконуються над об'єктами типу LIST2 (список). Однак не існує одного безлічі операторів, що виконуються над списками, що задовольняє відразу всі програми.

Щоб показати деякі загальні оператори, що виконуються над списками, припустимо, що маємо додаток, що містить список поштової розсилки, який ми хочемо очистити від повторюваних адрес. Концептуально це завдання вирішується дуже просто: для кожного елемента списку видаляються всі наступні елементи, які збігаються з даними. Однак для запису такого алгоритму необхідно визначити оператори, які повинні знайти перший елемент списку, перейти до наступного елементу, здійснити пошук і видалення елементів.

Тепер перейдемо до безпосереднього визначення безлічі операторів списку. Приймемо позначення: L - список об'єктів типу elementtype, x - об'єкт цього типу, p - позиція елемента в списку. Слід зазначити, що

«позиція» має інший тип даних, чия реалізація може бути різною для різних реалізацій списків. Зазвичай позиція розуміється як безліч цілих позитивних чисел, але на практиці можуть зустрітися додаткові подання.

INSERT (x, p, L). Цей оператор вставляє об'єкт х в позицію р і далі в наступну, більш високу позицію. Таким чином, якщо список L складається з елементів а1, a2, ..., an, то після виконання цього оператора він буде мати вигляд а1, a2, ..., ap-1, x, ap, ..., an. Якщо р. приймає значення END (L), то будемо мати a1, a2, ..., an, x. Якщо в списку

L немає позиції р, то результат виконання цього оператора не визначений.

LOCATE (x, L). Ця функція повертає позицію об'єкта х в списку L.еслі у списку об'єкт х зустрічається кілька разів, то повертається позиція перша від початку списку об'єкта х. Якщо об'єкта х немає в списку L, то повертається END (L).

RETRIEVE (p, L). Ця функція повертає елемент, який стоїть в позиції р. у списку L. Результат не визначений, якщо p = END (L) або в списку L немає позиції p. Елементи повинні бути одного типу, який в принципі може повертати функція. Однак на практиці ми завжди можемо змінити цю функцію так, що вона буде повертати покажчик на об'єкт типу elementtype.

DELETE (p, L). цей оператор видаляє елемент в позиції p списку L. Так, якщо список L складається з елементів a1, a2, ..., an, то після виконання цього оператора він буде мати вигляд a1, a2, ..., ap-1, ap 1, ..., an.

Результат не визначений, якщо у списку L немає позиції p або p = END (L).

NEXT (p, L) і PREVIOUS (p, L). Ці функції повертають відповідно наступну і попередню позиції від позиції p у списку L.еслі р - остання позиція в списку L, то NEXT (p, L) = END (L). Функція NEXT не визначена, коли p = END (L). Функція PREVIOUS не визначена, якщо p =

1. Обидві функції не визначені, якщо у списку L немає позиції p.

MAKENULL (L). Ця функція робить список L порожнім і повертає позицію

END (L).

FIRST (L). Ця функція повертає першу позицію в списку L. Якщо список порожній, то повертається позиція END (L).

8. PRINTLIST (L). Друкує елементи списку L в порядку їх розташування.

Стеки.

Стек - це спеціальний тип списку, в якому всі вставки та видалення виконуються тільки на одному кінці, що зветься вершиною (top). Стеки також іноді називають «магазинами», а в англійській літературі для позначення стеків ще використовується абревіатура LIFO (last-in-first-out - останній увійшов - першим вийшов). Інтуїтивними моделями стека можуть служити колода карт на столі при грі в покер, книги, складені в стопку, або стос тарілок на полиці буфету; у всіх цих моделях взяти можна тільки верхній предмет, а додати новий об'єкт можна, лише поклавши його на верхній. Абстрактні типи даних сімейства STAK (Стек) зазвичай використовують наступні п'ять операторів.

MAKENULL (S). Робить стек S порожнім.

TOP (S). Повертає елемент з вершини стека S. Зазвичай вершина стека ідентифікується позицією 1, тоді TOP (S) можна записати в термінах загальних операторів списку як RETRIEVE (FIRST (S), S).

POP (S). Видаляє з вершини стека (виштовхує з стека), в термінах операторів списку цей оператор можна записати як DELETE (FIRST (S),

S). Іноді цей оператор реалізується у вигляді функції, що повертає видаляється елемент.

PUSH (x, S). Вставляє елемент x в вершину стека S (заштовхує елемент в стек). Елемент, що раніше перебував у вершині стека, стає елементом, наступним за вершиною, і т.д. У термінах загальних операторів списку даний оператор можна записати як INSERT (x, FIRST (S), S).

EMPTY (S). Ця функція повертає значення true (істина), якщо стек S порожній, і значення false (неправда) в іншому випадку.

Черги.

Інший спеціальний тип списку - черга (queue), де елементи вставляються з одного кінця, званого заднім (rear), а видаляються з іншого, переднього (front). Черги також називають «списками типу FIFO»

(FIFO абревіатура розшифровується як first-in-first-out: першим увійшов - першим вийшов). Оператори, що виконуються над чергами, аналогічні операторам стеків. Істотна відмінність між ними полягає в тому, що вставка нових елементів здійснюється в кінець списку, а не на початок, як в стек. Крім того, різна усталена термінологія для стеків і черг. Для роботи з чергами будуть використовуватися наступні оператори.

MAKENULL (Q) очищає чергу Q, роблячи її порожньою.

FRONT (Q) - функція, яка повертає перший елемент черги Q. Можна реалізувати цю функцію за допомогою операторів списку як

RETRIEVE (FIRST (Q), Q).

ENQUEUE (x, Q) вставляє елемент x в кінець черги Q. За допомогою операторів списку цей оператор можна виконати наступним чином:

INSERT (x, END (Q), Q).

DEQUEUE (x, Q) видаляє перший елемент черги Q. Також реалізуємо за допомогою операторів списку як DELETE (FIRST (Q), Q).

EMPTY (Q) повертає значення true тоді і тільки тоді, коли Q є марною чергою.

Відображення .

Відображення - це функція, визначена на множині елементів

(області визначення) одного типу (буде позначатися domaintype - тип області визначення функції) і приймає значення з безлічі елементів (області значень) іншого типу, цей тип буде позначатися rangetype - тип області значень (звичайно, типи domaintype і rangetype можуть збігатися). Той факт, що відображення М ставить у відповідність елемент d типу domaintype з області визначення елементу r типу rangetype з області значень, буде записуватися як M (d) = r.

Деякі відображення, подібні square (i) = i2, легко реалізувати за допомогою функцій і арифметичних виразів мови Pascal. Але для багатьох відображень немає очевидних способів реалізації, за винятком зберігання для кожного d значення M (d). Наприклад, для реалізації функції, що ставить у відповідність працівникам їх тижневу зарплату, потрібно зберігати поточний заробіток кожного працівника.

Розглянемо оператори, які можна виконати над відображенням М.

Наприклад, по заданому елементу d типу domaintype ми хочемо отримати

M (d) або дізнатися, чи визначено M (d) (тобто довідатися, чи належить елемент d області визначення М). Або хочемо додати нові елементи в поточну область визначення М і поставити їм у відповідність елементи з області значень. Очевидна також необхідність мати оператор, який змінював би значення M (d). Крім того, потрібно засіб «обнулення» відображення, що переводить будь-яке відображення в пусте відображення, тобто таке, у якого область визначення порожній. Все це можна узагальнити в наступні три команди.

MAKENULL (M). Робить відображення М порожнім.

ASSIGN (M, d, r). Робить М (d) рівним r незалежно від того, як M (d) визначено раніше.

COMPUTE (M, d, r). Повертає значение true і привласнює змінної r значення M (d), якщо останнє слово, а повертає false в іншому випадку.

Структури даних та алгоритми для зовнішньої пам'яті.

В алгоритмах, які обговорювалися до цих пір, передбачалося, що обсяг вхідних даних дозволяє обходитися виключно основний

(оперативної) пам'яттю. Але як бути, якщо потрібно, наприклад, відсортувати всіх державних службовців з тривалості їх робочого стажу або зберігати інформацію з податкових декларацій, усіх громадян країни?

Коли виникає необхідність вирішувати такі завдання, об'єм оброблюваних даних набагато перевищує можливості основної пам'яті . У більшості комп'ютерних систем передбачені пристрої зовнішньої пам'яті, такі як жорсткі диски, або запам'ятовувальні пристрої великої ємності, на яких можна зберігати величезні обсяги даних. Однак характеристики доступу до таких пристроїв зовнішньої пам'яті істотно відрізняються від функцій доступу до основної пам'яті. Щоб підвищити ефективність використання цих пристроїв був розроблений ряд структур даних і алгоритмів.

У Pascal і деяких інших мовах передбачений файловий тип даних, призначений для представлення даних, що зберігаються у вторинній пам'яті. Навіть якщо в мові, якою ви користуєтеся, файловий тип даних не передбачений, в операційній системі поняття «зовнішніх» файлів, безсумнівно, підтримується. Про які б файлах скільки говорилося (файлах, передбачених в Pascal, або файлах, які підтримуються безпосередньо операційною системою), в будь-якому випадку доведеться діяти в рамках обмежень, що стосуються способів доступу до файлів. Операційна система ділить вторинну пам'ять на блоки однакового розміру. Розмір блоку залежить від конкретного типу операційної систем і зазвичай знаходиться в межах від 521 до 4096 байт.

Файл можна розглядати як зв'язний список блоків, хоча найчастіше операційна система використовує деревоподібну організацію блоків, при якій блоки, що складають файл , є листям дерева, а кожен внутрішній вузол містить покажчик на безліч блоків файлу. Якщо, наприклад, 4 байт достатньо, щоб зберігати адресу блоку, а довжина блоку складає 4096 байт, тоді кореневий каталог може містити покажчики максимум на 1024 блоку. Таким чином, файли, що складаються максимум з

1024 блоків (тобто приблизно чотирьох мільйонів байт), можна представити одним кореневим блоком і блоками, які містять сам файл. Файли, що складаються з максимум 220 блоків, або 232 байт, можна представити одним кореневим блоком, що вказує на 1024 блоку проміжного рівня, кожен з яких вказує на 1024 блоку-листа, що містять певну частину файлу і т.д.

Базовою операцією, що виконується по відношенню до файлів, є перенесення одного блоку в буфер, що знаходиться в основній пам'яті. Буфер являє собою зарезервовану область в основній пам'яті, розмір якої відповідає розміру блоку. Типова операційна система забезпечує читання блоків в тому порядку, в якому вони з'являються в списку блоків, який містить відповідний файл, тобто спочатку ми читаємо в буфер перший блок файлу, потім замінюємо його на другий блок, який записується в той самий буфер, і т.д.

Тепер неважко зрозуміти концепцію, яка лежить в основі правил читання файлів в мові Pascal . Кожен файл зберігається у вигляді визначеності блоків, кожен такий блок містить ціле число записів.

(Пам'ять буде використовуватися нераціонально, якщо зберігати частини однієї і тієї ж записи в різних блоках.) Покажчик зчитувань завжди вказує на одну із записів у блоці, який в даний момент знаходиться в буфері.

Коли цей покажчик повинен переміститися на запис, відсутню в буфері, настав час прочитати наступний блок файлу.

Аналогічно, процес запису файла в мовою Pascal можна розглядати як процес створення файлу в буфері. Коли запису «записуються» у файл, фактично вони переміщаються в буфер для цього файлу - безпосередньо слідом за записами, які вже знаходяться там. Якщо наступна запис не поміщається в буфер цілком, вміст буфера копіюється у вільний блок вторинної пам'яті, який приєднується до кінця списку блоків для даного файлу. Після цього можна вважати, що буфер вільний для приміщення в нього чергової порції записів.

Вартість операцій з зовнішньою пам'яттю.

Природа пристроїв вторинної пам'яті (наприклад, дисководів) така, що час, необхідне для пошуку блоку і читання його в основну пам'ять, достатньо велика, в порівнянні з часом, яке потрібно для відносно простої обробки даних, що містяться в цьому блоці.

Припустимо, наприклад, що є блок з 1000 цілих чисел на диску, що обертається зі швидкістю 1000 об/хв. Час, що потрібний для позиціонування голівки, що зчитує над доріжкою, яка містить цей блок

(так зване час встановлення головок), плюс час, що витрачається на очікування, поки потрібний блок зробить оборот і виявиться під голівкою (час очікування), може в середньому становитиме 100 мілісекунд. Процес запису блоку в певне місце у вторинній пам'яті займає приблизно стільки ж часу. Проте за ті ж 100 мілісекунд машина, як правило, встигає виконати 100 000 команд. Цього часу цілком достатньо, щоб виконати просту обробку тисячі цілих чисел, коли вони знаходяться в основній пам'яті (наприклад, їх підсумовування або знаходження серед них найбільшого числа). Цього часу може вистачити навіть для швидкого сортування цілих чисел.

Оцінюючи час роботи алгоритмів, у яких використовуються дані, що зберігаються у вигляді файлів, доведеться в першу чергу враховувати кількість звернень до блоків, тобто скільки разів блок зчитується в основну або записується у вторинну пам'ять. Така операція називається правами (або зверненням) до блоку. Передбачається, що розмір блоку фіксований в операційній системі, тому неможливо прискорити роботу алгоритму, збільшивши розмір блоку і скоротивши тим самим кількість звернень до блоків. Таким чином, мірою якості алгоритму, що працює з зовнішньою пам'яттю, є кількість звернень до блоків.

Зберігання даних у файлах.

У цьому розділі будуть розглянуті структури даних і алгоритми для зберігання та пошуку інформації у файлах, що знаходяться у зовнішній пам'яті.

Файл буде розглядатися як послідовність записів, причому кожен запис складається з однієї і тієї ж сукупності полів. Поля можуть мати або фіксовану довжину (заздалегідь певну кількість байт), або змінну. Файли із записами фіксованої довжини широко використовуються в системах управління базами даних для зберігання даних зі складною структурою. Файли із записами змінної довжини, як правило, використовуються для зберігання текстової інформації; в мові Pascal такі файли не передбачені. У цьому розділі будемо мати справу з полями фіксованої довжини; розглянуті методи після певної

(нескладної) модифікації можуть використовуватися для роботи з записами змінної довжини.

Будуть розглянуті наступні оператори для роботи з файлами .

INSERT вставляє певну запис у певний файл.

DELETE видаляє з певного файлу всі записи, що містять вказані значення у вказаних полях.

MODIFY змінює всі записи в певному файлі, задавши вказані значення певним полях у тих записах, які містять зазначені значеннях в інших полях.

RETRIEVE відшукує всі записи, що містять вказані значення у вказаних полях.

Проста організація даних.

Найпростішим (і найменш ефективним) способом реалізації перерахованих вище операторів роботи з файлами є використання таких примітивів читання і запису файлів, які зустрічаються, наприклад, в Pascal. У випадку використання подібної «організації» (яка насправді є дезорганізацією) запису можуть зберігатися в будь-якому порядку. Пошук записи з зазначеними значеннями в певних полях здійснюється шляхом повного перегляду файлу та перевірки кожної його запису на наявність у ній заданих значень. Вставку в файл можна виконувати шляхом приєднання відповідного запису до кінця файлу.

У разі зміни записів необхідно переглянути файл, перевірити кожен запис і з'ясувати, чи відповідає вона заданим умовам

(значення у вказаних полях). Якщо відповідає, до запису вносяться необхідні зміни. Принцип дії операції видалення майже той самий, але коли ми поля якої відповідають значенням, заданим в операції видалення, ми повинні знайти спосіб видалити її. Один з варіантів - зрушити всі послідовні записи в своїх блоках на одну позицію вперед, а перший запис в кожному наступному блоці перемістити на останню позицію попереднього блоку даного файлу. Однак такий підхід не годиться, якщо записи є закріпленими, оскільки покажчик на i-у запис у файлі після виконання цієї операції буде вказувати на

(i +1)-ю запис.

Якщо записи є закріпленими, варто скористатися якимось іншим підходом. Ми повинні якось позначати видалені записи, але не повинні усувати з посади, що залишилися, на місце видалених (і не повинні вставляти на їх місце нові записи). Таким чином виконується логічне видалення запису з файлу, але її місце у файлі залишається незайнятим. Це потрібно для того, щоб у разі появи вказівника на віддалену запис ми могли, по-перше, зрозуміти, що зазначена запис вже вилучена, і, по-друге, вжити відповідних заходів (наприклад, присвоїти цього вказівником значення NIL, щоб наступного разу не витрачати час на його аналіз).

Існують два способи позначати віддалені запису.

Замінити запис на якесь значення, яке ніколи не може стати значенням «справжньою» записи, і, зустрівши вказівник на будь-яку запис, вважати її віддаленої, якщо вона містить це значення.

Передбачити для кожного запису спеціальний біт видалення; цей біт містить 1 у віддалених записах і 0 - у «справжніх» записах.

Прискорення операцій з файлами.

Очевидним недоліком послідовного файла є те, що оператори з такими файлами виконуються повільно. Виконання кожної операції вимагає, щоб прочитали весь файл, а після цього ще й виконали перезапис деяких блоків. На щастя, існують такі способи організації файлів, які дозволяють звертатися до запису, зчитуючи в основну пам'ять лише невелику частину файлу.

Такі способи організації файлів передбачають наявність у кожного запису файла так званого ключа, тобто сукупності полів, яка унікальним чином ідентифікує кожний запис. Наприклад, у файлі з полями прізвище, адресу, телефон полі прізвище саме по собі може вважатися ключем, тобто можна припустити, що в такому файлі не може одночасно бути двох записів з однаковим значенням поля прізвище.

Пошук запису, коли задані значення її ключових полів, є типовою операцією, на забезпечення максимальної ефективності якої орієнтовані багато широко розповсюджені способи організації файлів.

Ще одним неодмінним атрибутом швидкого виконання операцій з файлами є можливість безпосереднього доступу до блоків (на відміну від послідовного перебору всіх блоків, що містять файл).

Багато структури даних, які використовуються для швидкого виконання операцій з файлами, використовують покажчики на самі блоки, які являють собою фізичні адреси цих блоків. На жаль, на мові

Pascal (і багатьох інших мовах програмування) не можна писати програми, що працюють з даними на рівні фізичних блоків та їх адрес, - такі операції, як правило, виконуються за допомогою команд файлової системи. Однак буде наведено короткий неформальне опис принципу дії операторів, у яких використовується прямий доступ до блоків.

Хешірованние файли.

Хешування - широко поширений метод забезпечення швидкого доступу до інформації, що зберігається у вторинній пам'яті . Основна ідея цього методу подібна до відкритого хешування. Записи файлу розподіляються між так званими сегментами, кожен з яких складається з зв'язкового списку одного або декількох блоків зовнішньої пам'яті. Є таблиця сегментів, що містить У покажчиків, - по одному на кожен сегмент.

Кожен вказівник у таблиці сегментів є фізична адреса першого блоку зв'язкового списку блоків для відповідного сегмента.

Сегменти пронумеровані від 0 до В-1. Хеш-функція h відображає кожне значення ключа в одне з цілих чисел від 0 до В-1. Якщо x - ключ, то h (x) є номером сегмента, який містить запис з ключем х

(якщо такий запис взагалі існує). Блоки, що складають кожен сегмент, утворюють зв'язний список. Таким чином, заголовок i-го блоку містить покажчик на фізичну адресу (i +1)-го блоку. Останній блок сегмента містить у своєму заголовку NIL-покажчик.

Такий спосіб організації показано на рис.2.

Таблиця

сегментів

Рис.2. Сегменти, що складаються з зв'язкових блоків.

Якщо розмір таблиці сегментів невеликий, її можна зберігати в основній пам'яті. В іншому випадку її можна зберігати послідовним способом в окремих блоках. Якщо потрібно знайти запис з ключем х, обчислюється h (x) і стоїть блок таблиці сегментів, що містить покажчик на перший блок сегмента h (x), поки не виявиться блок, який містить запис з ключем х. Якщо вичерпані всі блоки в зв'язкового списку для сегмента h (x), приходимо до висновку, що х не є ключем жодної із записів.

Така структура виявляється цілком ефективною, якщо в виконуваному операторі вказуються значення ключових полів. Середня кількість звернення до блоків, потрібний для виконання оператора, в якому зазначено ключ запису, приблизно дорівнює середній кількості блоків в сегменті, яке дорівнює n/bk, якщо n - кількість записів, блок містить b записів, а k відповідає кількості сегментів. Таким чином, при такій організації даних оператори, що використовують значення ключів, виконуються в середньому в k разів швидше, ніж у випадку неорганізованого файлу. На жаль, прискорення операцій, не заснованих на використанні ключів, домогтися не вдається, оскільки при виконанні подібних операцій доводиться аналізувати практично весь вміст сегментів. Єдиним універсальним способом прискорення операцій, не заснованих на використанні ключів, мабуть, є застосування вторинних індексів.

Щоб вставити запис з ключем, значення якого дорівнює х, потрібно спочатку перевірити, чи немає у файлі записи з таким ж значенням ключа. Якщо такий запис є, видається повідомлення про помилку, оскільки ми припускаємо, що ключ унікальним чином ідентифікує кожний запис. Якщо записи з ключем х ні, ми вставляємо новий запис у перший же блок ланцюжка для сегменту h (x), в які цей запис вдається вставити. Якщо запис не вдається вставити ні в який з існуючих блоків сегмента h (x), файлової системи видається команда знайти новий блок, до якого буде поміщена цей запис. Цей новий блок потім додається в кінець ланцюжка блоків сегмента h (x).

Щоб видалити запис з ключем х, потрібно спочатку знайти цей запис, а потім встановити її біт видалення. Ще однією можливою стратегією видалення (якої, втім, не можна користуватися, якщо ми маємо справу з закріпленими записами) є заміна віддаленої запису на останній запис в ланцюжку блоків сегмента h (x). Якщо таке вилучення останнього запису призводить до спустошення останнього блоку в сегменті h (x), цей порожній блок можна потім повернути файлової системи для повторного використання.

Добре продумана організація файлів з хешірованним доступом вимагає лише незначної кількості звернень до блоків при випол6неніі кожної операції з файлами. Якщо ми маємо справу з хорошою функцією хешування, а кількість сегментів приблизно дорівнює кількості записів у файлі, поділена на кількість записів, які можуть вміститися в одному блоці, тоді середній сегмент складається з одного блоку. Якщо не брати до уваги звернення до блоків, які можуть знадобитися для перегляду таблиці сегментів, типова операція пошуку даних, заснованого на ключах, потребують лише одного звернення до блоку, а операції вставки, видалення або зміни зажадають двох звернень до блоків. Якщо середня кількість записів у сегменті набагато перевершує кількість записів, які можуть вміститися в одному блоці, можна періодично реорганізовувати таблицю сегментів, подвоюючи кількість сегментів і ділячи кожен сегмент на дві частини.

-------- --------------- 4

2. 3

3.4 0

5.6 2

7.8 1

r1 r2 r3

r4 r5 r6

r7 r8