1. 2ВВЕДЕНІЕ

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

2. Р Е Ф Е Р А Т
"Алгоритми та структури даних мови Pascal"

2.1 Введення

Будь-яка програма, що виконується на ЕОМ, обробляє дані з
метою отримання необхідного результату. У сучасних мовах
програмування (Pascal, C, Modula-2, Ada) є базові типи
даних і засобів побудови структурних типів даних з базо-
вих; вони полегшують складання програм для вирішення складних за-
дач, однак не позбавляють програміста від проблем розробки ал-
горітмов і вибору відповідної структури даних.
При розробці алгоритму вибирається деяка зручна абс-
трактная структура даних і алгоритм розробляється в термінах
операцій над цим абстрактним типом даних.
Після розробки алгоритму вибирається подання абс-
трактной структури даних за допомогою структури даних мови
програмування (відображення на масив, на файли). Якщо завдання
дозволяє, доцільніше використовувати більш прості структури
данних.К таким традиційним структурам даних, що допускають
простий і ефективний подання на ЕОМ, належать масиви,
рядки, записи, стеки, списки, дерева, таблиці, графи, файли.
Дуже часто мова містить лише деякі з перерахованих
структур, а інші доводиться представляти за допомогою маю-
щіхся.Так в Pascal граф можна представити за допомогою масиву або
списку, рядок за допомогою масиву або списку.
Тепер розглянемо послідовно перелічені вище структу-
ри даних та їх представлення через більш прстие застосовне до
мові Pascal.

2.2 _Массів
Змінна або константа, що має структуру масиву, є по-
ся сукупністю елементів одного і того ж типу. Кожна від-
слушна компонента масиву може бути явно позначена, доступ до
ній може здійснюватись за одним або кількома індексам.Чісло
компонент масиву визначається при його описі і під час ра-
боти програми не змінюється. У Pascal масив є стандарт-
вим типом даних. Його оголошення може мати вигляд:
type massiv = array [1 .. 10,1 .. 10] of integer;
або packed array [1 .. 10,1 .. 10] of integer;
var M: massiv;
де М - масив розміром 10 * 10 з цілих чисел, а доступ до
компонентів здійснюється за індексами i і j. Можливість дина-
мічного завдання масиву, як у Modula-2, в Pascal відсутність-
ет. Кількість компонент масиву, їх тип повинні задаватися явно
тобто здаватися до початку роботи програми. Масиви знаходять ши-
рокое застосування при вирішенні багатьох завдань, у тому числі і для
відображення більш складних структур даних.

2.3 _Последовательние файли
Слово "файл" в мові Pascal вживається для об'єктів сос-
тоящіх з компонентів одного і того ж типу. У будь-який момент вре-
мени безпосередньо доступна (для читання і запису) тільки одна
компонента, інші стають доступними у міру просування по
файлу. Таким чином, щоб прочитати елемент файлу необхідно
переглянути всі елементи стоять до нього. Такі файли називають-
ся файлами послідовного доступу або послідовними фай-
лами. Довжина файлу не фіксується і може змінюватися в процесі
виконання програми.
Файловий тип в Pascal - це єдиний тип значень, пос-
редством якого дані, що обробляються програмою, можуть бути
отримані ззовні, а результати передані у зовнішній світ.
У Pascal файловий тип задається наступним чином:
type T = TValue; (тип компоненти файлу)
<Ім'я файлового типу> = file of T;
або packed file of T;
Як звичайно, файловий тип може бути введений у вживання в
розділі типів, як було описано вище, або безпосередньо за-
дан при описі змінних, наприклад:
var myfile: file of T;

