Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на C / C++

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.428 RSS
←   Июль 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/C
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

5.428 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на C / C++


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

_Ayl_
Статус: 8-й класс
Рейтинг: 621
∙ повысить рейтинг >> 		Micren
Статус: Практикант
Рейтинг: 394
∙ повысить рейтинг >> 		Stealthm
Статус: 4-й класс
Рейтинг: 148
∙ повысить рейтинг >>

∙ / КОМПЬЮТЕРЫ И ПО / Языки программирования / C/C++

Выпуск № 1351 от 07.07.2009, 00:35
Администратор рассылки: Dr_Andrew, Модератор
В рассылке: подписчиков - 630, экспертов - 150
В номере: вопросов - 1, ответов - 1

Нам очень важно Ваше мнение об этом выпуске рассылки. Вы можете оценить этот выпуск по пятибалльной шкале, пройдя по ссылке:
оценить выпуск >>

Вопрос № 170069: Здравствуйте. дано дерево, поля содержат текст, количество потомков не превышает 4, необходимо обойти все вершины и сравнить с исвестной строкой текста. кто подскажет примером как организовать поиск?...

Вопрос № 170069:

Здравствуйте.
дано дерево, поля содержат текст, количество потомков не превышает 4, необходимо обойти все вершины и сравнить с исвестной строкой текста. кто подскажет примером как организовать поиск?

Отправлен: 01.07.2009, 14:50
Вопрос задал: Will Wandom, Посетитель
Всего ответов: 1
Страница вопроса >>

Отвечает Micren, Практикант :
Здравствуйте, Will Wandom.
Программа. C++. MS VS 2008. Поиск организован рекурсивно. См. isContain(). Данные добавляются в дерево в отсортированном порядке(на то оно и дерево).
Код:

#include <iostream>
#include <locale>
#include <limits>
#include <string>

using
namespace std;

template<class T> class tree;

// Класс узел дерева
template<class T>
class tree_node
{
 friend class tree<T>;
private:
 tree_node<T>* _left;
 tree_node<T>* _right;
 T _data;
public:
 // Конструктор
 tree_node(void);
 tree_node(T data, tree_node* left=0, tree_node* right=0);
 virtual ~tree_node(void);
};

// Класс - дерево
template<class T
 >
class tree
{
private:
 tree_node<T>* _root;
 // Освобождает ресурсы
 void dispose();
protected:
 static void for_each(const tree_node<T>* const root , void (func)(const T&));
 static bool isContain(const tree_node<T>* const root,const T& item);
 void insert(tree_node<T>*& root,const T& data);
public:
 // Конструктор
 tree(void);
 tree(const tree& t);
 // Деструктор
 virtual ~tree(void);
 // Оператор равно
 const tree<T>&
operator=(const tree<T>& right);
 // Добавляет элемент к дереву
 void add(const T& item);
 // Обходит дерево
 void for_each(void (func)(const T&)) const;
 // Проверяет содержит ли дерево элемент item
 bool isContain(const T& item) const;
};

void print(const wstring& val)
{
 wcout<<val<<endl;
}

int main()
{
 locale::global(locale("russian_russia.866"));

 // Дерево со строками
 tree<
 wstring> myTree;

 // Вводим строки
 wcout<<L"Вводите строки(пустая строка для завершения ввода):"<<endl;
 wstring str;
 while(true)
 {
  getline(wcin,str);
  if(str.empty())
  {
   break;
  }
  myTree.add(str);
 }

 // Распечатаем
 wcout<<L"Введены следующие строки:"<<endl;
 myTree.for_each(print);

 // Что ищем?
 wcout<<L"Введите искомую строку:"<<endl;
 getline(wcin,str);

 //
Проверяем есть ли
 if(myTree.isContain(str))
 {
  wcout<<L"Найдена"<<endl;
 }
 else
 {
  wcout<<L"Не найдена"<<endl;
 }
 cout<<endl;
 system("PAUSE");
 return 0;
}

#pragma region class tree_node

// Конструктор
template<typename T>
tree_node<T>::tree_node(void)
:_left(0)
,_right(0)
{
}

template<typename T>
tree_
 node<T>::tree_node(T data, tree_node* left, tree_node* right)
:_left(left)
,_right(right)
,_data(data)
{
}

template<typename T>
tree_node<T>::~tree_node(void)
{
 if(_left)
 {
  delete _left;
 }
 if(_right)
 {
  delete _right;
 }
}

#pragma endregion

#pragma region class tree

// Конструктор
template<typename T>
tree<T>::tree(void)
:_root(0)
{
}

template<typename T>
tree<T>::tree(const
tree& t)
:_root(0)
{
 t.for_each(&tree<T>::add,*this);
}

// Деструктор
template<typename T>
tree<T>::~tree(void)
{
 dispose();
}

template<typename T>
const tree<T>& tree<T>::operator=(const tree<T>& right)
{
 if(this!=&right)
 {
  dispose();
  right.for_each(&tree<T>::add,*this);
 }
 return *this;
}

// Уничтожает дерево
template<
 typename T>
void tree<T>::dispose()
{
 if(_root)
 {
  delete _root;
  _root=0;
 }
}


template&l
t;typename T>
void tree<T>::insert(tree_node<T>*& root,const T& data)
{
 if(root)
 {
  tree_node<T>* current=root;
  tree_node<T>* insertingPos;
  while(current && current->_data>data)
  {
   insertingPos=current;
   current=current->_left;
  }
  if(current)
  {
   insert(current->_right,data);
  }
  else
  {
   insertingPos->_left=new tree_node<T>(data,0,0);
  }
 }
 else
 {
  root=new tree_node<T>(data,0,0);
 }
}

template<typename
T>
void tree<T>::add(const T& item)
{
 insert(_root,item);
}

template<typename T>
void tree<T>::for_each(void (func)(const T&)) const
{
 for_each(_root,func);
}

template<typename T>
void tree<T>::for_each(const tree_node<T>* const root , void (func)(const T&))
{
 if(root)
 {
  for_each(root->_left,func);
  func(root
 ->_data);
  for_each(root->_right,func);
 }
}

// Вот собственно метод обхода и поиска
template<typename T>
bool tree<T>::isContain(const tree_node<T>* const root,const T& item)
{
 if(root)
 {
  if(root->_data<item)
  {
   return isContain(root->_right,item);
  }
  else
  {
   return (root->_data==item) || isContain(root->_left,item);
  }
 }
 else
 {
  return false;
 }
}

template<typename
T>
bool tree<T>::isContain(const T& item) const
{
 return isContain(_root,item);
}

#pragma endregion

Пример:
Код:

Вводите строки(пустая строка для завершения ввода):
строка 1
еще одна строка
а
  эту строку будем искать
ну хватит

Введены следующие строки:
а эту строку будем искать
еще одна строка
ну хватит
строка 1
Введите искомую строку:
а эту строку будем искать
Найдена
исправление опечатки
-----
∙ Отредактировал: Victor Pyrlik, Модератор
∙ Дата редактирования: 02.07.2009, 17:30 (время московское)

Ответ отправил: Micren, Практикант
Ответ отправлен: 01.07.2009, 19:06

Оценка ответа: 5

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 251728 на номер 1151 (Россия) | Еще номера >>
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Нам очень важно Ваше мнение об этом выпуске рассылки. Вы можете оценить этот выпуск по пятибалльной шкале, пройдя по ссылке:
    оценить выпуск >>

    подать вопрос экспертам этой рассылки >>

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров >>

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2009, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.3 от 20.06.2009
    В избранное