Поняття структур даних .Масив; стек; черга.

Поняття структур даних Масив; стек; черга Цодікова Любов Михайлівна

Структура даних. В програмуванні та комп'ютерних науках структу́ри да́них — це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру. Бінарне дерево Дерево (можливо, нелінійне) — структура даних, яка складається з вузлів(вершин) і ребер, без будь-яких циклів. Дерево без вузлів називається нульовим або порожнім деревом. Дерево, яке не є порожнім, складається з кореневого вузла і багатьох рівнів додаткових вузлів, які утворюють ієрархію. Кожна вершина відвідується між відвіданням лівої та правої дитини (підвузел). Такий порядок особливо часто застосовується в бінарних деревах пошуку, тому що дає можливість обходу вершин у порядку збільшення їхніх порядкових номерів. Для цього бінарного дерева,Прямий порядок: 2, 7, 2, 6, 5, 11, 5, 9, 4 Зворотний порядок: 2, 5, 11, 6, 7, 4, 9, 5, 2 Центрований (центральний) порядок: 2, 7, 5, 6, 11, 2, 5, 4, 9

Існує безліч різних способів представлення дерев. Найбільш загальний спосіб представлення зображує вузли як записи, розташовані в динамічно виділеній пам'яті з вказівниками на своїх нащадків, предків (або і тих і інших), або, як елементи масиву, пов'язані між собою відносинами, визначеними їх позиціями в масиві. Загальне застосуванняуправління ієрархією даних;спрощення пошуку інформації (див. обхід дерева);управління сортованими списками даних;синтаксичний аналіз виразів (англ. parsing), оптимізація програм;як технологія компонування цифрових зображень для отримання різних візуальних ефектів;форма прийняття багатоетапного рішення (див. ділові шахи).

Лінійні структури даних (список (масив, стек, черга), асоціативний масив (або словник))Нелінійні структури даних (Структури Граф (база даних …), Дерево (структура даних))Базові структури даних (примітивні тип даних (int, char), Запис (програмування) або складні типи даних (Рядок, Дійсне подвійної точності, Дійсне, Об'єднання, Варіант Мічене об'єднання[en] , Буфер з проміжками )). Масив (англ. array) — сукупність елементів одного типу даних, впорядкованих за індексами, які зазвичай репрезентовані натуральними числами, що визначають положення елемента в масиві. Масив може бути одновимірним (вектором), та багатовимірним (наприклад, двовимірною таблицею), тобто таким, де індексом є не одне число, а кортеж(сукупність) з декількох чисел, кількість яких збігається з розмірністю масиву.

Приклад 1. Опис одновимірного масиву з 10 цілих чисел (тип int) з іменем A.int A[10];У результаті, в пам’яті комп’ютера виділяється 10 комірок типу int. Якщо одна комірка займає 2 байти, то всього буде виділено 20 байт пам’яті. Номер першої комірки починається з нуля. Ці комірки об’єднані спільним іменем A.                                                                   

Приклад 2. Масив з 10 елементів типу char.char M[10]; M[3] = 'a'; M[7] = '0'; M[8] = ';';                                                                    Рисунок 3. Масив з 10 елементів типу char

Приклад 1. Опис двовимірного масиву Matr цілих чисел розміром 3×4.int Matr[3][4]; // двовимірний масив розміром 3*4 Доступ до елементів масиву (рисунок 1): Matr[0][0] = 23; Matr[2][3] = 41; Matr[1][2] = -8; Рисунок 1. Доступ до елементів матриці Matr

LAZARUSОдновимірний масивvar a: array [1..10] of integer;Багатовимірний масивvar a: array [1..10, 1..10] of integer;var a: array [1..10] [1..10] of integer;var a: array [1..10] of array [1..10] of integer;Асоціативний масивможе не мати змісту про границі змінення індексів:var a: array of integer;var a: array of array of integer;Стек (англ. stack — «стос, стіс») в інформатиці та програмуванні — різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) «останнім прийшов — першим пішов» (LIFO, англ. last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім. Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку — «магазин», за аналогією з принципом роботи магазину в автоматичній зброї).

Приклад стеку: Компілятори мов програмування використовують стек для передавання параметрів в процесі виклику підпрограм, процедур та функцій. Спеціалізований стек використовується також для збереження адрес повернення з підпрограм. Операції зі стекомpush («заштовхнути елемент»): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow).pop («виштовхнути елемент»): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні «виштовхнути» елемент з вже пустого стеку, відбувається ситуація «незаповнення» стеку (англ. stack underflow). Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку. Додаткові операції (присутні не у всіх реалізаціях стеку):is. Empty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній.is. Full: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе.clear: звільнити стек (видалити усі елементи).top: отримати верхній елемент (без виштовхування).size: отримати розмір (кількість елементів) стека.swap: поміняти два верхніх елементи місцями.

Черга (англ. queue) в програмуванні — динамічна структура даних, що працює за принципом «перший прийшов — перший пішов» (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові. Така черга повністю аналогічна звичній «базарній» черзі, в якій хто перший встав в неї, той першим буде обслуженим. Основні операції з чергоюангл. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow).https://sites.google.com/site/studylazarus/home