c - 在 C 中的 trie 节点上添加列表

Question

我正在 trie 数据结构上添加单词(每个节点的字符) - 根据我在网络上找到的实现，这是正确发生的 - http://www.techiedelight.com/trie-implementation-insert-search-delete/ 尽管我想扩展它并添加一个包含一些基于单词的数据的列表，例如术语频率等。 现在，当我在 trie 节点上添加第一个元素时，我遇到了列表指针的问题 - 在方法 append_posting_list 中 - 并出现段错误。 这是到目前为止的代码。

main.h

#ifndef TRIE_H
#define TRIE_H

#define CHAR_SIZE 26

typedef struct posting_list {
    int doc_id;
    int tf;
    int df;
    struct posting_list *next;
} posting_list_node ;

struct Trie
{
    posting_list_node *p_node; // this will be the head of the posting list for every word;
    int isLeaf;    // 1 when node is a leaf node
    struct Trie* character[CHAR_SIZE];
};

struct Trie* getNewTrieNode();
void insert(struct Trie* *head, char* str, int doc_id);
int search(struct Trie* head, char* str);

#endif //TRIE_H

main.c

#include <stdio.h>
#include <stdlib.h>
#include "main.h"


int main(){
    struct Trie* head = getNewTrieNode();
    insert(&head, "hello", 1);
    return 0;
}

// Function that returns a new Trie node
struct Trie* getNewTrieNode()
{
    struct Trie* node = (struct Trie*)malloc(sizeof(struct Trie));
    node->isLeaf = 0;

    for (int i = 0; i < CHAR_SIZE; i++)
        node->character[i] = NULL;

    return node;
}

posting_list_node* get_mem(){
    posting_list_node* p;
    p = (posting_list_node *)malloc(sizeof(posting_list_node));
    if (p == NULL){
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    return p;
}

void append_posting_list(int doc_id, posting_list_node **n){
    posting_list_node *new, *q;
    new = get_mem();

    new->doc_id = doc_id;
    new->tf = 1;
    new->next = NULL;

    // if new is the first element of the list
    if(n == NULL) {
        *n = new;
    } else {
        q = *n;
        while( q->next!=NULL) {
            q = q->next;
        }
        q->next = new;
    }
}

// Iterative function to insert a string in Trie.
void insert(struct Trie* *head, char* str, int doc_id)
{
    // start from root node
    struct Trie* curr = *head;
    while (*str)
    {
        // create a new node if path doesn't exists
        if (curr->character[*str - 'a'] == NULL)
            curr->character[*str - 'a'] = getNewTrieNode();

        // go to next node
        curr = curr->character[*str - 'a'];

        // move to next character
        str++;
    }

    // already found this word, increase frequency
    if(curr->isLeaf) {
        curr->p_node->tf += 1;
    } else {
        append_posting_list(doc_id, curr->p_node);
        // mark current node as leaf
        curr->isLeaf = 1;
    }
}

// Iterative function to search a string in Trie. It returns 1
// if the string is found in the Trie, else it returns 0
int search(struct Trie* head, char* str)
{
    // return 0 if Trie is empty
    if (head == NULL)
        return 0;

    struct Trie* curr = head;
    while (*str)
    {
        // go to next node
        curr = curr->character[*str - 'a'];

        // if string is invalid (reached end of path in Trie)
        if (curr == NULL)
            return 0;

        // move to next character
        str++;
    }

    // if current node is a leaf and we have reached the
    // end of the string, return 1
    return curr->isLeaf;
}

我真的被困在这里了。 任何建议将不胜感激。

Answer 1

我发现了一些问题，修复后可以消除段错误。

在getNewTrieNode()中，我认为您需要将p_node设置为NULL

struct Trie* getNewTrieNode() {
    struct Trie* node = (struct Trie*)malloc(sizeof(struct Trie));
    node->isLeaf = 0;

    for (int i = 0; i < CHAR_SIZE; i++)
        node->character[i] = NULL;

    node->p_node = NULL;

    return node;
}

append_posting_list() 接受 post_list_node **，但在 insert() 中，您只传递 post_list_node * >

void append_posting_list(int doc_id, posting_list_node **n)

append_posting_list(doc_id, curr->p_node);

看起来应该是这样

append_posting_list(doc_id, &(curr->p_node));

在append_posting_list()

中

if (n == NULL) {

应该是

if (*n == NULL) {

为了查看是否传入了指向空列表的指针。

您确实应该有一些函数可以在处理数据结构时打印出来，这样您就可以在开发时测试每个部分。简单地编译和运行代码并且不出现任何错误并不能保证代码能够正确地处理像这样的复杂数据结构。在继续下一个部分之前确保每个部分都能完美工作，这将为您节省尝试追踪段错误和其他类似错误的时间。