C hsearch 查找操作总是返回错误的数据值但正确的键值

Question

我正在程序中处理hsearch功能。我生成我的 key ，它是一个 char *。而我存储的数据是一个整数。我总是添加一个元素没有问题，但是当我想用

查找时

条目 *elemp, elem;

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++] = '\0';

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("%d\n", res);
    hdestroy(); 
}

Answer 1

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

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

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

一个快速修复方法是在每个 ENTER 操作之前执行 elem.key = strdup(elem.key)。

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