Лабораторная работа №1 Вариант №21

2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Лабораторная работа №1

по дисциплине

«Структуры и алгоритмы»

на тему:

«Деревья»

Студент

^подпись, дата

^фамилия, инициалы

Группа

Принял

Журавлева М.Г.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2010

1. Задание

№ варианта

Ключ

Удаляемый узел

Распределение

Реализация

Степень дерева

Метод обхода

int

char[]

заменяется самым левым дочерним узлом

заменяется самым правым дочерним узлом

равномерное

нормальное

связный список дочерних узлов

список дочерних узлов, два массива

список дочерних узлов, массив структур, 3 поля

указатели

4

5

6

7

прямой

обратный

симметричный

21

+

+

+

+

+

+

2. Листинг программы

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <locale.h>

#include <windows.h>

int root(int **mas1,int **mas2)

{

if(mas1[0][0]!=-1)

{

printf("\nКорень - узел с ключом: %d\n",mas1[0][0]);

return mas1[0][0];

}

else

{

printf("\nКорень не найден.\n");

return -1;

}

}

void get_label(int **mas1,int **mas2)

{

}

void set_label(int **mas1,int **mas2)

{

}

int search(int **mas1,int **mas2,int n)

{

int p=0,k,key=-1;

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

if(mas1[i][0]==n)

{

p=1;

k=i;

break;

}

if(p!=1)

printf("\nУзел не найден");

else

{

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

if(mas2[i][0]==k)

for(int j=0;j<31;j++)

if(mas1[j][1]==i)

key=mas1[j][0];

if(key==-1)

{

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

if(mas2[i][0]==k)

for(int j=0;j<31;j++)

if(mas2[j][1]==i)

for(int x=0;x<31;x++)

if(mas1[x][1]==j)

key=mas1[x][0];

}

if(key!=-1)

printf("\nИскомый узел расположен за узлом с ключом %d",key);

else

printf("\nДанный узел является корнем");

}

return key;

}

void add(int **mas1,int **mas2,int n,int m)

{

int p=-1, k, i;

if(mas1[0][0]!=-1)

{

for(i=0;i<31;i++)

if(mas1[i][0]==n)

p=i;

if(p>-1)

{

if(mas1[p][1]==-1)

{

i=k=0;

while(mas2[i][0]!=-1)

i++;

while(mas1[k][0]!=-1)

k++;

mas1[p][1]=i;

mas2[i][0]=k;

mas1[k][0]=m;

}

else if(mas2[mas1[p][1]][1]==-1)

{

i=k=0;

while(mas2[i][0]!=-1)

i++;

while(mas1[k][0]!=-1)

k++;

mas2[mas1[p][1]][1]=i;

mas2[i][0]=k;

mas1[k][0]=m;

}

else

printf("\nПосле данного узла уже имеется 2 узла, больше добавить невозможно...");

}

else

printf("\nТакого узла не существует");

}

else

{

mas1[0][0]=m;

printf("Добавлен корень с ключом %d",m);

}

}

int parent(int **mas1,int **mas2,int n)

{

int key=-1,p=0;

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

if(mas1[i][0]==n)

{

p=1;

for(int j=0;j<31;j++)

if(mas2[j][0]==i)

for(int k=0;k<31;k++)

if(mas1[k][1]==j)

key=mas1[k][0];

}

if(key==-1)

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

if(mas1[i][0]==n)

for(int j=0;j<31;j++)

if(mas2[j][0]==i)

for(int k=0;k<31;k++)

if(mas2[k][1]==j)

for(int t=0;t<31;t++)

if(mas1[t][1]==k)

key=mas1[t][0];

if((p==1)&&(key!=-1))

printf("\nРодитель - узел с ключом %d",key);

else if((p==1)&&(key==-1))

printf("\nРодители отсутствуют - узел является корнем");

else

printf("\nУзел не найден");

return key;

}

int left_most_child(int **mas1,int **mas2,int n)

{

int key=-1;

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

if((mas1[i][0]==n)&&(mas1[i][1]!=-1))

key=mas1[mas2[mas1[i][1]][0]][0];

if(key!=-1)

printf("\nЛевый дочерний узел - узел с ключом %d",key);

else

printf("\nУ узла c ключом %d не существует дочерних узлов.",n);

return key;

}

int right_subling(int **mas1,int **mas2,int n)

{

int key=-1;

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

if(mas1[i][0]==n)

for(int j=0;j<31;j++)

if((mas2[j][0]==i)&&(mas2[j][1]!=-1))

key=mas1[mas2[mas2[j][1]][0]][0];

if(key!=-1)

printf("\nСосед справа - узел с ключом %d",key);

else

printf("\n У узла c ключом %d не существует соседа справа.",n);

return key;

}

void make_null(int **mas1,int **mas2)

{

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

for(int j=0;j<2;j++)

mas1[i][j]=mas2[i][j]=-1;

}

void del(int **mas1,int **mas2,int n)

