Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
усе, що реалізовано в одній з цих конструкцій, можна зробити і в інших.
|
|
Будь-який алгоритм може бути реалізований відповідною машиною Тьюринґа.
Це основна гіпотеза теорії алгоритмів у формі Тьюринґа. Одночасно ця теза є формальним визначенням алгоритму. Завдяки їй можна доводити існування або неіснування алгоритмів, створюючи відповідні машини Тьюринґа або доводячи неможливість їхньої побудови. Завдяки цьому з’являється загальний підхід до пошуку алгоритмічних розв’язків.
Якщо пошук розв’язку наштовхується на перешкоду, то можна використовувати цю перешкоду для доведення неможливості розв’язування, спираючись на основну гіпотезу теорії алгоритмів. Якщо ж при доказі неможливості виникає своя перешкода, то вона може допомогти просунутися в пошуку розв’язку, хоча б частково усунувши стару перешкоду. Так, по черзі намагаючись довести то існування, то відсутність розв’язку, можна поступово наблизитися до розуміння суті поставленної задачі.
Довести тезу Тьюринґа не можна, тому що в його формулюванні не визначене поняття будь-який алгоритм, тобто ліва частина тотожністі. Його можна тільки обґрунтувати, подаючи різноманітні відомі алгоритми у вигляді машин Тьюринґа. Додаткове обґрунтування цієї тези полягає в тому, що пізніше було запропоновано ще декілька загальних визначень поняття алгоритму і щораз вдавалося довести, що, хоча нові алгоритмічні схеми і виглядають інакше, вони насправді еквівалентні машинам Тьюринґа:
усе, що реалізовано в одній з цих конструкцій, можна зробити і в інших.
Ці твердження доводяться строго, тому що в них мова йде вже про тотожність формальних схем.
1.7.4. Рекурсія та її використання
Означення називається рекурсивним, якщо воно задає елементи множини за допомогою інших елементів цієї ж множини. Об’єкти, задані рекурсивним означенням, також називаються рекурсивними. Нарешті, рекурсія – це використання в алгоритмі рекурсивних означень.
Рекурсивною функцією називається функція, яка може бути отримана з базових функцій за допомогою скінченної кількості застосувань підстановок, та примітивних рекурсій.
До базових примітивних рекурсивних функцій відносяться три функції:
1) нуль-функція Z (x)=0 при будь-якому x;
2) додавання одиниці: N (x) = x +1;
3) проектуючі функції: Ui (x 1, …, xn)= xi для всіх x1, …, xn. (визначає натуральне число з цієї множини).
Функція f (x 1, …, xn) отримана з функцій g, h 1, …, hm, за допомогою підстановки, якщо f (x 1, …, xn) = g (h 1(x 1, …, xn), …, h 1(x 1, …, xn)).
Функція f (x 1, …, xn, y) отримана за допомогою рекурсії, якщо:
f (x 1, …, xn, y+1) = h (x 1, …, xn, y, f (x 1, …, xn, y));
f (x 1, …, xn, 0) = g (x 1, …, xn) при n ≠ 0;
f (y +1) = h (y, f (y)); f (0) = k, k – ціле невід’ємне число при n = 0.
Функція f (x1, …, xn) отримана за допомогою μ -оператора, якщо її значення дорівнює мінімальному значенню y, при якому g ((x 1, …, xn, y)=0.
Частково рекурсивною називається функція, яка конструюється за допомогою скінченного числа підстановок, рекурсій та μ -операторів, але визначена не при всіх значеннях арґументів.
Якщо деяка функція може бути сконструйована з базових функцій за допомогою скінченного числа тільки підстановок та рекурсій, вона називається примітивно рекурсивною.
Приклад 1.10. Визначення функції «факторіал» задаються виразом: 0! =1, n! =n× (n-1)!. Вони утворюють множину {1, 2, 6, …}: 0! =1, 1! =1, 2! =2, 3! =6, …. Усі її елементи, крім першого, визначаються рекурсивно.
Отже, функція «факторіал» задається рекурентним співвідношенням порядку 1 і початковим відрізком 0! =1. Загалом, будь-яке рекурентне співвідношення порядку k разом із завданням перших k елементів послідовності є прикладом рекурсивного означення.
Приклад 1.11. Арифметичні вирази зі сталими та знаком операції ‘+’ у повному дужковому записі (ПДЗ) задаються таким означенням:
1) стала є виразом у ПДЗ;
2) якщо E і F є виразами у ПДЗ, то (E)+(F) також є виразом у ПДЗ.
Такими виразами є, наприклад, 1, 2, (1)+(2), ((1)+(2))+(1). Всі вони, крім сталих, означаються рекурсивно.
Для коректного виходу з рекурсії повинні виконуватися умови:
ü множина означуваних об’єктів є частково упорядкованою;
ü кожна спадна за цим впорядкуванням послідовність елементів закінчується деяким мінімальним елементом;
ü мінімальні елементи означаються нерекурсивно;
ü немінімальні елементи означаються за допомогою менших від них елементів.
Глибина рекурсії – кількість викликів підпрограми, що реалізують рекурсію.
Вживання рекурсивних підпрограм вимагає обережності та вміння оцінити можливу глибину рекурсії та загальну кількість викликів. Не завжди треба писати рекурсивні підпрограми безпосередньо за рекурсивним означенням. Справа в тому, що виконання кожного виклику підпрограми потребує додаткових дій комп’ютера. Тому «циклічний» варіант описання обчислень виконується, як правило, швидше від рекурсивного. Також не треба вживати рекурсію для обчислення елементів рекурентних послідовностей. За великої глибини рекурсії це взагалі може призвести до вичерпання автоматичної пам’яті та аварійного завершення програми.
Наведемо приклад нерекурсивного та рекурсивного визначення значення функції.
Приклад 1.12. Маємо функцію, що розкладається у ряд:
.
#include < stdio.h>
#include < math.h>
double func1(int n); // прототип нерекурсивної функції ряду
double func2(int n); // прототип рекурсивної функції ряду
void main()
{
int n; // n – кількість елементів ряду
double s=1; // значення функції
scanf(“%n”, & n); // ввели кількість елементів ряду
printf(“Nonrecursiv esult is %6.2f”, func1(n));
printf(“Recursiv esult is %6.2f”, func2(n));
}
double func1(int n)
{
double s=1;
int x; // x – поточний член ряду
for(x=1; x< =n; x++)
s*=x/(exp(x) – x*x)
return (s);
}
double func2(int n)
{
double s=1;
if (n< 1) // умова виходу з рекурсії
return (s);
else
s*=n/(exp(n) – n*n)*func2(n-1); // виклик рекурсивної функції з n-1
}
Найкраще рекурсію використовувати тоді, коли розв’язання задачі з допомогою рекурсії загалом зводиться до розв’язання подібної задачі, але меншої розмірності, а, отже, легшої для розв’язання.
Найяскравіший приклад задачі такого плану – задача про ханойські вежі.
Легенда свідчить, що десь в Ханої знаходиться храм, в якому розміщена така конструкція: на підставці знаходяться 3 діамантових стержня, на яких при створенні світу Брахма нанизав 64 золотих диска із отвором посередині, причому внизу опинився найбільший диск, на ньому трохи менший і так далі, поки на верхівці піраміди не опинився найменший диск. Жерці храму зобов’язані перекладати диски за такими правилами:
1) за один хід можна перенести лише один диск,
2) не можна класти більший диск на менший.
Керуючись цими правилами, жерці повинні перенести початкову піраміду з 1-го стержня на 3-й. Як тільки вони впораються з цим завданням, настане| кінець світу.
Для розв’язання задачі спочатку спробуємо побудувати абстрактну модель процесу перенесення частини піраміди.
Отже, вирішуємо узагальнену задачу: як перенести піраміду з n кілець із стержня і на стержень j, користуючись стержнем k як допоміжним? Ця задача розв’язується таким чином.
1. Перенести (n-1) кільце i на k.
2. Перенести 1 кільце з i на j.
3. Перенести (n-1) кільце на j.
Отже, задача перенесення n кілець розв’язується через перенесення (n-1) кільця. Залишилося лише додати тривіальну граничну умову для виродженого випадку перенесення порожньої піраміди з 0 кілець, щоб наш алгоритм завершився.
Реалізація алгоритму на мові С:
void Hanoj (int n, short i, short j, short k)
// перенесення піраміди з n дисків з стержня i
// на стержень j, використовуючи стержень k як допоміжний
{
// перевірка граничної умови – порожню піраміду не переміщувати
if (! n) return;
Hanoj (n-1, i, k, j);
// переносимо одне кільцо – фактично це Hanoj (1, i, j, k);
printf(«%2d - %2d\n», i, j);
Hanoj (n-1, k, j, i);
}
1.7.5. Теза Чорча. Алгоритмічно нерозв’язні проблеми
Теза Чорча часто формулюється в еквівалентній формі, а саме: будь-який алгоритм в інтуїтивному розумінні цього слова може бути реалізований за допомогою деякої машини Тьюринґа. Іншими словами, за допомогою машини Тьюринґа можна розв’язати будь-яку задачу, для якої існує алгоритм розв’язування в інтуїтивному розумінні.
Довести тезу Чорча неможливо. Її можна було б спростувати, якби були запропоновані формалізації поняття алгоритму, здатні обчислювати нерекурсивні функції. Але таких формалізмів досі запропоновано не було.
Якщо ми визнаємо тезу Чорча, ми можемо прийняти машину Тьюринґа як основу для загального визначення алгоритму: алгоритм є послідовністю інструкцій, яка може бути виконана за допомогою машини Тьюринґа або еквівалентної їй обчислювальної моделі.
Тепер ми можемо дати більш чітке визначення універсального комп’ютера: універсальним називається комп’ютер, за допомогою якого можна промоделювати роботу машини Тьюринґа.
Якщо теза Чорча є справедливою, ми маємо визнати наступне. Якщо вдається довести, що не існує машини Тьюринґа, яка могла б вирішити певну проблему, то ця проблема є алгоритмічно нерозв’язною, тобто для неї не існує загального алгоритму розв’язування. Такі проблеми насправді існують.
Наприклад, це знаменита проблема зупинки, яка формулюється так: потрібно для будь-яких початкових даних визначити, зупиниться машина Тьюринґа чи ні. Оскільки будь-яка програма, яка працює на будь-якому комп’ютері, може бути реалізована і на машині Тьюринґа, це твердження можна переформулювати так: не існує загального алгоритму, який для будь-якої програми заздалегідь визначав би, зупиниться вона чи ні.
Але можна навести формалізми, які полегшують програмування і дозволяють здійснювати обчислення швидше, ніж машини Тьюринґа.
Резюме
1. Інформація – це відомості, пояснення, знання про всілякі об’єкти, явища, процеси реального світу
2. Інформатика – це наука про методи подання, накопичення, передавання та опрацювання інформації за допомогою комп’ютера.
3. Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату.
4. Виконавцем називають пристрій, здатний виконувати дії із заданого набору дій. Він складається з пристрою керування і «робочого інструмента».
5. Є такі способи описуваннявання алгоритмів: словесний, формульний, графічний, алгоритмічною мовою.
6. Алгоритм має такі властивості: визначеність, скінченність, результативність, правильність, формальність, масовість.
7. Основними мірами обчислювальної складності є часова складність та ємнісна складність.
8. Є такі класи алгоритмів: логарифмічні, лінійні, поліміальні, експоненційні. Експоненційні алгоритми часто пов’язані з перебором різних варіантів розв’язування.
9. Клас P складається із задач, для яких існують поліноміальні алгоритми рішення. Клас NP складають задачі, для яких існують поліноміальні алгоритми перевірки правильності рішення (точніше, якщо є розв’язок задачі, то існує деяка підказка, яка дозволяє за поліноміальний час отримати цю відповідь).
10. Машина Тьюринґа є однією з можливих формалізацій поняття алгоритму.
11. Означення називається рекурсивним, якщо воно задає елементи множини за допомогою інших елементів цієї ж множини. Об’єкти, задані рекурсивним означенням, також називаються рекурсивними.
12. Рекурсивною називається функція, яка може бути отримана з базових функцій за допомогою скінченної кількості застосувань підстановок, примітивних рекурсій. Базові примітивні рекурсивні функції: нуль-функція, додавання одиниці, проектуюча функція.
13. Глибина рекурсії – кількість викликів підпрограми, що реалізують рекурсію.
14. Теза Чорча: будь-який алгоритм в інтуїтивному розумінні цього слова може бути реалізований за допомогою деякої машини Тьюринґа. Іншими словами, за допомогою машини Тьюринґа можна вирішити будь-яку задачу, для якої існує алгоритм розв’язування в інтуїтивному розумінні.
Контрольні запитання
1. Яке походження терміну «алгоритм»?
2. Що ми розуміємо під поняттям «алгоритм»?
3. Що таке допустимі команди виконавця?
4. Які є способи описуваннявання алгоритмів?
5. Які властивості повинен мати алгоритм?
6. Що означає скінченність (дискретність) алгоритму?
7. Що таке формальність алгоритму?
8. Що означає масовість алгоритму?
9. Яка різниця між поліноміальними та експоненційними класами алгоритмів?
10. Дайте визначення часової складності.
11. Дайте визначення класу задач P та NP.
12. Поясніть принцип роботи машини Тьюринґа.
13. Дайте визначення рекурсивної функції.
14. Наведіть приклади частково рекурсивної функції.
15. Наведіть приклад примітивної рекурсії.
16. Дайте визначення терміну «глибина рекурсії».
17. Наведіть приклади рекурсивних функцій.
18. Сформулюйте тезу Чорча.
19. Вкажіть відмінність між інформацією та даними.
Розділ 2.
Поняття структури даних. Рівні подання структур даних
à Поняття структури даних.
à Рівні описуваннявання даних.
à Класифікація СД у програмах користувача й у пам’яті комп’ютера.
à Основні види складених типів даних.
à Структури даних у пам’яті комп’ютера.
Розділ присвячений розгляду різних типів структур даних. Описано рівні структур даних та здійснено їх класифікацію. Подано особливості відображення структур даних у пам’яті комп’ютера.
2.1. Поняття структури даних
Структура даних (СД) – загальна властивість інформаційного об’єкта, з яким взаємодіє та або інша програма. Ця загальна властивість характеризується:
ü множиною допустимих значень цієї структури;
ü набором допустимих операцій;
ü характером організованості.
Найпростіші структури даних називаються також типами даних.
У програмуванні та комп’ютерних науках структури даних — це способи організації даних у комп’ютерах. Часто разом зі структурою даних пов’язується і специфічний перелік операцій, які можуть бути виконаними над даними, організованими в таку структуру.
Правильний підбір структур даних є надзвичайно важливим для ефективного функціонування відповідних алгоритмів їх опрацювання. Добре побудовані структури даних дозволяють оптимізувати використання машинного часу та пам’яті комп’ютера для виконання найбільш критичних операцій.
Відома формула «Програма = Алгоритми + Структури даних» дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для опрацювання масиву даних визначає вибір тієї чи іншої структури даних для їх збереження, а навпаки.
2.2. Рівні описуваннявання даних
Розрізняють наступні рівні описуваннявання даних:
ü абстрактний (математичний) рівень;
ü логічний рівень;
ü фізичний рівень.
Логічний рівень (ЛСД) – подання структури даного на тій чи іншій мові програмування. Фізичний рівень (ФСД) – відображення у пам’ять комп’ютера інформаційного об’єкту відповідно до логічного описування. Оскільки пам’ять комп’ютера обмежена, то виникають питання розподілу пам’яті й керування нею.
Логічний і фізичний рівні відрізняються один від одного, тому в обчислювальних системах здійснюється відображення фізичного рівня на логічний і навпаки (рис. 2.1).
Рис. 2.1. Зв’язок між логічним та фізичним рівнями подання СД.
Будь-яка структура на абстрактному рівні може бути подана у вигляді двійки < D, R >, де D – скінчена множина елементів, які можуть бути типами даних або структурами даних, а R – множина відношень, властивості якої визначають різні типи структур даних на абстрактному рівні.
2.3. Класифікація структур даних у програмах користувача й у пам’яті комп’ютера
Структури даних поділяються на вбудовані (реалізовані в мовах програмування) та похідні (утворюються користувачами). Класифікація СД у програмах користувача та пам’яті комп’ютера подана на рис. 2.2.
Рис. 2.2. Класифікцаія СД
Важливою ознакою для класифікації є зміна структур даних під час виконання програми. Наприклад, якщо змінюється кількість елементів і/або відношення між ними, то такі структури даних називаються динамічними, інакше – статичними.
2.4. Основні види складених типів даних
Складеним типом даних назвемо тип даних, що складається із скінченної та наперед заданої множини елементів певного типу, які не обов’язково є атомарними.
Перерахуємо складені типи даних та дамо їм коротку характеристику.
Множина – скінчена сукупність елементів, в якої R =Æ.
Послідовність – абстрактна структура, у якої множина R складається з одного відношення лінійного порядку (тобто для кожного елемента, крім першого і останнього, є попередній і наступний елементи).
Матриця – структура, в якої множина R складається із двох відношень лінійного порядку.
Дерево – множина R складається з одного відношення ієрархічного порядку.
Граф – множина R складається з одного відношення бінарного порядку.
Гіперграф – множина R складається із двох і більше відношень різного порядку.
Приклади СД подано на рис. 2.3.
Рис. 2.3. Приклади подання структур даних
Прикладом гіперграфа є мережа Петрі – дводольний граф, який складається з двох типів вершин: станів, які мають певну кількість фішок, та переходів, що перерозподіляють фішки у станах залежно від кількості вхідних та вихідних дуг.
2.4. Структури даних у пам’яті комп’ютера
2.4.1. Структури даних в оперативній пам’яті
В оперативній пам’яті структури даних можна подати як на рис. 2.4.
Рис. 2.4. Подання СД в оперативній пам’яті
Слід зазначити, що оперативна пам’ять є масивом. Слово – мінімальна кількість біт, яка може опрацьовуватися одночасно.
2.4.2. СД у зовнішній пам’яті
На рис 2.5. подано структури даних у зовнішній пам’яті.
Рис. 2.5. Подання СД у зовнішній пам’яті.
СД послідовного доступу передбачає опрацювання даних у порядку їх розміщення на носії. Така СД є простою для реалізації, але унеможливлює безпосередній доступ до заданого елемента. Приклад структури даних послідовного доступу: стек, черга, дек.
На мові Сі для послідовного зчитування з файла можна скористатися таким фраґментом програми:
f=fopen(“my.txt”, “rt”); //відкрили послідовно для читання
for(i=0; i< k; i++)
{читаємо k елементів без перевірки правильності зчитування}
fscanf(f, “%d”, & x);
СД прямого доступу дозволяє опрацьовувати елементи у необхідному для користувача порядку шляхом зміщення певної кількості бітів. Переваги: швидкість, простота. Недоліки: відірваність процедур доступу від самих даних.
Прикладом прямого доступу є запис у файл fd змінної типу long, починаючи з 20-ої позиції:
#define SEEK_SET 0 // позиція на початку файла
long a=0 x1256;
fseek (fd, 20L, SEEK_SET);
fwrite (& a, sizeof(long), 1, fd);
Індексно-послідовна модель передбачає, що для кожного опрацьованого елемента даних вводиться ідентифікатор даних – ключ. Звертання до елементів даних здійснюється через значення ключа. Прикладом такого ключа є номер елемента масиву.
Резюме
1. Структура даних – загальна властивість інформаційного об’єкту, з яким взаємодіє та чи інша програма. Ця загальна властивість характеризується: множиною допустимих значень цієї структури; набором допустимих операцій; характером організованості.
2. Рівні описування даних: абстрактний, логічний, фізичний.
3. Структури даних поділяються на вбудовані (реалізовані в мовах програмування) та похідні (утворюються користувачами).
4. Складеним типом даних назвемо тип даних, що складається із скінченної та наперед заданої множини елементів певного типу, які не обов’язково є атомарними. Перерахуємо складені типи даних: множина, послідовність, матриця, дерево, граф, гіперграф.
5. В зовнішній пам’яті структури даних можна подати таким чином: фізичний блок або схема зберігання. Схема зберігання формується через структури даних прямого доступу, послідовного доступу, індексно-послідовного доступу.
Контрольні запитання
1. Поняття структури даних. Рівні подання структур даних.
2. Рівні описування даних.
3. Основні види (типи) структур даних.
4. Класифікація структур даних у програмах користувача й у пам’яті комп’ютера.
5. Приклади структур даних.
6. Структури даних в оперативній пам’яті.
7. Структури даних у зовнішній пам’яті.
8. Порівняти різні схеми зберігання даних.
9. Навести приклади прямого доступу до даних.
Розділ 3.
Структурні та лінійні типи даних
à Поняття структури даних типу «масив».
à Набір допустимих операцій для СД типу «масив».
à Дескриптор СД типу «масив».
à Ефективність масивів.
à Зберігання багатовимірних масивів.
à Структура даних типу «множина».
à СД типу «запис».
à СД типу «таблиця».
à СД типу «стек».
à СД типу «черга».
à СД типу «дек».
У розділі описано одну з найпростіших та водночас найпоширеніших структур даних – масив. Описано операції, що можуть виконуватися над масивом. Показано способи подання масивів. Також здійснено опис структури даних типу «запис» і показано, що записи найчастіше подаються за допомогою масивів. Подано характеристики динамічних структур даних типу «стек», «черга», «дек» та показано відмінності між ними. Показано відображення стека та черги на масив та на список.
3.1. Поняття структури даних типу «масив»
Масив – послідовність елементів одного типу, який називається базовим. Математичною мовою масив – це функція з обмеженою областю визначення. Структура масивів однорідна. Для виділення окремого компонента масиву використається індекс. Індекс – це значення спеціального типу, визначеного як тип індексу певного масиву. Тому на логічному рівні СД типу «масив» можна записати так:
type A = array [T 1 ] of T 2,
де Т 1 – базовий тип масиву, Т 2 – тип індексу.
Якщо DT 1 – множина значень елементів типу Т 1, DТ 2 – множина значень елементів типу Т2, то А: DT 1 ® DТ 2 (відображення).
Кардинальне число Car(T) структури типу Т – це множина значень, які може приймати задана структура типу Т. Кардинальне число характеризує об’єм пам’яті, необхідний такій структурі.
Для масиву A: Car(A) = [Car(T 2)] Car(T 1).
Масив може бути одновимірним (вектором), та багатовимірним (наприклад, двовимірною таблицею), тобто таким, де індексом є не одне число, а кортеж (сукупність) із декількох чисел, кількість яких співпадає з розмірністю масиву.
У переважній більшості мов програмування масив є стандартною вбудованою структурою даних.
Отже, з вищенаведеного сформулюємо такі властивості масиву:
ü усі елементи масиву мають той самий тип;
ü кожний компонент має свій номер у послідовності (індекс) і відрізняється ним від інших елементів (ідентифікується);
ü множина індексів (індексова множина) скінченна й зафіксована в означенні масиву і ід час виконання програми не змінюється;
ü можливість опрацювання компонента, або його доступність, не залежить від його місця в послідовності (елементи рівнодоступні).
3.2. Набір допустимих операцій для СД типу «масив»
Над масивом можна виконувати такі операції:
1) Операція доступу (доступ до елементів масиву – прямий; від розміру структури операція не залежить).
2) Операція присвоювання.
3) Операція ініціалізації (визначення початкових умов).
На фізичному рівні СД типу «масив» є неперервною ділянкою пам’яті елементів однакового об’єму. Ділянка пам’яті, необхідна для одного елемента, називається слотом.
Var B: A {визначаємо змінну В як змінну типу «масив А»};
p £ i £ g, де p – індекс першого елемента масиву, g – індекс останнього елемента масиву, i – індекс елемента.
3.3. Дескриптор СД типу «масив»
Нерідко фізичній структурі ставиться у відповідність дескриптор (заголовок), що містить загальні відомості про задану фізичну структуру. Дескриптор також зберігається, як і структура, в пам’яті. Загалом дескриптор являє собою структуру типу «запис».
Стосовно до СД типу «масив», дескриптор містить такі компоненти: ім’я масиву, умовне позначення заданої структури, адресу першого елемента масиву, індекси нижньої й верхньої границь масиву, тип елемента масиву, розмір слота.
Наприклад, для наступного описування масиву:
var A: array [-5.. 4] of Char
дескриптор буде виглядати так:
| V | A | ||
| Adr (A [-5]) | |||
  -5
