Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
#1

Контейнер map: реализовать проверку на уникальность ключа - C++

31.10.2012, 21:34. Просмотров 1337. Ответов 5
Метки нет (Все метки)

Приветствую форумчан, имеется контейнер map с элементами
C++
1
2
3
4
struct Elemnts {
    int key;
    char *word;
};
Главное требование контейнера map, это уникальность ключей, каким образом можно реализовать проверку на уникальность ключа?
Заранее спасибо.

Добавлено через 33 минуты
Срочно нужна помощь.

Добавлено через 1 минуту
вот код мультикарты, как из нее сделать обычную map?
C++
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "iostream"
#include <stdio.h>
//МУЛЬТИКАРТА
using namespace std;
int m=4;         //начальный размер контейнера
struct tElem {//элемент контейнера
    int key;
    char *word;
};
struct tIter;
struct tNode{
    tElem * HMap; //хэш-таблица
    double KF;       //коэффициент ее заполнения     
    int Volume;   //число ячеек в массиве hmap
    tIter *Iter;   //попытка создать контейнер внутри контейнера
};
 
int fExtend(tNode *& );
void conout(tNode *& );
tNode*  fCreate(int size){//cоздать мултикарту на основе хэш-таблицы с открытой адресацией
    tElem *map= new  tElem[size];
    //for(int i =0;i<size;i++)
        //map[i].word=new char[64];
    tNode *a=new tNode;
    a->HMap=map;  
    a->Volume=size;
    a->KF=0;
    a->Iter=0;
    int i=0;while(i!=size){
        map[i].word ="nil";i++;} // пометили весь массив как "пустой"
    return a;
}
 
int fDestroy (tNode *& map){//удалить контейнер
    //for(int i =0;i<map->Volume;i++)   почему не работает?
    //  delete map->HMap[i].word;
    delete [] map->HMap;
    delete map;map=NULL;
    return 1;
}
 
//////////////////////////
int Hash(int key,int a){
    return abs(key%a);
}
////////////////////////////
int fCheck(tNode *&map,int key,char *word,int Vol){ //проверка и выдача номера индекса для нового элемента
    if(!strlen(word)) {printf("enter the word\n"); return -1;}
    int q=Hash( key,Vol);
    int i=0;
    while( (*map).HMap[q+i].word!="nil"&&map->HMap[q+i].word!="deleted") {// nill-метка означает пустоту ячейки как для поиска так и для записи , deleted-метка свободна для записи и занята при поиске элемента
        if(!strcmp(map->HMap[q+i].word,word))
          if (map->HMap[q+i].key==key)
            {printf("element is already existance,\n");
        return -1;
        } 
        i++;
        if(q+i==map->Volume)q=i=0;//идем по кругу
    }
        return q+i;//индекс ,куда будем записывать
    }
 
int fAdd(tNode *&map,int key,char *str){//   ф-я добаления 
    char *word=new char[64];strcpy(word,str);
    int i=fCheck( map, key, word,map->Volume);  //проверка и подбор индекса
    if (i==-1)return 0;
    map->HMap[i].key=key;
    map->HMap[i].word=word;
    map->KF += (double)1/map->Volume;
    if(map->KF>0.5)
    fExtend(map);// возможно нужно расширить таблицу
    return 1;
}
int fExtend(tNode *& map){
    int OldVol=map->Volume; //запомнил старый размер таблицы
    tElem *a=new tElem[map->Volume];  //буфер
    int i=map->Volume;
    while(i){
        a[i-1]=map->HMap[i-1];
            i--;
    }
    fDestroy(map);
    map=fCreate(OldVol*2);// создали новый контейнер,скопировали в нег старый, удалили
    for(int i=0;i<OldVol;i++)
        if(a[i].word!="nil"&&a[i].word!="deleted")
           fAdd(map,a[i].key,a[i].word);
    
    delete[]a;
    return 1;
}
 
 
 
