2.8. Динамічні структури даних
Полу статичні структури даних
Властивості напівстатичних структур даних :
вони мають змінну довжину і прості способи її зміни;
зміна довжини структури відбувається в певних межах, не перевищуючи якогось максимального (граничного) значення.
З логічної точки зору напівстатична структура є послідовністю даних, пов'язаною стосунками лінійного списку (см разд. 3.3.5). Доступ до елементу може здійснюватися по його порядковому номеру.
Фізично напівстатичні структури представляються або у вигляді вектору, т. е. розташовуються в безперервній області пам'яті, або у вигляді однонапрямленого зв'язного списку, де кожен наступний елемент адресується покажчиком, що знаходиться в поточному елементі.
До напівстатичних структур відносяться стеки, черги, деки, рядки.
Динамічні структури не мають постійного розміру, тому пам'ять під окремі елементи таких структур виділяється в мить, коли вони створюються в процесі виконання програми, а не під час трансляції. Коли в елементі структури більше немає необхідності, займана ним пам'ять звільняється (елемент "руйнується").
Оскільки елементи динамічної структури розташовуються в пам'яті не по порядку і навіть не в одній області, адреса елементу такої структури не може бути вичислена з адреси початкового або попереднього елементу. Зв'язок між елементами динамічної структури встановлюється через покажчики, що містять адреси елементів в пам'яті. Таке представлення даних в пам'яті називається зв'язковим.
Таким чином, окрім інформаційних полів, заради яких створюється структура і які є видимими для кінцевого користувача ПО, динамічні структури містять поля для зв'язку з іншими елементами, видимі тільки для програміста - розробника ПО.
За допомогою зв'язного представлення даних забезпечується висока мінливість структури. Достоїнства динамічних структур :
розмір структури обмежується тільки об'ємом пам'яті комп'ютера;
при зміні логічної послідовності елементів структури (видаленні, додаванні елементу, зміні порядку дотримання елементів) потрібно тільки корекцію покажчиків.
З іншого боку, такі структури мають ряд недоліків :
робота з покажчиками вимагає високої кваліфікації програміста;
на покажчики витрачається додаткова пам'ять;
додаткова витрата часу на доступ до елементів зв'язної структури.
Література
Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения: Пер. с англ.— М.: Мир, 1982 — 368 с., ил.
Іващук В.В. Курс лекцій «Засоби мультимедіа в нових інформаційних технологіях» Національний університет харчових технологій.-К.: НУХТ, 2011. – 77 с.
Когутяк М.І., Дранчук М.М., Когуч Я.Р., Шавранський М.В., Лещій Р.М. Автоматизація неперервних технологічних процесів в нафтовій та газовій промисловості: Навчальний посібник.–Івано-Франківськ: Факел, 2006.–385с.
Конспект лекцій з дисципліни “Системи технологій” : к. т. н., доц. Фесенко М.С. Алчевськ ДонДТУ 2006, 70 стр.
Кухнюк Н.В., викладач Технічного коледжу. Інтерактивний комплекс. з дисципліни “Автоматизація технологічних процесів”. 2008, 227 ст.
Ларман Крэг. Применение UML и шаблонов проектирования. 2-е издание.: Пер. с англ. – М. Вильямс, 2004-624 с.:ил.
Проць, О.А. Данилюк, Т.Б. Лобур. Автоматизація неперервних технологічних процесів. Навчальний посібник для технічних спеціальностей вищих навчальних закладів. – Тернопіль: ТДТУ ім. І.Пулюя, 2008. – 239 с.
С.В.Шаповал, Н.Г.Морковська. Конспект лекцій з курсу „Системи технологій” Харків. ХНАМГ, 2005.- 70 с.
Microsoft Corporation Принципы проектирования и разработки программного обеспечения. Учебный курс MCSD/Пер. с англ. -2-е издание. Русская Редакция, 2002 – 736 стр., ил.
Гагарина Л. Г., Кокорева Е. В., Виснадул Б. Д. Технология разработки программного обеспечения: учебное пособие / под ред. Л. Г Гагариной. — М.: ИД «ФОРУМ»: ИНФРА-М, 2008. — 400 с.: ил. — (Высшее образование).
Галіцин В.К., Сидоренко Ю.Т., Потапенко С.Д. Технологія програмування і створення програмних продуктів: Навч. посіб. — К.: КНЕУ, 2009. — 372 с.
Гужва В. М. Інформаційні системи і технології на підприємствах: Навч. посібник. — К.: КНЕУ, 2001. — 400 c.
Лекція № 3
|
Скачать 14.87 Mb.