Двохзв'язні списки

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

Двохзв'язним списком (doubly linked list) називається такий список, де кожен елемент зв'язаний і з попереднім і з наступним.

Циклічно зв'язаним списком (circulary linked list) називається такий список, у якому останній вузол зв'язаний з першим вузлом. Тому завжди існує можливість доступу до будь-якого елемента списку. починаючи з довільно обраного.

Такий список можна описати як однозв'язний чи двозв'язаний:

Стеки - це дискретні, зв'язані, динамічні, рекурсивні інформаційні структури.

Для стеків характерно:

Складаються з елементів того самого типу. Тип елементів може бути кожним.

Зв'язок між елементами і доступ до стек здійснюється за допомогою типізованих покажчиків. По цьому на ряді з інформацією кожен елемент стека повинна мати покажчики на попередній елемент.

Кількість елементів стека заздагеліть не задається. Воно може змінюватися в процесі виконання програми. Розмір одного елемента стека не може перевищувати 64 Кбайт.

При описі типу - стек, використовується рекурсія.

Доступ до елементів стека послідовний і обмежений. Вштовхування елемента в стек (Push), виштовхування елемента зі стека (Pop) можливі тільки з одного кінця структури - вершини стека (Top). Тому при створенні і використанні стека потрібно заготовити перемінну покажчик на вершину стека Top. Це може бути нетипізований покажчик типу Pointer. Доступ до інформації в такій структурі реалізується за принципом "Останнім прийшов, першим пішов" Lifo (Last in, First out). Завдяки цій особливості стекам іноді дають наступне визначення:

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

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

Черги- це дискретні, зв'язані, динамічні, рекурсивні інформаційні структури.

Для черг характерно:

Складаються з елементів того самого типу. Тип елементів може бути будь-яким.

Зв'язок між елементами і доступ до черг здійснюється за допомогою типізованих і нетипізованих покажчиків. По цьому на ряді з інформацією кожен елемент черги повинний мати покажчик на наступний елемент.

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

При описі типу - черга, використовується рекурсія.

Доступ до елементів черги послідовний і обмежений. Він можливий із двох кінців. Один кінець черги, з якого можливе виключення елементів називається "головою" (Head), другий кінець - "хвіст" (Tail), з його здійснюється постановка елементів у чергу. Тому при створенні і використанні черги потрібно заготовити перемінні покажчики: на "голову" (Head) і "хвіст" (Tail). Це можуть бути нетипізовані покажчики типу Pointer. Доступ до інформації в такій структурі реалізується за принципом "Першим прийшов, першим пішов" Fifo (First in, First out). Завдяки цій особливості стекам іноді дають наступне визначення:

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

Ця структура даних в інформатику і програмування прийшла з життя - аналіз реальних черг (середня довжина черги, час перебування замовлення в черги, імовірність замовлення в постановці на чергу при обмеженні її довжини, дисципліна обслуговування черги). В інформатиці черги застосовуються для реалізації буфера клавіатури, багатозадачності, списки у виді черг реалізовані в мовах програмування Lisp, Prolog, Logo.

Деки- це дискретні, зв'язані, динамічні, рекурсивні інформаційні структури.

Для деків характерно:

Складаються з елементів того самого типу. Тип елементів може бути будь-яким.

Зв'язок між елементами і доступ до деку здійснюється за допомогою типізованих вказівників. По цьому, на ряду з інформацією, кожен елемент дека повинний мати вказівники на попередній елемент.

Кількість елементів дека заздагеліть не задається. Вона може змінюватися у процесі виконання програми. Розмір одного елемента дека не може перевищувати 64 Кбайт.

При описі типу - деків, використовується рекурсія.

Доступ до елементів дека послідовний і обмежений. Додавання і видалення елементів дека можливо з обох його кінців. Тому при створенні і використанні дека потрібно заготовити перемінні вказівники на вершини дека Left і Right. Це може бути нетипізований вказівник типу Pointer. Завдяки таким можливостям доступу декам іноді дають наступне визначення:

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

<== попередня сторінка	\|	наступна сторінка ==>
Однозв'язні списки	\|	НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.