Реалізація атд “Список” при допомозі масивів
При реалізації списку при допомозі масиву елементи списку розташовуються в суміжних комірка масиву.Така реалізація дозволяє легко проглядати список і вставляти нові елементи в його кінець. Але вставка нового елементу в його середину потребує переміщення всіх послідуючих елементів на одну позицію до кінця масиву. Видалення елементу також потребує зсуву всіх решти елементів на одну позицію.При використанні масиву ми визначимо структуру типу LIST з двома значеннями: перше поле – elements, яке визначає масив елементів, друге поле –last - ціле число яке вказує на позицію останнього елементу в масиві.
Реалізація АТД “Список” при допомозі вказівників. Однозв’язні списки.
В
даному випадку, для реалізації зв’язку
між елементами списку використовується
вказівники, що звільняє нас від
необхідності використовувати неперервну
ділянку пам’яті, а відповідно і
віднеохідності пересування всіх
елементів при вставці чи видаленні
одного із них.Список
складається з комірок, кожна з яких
містить значення елементу списку і
вказівник на наступний елемент цього
списку.
Реалізація АТД “Список” при допомозі вказівників. Двозв’язні списки.
В
даному випадку, для реалізації зв’язку
між елементами списку використовується
вказівники, що звільняє нас від
необхідності використовувати неперервну
ділянку пам’яті, а відповідно і
віднеохідності пересування всіх
елементів при вставці чи видаленні
одного із них.Список
складається з комірок, кожна з яких
містить значення елементу списку і
вказівник на наступний елемент цього
списку.
Реалізація АТД “Список” при допомозі курсорів
Курсорами називатимемо - цілі числа, які вказують на положення елемента в масиві.
Представлено два масиви L = a, b, c і M = d, e. Вкладені в один масив SPACE:
Всі комірки масиву, незайняті елементами списку, утворюють окремий список, що називається вільним і використовується як джерело вільних комірок при вставці нових елементів.
Тип даних “Стек”. Оператори для роботи із АТД “Cтек”
Стек – це спеціальний тип списку, в якому всі вставки і видалення елементів виконуються тільки на одному з його кінців, який називається вершиною стеку (top).
MAKENULL(S) – робить стек порожнім.
TOP (S) – повертає елемент, що знаходиться на вершині стеку S.
POP(S) – видаляє елемент з вершини стеку (виштовхує із стеку).
PUSH(x, S) – встановлює елемент x на вершину стеку S (заштовхує елемент в стек).
EMPTY(S) – повертає значення true, якщо стек порожній, і значення false – в противному випадку.
Реалізація АТД “Стек” при допомозі массиву
function MAKENULL (STACK S)
S.top = maxlenght+1
function EMPTY (STACK S) {
if S.top > maxlenght
then return true
else return false
function TOP (STACK S)
if EMPTY(S)
then error (“стек порожній”)
else return S.elementtype[S.top] }
function POP (STACK S)
if EMPTY(S)
then error (“стек порожній”)
else S.top = S.top + 1 }
function PUSH (elementtype x, STACK S)
if S.top == 1
then error (“Стек повний”)
else
S.top = S.top – 1;
S.elements[S.top] = x;
Тип даних “Черга”. Оператори для роботи з АТД “Черга”
Черга (queue) – спеціальний тип списку, де елементи додаються з одного кінця,який назив. хвостом (tail або rear), а вилучаються з іншого, який називається головою.
MAKENULL(Q) – очищає чергу Q, роблячи її порожньою.
FRONT(Q) – функція повертає перший елемент черги Q.
ENQUEUE(x,Q) – ставить елемент x в кінець черги Q.
DEQUEUE (Q) – видаляє перший елемент із черги Q.
EMPTY(Q) – повертає значення true тоді і лише тоді коли чергою Q є порожньою.
Реалізація АТД “Черга” при допомозі вказівників
function MAKENULL (QUEUE Q)
new Q.front
Q.front->next = NULL
Q.rear = Q.front;
function EMPTY (QUEUE Q)
if Q.front == Q.rear
then return true
else return false;
function FRONT (QUEUE Q)
if EMPTY(Q)
then error (“черга порожня”)
else return Q.front->next->element
function ENQUEUE (elementtype x, QUEUE Q)
new Q.rear->next
Q.rear = Q.rear->next
Q.rear->element = x
Q.rear->next = NULL
function DEQUEUE (QUEUE Q)
if EMPTY(Q)
then error (“черга пуста”)
else Q.front = Q.front->next;