Алгоритми і структури даних Опорний конспект лекцій для студентів заочно-дистанційної форми навчання спеціальності „Економічна кібернетика”



Сторінка7/19
Дата конвертації20.11.2016
Розмір1.02 Mb.
1   2   3   4   5   6   7   8   9   10   ...   19

4.4.Деки


Дек – особливий вид черги. Дек (deq – double ended queue, тобто черга з двома кінцями) – це такий послідовний список, в якому як включення, так і виключення елементів, може здійснюватися з будь-якого з двох кінців списку. Так само можна сформулювати поняття деку, як стек, в якому включення і виключення елементів може здійснюватися з обох кінців.

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

Над деком доступні наступні операції:


  • включення елемента праворуч;

  • включення елемента ліворуч;

  • виключення елемента з права;

  • виключення елемента з ліва;

  • визначення розміру;

  • очищення.

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

4.5.Лінійні списки


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

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

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

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

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

Найчастіше зі списками доводиться виконувати такі операції:



  • Знайти елемент із заданою властивістю;

  • Визначити і-й елемент у лінійному списку;

  • Внести додатковий елемент до або після вказаного вузла;

  • Вилучити певний елемент списку;

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

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

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

Над лінійним списком допустимі наступні операції.

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

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

Операція вибірки елемента з списку – повертає елемент, який знаходиться в конкретній позиції списку. Результат не визначений, якщо в списку немає такої позиції.

Операція вилучення – вилучає елемент в конкретній позиції зі списку. Результат невизначений, якщо в списку немає вказаної позиції.

Операції вибірки попереднього і наступного елемента – повертають відповідно наступній і попередній елемент списку відносно конкретної позиці в списку.

Функція очистки списку робить список пустим.

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

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

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

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

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



Проте, обробка однозв’язного списку не завжди зручна, оскільки відсутня можливість просування в протилежну сторону. Таку можливість забезпечує двох-зв’язний список, кожний елемент якого містить два покажчики: на наступний і попередній елементи списку.



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

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

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

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

Розглянемо деякі прості операції над лінійними списками.

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

Вставка елемента в двох-зв’язний список:

Наведені приклади забезпечують вставку в середину списку, але не можуть бути застосовані для вставки на початок списку. При такій операції повинен модифікуватися покажчик на початок списку:



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



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



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

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

У процедурі перестановки для двох-зв’язного списку неважко врахувати і перестановку на початку списку.


1   2   3   4   5   6   7   8   9   10   ...   19


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка