рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Особливості динамічних структур

Реферат Курсовая Конспект

Выберите учебное заведение

Особливості динамічних структур

Особливості динамічних структур - раздел Образование, Графи P Динамічні Структури Даних По Визначенню Характеризуються:...

Динамічні структури даних по визначенню характеризуються:

Ø відсутністю фізичної суміжності елементів структури в пам'яті,

Ø мінливістю і непередбачуваністю розміру (числа елементів) та структури в процесі її обробки.

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

Елемент динамічної структури складається з двох полів:

Ø інформаційного поля або поля даних, у якому містяться ті дані, заради яких і створюється структура; у загальному випадку інформаційне поле саме є інтегрованою структурою – вектором, масивом, записом і т.п.;

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

Коли зв'язне представлення даних використовується для рішення прикладної задачі, для кінцевого користувача "видимим" робиться тільки вміст інформаційного поля, а поле зв'язків використовується тільки програмістом-розроблювачем. Достоїнства зв'язного представлення даних:

Ø у можливості забезпечення значної мінливості структур;

Ø розмір структури обмежується тільки доступним обсягом машинної пам'яті;

Ø при зміні логічної послідовності елементів структури потрібно не переміщення даних у пам'яті, а тільки корекція покажчиків.

Разом з тим зв'язне представлення не позбавлене і недоліків, основні з яких є:

Ø робота з покажчиками вимагає, як правило, більш високої кваліфікації від програміста;

Ø на поля зв'язків витрачається додаткова пам'ять;

Ø доступ до елементів зв'язної структури може бути менш ефективним за часом.

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

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Графи P

ДИНАМІЧНІ СТРУКТУРИ ДАНИХ R... Особливості динамічних структурP Лінійні зв язні списки P...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Особливості динамічних структур

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Застосування лінійних списків
Лінійні списки знаходять широке застосування в додатках, де непередбачені вимоги на розмір пам'яті, необхідної для збереження даних; велике число складних операцій над даними, особливо операцій

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

Застосування списків
Найбільше впровадження списки знайшли у мові програмування LISP. LISP – це мова обробки списків. Усі дані в LISP представляються у вигляді списків, структура елемента списку включає

Логічна структура, визначення
Граф - це складна нелінійна багатозв’язна динамічна структура, що відображає властивості і зв'язки складного об'єкта і має наступні властивості: - на кожен елемент (вузол,

Машинне представлення орграфів
Існують два основних методи представлення графів у пам'яті ЕОМ: матричний, тобто масивами, і зв'язними нелінійними списками. Вибір методу представлення залежить від природи даних і операцій, вик

Алгоритми обробки графів
Алгоритми обробки графів аналогічні алгоритмам обробки нелінійних списків, до яких можуть бути віднесені графи. Як приклад приведемо програму, що знаходить найкоротший шлях між двом

Основні визначення
Дерево - це граф, що характеризується наступними властивостями: - існує єдиний елемент (вузол, вершина), на який не посилається ніякий інший елемент - який називається корене

Логічне представлення і зображення дерев
Мається ряд способів графічного зображення дерев (див. рис. 7.17). 1). Використання діаграм Венна, що наочно показують вкладеність піддерев. 2). Спосіб,

Бінарні дерева
Відрізняють m-арні дерева, тобто такі дерева в яких напівступінь виходу кожної вершини менше або дорівнює m (де m може дорівнювати 0,1,2,3 і т.д.). Якщо напівступінь виходу кожної вершини в точн

Типи бінарних дерев
Очевидно, що дерева, що складаються з n вершин, можуть бути побудовані по-різному. У залежності від того, як будуються дерева, розрізняють: ідеально збалансовані дерева, збалансовані і не збалан

Основні операції над деревами
Над деревами визначені наступні основні операції: - обхід дерева у визначеному порядку, - пошук вузла з заданим ключем, - додавання нового вузла, - видалення вуз

Використання дерев
Дерева знаходять широке застосування при реалізації трансляторів, при роботі з арифметичними виразами, для створення і роботи з частотними словниками, в системах економічного кодування сповіщень, т