时间戳

首页 > 解决方案 > 我的 HashTable 中的指针损坏或我遗漏了什么？

c - 我的 HashTable 中的指针损坏或我遗漏了什么？

问题描述

这是我的代码，

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

typedef struct DF
{
    char str[101];
    int D;
    struct DF *next;
} DF;
DF *df[5];

int hash (char str[])
{
    int sum=0, len=strlen (str);
    for (int x=0; x<len; x++) sum+=str[x];
    
    return sum%5;
}

DF* ND (char str[])
{
    DF *node=(DF*) malloc (sizeof (DF));
    strcpy (node->str, str); node->D=1;
    node->next=NULL;
    
    return node;
}

void add (char str[])
{
    int idx=hash (str);
    if (df[idx])
    {
        DF *temp=df[idx];
        while (temp) temp=temp->next;
        temp=ND (str);
    }
    else df[idx]=ND (str);
}

int main (void)
{
    char str1[]="The"; add (str1);
    char str2[]="App"; add (str2);
    
    if (df[4])
    {
        printf ("[4] %s", df[4]->str);
        DF *temp=df[4]->next;
        while (temp)
        {
            printf (" -> %s", temp->str);
            temp=temp->next;
        }
        puts ("");
    }
    
    return 0;
}

请注意void add (char[])，为什么没有输出[4] The -> App？即使我改成DF *temp=df[idx];它DF *temp=df[idx]->next;也没有什么区别。但是如果我把它的功能改成这个，

void add (char str[])
{
    int idx=hash (str);
    if (df[idx])
    {
        DF *temp=df[idx];
        while (temp->next) temp=temp->next;
        temp->next=ND (str);
    }
    else df[idx]=ND (str);
}

它打印出来[4] The -> App。那么，这两种算法有什么区别呢？

标签： cpointershashtable

解决方案

第一种方式：

temp=ND (str);

只需分配一个局部变量，因此它对函数外部没有影响，因为您有内存泄漏（但未修改列表，未添加元素）

但第二种方式：

temp->next=ND (str);

修改链表

要工作，您可以修改第一种方法：

void add (char str[])
{
    int idx=hash (str);
    if (df[idx])
    {
        DF **temp=&df[idx];
        while (*temp) temp=&(*temp)->next;
        *temp=ND (str);
    }
    else df[idx]=ND (str);
}

但这很复杂，除非你想删除if：

void add (char str[])
{
    DF ** temp=&df[hash(str)];
    
    while (*temp)
      temp=&(*temp)->next;
    *temp=ND (str);
}

注意在同义词列表末尾添加一个新单元格是没有用的，你没有全局顺序，你可以直接这样做：

void add (char str[])
{
    DF * temp=ND (str);
    int idx=hash (str);

    temp->next = df[idx];
    df[idx] = temp;
}

在ND：

strcpy (node->str, str); node->D=1;

很危险，因为str可能太长而无法保存node->str，您可以使用strncpy

当要保存的字符串很小时，您会失去记忆。

不使用数组作为字段str而是使用 achar*并复制字符串（strdup例如）怎么样？

在哈希中你遍历字符串两次，你不需要计算strlen并且可以使用

for (int x=0; str[x] != 0; x++) sum+=str[x];

推荐阅读