Динамічні структури даних
Статичні структури даних
Статичні структури даних. Напівстатичні структури даних.
Статичні структури є структурованою безліччю примітивних структур. Наприклад, вектор може бути представлений впорядкованою безліччю чисел. Мінливість невластива статичним структурам, т. е. розмір пам'яті комп'ютера, що відводиться для таких даних, постійний і виділяється на етапі компіляції або виконання програми.
Вектори
З логічної точки зору вектор (одновимірний масив) є структурою даних з фіксованим числом елементів одного і того ж типу. Кожен елемент вектору має свій унікальний номер (індекс). Звернення до елементу вектору виконується по імені вектору і номеру елементу.
З фізичної точки зору елементи вектору розміщуються в пам'яті в підряд розташованих елементах пам'яті (мал. 3.6). Під елемент вектору виділяється кількість байт пам'яті, визначуване базовим типом елементу цього вектору. Тоді розмір пам'яті, що відводиться для розміщення вектору, визначатиметься наступним співвідношенням: S= до* Sizeof(тип), де до - кількість елементів (довжина) вектору, а Sizeof(тип) -- розмір пам'яті, необхідної для зберігання одного елементу вектору.
Мал. 3.6. Представлення вектору в пам'яті:
@Ім'я - адреса вектору або адреса першого елементу вектору
Двовимірні масиви
Двовимірний масив (матриця) - це вектор, кожен елемент якого вектор. Тому те, що справедливо для вектору, справедливо і для матриці (аналогічно для n -мерных масивів).
Полу статичні структури даних
Властивості напівстатичних структур даних :
• вони мають змінну довжину і прості способи її зміни;
• зміна довжини структури відбувається в певних межах, не перевищуючи якогось максимального (граничного) значення.
З логічної точки зору напівстатична структура є послідовністю даних, пов'язаною стосунками лінійного списку (см разд. 3.3.5). Доступ до елементу може здійснюватися по його порядковому номеру.
Фізично напівстатичні структури представляються або у вигляді вектору, т. е. розташовуються в безперервній області пам'яті, або у вигляді однонапрямленого зв'язного списку, де кожен наступний елемент адресується покажчиком, що знаходиться в поточному елементі.
До напівстатичних структур відносяться стеки, черги, деки, рядки.
Динамічні структури не мають постійного розміру, тому пам'ять під окремі елементи таких структур виділяється в мить, коли вони створюються в процесі виконання програми, а не під час трансляції. Коли в елементі структури більше немає необхідності, займана ним пам'ять звільняється (елемент "руйнується").
Оскільки елементи динамічної структури розташовуються в пам'яті не по порядку і навіть не в одній області, адреса елементу такої структури не може бути вичислена з адреси початкового або попереднього елементу. Зв'язок між елементами динамічної структури встановлюється через покажчики, що містять адреси елементів в пам'яті. Таке представлення даних в пам'яті називається зв'язковим.
Таким чином, окрім інформаційних полів, заради яких створюється структура і які є видимими для кінцевого користувача ПО, динамічні структури містять поля для зв'язку з іншими елементами, видимі тільки для програміста - розробника ПО.
За допомогою зв'язного представлення даних забезпечується висока мінливість структури. Достоїнства динамічних структур :
• розмір структури обмежується тільки об'ємом пам'яті комп'ютера;
• при зміні логічної послідовності елементів структури (видаленні, додаванні елементу, зміні порядку дотримання елементів) потрібно тільки корекцію покажчиків.
З іншого боку, такі структури мають ряд недоліків :
• робота з покажчиками вимагає високої кваліфікації програміста;
• на покажчики витрачається додаткова пам'ять;
• додаткова витрата часу на доступ до елементів зв'язної структури.
Література
13. Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения: Пер. с англ.— М.: Мир, 1982 — 368 с., ил.
14. Іващук В.В. Курс лекцій «Засоби мультимедіа в нових інформаційних технологіях» Національний університет харчових технологій.-К.: НУХТ, 2011. – 77 с.
15. Когутяк М.І., Дранчук М.М., Когуч Я.Р., Шавранський М.В., Лещій Р.М. Автоматизація неперервних технологічних процесів в нафтовій та газовій промисловості: Навчальний посібник.–Івано-Франківськ: Факел, 2006.–385с.
16. Конспект лекцій з дисципліни “Системи технологій” : к. т. н., доц. Фесенко М.С. Алчевськ ДонДТУ 2006, 70 стр.
17. Кухнюк Н.В., викладач Технічного коледжу. Інтерактивний комплекс. з дисципліни “Автоматизація технологічних процесів”. 2008, 227 ст.
18. Ларман Крэг. Применение UML и шаблонов проектирования. 2-е издание.: Пер. с англ. – М. Вильямс, 2004-624 с.:ил.
19. Проць, О.А. Данилюк, Т.Б. Лобур. Автоматизація неперервних технологічних процесів. Навчальний посібник для технічних спеціальностей вищих навчальних закладів. – Тернопіль: ТДТУ ім. І.Пулюя, 2008. – 239 с.
20. С.В.Шаповал, Н.Г.Морковська. Конспект лекцій з курсу „Системи технологій” Харків. ХНАМГ, 2005.- 70 с.
21. Microsoft Corporation Принципы проектирования и разработки программного обеспечения. Учебный курс MCSD/Пер. с англ. -2-е издание. Русская Редакция, 2002 – 736 стр., ил.
22. Гагарина Л. Г., Кокорева Е. В., Виснадул Б. Д. Технология разработки программного обеспечения: учебное пособие / под ред. Л. Г Гагариной. — М.: ИД «ФОРУМ»: ИНФРА-М, 2008. — 400 с.: ил. — (Высшее образование).
23. Галіцин В.К., Сидоренко Ю.Т., Потапенко С.Д. Технологія програмування і створення програмних продуктів: Навч. посіб. — К.: КНЕУ, 2009. — 372 с.
24. Гужва В. М. Інформаційні системи і технології на підприємствах: Навч. посібник. — К.: КНЕУ, 2001. — 400 c.