Лабораторная работа N 9

Работа с иерархическими структурами (бинарные деревья)

Цель работы: Получение навыка работы с иерархическими структурами.

 

Домашнее задание

1.1. Тщательно изучите листинг программ №1. Нарисуйте блок-схему функции iTakeOut.

1.2. Составьте произвольный список из учеников вашей группы с вашей фамилией в начале списка. Нарисуйте дерево, использую составленный список.

 

Лабораторное задание

2.1. Наберите программу №1 (комментарии можно не набирать).

#include "stdafx.h"

#include <stdlib.h>

# include <string.h>

# include <stdio.h>

# include <malloc.h>

# include <conio.h>

 

 

# define STAFF struct sStaffType

STAFF // Учебно-вспомогательный персонал

{

int iYearsOfService; // Время работы (лет)

float fHourlyWage; // Почасовая оплата

};

# define STUDENT struct sStudentType

STUDENT

{

float fGradePtAverage; // Средний рейтинг

int iLevel; // Год обучения

};

# define PROFESSOR struct sProfType

PROFESSOR

{

int iDepartmentNumber; // Номер кафедры

float fAnnualSalary; // Годовая зарплата

};

# define NODE_TYPE enum eNodeType

typedef NODE_TYPE {student, professor, staff};

# define TREE struct sTree

TREE

{

char sLastName[15]; // Фамилия

char sFirstName[15]; // Имя

int iAge; // Возраст

TREE *Left, *Right; // Указатели на левый и правый листья (ветви)

NODE_TYPE tag; // описатель типа узла - студент или профессор или УВП

union

{

STUDENT student;

PROFESSOR professor;

STAFF staff;

} uNodeTag; // Обьединение, содержащее информацию по

}; // студенту или сотруднику университета

extern void Insert(TREE **root, TREE *item); // Вставить в дерево новый элемент item

extern void Display(TREE *root); // Показать содержимое дерева

extern int iIsPresent(TREE *root, TREE *item); // Содержится ли информация item в дереве?

extern int iTakeOut(TREE **root, TREE *item); // Удалить элемент item из дерева

extern void Destroy(TREE *root); // Уничтожить дерево

static TREE* CreateNode(TREE* item) // Создать элемент item

{

TREE* node;

node = (TREE*) malloc(sizeof(TREE));

*node = *item;

return node;

}

void Destroy(TREE* root) // Уничтожить дерево

{

if (root) // Обратите особое внимание на рекурсивную работу этой функции

{

Destroy(root->Left);

Destroy(root->Right);

free(root); // Освободить память, которая была выделена для узла дерева

}

root = 0;

}

int iTakeOut(TREE** root, TREE* item) // Удалить элемент item из дерева

{

TREE *previous = 0, // Предыдущий узел дерева

*present = *root, // Текущий узел дерева

*replace, // Вспомогательные узлы,

*s, // используемые для перемещения элементов

*parent; // дерева после удаления найденного узла

int iFound = 0;

while (present && !iFound) // Пока не будет найден элемент item

{

if(strcmp(item->sLastName, present->sLastName) == 0)

iFound = 1; // Информация по человеку с таким именем и фамилией есть в дереве

else

{

previous = present;

// Если ASCII представление фамилии из item меньше ASCII кода фамилии

// из текущего узла дерева (present), то перейти к просмотру левого

// узла (листа) относительно present, иначе - правого

if(strcmp(item->sLastName, present->sLastName) < 0)

present = present->Left;

else

present = present->Right;

}

}

if (iFound) // если item присутствует в дереве

{

if (present->Left == 0) // Если найденный элемент не имеет ветви слева

replace = present->Right;

else

{

if (present->Right == 0) // Если найденный элемент не имеет ветви справа

replace = present->Left;

else // Если удаляемый элемент имеет и левую и правую ветвь (листья)

{

parent = present;

replace = present->Right;

s = replace->Left;

// Теперь необходимо подвинуть все элементы ветви, чтобы избежать разрыва

// дерева при удалении найденного элемента (present)

while (s != 0) // Пока не будет достигнут крайний левый лист в рассматриваемой ветви

{ // Спускаемся вниз дерева по левой ветви

parent = replace;

replace = s;

s = replace->Left;

}

if (parent != present) // Есть левая ветвь от правой ветви от найденного элемента

{

parent->Left = replace->Right; // Правую подветвь переносимого элемента сделать левой подветвью предыдущего

replace->Right = present->Right; // Переместить элемент на место удаляемого

}

replace->Left = present->Left; // Переместить левую ветвь

}

}

if (previous == 0) // Элемент лежит сразу же за корнем дерева

*root = replace;

else

if(present == previous->Left) // Предыдущий спуск был по левой ветви

previous->Left = replace;

else // Предыдущий спуск был по правой ветви

previous->Right = replace;

free (present); // Удалить найденный элемент

}

return iFound; // 1 - если элемент был удален, 0 - если такого элемента в дереве не было

}

void Insert(TREE **root, TREE *item ) // Вставить элемент item в дерево

{

TREE *parent = 0,

// current (текущий) указатель на дерево указывает на его вершину (корень)

*current = *root;

TREE *new_node; // Новый узел

int iFound = 0;

while (current && !iFound) // Пока элемент item не найден

{

if (strcmp(item->sLastName, current->sLastName) == 0) iFound = 1;

else

{

parent = current;

if (strcmp(item->sLastName, current->sLastName) < 0)

current = current->Left; // перемещаться по левой ветви

else

current = current->Right; // перемещаться по правой ветви

}

}

if (iFound == 0)

{

if (parent == 0) // в дереве нет еще элементов - создаем его

{

*root = CreateNode(item); // создать узел

(*root)->Left = (*root)->Right = 0;

}

else // Вставить узел в дерево

{

new_node = CreateNode(item);

new_node->Left = new_node->Right = 0;

if (strcmp(item->sLastName, parent->sLastName) < 0)

parent->Left = new_node;

else

parent->Right = new_node;

}

}

}

