і Масив може бути одновимірним вектором та багатовимірним наприклад двовимірною таблицею

Работа добавлена на сайт samzan.net:

1.  Масиви даних

В програмуванні масив ( array) — одна з найпростіших структур даних,сукупність елементів одного типу даних, впорядкованих за індексами, які зазвичай репрезентовані натуральними числами, що визначають положення елемента в масиві. Масив може бути одновимірним (вектором), та багатовимірним (наприклад, двовимірною таблицею). Доступ до елементів масиву здійснюється  за допомогою індексу. В загальному випадку, якщо перший елемент знаходиться за адресою x,тоді напр. четвертий — за індексом x+4. Загальний алгоритм переходу до елементу, який знаходиться у i-му рядку j-стовпця виглядає  наступним чином:x + (c * (i-1)) + (j-1),де x – адреса комірки, яка містить елемент з першого рядка першого стовпця. Такий вираз називається поліномом адреси.

1.  Списки даних – вказівники.

Список – це динамічна структура даних . Вказівник — комірка пам’яті, яка містить адресу розташування іншої комірки пам’яті. На основі вказівників можна формувати складні масиви даних, напр. записи у бібліотечному каталозі.У тому випадку, коли книжки в бібліотеці відсортовано за назвою у алфавітному порядку, виникає проблема пошуку книг одного автора. Для її розв’язку можна зарезервувати в блоці комірок пам’яті додаткове місце для вказівникаНехай кожен вказівник буде містити адресу блоку, де записано іншу книжку даного автора.Таким чином всі книжки буде об’єднано у своєрідне кільце .

1.  Списки даних – безперервні списки.

Основні методи для зберігання списку імен в пам’яті:

Зберігання списку  з послідовними адресами.

Зберігання кожного елементу списку в іншому місці з їх зв’язуванням між собою

Організація зберігання списку одним блоком з послідовними адресами:

Якщо кожне ім’я  не більше  8-ми літер, то можна розділити великий блок на підблоки по 8 комірок.

В кожному з підблоків можна зберігати окремо ім’я, яке записується  по одній комірці на кожну літеру

Якщо одне з полів не використовується воно може заповнюватися пробілами

Якщо таких імен буде 8, тоді блок буде складати з  80 послідовних комірок пам’яті. Приклад блоку подано на рис. 9.3.

Хоча ця структура є простою, вона має ряд недоліків:

Припустимо, що необхідно видалити ім’я на початку списку, зі зберіганням порядку списку. Для цього доведеться всі наступні імена змістити на одиницю вперед. Іншою проблемою є збільшення елементів у наявному списку, оскільки для цього доведеться перемістити весь список в інше місце, щоб отримати новий блок безперервної пам’яті достатнього розміру

1.  Списки даних – зв’язні списки.

Для уникнення проблем, згаданих вище можна зберігати всі імена в різних місцях пам’яті.Для цього буде потрібно зберігати кожне ім’я в блоці з 9-ти комірок

1.  8 комірок буде використовуватися для зберігання імені
2.  1 комірка буде використовуватися для зберігання вказівника на наступний елемент

      Відповідно до організації така структура називається зв’язаним списком. Зв’язний Список – це динамічна     структура даних яка містить вузли в яких міститься основна інформація і вказівники на наступний і (або) на попередній елементи(вузли). На відмінно від масиву форма та розмір списку можуть змінюватися. Для отримання місця знаходження першого елементу використовується окрема комірка пам’яті

Така комірка вказує  на початок списку і називається вказівником головного елементу

Кінець списку відзначається спеціальним нульовим вказівником (NIL), який знаходиться в комірці вказівника останнього елементу, і означає, що більше вказівників немає. Для отримання місця знаходження першого елементу використовується окрема комірка пам’яті

Така комірка вказує  на початок списку і називається вказівником головного елементу

Кінець списку відзначається спеціальним нульовим вказівником (NIL), який знаходиться в комірці вказівника останнього елементу, і означає, що більше вказівників немає.

1.  Поняття стеку.

Стек — список, в якому всі додавання та видалення елементів виконуються лише на одному кінці структури. В результаті такого обмеження елемент, який додається до списку останнім може видалятися з нього першим, що дало назву даному методу організації даних LIFO (Last In — First Out, останній прийшов, перший пішов). Кінець стеку, на якому виконуються операції додавання та видалення називається вершиною. Процес дод-ня елементу до стеку називається вставкою. Процес видалення елементу зі стеку називається отриманням.

1.  Стеки – механізм повернення.

Класичним застосуванням стеків є виконання програм, які виконують процедури. Коли програма повинна виконати процедуру, комп’ютер повинен перемкнути увагу на цю процедуру. Коли ж процедура вимагає виконання іншої процедури — механізм ускладнюється.

Наприкінці всього циклу виконання комп’ютер повинен повертатися до початкової програми у місці переходу до процедури.

1.  Стеки – реалізація стеків.

Для реалізації стекової структури в пам’яті комп’ютера резервується безперервний блок комірок пам’яті, щоб стек міг розміститися там не залежно від додавання чи видалення елементів. Один з кінців цього блоку позначається як основа стеку. В основу стеку вставляється перший елемент. При додаванні, новий елемент вставляється після попередника, при цьому стек збільшується в другу сторону. Для забезпечення механізму запису поточної адреси вершини стеку використовується додаткова комірка пам’яті, яка називається вказівником на вершину стеку. Вказівник на вершину стеку завжди визначає поточне місце вершини стеку.

Механізм роботи є наступним:

1.  Для вставки елементу до стеку потрібно:
   1.  змінити поточне значення вершини стеку, щоб воно вказувало на вільну позицію
   2.  помістити в поточну позицію вершини стеку новий елемент
