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

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

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.428 RSS
←   Апрель 2011   →
 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


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


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

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

Статистика

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

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


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

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

Лучшие эксперты данной рассылки

Асмик Александровна
Статус: Академик
Рейтинг: 7749
∙ повысить рейтинг » 		Boriss
Статус: Академик
Рейтинг: 2644
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2338
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++

Номер выпуска:1655
Дата выхода:16.04.2011, 23:30
Администратор рассылки:Киселёва Алёна aka Verena (Профессор)
Подписчиков / экспертов:318 / 185
Вопросов / ответов:1 / 2

Вопрос № 182798: Уважаемые эксперты! Помогите с программой на С++. Под ОС Windows XP, Borland Builder 6 и Visual Studio 2005. Условие задачи: Таблица реализована в виде дерева.

Вопрос № 182798:

Уважаемые эксперты! Помогите с программой на С++. Под ОС Windows XP, Borland Builder 6 и Visual Studio 2005. Условие задачи:
Таблица реализована в виде дерева.

Код:
const int N=4; //Количество элементов в одном
квадрате
struct element 
{
 int keyX; //Ключ 1
 int keyY; //Ключ 2
 char *info; //Информация 
};

//Узел дерева
struct Node
{
 int minX; //Нижняя граница X
 int maxX; //Верхняя граница X
 int minY; //Нижняя граница Y
 int maxY; //Верхняя граница Y
 Node *child[4]; //Массив указателей на поддеревья
 element *inf[N];//Массив указателей на элементы
};


Написать процедуру включения нового элемента. Прим ер вставки: В узел записываем элементы с ключами keyX, keyY (minX<keyX<maxX,minY<keyY<maxY). Одинаковой пары ключей быть не может. В каждом узле может быть не больше N элементов. После того, как N элементов было записано для соответствующего узла создаются дочерние (границы X,Y формируются в соответствии с рисунком). Далее в соответствии с границей X/Y и введенным значением ключа (keyX, keyY) - выбирается соответствующий дочерний квадрат (minX<keyX<maxX,minY<keyY<maxY). После переполнения дочернего квадрата создаются дочерние для него.

Написать процедуру поиска информации по паре ключей.
Вывод всего содержимого таблицы.
Огромное спасибо!

Отправлен: 11.04.2011, 01:28
Вопрос задал: zim-zum (Посетитель)
Всего ответов: 2
Страница вопроса »

Отвечает Micren (Профессор) :
Здравствуйте, zim-zum!
Программа. С++. Компилировал GCC.
Код:
#include <cstdlib>
#include <cstring>
#include <stdexcept>
#include <iostream>
#include <locale>

using namespace
std;

// Элемент таблицы

class element
{
public:
    // Конструкторы
    element(int keyX, int keyY, const char* const info);
    element(const element& e);
    // Деструктор
    ~element();
    // Оператор присваивания
    const element & operator=(const element& e);
    // Ключи
    int keyX() const;
    int keyY() const;
    // Данные
    const char* info() const;
private:
    // Копируют аргумент в чл
 ены класса
    void copy(const element& e);
    void copy(const char* const s);
    // Освобождает ресурсы
    void destroy();

    int _keyX;
    int _keyY;
    char* _info;
};

// Узел таблицы

class node
{
public:
    // Конструктор
    node(int minX, int maxX, int minY, int maxY);
    ~node();
    // Обход всех элементов дерева с вызовом для каждого заданной функции
    void for_each(void (*func)(int keyX, int keyY, const char* info));
protected:

   // Добавление элемента
    void add(const element& item);
    // Поиск элемента
    const element * find(int keyX, int keyY) const;

    // Количество ветвей
    static const size_t _CHILD_NUM = 4;
    // Количество данных
    static const size_t _INF_NUM = 4;

    int _minX, _maxX;
    int _minY, _maxY;
    node* _child[_CHILD_NUM];
    size_t _childNum;
    element* _inf[_INF_NUM];
    size_t _infNum;
private:<
 br>    node(const node&);
    const node & operator=(const node&);
};

class table : public node
{
public:
    explicit table(int minX = 0, int maxX = 100, int minY = 0, int maxY = 100);
    ~table();
    // Добавляет элемент в таблицу
    void add(int keyX, int keyY, const char* const info);
    // Поиск элемента
    const char* find(int keyX, int keyY) const;
private:
    table(const table&);
    const table & operator=(const table&);
};

