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

Хоча терміни тип даних (чи навіть тип), структура даних, і абстрактний тип даних звучать схоже, але мають вони різний зміст. У мовами програмування тип даних перемінної позначає безліч значень, що може приймати ця змінна. Наприклад, змінна булевого (логічного) типу може приймати тільки два значення: значення 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 означатиме нульпокажчик під час використання курсоров і покажчиків. Але, ніж виникали проблеми при цього угоди, слід також умовитися, що масиви, куди вказують курсоры, індексуються починаючи із першого, а чи не з 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 для і = 1, 2, …, n-1 і аi слід за ai-1 для і = 2, 3, …, n. Говориться також, що елемент аi має позицію і. З іншого боку, постулюється існування позиції, наступній за останнім елементом списку. Функція END (L) повертатиме позицію, таку за позицією n в n-элементном списку L. Слід зазначити, позиція END (L), розглянута як відстань з початку списку, може змінюватися при зменшенні чи збільшенні списку, тоді як інші позиції мають фіксований (незмінне) відстань з початку списка.

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

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

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

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

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

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

LOCATE (x, L). Ця функція повертає позицію об'єкта x у списку L. если у списку об'єкт x зустрічається кілька разів, то повертається позиція першого з початку списку об'єкта x. Якщо об'єкта x немає у списку 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-firstout — останній ввійшов — перший вийшов). Інтуїтивними моделями стека можуть бути колода карт на столі при гру покер, книжки, складені до стопки, чи стос тарілок полиці буфета; в усіх цих моделях взяти можна тільки верхній предмет, а додати новий об'єкт можна, лише поклавши його за верхній. Абстрактні типи даних сімейства STAK (Стік) зазвичай використовують наступні п’ять операторов.

MAKENULL (S). Робить стік P. S пустым.

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

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

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

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

EMPTY (S). Ця функція повертає значення true (істина), якщо стік P. 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.

x.

Таблица.

Сегментов.

Рис. 2. Сегменти, які з зв’язкових блоков.

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

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

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

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

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

———————————- 4.

2. 3.

3.

3.4 0.

5.6 2.

7.8 1.

r1 r2 r3.

r4 r5 r6.

r7 r8.