RFpro.ru: Программирование на C / C++
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты по данной тематике
/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++
Консультация # 186030: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: Помогите, пожалуйста, написать программу, работающую с деревом, вариант задания номер 3: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Дата отправки: 15.05.2012, 14:44 Консультирует Лысков Игорь Витальевич (Старший модератор): Здравствуйте, Барс Иван! Код : #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <malloc.h>
//первый элемент nocolor нужен для поиска родителя-корня
typedef enum { nocolor, red, green, blue, orange, yellow, indigo, violet, brown, white, black } node_t;
struct Node
{
node_t Color; //цвет
Node *Son; //указатель на первого сына
Node *Brother; //указатель на слеующего брата
};
Node * Root = NULL; //корень дерева
void AddElement();
void DelElement();
void OutTree();
void CalcMinDepth();
void Exit();
int GetNum();
node_t GetColor(bool);
//преобразование enum в строку
char* GetColorString(node_t color)
{
switch (color)
{
case nocolor:
return "корень или братья корня";
case red:
return "красный";
case green:
return "зеленый";
case blue:
return "голубой";
case orange:
return "оранжевый";
case yellow:
return "желтый";
case indigo:
return "индиго";
case violet:
return "фиолетовый";
case brown:
return "коричневый";
case white:
return "белый";
case black:
return "черный";
default:
return "неизвестный"; //на всякий случай
}
}
char *mesMain[] = //сообщения меню
{
"Включить новый элемент",
"Удалить элемент",
"Вывести дерево",
"Найти лист с минимальной глубиной",
"Выход"
};
//количество пунктов меню
int MesMainCount = sizeof( mesMain ) / sizeof( mesMain[0] );
//функции отработки пунктов меню
void ( *funcMain[] )() = {AddElement, DelElement, OutTree, CalcMinDepth, Exit};
//создание нового узла, возвращает указатель на этот элемент
Node* CreateNode(node_t Color)
{
Node * node = (Node*)malloc(sizeof(Node));
node->Color = Color; //цвет
node->Son = NULL; //без детей
node->Brother = NULL; //и брата нет
return node;
}
//рекурентный поиск узла с аданным цветом
//Current - первый в списке братьев
//Color - искомый цвет
//pParent - адрес указателя на родителя, в начале должен быть NULL
// используется при удалении узла
//pBrother- арес указателя на предыдущего брата, там в начале должен быть NULL
// используется при удалении узла
Node* Find(Node* Current, node_t Color, Node** pParent, Node** pBrother)
{
Node *node, *nodeSon;
//сначала сравним поле для братьев, начиная с заданного
for (node=Current; node; node=node->Brother)
{
//сравниваем цвет
if (node->Color == Color)
{
return node; //нашли, вернем указатель на узел
}
*pParent = NULL; //NULL для всех последующих братьев
*pBrother = node; //сохраним указатель на предыдущего брата
}
//идем на седующий уровень - по сыновьям всех братьев
for (node=Current; node; node=node->Brother)
{
//зададим родителя для первого сына
*pParent = node;
//ищем среди всех потомков текущего брата
if (NULL != (nodeSon=Find(node->Son, Color, pParent, pBrother)))
//если наши, то возвращаем выше указатель на узел
return nodeSon;
}
return NULL; //не найдено
}
//поиск последнего в списке братьев
Node* Last(Node * node)
{
for (; node->Brother; node=node->Brother);
return node;
}
//добавение узла с указанием цвета родителя(или 0 для корня и его братьев) и вставяемого узла
int AddNode (node_t ColorParent, node_t Color)
{
Node *node, *nodeLast, *nodeNew;
Node *Parent = NULL;
Node *Brother = NULL;
//что-то есть вообще?
if (Root == NULL) //корня еще пока нет
{
if (ColorParent == nocolor) //проверим правильность задания цвета родителя! Для корня 0!
{
Root = CreateNode(Color);//создаем корень
return 1; //внесли
}
else
return 2; //неправильные данные - родитель не найден!
}
else if (ColorParent == nocolor) //родитель - 0 уровень, т.е. братья корня?
{
if (NULL == Find(Root, Color, &Parent, &Brother)) //есть ли уже узел с цветом color?
{
nodeNew = CreateNode(Color); //создаем узел
nodeLast = Last(Root); //ищем последнего брата
nodeLast->Brother = nodeNew; //добавляем нового в цепочку братьев
return 1; //внесли
}
else
return 0; //дубликат цвета
} //родитель - не корень
//ищем родителя
else if (NULL != (node = Find(Root, ColorParent, &Parent, &Brother)))
{
//есть ли уже узел с цветом color?
Parent = NULL; //начинаем искать с начала
Brother = NULL;
if (NULL == Find(Root, Color, &Parent, &Brother))
{ //цвет не найден
//добавяем
nodeNew = CreateNode(Color); //создаем узел
if (NULL == node->Son) //у родителя уже есть дети?
node->Son = nodeNew; //нет - будем первым сыном
else
{ //есть - будем младшим сыном
nodeLast = Last(node->Son); //ищем самого последнего
nodeLast->Brother = nodeNew;//и добавляем новый элемент в конец цепочки братьев
}
return 1; //внесли
}
else
return 0; //дубликат цвета
}
else
return 2; //родитель не найден!
}
//рекурентное удаление узла вместе со всеми потомками
void DeleteAllSons(Node *nodeParent)
{
Node *node,*nodeBrother;
//по всем сыновьям
for(node=nodeParent->Son; node; node=nodeBrother)
{
//запомним следуюещго брата
nodeBrother = node->Brother;
//удаляем текущего сына со всего его потомками
DeleteAllSons(node);
}
//удаляем сам узел
free (nodeParent);
}
//удаление узла с заанным цветом
bool DelNode(node_t Color)
{
Node *node, *nodeBrother;
Node *Parent = NULL;
Node *Brother = NULL;
//ищем узел
if (NULL != (node=Find(Root, Color, &Parent, &Brother)))
{ //нашли!
nodeBrother = node->Brother;//запомним следующего брата
DeleteAllSons(node); //удаляем узел со всеми потомками
//подправим ссылку
if (node == Root) //узел - корень?
Root = nodeBrother; //корнем будет следующий брат
else if (Parent != NULL) //узел - первый из братьев?
Parent->Son = nodeBrother; //делаем первым сыном брата
else
Brother->Brother = nodeBrother; //сеующий брат будет идти за предыдущим брат
return true; //уалили
}
else
return false; //узел не найден
}
//удаение всего дерева (в конце)
void DelAll(void)
{
while(Root)
DelNode(Root->Color); //удаяем всех братьев корня
}
//рекурентный структуированный вывод дерева, начиная с узла node
//уровень узла задается параметром level
void PrintTree(Node* node, int level)
{
char str[80]; //для формирования первых пробелов
int i;
for (; node; node=node->Brother) //по братьям
{
for (i=0; i<level; i++) //сформируем level пробелов
str[i] = ' '; //можно по-разному, я сделал "в лоб"
str[i] = 0; //закрываем строку нулем
//выводим цвет с пробелами
printf("%s%s\n", str, GetColorString(node->Color));
PrintTree(node->Son, level+2); //выводим потомков, на каждый уровень по 2 пробела
}
}
//рекурентный поиск узла с минимальной глубиной
//nodeParent - началный узел
//iDepth - глубина до текущего уровня (в начале 0)
//piDepthMin - адрес переменной - минимальной глубины
//nodeMin - адрес указателя на узел с минимальной глубиной
void SearchLeafs(Node *nodeParent, int iDepth, int *piDepthMin, Node **nodeMin)
{
Node *node;
//если NULL, то начинаем с корня, иначе с первого сына
node = (nodeParent == NULL) ? Root : nodeParent->Son;
iDepth++; //глубина текущего уровня
for (; node; node=node->Brother) //по братьям
{
if (node->Son == NULL) //узел - лист (без сыновей)?
{ //в начале просто сохраняем первого
//для всех остальных - ищем минимального
if ((*piDepthMin == NULL)||(*piDepthMin > iDepth))
{
*piDepthMin = iDepth; //сохраняем глубину
*nodeMin = node; //и узел
}
}
else //имеет потомков - задаем поиск по потомкам
SearchLeafs(node, iDepth, piDepthMin, nodeMin);
}
}
//добавить элемент
void AddElement()
{
node_t parent, Color;
printf("Введите цвет родителя\n");
parent = GetColor(true); //вводим цвет родителя, с возможностью ввода корня
printf("Введите цвет элемента\n");
Color = GetColor(false); //вводим цвет нового элемента
switch (AddNode(parent, Color)) //пытаемся добавить
{
case 1:
printf("Элемент добавлен\n");
break;
case 0:
printf("Элемент c данным цветом уже есть\n");
break;
case 2:
printf("Родитель не найден\n");
}
}
//удалить элемент
void DelElement()
{
node_t Color;
printf("Введите цвет элемента\n");
Color = GetColor(false); //вводим цвет
if (DelNode(Color)) //пытаемся удалить
printf("Элемент удален\n");
else
printf("Элемент c данным цветом не найден\n");
}
//вывод дерева
void OutTree()
{
PrintTree(Root, 0); //начинаем с корня и уровня 0
}
//поиск узла с минималной глубиной
void CalcMinDepth()
{
int iDepthMin = 0;
Node *nodeMin = NULL;
SearchLeafs(NULL, 0, &iDepthMin, &nodeMin); //ищем
if (iDepthMin)
printf("Минимальная глубина = %d, Цвет = %s\n", iDepthMin, GetColorString(nodeMin->Color));
else
printf("Дерево пустое\n");
}
void Exit() //выход
{
DelAll(); //освобождаем память
}
bool IsNum(char *str) //проверка строки на число
{
for(;isdigit(*str);str++);
return (*str == 0);
}
//ввод числа
int GetNum()
{
char str[80];
while(1)
{
gets(str); //введем строку
if (IsNum(str)) //проверим на корректность
return(atoi(str)); //возвращаем число
printf("Введите число!\n");
}
//сюда не попадем, но
return -1; //подпрограмма должна что-то возвращать
}
//ввод цвета с отображением всех цветов
//Parent = true для выбора родителя - корня
node_t GetColor(bool Parent)
{
node_t iColor;
while(1)
{
//выведем цведа в две строки для выбора
for(iColor=red; iColor<yellow; iColor=(node_t)((int)iColor+1))
printf("%d.%s,\t", iColor, GetColorString(iColor));
printf("%d.%s\n", iColor, GetColorString(iColor));
for(iColor=indigo; iColor<black; iColor=(node_t)((int)iColor+1))
printf("%d.%s,\t", iColor, GetColorString(iColor));
printf("%d.%s\n", iColor, GetColorString(iColor));
//выбор корня нужен?
if (Parent)
printf("%d.%s\n", nocolor, GetColorString(nocolor));
printf("Ваш выбор: ");
iColor = (node_t)GetNum();
if (Parent)
{
if ((iColor >= nocolor) || (iColor <= black))
return(iColor);
}
else if((iColor >= red) || (iColor <= black))
return(iColor);
else
printf("Введите число из диапозона!\n");
}
return nocolor; //сюда не попадем никогда
}
//показ меню с вводом номера строки
int ViewMenu(char** mes, int max)
{
int ret;
do
{
//меню
for ( int i = 0; i < max; i++ )
printf("%d. %s\n", i+1, mes[i]);
printf("Ваш выбор: ");
//вводим число
ret = GetNum();
}
//проверим на допустимость
while ( ret < 1 || ret > max );
//вернем номер строки
return ret;
}
int main()
{
int ret;
//чтобы писалось по-русски
system("chcp 1251 >> nul");
do
{
ret = ViewMenu(mesMain, MesMainCount); //выводим меню, вводим номер строки
funcMain[ret-1](); //отрабатываем пункт меню
printf("--------------------------------\n");
if (ret == MesMainCount) //последняя - выход
break;
}while ( ret );
return 0;
}
Оценить выпуск | Задать вопрос экспертам
главная страница
|
стать участником
|
получить консультацию
© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Версия системы: 2011.6.36 от 26.01.2012 |
Очень прошу помощи! Заранее спасибо, с уважением,...
| В избранное | ||