void find(const
table& t, int keyX, int keyY)
{
    const char* res = t.find(keyX, keyY);
    cout << "Поиск для ключей [" << keyX << "," << keyY << "]: ";
    if (res)
    {
        cout << res;
    }
    else
    {
        cout << "не найдено.";
    }
    cout << endl;
}

void print(int keyX, int keyY, const char* info)
{
    cout << "[
 " << keyX << "," << keyY << "]:" << info << endl;
}

int main()
{
    locale::global(locale(""));

    table myTable;

    myTable.add(1, 2, "1,2");
    myTable.add(5, 7, "5,7");
    myTable.add(8, 3, "8,3");
    myTable.add(12, 22, "12,22");
    myTable.add(10, 2, "10,2");
    myTable.add(5, 6, "5,6");
    myTable.add(2, 2, "2,2");


   find(myTable, 20, 30);
    find(myTable, 5, 7);
    find(myTable, 2, 2);

    cout << "Таблица:" << endl;
    myTable.for_each(print);

#ifdef _WIN32
    system("pause");
#endif

    return (EXIT_SUCCESS);
}

element::element(int keyX, int keyY, const char* const info)
: _keyX(keyX)
, _keyY(keyY)
, _info(0)
{
    copy(info);
}

element::element(const elemen
 t& e)
: _keyX(e._keyX)
, _keyY(e._keyY)
, _info(0)
{
    copy(e._info);
}

element::~element()
{
    destroy
();
}

const element& element::operator =(const element& e)
{
    if (&e != this)
    {
        copy(e);
    }
    return *this;
}

inline int element::keyX() const
{
    return _keyX;
}

inline int element::keyY() const
{
    return _keyY;
}

inline const char* element::info() const
{
    return _info;
}

void element::copy(const element& e)
{
    destroy();
    _keyX = e._keyX;
    _keyY = e._keyY;
    copy(e._info);
}

void
element::copy(const char* const s)
{
    if (s)
    {
        size_t size = strlen(s) + 1;
        _info = new char[size];
        strcpy(_info, s);
    }
}

void element::destroy()
{
    if (_info)
    {
        delete [] _info;
        _info = 0;
    }
}

node::node(int minX, int maxX, int minY, int maxY)
: _minX(minX)
, _maxX(maxX)
, _minY(minY)
, _maxY(maxY)
, _childNum(0)
, _infNum(0)
{
    for (size_t i = 0; i < _CHILD_NUM; ++i)
    {
        _child[i] = 0;
    }
    for (size_t i = 0; i < _INF_NUM; ++i)
    {
        _inf[i] = 0;
    }
}

node::~node()
{
    for (size_t i = 0; i < _childNum; ++i)
    {
        if (_child[i])
        {
            delete _child[i];
            _child[i] = 0;
        }
    }
    for (size_t i = 0; i < _infNum; ++i)
    {
        if (_inf[i])
        {

           delete _inf[i];
            _inf[i] = 0;
        }
    }
}

void node::for_each(void (*func)(int, int, const char*))
{
    for (size_t i = 0; i < _infNum; ++i)
    {
        func(_inf[i]->keyX(), _inf[i]->keyY(), _inf[i]->info());
    }
    for (size_t i = 0; i < _childNum; ++i)
    {
        _child[i]->for_each(func);
    }
}

