Курсова робота на тему:«АЛГОРИТМИ РОБОТИ З ДИНАМІЧНИМИ СТРУКТУРАМИ ДАНИХ»

Вступ    3

Спискові структури даних    4

Визначення лінійного списку та його різновидів    4

Робота зі стеком    6

Алгоритм вставки елемента до стеку    6

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

Приклад 1    7

Робота з чергою    10

Алгоритм вставки елемента до черги    10

Робота з лінійним списком    11

Алгоритм створення одноелементного списку    12

Алгоритм вставки елемента всередину списку    12

Алгоритм видалення елемента зсередини списку    12

Алгоритм видалення елемента з кінця списку    13

Приклад 2    13

Алгоритм роботи з алфавітним переліком слів    13

Дерева. Основні поняття    18

Алгоритми роботи з бінарними деревами    20

Створення бінарного дерева    20

Приклад 3    20

Обхід дерева    23

Таблиця 1    24

Приклад 4    24

Дерева бінарного пошуку    27

Приклад 5    27

Включення вузлів у дерево    30

Приклад 6    31

Видалення вузлів бінарного дерева    34

Приклад 7    36

Висновки    39

Література    41

 

Вступ

Дана курсова робота присвячена темі “Алгоритми роботи з динамічними структурами даних”. Її метою є ознайомити студентів з різновидами динамічних структур даних.

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

Список- це скінченна сукупність даних одного типу, між якими налагоджено зв’язок. Елемент списку складається з двох частин: самого даного (даних) та вказівника на наступний елемент списку.

Стек- це структура даних, у якій елемент, записаний останнім, зчитують (він є доступний до опрацювання) першим. Принцип “останній прийшов – перший пішов”

Використовується в багатьох технічнич пристроях і побуті.

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

Черги- це структура даних, у якій елемент, записаний першим, зчитують першим. Тут діє принцип “перший прийшов-перший пішов “, добре відомий з побуту черга за квитками тощо.

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

Деревоподібна структура даних, або дерево, є нелінійною структурою, що зображує ієрархічні зв’зки типу “предок- нащадок”: компонент-предок може мати багато нащадків, хай для кожного компонента-нащадка визначено не більше одного предка.

Спискові структури даних

Використання покажчиків є ефективним способом побудови динамічних структур даних. У розділах 7-9 вже розглядалися структури даних, такі як масиви, множини, записи та файли. Ці структури є статичними, тому що їхні розміри визначаються на етапі компіляції і залишаються незмінними протягом усього часу виконання програми. Розміри динамічних структур даних визначаються і можуть, змінюватися під час виконання. Основними різновидами динамічних структур є лінійні списки, дерева (нелінійні списки) і динамічні масиви.

Визначення лінійного списку та його різновидів

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

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

Над зв’язними лінійними списками виконуються такі дії:

  • додавання нового компонента на початок списку;
  • додавання нового компонента в кінець списку;
  • вставка нового компонента між двома наявними компонентами списку;
  • видалення компонента зі списку.

Зв’язні лінійні списки поділяють на такі різновиди:

  • однозв’язний лінійний список;
  • двозв’язний лінійний список;
  • однозв’язний циклічний список;
  • двозв’язний циклічний список;
  • стек;
  • черга.

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Dynam Str Danyh (545.5 KiB, Завантажень: 9)

Сторінка: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
завантаження...
WordPress: 23.35MB | MySQL:26 | 0,350sec