Зв’язний список та наскрізний прохід по зв’язному списку. Операції над зв’язними списками. Додавання та вилучення елементів у зв’язному списку. Навести приклади.

 

 

 

11. Структури даних. Типові статичні та динамічні структури даних. Доступ до даних.

Під структурою даних будемо розуміти таблиці даних, які включають структурні відношення. Структури даних можуть бути динамічними, статичними та мішаними.

Статичні структури даних характеризуються тим, що кількість даних і відношення не змінюються в часі.

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

Класичною задачею в галузі структур даних є задача інформаційного пошуку в структурах даних.

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

Типовою стандартною статичною структурою даних є масив. Його властивості:

Усі елементи масиву мають один і той же тип.

Усі елементи розташовуються один за одним.

Індекс першого елементу — 0.

Ім’я масиву є вказівником-константою, що дорівнює адресі початку масиву (перший байт першого елемента).

Компілятор відводить для масиву пам’ять N*sizeof(тип_елементів).

Розмір масиву може визначатися як на етапі компіляції (int a[10];), так і на етапі виконання (int *a = new int[input];). На етапі виконання додати до масиву більше елементів, ніж виділено на нього пам’яті, просто так не можна.

Динамічні структури даних — стек, двійкове дерево, контейнери, наприклад, однозв’язні та двозв’язні списки, динамічними масивами, тощо. У мові С++ контейнери представлені в стандартній бібліотеці шаблонів (STL), яка є складовою мови С++.

Розглянемо деякі контейнери детальніше:

vector — С-подібний динамічний масив. Елементи зберігаються в пам’яті послідовно, додавання в кінець масиву здійснюється за допомогою процедури push_back. Доступ до елементів здійснюється за рахунок перевантаженої операції [] так само, як до елементів звичайного масиву:

vector<int> vec; …; for (int i=0; i<vec.size(); ++i) { cout << vec[i];}

list — двозв’язний список, елементи якого зберігаються в довільних ділянках пам’яті.

map — упорядкований асоціативний масив пар елементів, що складаються із ключів та відповідних значень. Ключі повинні бути унікальними. Відрізняється швидким часом пошуку за ключем.

Найпростіший динамічний список можна виготовити самому:

struct ListElement {

int value; // значення, що зберігає елемент списку

ListElement *next_element; // вказівник на наступ ний елемент списку

};

struct List {

ListElement *list_elements;

List(): list_elements(NULL) {}

void addElement(int element) { /* реалізація процедури додавання елемента */}

int getElement(int element_number) {/* реалізація процедури отримання елемента за його номером*/}

};

Аналіз методів подання графів у вигляді динамічних та статичних структур даних. Матриця суміжності

Матриця суміжності це двовимірний масив розміром N*N, де N кількість вершин у графі:

Статичний:

int Graph[N][N];

Динамічний:

int** Graph; //масив массивів (тобто двовимірний масив)

Graph=new int*[N]; //виділяємо пам’ять для масиву вказівників (на масиви)

for (int i=0; i<N; i++)

Graph[i]=new int[N]; // виділяємо пам’ять для кожного рядка

При цьому Graph[i][j] дорівнює 0, якщо вершини i та j не є суміжними, та 1 для суміжних вершин. Для зваженого графа Graph[i][j] дорівнює вазі ребра (дуги) з вершини i у вершину j (якщо ребра не існує то якійсь домовленій константі – це або дуже велике число, або від’ємне, якщо немає від’ємних ваг).

Просторова складність цього способу O(N²).

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

Матриця інцидентності

Ребро і її вершина називаються інцидентними.

Матриця інцидентності це двовимірний масив розміром N*M:

 

Статичний:

int Graph[N][M];

Динамічний:

int** Graph; //масив массивів (тобто двовимірний масив)

Graph=new int*[N]; //виділяємо пам’ять для масиву вказівників (на масиви)

for (int i=0; i<N; i++)

Graph[i]=new int[M]; // виділяємо пам’ять для кожного рядка

M кількість ребер.

При цьому Graph[i][j] дорівнює 0, якщо вершини i та ребро j не є інцидентними, -1, якщо вершина i є кінцем орієнтованого ребра j, +1, якщо вершина i є початком орієнтованого ребра j. Інколи зручно користуватись означенням, у якому Graph[i][j] рівний вазі ребра (дуги) j, що є інцидентним вершині i.

Матриця інцидентності найкраще підходить для операції перерахування ребер, що є інцидентними вершині x.

Списки суміжності

Список суміжності це послідовність (масив, список) розміром N, кожен елемент якої є списком вершин суміжних з даною:

Статична структура:

struct NodeType

{

int count; //кількість вершин суміжних з даною

struct

{

int Node; //номер вершини

int Weight; //номер ребер

} List[N]; //масив суміжних вершин та ваг ребер, що їх з’єднують

} Graph[N];

Динамічна(у вигляді масиву однозв’язних списків):

struct NodeType

{

NodeType* next;

struct

{

int Node;

int Weight;

} item;

} *Graph=new NodeType[N];

Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з x.

Список ребер

Статичний:

struct

{

int Node1; //звідки ребро

int Node2; //куди

int Weight; //вага

} Branches[M];

Динамічний (у вигляді списку):

struct NodeType

{

NodeType* next;

struct

{

int Node1;

int Node2;

int Weight;

} item;

} FirstBranch;

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

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

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