Структура даних і алгоритми на мові pascal

Структура даних і алгоритми на мові Pascal

Черги, стеки, пов'язані списки і дерева


Програми складаються з алгоритмів і структур даних. Хороші програми використовують переваги їх обох. Вибір і розробка структури даних настільки ж важлива, як і розробка процедури, яка маніпулює ними. Організація інформації та методи доступу до неї зазвичай визначаються характером стоїть перед програмістом завдання. Тому кожен програміст повинен мати в своєму "доробку" відповідні методи представлення та пошуку даних, які можна застосувати в кожній конкретній ситуації.
Насправді структури даних в ЕОМ будуються на основі базових типів даних, таких як "char", "integer", "real". На наступному рівні знаходяться масиви, що представляють собою набори базових типів даних. Потім йдуть записи, що представляють собою групи типів даних, доступ до яких здійснюється по одному з даних, а на останньому рівні, коли вже не розглядаються фізичні аспекти представлення даних, увага звертається на порядок, в якому дані зберігаються і в якому робиться їх пошук. По суті фізичні дані пов'язані з "машиною даних", яка управляє способом доступу до інформації у вашій програмі. Є чотири такі "машини":
  • чергу;
  • стек;
  • пов'язаний список;
  • двоичное дерево.

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


Черга є лінійний список даних, доступ до якого здійснюється за принципом "перший увійшов, перший вийшов" / іноді скорочено його називають методом доступу FIFO /. Елемент, який був першим поставлений в чергу, буде першим отриманий при пошуку. Елемент, поставлений в чергу другим, при пошуку буде отримано також другим і т.д. Цей спосіб є єдиним при постановці елементів в чергу і при пошуку елементів в черзі. Застосування черги не дозволяє робити прямий доступ до будь-якого окремого елементу.
У повсякденному житті черзі зустрічаються часто. Наприклад, черга в банку або чергу в кафетеріях з швидким обслуговуванням є чергою в зазначеному вище сенсі / виключаючи ті випадку, коли людина намагається домогтися обслуговування позачергово! /. Для того, щоб краще зрозуміти роботу черги, розглянемо дві процедури: постановка в чергу і вибірка з черги. При виконанні процедури постановки в чергу була розташована в кінець черги. При виконанні процедури вибірки з черги з неї видаляється перший елемент, який є результатом виконання даної процедури. Робота черзі проілюстрована на рис.1. Слід пам'ятати, що при вибірці з черги з неї дійсно видаляється один елемент. Якщо цей елемент ніде не буде збережений, то надалі до нього не можна буде здійснити доступ.
Рис.1. Робота черзі: 1 - постановка в чергу; 2 - вибірка з черги елемента А, В, С.
Черги в програмуванні використовуються в багатьох випадках, наприклад, при моделюванні (обговорюється нижче у відповідній главі), при плануванні робіт (метод Перт або графіки Гатта), при буферизації введення-виведення.
Як приклад розглянемо просту програму планування приписів, яка дозволяє звертатися до кількох приписами. При кожному зверненні припис видаляється зі списку і на екран виводиться наступне припис. Для простоти в програмі використовується масив символьних рядків для управління подіями. Опис приписи обмежується 80 символами і число розпоряджень не повинно перевищувати 100. Перш за все в цій програмі планування повинні бути передбачені процедура постановки в чергу і процедура вибірки з черги. Ці процедури наводяться нижче і даються необхідні описи глобальних змінних і типів даних.
У роботі цих функцій використовуються три глобальні змінні: "spos", яка містить індекс наступного вільного елементу; "Rpos", яка містить індекс наступного обраного елемента і "event", яка являє собою масив символьних рядків з описом приписів. Змінні "spos" і "rpos" повинні бути встановлені в нульове значення до першого звернення до процедур постановки в чергу і вибірки з черги.
У цій програмі процедура постановки в чергу поміщає нові події в кінець списку і робить перевірку заповнення списку. Функція вибірки з черги вибирає події з черги при необхідності їх обробки. Коли планується нове подія, змінна "spos" збільшується на одиницю, а коли подія завершується, то збільшується на одиницю змінна "rpos". Фактично змінна "rpos" переслідує змінну "spos" в проходах по черзі. Цей процес ілюструється на рис.2. Якщо значення покажчика вільного місця збігається зі значенням покажчика обраного елемента, то це означає, що в черзі немає подій. Слід пам'ятати, що хоча функція вибірки елемента з черги насправді не порушує інформацію в черзі, повторний доступ до неї неможливий і фактично вона зникає.
Нижче наводиться цілком програма, що здійснює просте планування приписами. Ви можете вдосконалити цю програму за власним бажанням.

циклічна чергу

2 - покажчик зв'язку;

1 Новий перший елемент

1 Deleting the First Item

6 Deleting a Middle Item

7 Deleting the Last Item

Списки з подвійним зв'язком

1 Inserling a New First Element

1 Deleting the First Item

6 Deleting a Middle Item

7 Deleting the Last Item


Рис.9. Видалення елемента зі списку з подвійним зв'язком: 1 - видалення першого елемента; 2 - інформаційні поля; 3 - лівий список перетворюється в правий; 4 - віддалений елемент; 5 - указу- тель з нульовим значенням; 6 - видалення середнього елемента; 7 - видалення останнього елемента.
Нижче наводиться функція, яка виконує видалення елемента типу "address" зі списку з подвійним зв'язком:
Цій функції передається на один покажчик менше, ніж для відповідної функції при використанні списку з одним зв'язком. / Віддалений елемент вже має покажчик на попередній елемент і покажчик на наступний елемент /. Оскільки перший елемент в списку може змінитися, функція повертає покажчик на початок списку.


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

двійкового дерева


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