Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
В програмуванні масив ( array) — одна з найпростіших структур даних,сукупність елементів одного типу даних, впорядкованих за індексами, які зазвичай репрезентовані натуральними числами, що визначають положення елемента в масиві. Масив може бути одновимірним (вектором), та багатовимірним (наприклад, двовимірною таблицею). Доступ до елементів масиву здійснюється за допомогою індексу. В загальному випадку, якщо перший елемент знаходиться за адресою x,тоді напр. четвертий — за індексом x+4. Загальний алгоритм переходу до елементу, який знаходиться у i-му рядку j-стовпця виглядає наступним чином:x + (c * (i-1)) + (j-1),де x – адреса комірки, яка містить елемент з першого рядка першого стовпця. Такий вираз називається поліномом адреси.
Список – це динамічна структура даних . Вказівник — комірка пам’яті, яка містить адресу розташування іншої комірки пам’яті. На основі вказівників можна формувати складні масиви даних, напр. записи у бібліотечному каталозі.У тому випадку, коли книжки в бібліотеці відсортовано за назвою у алфавітному порядку, виникає проблема пошуку книг одного автора. Для її розв’язку можна зарезервувати в блоці комірок пам’яті додаткове місце для вказівникаНехай кожен вказівник буде містити адресу блоку, де записано іншу книжку даного автора.Таким чином всі книжки буде об’єднано у своєрідне кільце .
Основні методи для зберігання списку імен в пам’яті:
Зберігання списку з послідовними адресами.
Зберігання кожного елементу списку в іншому місці з їх зв’язуванням між собою
Організація зберігання списку одним блоком з послідовними адресами:
Якщо кожне ім’я не більше 8-ми літер, то можна розділити великий блок на підблоки по 8 комірок.
В кожному з підблоків можна зберігати окремо ім’я, яке записується по одній комірці на кожну літеру
Якщо одне з полів не використовується воно може заповнюватися пробілами
Якщо таких імен буде 8, тоді блок буде складати з 80 послідовних комірок пам’яті. Приклад блоку подано на рис. 9.3.
Хоча ця структура є простою, вона має ряд недоліків:
Припустимо, що необхідно видалити ім’я на початку списку, зі зберіганням порядку списку. Для цього доведеться всі наступні імена змістити на одиницю вперед. Іншою проблемою є збільшення елементів у наявному списку, оскільки для цього доведеться перемістити весь список в інше місце, щоб отримати новий блок безперервної пам’яті достатнього розміру
Для уникнення проблем, згаданих вище можна зберігати всі імена в різних місцях пам’яті.Для цього буде потрібно зберігати кожне ім’я в блоці з 9-ти комірок
Відповідно до організації така структура називається зв’язаним списком. Зв’язний Список – це динамічна структура даних яка містить вузли в яких міститься основна інформація і вказівники на наступний і (або) на попередній елементи(вузли). На відмінно від масиву форма та розмір списку можуть змінюватися. Для отримання місця знаходження першого елементу використовується окрема комірка пам’яті
Така комірка вказує на початок списку і називається вказівником головного елементу
Кінець списку відзначається спеціальним нульовим вказівником (NIL), який знаходиться в комірці вказівника останнього елементу, і означає, що більше вказівників немає. Для отримання місця знаходження першого елементу використовується окрема комірка пам’яті
Така комірка вказує на початок списку і називається вказівником головного елементу
Кінець списку відзначається спеціальним нульовим вказівником (NIL), який знаходиться в комірці вказівника останнього елементу, і означає, що більше вказівників немає.
Стек — список, в якому всі додавання та видалення елементів виконуються лише на одному кінці структури. В результаті такого обмеження елемент, який додається до списку останнім може видалятися з нього першим, що дало назву даному методу організації даних LIFO (Last In — First Out, останній прийшов, перший пішов). Кінець стеку, на якому виконуються операції додавання та видалення називається вершиною. Процес дод-ня елементу до стеку називається вставкою. Процес видалення елементу зі стеку називається отриманням.
Класичним застосуванням стеків є виконання програм, які виконують процедури. Коли програма повинна виконати процедуру, комп’ютер повинен перемкнути увагу на цю процедуру. Коли ж процедура вимагає виконання іншої процедури — механізм ускладнюється.
Наприкінці всього циклу виконання комп’ютер повинен повертатися до початкової програми у місці переходу до процедури.
Для реалізації стекової структури в пам’яті комп’ютера резервується безперервний блок комірок пам’яті, щоб стек міг розміститися там не залежно від додавання чи видалення елементів. Один з кінців цього блоку позначається як основа стеку. В основу стеку вставляється перший елемент. При додаванні, новий елемент вставляється після попередника, при цьому стек збільшується в другу сторону. Для забезпечення механізму запису поточної адреси вершини стеку використовується додаткова комірка пам’яті, яка називається вказівником на вершину стеку. Вказівник на вершину стеку завжди визначає поточне місце вершини стеку.
Механізм роботи є наступним:
При організації стеку в безперервному блоці комірок пам’яті різниця між концептуальною та реальною структурами є невеликою. Однак неможливо визначити розмір стеку, який буде завжди гарантовано задовольняти поставленим умовам. В такому випадку слід реалізовувати стек у вигляді зв’язаного списку.
Тоді можна уникнути обмежень розміру стеку у випадку використання безперервного блоку.
Однак така реалізація стеку буде відрізнятися від комп’ютерної реалізації.
На противагу стеку, черга є таким списком, в якому додавання елементів відбувається на одному кінці, а видалення — на іншому
Подібні структури відносяться до систем зберігання та працюють по принципу:
FIFO — first in, first out перший прийшов, перший вийшов)
Кінці черги отримали свої назви відповідно до своїх ролей:
початок — кінець черги, де відбувається видалення елементів
кінець (хвіст) — кінець черги, де відбувається додавання елементів
Чергу можна реалізувати аналогічно до реалізації стеку, єдиною відмінністю при цьому буде використання двох вказівників замість одного:
вказівник початку черги — відслідковує положення початку черги
вказівник кінця черги — відслідковує положення кінця черги
Коли черга пуста, обидва вказівники вказують на оду і ту ж ділянку пам’яті. Видалення елементу з черги означає отримання елементу, на який показує вказівник початку черги, з подальшою зміною його значення таким чином, щоб він вказував на наступний за видаленим елемент черги
Деревовидні структури — останній тип структур, які ми розглянемо.
Даний тип має схему організації типової компанії (рис. 9.10.), де на вершині знаходиться президент, від якого лінії йдуть до віце-президентів, за якими йдуть регіональні менеджери тощо. На цю структуру накладемо додаткове обмеження, яке полягає в тому, що один працівник не може знаходитися у підпорядкуванні двох керівників.
Кожен елемент дерева називається вузлом або вершиною. Найвища точка має назву кореневої вершини.
Бінарних деревах, тобто таких, які мають не більше двох дочірніх вершинТакі дерева зберігаються у пам’яті з використанням зв’язаних структур, аналогічних до зв’язаних списків. Замість двох компонентів бінарне дерево складається з трьох компонентів: значення даних, вказівника на першу дочірню вершину, вказівника на другу дочірню вершину. Перша дочірня вершина називається лівою, а друга — правою. Таким чином кожна вершина є коротким неперервним блоком пам’яті. Для зберігання дерева в пам’яті слід знайти доступні блоки комірок, яких достатньо для збереження окремих вершин, і зв’язати ці вершини відповідно до структури дерева. Тобто кожен вказівник треба встановити на ліву або праву дочірню вершину даної вершини, або присвоїти значення NIL. Відповідно у листків вказівники на обидві дочірні вершини дорівнюють NIL. Також слід звернути увагу на вказівник кореневої вершини — окрему комірку пам’яті, яка буде описувати дерево загалом.
Така структура забезпечує зручний метод пошуку будь-якої вершини дерева:її материнську вершину, або вершини, які мають спільну материнську вершину з даною. Місцезнаходження материнської вершини для даної вершини можна знайти,розділивши позицію даної вершини на 2 та відкинувши остачу.