Форум программистов, компьютерный форум CyberForum.ru

Разработка контейнера типа Карта (Map) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
16.10.2012, 20:36     Разработка контейнера типа Карта (Map) #1
Приветсвую всех форумчан! Имеется задача разработать решение реализующее динамическую структуру данных (контейнер) типа «Карта»(map, ассоциативный массив пар элементов, состоящих из ключей и
соответствующих им значений. Ключи должны быть уникальны. Порядок следования
элементов определяется ключами. Элементами контейнера являются такие пары: целый
ключ + значение в виде строки символов произвольной длины.)

В программном решении следует реализовать следующие операции над контейнером:

• создание и уничтожение контейнера;
• добавление и извлечение элементов контейнера;
• обход всех элементов контейнера (итератор);
• вычисление количества элементов в контейнере;
• объединение и пересечение контейнеров;
• сохранение контейнера в дисковом файле и восстановление контейнера из файла.
Вся проблема в том, что запрещено использовать средства C++, такие как объекты, классы, шаблоны классов, а также сам готовый контейнер map.
Описал структуру (правильно ли?), что дальше делать в толк не возьму.
Код
struct Karta
{
    char* key;  //ключ
    char* Data;      //значение
};
Кто чем поможет премного благодарю=)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.10.2012, 20:36     Разработка контейнера типа Карта (Map)
Посмотрите здесь:

Вывод контейнера map C++
C++ Использование контейнера map
C++ Задача по теме карта (map)
C++ Копирование содержимого контейнера map
C++ Разработка класса контейнера
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rangerx
1908 / 1517 / 139
Регистрация: 31.05.2009
Сообщений: 2,876
16.10.2012, 21:32     Разработка контейнера типа Карта (Map) #2
Цитата Сообщение от Deimoser Посмотреть сообщение
Описал структуру (правильно ли?), что дальше делать в толк не возьму.
Почитать и разобраться, что из себя представляют бинарные(двоичные) деревья поиска(binary search tree). Стандартный map в C++ это "красно-черное дерево".
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
16.10.2012, 22:22  [ТС]     Разработка контейнера типа Карта (Map) #3
Цитата Сообщение от rangerx Посмотреть сообщение
Почитать и разобраться, что из себя представляют бинарные(двоичные) деревья поиска(binary search tree). Стандартный map в C++ это "красно-черное дерево".
Почитал и разобрался, только не пойму зачем использовать в моем случае красно-черное дерево.
Как я представляю себе контейнер map:
Есть ключ и есть его значение, при чтению ключа мы читаем значение с которым он(ключ) ассоциируется.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
16.10.2012, 22:30     Разработка контейнера типа Карта (Map) #4
А как именно вы организуете пары ключ — значение? Список? Вектор? Дерево? Ведь их наверняка будет больше одной, их надо как-то упорядочить в памяти.
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
16.10.2012, 23:00  [ТС]     Разработка контейнера типа Карта (Map) #5
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
А как именно вы организуете пары ключ — значение? Список? Вектор? Дерево? Ведь их наверняка будет больше одной, их надо как-то упорядочить в памяти.
Не совсем понимаю как реализовать пару ключ-значение через двоичное дерево. Родитель - ключ, а наследник - значение?

Наткнулся на код КЧ дерева на Интуите, но компилятор (VS10) отказывается работать

Код
//создание красно-черного дерева
void Make_RBTree(RBTree** Node, int n){
  int Data;
  while (n > 0) {
    cout << "Введите значение ";
        cin >> Data;
    Insert_Node(Node, Data);
    n--;
  }
}

//добавление узла в красно-черное дерево
void Insert_Node(RBTree** Node,int Data) {
  RBTree **Curent, *Parent, *New_Node;
  Curent = Node;
  Parent = NIL;
  // Поиск местоположения
  while (*Curent != NIL) {
    Parent = (*Curent);
    Curent = Data < (*Curent)->Data ? &((*Curent)->Left) : &((*Curent)->Right);
  }
  // Создание нового узла
  New_Node = new RBTree();
  New_Node->Data = Data;
  New_Node->Parent = Parent;
  New_Node->Left = NIL;
  New_Node->Right = NIL;
  New_Node->color = RED;
  // Вставка элемента в дерево
  if(Parent != NIL){
    if (Data < Parent->Data) Parent->Left = New_Node;
    else Parent->Right = New_Node;
  }
  else (*Curent) = New_Node;
  Insert_Fixup(Node, New_Node);
} 

