插入函数散列table C
Insert function hash table C
我在为哈希 table 实现插入函数时遇到问题 table。
所以我实现了一些测试调用,我只是单独调用函数。对于实际使用,我在 while 循环中调用该函数。出于测试目的,我只 运行 循环了 4 次。
我post下面的一些输出。 table 看起来很奇怪的原因是因为我的哈希函数。它对单词进行哈希处理,使得 A = 1、B = 2、C = 3 等等。字母在单词中的位置无关紧要,因为我会考虑单词的排列。而且,字母的大小写在这个问题中也是无关紧要的,所以a的值= A的值= 1.
对于字符串,abc = 1 + 2 + 3 = 6,bc = 2 + 3 = 5,等等
总的来说,哈希函数没问题。问题是插入函数。
我本地字典的前 4 个词是 A、A's、AA's、AB's。
我的预期输出应该是(当我 运行 测试调用时我得到相同的输出):
0:
1: [W: A, Len:1]
2:
3:
...
18:
19:
20: [W: A's, Len:3]
21: [W: AA's, Len:4]
22: [W: AB's, Len:4]
但是当我在循环中调用该函数时,列表中最后的内容将覆盖其他条目。如果我 运行 循环 100 次,那么最后一个条目仍然会替换之前的条目(注意单词的长度是如何不变的,但只有单词被替换):
0:
1: [W: AB's, L:1]
2:
3:
...
18:
19:
20: [W: AB's, Len:3]
21: [W: AB's, Len:4]
22: [W: AB's, Len:4]
下面是我的代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int hash(char *word)
{
int h = 0;
while(*word != '[=13=]')
{
if(*word >='A' && *word < 'A'+26) {
h=h+(*word -'A' + 1);
}
else if(*word >='a' && *word < 'a'+26) {
h=h+(*word -'a' + 1);
}
//else { // special characters
// return -1;
//}
word++;
}
return h;
}
typedef struct Entry {
char *word;
int len;
struct Entry *next;
} Entry;
#define TABLE_SIZE 1000 // random numbers for testing
Entry *table[TABLE_SIZE] = { NULL }; // an array of elements
void init() {
int i;
for (i = 0; i < TABLE_SIZE; i++) {
// initialize values
struct Entry *en = (struct Entry *)malloc(sizeof(struct Entry));
en->word = "";
en->len = 0;
en->next = table[i];
table[i] = en;
}
}
//Insert element
void insertElement(char *word, int len) {
int h = hash(word);
int i;
// because all words are different so there is no need to check for duplicates
struct Entry *en = (struct Entry *)malloc(sizeof(struct Entry));
en->word = word;
en->len = len;
en->next = table[h];
table[h] = en;
}
void cleanTable()
{
struct Entry *p, *q;
int i;
for( i=0; i<TABLE_SIZE; ++i )
{
for( p=table[i]; p!=NULL; p=q )
{
q = p->next;
free( p );
}
} // for each entry
}
int main() {
init(); // create hash table
// test calls produce correct output
//insertElement("A", (int)strlen("A"));
//insertElement("A's", (int)strlen("A's"));
//insertElement("AA's", (int)strlen("AA's"));
//insertElement("AB's", (int)strlen("AB's"));
int i;
i = 0;
FILE* dict = fopen("/usr/share/dict/words", "r"); //open the dictionary for read-only access
if(dict == NULL) {
return;
}
// Read each line of the file, and insert the word in hash table
char word[128];
while(i < 4 && fgets(word, sizeof(word), dict) != NULL) {
size_t len = strlen(word);
if (len > 0 && word[len - 1] == '\n') {
word[len - 1] = '[=13=]'; // trim the \n
}
insertElement(word, (int)strlen(word));
i++;
}
for ( i=0; i < 50; i++)
{
printf("%d: ", i);
struct Entry *enTemp = table[i];
while (enTemp->next != NULL)
{
printf("[W: %s, Len:%d] ", enTemp->word, enTemp->len);
enTemp = enTemp->next;
}
printf("\n");
}
cleanTable();
return 0;
}
尝试在这部分代码的每个循环中重新分配内存:
char* word = malloc(sizeof(char)*128);
while(i < 4 && fgets(word, sizeof(word), dict) != NULL) {
size_t len = strlen(word);
if (len > 0 && word[len - 1] == '\n') {
word[len - 1] = '[=10=]'; // trim the \n
}
insertElement(word, (int)strlen(word));
word = malloc(sizeof(char)*128);
i++;
}
您忘记为每个字符串重新分配内存导致所有指针指向同一点
注:未测试
请注意,您的 insertElement 获得了一个指向字符串的指针,并将该指针分配给当前的 Entry,但它是主要函数,您传递指向堆栈分配字符串的 word 参数(指针),并且在每次读取一个单词后更改该字符串。你必须使用 malloc 以便每个 word 指向它自己的内存区域
我在为哈希 table 实现插入函数时遇到问题 table。
所以我实现了一些测试调用,我只是单独调用函数。对于实际使用,我在 while 循环中调用该函数。出于测试目的,我只 运行 循环了 4 次。
我post下面的一些输出。 table 看起来很奇怪的原因是因为我的哈希函数。它对单词进行哈希处理,使得 A = 1、B = 2、C = 3 等等。字母在单词中的位置无关紧要,因为我会考虑单词的排列。而且,字母的大小写在这个问题中也是无关紧要的,所以a的值= A的值= 1.
对于字符串,abc = 1 + 2 + 3 = 6,bc = 2 + 3 = 5,等等
总的来说,哈希函数没问题。问题是插入函数。
我本地字典的前 4 个词是 A、A's、AA's、AB's。
我的预期输出应该是(当我 运行 测试调用时我得到相同的输出):
0:
1: [W: A, Len:1]
2:
3:
...
18:
19:
20: [W: A's, Len:3]
21: [W: AA's, Len:4]
22: [W: AB's, Len:4]
但是当我在循环中调用该函数时,列表中最后的内容将覆盖其他条目。如果我 运行 循环 100 次,那么最后一个条目仍然会替换之前的条目(注意单词的长度是如何不变的,但只有单词被替换):
0:
1: [W: AB's, L:1]
2:
3:
...
18:
19:
20: [W: AB's, Len:3]
21: [W: AB's, Len:4]
22: [W: AB's, Len:4]
下面是我的代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int hash(char *word)
{
int h = 0;
while(*word != '[=13=]')
{
if(*word >='A' && *word < 'A'+26) {
h=h+(*word -'A' + 1);
}
else if(*word >='a' && *word < 'a'+26) {
h=h+(*word -'a' + 1);
}
//else { // special characters
// return -1;
//}
word++;
}
return h;
}
typedef struct Entry {
char *word;
int len;
struct Entry *next;
} Entry;
#define TABLE_SIZE 1000 // random numbers for testing
Entry *table[TABLE_SIZE] = { NULL }; // an array of elements
void init() {
int i;
for (i = 0; i < TABLE_SIZE; i++) {
// initialize values
struct Entry *en = (struct Entry *)malloc(sizeof(struct Entry));
en->word = "";
en->len = 0;
en->next = table[i];
table[i] = en;
}
}
//Insert element
void insertElement(char *word, int len) {
int h = hash(word);
int i;
// because all words are different so there is no need to check for duplicates
struct Entry *en = (struct Entry *)malloc(sizeof(struct Entry));
en->word = word;
en->len = len;
en->next = table[h];
table[h] = en;
}
void cleanTable()
{
struct Entry *p, *q;
int i;
for( i=0; i<TABLE_SIZE; ++i )
{
for( p=table[i]; p!=NULL; p=q )
{
q = p->next;
free( p );
}
} // for each entry
}
int main() {
init(); // create hash table
// test calls produce correct output
//insertElement("A", (int)strlen("A"));
//insertElement("A's", (int)strlen("A's"));
//insertElement("AA's", (int)strlen("AA's"));
//insertElement("AB's", (int)strlen("AB's"));
int i;
i = 0;
FILE* dict = fopen("/usr/share/dict/words", "r"); //open the dictionary for read-only access
if(dict == NULL) {
return;
}
// Read each line of the file, and insert the word in hash table
char word[128];
while(i < 4 && fgets(word, sizeof(word), dict) != NULL) {
size_t len = strlen(word);
if (len > 0 && word[len - 1] == '\n') {
word[len - 1] = '[=13=]'; // trim the \n
}
insertElement(word, (int)strlen(word));
i++;
}
for ( i=0; i < 50; i++)
{
printf("%d: ", i);
struct Entry *enTemp = table[i];
while (enTemp->next != NULL)
{
printf("[W: %s, Len:%d] ", enTemp->word, enTemp->len);
enTemp = enTemp->next;
}
printf("\n");
}
cleanTable();
return 0;
}
尝试在这部分代码的每个循环中重新分配内存:
char* word = malloc(sizeof(char)*128);
while(i < 4 && fgets(word, sizeof(word), dict) != NULL) {
size_t len = strlen(word);
if (len > 0 && word[len - 1] == '\n') {
word[len - 1] = '[=10=]'; // trim the \n
}
insertElement(word, (int)strlen(word));
word = malloc(sizeof(char)*128);
i++;
}
您忘记为每个字符串重新分配内存导致所有指针指向同一点
注:未测试
请注意,您的 insertElement 获得了一个指向字符串的指针,并将该指针分配给当前的 Entry,但它是主要函数,您传递指向堆栈分配字符串的 word 参数(指针),并且在每次读取一个单词后更改该字符串。你必须使用 malloc 以便每个 word 指向它自己的内存区域