«списки и сети (деревья и графы) динамические линейные и нелинейные структуры»

ЛАБОРАТОРНАЯ РАБОТА № 3.
ТЕМА: «СПИСКИ И СЕТИ (ДЕРЕВЬЯ И ГРАФЫ)
ДИНАМИЧЕСКИЕ ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ СТРУКТУРЫ»
ЗАДАНИЕ 1. Реализовать структуру односвязный или двусвязный список на основе пары– значение (указатели и данные). Во всех вариантах предусмотреть динамическое выделение памяти и освобождение неиспользуемых участков. Во всех задачах перед обработкой выводить исходный список и результирующий список.

Заполнить список случайными положительными и отрицательными целыми числами. Удалить из списка все отрицательные элементы.

Если очередной элемент массива отрицателен, то все элементы следующие за ним надо передвинуть на одну ячейку вперед. В результате отрицательный элемент как бы затрется, а учитываемую длину массива надо уменьшить на единицу.
Поскольку непредсказуемо могут меняться как длина массива, так и счетчик-индекс элементов, то цикл for не подходит. Когда встречается отрицательный элемент, то индекс не увеличивается, т.к. на это место записывается новый элемент, который будет проверяться в следующей итерации цикла. При этом надо уменьшить значение длины массива.
Если же элемент не отрицательный, то надо перейти к следующему элементу, т.е. увеличить индекс и при этом не уменьшать длину массива.
#include < stdio.h>
#define N 10
main() {
int a[N], i,j, m;
srand(time(NULL));
for (i=0; i< N; i++) {
a[i] = rand()%10 - 5;
printf("%d ", a[i]);
}
printf("\n");
i = 0;
m = N;
while (i < m)
if (a[i] < 0) {
m -= 1;
for (j=i; j < m; j++)
a[j] = a[j+1];
} else
i += 1;


for (i=0; i< m; i++) {
printf("%d ", a[i]);
}
printf("\n");
}



ЗАДАНИЕ 2. Определить новую динамическую структуру данных (бинарное дерево на основе нелинейного связного списка). Описать стандартные операции-процедуры по работе со структурой данных (добавления нового элемента, обхода дерева, удаления элемента, визуализации дерева и индивидуального задания).
Вершины дерева вещественные числа. Описать процедуру, которая строит список, узлами которого являются вершины с положительными значениями


#include
using namespace std;


int tabs = 0; //Для создания отступов
int kol_vo = 0;
//Кол-во отступов высчитывается по кол-ву рекурсивного вхождения при выводе в фукцию print


//Структура ветки
struct Branch
{
int Data; //Поле данных
Branch* LeftBranch; //УКАЗАТЕЛИ на соседние веточки
Branch* RightBranch;
};


//Функция внесения данных
void Add(int aData, Branch*& aBranch)
{
//Если ветки не существует
if (!aBranch)
{ //создадим ее и зададим в нее данные
aBranch = new Branch;
aBranch->Data = aData;
aBranch->LeftBranch = 0;
aBranch->RightBranch = 0;
return;
}
else //Иначе сверим вносимое
if (aBranch->Data > aData)
{ //Если оно меньше того, что в этой ветке - добавим влево
Add(aData, aBranch->LeftBranch);
}
else
{ //Иначе в ветку справа
Add(aData, aBranch->RightBranch);
};
}


//Функция вывода дерева
void print(Branch* aBranch)
{
if (!aBranch) return; //Если ветки не существует - выходим. Выводить нечего
tabs += 5; //Иначе увеличим счетчик рекурсивно вызванных процедур
//Который будет считать нам отступы для красивого вывода


print(aBranch->LeftBranch); //Выведем ветку и ее подветки слева
for (int i = 0; i < tabs; i++) cout << " "; //Потом отступы
cout << aBranch->Data << endl; //Данные этой ветки


print(aBranch->RightBranch);//И ветки, что справа
tabs-= 5; //После уменьшим кол-во отступов
return;
}


void pr_obh(Branch*& aBranch)
{
if (NULL == aBranch) return; //Если дерева нет, выходим

cout << aBranch->Data << endl; //Посетили узел
pr_obh(aBranch->LeftBranch); //Обошли левое поддерево
pr_obh(aBranch->RightBranch); //Обошли правое поддерево
}


int main()
{
setlocale(LC_ALL, "rus");
Branch* Root = 0;
int vel;
int element;
int k;


cout << "Введите кол-во элементов для будущего дерева: ";
cin >> vel;
cout << endl;


for (int i = 0; i < vel; i++)
{
Add(rand() % 201 + (-100), Root);
}


cout << "Вывод бинарного дерева: " << endl;
print(Root);
cout << endl;


cout << "Прямой обход бинарного дерева: " << endl;
pr_obh(Root);
cout << endl;


return 0;
}