{

int key=-1,p=0,k,b,d,m[31][2],i,j,l,m1,m2;

for(l=0;l<31;l++)

m[l][0]=m[l][1]=-1;

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

if(mas1[i][0]==n)

for(int j=0;j<31;j++)

if(mas2[j][0]==i)

{

p=left_most_child(mas1,mas2,n);

for(int t=0;t<31;t++)

if(mas1[t][0]==p)

mas2[j][0]=t;

}

p=right_subling(mas1,mas2,left_most_child(mas1,mas2,n));

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

if(mas1[i][0]==p)

k=d=i;

i=j=0;

if(mas1[k][1]!=-1)

m[j][1]=mas1[k][1];

while(k!=31)

{

for(l=0;l<31;l++)

if(m[l][1]!=-1)

{

m2=m[l][1];

if(mas2[m2][1]!=-1)

{

m[j+1][1]=mas2[m2][1];

j++;

}

if(mas1[m2][1]!=-1)

{

m[j+1][1]=mas1[m2][1];

j++;

}

}

k++;

}

for(l=0;l<31;l++)

{

if(m[l][1]!=-1)

m[l][0]=mas2[m[l][1]][0];

printf("\n%d\t%d\t**%d",m[l][0],m[l][1],l);

}

for(l=0;l<31;l++)

if(mas2[l][0]==d)

mas2[l][0]=mas2[l][1]=-1;

mas1[d][0]=mas1[d][1]=-1;

for(l=0;l<31;l++)

if(mas1[l][0]==n)

{

if(mas1[l][1]!=0)

mas2[mas1[l][1]][0]=mas2[mas1[l][1]][1]=-1;

mas1[l][0]=mas1[l][1]=-1;

}

for(l=0;l<31;l++)

{

if(m[l][0]!=-1)

mas1[m[l][0]][0]=mas1[m[l][0]][1]=-1;

if(m[l][1]!=-1)

mas2[m[l][1]][0]=mas2[m[l][1]][1]=-1;

}

}

void main()

{

setlocale(LC_ALL,"Rus");

int **mas1, **mas2, k=1,n,m,h;

mas1=(int**)malloc(31*sizeof(int*));

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

mas1[i]=(int*)malloc(2*sizeof(int));

mas2=(int**)malloc(31*sizeof(int*));

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

mas2[i]=(int*)malloc(2*sizeof(int));

make_null(mas1,mas2);

//mas1[0][0]=7;

do

{

//system("cls");

printf("\nЧто вы хотите сдeлaть?\n");

printf("1. Вернуть корень дерева\n");

//printf("2. Возвратить ключ узла n\n");

//printf("3. Установить ключ m узла n\n");

printf("4. Поиск узла с ключом m\n");

printf("5. Добавить узел после узла n с ключом m\n");

printf("6. Удалить узел с ключом m\n");

printf("7. Возвратить родителя узла n\n");

printf("8. Возвратить самый левый узел узла с ключом n\n");

printf("9. Возвратить правого соседа узла c ключом n\n");

printf("10. Очиcтить дерево\n");

printf("0. Выход\n");

scanf("%d",&h);

switch(h){

case 1:

root(mas1,mas2);

break;

case 2:

get_label(mas1,mas2);

break;

case 3:

set_label(mas1,mas2);

break;

case 4:

printf("\nВведите ключ искомого узла: ");

scanf("%d",&n);

search(mas1,mas2,n);

break;

case 5:

printf("\nВведите ключ узла, после которого хотите добавить узел: ");

scanf("%d",&n);

do

{

k=0;

printf("\nВведите ключ добавляемого узла: ");

scanf("%d",&m);

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

if(mas1[i][0]==m)

k=1;

if(k==1)

printf("\nУзел с таким ключом уже существует, повторите ввод: ");

}while(k==1);

add(mas1,mas2,n,m);

break;

case 6:

printf("\nВведите ключ узла, который хотите удалить: ");

scanf("%d",&n);

del(mas1,mas2,n);

break;

case 7:

printf("\nВведите ключ узла, родителя которого хотите узнать: ");

scanf("%d",&n);

parent(mas1,mas2,n);

break;

case 8:

printf("\nВведите ключ узла, левого потомка которого хотите узнать: ");

scanf("%d",&n);

left_most_child(mas1,mas2,n);

break;

case 9:

printf("\nВведите ключ узла, правого соседа которого хотите узнать: ");

scanf("%d",&n);

right_subling(mas1,mas2,n);

break;

case 10:

make_null(mas1,mas2);

break;

}

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

printf("\n%d\t%d\t|||\t%d\t%d",mas1[i][0],mas1[i][1],mas2[i][0],mas2[i][1]);

}while(h!=0);

}

3. Контрольный пример

4. Блок-схема

5. Вывод

При выполнении данной лабораторной работы я получил навыки программирования деревьев.

6. Список использованной литературы

1. Шилдт Г. Искусство программирования на C++. БХВ.2005

2. Шилдт Г. C++ Руководство для начинающих. Вильямс.2005

3. Страуструп Б. Язык программирования С++. Специальное издание, 3-изд. Бином.2004