1

我写了一段代码来实现哈希函数。将第 9 个元素“a12a”添加到列表时出现问题，gdb 报告如下，似乎问题是在 malloc 应用内存期间发生的。但是在添加第9个元素之前，我曾经在添加第6个元素“ad”时通过malloc成功申请了一次内存，为什么第二次申请内存失败？

Breakpoint 1, insert (p=0x3d2d10, value=0x4030e8 "a12a") at hashop.c:39
39              id = hash(value);
(gdb) n
40              *current = p + id;
(gdb)
41              if((*current)->value == NULL) {
(gdb)
44                      if((lookup(p+id, value)) == NULL) {
(gdb)
45                              new = (nList *)malloc(sizeof(nList));
(gdb)

Program received signal SIGSEGV, Segmentation fault.
0x7c938996 in ntdll!RtlDuplicateUnicodeString ()
   from C:\WINDOWS\system32\ntdll.dll
(gdb)

我的代码是：

void insert(nList *p, char *value)
{
    nList *new, **current;
    int id;

    id = hash(value);
    *current = p + id;
    if((*current)->value == NULL) {
        (*current)->value = value;
    } else {
        if((lookup(p+id, value)) == NULL) {
            new = (nList *)malloc(sizeof(nList));
            new->value = value;
            new->next = NULL;       
            while((*current)->next != NULL) {
                (*current) =(*current)->next;
            }
            (*current)->next = new;
        }
    }
}   

static char *str2[] = {"ac", "ba", "abv", "bc", "bx", "ad", "xx", "aaa", "a12a", "b123"};

每个元素的hash id如下：

ac, HashId=6
ba, HashId=5
abv, HashId=3
bc, HashId=7
bx, HashId=8
ad, HashId=7
xx, HashId=0
aaa, HashId=1
a12a, HashId=3
b123, HashId=8

从上面的列表中，可以确定“bc”和“ad”具有相同的哈希 id，所以在我的 insert() 函数中，我将应用一块内存来存储“ad”。“abv”和“a12a”也是一样，我也申请了一块内存，但这次失败了。为什么？任何人都可以弄清楚吗？赞赏！

4

2 回答 2

4

您正在使用此行破坏内存：

*current = p + id;

传递-Wall给 gcc 以打开所有警告，您将看到：

buggy-hash.c: In function ‘insert’:
buggy-hash.c:19:14: warning: ‘current’ is used uninitialized in this function [-Wuninitialized]

提示：在 Linux 下的Valgrind 之gcc -Wall类的内存调试器下使用和运行您的程序会更容易发现这些内存问题。

我猜你是通过在 Windows 下使用 CodeBlocks 或其他 IDE 来学习 C 编程的？在 Visual Studio 中以调试模式构建程序也会发现这些问题。

于 2012-10-04T18:25:48.597 回答
0

The problem is I have used p+id as the input of lookup function but forgot the p is already changed by *current. so the correct code is:

void insert(nList *p, char *value)
{
    nList *new, **current = &p;
    int id;
    id = hash(value);
    *current += id;

    if((*current)->value == NULL) {
        (*current)->value = value;
    } else {
        if((lookup(*current, value)) == NULL) {
            new = (nList *)malloc(sizeof(nList));

            if(new == NULL)
                printf("\nCannot get memory");
            else {
                new->value = value;
                new->next = NULL;       

                while((*current)->next != NULL) {
                    (*current) =(*current)->next;
                }

                (*current)->next = new;
            }
        }
    }
}
于 2012-10-05T01:18:18.763 回答