As I am searching dictionary example in C, I have come accross the example in here stackoverflow which references K&R The C Programming Language book. In that book, there is a table lookup topic in section 6.6. The section exemplifies table lookup as a hash table.

在本例中,哈希表由101个大小为nlist(以下代码段中的 struct )的自引用 node 组成.

我的问题是,为什么他们在查找表中使用自引用 struct ?查找表作为键值对工作,所以我们不必保留下一个 node .

struct nlist { 
 /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

我的问题的第二部分与示例有关,是关于lookup(char *s)函数中的循环语句.这个循环只工作一次,而且可能与此无关,我想可能是我错过了什么!

struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

我问题的最后一部分是关于函数*install(char *name, char *defn)中的赋值np->next = hashtab[hashval];(下面的函数),实际上它将当前 node 分配给自己作为下一个 node .

struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
          return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
       return NULL;
    return np;
}

提前谢谢.

推荐答案

表不是直接用键索引的,而是用键的散列索引的.不同的密钥可能具有相同的哈希.这叫做hash collisions.

  1. 此实现存储与键对应的所有值,这些值与链表具有相同的哈希,因此是一种自引用 struct .该表存储键值对的链接列表.同一列表中的所有键都有相同的哈希.(这不是处理碰撞的唯一方法).
  2. 在发生碰撞的情况下,循环会多次工作.如果你没有看到这个循环执行了不止一次,那么继续添加条目,直到发生冲突.
  3. 不,它不会将 node 分配给自身.它在链表的开头插入一个新分配的 node .列表的前一个标题将成为列表中的第二个 node .

C++相关问答推荐

在struct中调用函数,但struct在void中 *

为什么在C中二维字符数组会有这样的行为?

SDL 2.0-从数组渲染纹理

无效指针值在函数调用之间莫名其妙地改变

C lang:当我try 将3个或更多元素写入数组时,出现总线错误

X86/x64上的SIGSEGV,由于原始内存访问和C中的DS寄存器之间的冲突,在Linux上用TCC编译为JIT引擎

如何在C中引发/处理自定义信号?

限制不同类型的限定符

这个C程序在工作中途停止获取输入.我收到分段故障(核心转储).我还是不知道问题出在哪里

用C语言计算文本文件中的整数个数

如何将另一个数组添加到集合中,特别是字符串?

如何确保我将使用C标准库函数的函数版本,如&getc";,而不是类似函数的宏版本?

Printf()在C中打印终止字符之后的字符,我该如何解决这个问题?

OSDev--双缓冲重启系统

在C中使用无符号整数模拟有符号整数

创建 makefile 来编译位于不同目录中的多个源文件

初始化动态分配的布尔二维数组的最佳方法是什么?

将帧从相机 (/dev/video0) 复制到帧缓冲区 (/dev/fb0) 会产生意外结果

C++11 的 constexpr 和 C23 的 [[reproducible]] 有什么区别?

用C程序读取.txt文件并解析,如何处理空字段