RFpro.ru: Программирование на C / C++
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты по данной тематике
/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++
Консультация # 186094: Уважаемые эксперты! Прошу вас ответить на следующий вопрос и прокоментировать код: Написать программу для работы по запросам оператором с упорядочнной таблицей, реализованной в виде двоичного дерева поиска. Ключ - целое число. Информация - строка произвольной длины. Узел дерева содержит ключ, указатели на правое и левое поддеревья и указатель... Уважаемые эксперты! Прошу вас ответить на следующий вопрос и прокоментировать код:
Дата отправки: 18.05.2012, 22:53 Консультирует Александр Чекменёв {vanger} (Профессор): Здравствуйте, ШмонинЕА! Код :
// майкросовтовский компилятор без этой строчки выдаёт предупреждения на стандартные POSIX-овские функции вида scanf и т.п.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
// тип "узел"
typedef
struct _tagNode
{
int key;
char * data;
_tagNode * left;
_tagNode * right;
}
Node;
// создаёт пустой узел
Node * assignNode()
{
Node * node;
node = (Node *)malloc( sizeof(Node) );
//node->key = 0;
node->data = 0;
node->left = 0;
node->right = 0;
return node;
}
// освобождает память ноды и всех детей
void freeNode( Node * node )
{
if( node == 0 ) return;
freeNode( node->left );
freeNode( node->right );
if( node->data != 0 ) free( node->data );
free( node );
}
// освобождает память детей, а саму зануляет
void nullNode( Node * node )
{
if( node == 0 ) return;
freeNode( node->left );
freeNode( node->right );
if( node->data != 0 ) free( node->data );
//node->key = 0;
node->data = 0;
node->left = 0;
node->right = 0;
}
void copyNode( const Node * from, Node * to )
{
to->key = from->key;
to->data = from->data;
to->left = from->left;
to->right = from->right;
}
// добавление элемента
void insert( Node * root, int key, const char * data )
{
// если дерево пустое
if( root->data == 0 )
{
// без затей заполняем поля
// выделяем память(+1 - символ завершения строки)
root->data = (char *)malloc( (strlen(data) + 1) * sizeof(char) );
root->key = key;
strcpy( root->data, data );
}
else // если нет
{
// рекурсивно добавляем в правое или левое поддерево, в зависимости от ключа
int cmp = (key == root->key ? 0 : (key > root->key ? 1 : -1));//strcmp( key, root->key );
if( cmp != 0 )
{
Node * child = 0;
if( cmp > 0 )
child = root->right;
else
child = root->left;
// если узел пустой
if( child == 0 )
{
// создаём его
child = assignNode();
// и назначаем правым
if( cmp > 0 )
root->right = child;
// или левым ребёнком
else
root->left = child;
}
insert( child, key, data );
}
else
{
printf( "Ошибка: элемент с ключом %i уже существует\n", key );
}
}
}
// удаление узла
void remove( Node * root, int key )
{
// если дерево пустое
if( root == 0 ? true : root->data == 0 ) return;
int cmp = (key == root->key ? 0 : (key > root->key ? 1 : -1));//strcmp( key, root->key );
if( cmp > 0 )
remove( root->right, key );
else if( cmp < 0 )
remove( root->left, key );
else
{
// если обоих детей нет
if( root->left == 0 && root->right == 0 )
{
// зануляем текущий узел
nullNode( root );
}
// если есть только левый
else if( root->left != 0 && root->right == 0 )
{
Node * child = root->left;
copyNode( child, root );
freeNode( child );
}
// если есть только правый
else if( root->left == 0 && root->right != 0 )
{
Node * child = root->right;
copyNode( child, root );
freeNode( child );
}
// если же оба есть
else
{
// ищем в правом поддереве самый левый узел
Node * curNode = root->right;
Node * needNode = curNode;
while( curNode != 0 )
{
if( curNode->data != 0 )
needNode = curNode;
curNode = curNode->left;
}
// левый узел "самого левого узла" может оказаться пустым. освободим память
freeNode( curNode->left );
// копируем данные
root->key = curNode->key;
root->data = curNode->data;
// рекурсивно удаляем узел
remove( curNode, curNode->key );
}
}
}
// поиск элемента
Node * find( Node * root, int key )
{
// дерево пустое - ничего не нашли
if( root == 0 ? true : root->data == 0 ) return 0;
int cmp = (key == root->key ? 0 : (key > root->key ? 1 : -1));//strcmp( key, root->key );
if( cmp < 0 )
// рекурсивно ищем в левом поддереве
return find( root->left, key );
else if( cmp > 0 )
// в правом
return find( root->right, key );
// нашли!!!
return root;
}
void print_cool( Node * root, unsigned n = 0 )
{
// если дерево пустое - выводим символ пустого узла и всё
if( root == 0 ? true : root->key == 0 )
{
for( unsigned i = 0; i < n; ++i )
printf( " " );
printf( "-\n" );
return;
}
// выводим себя
for( unsigned i = 0; i < n; ++i )
printf( " " );
printf( "%s\n", root->data );
// рекурсивно выводим левое поддерево
print_cool( root->left, n + 1 );
// правое поддерево
print_cool( root->right, n + 1 );
}
// выводит элементы дерева, ключ которых превышает данный, в порядке убывания ключей
void print( Node * root )
{
// если дерево пустое - выводим символ пустого узла и всё
if( root == 0 ? true : root->data == 0 )
{
return;
}
// правое поддерево
print( root->right );
// выводим себя
printf( "%s\n", root->data );
// рекурсивно выводим левое поддерево
print( root->left );
}
int load( const char * fileName, Node * root )
{
FILE * file;
char str[64];
int i;
file = fopen( fileName, "r" );
if( 0 == file)
{
printf( "Не получилось открыть файл '%s'\n", fileName );
return 0;
}
while( 2 == fscanf( file, "%i%s", &i, str ) )
{
insert( root, i, str );
}
fclose( file );
return 1;
}
int main( int argc, char *argv[] )
{
// для нормального отображения кириллицы
setlocale( LC_ALL, "Russian" );
//load( "zzz.txt" );
// хотя бы корень надо создать руками
Node * root = assignNode();
// тестовое содержание дерева. не обязательно
insert( root, 2, "bbb" );
insert( root, 3, "ccc" );
insert( root, 1, "aaa" );
insert( root, 4, "ddd" );
insert( root, 5, "aaaa" );
// буферы для ввода
const int BUF_SIZE = 64;
char buf[BUF_SIZE];
char buf1[BUF_SIZE];
char buf2[BUF_SIZE];
int i;
// консольные команды
const char com_insert [] = "insert";
const char com_remove [] = "remove";
const char com_find [] = "find";
const char com_print [] = "print";
const char com_print_c [] = "print_cool";
const char com_load [] = "load";
const char com_help [] = "help";
const char com_exit [] = "exit";
printf( "Введите help для вывода списка команд\n" );
do
{
scanf( "%s", buf );
if( 0 == strcmp( buf, com_insert ) )
{
printf( "Введите ключ: " );
scanf( "%i", &i );
printf( "Введите данные: " );
scanf( "%s", buf2 );
insert( root, i, buf2 );
}
if( 0 == strcmp( buf, com_load ) )
{
printf( "Введите имя файла: " );
scanf( "%s", buf2 );
load( buf2, root );
}
else if( 0 == strcmp( buf, com_remove ) )
{
printf( "Введите ключ: " );
scanf( "%i", &i );
remove( root, i );
}
else if( 0 == strcmp( buf, com_find ) )
{
printf( "Введите ключ: " );
scanf( "%i", &i );
Node * node = find( root, i );
if( node == 0 )
printf( "Таких элементов не найдено\n" );
else
printf( "Данные: %s\n", node->data );
}
else if( 0 == strcmp( buf, com_print ) )
{
print( root );
}
else if( 0 == strcmp( buf, com_print_c ) )
{
print_cool( root );
}
else if( 0 == strcmp( buf, com_help ) )
{
printf( "Команды:\n" );
printf( "%s - добавление элемента\n", com_insert );
printf( "%s - удаление элемента\n", com_remove );
printf( "%s - поиск элемента с данным ключом\n", com_find );
printf( "%s - вывод элементов в порядке убывания улючей\n", com_print );
printf( "%s - вывод дерева в читаемом виде\n", com_print_c );
printf( "%s - загрузка из файла\n", com_load );
printf( "%s - выход из программы\n", com_exit );
}
}
while( 0 != strcmp(buf, com_exit) );
// освобождаем память. хоть её всё равно ОС освободит...
freeNode( root );
return 0;
}
Оценить выпуск | Задать вопрос экспертам
главная страница
|
стать участником
|
получить консультацию
© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Версия системы: 2011.6.36 от 26.01.2012 |
| В избранное | ||