Файли, імена яких включаються до списку заголовка програм-
ми, називаються зовнішніми файлами, вони існують поза програмою.
Якщо ж імена файлів не внесені до списку заголовка програми,
то такі файли існують тільки під час виконання програми
і називаються внутрішніми. Внутрішні файли носять в основному
допоміжний характер. Стандартний введення здійснюється з
файлу input, а висновок у файл output.
Для доступу до окремих елементів файлу в Pascal введені
спеціальні процедури. Оператор процедури rewrite (f) встановлюється
кість файл у режим запису, якщо раніше в цей файл були записані
якісь дані, то вони губляться. Оператор процедури write (f, x)
записує в файл f чергову компоненту x, після чого вікно
зсувається на наступну позицію.
Якщо який-то, компоненти якого вже записані раніше, необ-
ходимо прочитати, то для цього в Pascal використовуються стандартні
процедури reset і read. Оператор процедури reset (f) переводить
файл f в режим читання і встановлює вікно на першого пози-
цію файлу. Оператор процедури read (f, v) присвоює змінній
v значення поточної компоненти з файлу f і пересуває вікно на
наступну позицію. Процедура reset може застосовуватися до одного і
того ж файлу кілька разів і при цьому вміст його не вимірюв-
вується.
Якщо необхідно розділити копіювання поточного елемента і
пересування вікна, використовують стандартні процедури з вико-
ристанням буферної змінної. Вона позначається f?, Де f - ім'я
файлу. Тоді при читанні копіюється значення елемента з вікна
е: = f? і вікно зсувається оператором процедури get (f). При запи-
сі спочатку буферної змінної привласнюється значення нового
елемента файла f?: = e і вікно зсувається оператором процедури
put (f).
Робота з файлом може проходити або в режимі запису, або в
режимі чтенія.Для визначення кінця файлу в Pascal є
стандартна логічна функція eof (end of file).
Операція конкатенації двох файлів і відношення рівності над
файлами в Pascal не визначені, але їх достатньо просто реалі-
тися засобами мови.

