Характеристики графу

Створення вузла

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

// Виділення вузла з даними-членом item і вказівником nextPtr

template <class T>

Node<T> *GetNode(const T& item, Node<T> *nextPtr - NULL)

{

Node<T> *newNode;

// Виділення пам'яті при передачі item і NextPtr конструктору.

// Завершення програми, якщо виділення пам'яті

// виконалося невдало 3

newNode ш new Node<T>(item, nextPtr);

if (newNode == NULL)

{

cerr << "Помилка виділення пам'яті!" «endl;

exit(1);

}

return newNode;

}

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

head = GetNode(item,head);

Функція InsertFront приймає поточну голову списку, яка є вказівником, визначаючим список, а також приймає нове значення даних. Вона вставляє значення даних у вузол на початку списку. Так як голова буде змінюватися цією операцією, вона передається як контрольний параметр.

// Вставка елемента в початок списку

template <class T>

void InsertFront(Node<T>* & head, T item)

{

// Створення нового вузла, щоб він вказував на

// Первісну голову списку 5

// Зміна голови списку

head = GetNode (item, head);

}

Функції InsertAfter і DeleteAfter є основними операціями створення списків. У кожному разі процес включає тільки зміни вказівника.

// вставити вказівник р після поточного вузла

template <class T>

void Node<T>::InsertAfter(Node<T> *p)

{

// p вказує на наступний за поточним вузол,

// a поточний вузол - на р..

p->next = next;

next = р;

}

// видалити вузол, наступний за поточним, і повернути його адресу

template <class T>

Node<T> *Node<T>::DeleteAfter(void)

{ 6

// зберегти адресу вузла, що видаляється

Node <T> * tempPtr = next;

// Якщо немає наступного вузла, повернути NULL

if (next =«NULL)

return NULL;

// Поточний вузол вказує на вузол, наступний за tempPtr.

next = tempPtr-> next;

// Повернути вказівник на непов'язаний вузол

return tempPtr;

}

Об’єднання (конкатенація) списків.

Якщо операція об’єднання списків, тоді:

.

Властивості операції.

Нехай – списки.

1. .

2. .

Реалізація операції. 7

Модифікація операції (вставка у середину списку)

.

Супроводжується двома діями:

1) ;

2) .

Циклічні списки.

Схема структури циклічного списку:

Звернемо увагу на те, що звичайному списку його голова позначається як head, а у циклічному – header.

Зауважимо, що для стандартного пов'язаного списку і

циклічного зв'язаного списку тести, 8

що визначають, чи є список порожнім, різні.

Стандартний зв'язаний список: head == NULL

Циклічний зв'язаний список: header-> next == header

Схема порожнього списку наступна:

При додаванні вузлів до списку останній вузол вказує на заголовний вузол.

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

Вузол у двозв'язному списку містить два вказівники для створення потужної і гнучкої структури обробки списків.

Слід звернути увагу на те, що зв’язки полів вказівників мають обопільні посилання «у право і у ліво», як це показано на наступному малюнку:

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

У двозв'язному списку вузол може видалити сам себе зі списку, змінюючи два вказівники. На наступному малюнку

показані відповідні цьому зміни: 10

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

Графи.

Граф упорядкована сукупність вершин і пар вершин , який можна позначити як: . Де , – декартовий добуток множини самої на себе. Якщо пари упорядковані, то граф зветься орієнтований або –

орграф, в протилежному випадку не орієнтованим. 11

Граф може представлятися графічно або аналітично.

Нехай , тоді графічне представлення є.

Характеристики графу

1. Шлях графу послідовність зв’язаних вершин , – початок шляху, – кінець шляху.

2. Довжина шляху (глибина графу на шляху ) – кількість вершин шляху – 1.

3. Петля графу – .

4. Контур графу – шлях, у якому початкова і кінцева вершини однакові.

5. Шлях повний, якщо його не можна доповнити ні одною вершиною графа.

6. Степінь вершини графу – кількість вхідних і вихідних дуг вершини .

Часткові випадки графів. 12

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

Ліс – Дверевовидний граф з декількома корінями і спільними вершинами.

–ні дерева і їх різновиди.

Бінарні дерева .

2 – 3 дерева .

Збалансовані дерева. Дерево є збалансованим, якщо для всіх повних шляхів справедливе або для деяких шляхів .

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

Приклад вузла В – дерева:

Структури даних – дерева 13

Вузол дерева містить поле даних і два поля з вказівниками. Поля вказівників називаються лівим вказівником (left) і правим вказівником (right), оскільки вони вказують на ліве і праве піддерево, відповідно. Значення NULL є ознакою порожнього вказівника або піддерева, коли обидва вказівники мають значення NULL.

Вироджене дерево еквівалентне зв'язаному списку.

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

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

Повні бінарні дерева дають цікаві математичні факти. На нульовому рівні є 2⁰ вузлів, на першому – 2¹, на другому – 2² і т.д. На перших к-1 рівнях мається 2 вузлів.

На к-му рівні кількість додаткових вузлів коливається від 1 до 2к. У повному дереві число вузлів дорівнює

1 + 2 + 4 +... + 2 + 2 = 2 – 1.

Не нашли, что искали? Воспользуйтесь поиском: