Лабораторна робота № 3

Лабораторна робота № 2

Записи. Масиви записів.............................………...….........................11

Лабораторна робота № 3

Типізовані послідовні файли..............................…………...................15

5 Лабораторна робота № 4

Організація черги за допомогою списку................……..………........19

6 Лабораторна робота № 5

Організація стека за допомогою списку..………....……...................25

7 Лабораторна робота № 6

Реалізація двунаправленого циклічного списку...……..……............27

8 Лабораторна робота № 7

Застосування бінарних дерев....…........................................………....34

9 Література..........…...............................................................…………..37

1 ЗАГАЛЬНI ВIДОМОСТI ПРО СПОСОБИ ПОДАННЯ СТРУКТУРНОЇ IНФОРМАЦIЇ В ЕОМ

В цьому роздiлi викладенi концепцiї подання структурної iнформацiї в ОП ЕОМ.

Логiчна структура даних не несе у собi iнформацiї про те, яким чином данi та зв'язки мiж ними подаються в пам'ятi ЕОМ.

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

Проблема вiдображення абстрактних структур зберiгання полягає у знаходженнi ефективних методiв, тобто таких, котрим вiдповiдають наступні якостi:

- легка формалiзуємiсть з можливiстю подання результата формалiзацii у виглядi адресної функцiї;

- можливiсть реалiзацiї адресної функцiї простим алгоритмом з мiнiмальним обчисленням та виконання вiдображення в автоматичному режимi;

- адресацiя елементiв даних.

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

При реалiзацiї адресних функцiй слiд пам'ятати адресну структуру ОП ЕОМ, у яких пам'ять подана як єдиний вектор з елементами - байтами, проiдентифікованими адресами та впорядкованими по збiльшенню адрес вiд 0 до найбiльшої. Ця

структура вiдображає найбiльш вiдповiдну структуру даних для зберiгання в ОП - кiнцеву послiдовнiсть, яку називають списком. Список - лiнiйна структура. Багато типiв абстрактних структур без особливих перешкод можуть бути перебудованi у список. Це дуже важливо, тому що для вiдображення списка у структуру зберiгання

iменi застосовується тип адресних функцiй: послiдовне або зв'язане розподілення пам'ятi.

При послiдовному розподіленнi пам'ятi елементи списка розташовуються у послiдовних елементах пам'ятi.

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

Зв'язане подання списка називається зв'язанним списком. Зв'язанi списки - зручна форма подання в пам'ятi ЕОМ абстрактних лiнiйних структур, що диннамічно змінюються. Вказанi типи адресних функцiй застосовують тiльки для спискiв. Велику кiлькiсть типiв абстрактних структур не можливо перебудувати до списку.

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

Нелiнiйна абстрактна структура моделюється з багатозв'язаним списком. До багатозв'язаного списку застосовується адресна функцiя зв'язного розподiлення пам'ятi. Багатозв'язний список вiдрiзняється вiд списка наявнiстю явно заданих зв'язкiв мiж собою.