void node::add(const element& item)
{
    // Проверка гра
 ниц
    if (_minX <= item.keyX() && item.keyX() < _maxX && _minY <= item.keyY() && item.keyY() < _maxY)
    {
        // Если есть куда вставлять
        if (_infNum < _INF_NUM)
        {
            _inf[_infNum++] = new element(item);
        }
        else
        {
            // Перебираем ветви
            for (size_t i = 0; i < _childNum; ++i)
            {
                try
                {
                    _child[i]->add(item);

                   return;
                }
                catch (invalid_argument&)
                {

                }
            }
            // Если еще не вставлен смотрим есть ли куда отрастить ветвь
            if (_childNum < _CHILD_NUM)
            {
                // Разбиваем квадрат согласно условия
                int midX = (_minX + _maxX) / 2;
                int midY = (_minY + _maxY) / 2;
               
  int minX, maxX, minY, maxY;
                if (item.keyX() < midX)
                {
                    minX = _minX;
                    maxX = midX;
                }
                else
                {
                    minX = midX;
                    maxX = _maxX;
                }
                if (item.keyY() < midY)
                {
                    minY = _minY;
                    maxY = midY;
                }
                else

               {
                    minY = midY;
                    maxY = _maxY;
                }
                // Выделяем память и добавляем
                node* n = new node(minX, maxX, minY, maxY);
                n->add(item);
                _child[_childNum++] = n;
            }
            else
            {
                throw logic_error("Не могу разместить элемент");
            }
        }
  
   }
    else
    {
        throw invalid_argument("Ключ не попадает в диапазон значений для узла");
    }
}
const element * node::find(int keyX, int keyY) const
{
    // Проверка границ
    if (_minX <= keyX && keyX < _maxX && _minY <= keyY && keyY < _maxY)
    {
        // Ищем в своих данных
        for (size_t i = 0; i < _infNum; ++i)
        {
            if (_inf[i]->keyX() == keyX && _inf[i]->keyY() == keyY)
            {
                return _inf[i];
            }
        }
        // Ищем в ветвях
        for (size_t i = 0; i < _childNum;
++i)
        {
            const element* e = _child[i]->find(keyX, keyY);
            if (e)
            {
                return e;
            }
        }
    }
    return 0;
}

table::table(int minX, int maxX, int minY, int maxY)
: node(minX, maxX, minY, maxY)
{
}

table::~table()
{

}

void table::add(int keyX, int keyY, const char* const info)
{
    node::add(element(keyX, keyY, info));
}
 

const char* table::find(int keyX, int keyY) const
{
    const element* e = node::find(keyX, keyY);
    return e ? e->info() : 0;
}

Пример работы:
Код:
Поиск для ключей [20,30]:
не найдено.
Поиск для ключей [5,7]: 5,7
Поиск для ключей [2,2]: 2,2
Таблица:
[1,2]:1,2
[5,7]:5,7
[8,3]:8,3
[12,22]:12,22
[10,2]:10,2
[5,6]:5,6
[2,2]:2,2

По условию
© Цитата:
Одинаковой пары ключей быть не может
Поэтому при вставке не делалось никаких дополнительных проверок на наличие элементов с такими же ключами в таблице.

Ответ отправил: Micren (Профессор)
Ответ отправлен: 12.04.2011, 12:04
Номер ответа: 266664
Украина, Краматорск

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

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

    • Отвечает Лысков Игорь Витальевич (Старший модератор) :
    Здравствуйте, zim-zum!
    Программа создает дерево, случайно заполняет его элементами, выводит на экран.
    После чего запрашивает данные для поиска, выводит соответствующее сообщение.
    Выход из поиска - ввод x>=100
    Что непонятно, спрашивайте

    Код:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <malloc.h>
    #include <time.h>

    const int N=4;  //Количество элементов в одном квадрате
    const int M=4;  //Количество квадратов
    const int MAX_X=100; //Максимальное значение по Х
    const int MAX_Y=100; //Максимальное значение по Y
    const i
 nt COUNT=50; //Число элементов

    struct element 
    {
     int keyX;   //Ключ 1
     int keyY;   //Ключ 2
     char *info;   //Информация 
    };

    //Узел дерева
    struct Node
    {
     int minX;   //Нижняя граница X
     int maxX;   //Верхняя граница X
     int minY;   //Нижняя граница Y
     int maxY;   //Верхняя граница Y
     Node *child[M];  //Массив указателей на поддеревья
     element *inf[N]; //Массив указателей на элементы
    };

    //рекурентная п/п освобождения памяти, занятой деревом
    //параметр
- адрес узла
    void TreeFree(Node * node)
    {
     int i;

     //по всем элементам узла
     for (i=0; i<N; i++)
     {
      //сначала проверим, есть ли элемент
      if (node->inf[i])
      {
       //есть ли поле info
       if (node->inf[i]->info)
        free(node->inf[i]->info);
       //освобождаем память элемента
       free(node->inf[i]);
      }
     }
     //по всем поддеревьям
     for (i=0; i<M; i++)
     {
      //проверим, есть ли поддере
 во
      if (node->child[i])
       //вызываем себя же с адресом поддерева
       TreeFree(node->child[i]);
     }
     //освобождаем память узла
     free(node);
    }

    //п/п инициализации корня дерева
    //параметр - адрес адреса корня
    void TreeInit(Node ** node)
    {
     //запрашиваем память под корень
     //используем calloc для обнуления памяти
     *node = (Node*)calloc(1, sizeof Node);
     //зададим максимальные значения (минимальные = 0)
     (*node)->maxX = MAX_X;
     (*node)->maxY = MAX_Y;
    }

    //п/п
