C 内存管理 -> 哈希

Question

我不知道我的问题是内存泄漏，还是我没有以正确的方式访问哈希表。

我的hash.h

#define HASHSIZE 31
#define EMPTY   ""
#define DELETED "-"

typedef char KeyType[9];

typedef void *Info;

typedef struct entry
{
    KeyType key;
    Info info;
}Entry;

typedef Entry HashTable[HASHSIZE];

我的hash.c

int Hash(KeyType k){
    return atoi(k)%HASHSIZE;
}

void InitializeTable(HashTable t){
    for(int i=0; i < HASHSIZE; i++){
        strncpy(t[i].key,EMPTY,9);
    }
}

void ClearTable(HashTable t){
    InitializeTable(t);
}

void InsertTable_LP(HashTable t, KeyType k, Info i){
    int a = 0;
    int hash = Hash(k);
    while((a<HASHSIZE) 
            && strcmp(t[hash].key,EMPTY)!=0
                && strcmp(t[hash].key,DELETED)!=0  ){
        hash = (hash + 1) % HASHSIZE;
        a++;
    }

    strncpy(t[hash].key,k,9);
    t[hash].info = i;
    printf("Value of info is %d\n",(int)t[hash].info);

}

int RetrieveTable_LP(HashTable t, KeyType k){
    int a=0;
    int hash = Hash(k);

    while(a<HASHSIZE 
            && strcmp(t[hash].key,k)!=0
                && strcmp(t[hash].key,EMPTY)!=0){
        hash=(hash+1) % HASHSIZE;
        a++;    
    }

    if(strcmp(t[hash].key,k)==0)
        return hash;
    return -1;

}


int main(){
    HashTable *t = malloc(HASHSIZE*sizeof(Entry));
    int valores[] = {1,2,3,4,5,6,7,8,9};

    ClearTable(*t);
    InsertTable_LP(*t,"1",valores);
    InsertTable_LP(*t,"2",valores+1);
    InsertTable_LP(*t,"3",valores+2);
    InsertTable_LP(*t,"4",valores+3);
    InsertTable_LP(*t,"5",valores+4);

    int pos = RetrieveTable_LP(*t,"2");
    if(pos==-1){
        printf("Error\n");
    }
    else
        printf("Position %d\n",pos);
        printf("okay %d\n",(int)t[pos]->info);

    printf("asdasdas\n");

    return 1;
}

我的输出是

Value of info is 1537727040
Value of info is 1537727044
Value of info is 1537727048
Value of info is 1537727052
Value of info is 1537727056
Position 2
okay 0

如果有人能给我解释一下，在此先感谢。

Answer 1

你的 malloc 不是必需的，之所以不明显是因为它被你 typedefd HashTable 的方式隐藏了，永远不要那样做，以下代码按您预期的方式工作

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASHSIZE 31
#define EMPTY   ""
#define DELETED "-"

typedef char KeyType[9];

typedef void *Info;

typedef struct entry
{
    KeyType key;
    Info info;
}Entry;

typedef Entry HashTable[HASHSIZE];

int Hash(KeyType k){
    return atoi(k)%HASHSIZE;
}

void InitializeTable(HashTable t) {
    int i;
    for(i=0; i < HASHSIZE; i++) {
        strncpy(t[i].key, EMPTY, 9);
    }
}

void ClearTable(HashTable t) {
    InitializeTable(t);
}

void InsertTable_LP(HashTable t, KeyType k, Info i){
    int a = 0;
    int hash = Hash(k);
    while((a<HASHSIZE) && strcmp(t[hash].key, EMPTY) !=0 && strcmp(t[hash].key, DELETED) !=0  ) {
        hash = (hash + 1) % HASHSIZE;
        a++;
    }
    strncpy(t[hash].key, k, 9);

    t[hash].info = i;

    printf("Value of info is %p\n", t[hash].info);

}

int RetrieveTable_LP(HashTable t, KeyType k){
    int a=0;
    int hash = Hash(k);

    while(a<HASHSIZE 
            && strcmp(t[hash].key,k)!=0
                && strcmp(t[hash].key,EMPTY)!=0){
        hash=(hash+1) % HASHSIZE;
        a++;    
    }

    printf("%s, %s\n", t[hash].key, k);
    if(strcmp(t[hash].key, k)==0)
        return hash;
    return -1;

}


int main(){
    /* 
     * You don't need to malloc, since HashTable is an array,
     * and it does not need to be a pointer, since it decays
     * to one when passed as such.
     */
    HashTable t;// = malloc(HASHSIZE * sizeof(Entry));
    int valores[] = {1,2,3,4,5,6,7,8,9};

    ClearTable(t);

    InsertTable_LP(t,"1",valores);
    InsertTable_LP(t,"2",valores+1);
    InsertTable_LP(t,"3",valores+2);
    InsertTable_LP(t,"4",valores+3);
    InsertTable_LP(t,"5",valores+4);

    int pos = RetrieveTable_LP(t, "2");
    if(pos==-1) {
        printf("Error\n");
    }
    else
    {
        printf("Position %d\n",pos);
        printf("okay %p\n", t[pos].info);
    }

    printf("asdasdas\n");

    return 1;
}

HashTable 的 typedef 让人很难知道如何处理 HashTable 类型的变量，这不是 typedef 的很好用法。

另外第二个printf不管条件

都会被执行

else
    printf("Position %d\n",pos);
    printf("okay %d\n",(int)t[pos]->info);

您需要添加{

else
{
    printf("Position %d\n",pos);
    printf("okay %d\n",(int)t[pos]->info);
}

Answer 2

valores 是一个数组。您插入的 Info 已被 typedef 编辑为 void *。你需要解决这些问题。

C 内存管理 -> 哈希

C Memory Management -> Hash

c

algorithm

hash

hashtable