// Поддержка баланса дерева после вставки нового элемента
void Insert_Fixup(RBTree** Node,RBTree* New_Node){
  RBTree* Current = New_Node;
  // Проверка свойств дерева
  while (Current != *(Node) && Current->Parent->color == RED){
    // если есть нарушение
    if (Current->Parent == Current->Parent->Parent->Left) {
      RBTree *ptr = Current->Parent->Parent->Right;
      if (ptr->color == RED) {
        Current->Parent->color = BLACK;
        ptr->color = BLACK;
        Current->Parent->Parent->color = RED;
        Current = Current->Parent->Parent;
      }
      else {
        if (Current == Current->Parent->Right) {
          // сделать Current левым потомком
          Current = Current->Parent;
          Rotate_Left(Node,Current);
        }
        // перекрасить и повернуть
        Current->Parent->color = BLACK;
        Current->Parent->Parent->color = RED;
        Rotate_Right(Node,Current->Parent->Parent);
      }
    }
    else {
      RBTree *ptr = Current->Parent->Parent->Left;
      if (ptr->color == RED) {
        Current->Parent->color = BLACK;
        ptr->color = BLACK;
        Current->Parent->Parent->color = RED;
        Current = Current->Parent->Parent;
      }
      else {
        if (Current == Current->Parent->Left) {
          Current = Current->Parent;
          Rotate_Right(Node,Current);
        }
        Current->Parent->color = BLACK;
        Current->Parent->Parent->color = RED;
        Rotate_Left(Node,Current->Parent->Parent);
      }
    }
  }
  (*Node)->color = BLACK;
}

//поворот узла Current влево
void Rotate_Left(RBTree** Node,RBTree *Current) {
  RBTree *ptr = Current->Right;
  Current->Right = ptr->Left;
  if (ptr->Left != NIL) ptr->Left->Parent = Current;
  if (ptr != NIL) ptr->Parent = Current->Parent;
  if (Current->Parent != NIL) {
    if (Current == Current->Parent->Left)
      Current->Parent->Left = ptr;
    else
      Current->Parent->Right = ptr;
    }
  else {
    (*Node) = ptr; 
  }
  ptr->Left = Current;
  if (Current != NIL) Current->Parent = ptr;
}

//поворот узла Current вправо
void Rotate_Right(RBTree** Node,RBTree *Current) {
  RBTree *ptr = Current->Left;
  Current->Left = ptr->Right;
  if (ptr->Right != NIL) ptr->Right->Parent = Current;
  if (ptr != NIL) ptr->Parent = Current->Parent;
  if (Current->Parent != NIL) {
    if (Current == Current->Parent->Right)
      Current->Parent->Right = ptr;
    else
      Current->Parent->Left = ptr;
  }
  else {
    (*Node) = ptr;
  }
  ptr->Right = Current;
  if (Current != NIL) Current->Parent = ptr;
}

//печать красно-черного дерева
void Print_RBTree(RBTree* Node, int l){
  int i;
  if (Node != NIL) {
    Print_RBTree(Node->Right, l+1);
    for (i=0; i< l; i++) cout << "    ";
    if (Node->color == RED) 
      SetConsoleTextAttribute(hStd,FOREGROUND_RED);
    cprintf ("%4ld", Node->Data);
    SetConsoleTextAttribute(hStd,atr);
    Print_RBTree(Node->Left, l+1);
  }
  else cout << endl;
}

//прямой обход красно-черного дерева
void PreOrder_RBTree(RBTree* Node){
  if (Node != NIL) {
    printf ("%3ld",Node->Data);
    PreOrder_RBTree(Node->Left);
    PreOrder_RBTree(Node->Right);
  }
}

//обратный обход красно-черного дерева
void PostOrder_RBTree(RBTree* Node){
  if (Node != NIL) {
    PostOrder_RBTree(Node->Left);
    PostOrder_RBTree(Node->Right);
    printf ("%3ld",Node->Data);
  }
}

//симметричный обход красно-черного дерева
void SymmetricOrder_RBTree(RBTree* Node){
  if (Node != NIL) {
    PostOrder_RBTree(Node->Left);
    printf ("%3ld",Node->Data);
    PostOrder_RBTree(Node->Right);
  }
}

//проверка пустоты красно-черного дерева
bool Empty_RBTree(RBTree* Node){
  return ( Node == NIL ? true : false );
}

