Мiнiстерство освіти і науки України

Мiнiстерство освіти і науки України

Тернопільський національний технічний університет імені Івана Пулюя

Факультет комп'ютерно-інформаційних систем і програмної інженерії

Кафедра програмної інженерії

ЗВІТ

до лабораторної роботи №2

з навчальної дисципліни «Алгоритми та структури даних»

Тема: Абстрактний тип даних “Cписок“

Підготував:

студент групи СП-11

Мойсеюк Дмитро Вадимович

Тернопіль 2013

Завдання 1. Реалізувати з допомогою псевдокоду алгоритми виконання наступних операцій для двозвязного списку:

- MAKENULL (створює порожній список)

- INSERT (додає елемент до списку в задану позицію)

- DELETE (видаляє елемент з списку)

- LOCATE (знаходить позицію елементу в списку)

- RETRIEVE (повертає значення елементу списку)

- PREVIOUS (повертає вказівник на попередній елемент списку)

- NEXT (повертає вказівник на наступний елемент списку)

- PRINTLIST (друкує перелік усіх елементі в списку).

Короткі теоретичні відомості.

Тип даних – це множина значень, яких може набувати перемінна.

Структура даних – це деякий спосіб збереження організації даних, що полегшує доступ до даної модифікації.

АТД [Абстрактний тип даних] являє собою математичну модель представлення даних та набір операцій, які можна виконувати в межах даної моделі.

У математиці списком називають послідовність елементів певного типа, який в загальному випадку позначатимемо як elementtype (тип елементу) і записують у вигляді послідовності елементів, розділених комами: a₁, а₂,..., а_n, де п > 0 (де а_i має тип elementtype).

Кількість елементів n такого списку називатимемо довжиною списку. Якщо n > 1, то а₁ називається першим елементом, а а_n - останнім елементом списку. Якщо разі n = 0, маємо порожній список, який не містить елементів.

Основою властивістю списків, є можнливість лінійного впорядкування його елементів, тобто ми можемо стверджувати, що елемент a_i передує елементу a_i+1 (для i=1,2,3,…n-1) і слідує за елементом a_i-1 (для n=2,3,…n).

Для формування абстрактного типу даних на основі математичного визначення поняття списку, ми можемо використати оператори(дії): MAKENULL, INSERT, DELETE, LOCATE, RETRIEVE, PREVIOUS, NEXT, PRINTLIST.

Перейдемо до реалізації.

struct celltype

elementtype element

celltype *next

celltype *prev

1. function MAKENULL(L)

{ position p;

p=new celltype;

p->next=null;

p->prev=null;

p=null;

2. function INSERT(x, p, L)

{ position p;

position tmp;

tmp = new celltype;

tmp->next=p->next;

p->next->prev = tmp;

tmp->prev = p;

tmp->element=x;

}

3. function DELETE(p, L)

{ position p;

if(p->prev!=null)

{

p->next->prev=p->prev;

if(p->next!=null)

{

p->prev->next=p->next;

}

}

}

4. function LOCATE(x, L)

{ position p;

while(p->next!=null)

if(p->next->element==x)

return p;

else p=p->next;

return null;

}

5. function RETRIEVE(p, L)

{ position p;

if(p<1 || p->next=null)

return error;

else

{

for p=1 to p->next=null do

{

p=p->next;

return p->element;

}

}

}

6. function PREVIOUS(p, L)

{ position p;

Position q;

if(p->prev!=null)

{

q=p->next;

q->next=p;

return q;

} else error; }

7. function NEXT(p, L)

{ position p;

position q;

if(p->next!=null)

{

q=p->next;

p->prev=p;

return q;

}

else error;

}

8. function PRINTLIST(L)

{ position p;

for p=1 to p->next=null do

{

cout<<p->element;

p=p->next;

}

}

Висновок.

Я набув навичок щодо реалізації АТД “Cписок” при допомозі двозвязного списку та інших методів.

Дата добавления: 2015-11-04