小词典的散列 [英] Hashing of small dictionary

问题描述

我想散列小词典("dictionaries/small").主文件可以正确编译，但是在运行时，它会生成带有功能insert()的分段错误" 消息(特别是malloc()出错，但是我不知道是什么).

I want to hash small dictionary ("dictionaries/small"). Main file compiles correctly, but at runtime it produces "Segmentation fault" message with function insert() (specifically something wrong with malloc(), but I don`t know what).

HASH.c

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

typedef struct node
{
    char* name;
    struct node* next;
}
node;

node* first[26] = {NULL};

int hash(const char* buffer)
{
    return tolower(buffer[0]) - 'a';
}

void insert(int key, const char* buffer)
{
    node* newptr = malloc(sizeof(node));
    if (newptr == NULL)
    {
        return;
    }

    strcpy(newptr->name, buffer);
    newptr->next = NULL;

    if (first[key] == NULL)
    {
       first[key] = newptr;
    }
    else
    {
        node* predptr = first[key];
        while (true)
        {
            if (predptr->next == NULL)
            {
                predptr->next = newptr;
                break;
            }
            predptr = predptr->next;
        }
    }
}

推荐答案

在函数insert()中，您可以正确分配新节点:

In function insert() you correctly allocate the new node:

node* newptr = malloc(sizeof(node));

通过这种方式，您可以为完整的结构节点腾出空间:指向node的指针和指向char 的指针.但是，您不必分配那些指针应该指向的空间.

In this way you make room for a full struct node: a pointer to node and a pointer to char. But you don't allocate the space where those pointer are supposed to point.

因此，当您在name字段中复制输入缓冲区时，您正在执行非法尝试写入尚未分配甚至未初始化的char *指针:

So, when you copy the input buffer within name field, you are performing an illegal attempt to write to a char * pointer that has not been allocated and not even initialized:

strcpy(newptr->name, buffer);

在写入所有指针之前，需要对其进行分配(或至少将其初始化为有效的内存位置).就您而言:

All pointers need to be allocated (or at least initialized to a valid memory location) before writing in them. In your case:

newptr->name = malloc( strlen( buffer ) + 1 );
if( newptr->name )
{
    strcpy(newptr->name, buffer);
}

这篇关于小词典的散列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！