2.  Для отримання елементу зі стеку потрібно:
   1.  зчитати дані, на які вказує вершина стеку
   2.  відкоригувати значення вершини стеку таким чином, щоб воно вказувало на наступний (нижчий) елемент стеку.

При організації стеку в безперервному блоці комірок пам’яті різниця між концептуальною та реальною структурами є невеликою. Однак неможливо визначити розмір стеку, який буде завжди гарантовано задовольняти поставленим умовам. В такому випадку слід реалізовувати стек у вигляді зв’язаного списку.

Тоді можна уникнути обмежень розміру стеку у випадку використання безперервного блоку.

Однак така реалізація стеку буде відрізнятися від комп’ютерної реалізації.

1.  Поняття черги

На противагу стеку, черга є таким списком, в якому додавання елементів відбувається на одному кінці, а видалення — на іншому

Подібні структури відносяться до систем зберігання та працюють по принципу:

FIFO — first in, first out перший прийшов, перший вийшов)

Кінці черги отримали свої назви відповідно до своїх ролей:

початок — кінець черги, де відбувається видалення елементів

кінець (хвіст) — кінець черги, де відбувається додавання елементів

Чергу можна реалізувати аналогічно до реалізації стеку, єдиною відмінністю при цьому буде використання двох вказівників замість одного:

вказівник початку черги — відслідковує положення початку черги

вказівник кінця черги — відслідковує положення кінця черги

Коли черга пуста, обидва вказівники вказують на оду і ту ж ділянку пам’яті. Видалення елементу з черги означає отримання елементу, на який показує вказівник початку черги, з подальшою зміною його значення таким чином, щоб він вказував на наступний за видаленим елемент черги

1.  Деревовидні структури

Деревовидні структури — останній тип структур, які ми розглянемо.

Даний тип має схему організації типової компанії (рис. 9.10.), де на вершині знаходиться президент, від якого лінії йдуть до віце-президентів, за якими йдуть регіональні менеджери тощо. На цю структуру накладемо додаткове обмеження, яке полягає в тому, що один працівник не може знаходитися у підпорядкуванні двох керівників.

Кожен елемент дерева називається вузлом або вершиною. Найвища точка має назву кореневої вершини.

1.  Вершини на протилежній стороні дерева мають назву кінцівок або листків
2.  Вершина разом з її підструктурами називається піддеревом
3.  Такий аналіз дозволяє посилатися на предків та нащадків даної вершини
4.  Безпосередні предки даної вершини називаються материнськими вершинами
5.  Безпосередні нащадки — дочірні вершини
6.  Вершини, які мають спільну материнську вершину називають близнюками
7.  Найдовша кількість вузлів від кореневої вершини до листа називається глибиною дерева

1.  Пакет реалізації бінарних дерев

Бінарних деревах, тобто таких, які мають не більше двох дочірніх вершинТакі дерева зберігаються у пам’яті з використанням зв’язаних структур, аналогічних до зв’язаних списків. Замість двох компонентів бінарне дерево складається з трьох компонентів: значення даних, вказівника на першу дочірню вершину, вказівника на другу дочірню вершину. Перша дочірня вершина називається лівою, а друга — правою. Таким чином кожна вершина є коротким неперервним блоком пам’яті. Для зберігання дерева в пам’яті слід знайти доступні блоки комірок, яких достатньо для збереження окремих вершин, і зв’язати ці вершини відповідно до структури дерева. Тобто кожен вказівник треба встановити на ліву або праву дочірню вершину даної вершини, або присвоїти значення NIL. Відповідно у листків вказівники на обидві дочірні вершини дорівнюють NIL. Також слід звернути увагу на вказівник кореневої вершини — окрему комірку пам’яті, яка буде описувати дерево загалом.

Така структура забезпечує зручний метод пошуку будь-якої вершини дерева:її материнську вершину, або вершини, які мають спільну материнську вершину з даною. Місцезнаходження материнської вершини для даної вершини можна знайти,розділивши позицію даної вершини на 2 та відкинувши остачу.

1.  Субъект объект цели задачи государственного регулирования экономики
2. Отказ в возбуждении уголовного дела
3. botulus колбаса[1] тяжёлое токсикоинфекционное заболевание характеризующееся поражением нервной системы
4. Тематический словарь 2
5. тематики Реферат
6. 7 Пояснительная записка
7. Життя й революція
8. Бухгалтерский баланс Виды баланса
9. во частей- 17 Статус- закончен Описание-1837 год
10. У Платона вещи чувственно воспринимаемого мира рассматриваются лишь как видимость как искаженное отражени
11. АКАДЕМИЯ ТРУДА И СОЦИАЛЬНЫХ ОТНОШЕНИЙ
12. Ювелирторг СКУПКАПРОДАЖА ЛОМА ЮВЕЛИРНЫХ ИЗДЕЛИЙ ИЗ ДРАГМЕТАЛЛО
13. Реферат- Краткий очерк истории религии в домарксистской и буржуазной науке
14. винторезный станок 1М 64 11 045 353 АПРТО 3X10
15. Арбитражный процесс- основные понятия и документы
16. Вариант 1 Часть 1
17. практикум Практика и подходы к реализации новых образовательных стандартов в урочной и внеурочной деятель
18. ТЕМА- НЕЙРОЭНДОКРИННЫЕ СИНДРОМЫ
19. Звичайні співробітники будуть зацікавлені в гарних стосунках з Вами від Вас чимало залежить
20.  АНАЛИЗ СОСТОЯНИЯ ДЛИННОЙ ЛИНИИ ПРИ ЛИНЕЙНОЙ НАГРУЗКЕ В зависимости от исходных данных анализ состоян

Материалы собраны группой SamZan и находятся в свободном доступе