Теоритическая часть
Одним из отличительных признаков различных структур данных является характер отношений между элементами. По взаимной подчиненности элементов структуры данных подразделяются на линейные и нелинейные. В линейных структурах все элементы равноправны. К ним относятся массив, множество, стек, очередь.
В нелинейных структурах между элементами существуют отношения подчиненности или они могут быть связаны логическими условиями. К ним относятся деревья, графы, фреймы.
Дерево (корневое дерево) – это непустое множество элементов (узлов), в котором выделен один элемент, называемый корнем дерева, а все остальные элементы разбиты на несколько непересекающихся подмножеств, называемых поддеревьями исходного дерева. Каждое из поддеревьев, в свою очередь, есть дерево.
Число поддеревьев данного узла называется степенью данного узла.
Каждому из узлов дерева, кроме корня, можно сопоставить ровно один из других имеющихся узлов, который называется предком данного узла. Тогда данный узел будет считаться потомком этого узла. Корень дерева – это единственный узел, не имеющий предка. Если узел не имеет потомков, то он называется концевым или терминальным узлом или листом дерева. Уровень узла – величина, на единицу большая расстояния (количества ребер) до корня (единица – это уровень корня).
Графы формально описывают множество близких ситуаций. Графы ориентированы (подобно улицам с односторонним движением) или взвешены - каждой дороге приписана стоимость путешествия по ней (если, например, дороги платные). Существует много способов хранения графов в памяти компьютера, отличающихся по величине накладных расходов; выбор способа может зависеть от самого графа.
Для графов общего вида ситуация оказывается сложнее: в среднем графе гораздо больше связей, чем в дереве. Есть два метода обхода графов: в глубину и по уровням (в ширину), позволяющих преодолеть эту трудность. Существует понятие остовного дерева. Остовное дерево представляет собой связное подмножество графа, не содержащее циклов, включающее в себя все вершины графа и некоторые из его ребер. Минимальное остовное дерево это остовное дерево, имеющее минимально возможную сумму весов ребер. Одно из применений минимальных остовных деревьев - организация внутренней компьютерной сети. Передающие станции устанавливаются в стратегически важных местах некоторой области. Если мы хотим уменьшить суммарную стоимость объединения станций в сеть, то можно нарисовать граф, в котором станции будут служить вершинами, а ребрам, их соединяющим, можно приписать стоимость соединения. Минимальное остовное дерево этого графа указывает, какие станции следует соединить между собой, чтобы любые две станции оказались соединенными, причем общая стоимость соединения была минимально возможной. (2)
Практические задачи
Деревья
Задание:определить среднее арифметическое значение узлов дерева.
Таблица № 8.
| Наименование переменной | Тип | Назначение | |
| Входные данные | t->inf | int | Информационная часть дерева |
| a | int | Считывается из файла и добавляется в дерево | |
| sum | int | Подсчитывает сумму элементов дерева | |
| cnt | int | Подсчитывает количество элементов дерева | |
| Выходные данные | t->inf | int | Хранятся числа из файла |
Блок-схема функции treeЕ()
Листинг программы(неполный):
#include<stdio.h>
#include<stdlib.h>
struct tree
{
int inf;
tree *l;
tree *r;
}*t;
int sum=0,cnt=0;
void treeE();
//прототипы функций дерева
void preorder(tree *tr);
void inorder(tree *tr);
void postorder(tree *tr);
void add(int x, tree *&tr);
void search(int x, tree *tr);
void del_tree(tree *&tr);
void print_list(tree *tr);
void main_tree (void)
{
printf("Деревья\n");
for(;;)
{
printf("1-Задание\n");
printf("2-Вернуться к главному меню\n");
int q;
do
{
printf("Выберите пункт меню:");
scanf("%d",&q);
}while(q<0||q>3);
switch (q)
{
case 1:
{
treeE();
system("pause");
system("cls");
break;
}
case 2: return;
}
}
}
Полный листинг программы приведен в приложении
Результат выполнения программы:
Рис. 6.1. Дерево.
Графы
Задание: Найти все вершины графа, недостижимые из заданной вершины.
Таблица № 9.
| Наименование переменной | Тип | Назначение | |
| Входные данные | i,j,i2 | int | Переменные для цикла |
| num | int | Вводимая пользователем, номер вершины для которой ищется недостижимые вершины | |
| **gr | int | Массив для матрицы смежности | |
| q[10] | int | Для определения смежности | |
| Выходные данные | q[10] | int | Хранятся нули и еденицы в зависимости от вершины,смежная или нет с данной |
Блок-схема функции graf()
Листинг программы:
#include<stdio.h>
#include<stdlib.h>
void graf(void);
void main_graf()
{
printf("Графы\n");
for(;;)
{
printf("1-Задание\n");
printf("2-Вернуться к главному меню\n");
int q;
do
{
printf("Выберите пункт меню:");
scanf("%d",&q);
}while(q<0||q>3);
switch (q)
{
case 1:
{
graf();
system("pause");
system("cls");
break;
}
case 2: return;
}
}
}
Полный листинг программы приведен в приложении.
Результат выполнения программы:
Рис.6.2. Определение недостижимых вершин для вершины 1
Рис.6.3. Определение недостижимых вершин для вершины 3
Рис.6.4. Определение недостижимых вершин для вершины 2