| |||
| Char | |||
Для СД типу «масив» розмір дескриптора не залежить від розмірності масиву. При кожній операції доступу використовується вся інформація дескриптора. Наприклад, поля границі зміни індексу використовуються при обробці виняткових операцій.
3.4. Ефективність масивів
Масиви ефективні при звертанні до довільного елемента, яке відбувається за постійний час (
(1)), однак такі операції як додавання та видалення елемента, потребують часу (n), де n – розмір масиву. Тому масиви переважно використовуються для зберігання даних, до елементів яких відбувається довільний доступ без додавання або видалення нових елементів, тоді як для алгоритмів з інтенсивними операціями додавання та видалення, ефективнішими є зв’язані списки.
Інша перевага масивів, яка є досить важливою – це можливість компактного збереження послідовності їх елементів в локальній області пам’яті (що не завжди вдається, наприклад, для зв’язаних списків), що дозволяє ефективно виконувати операції з послідовного обходу елементів таких масивів.
Масиви є дуже економною щодо пам’яті структурою даних. Для збереження 100 цілих чисел у масиві треба рівно у 100 разів більше пам’яті, ніж для збереження одного числа (плюс, можливо, ще декілька байтів). У той же час, усі структури даних, які базуються на вказівниках, потребують додаткової пам’яті для збереження самих вказівників разом із даними. Однак, операції з фіксованими масивами ускладнюються тоді, коли виникає необхідність додавання нових елементів у вже заповнений масив. Тоді його слід розширювати, що не завжди можливо і для таких задач слід використовувати зв’язані списки, або динамічні масиви.
У випадках, коли розмір масиву є досить великий і використання звичайного звертання за індексом стає проблематичним, або великий відсоток його комірок не використовується, треба звертатися до асоціативних масивів, де проблема індексування великих об’ємів інформації вирішується оптимальніше. В асоціативному масиві замість числових індексів використовуються ключі будь-яких типів. Дані в асоціативному масиві так само можуть бути різнотипними. Така структура також відома як «хеш» або як «словник». Це лише відображення «назва-значення», як показано нижче:
h = {1 => 2, «2» => «4»}
print hash,»\n»
print hash[1],»\n»
print hash[«2»],»\n»
print hash[5],»\n»
З тої причини, що масиви мають фіксовану довжину, треба дуже обережно ставитися до процедури звертання до елементів за їхнім індексом, тому що намагання звернутися до елемента, індекс якого перевищує розмір такого масиву (наприклад, до елемента з індексом 6 у масиві з 5 елементів), може призвести до непередбачуваних наслідків.
Треба також бути уважним щодо принципів нумерації елементів масиву, яка в одних мовах програмування може починатись з 0, а в інших – з 1.
3.5. Зберігання багатовимірних масивів
Збереження одновимірного масиву в пам’яті є тривіальним, тому що сама пам’ять комп’ютера є одновимірним масивом. Для збереження багатовимірного масиву ситуація ускладнюється. Припустимо, що ми хочемо зберігати двовимірний масив такого вигляду:
Найпоширеніші способи його організації в пам’яті наведео нижче.
Розташування «рядок за рядком». Це найбільш уживаний на сьогодні спосіб, який зустрічається у більшості мов програмування:
1 2 3 4 5 6 7 8 9
Розташування «стовпчик за стовпчиком». Такий метод розташування масивів використовується, зокрема, в мові програмування Fortran:
1 4 7 2 5 8 3 6 9
Масив із масивів. Багатовимірні масиви репрезентуються одновимірними масивами вказівників на одновимірні масиви. Розташування може бути як «рядок за рядком», так і «стовпчик за стовпчиком».
Перші два способи дозволяють розміщувати дані компактніше (мають більшу локальність), однак це одночасно і обмеження: такі масиви мають бути «прямокутними», тобто кожний рядок має містити однакову кількість елементів. Розташування «масив із масивів», з іншого боку, не дуже ефективне щодо використання пам’яті (необхідно зберігати додатково інформацію про вказівники), але знімає обмеження на «прямокутність» масиву.
Особливим видом масивів є розріджений масив (матриця), в якому дані подані не незперервно, а фраґментарно. Алгоритми опрацювання розріджених матриць передбачають дії тільки з ненульовими елементами і, отже, кількість операцій буде пропорційна кількості ненульових елементів.
Існують різні методи зберігання елементів матриці в пам’яті, наприклад, лінійний зв’язний список. Можна зберігати матрицю, використовуючи кільцевий зв’язний список, двонапрямлені стеки і черги (детальніше розглянуто далі). Існує діагональна схема зберігання симетричних матриць, а також зв’язні схеми розрідженого зберігання. Зв’язна схема зберігання матриць, запропонована Кнутом [7, 8], пропонує зберігати в масиві (наприклад, в AN) в довільному порядку самі елементи, індекси рядків і стовпців відповідних елементів (наприклад, в масивах I і J), номер (з масиву AN) наступного ненульового елемента, розташованого в матриці у рядку (NR) і у стовпці (NC), а також номера елементів, з яких починається рядок (вказівники для входу в терміні – JR) і номери елементів, з яких починається стовпець (вказівники для входу в стовпець – JC). Така схема зберігання надлишкова, але дозволяє легко здійснювати будь-які операції з елементами матриці.
Найширше вживана схема зберігання розріджених матриць – це схема, запропонована Чангом і Густавсоном: «розріджений рядковий формат» [22]. Ця схема висуває мінімальні вимоги до пам’яті і дуже зручна при виконанні операцій додавння, множення матриць, транспонування, розв’яузування систем лінійних рівнянь, при зберіганні коефіцієнтів у розріджених матрицях і т.ін. У цьому випадку значення ненульових елементів зберігаються в масиві AN, відповідні їм індекси стовпців – у масиві JA. Крім того, використовується масив вказівників, наприклад IA, що відзначають позиції AN і JA, з яких починається опис чергової стрічки. Додатковий компонент в IA містить вказівник першої вільної позиції в JA і AN.
На практиці для роботи з розрідженим масивом розробляються функції:
а) для перетворення індексів масиву в індекс вектора;
б) для визначення значення елементу масиву з його запакованого подання за двома індексами (рядок, стовпчик);
в) для запису значення елементу масиву в його запакованому поданні за двома індексами.
При такому підході звернення до елементів початкового масиву виконується за допомогою вказаних функцій. Наприклад, нехай є двовимірна розріджена матриця, у якій усі ненульові елементи розташовані у шаховому порядку, починаючи з другого елемента. Для такої матриці формула обчислення індексу елементу в лінійному поданні буде такою:
L =((y -1)* XM + x) /2),
де L – індекс у лінійному поданні; x, y – відповідно рядок та стовпчик у двовимірному поданні; XM – кількість елементів у рядку початкової матриці.
Програмна реалізація цього методу така (значення XM відоме):
Function PutTab(у, x, value: integer): boolean;
Function GetTab(x, y: integer): integer;
Var arrp: array[1..XM*XM div 2] of integer;
Function NewIndex(y, x: integer): integer;
var i: integer;
begin NewIndex: =((y-1)*XM+x) div 2); end;
Function PutTab(у, x, value: integer): boolean;
begin
if NOT ((x mod 2< > 0) and (y mod 2< > 0)) or
NOT ((x mod 2=0) and (y mod 2=0)) then begin
arrp[NewIndex(у, x)]: =value; PutTab: =true; end
else PutTab: =false;
end;
Function GetTab(x, y: integer): integer;
begin
if ((x mod 2< > 0) and (y mod 2< > 0)) or
((x mod 2=0) and (y mod 2=0)) then GetTab: =0
else GetTab: =arrp[NewIndex(у, x)];
end;
end.
Стисле подання матриці зберігається у векторі arrp.
Функція NewIndex виконує перерахунок індексів за наведеною вище формулою і повертає індекс елемента у векторі arrp.
Функція PutTab виконує зберігання у стислому поданні одного елемента з індексами x, у і значенням value. Зберігання виконується тільки у тому випадку, якщо індекси x, у адресують не нульовий елемент. Якщо зберігання виконане, функція повертає true, інакше – false.
Для доступу до елемента за індексами двовимірної матриці використовується функція GetTab, яка за індексах x, у повертає вибране значення. Якщо індекси адресують нульовий елемент матриці, функція повертає 0.
Розглянемо дещо інший спосіб ефективного зберігання розрідженої матриці: для матриці створюється дескриптор – масив desc, який заповнюється при ініціалізації матриці таким чином, що i -ий елемент масиву desc містить індекс першого елементу i -ого рядка матриці у її лінійному поданні. Такий метод спрощує доступ до кожного елемента матриці (функція NewIndex): за номером рядка з дескриптора відразу вибирається індекс початку рядка і до нього додається зсув елемента зі стовпчика x. Процедури PutTab і GetTab – такі ж, як і в попередній реалізації, тому тут не наводяться.
Function PutTab(у, x, value: integer): boolean;
Function GetTab(x, y: integer): integer;
Procedure InitTab;
Var arrp: array[1..XM*XM div 2] of integer;
desc: array[1..XM] of integer;
Procedure InitTab;
var i: integer;
begin
desc[1]: =0; for i: =1 to XM do desc[i]: =desc[i-1]+XM;
end;
Function NewIndex(у, x: integer): integer;
var i: integer;
begin NewIndex: =desc[y]+x div 2; end;
end.
3.6. СД типу «множина»
Множина – скінчений набір елементів одного типу, для яких не важливий порядок слідування і жоден з елементів не може бути два рази включений. Така СД визначається конструкцією type T = set of T 0, де T 0 – вбудований або раніше визначений тип даних (базовий тип). Значеннями змінних типу T є множини елементів типу T 0 (зокрема, порожні множини).
Кардинальне число множини (потужність) рівне кількості її елементів.
Набір допустимих операцій для СД типу «множина»: «*» – перетин множин, «+» – об’єднання множин, «-«– різниця множин, «in» – перевірка належності до множини елемента базового типу.
Дескриптор СД типу «множина» не відрізняється від дескриптора СД типу «масив».
Подамо програму, яка виводить усі цифри, що не входять у десятковий запис числа. Для цього скористаємося множиною s, що міститиме усі цифри.
Var s: set of 0..9;
n, ost, i: integer; {n – число, яке треба проаналізувати}
begin write(‘Input number’);
readln(n);
s: =[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; {включили у множину всі цифри}
while n> 0 do
{виділяємо цифри числа методом ділення його на 10}
begin
{визначаємо остачу від ділення}
ost: =n mod 10;
n: =n div 10;
if (ost in s) then s: =s-[ost] {здійснюємо операцію різниці}
end;
{виведемо всі цифри, що не належать до запису числа, за зростанням}
for i: =0 to 9 do
if i in s then write(i, ’, ’)
end.
Найчастіше множини використовуються для формування набору елементів, що зустрічаються у масивах лише один раз.
3.7. СД типу «запис (прямий декартовий добуток)»
Запис – послідовність елементів, які, в загальному випадку, можуть бути одного типу. На логічному рівні СД типу «запис» можна записати так:
type Т = Record
S1: T1;
S2: T2;
………...
Sn: Tn;
End;
Тут: Ti змінюється при i = 1, 2, …, n; S 1, …, Sn – ідентифікатори полів;
Т 1, …, Tn – типи даних. Якщо Ti також є у свою чергу записом, то Si – ієрархічний запис.
Якщо DT 1 – множина значень елементів типу Т 1, DТ 2 – множина значень елементів типу Т 2, …, DТn – множина значень елементів типу Т n, те DT – множина значень елементів типу Т буде визначатися за допомогою прямого декартового добутку: DT = DT 1 ´ DT 2 ´ … ´ DТn. Іншими словами, множина допустимих значень СД типу «запис»: 
.
Допустимі операції для СД типу «запис» аналогічні до операцій для СД типу «масив».
Дескриптор СД типу «запис» містить у собі: умовне позначення, назва структури, кількість полів, вказівник на перший елемент (у випадку прямокутної СД), характеристики кожного елемента, умовні позначення типу кожного елемента, розмір слота, а також зсув, необхідний для обчислення адреси.
Загалом, зсув – це адреса компоненту (поля) ri щодо початкової адреси запису r. Зсув обчислюється так: ki = S 1 + S 2 + … + Si- 1, i= 1, 2, …, n, де Si – розмір слота кожного елемента запису.
Дескриптор СД типу «запис», на відміну від дескриптора СД типу «масив», залежить від кількості елементів запису.
Приклад структури на мові Сі:
typedef struct { char name[20];
char city[30];
char dcount[10];
} school;
Тут оголошена структура (запис), що складається із 3 стрічкових компонентів різної довжини і визначено назву цієї структури – school.
Покажемо, яким чином можна поєднати особливості СД типу «множина» та СД типу «запис». Нехай виникла задача формування списку міст, у яких розміщені задані школи. Оскільки у кожному місті є, як мінімум, одна школа, то назви міст у записах можуть повторюватись. Для цього сформуємо множину міст. Оскільки мова С не підтримує СД «множина», то сформуємо множину за допомогою масиву.
#include< stdio.h>
#include< string.h>
struct school
{
char name[20];
char city[20];
char dcount[10];
} a[10];
void main()
{
// множина міст
char set[10][20];
//на початку роботи програми множина порожня
int k=0, i, j;
for(i=0; i< 10; i++)
scanf(" %s%s%s", & a[i].name, & a[i].city, & a[i].dcount);
strcpy(set[0], a[0].adress);
for(i=1; i< 10; i++)
{
int l=0;
for(j=0; j< =k; j++)
//перевірка, чи є елемент у множині
if(strcmp(a[i].city, set[j])==0) l++;
//якщо немає, то включаємо
if(! l) strcpy(set[++k], a[i].city);
}
for(j=0; j< =k; j++)
printf(" %s\n", set[j]);
}
3.8. СД типу «таблиця»
Таблиця – послідовність записів, які мають ту саму організацію. Такий окремий запис називається елементом таблиці. Найчастіше використовується простий запис. Отже, таблиця – це аґреґація елементів. Якщо послідовність записів впорядкована щодо певної ознаки, то така таблиця називається впорядкованою, інакше – таблиця невпорядкована.
Класифікацію СД типу таблиця подано на рис. 3.1.
Рис. 3.1. Класифікція СД типу «таблиця».
Якщо один елемент di, то кортеж – це < d 1, d 2, …, dn >, причому DTi Î di. Множина значень елементів типу Т (множина допустимих значень СД типу «таблиця») буде визначатися за допомогою прямого декартового добутку:
DT = DT 1 ´ DT 2 ´ … ´ DТn, причому DTi Î < d 1, d 2, …, dn > …
Сам елемент таблиці можна подати у вигляді двійки < K, V >, де К – ключ, а V – тіло елемента. Ключем може бути різна кількість полів, які визначають цей елемент. Ключ використовується для операції доступу до елемента, тому що кожний із ключів унікальний для заданого елемента. Отже, таблиця є сукупністю двійок < K, V >.
На логічному рівні елемент СД типу «таблиця» описуванняється так (приклад на мові Паскаль):
Type Element = record
Key: integer;
{опис інших полів}
end;
При реалізації таблиці як відображення на масив її опис виглядає так:
Tabl = array [0.. N] of Element.
Під час виконання програми кількість елементів може змінюватися. Структура, у якій змінюється кількість елементів під час виконання програми, називається динамічною. Якщо розглядати динамічну структуру як відображення на масив, то така структура називається напівстатичною.
Перед тим як визначити операції, які можна виконувати над таблицею, розглянемо класифікацію операцій.
Конструктори – операції, які створюють об’єкти розглянутої структури.
Деструктори – операції, які руйнують об’єкти розглянутої структури. Ознакою цієї операції є звільнення пам’яті.
Модифікатори – операції, які модифікують відповідні структури об’єктів. До них належать динамічні й напівстатичні модифікатори.
Спостерігачі – операції, у яких елементом (вхідним параметром) є об’єкти відповідної структури, а повертають ці операції результати іншого типу. Отже, операції-спостерігачі не змінюють структуру, а лише подають інформацію про неї.
Ітератори – оператори доступу до вмісту частини об’єкта у певному порядку.
Набір допустимих операцій для СД типу «таблиця» подаємо нижче
ü Операція ініціалізації (конструктор).
ü Операція включення елемента в таблицю (модифікатор).
ü Операція виключення елемента з таблиці (модифікатор).
ü Операції-предикати:
· таблиця порожня / таблиця не порожня (спостерігач),
· таблиця переповнена / таблиця не переповнена (спостерігач).
· Читання елемента за ключем (спостерігач).
3.9. СД типу «стек»
Стек – це послідовність, у якій включення й виключення елемента здійснюється з однієї сторони послідовності (вершини стека). Так само здійснюється й операція доступу. Структура функціонує за принципом LIFO (останній, що прийшов, обслуговується першим). Умовні позначення стека зображені на рис 3.2.
а) відображеня на масив б) відображення на список
Рис. 3.2. Організація стека.
При реалізації стека розглядаються стек як відображення на масив і стек як відображення на список.
Відображення на масив передбачає оголошення звичайного масиву та змінної, значення якої дорівнюватиме значенню індексу елемента, що відіграватиме роль «голови» (елемента, на який вказуватиме вказівник):
int a[100]; // оголошення стеку
int n=0; // дійсна кількість елементів у стека
int current=99; // індекс «голови», діє принцип LIFO
void pop () // функція видобування (вилучення) елемента зі стека
{
if (n! =0)
{ current++; // зсунули «голову» на один елемент вперед
printf(“%d%, a[current]);
n--; } // зменшили кількість елементів
}
void push () // функція додавання елемента до стеку
{
if (n< 99)
{ current--;
//додали «голову», зсунувши індекс на один елемент вперед
scanf(“%d%, & a[current]);
n++; } // збільшили кількість елементів
}
Відображення на список передбачає оголошення динамічної структури. Перевагою такого відображення є відсутність обмежень на максимальну кількість елементів у стеку, але, водночас, передбачає підтримку складнішої вказівникової структури:
struct stack {
int el; // значення елемента
struct stack *next; } st // адреса наступного елемента
st *head, *p1, *p2; //вказівник на «голову», допоміжні вказівники
st* push(int a; st *cur)
// функція додавання елемента,
// а – значення, яке треба внести у стек
// cur – вершина («голова») стека
{ st *p;
// якщо стек порожній
if(! cur)
{
// створюємо вершину
cur=(st*)malloc(sizeof(st));
cur-> el=a;
cur-> next=NULL;
return(cur);
}
else
{
// створюємо новий елемент, який стане вершиною стека
p=(st*)malloc(sizeof(st));
p-> el=a;
p-> next=cur;
return(p);
}
}
st* pop() // видалення вершини стека
{ st *p;
if(head) // якщо в стеку є елементи
{.// вершиною стає наступний елемент
p=head-> next;
// знищуємо «голову»
free(head);
return(p);
}
else return (NULL);
}
Сукупність операцій, що визначають структуру типу «стек», подана нижче.
ü Операція ініціалізації.
ü Операція включення елемента в стек.
ü Операція виключення елемента зі стека.
ü Операція перевірки: стек порожній / стек не порожній.
ü Операція перевірки: стек переповнений / стек не переповнений (ця операція характерна для стека як відображення на масив).
ü Операція читання елемента (доступ до елемента).
Є дві модифікації стека:
ü вказівник перебуває на вершині стека, показуючи на перший порожній елемент;
ü 
|
вказівник вказує на перший заповнений елемент.
3.9.1. Дескриптор СД типу «стек»
Дескриптор СД типу «стек» містить:
ü адреси початку та кінця стека,
ü адресу вказівника,
ü опис елементів
|
3.9.2. Області застосування СД типу «стек»
Стек використовується при перетворенні рекурсивних алгоритмів у нерекурсивні. Зокрема, за допомогою стека можна модифікувати алгоритм сортування Хоора (описаний у наступних розділах) [4, 7, 8].
Стек використовується при розробленні компіляторів.
Cтеки вплинули й на архітектуру комп’ютера, послужили основою для стекових машин. У такого комп’ютера акумулятор виконаний у вигляді стека, що дозволяє розширити спектр безадресних команд, тобто команд, що не вимагають явного задання адрес операндів. Наслідком використання стека є збільшення швидкості опрацювання.
3.10. СД типу «черга»
Черга – послідовність, у яку включають елементи з одного боку, а виключають – з іншого. Структура функціонує за принципом FIFO (надійшовший першим, обслуговується першим). Умовне позначення черги подане на рис 3.3.
Рис. 3.3. СД типу «черга».
При реалізації черги розглядаються черга як відображення на масив (напівстатична реалізація) і черга як відображення на список.
Відображення на масив:
int a[100]; // оголошення черги
int n=0; // індекс останнього елемента у черзі
int current=0; // індекс «голови», діє принцип FIFO
void pop () // функція видобування (вилучення) елемента з черги
{
if (n! =0)
{ current++; // зсунули «голову» на один елемент вперед
printf(“%d%, a[current]);
}
}
void push () // функція додавання елемента до черги
{
if (! current) // черга порожня
{ scanf(“%d%, & a[current]); }
else
if (n< 99)
{ // збільшили кількість елементів
n++; // додали елемент у кінець черги
scanf(“%d%, & a[n]);
}
}
Відображення на список:
struct cherga {
int el; // значення елемента
struct charga *next; } ch // адреса наступного елемента
ch *head, *p1, *p2; //вказівник на «голову», допоміжні вказівники
ch* push(int a; ch *cur)
// функція додавання елемента,
// а – значення, яке треба внести у чергу
// cur – останній елемент черги
{ ch *p;
// якщо черга порожня
if(! cur)
{ // створюємо вершину
cur=(ch*)malloc(sizeof(ch));
cur-> el=a;
cur-> next=NULL;
return(cur);
}
else
{ // створюємо новий елемент та додаємо його у кінець
p=(ch*)malloc(sizeof(ch));
p-> el=a;
сur-> next=p;
return(p);
}
}
ch* pop() // видалення вершини черги
{ ch *p;
if(head) // якщо в черзі є елементи
{.// вершиною стає наступний елемент
p=head-> next;
// знищуємо «голову»
free(head);
return(p);
}
else return (NULL);
}
Сукупність операцій, що визначають структуру типу «черга» подана нижче.
ü Операція ініціалізації.
ü Операція включення елемента в чергу.
ü Операція виключення елемента із черги.
ü Операція перевірки: черга порожня / черга не порожня.
ü Операція перевірки: черга переповнена / черга не переповнена.
У послідовній пам’яті черга має такий вигляд, як на рис. 3.4.
Тут: Uk 1 – вказівник на «голову» (початок) черги, Uk 2 – вказівник на «хвіст» (кінець) черги.
Щоб уникнути переповнення, раціонально використати кільцеву чергу. При цьому Uk 1 > Uk 2 або Uk 2 > Uk 1. У випадку ж якщо черга не кільцева, то завжди Uk 2 > Uk 1. Якщо черга порожня або переповнена, то Uk 1 = Uk 2.
Рис. 3.4. Структура даних типу «черга» у послідовній пам’яті.
Нехай n – поточний стан черги, а N – кількість елементів у черзі, тоді маємо умову 0 £ n £ N, і значення n може бути умовою перевірки стану черги. Операція включення можлива, якщо n < N, а операція виключення – якщо
n > 0. У випадку кільцевої черги при операції модуля вказівники будуть змінюватися так: Uk 1= Uk 1 mod N + 1, Uk 2 = Uk 2 mod N + 1.
Схема на фізичному рівні СД типу «черга» виглядає так:
Дескриптор:
Області застосування СД типу «черга»
Черга використається при передаванні даних з оперативної у вторинну пам’ять (при цьому відбувається процедура буферизації: накопичується блок і передається у вторинну пам’ять). Наявність буфера забезпечує незалежність взаємодії процесів між виробником і споживачем (рангування задач користувача). Задачі розділяються за пріоритетами:
ü задачі, розв’язувані в режимі реального часу (вищий пріоритет) (черга 1);
ü задачі, розв’язувані в режимі розділення часу (черга 2);
ü задачі, розв’язувані в пакетному режимі (фонові задачі) (черга 3).
Доступ до елементів черги здійснюється послідовно.
3.11. СД типу «дек»
Дек – особливий вид черги. Дек (з англ. deq – double ended queue, черга з двома кінцями) – це такий послідовний список, у якому як включення, так і виключення елементів може здійснюватися з обох кінців списку. Окремий випадок дека – дек з обмеженим входом і дек з обмеженим виходом. Логічна і фізична структури дека аналогічні логічній і фізичній структурі кільцевої FIFO-чперги. Проте, стосовно дека доцільно говорити не про початок і кінець, а про лівий і правий кінець.
Набір допустимих операцій для СД типу «дек»:
ü ініціалізація;
ü включення елемента справа;
ü включення елемента зліва;
ü виключення елемента справа;
ü виключення елемента зліва;
ü визначення розміру;
ü очищення.
Така структура даних є однією з найлегших для опрацювання серед зв’язних списків та поєднує позитивні сторонни реалізації списку у вигляді стеку та черги.
Задачіадачі, що вимагають структури дека, зустрічаються в обчислювальній техніці і програмуванні набагато рідше, ніж задачіадачі, що реалізовуються на структурі стека або черги. Як правило, вся організація дека виконується програмістом без якихось спеціальних засобів системної підтримки.
Прикладом дека може бути, наприклад, якийсь термінал, у який вводяться команди, кожна з яких виконується заданий час. Якщо ввести наступну команду і не дочекатися закінчення виконання попередньої, то вона встане у чергу і почне виконуватися, як тільки звільниться термінал. Це FIFO-черга. Якщо ж додатково ввести операцію відміни останньої введеної команди, то виходить дек.
#include " stdio.h"
#include " conio.h"
struct node
{
int data; // описуємо структуру
struct node *next;
struct node *prev;
};
node *first(int data); // визначаємо перший елемент
node *add(node *p, int data); // додаємо елемент на початок
node *addAfter(node *head, int data); //додаємо елемент у кінець
node *del(node *del, int st); //знищуємо елемент
void view(node *head); //відображення дека
void delDek(node *head); //знищуємо дек
// головна програма
main()
{
node *head, *p;
head=NULL;
int m_gl, m_dob, m_ud, m_vi;
int data;
while(m_gl! =4)
{
clrscr();
printf(" 1. Додати елеметн.\n");
printf(" 2. Знищити елемент.\n");
printf(" 3. Вивести дек.\n");
printf(" 4. Вихід.\n");
gotoxy(1, 6);
scanf(" %i", & m_gl);
if(m_gl==1)
{
while(1)
{
clrscr();
if (head==NULL)
{
printf(" Дек порожній. Введіть елемент: ");
scanf(" %i", & data);
head = p = first(data);
}
clrscr();
printf(".....Додати елемент....\n");
printf(" 1. На початок.\n ");
printf(" 2. У кінець.\n");
printf(" 3. Повернутись назад.\n");
gotoxy(1, 6);
scanf(" %i", & m_dob);
if (m_dob==1)
{
clrscr();
printf(" Додати елемент на початок.\n");
scanf(" %i", & data);
head=addAfter(head, data);
}
if (m_dob==2)
{
clrscr();
printf(" Додати елемент у кінець.\n");
scanf(" %i", & data);
p=add(p, data);
}
if (m_dob==3) break;
}
}
if(m_gl==2)
{
while(1)
{ // виводимо меню програми
clrscr();
printf(" Знищити елемент....\n");
printf(" 1. На початку.\n");
printf(" 2. У кінці.\n");
printf(" 3. Очистити дек.\n");
printf(" 4. Повернутись назад.\n");
gotoxy(1, 6);
scanf(" %i", & m_ud);
if (m_ud == 2) p = del(p, m_ud);
else if (m_ud==1) head=del(head, m_ud);
else if (m_ud==3)
{delDek(head); head=NULL; printf(" Дек очистили! "); }
if (m_ud==4) break;
}
}
if (m_gl==3)
{
while(1)
{
clrscr();
if (head! =NULL) view(head);
else printf(" Дек порожній.\n");
printf(" 1. Повернутись назад.\n");
scanf(" %i", & m_vi);
if (m_vi==1) break;
}
}
}
}
node *first(int data)
{ //створюємо перший елемент
node *temp = new node;
temp-> data=data;
temp-> next=NULL;
temp-> prev=NULL;
return temp;
}
node *add(node *p, int data)
{ // елемент зі значенням data розміщуємо після р
node *temp=new node;
temp-> data=data;
temp-> prev=p;
temp-> next=NULL;
p-> next=temp;
return temp;
}
node *addAfter(node *head, int data)
{ // елемент зі значенням data розміщуємо перед головою
node *temp = new node;
temp-> data=data;
temp-> next=head;
head-> prev=temp;
temp-> prev=NULL;
return temp;
}
void view(node *head)
{ // виводимо на екран значення елементів дека
node *t=head;
printf(".........DEK.........\n");
while(t)
{
printf(" %i\t",
|
|