//освобождение памяти, выделенной под красно-черное дерево
void Delete_RBTree(RBTree* Node){
  if (Node != NIL) {
    Delete_RBTree(Node->Left);
    Delete_RBTree(Node->Right);
    delete(Node);
  }
}
Добавлено через 18 минут
Нужен контейнер работающий по принципу map, "ключ" => "значение". Способ реализации значения не имеет (но интереснее было бы взглянуть на все возможные), главное соблюсти главное условие: "не использовать средства C++, такие как объекты, классы, шаблоны классов". Если кто подкинет исходный код буду очень благодарен.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
16.10.2012, 23:03     Разработка контейнера типа Карта (Map) #6
Цитата Сообщение от Deimoser Посмотреть сообщение
Не совсем понимаю как реализовать пару ключ-значение через двоичное дерево. Родитель - ключ, а наследник - значение?
Есть бинарное дерево. Каждый узел — это именно такая пара ключ — значение. Узлы упорядочиваются и отыскиваются по ключу. Дерево тут затем, чтобы быстро искать нужное значение по ключу. Можно было бы запихнуть эти пары в массив, но тогда поиск занимает O(N) времени, дерево даёт O(log N).
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
16.10.2012, 23:13  [ТС]     Разработка контейнера типа Карта (Map) #7
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Есть бинарное дерево. Каждый узел — это именно такая пара ключ — значение. Узлы упорядочиваются и отыскиваются по ключу. Дерево тут затем, чтобы быстро искать нужное значение по ключу. Можно было бы запихнуть эти пары в массив, но тогда поиск занимает O(N) времени, дерево даёт O(log N).
Опять не понял, в каждом узле находится два элемента?

Реализация через дин. массив выглядит так?
Код
struct Map
{
Map X; 
Map Y; 
char* Data;          //значение
}int key;            //ключ;
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
16.10.2012, 23:23     Разработка контейнера типа Карта (Map) #8
Цитата Сообщение от Deimoser Посмотреть сообщение
Опять не понял, в каждом узле находится два элемента?
Да, по одному из них (ключу) этот узел можно отыскать в дереве. Другой (значение) просто подвешен к этом элементу, он играет пассивную роль (для дерева). Ключ — как индекс в массиве. Значение — как значение в ячейке массива. Из-за структуры дерева индексы хранятся рядом со значениями и недоступны отдельно.

Что-то вроде
C
1
2
3
4
5
struct tree_node {
    int key;
    struct tree_node *left, *right;
    char *data;
};
И всё же спросите, надо ли дерево или можно отмазаться хеш-таблицей. Самобалансирующееся дерево ещё надо написать и отладить (или вкурить в то, что написано до вас). Это сложнее, чем сделать map через хеш-таблицу.
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
16.10.2012, 23:35  [ТС]     Разработка контейнера типа Карта (Map) #9
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Да, по одному из них (ключу) этот узел можно отыскать в дереве. Другой (значение) просто подвешен к этом элементу, он играет пассивную роль (для дерева). Ключ — как индекс в массиве. Значение — как значение в ячейке массива. Из-за структуры дерева индексы хранятся рядом со значениями и недоступны отдельно.

Что-то вроде
C
1
2
3
4
5
struct tree_node {
    int key;
    struct tree_node *left, *right;
    char *data;
};
Спасибо, кажется разобрался))

Добавлено через 6 минут
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
И всё же спросите, надо ли дерево или можно отмазаться хеш-таблицей. Самобалансирующееся дерево ещё надо написать и отладить (или вкурить в то, что написано до вас). Это сложнее, чем сделать map через хеш-таблицу.
Все что угодно, любой максимально кривой быдло код, лишь бы работало.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
16.10.2012, 23:48     Разработка контейнера типа Карта (Map) #10
Хотя, хеш не особо подходит, так как вам надо итератор по порядку ключей. Боюсь, это всё же дерево.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2012, 21:42     Разработка контейнера типа Карта (Map)
Еще ссылки по теме:

Map, карта в карте C++
Заполнение контейнера map из файла без цикла C++
Не получается вывести и удалить последний элемент контейнера map C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
31.10.2012, 21:42  [ТС]     Разработка контейнера типа Карта (Map) #11
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Хотя, хеш не особо подходит, так как вам надо итератор по порядку ключей. Боюсь, это всё же дерево.
Пойдет и хэш таблица, с итератором тоже разберусь, проблема с уникальностью ключей, не удается реализовать проверку на уникальность. А то вместо map multimap получается
Yandex
Объявления
31.10.2012, 21:42     Разработка контейнера типа Карта (Map)
Ответ Создать тему
Опции темы

Текущее время: 03:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru