Блог FX’а

Еще две лабораторные работы: бинарное дерево поиска и хеш таблица (хеш-таблица еще не документирована).

Исходники и примеры работы с классами - далее по тексту.

Пример работы с деревом:

#include <iostream>
#include "tree.h"

void echo(fx::Node<int, int>& node)
{
    std::cout << node.value() << '\n';
}

int main()
{
    fx::Tree<int, int> t(1, 3);
    t.add(5, 2);
    t.add(2, 2);
    t.add(8, 10);
    t.add(15, -10);
    t.add(12, 5);
    t.add(20, 15);
    t.add(16, 2);
    t.add(30, 2);
    t.add(25, 20);
    t.add(35, 230);
    t.add_to_root(111, 1);
    t.remove(35);
    t.remove(25);

    // выводим с помощью итератора
    for(fx::Tree<int, int>::iterator_depth i = t.begin_depth(); i != t.end_depth(); ++i)
    {
        std::cout << *i << '\n';
    }
    std::cout << '\n';

    // выводим с помощью итератора
    for(fx::Tree<int, int>::iterator_width i = t.begin_width(); i != t.end_width(); ++i)
    {
        std::cout << *i << '\n';
    }
    std::cout << '\n';
    // доступ к корню
    std::cout << t.root()->key() << '\n';
    // поиск по ключу
    std::cout << t.find(30).value() << '\n';

    // подсчет количества различиных узлов в дереве
    std::cout << t.count() << '\n';
    std::cout << t.count_if(&fx::Node<int, int>::leaf) << '\n';
    std::cout << t.count_if(&fx::Node<int, int>::node_one) << '\n';
    std::cout << t.count_if(&fx::Node<int, int>::node_two) << '\n';

    // подсчет количества различиных узлов на каждом уровне дерева
    for(unsigned int i = 0; i < t.height(); ++i)
    {
        std::cout << t.on_level(i) << '\t'
                      << t.on_level_if(i, &fx::Node<int, int>::leaf)<< '\t'
                      << t.on_level_if(i, &fx::Node<int, int>::node_one) << '\t'
                      << t.on_level_if(i, &fx::Node<int, int>::node_two) << '\n';
    }

    // высота и максимальная ширина дерева
    std::cout << t.height() << '\n';
    std::cout << t.width() << '\n';

    // является ли дерево деревом поиска
    // для всех узлов: ключ правого подузла больше ключа узла
    // и ключ левого подузла меньше ключа узла
    std::cout << t.search_tree() << '\n';

    // длины наибольшего вырожденного и полного поддеревьев
    std::cout << t.degenerated() << '\n';
    std::cout << t.full() << '\n';

    // обходы, выполняется функция echo для каждого узла: echo(узел)
    t.infix_traverse(echo);
    t.prefix_traverse(echo);
    t.postfix_traverse(echo);
    t.width_traverse(echo);

    return 0;
}

Пример работы с хеш-таблицей:

#include <iostream>
#include <string>
#include "hash.h"

unsigned int hash(const std::string& str)
{
    unsigned int k = 0;
    for(unsigned int i = 0; i < str.size(); ++i)
    {
        k *= str[i];
        k %= 1009;
    }
    return k;
}

unsigned int hash2(const std::string& str)
{
    unsigned int k = 0;
    for(unsigned int i = 0; i < str.size(); ++i)
    {
        k *= str[i];
        k %= 1099;
    }
    return k;
}

int main()
{
    fx::HashTable<std::string, int> h(&hash, 1009);
    h.add("Петя the best", 0);
    h.add("Петя2 the best", 0);
    h.add("Петя the best3", 0);
    h.add("Вася", 1);
    h.add("Вася the best", 0);
    h.remove("Вася the best");

    // выводим значение, соответствующее ключу "Вася" - 1
    std::cout << h["Вася"].value() << '\n';

    // присваеваем записи в таблице с ключем "Вася" значение 20
    h["Вася"] = 20;

    // выводим значение, соответствующее ключу "Вася" - 20
    std::cout << h["Вася"].value() << '\n';

    // количество записей в таблице на данный момент
    std::cout << h.size();

    // проверка - пустая ли таблица
    std::cout << h.empty();

    // степень заполненности таблицы (0...1)
    std::cout << h.full_percent() << '\n';

    // меняем размер таблицы
    h.rehash(&hash2, 1099);

    // и опять смотрим степень заполненности
    std::cout << h.full_percent() << '\n';

    // выводим значение, соответствующее ключу "Вася"
    std::cout << h["Вася"].value() << '\n';

    return 0;
}

Файлы: Search Tree, Hash Table, Exception (нужен для работы остальных).

PS. Для работы хеш-таблицы дерево тоже нужно.

written by FX Poster \\ tags: C++, Classes, Hash-Table, Search-Tree