Study & Dev | Blog Archive | Структуры данных и алгоритмы. Практика. Деревья

Структуры данных и алгоритмы. Практика. Деревья

January 20, 2007

Примеры. Итератор по дереву.

```
#include <cstdio>
```
```
#include <vector>
```
```
#include <map>
```
```
#include <string>
```
```
#include <iostream>
```
```
 
```
```
using namespace std;
```
```
 
```
```
struct invalid_iterator_operation{};
```
```
struct invalid_node_state {};
```
```
 
```
```
struct BinNode {
```
```
	int data;
```
```
	BinNode * left, * right, *parent;
```
```
 
```
```
	BinNode (int d):
```

	data (d), left (NULL) , right (NULL) , parent (NULL){}

```
	operator int (){
```
```
		return data;
```
```
	}
```
```
};
```
```
 
```
```
struct tree_iterator {
```
```
	BinNode * cur;
```
```
 
```
```
	map <BinNode *, int> stages;
```
```
	tree_iterator (BinNode * _cur):
```
```
	cur (_cur){stages[cur]= 0;}
```
```
	tree_iterator (): cur (NULL) {}
```
```
 
```
```
 
```
```
	tree_iterator & operator ++ (){
```

		if (cur == NULL) throw invalid_iterator_operation();

```
 
```
```
		if (stages[cur] == 2){
```
```
			cur = cur->parent;
```
```
			try{
```
```
				return ++(*this);
```
```
			}
```

			catch (invalid_iterator_operation){return *this;}

```
		}
```
```
		if (stages [cur] == 1){
```
```
			if (cur->right)
```
```
			{
```
```
				stages [cur]++;
```
```
				int tmp = stages [cur];
```
```
				cur = cur->right;
```
```
				stages [cur] = 0;
```
```
				return *this;
```
```
			}
```
```
			else{
```
```
				stages[cur]++;
```
```
				int tmp = stages [cur];
```
```
				return ++(*this);
```
```
			}
```
```
		}
```
```
		if (stages[cur] == 0){
```
```
			BinNode *saved = cur;
```
```
			stages [cur]++;
```
```
			int tmp = stages [cur];
```
```
			try{
```
```
				cur = cur->left;
```
```
				stages [cur] = -1;
```
```
				return ++(*this);
```
```
			}catch (invalid_iterator_operation){
```
```
				cur = saved;
```
```
				stages [cur]++;
```
```
				int tmp = stages [cur];
```
```
				cur = cur->right;
```
```
				stages [cur] = -1;
```
```
				try{
```
```
					return ++(*this);
```
```
				}
```
```
				catch (invalid_iterator_operation){
```
```
					cur = saved;
```
```
					stages [cur]++;
```
```
					int tmp = stages [cur];
```
```
					cur = cur->parent;
```
```
					tmp = stages [cur];
```
```
					return ++(*this);
```
```
				}//catch ()
```
```
			}//catch ()
```
```
		}//if (stages [cur] == 0)
```
```
		if (stages [cur] == -1){
```
```
			stages[cur]++;
```
```
			return *this;
```
```
		}
```
```
 
```

		cerr << "State Error: Unknow Node State " << stages [cur] << " : " << *cur<<endl;

```
		throw invalid_node_state();
```
```
 
```
```
	};
```
```
 
```
```
	tree_iterator & operator ++(int){
```
```
		return operator ++ ();
```
```
	}
```

	bool operator != (const tree_iterator & ai){

```
		return cur != ai.cur;
```
```
	}
```
```
 
```
```
	BinNode * operator * (){
```
```
		return cur;
```
```
	}
```
```
 
```
```
};
```

BinNode * add (BinNode * w, int x, BinNode *parent){

```
	if (w == NULL){
```
```
		BinNode * n = new BinNode (x);
```
```
		n->parent = parent;
```
```
		return n;
```
```
	}
```
```
	if ( x < w->data)
```
```
		w->left = add (w->left , x , w);
```
```
	else
```
```
		w->right = add (w->right , x , w);
```
```
	return w;
```
```
}
```
```
 
```
```
void print_LR (BinNode *w , int level){
```
```
	if (w == NULL) return;
```

	for (int i = 0; i < level;i++) cout << "\t";

```
	cout << w->data << endl;
```
```
	print_LR (w->left, level+1);
```
```
	print_LR (w->right, level+1);
```
```
}
```
```
void main(void)
```
```
{
```
```
	BinNode * root = NULL;
```
```
	for (int i = 0; i < 50; i++)
```

		root = add (root , rand () % 100 , NULL);

```
	print_LR (root , 0);
```

	tree_iterator I = tree_iterator (root);

```
	tree_iterator I_end;
```
```
	try{
```
```
		while ( I != I_end){
```
```
			cout << *(*I) << ", ";
```
```
			I++;
```
```
		}
```
```
	}
```
```
	catch (invalid_node_state){
```
```
		cerr << "invalid_node_state" << endl;
```
```
	}
```
```
	catch (invalid_iterator_operation){
```

		cerr << "invalid_iterator_operation" << endl;

```
	}
```
```
 
```
```
}
```

Задания к практической работе

Сегодняшняя работа посвящена работе с деревьями.

1. Необходимо создать класс GenTree который будет представлять собой генеалогическое дерево. Дерево должно быть бинарным: у каждого узла (человека, который описывается данным узлом) должны быть два родителя. В состав класса необходимо включить следующее множество методов:

 • add (GenNode * child, string fio, bool sex) – 
 метод для добавления информации об одном из родителей для человека на которого ссылается указатель child.
 • add (string parent_path, string fio , bool sex) – 
 добавление информации об одном из родителей: путь(местоположение) добавляемого узла задается в виде xpath – строки
 (<em>“vasya\tatiana\igor\anna”</em>) в случае не возможности найти место, куда следует добавить узел должно генерироваться
 исключение <em>bad_xpath_expression</em>.
 • delete (string deleted_xpath) – метод должен служить для удаления всех узлов которые находятся ниже чем тот,
 на который указывает xpath – выражение.
 • bool get_sex (string name_xpath) – данная функция должна возвращать признак пола у человека,
 на которого ссылается xpath-выражение.
 • print_all_tree () – данная функция должна распечатывать все генеалогическое дерево, при этом необходимо,
 чтобы данные были представлены в удобном виде, например, так:

```
vasya:
```
```
father: petya
```
```
		father:	anton
```
```
			father: serge
```
```
		mother: vika
```
```
		mother: alla
```
```
			father: boris
```
```
		mother: anna
```
```
mother: irina
```
```
….
```

 - а всех узлов лежащих ниже чем тот, на который ссылается xpath-выражение.

 (например, “alla”) и должна пройтись по всему дереву найти все ссылки на данную фамилию 
 (ведь в общем случае, имена повторяются) и вывести все xpath-пути ведущие к найденным фамилиям 
 (для вышеприведенного дерева, это будет “<em>vasya\petya\alla</em>”).

 обо всех людях которые есть в нашем дереве которые имеют пол sex – возвращается map,
 в качестве ключа будут храниться xpath выражения которые ведут к найденному человеку, 
 а в качестве значения по ключу будет количество дочерних элементов в дереве 
 (т.е. таких людей которые были предками для найденного).

print_below (string xpath) – вывод на экран в форме подобной той что приведена выше не всего дерева
print_xpath_by_fio (string fio) - данная функция получает на вход только фио одного человека
map collect (bool sex) – данная функция должна формировать карту в которой должны храниться данные

2. Создать дерево в котором будут храниться перекрестные ссылки на слова некоторого файла: необходимо прочитать текстовой файл, все слова которые содержатся в нем необходимо поместить в двоичное дерево поиска (нечто подобное было приведено в методическом пособии), но кроме этого необходимо создать список ссылок. Для каждого слова необходимо вести учет того в каких именно строках оно встречается. Программа должна анализировать файл, имя которого задается как первый параметр командной строки, как второй параметр командной строки задается слово которое должно быть найдено. В качестве результата работы выводится сначала само построенное дерево (обязательно, как и в предыдущем задании необходимо при выводе каждого узла делать некоторое количество отступов прапорциональное уроню узла), а также вывести список всех предложений где встречается данное слово.

Categories: Структуры данных и алгоритмы

Study & DevО программировании и не только

Структуры данных и алгоритмы. Практика. Деревья

Задания к практической работе

Поиск

Недавнее

Архив

Разделы