Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
1

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

16.10.2012, 20:36. Просмотров 2378. Ответов 10
Метки нет (Все метки)

Приветсвую всех форумчан! Имеется задача разработать решение реализующее динамическую структуру данных (контейнер) типа «Карта»(map, ассоциативный массив пар элементов, состоящих из ключей и
соответствующих им значений. Ключи должны быть уникальны. Порядок следования
элементов определяется ключами. Элементами контейнера являются такие пары: целый
ключ + значение в виде строки символов произвольной длины.)

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

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

Из каждого элемента контейнера map вычесть среднее арифметическое контейнера
Контейнер map, тип элементов Int 3.Из каждого элемента вычесть среднее арифметическое контейнера

Вывод контейнера map
Подскажите пожалуйста как вывести на экран значение карты. Программа такая: надо создать карту, где...

Использование контейнера map
Доброе утро) Никак не пойму как пользоваться контейнером map и зачем он, вообще, нужен?! Скажем...

Копирование содержимого контейнера map
Итак, есть контейнер map<string,fsElem *>, где fsElem - базовый класс, также есть наследуемый от...

10
1992 / 1592 / 488
Регистрация: 31.05.2009
Сообщений: 2,980
16.10.2012, 21:32 2
Цитата Сообщение от Deimoser Посмотреть сообщение
Описал структуру (правильно ли?), что дальше делать в толк не возьму.
Почитать и разобраться, что из себя представляют бинарные(двоичные) деревья поиска(binary search tree). Стандартный map в C++ это "красно-черное дерево".
0
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
16.10.2012, 22:22  [ТС] 3
Цитата Сообщение от rangerx Посмотреть сообщение
Почитать и разобраться, что из себя представляют бинарные(двоичные) деревья поиска(binary search tree). Стандартный map в C++ это "красно-черное дерево".
Почитал и разобрался, только не пойму зачем использовать в моем случае красно-черное дерево.
Как я представляю себе контейнер map:
Есть ключ и есть его значение, при чтению ключа мы читаем значение с которым он(ключ) ассоциируется.
0
~ Эврика! ~
1253 / 1002 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
16.10.2012, 22:30 4
А как именно вы организуете пары ключ — значение? Список? Вектор? Дерево? Ведь их наверняка будет больше одной, их надо как-то упорядочить в памяти.
0
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
16.10.2012, 23:00  [ТС] 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++, такие как объекты, классы, шаблоны классов". Если кто подкинет исходный код буду очень благодарен.
0
~ Эврика! ~
1253 / 1002 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
16.10.2012, 23:03 6
Цитата Сообщение от Deimoser Посмотреть сообщение
Не совсем понимаю как реализовать пару ключ-значение через двоичное дерево. Родитель - ключ, а наследник - значение?
Есть бинарное дерево. Каждый узел — это именно такая пара ключ — значение. Узлы упорядочиваются и отыскиваются по ключу. Дерево тут затем, чтобы быстро искать нужное значение по ключу. Можно было бы запихнуть эти пары в массив, но тогда поиск занимает O(N) времени, дерево даёт O(log N).
0
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
16.10.2012, 23:13  [ТС] 7
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Есть бинарное дерево. Каждый узел — это именно такая пара ключ — значение. Узлы упорядочиваются и отыскиваются по ключу. Дерево тут затем, чтобы быстро искать нужное значение по ключу. Можно было бы запихнуть эти пары в массив, но тогда поиск занимает O(N) времени, дерево даёт O(log N).
Опять не понял, в каждом узле находится два элемента?

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

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

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

Добавлено через 6 минут
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
И всё же спросите, надо ли дерево или можно отмазаться хеш-таблицей. Самобалансирующееся дерево ещё надо написать и отладить (или вкурить в то, что написано до вас). Это сложнее, чем сделать map через хеш-таблицу.
Все что угодно, любой максимально кривой быдло код, лишь бы работало.
0
~ Эврика! ~
1253 / 1002 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
16.10.2012, 23:48 10
Хотя, хеш не особо подходит, так как вам надо итератор по порядку ключей. Боюсь, это всё же дерево.
0
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
31.10.2012, 21:42  [ТС] 11
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Хотя, хеш не особо подходит, так как вам надо итератор по порядку ключей. Боюсь, это всё же дерево.
Пойдет и хэш таблица, с итератором тоже разберусь, проблема с уникальностью ключей, не удается реализовать проверку на уникальность. А то вместо map multimap получается
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.10.2012, 21:42

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Удалить элементы из контейнера map
#include &lt;iostream&gt; #include &lt;map&gt; using namespace std; int main() { map&lt;int, int&gt; map1; ...

Реализация контейнера по типу map
Необходимо создать пользовательский класс по типу map, для реализации &quot;словаря&quot;. Можете помочь с...

Удаление символа в элементе контейнера map
Доброго времени суток! Есть текстовый файл , его записал в map , остались элементы такого вот рода...

Заполнение контейнера map объектами класса
Здравствуйте! Помогите разобраться с map. Не получается заполнить контейнер объектами класса....


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.