добавления M пустых поддеревьев
    //параметр - адрес узла
    void TreeNodesInsert(Node * node)
    {
     //запрашиваем память сразу под все M=4 поддерева
     for (int i=0; i<M; i++)
      node->child[i] = (Node*)calloc(1, sizeof Node);

     //пропишем минимальные и максимальные значения
     node->child[0]->minX = node->child[2]->minX = node->minX;
     node->child[1]->minX = node->child[3]->minX = 
      node->chil
 d[0]->maxX = node->child[2]->maxX = (node->maxX + node->minX)/2;
     node->child[1]->maxX = node->child[3]->maxX = node->maxX;

     node->child[0]->minY = node->child[1]->minY = node->minY;
     node->child[2]->minY = node->child[3]->minY = 
      node->child[0]->maxY = node->child[1]->maxY = (node->maxY + node->minY)/2;
     node->child[2]->maxY = node->child[3]->maxY = node->maxY;
    }

    //рекурентная п/п вставки
нового элемента в дерево
    //параметры: адрес узла и значения x, y, info для нового элемента
    void TreeInsert(Node * node, int NewKeyX, int NewKeyY, char *NewInfo)
    {
     int  i;

     //просмотрим, есть ли место, куда записать в элементы текущего узла
     //по всем элементам узла
     for (i=0; i<N; i++)
     {
      //пустое ли место
      if (NULL == node->inf[i])
      {
       //запросим память под элемент
       node->inf[i] = (element*)malloc(sizeof eleme
 nt);
       //заполним информацией
       node->inf[i]->keyX = NewKeyX;
       node->inf[i]->keyY = NewKeyY;
       //под строку н
адо на 1 больше, чем длина (под 0)
       node->inf[i]->info = (char*)malloc(strlen(NewInfo)+1);
       strcpy(node->inf[i]->info, NewInfo);
       //задача выполнена - выходим
       return;
      }
     }

     //все уже заполнено
     //проверим, есть ли поддеревья на данном уровне
     //достаточно проверить только 0-й квадрат (или все, или ни одного)
     if (NULL == node->child[0])
      //добавляем поддеревья
      TreeNodesInsert(node);

     //самый интересный момент :)
     //вычислим тндекс
поддерева, как выражение (Y выше середины)*2 + (X правее середины),
     //где (Y выше середины) и (X правее середины) - логические величины, равные 0 или 1
     i = (NewKeyY >= (node->maxY + node->minY)/2)*2 + 
      (NewKeyX >= (node->maxX + node->minX)/2);

     //вызываем себя же, чтобы вставить элемент в поддерево
     TreeInsert(node->child[i], NewKeyX, NewKeyY, NewInfo);
    }

    //рекурентная п/п вывода дерева на экран в виде:
    //[квадрат,]
 ...[квадрат,]индекс элемента    x = <value>, y = <value>, xmin, xmax, ymin, ymax
    //x и y выводим, как ранее сформированную строку, хранимую в поле info
    //параметры: узел и строка, содержащая строку с квадратами предыдущих уровней
    void TreePrint(Node * node, char * sLevel)
    {
     int  i;
     //строка для хранения строки с квадратами для последующего вызова
     char sLevelCurr[128];

     //проходим по всем элементам уровня
     for (i=0; i<M; i++)
     {
      //проверим на наличие
      if
(node->inf[i])
       //выводим
       printf("%s%d\t%s,\t\t%d\t%d,\t%d\t%d\n", sLevel, i, node->inf[i]->info, 
        node->minX, node->maxX, node->minY, node->maxY);
     }
     //пробежимся по поддеревьям
     //только, если они есть
     if (node->child[0])
     {
      //по всем
      for (i=0; i<N; i++)
      {
       //добавим к строке пройденных квадратов текущий квадрат
       sprintf(sLevelCurr, "%s%d,", sLevel, i);
      
  //вызовем себя же для вывода поддерева
       TreePrint(node->child[i], sLevelCurr);
      }
     }
    }


    //рекурентная п/п поиска в дерева элемента с заданными x и y
    //параметры: узел, x, y, адрес переменной, куда запишется адрес узла с найденным элементом
    //и адрес переменной, куда запишется индекс в массиве элементов
    //возвращается 1, если элемент найден и 0, если не найден
    bool TreeSearch(Node * node, int x, int y, Node ** pNode, int * pIdx)
    {
     int  i;

     //просмотрим массив
элементов текущего узла
     for (i=0; i<N; i++)
     {
      //проверим на существование и на совпадение x и y
      if ((node->inf[i]) && (node->inf[i]->keyX == x) && (node->inf[i]->keyY == y))
      {
       //нашли!
       *pNode = node; //возвратим адрес узла
       *pIdx = i;  //и индекс в массиве элементов
       return 1;  //элемент найден
      }
     }
     //просмотрим поддеревья
     for (i=0; i<M; i++)
     {
      //проверим на существование
      
 if (node->child[i])
      {
       //вызовем себя же для проверки поддерева
       if (TreeSearch(node->child[i], x, y, pNode, pIdx))
        //если найдено, то выходим
        return 1;
      }
     }
     //не найден!
     return 0;
    }

    //основная программа
    int main(void)
    {
     Node *Root;  //корень дерева
     Node *Node;  //адрес узла, используется для поиска
     int  i;   //просто переменная цикла
     int  x, y;  //переменные для для заполнения и поиска по дереву
     int  idx;  //переменная для
индекса в массиве индексов, используется для поиска
     char string[32]; //строка для формирования поля info

     //будем заполнять дерево случайными элементами
     //инициализация последовательности псевдослучайных чисел
     srand( (unsigned)time( NULL ) );

     //создаем корень дерева
     TreeInit(&Root);

     //заполняем дерево
     //предварительно проверяем на уникальность ключей поиском по дереву
     for (i=0; i<COUNT; i++)
     {
      do
      {
       x 
 = rand()%MAX_X;
       y = rand()%MAX_Y;

       //если найдется, то генерим новый элемент
      }while (TreeSearch(Root, x, y, &Node, &id
x));
      
      //формируем строку для info
      sprintf(string, "x = %d,\ty = %d", x, y);
      //заносим в дерево
      TreeInsert(Root, x, y, string);
     }
     
     //выведем все элементы дерева
     printf("All elements of tree:\n\n");
     //начинаем с корня, вторым параметром пустая строка, потому что 
     //для корня будем выводить только индексы в массиве элементов
     TreePrint(Root, "");

     //начинаем бесконечный цикл поиска в дереве введенных элементов
     //для выхода
из цикла необходимо ввести x >= 100
     printf("\nSearch elements (Enter x>=100 for exit)...\n");
      
     //циклим пока x < 100 (в начале x наверняка < 100)
     while(x < MAX_X)
     {
      //вводим x
      printf("\nEnter x: ");
      scanf("%d",&x);
      //ищем или выходим?
      if (x < MAX_X)
      {
       //вводим y
       printf("Enter y: ");
       scanf("%d",&y);
       //на всякий случай, найдем ост
 аток от деления на 100
       y %= MAX_Y;
       //ищем
       if (TreeSearch(Root, x, y, &Node, &idx))
       {
        //нашли - выводим
        printf("%s,\t\t%d\t%d,\t%d\t%d\n", Node->inf[idx]->info, 
         Node->minX, Node->maxX, Node->minY, Node->maxY);
       }
       else
        //не нашли
        printf("Element not found\n");
      }
     }

     //освободим память
     TreeFree(Root);
     
     return 0;
    }


    Примерный вывод программы:


    -----
    Люби своего ближнего, как самого себя

    Ответ отправил: Лысков Игорь Витальевич (Старший модератор)
    Ответ отправлен: 12.04.2011, 17:17
    Номер ответа: 266675
    Украина, Кировоград
    Тел.: +380957525051
    ICQ # 234137952
    Mail.ru-агент: igorlyskov@mail.ru

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

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

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

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

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

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

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

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

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