ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 397
Скачиваний: 2
Базові структури даних
Поняття структури даних можна визначити як особливу систему організації взаємозв’язаних елементів даних. Структура самих елементів залежить від конкретної задачі. Вони можуть бути як дуже простими (наприклад, цілі числа або строки символів) так і дуже складними (наприклад, для зображення матриці часто використовують одномірний масив, кожний елемент якого в свою чергу також є одномірним масивом). Розглянемо деякі структури даних, що найчастіше зустрічаються.
Лінійні структури даних
Серед простих структур даних можна виділити два найважливіших – одномірний масив і зв’язаний список.
Одномірний масив – це послідовність із n однотипних елементів, що розташовані підрід в оперативній пам’яті комп’ютера, доступ до яких виконується по значенню індексу масиву:
|
Елемент [0] |
Елемент [0] |
… |
Елемент [n-1] |
В більшості випадків індекс масиву, що складається із n елементів, є цілим числом, що має значення від 0 до n-1 або від 1 до n В деяких мовах програмування допускається, щоб індекс набував любих цілочисельних значень, включаючи від’ємні. Головне, щоб він не виходив за межі раніше встановленого діапазону, що встановлює верхню і нижню межу зміни індексу.
Іноді в мовах програмування для доступу до елементів масиву можуть використовуватись нечислові індекси. Такі масиви називаються асоціативними. Наприклад, можна створити масив із 12 елементів, що відповідає місяцям року, доступ до яких здійснюється по назві місяців.
Час звернення до любого елементу масиву однаковий і не залежить від його положення в масиві. Ця особливість відрізняє масиви від зв’язаних списків, мова про які піде пізніше. Проте кожен елемент масиву займає однакову кількість чарунок пам’яті в комп’ютері.
На основі одномірних масивів створюються різні структури даних, серед яких особливу увагу заслуговують рядки.
Рядки – послідовність символів раніше обумовленого алфавіту, що закінчується особливим символом, що служить ознакою кінця рядка. Рядки, елементами яких є лише 0 та 1, називаються двійковими (бінарними) або бітовими.
Рядки є основним елементом, що використовується при обробці текстових даних, визначення синтаксису мови програмування, компілювання створених на ній програм, а також при вивченні абстрактних обчислювальних моделей.
Операції, що виконуються над масивами, залежать від його типу – операції, що виконуються над рядками, відрізняються від операцій, що виконуються над масивом чисел (визначення довжини рядків, об’єднання двох рядків для створення однієї, порівняння двох рядків).
Зв’язаний список – послідовність (в т.ч. і порожня) кількох елементів даних, що називаються вузлами. В кожному вузлі зберігається інформація двох видів: самі дані та одна або більше посилань на інші вузли списку, що називаються вказівниками. Якщо поточний елемент є останнім, то в нього поміщується нульовий вказівник зі спеціальним значенням NULL – це вказує на те, що вказівник ні на що не вказує.
В однонапрямленому зв’язаному спискові кожний вузол вміщує лише один вказівник, в якому міститься посилання на наступний елемент списку, або NULL, якщо поточний елемент є останнім.
|
Елемент [0] |
|
|
Елемент [1] |
|
|
Елемент [n-1] |
Null |
Для досягнення заданого елемента зв’язаного списку необхідно обрати перший вузол списку, потім пересуватися по ланцюгу елементів до необхідного вузла. Тому час доступу до конкретного елемента списку залежить від місця його положення в списку і може дуже суттєво відрізнятися від того, що затрачується в масиві для подібної операції. Це є недоліком зв’язаного списку. Перевага зв’язаного списку полягає в тому, що для списку немає необхідності резервувати оперативну пам’ять комп’ютера. Крім того, вставка та видалення елементів списку не завдають труднощів і виконуються достатньо швидко шляхом зміни вказівників.
Існує модифікація структури однонапрямленого зв’язаного списку - двонапрямлений зв’язаний список. Відміна між ними в тому, що кожен вузол двонапрямленого списку крім першого та останнього включають в себе вказівники на попередній та наступний вузли:
|
Null |
Елемент [0] |
|
|
|
Елемент [0] |
|
… |
|
Елемент [n-1] |
Null |
Масив та зв'язаний список частіше всього використовують для зображення ще однієї абстрактної структури даних – лінійний список або просто список. Список являє собою скінчену послідовність елементів даних, що організовані в заданому лінійному порядку. До цієї структури даних можуть бути застосовані наступні операції: пошук, видалення та додавання елемента.
Серед всієї множини можна виділити два типи списків: стеки та черги.
Стек – це такий список, в якому можна виділити тільки останній елемент, а новий елемент можна додати тільки в кінець. Цей кінець називають вершиною стеку, оскільки стеки зазвичай зображують на малюнках у вигляді вертикального прямокутника. Принцип роботи стека – LIFO (last-in-first-out), оскільки першим видаляється елемент, котрий був останнім у стеці. Цей стек нагадує купку тарілок, оскільки ми можемо взяти з неї тільки верхню тарілку, а нову покласти на верх купки. Стеки широко використовуються на практиці – без них не обійтися при реалізації рекурсивних алгоритмів.
Черга – це такий список, елементи якого видаляються з однієї сторони структури (вона називається головою), а додаються з іншої (вона називається хвостом). Перша операція називається видаленням елемента з черги, а друга – постановкою в чергу. Принцип роботи черги – FIFO (first-in-first-out). Аналогія – черга в магазині. Область використання – алгоритми розв’язку задач теорії графів.
В багатьох випадках необхідно вибрати серед множини елементів, що динамічно змінюється, елемент з найвищим пріоритетом. Для розв’язку таких задач використовують структуру даних, що називається чергою з пріоритетами або просто пріоритетною чергою. До основних операцій над чергою з пріоритетами відносяться: пошук найбільшого елемента, видобування найбільшого елемента та додавання нового елемента. Дві останні операції повинні бути реалізовані так, щоб в результаті їх виконання утворилась нова черга с пріоритетами або перевпорядкована стара. Найпростіше реалізувати таку структуру на основі масиву або впорядкованого масиву, хоча так не досягається максимальна ефективність. Кращою є реалізація на основі структури даних, що називається пірамідою.
Динамічним називають такий масив, розмір якого можна змінювати під час виконання програми. Динамічні масиви надають змогу більш гнучко працювати з даними, оскільки дозволяють вводити довільний розмір. Для зміни розміру динамічного масиву мова програмування, що підтримує такі масиви, повинна надавати вбудовану функцію чи оператор. В порівняні зі статичним масивом, динамічний не має фіксованого розміру та може задаватись під час виконання програми. Замість використання змінної типу string можна використовувати масив змінних типу char. У задачах пов'язаних з матрицями, матриці записують, як двовимірний масив. В старих комп'ютерах з малою кількістю оперативної пам'яті, а також при операціях з великою кількістю даних існує загроза повного засмічення пам'яті, тому в кінці програми прийнято видаляти масив.
Зв'язаний список в програмуванні — одна з найважливіших структур даних, в якій елементи лінійно впорядковані, але порядок визначається не номерами елементів, а вказівниками, які входять в склад елементів списку та вказують на наступний за даним елемент (в однозв'язаних або однобічно зв'язаних списках) або на наступний та попередній елементи (в двозв'язаних або двобічно зв'язаних списках). Список має «голову» — перший елемент та «хвіст» — останній елемент.
Зв'язані списки мають серію переваг порівняно з масивами. Зокрема, в них набагато ефективніше (за час О(1), тобто незалежно від кількості елементів) виконуються процедури додавання та вилучення елементів. Натомість, масиви набагато кращі в операціях, які потребують безпосереднього доступу до кожного елементу, що у випадку зі зв'язаними списками неможливо та потребує послідовного перебору усіх елементів, які передують даному.
Однобічно
зв'язаний список з трьох елементів
В однобічно зв'язаному списку, який є найпростішим різновидом зв'язаних списків, кожний елемент складається з двох полів: data або даних, та вказівника next на наступний елемент. Якщо вказівник не вказує на інший елемент (інакше: next = NULL), то вважається, що даний елемент — останній в списку.
Двобічно зв'язаний список
В двобічно зв'язаному списку елемент складається з трьох полів — вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент. Якщо prev=NULL, то в елемента немає попередника (тобто він є «головою» списку), якщо next=NULL, то в нього немає наступника («хвіст» списка)
В кільцевому списку перший та останній елемент зв'язані. Тобто, поле prev голови списка вказує на хвіст списка, а поле next хвоста списка вказує на голову списка.
Зв'язані списки та масиви
Списки мають деякі переваги над масивами. Вони досить ефективні щодо операцій додавання або видалення елементу в довільному місці списка, виконуючи їх за постійний час, тоді як масиви для цього потребують часу O(n), тобто час зростає з ростом кількості елементів масиву.
В списках також не існує проблеми «розширення», яка рано чи пізно виникає в масивах фіксованого розміру, коли виникає необхідність включити в нього додаткові елементи. Точно так, фіксований масив, з якого було видалено багато елементів (або вони просто не використовуються) є дуже неефективним з точки зору використання пам'яті. Функціонування списків можливо в ситуації, коли пам'ять комп'ютера фрагментована, тоді як масиви переважно потребують неперервної області для зберігання.
З іншого боку, масиви дозволяють безпосередній доступ до будь-якого елементу. Однобічно зв'язані списки, натомість, потребують проходження усіх попередніх елементів. Це призводить до складнощів застосування списків в задачах, де необхідно швидко знаходити елемент за його індексом, наприклад в алгоритмах сортування. Кешування списків в таких випадках майже не дає ефекту.
Іншим очевидним недоліком списків є необхідність разом з корисною інформацією додаткового збереження інформації про вказівники, що позначається на ефективності використання пам'яті цими структурами.
Двобічне зв'язування потребує більше пам'яті на елемент та більших обчислювальних затрат на виконання елементарних операцій. Але такими списками легше маніпулювати, тому що вони дозволяють проходження по списку в обох напрямах, що є необхідною умовою функціонування деяких алгоритмів.
Стек (стос, стіс) в інформатиці та програмуванні — різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) «останній прийшов — перший пішов» (LIFO, англ. last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім.
Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку — «магазин», за аналогією з принципом роботи магазину в автоматичній зброї).
Зміст
Операції зі стеком
-
push («заштовхнути елемент»): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow).
-
pop («виштовхнути елемент»): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні «виштовхнути» елемент з вже пустого стеку, відбувається ситуація «незаповнення» стеку (англ. stack underflow).
Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.
Додаткові операції (присутні не у всіх реалізаціях стеку):
-
isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній.
-
isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе.
-
clear: звільнити стек (видалити усі елементи).
-
top: отримати верхній елемент (без виштовхування).
-
size: отримати розмір (кількість елементів) стека.
-
swap: поміняти два верхніх елементи місцями.
Організація в пам'яті комп'ютера
Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку.
Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.
Приклади застосування
Калькулятори, які використовують зворотну польську нотацію, використовують стек для збереження даних обчислень.
Існують «стеко-орієнтовані» мови програмування (Forth, PostScript), які використовують стек як базову структуру даних при виконанні багатьох операцій (арифметичних, логічних, вводу-виводу тощо).
Стеко-орієнтованими є деякі з віртуальних машин, наприклад віртуальна машина Java.
Компілятори мов програмування використовують стек для передавання параметрів в процесі виклику підпрограм, процедур та функцій. Спеціалізований стек використовується також для збереження адрес повернення з підпрограм.
Реалізація базових алгоритмів
На мовах програмування високого рівня, стек може бути реалізований за допомогою масиву та додаткової змінної: Для зберігання елементів стеку резервується масив S[1..n] певного розміру та додаткова змінна top[S], яка буде зберігати індекс верхівки стеку.
Операції push та pop тоді можуть бути записані так (без перевірки на переповнення та «незаповнення»):
PUSH (S,
x)
1
top[S] := top[S] + 1 // збільшення індексу на
1
2
S[top[S]] := x // запис нового елемента у
верхівку стека
POP (S)
1
top[S] := top[S] - 1 // зменшення
індексу
на
1
2 return S[top[S]
+ 1] // повернення
колишньої
верхівки
стеку
Наведемо кроки алгоритму пошуку в глибину з використанням стеку
Нехай G=(V, E) - простий зв'язний граф, усі вершини якого позначено попарно різними символами. У процесі пошуку вглиб вершинами графа G надають номери (DFS-номери) та певним способом даних для збереження множин, яку називають стеком. Зі стеку можна вилучити тільки той елемент, котрий було додано до нього останнім: ". Інакше кажучи, додавання й вилучення елементів у стеку відбувається з одного кінця, який називається верхівкою стеку. DFS-номери вершини х позначають DFS(х).
-
Почати з довільної вершини v. Виконати DFS(v):=1. Включити цю вершину в стек.
-
Розглянути вершину у верхівці стеку: нехай це вершина х. Якщо всі ребра, інцидентні вершині х, позначено, то перейти до кроку 4, інакше - до кроку 3.
-
Нехай {x,y} - непозначене ребро. Якщо DFS(у) уже визначено, то позначимо ребро {x,y} потовщено суцільною лінією, визначити DFS(у) як черговий DFS-номер, включити цю вершину в стек і перейти до кроку 2.
-
Виключити вершину х зі стеку. Якщо стек порожній, то зупинитись, інакше - перейти до кроку 2.