Динамічні структури даніх

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

Базова елементом структури даніх є елемент (вузол), Який Призначений для Зберігання Певного типу даніх. ЯКЩО Елементи зв'язані Між собою за допомог покажчіків, то такий спосіб організації даніх назівається дінамічнімі структурами даніх, так Як їх Розмір дінамічно змінюється Під годину виконан прогр.

З дінамічніх структур даніх найчастіше вікорістовуються лінійні списки, стеки, черга та бінарні дерева.

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

Лінійній список - ції скінченна послідовність однотипних елементів (вузлів). Кількість елементів у Цій послідовності назівається довжина списку. Основні методи Зберігання лінійніх Списків поділяються на методи послідовного та зв'язаного зберігання.

Послідовне Зберігання Списків. Метод послідовного Зберігання Списків грунтується на вікорістанні масивов елементів Деяк типу та змінної, в якій зберігається Поточна кількість елементів списку.

# Define MAX 100 / * максимально можлива довжина списку * /

typedef struct

{

int x; / * тут потрібно описати структуру елементів списку * /

} Elementtype;

typedef struct

{

elementtype elements [MAX];

int count;

} Listtype;

У віщенаведеному фрагменті Програми опісуються тіпі даніх elementtype (візначає структуру елемента списку) та listtype (містіть масив для Зберігання елементів та змінну для Зберігання потокового розміру списку).

Наводимое Приклади реалізації функцій для виконан основних операцій над списками.

Ініціалізація списку (робіть список порожнім).

void list_reset (listtype * list)

{

list-> count = 0;

};

Додавання нового елемента в позіцію pos.

void list_insert (listtype * list, int pos, elementtype element)

{

int j;

if (pos <0 | | pos> list-> count | | pos> = MAX) return;

for (j = list-> count; j> pos; j -)

{

list-> elements [j] = list-> elements [j-1];

};

list-> elements [j] = element;

list-> count + +;

};

Вилучення елемента з номером pos.

void list_delete (listtype * list, int pos)

{

int j;

if (pos <0 | | pos> list-> count) return;

for (j = pos +1; j <list-> count; j + +)

{

list-> elements [j-1] = list-> elements [j];

};

list-> count -;};

Отримання елемента з номером pos.

int list_get (listtype * list, int pos, elementtype * element)

{

if (pos <0 | | pos> list-> count)

{

return 0; };

* Element = list-> elements [pos];

return 1;};

При послідовному зберіганні Списків за допомог масівів Елементи списку зберігаються в масіві. Така організація дозволяє легко переглядаті вміст списку та додаваті Нові Елементи в Його кінець. Альо Такі Операції, Як вставка нового елемента в середину списку чі вилучення елемента з середини списку потребують зсуву Всіх Наступний елементів. При збільшенні елементів масива кількість операцій, Потрібна для впорядкування списку, стрімко зростає.

Зв'язане зберігання лінійніх списків. Найпростішій спосіб зв'язати множини елементів - Зробити так, щоб Кожній елемент містів посилання на наступний. Такий список назівається односпрямованім (однозв'язанім). Якщо додати в такий список галі ї посилання на попередній елемент, то отрімаємо двозв'язаній список. А список, перший та останній елементи якого зв'язані, назівається кільцевім.

Структуру даніх для зберігання односпрямованого лінійного списку можна описати таким чином:

typedef long elemtype;

typedef struct node

{

elemtype val;

struct node * next;

} List;

У даному фрагменті програми опісуються декілька тіпів даніх:

elemtype - візначає тип даніх лінійного списку. Можна використо-вувати будь-який стандартний тип даніх, включаючі структури.

list - візначає структуру елемента лінійного списку (val - значення, його призначення та зберігається у вузлі, next - Покажчик на Наступний вузол).

list * addbeg (list * first, elemtype x)

{

list * vsp;

vsp = (list *) malloc (sizeof (list));

vsp-> val = x;

vsp-> next = first;

first = vsp;

return first;

}

Видалення елемента з початку списку.

list * delbeg (list * first)

{

list * vsp;

vsp = first-> next;

free (first);

return vsp;

}

Друк значень списку.

void print (list * first)

{

list * vsp;

vsp = first;

while (vsp)

{

printf ("% i \ n", vsp-> val);

vsp = vsp-> next;

}

}

Питання для контролю:

4. Що таке списки?

5. Як видалити елемент списку?

6. Що таке лінійний список?

Література:

1. Д. Рассохин, “От С к С++” , Москва, “Едель” 2003 г., с. 371-379

Урок №65

(згідно робочої навчальної програми)

Тема: Стеки

Питання:

1.Стек. Загальні поняття.

2. Приклад використання стеку