tElem * fFind(tNode* &map,int key,char *word){  //поиск
    int q=Hash( key,map->Volume); int i=0,count =0;
 
    while(map->HMap[q+i].word!="nil"){
        if(!strcmp(map->HMap[q+i].word,word))
            if (map->HMap[q+i].key==key)
                return &map->HMap[q+i]; 
        i++;count++;
        if(q+i==map->Volume)q=i=0;//идем по кругу   
    }
    printf("no element\n");
    return  NULL;
}
tElem  fExecute(tNode* &map,int key,char *word){  //извлечение
    tElem* g=fFind(map,key,word);
    tElem a= {-99999,"FAIL-ERROR"};
    if(!g)return a;
    a.key=g->key;a.word=g->word;
    g->word="deleted";
    map->KF -= (double)1/map->Volume;
    
    return a;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.10.2012, 21:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Контейнер map: реализовать проверку на уникальность ключа (C++):

Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std::map? - C++
Здравствуйте. Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std map? Например: std::map...

Контейнер map - C++
Cоздать ассоциативный список имен (ключей), телефонов. Осуществить поиск по именам. Дополнить его данным адрес. Добавить возможности...

Контейнер map ? - C++
Не совсем удается разобраться Не удается разобраться с ассоциативными контейнерами ! Как выглядит объявление функции в псевдокоде? Что...

Контейнер map - C++
Здравствуйте, работаю с контейнером map, анализирую текст, получаю записи типа &quot;слово: число его появлений в тексте&quot;. Хотелось бы вывести...

Контейнер map - C++
в программе используется ассоциативный массив, идентификатором которого являются символы проблема в том что появляется элемент с...

контейнер map - C++
Помогите, пожалуйста дописать программу. Определите карту, в которой ключом является фамилия семьи, а значением вектор, который содержит...

5
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
31.10.2012, 22:03  [ТС] #2
Неужели все не вкурсах как реализовать?
0
I.M.
565 / 548 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
31.10.2012, 22:10 #3
Deimoser, алгоритм прост. Допустим, вам надо добавить пару ключ-значение. Ищите по дереву элемент с таким же ключом. Если он есть, то меняете его значение на новое. Если нет, то добавляете новый элемент.
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.10.2012, 22:13 #4
Не, просто не горю желанием разбирать ваш код :)

А в чём глобальная проблема? У вас есть хешик. Вы пытаетесь добавить новый элемент. Сначала проверяете, есть ли он в хеше. Если есть, то заменяете то значение, что уже есть, на новое. Если нет, то прицепляете к списку новый элемент.
0
Deimoser
4 / 4 / 0
Регистрация: 16.10.2012
Сообщений: 39
31.10.2012, 23:25  [ТС] #5
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Не, просто не горю желанием разбирать ваш код :)

А в чём глобальная проблема? У вас есть хешик. Вы пытаетесь добавить новый элемент. Сначала проверяете, есть ли он в хеше. Если есть, то заменяете то значение, что уже есть, на новое. Если нет, то прицепляете к списку новый элемент.
Да, сам алгоритм я понял, но не удается реализовать его на практике. Сейчас допишу один вариант. но сомниваюсь в его работе, как допишу скину наработки.

Добавлено через 55 минут
Как ни странно, удалось написать даже такому недалекому в програмировании челвеку как я, спасибо)

Однако возникла новая проблема, требуется объединить два контейнера, как поступить при наличии в них одинаковых ключей?

Добавлено через 10 минут
Удалить оба элемента, оставить один из них или оставить один как есть, а второму изменить ключ на уникальный?
0
I.M.
565 / 548 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
01.11.2012, 04:59 #6
Deimoser, если вы к одной мапе добавляете другую, то при совпадении ключей логично поступать так же, как и с добавлением одного элемента - т.е. заменяем существующее значение новым
если вы объединяете две мапы в новую, третью мапу - т.е. объединяемые мапы не должны измениться, то из двух объединяемых мап надо выбрать ту, у которой приоритет больше. Приоритет - это условное понятие. Его не надо высчитывать. Надо просто сделать соглашение. Например, та мапа, которая идет вторым аргументом, имеет больший приоритет на той мапой, которая идет первым аргументом
Удалять оба элемента не логично. А менять ключ на уникальный - трудоемко в плане замены и неудобно в плане использования.
0
01.11.2012, 04:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2012, 04:59
Привет! Вот еще темы с ответами:

Контейнер map - C++
Стоит задача реализовать контейнер map. Вопрос возникает при реализации итератора для этого контейнера. В итераторе должны быть реализованы...

Перевернуть контейнер map? - C++
Здравствуйте. Нужно отсортировать map по убыванию. Сделать что-то вроде прохода от map.end() до map.begin Спасибо.

Map контейнер сортировка - C++
Добрый день. Собственно необходимо вывести отсортированный мап контейнер по числу гласных в слове. Вводить строку и выводить мап...

Контейнер map<int, some*> - C++
доброго времени суток. Никак не могу разобраться с проблемой. суть такая. Хочу в классе создать статический контейнер с адресами...


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

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

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