2.4 _Спіскі
Використання тільки статичних об'єктів при програмування-
нії може викликати певні труднощі, тому що не завжди
вдається отримати ефективну програму, а ефективність при ре-
шеніі багатьох завдань є головним чинником. Інколи до роботи
програми ми не знаємо не тільки розміру значення об'єкта, але і
навіть того, чи буде він існувати чи ні. Такого роду прог-
раммние об'єкти, які виникають при виконанні програми або
розмір яких змінюється під час виконання програми, називаються
вають динамічними. Мова Pascal передбачає можливість
складання ефективних програм з використанням динамічних
об'єктів. При цьому динамічний об'єкт не може мати власної
ного імені, тому що всі ідентифікатори повинні бути описані в
відповідних розділах програми. Тому в Pascal прийнято не
іменувати, а позначати динамічний об'єкт і введено спеці-
ний контрольний тип. Значення цього типу є посилання на
програмний об'єкт, за якою здійснюється прямий доступ до
цьому об'єкту. Динамічний об'єкт позначається приєднанням
символу? до імені змінної-посилання на цей об'єкт:
type T = integer; (тип динамічного об'єкта)
pointer = ^ T; (ім'я посилального типу - pointer)
Змінна-посилання повинне бути описана в розділі var:
var p: pointer;
Значеннями посилального типу є значення адрес одиниць
оперативної пам'яті конкретної машини. Значення NIL належить
посилальної будь-якого типу. Воно вказує на відсутність зв'язку з
об'єктом. Сам динамічний об'єкт породжується за допомогою стан-
дротяні процедури new, фактичним параметром якої є
посилання на цей об'єкт. Виконання процедури new (p) породжує
динамічний об'єкт типу Т, тобто процедура new шукає в оперативними-
ної пам'яті незадіяну до цього моменту область пам'яті
відповідного розміру і привласнює змінної-посиланням p значення
адреси початку цієї області.
У мові Pascal також визначена спеціальна процедура
dispose, нищівна динамічний об'єкт, тобто вивільняє
область пам'яті, зарезервованої під цей об'єкт. Динамічні
об'єкти розміщуються на зовнішніх носіях зазвичай мають струк-
туру файлу.
За допомогою посилального типу можна створювати динамічні
структури самого різноманітного характеру, наприклад лінійні
списки.
Структура даних, де кожний інформаційний елемент постачає-
ся посиланням на наступний за ним, називається зв'язковим списком. В
списку передбачено заголовної ланка. Покажчик списку, значен-
ням якого є посилання на головній ланка, представляє
список як єдиний об'єкт. Однонаправлений список з цілих чи-
сів на Pascal можна організувати так:
type TValue = integer;
pointer = ^ element;
element = record
info: TValue;
next: pointer;
end;
list = pointer;
де поле next - покажчик на наступний елемент списку. Ука-
затель останнього елемента дорівнює NIL. Однак при використанні
односпрямований списків для розв'язання деяких завдань можуть віз-
нікнуть певні труднощі. За однонаправленої списку
можна рухатися тільки в один бік - від першого елементу до
останньому. Тим часом нерідко необхідно провести обробку
елементів, що передують елементу із заданою властивістю. Для
усунення цього незручності в кожен елемент додається ще
одне поле prev - покажчик на попередній елемент:
type pointer = ^ element;
element = record
info: TValue;
prev: pointer;
next: pointer;
end;
dlist = pointer;
Динамічна структура складається з ланок такого типу на-
ни опиняються двонаправленим списком. Наявність посилання на попередній
елемент списку дозволяє рухатися в будь-якому напрямку по спис-
ку. У полі prev заголовного ланки стоїть посилання NIL, так як у
заголовного ланки немає попереднього. Іноді значенням поля next
останньої ланки ставлять посилання на головній ланка, а в полі
prev заголовного ланки - посилання на останню ланку. Список зами-
кається в "кільце". Списки такого виду називають кільцевими.
Списки також допускають відображення на масив, наприклад одно-
спрямований список допускає таке відображення:
type elem = record
info: TValue;
next: integer;
end;
list = array [1 .. 10] of elem;
var L: list;
use, free: integer;
де поле next - покажчик на розташування (індекс) Наст-
го елемента в масиві, а мінлива use вказує на першому
елемент списку. Також використовується список вільних елементів,
теж пов'язаних між собою. Змінна free вказує на першому
елемент списку вільних елементів. Відображення на масив є-
ся менш вдалим, так як кількість записів у списку заздалегідь
обмежується максимальним числом, тобто розміром масиву. Сле-
послідовно список перестає бути динамічною структурою.
Для зручної роботи над списком визначаються наступні базо-
ві операції:

Init (L) - створення списку.
Insert (L, n, v) - вставка елемента v до списку під номером n.
Delete (n) - видалення n-го елемента списку або видалення еле-
мента по імені.
Print (L) - друк списку.
Find (L, v) - пошук елемента в списку.

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

2.5 Оч _ередь
Черга - впорядкований, одновимірний,, змінюваний
набір компонентів, в якому включення нових компонент вироб-
диться з одного кінця черги, а доступ і виключення з іншого.
Довгій черги називається кількість її компонент. Черга яв-
ляется динамічним об'єктом і довжина її не фіксується. Так
як у Pascal немає структурного типу чергу, його можна відобра-
возити на вже наявні структури: файл і масив. Відображення
черги з цілих чисел на масив можна реалізувати так:
const N = 10;
type Qel: integer;
Queue: record
first, last: integer;
body: array [1 .. N] of Qel;
end;
де first та last - покажчики на першій і останній елемент
черзі відповідно, а N - максимальне число компонент оче-
реді. Відображення на масив накладає обмеження на довжину
черги, крім того програміст сам забороняє собі прямий дос-
туп до елементів масиву. Для роботи з чергою реалізуються сле-
дмуть процедури:

Init (Q) - процедура створення черги Q.
Empty (Q) - логічна функція, якщо чергу порожня Empty ви-
дає значення true, якщо ні - false.
Pop (Q) - процедура, виштовхуюча перший елемент черги Q.
Top (Q) - функція, що видає значення першого елемента черги.
Push (Q, v) - процедура, що додає новий елемент v типу Qel
в кінець черги Q.
Print (Q) - процедура, роздруковуються вміст черги.
Size (Q) - функція, що видає число компонент (довжину) черги.

Відображення черзі на файл виглядає так:
type T = Qel;
Queue = file of T;
Операції над чергою визначаються також як і при відображений-
панії на масив, а обробка елементів ведеться з використанням
буферної змінної. При такому відображенні час на операції
витрачається більше, тому що файл доводиться весь час "перемат-
вать ".
На Pascal чергу може бути організована і як двунаправ-
ленний список:
type T = Qel;
pointer = ^ T;
Queue = record
info: T;
pred, sled: pointer;
end;
де pred і sled - покажчики на попередній і наступний еле-
мент черги. Операції над чергою за такої організації визна-
виділяється аналогічно.

2.6 _Стек
Стек - структура даних, у якій можна додавати і уда-
лять елементи даних, при цьому безпосередньо доступний тільки
останній доданий елемент. Як і черга стек в Pascal мож-
але організувати у вигляді лінійного списку:
type pointer = ^ elem;
elem = record
info: TValue;
sled: pointer;
end;
Stask = pointer;
або відображення на масив:
const N = 10;
type Stask = record
tp: integer;
body: array [1 .. N] of TValue;
end;
Для роботи зі стеком реалізуються процедури:

Init (S) - процедура створення стека S.
Empty (S) - логічна функція, що видає true якщо стек порожній
і false якщо в ньому є елементи.
Push (S, v) - процедура вставляються новий елемент v в стек.
Pop (S) - процедура виштовхуюча верхній елемент зі стека.
Top (S) - функція, що повертає значення верхнього елементу
стека.
Size (S) - функція, яка повертає число елементів стека.
Display (S) - процедура, роздруковуються вміст стека.

Маючи ці базові процедури досить просто реалізувати про-
цедури: вставки елемента в стек під якимсь номером
(Insert (S, v, n)) і видалення елемента з стека за значенням
(Remove (S)). Треба зауважити, що стек - одна з найбільш викорис-
зуемих структур даних, яка виявляється дуже зручною при
вирішенні різних завдань.

2.7 _Дек
Deque (double-ended queue) - двостороння чергу, структу-
ра даних, де елементи можуть додаватися і видалятися з обох
кінців. Грудень є і стеком і чергою одночасно. При реа-
лізації повинні бути визначені операції: вставка нового елементом
та в початок дека, вставка нового елемента в кінець дека, видаліть-
ня (або перегляд) елемента з початку дека, видалення елемента
з кінця дека.

2.8 _Графи
Безліч об'єктів з'єднаних довільним чином, але не
більш ніж однією лінією зв'язку між двома об'єктами - називається
графом.Связний граф - коли є шлях між двома вершинами,
орієнтований граф - в якому лінії зв'язку мають певний
направленіе.Прі використанні графів часто виникає проблема
пошуку шляху між двома вершинами.
У Pascal зручно для цієї мети представляти граф у вигляді мат-
Ріци суміжності, в якій зберігається інформація про зв'язки між
вершинами графа.Еслі граф містить N вершин, то матриця смеж-
ності - квадратна Булевського матриця N * N, в якій
М (i, j) = true, якщо є зв'язок між i-ий і j-ий вершинами і
М (i, j) = false в іншому випадку. Для неорієнтовані графів
матриця суміжності симетрична.
Граф з К вершинами можна також представити у вигляді До списків,
відповідних вершин і містять номери вершин з якими
у даної є связь.Еслі граф змінюється в процесі обробки,
тобто додаються й видаляються вершини та лінії зв'язку, то зручное
використовувати списки.
Графи застосовуються в задачах машинного проектування і в
створення систем штучного інтелекту.

2.9 _Деревья
Дерево - окремий випадок графа.Структура визначається рекур-
пасивного, утворена даними елементом, який називають коренем дерева,
і кінцевим списком із змінним числом елементів - дерев то-
го ж типу, які називаються піддерев. Двійковим або бінарним де-
ревом називається дерево складається з кореня, правого і лівого
піддерев.
У Pascal двійкове дерево можна визначити так:
type BTree = ^ BNode;
BNode = record
info: TValue;
left, right: BTree;
end;
При аналізі структур даних, заданих у вигляді дерева, примі-
няются різні способи перегляду та перебору узлов.Основная
особливість кожного обходу полягає в тому, що переглядаючи-
ються всі вузли дерева в певному порядку, причому кожен вузол
обробляється рівно один раз.
Для бінарного дерева визначені три способи обходу: прямий
або префіксний (корінь - ліве піддерево - праве підтри-
во), зворотний або інфіксний (ліве піддерево - корінь - праве
піддерево) і кінцевий або постфіксний (ліве піддерево - праве
піддерево - корінь).
При обході дерева використовуються рекурсивні процедури або
стек.В прошитих деревах використовуються додаткові покажчики
на наявність піддерев (LTAG і RTAG). Введення додаткових
покажчиків не призводить до великого збільшення витрат пам'яті, але
дозволяє при обході відмовитися від стека.
Треба відзначити, що будь-яке дерево загального вигляду можна уявити
у вигляді довічного, треба у вихідному дереві у кожного вузла З'єднан-
нитка його синів від старшого до молодшого і прибрати всі зв'язки вузла
з синами, залишивши тільки зв'язок зі старшим сином.
Над деревами зручно визначити операції: читання інфор-
онной частини з вузла дерева, створення дерева, приєднання до
вузла нового піддереві, видалення піддереві.
Особливо корисні дерева при сортіровке.Алгорітм полягає в
те, що під час перегляду даних черговий елемент міститься в
двійкове дерево. Ключ нового елемента порівнюється з ключем те-
кущего узла.Еслі покажчик поточного вузла NIL, то покажчик на
новий вузол додається в те місце звідки був витягнутий NIL.Еслі
ключ нового вузла менше ключа поточного вузла, то пошук місця для
нового вузла продовжується в лівому піддереві, якщо більше - в
правом.После того, як всі дані занесені в двійкове дерево
сортування, виконується зворотний обхід дерева з висновком.
Дерева застосовуються також при інтерпретації та обчисленні
як арифметичних, так і логічних.

Тепер розглянемо області застосування складних структур дан-
них.Одной з таких областей є процес створення компіля-
торів, який відпрацьований достатньо добре.
Оригінальний текст розбивається на лексеми (ідентифікатори, конс-
танто, знаки операцій). Лексеми заносяться в таблиці, а в тексті
лексема замінюється посиланням на елемент таблиці, таким чином
текст програми замінюється на послідовність лексем. Для
того, щоб один і той же ідентифікатор замінювався посиланням на
один і той же елемент таблиці, необходлімо для кожного аналізі-
руемого ідентифікатора переглядати всі зустрілися раніше.
Для прискорення цього пошуку застосовуються: упорядкування елементів
таблиці (сортування) для подальшого бінарного пошуку, хеш-ад-
ресація і деякі інші способи.Для зберігання послідовник-
ності лексем використовують масиви і списки.
Наступним етапом після заміни тексту програми на ланцюжок
лексем є синтаксичний аналіз, при якому широко ис-
користуються стеки, таблиці і рядки.
В операційних системах поширені такі складні струк-
тури даних, як черги. Операційна система змушена під-
держівать кілька черг: черга процесів готових до ви-
полнению, черга на свопінг на диск і черги до пристроїв
(наприклад з принтером).
Складні структури даних використовуються також в системах уп-
равленія базами даних (СУБД). СУБД можуть накопичувати інфор-
цію про велику кількість об'єктів, опис яких містять різні
відомості.
Властивості об'єктів можуть виступати в ролі ключів (наприклад
прізвище службовця) і тоді за цим властивостям об'єкти можуть бути
відсортовані, що значно прискорює пошук.
Для опису об'єктів зазвичай використовують записи, які в
свою чергу можуть містити посилання на список із записів.
Нарешті, ще однією областю застосування є завдання із використанням
користуванням розріджених матриць (з відносно невеликим чис-
лом ненульових елементів). Іноді при нестачі оперативної пам'яті
буває вигідно зберігати тільки ненульові елементи, застосовуючи раз-
особисті методи упаковки (у три масиву, в один масив, за допомогою
зв'язкового списку і т.д.).
Мова Pascal надає досить гнучкі можливості у відно-
шеніі використовуваних структур даних. Вдалий вибір структури
даних впливає на простоту алгоритму, і отже зменшує
трудомісткість розробки і підвищує надійність.

2.10 С П И С О К И С П О Л Ь З О В А Н Н И Х
І С Т О Ч Н И К О В

1. В. М. Брябрін. Програмне забезпечення персональних
ЕОМ, М., "Наука", 1990.

2. Н. Вірт. Програмування на мові Модула-2,
М., "Світ", 1987.

3. К. Крістіан. Введення в операційну систему UNIX,
М., "Фінанси і статистика", 1985.

4. М. І. Беляков, Ю. І. Рабовер, А. Л. Фрідман.
Мобільний операційна система, М., "Радіо і зв'язок",
1991.

5. Ф. Л. Бауер, Г. Гооз, Інформатика, т.2, М., "Світ",
1990.

6. В. Г. Абрамов, Н. П. Трифонов, Г. Н. Трифонова,
Введення в мову паскаль, М., "Наука", 1988.

7. І. З. Лугова, Л. Н. Чернишов, С. М. Юдін,
Динамічні структури даних мови паскаль, М.,
видавництво МАІ, 1988.

8. Л. Н. Чернишов, С. М. Юдін, Інструментальна система
ІНФОРТ і робота з динамічними структурами даних,
М., видавництво МАІ, 1984.

9. Лекції, семінари, консультації з АЯП.