哈希表與鏈接方法程序不按預期方式工作

我正在C中使用鏈接列表鏈接方法實現哈希表。該程序運行，但在搜索條目時，我總是得到結果"Element is not found"，儘管該元素是在散列。這篇文章是對我以前的文章的輕微修改。該方案是如下：哈希表與鏈接方法程序不按預期方式工作

struct llist{ 
    char *s; 
    struct llist *next; 
}; 

struct llist *a[100]; 

void hinsert(char *str){ 
    int strint, hashinp; 
    strint = 0; 
    hashinp = 0; 
    while(*str){ 
     strint = strint+(*str); 
     str=str+1; 
    } 
    hashinp = (strint%100); 
    if(a[hashinp] == NULL){ 
     struct llist *node; 
     node = (struct llist *)malloc(sizeof(struct llist)); 
     node->s = str; 
     node->next = NULL; 
     a[hashinp] = node; 
    } 
    else{ 
     struct llist *node, *ptr; 
     node = (struct llist *)malloc(sizeof(struct llist)); 
     node->s = str; 
     node->next = NULL; 
     ptr = a[hashinp]; 
     while(ptr->next != NULL){ 
     ptr = ptr->next; 
     } 
     ptr->next = node; 
    } 
} 

void hsearch(char *strsrch){ 
    int strint1, hashinp1; 
    strint1 = 0; 
    hashinp1 = 0; 
    while(*strsrch){ 
     strint1 = strint1+(*strsrch); 
     strsrch = strsrch+1; 
    } 
    hashinp1 = (strint1%100); 
    struct llist *ptr1; 
    ptr1 = a[hashinp1]; 
    while(ptr1 != NULL){ 
     if(ptr1->s == strsrch){ 
     cout << "Element Found\n"; 
     break; 
     }else{ 
     ptr1 = ptr1->next; 
     } 
    } 
    if(ptr1 == NULL){ 
     cout << "Element Not Found\n"; 
    } 
}

hinsert()是將元素插入散列和hsearch是在散列來搜索的元素。散列函數寫入hinsert()本身。在main()，我所初始化所有元素a[]是NULL這樣的：

for(int i = 0;i < 100; i++){ 
    a[i] = NULL; 
}

來源

2012-10-31 Justin Carrey

1）hsearch是庫函數的名稱。 2）在C中沒有<<運算符類型爲「char *」的操作符3）不投射malloc（）的返回值，它是void *並且可以轉換爲任何指針類型。 4）您正在比較字符串指針，嘗試比較字符串。 5）嘗試使用無符號類型進行索引，這將釋放大量索引下溢問題6）for（）循環與while（）循環相比，會爲您節省2行和很多頭痛問題。 7）常量100在程序中出現兩次。預處理器和sizeof是你的朋友。 – wildplasser

我發現了這個錯誤。我應該單獨編寫散列函數。如果我在插入函數中寫入它，str在while循環完成後變爲'\ 0'。所以，當我說node-> s = str時，'\ 0'被插入到node-> s中。這正在搞亂一切。再次感謝！！ –

這只是一個錯誤。還有（至少）四個左邊。 – wildplasser

你不會在這個循環中前進指針。（這也是一個非常糟糕的散列函數）

while(*str){ 
     strint = strint+(*str); 
}

來源

2012-10-31 16:58:10 Art

爲什麼這是一個糟糕的散列函數？這是我實施的方式嗎？我只是好奇。如果有任何建議，我可以改進該計劃。 –

其中一個原因是它可能會導致負值。另一個是「abc」和「cba」會哈希到相同的值。第三個是循環永遠不會結束。 – wildplasser

@JustinCarrey在網上尋找人們討論散列字符串或一般哈希。有很多研究和測試，還有無盡的爭論。除非你的字符串是完全隨機的，否則一個簡單的總和將會導致散列值分佈不正確。我個人停止尋找完美的哈希函數並使用樹來存儲數據。它更優雅，沒有可利用的角落案例，在很多情況下，宏觀基準更快。 – Art

是你的程序在一個無限循環？也許用這條線？

while(*str){ 
     strint = strint+(*str); 
}

你的指針*str將永遠不會在這個循環的範圍無效，所以你應該得到一個無限循環。

來源

2012-10-31 16:57:41

哈希表與鏈接方法程序不按預期方式工作

回答

相關問題