"> int getKeyByValue (int value, int * arr, int numItems)
Функція визначає і повертає номер ключа масиву, відповідний значенням value. В якості параметрів приймає значення для пошуку, одновимірний масив і його розмірність. p align="justify"> Вхідні і вихідні дані
Програма отримує дані з файлу, в якому зберігається список околиць вершин орієнтованого графа. Структура файлу має бути такою: номер рядка означає номер (ідентифікатор) вершини графа, в кожному рядку через пропуск записані ідентифікатори вершин, в які входять дуги, що виходять з поточної вершини. Якщо вершина не має вихідних дуг, то в рядку, що відповідає даній вершині стоїть 0. На основі лічених з файлу даних будується динамічний двонаправлений лінійний список, який зберігає список дуг орієнтованого графа. p align="justify"> На виході виводяться:
В· ім'я графа;
В· список околиць вершин, яким поставлено даний граф;
В· ступеня результату всіх вершин і ідентифікатор вершини з максимальним ступенем результату;
В· список околиць вершин графа після видалення вершин, суміжних з вершиною, що має найбільший ступінь результату;
В· матриця суміжності нового графа.
Алгоритм однією з функцій
Функція completeAjacencyMatrix.
Параметри, що приймаються функцією:
В· * firstNode - покажчик на перший вузол динамічного списку;
В· NUM_VERTEX - кількість вершин графа
В
. Аналіз тимчасової і ємнісний складності
Аналіз тимчасової складності
Для визначення тимчасової складності програми необхідно розрахувати кількість ітерацій циклів у програмі.
Кількість ітерацій циклів залежить від кількості дуг у графі, а так само від величини ідентифікатора вершини з максимальним ступенем результату і ступеня результату цієї вершини.
Нехай M - кількість дуг графа, - кількість дуг графа після видалення вершин, суміжних з вершиною, що має максимальну ступінь результату (далі - видалення), N - кількість вершин графа, - ступінь результату вершини. Тоді кількість ітерацій циклів у програмі можна обчислити за такою формулою:
В
Формула 1
Аналіз ємнісний складності
Для визначення ємнісний складності програми необхідно визначити розмір динамічного списку і матриці суміжності.
Розмір динамічного списку і матриці суміжності залежить від заданого списку о...