void Display(TREE *root) // Показать дерево

{

if(root) // Обратите внимание также на рекурсивный обход дерева

{

Display(root->Left);// показать вначале левую ветвь (лист) дерева

printf("\n%s, %s", root->sLastName, root->sFirstName);

printf("\n Old - %d", root->iAge);

switch(root->tag) // Обратите внимание на использование в

{ // конструкции switch элементов перечислимого

case student: // (enum) типа

printf("\nReyting: %.2f",

root->uNodeTag.student.fGradePtAverage);

printf("\nKurs: %d\n", root->uNodeTag.student.iLevel);

break;

case professor:

printf("\nNumber of kafedra: %d",

root->uNodeTag.professor.iDepartmentNumber);

printf("\nYear selary: %.2f\n",

root->uNodeTag.professor.fAnnualSalary);

break;

case staff:

printf("\n Time of work(year): %d",

root->uNodeTag.staff.iYearsOfService);

printf("\nSelary of oure: %.2f\n",

root->uNodeTag.staff.fHourlyWage);

}

Display(root->Right); // Вывести информацию о содержимом правого узла

}

}

int iIsPresent(TREE *root, TREE *item)

{

TREE *current = root; // Устанавливаем указатель на вершину (корень) дерева

int iFound = 0;

while (current && !iFound) // пока элемент item не найден

{

if (strcmp(item->sLastName, current->sLastName) == 0) iFound = 1;

else

{ // Если ASCII код фамилии из item меньше ASCII кода из текущего узла (current)

if (strcmp(item->sLastName, current->sLastName) < 0)

current = current->Left; // то перейти к рассмотрению левого узла

else

current = current->Right; // иначе перейти к рассмотрению правого узла

}

}

return iFound; // Если не найден - 0, если найден - 1

}

TREE* sMyTree;

void main()

{

// Выделяем память на три узла дерева

TREE* item1 = (TREE*) malloc(sizeof(TREE));

TREE* item2 = (TREE*) malloc(sizeof(TREE));

TREE* item3 = (TREE*) malloc(sizeof(TREE));

// Инициализация первого элемента

strcpy(item1->sLastName, "Fyfikov");

strcpy(item1->sFirstName, "Ziberman");

item1->iAge = 32;

item1->tag = staff;

item1->uNodeTag.staff.iYearsOfService = 3;

item1->uNodeTag.staff.fHourlyWage = 5.25;

// Вставить элемент в дерево

Insert(&sMyTree, item1);

strcpy(item2->sLastName, "Vibigalo");

strcpy(item2->sFirstName, "Ivanov");

item2->iAge = 56;

item2->tag = professor;

item2->uNodeTag.professor.iDepartmentNumber = 7;

item2->uNodeTag.professor.fAnnualSalary = 15321.0;

Insert(&sMyTree, item2);

strcpy(item3->sLastName, "Sidorov");

strcpy(item3->sFirstName, "Antonov");

item3->iAge = 18;

item3->tag = student;

item3->uNodeTag.student.iLevel = 1;

item3->uNodeTag.student.fGradePtAverage = 0.75;

Insert(&sMyTree, item3);

Display(sMyTree); // Показать дерево

getchar();

if(iIsPresent(sMyTree, item2))

printf("\n 2- element out of tree\n");

else

printf("\n element out of tree\n");

getchar();

iTakeOut(&sMyTree, item1);

Display(sMyTree);

getchar();

iTakeOut(&sMyTree, item2);

Display(sMyTree);

getchar();

iTakeOut(&sMyTree, item3);

Display(sMyTree);

getchar();

printf("\n");

}

 

2.3. Запустите программу и проанализируйте результаты ее работы.

2.4. Измените программу таким образом, чтобы в дерево можно было бы вставлять информацию о студентах колледжа.

2.5 Измените программу так, чтобы в дерево можно было вставлять однофамильцев.

2.6 Модифицируйте класс sTree так, чтобы его объекты можно было вставлять в контейнер set библиотеки STL. Продемонстрируйте примеры вставки.

 

Содержание отчета

1. Титульный лист отчета должен содержать название, цель лабораторной работы, группу и фамилию студента, выполнившего её, и фамилию преподавателя, проверившего отчет.
2. Выполненное домашнее задание.
3. Тексты программ, написанных при выполнении 2.4, 2.5 и 2.6 пунктов лабораторного задания.

 

 

Вопросы к защите

3.1. Использую библиотеку STL, напишите класс вектор целых чисел.

3.2. Использую библиотеку STL, напишите класс очередь вещественных чисел.

3.3. Использую библиотеку STL, напишите класс список символьных переменных.

3.4. Использую библиотеку STL, напишите класс множество символьных переменных.

3.5. Использую библиотеку STL, напишите класс мультимножество символьных переменных.

3.6. Нарисуйте пример двоичного дерева поиска и покажите, как изменяется его структура при удалении из него элемента.

3.7. Нарисуйте пример двоичного дерева поиска и покажите, как изменяется его структура при вставке в него элемента.

3.8. Напишите функцию сохранения и восстановления дерева из файла.

3.9. Напишите функцию, позволяющую найти и отредактировать содержимое любого узла в дереве.

3.10. Напишите функцию, выводящую на экран информацию о узлах дерева удовлетворяющих заданному с клавиатуры пользователем диапазону (например, вывести все узлы начинающиеся с букв от В до Е).

3.11. Модифицируйте программу так, чтобы фамилия и имя в узле дерева заносились не в статический, а динамический массив памяти.