搜索查找操作总是返回错误的数据值，但返回正确的键值

Question

我正在处理程序中的hsearch函数。我生成的密钥是一个字符*。我存储的数据是一个整数。我总是添加一个元素没有问题，但当我想用查找时

入口*标高，标高；

elemp=hsearch(elem，FIND(。

elemp->data总是一个错误的值(不是插入的值(。

这有已知的问题吗。

#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
#include <search.h>
#define N 1
#define B 0
#define U 2
#define TAILLE 100000
char key[1000];
char* convTableToKeyString(int lignes, int colonnes, int joueur_tour, int  tab[lignes][colonnes]) {
int indice = 0;
switch (joueur_tour) {
case 0:
key[indice++] = 'B';
break;
case 1:
key[indice++] = 'N';
break;
}

for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
switch (tab[i][j]) {
case 0:
key[indice++] = 'B';
break;
case 1:
key[indice++] = 'N';
break;
case 2:
key[indice++] = 'U';
break;
}       
}
}
key[indice++] = '';
return key;
}
int valeur_configuration(int couleur_tour, int colonnes, int lignes, int tabEchec[lignes][colonnes]) {
ENTRY elem, *elemp;
int res;
int i,j;
int prochain_joueur = couleur_tour == B ? N : B;
int tabCase1[lignes][colonnes], tabCase2[lignes][colonnes], tabCase3[lignes][colonnes]; 
int lose_range = couleur_tour == B ? lignes-1 : 0;
int tabConf[3*colonnes];
int nbreCoupsPossibles = 0;
//generate the key and look if it already exist in the table
elem.key = convTableToKeyString(lignes, colonnes, couleur_tour, tabEchec);
elemp = hsearch(elem, FIND);
if (elemp != NULL) {
return (int) (elemp->data);
}
/* The value is not present in the hash, so I can calculate it */
//my code logic check the possible moves and add the value in the hash table
for (i = 0; i < lignes; i++) {
for (j = 0; j < colonnes; j++) {
int front = couleur_tour == B ? i-1 : i+1;
if (tabEchec[i][j] == couleur_tour) {
if (j != 0 && tabEchec[front][j-1] == prochain_joueur) {
/* some operations */
tabConf[nbreCoupsPossibles++] = valeur_configuration(prochain_joueur, colonnes, lignes, tabCase2);
if(tabConf[nbreCoupsPossibles-1] ==0) {
res = 1;
elem.data = (void *) res;
elemp = hsearch(elem, ENTER);
/* there should be no failures */
if (elemp == NULL) exit(EXIT_FAILURE);
return 1;
}
} // if (j != 0 && tabEchec[front][j-1] == prochain_joueur)

if (j != colonnes-1 && tabEchec[front][j+1] == prochain_joueur) {
/* some operations */
tabConf[nbreCoupsPossibles++] = valeur_configuration(prochain_joueur, colonnes, lignes, tabCase3);
if(tabConf[nbreCoupsPossibles-1] ==0) {
res = 1;
elem.data = (void *) res;
elemp = hsearch(elem, ENTER);
/* there should be no failures */
if (elemp == NULL) exit(EXIT_FAILURE);                                      
return 1;
}
} // if (j != colonnes-1 && tabEchec[front][j+1] == prochain_joueur)

if (tabEchec[front][j] == U) {
/* some operations */
tabConf[nbreCoupsPossibles++] = valeur_configuration(prochain_joueur, colonnes, lignes, tabCase1);
if(tabConf[nbreCoupsPossibles-1] ==0) { 
res = 1;
elem.data = (void *) res;
elemp = hsearch(elem, ENTER);
/* there should be no failures */
if (elemp == NULL) exit(EXIT_FAILURE);                  
return 1;
}
} // if (tabEchec[front][j].couleur == U)

} // if (tabEchec[i][j] == couleur_tour)
} // for (j = 0; j < colonnes; j++)
} // for (i = 0; i < lignes; i++)
if(nbreCoupsPossibles == 0) {
//Haven't move, I lost
res = 0;
elem.data = (void *) res;
elemp = hsearch(elem, ENTER);
/* there should be no failures */
if (elemp == NULL) exit(EXIT_FAILURE);
return 0;
}
i = 0;
int maxi = 0;
while (i < nbreCoupsPossibles && tabConf[i] > 0) {
maxi = maxi > tabConf[i] ? maxi : tabConf[i];
i++;
}
if (i >= nbreCoupsPossibles) {
res = -1 * (maxi+1);
elem.data = (void *) res;
elemp = hsearch(elem, ENTER);
/* there should be no failures */
if (elemp == NULL) exit(EXIT_FAILURE);
return res;
} else {
maxi = tabConf[i];
while (i < nbreCoupsPossibles) {
if (tabConf[i] < 0) {
maxi = maxi > tabConf[i] ? maxi : tabConf[i];
}
i++;
}
res = -1 * (maxi-1);
elem.data = (void *) res;
elemp = hsearch(elem, ENTER);
elemp = hsearch(elem, FIND);
/* there should be no failures */
if (elemp == NULL) exit(EXIT_FAILURE);
return res;
} // if (i >= nbreCoupsPossibles)
return 0;
}

/* Function call first call*/
int main() {
int n,m,i,j;
hcreate(TAILLE);
int colonnes;
int lignes;
char b = 'a';   
scanf("%d", &n);
scanf("%d", &m);
int tabPions[n][m];
char temp[m];
//Fake : just for flushing scanf internal functions
scanf("%c", &b);

for (i = 0; i < n; i++) {
scanf("%[^n]%*c", temp);
for (j = 0; j < m; j++) {
if (temp[j] != 'p' && temp[j] != 'P') tabPions[i][j] = U;
if (temp[j] == 'p') tabPions[i][j] = N;
if (temp[j] == 'P') tabPions[i][j] = B;
}
}
colonnes = m;
lignes = n;
int res = valeur_configuration(B, colonnes, lignes, tabPions);
printf("%dn", res);
hdestroy(); 
}

Answer 1

我不完全理解这个程序，但我想我可以解释你的hsearch问题。

您正在为每个键重用全局char key[1000]缓冲区。hsearch不允许这样做。向哈希表中添加项目时，hsearch不会复制密钥字符串。它只复制指针。

由于所有ENTER和的FIND都使用相同的密钥缓冲区，因此哈希表中的每个密钥每次都与您要查找的密钥匹配，因为它们都是相同的字符串！它们中的大多数都在错误的哈希桶中，这使得查找的结果有些随机。

快速解决方案是在每次ENTER操作之前执行elem.key = strdup(elem.key)。

如果您关心在程序退出之前释放字符串，则必须在内存管理方面更加努力。hsearch在这方面没有帮助，因为它没有提供迭代器。