在 C 中的一个 trie 节点上添加一个列表

Question

我在 trie 数据结构上添加单词（每个节点的字符）- 根据我在网上找到的实现正确发生 - http://www.techiedelight.com/trie-implementation-insert-search-delete/ 虽然我想扩展它并添加一个包含一些基于单词的数据的列表，比如术语频率等。现在我在 trie 节点上添加第一个元素时遇到列表指针的问题 - 在方法 append_posting_list 中 - 并获得 segmetation fault。这是到目前为止的代码。

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) {

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

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

在 C 中的一个 trie 节点上添加一个列表

Add a list on a trie node in C

c

pointers

memory-management

trie

data-structures