Дек як структура даних.

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

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

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

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

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

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

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

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

• очищення.

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

• Додавання елемента в кінець черги

• Додавання елемента в початок черги

• Вибірка останнього елемента

• Вибірка першого елемента

• Перевірка першого елемента (без видалення з деку)

• Перевірка останнього елемента (без видалення з деку)

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

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

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

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

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

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

Однонаправлений лінійний список.

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

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

Двонаправлений лінійний список.

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

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

Основні поняття мультисписків.

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

Стрічка як структура даних.

Стрічка – це лінійно впорядкована послідовність символів, які належать до скінченої множини символів, яка називається алфавітом.

Стрічки мають наступні важливі властивості:

• їхня довжина, як правило, змінна, хоч алфавіт фіксований;

• звичайне звернення до символів стрічки йде з будь-якого одного боку послідовності (важлива впорядкованість послідовності, а не її індексація);

• метою доступу до стрічки є на окремий її елемент, а ланцюжок символів.

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

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

• визначення довжини стрічки;

• присвоєння стрічки;

• конкатенація (зчеплення) стрічок;

• виділення підстрічки;

• пошук входження.

Зв’язне представлення даних.

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

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

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

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

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

Переваги зв’язного представлення даних:

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

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

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

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

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

• на поля зв’язку витрачається додаткова пам’ять;

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