0

我正在编辑一个 trie 程序以将我自己的字符串输入到 trie 中。当我传递像“hello”这样的常量时，没有分段错误的情况，但是当我传递一个字符串变量时，它会出现分段错误（核心转储）。这是功能： -

void insert(struct Trie *head, char* str)//FUNCTION CONCERNED WITH SEGMENTATION FAULT POSSIBLY OTHERS
{
    // 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++;
    }

考虑

struct Trie *head=(struct Trie*)malloc(sizeof(struct Trie));
insert(head,"hello");

这很好，但如果我为字符串（输入）赋值并传递它

char str[100];
scanf("%s",str);
insert(head,str);

这会产生段错误。（插入函数，而不是 scanf）我不擅长调试段错误，所以我想要一些关于为什么会这样的帮助。以及如何纠正它下面的完整代码以供参考（完全向下滚动到主要功能）

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<ctype.h>
// define character size
#define CHAR_SIZE 26

// A Trie node
struct Trie
{
    int isLeaf; // 1 when node is a leaf node
    struct Trie* character[CHAR_SIZE];
};

// 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;
}

// Iterative function to insert a string in Trie
void insert(struct Trie *head, char* str)//FUNCTION CONCERNED WITH SEGMENTATION FAULT POSSIBLY OTHERS
{
    // 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++;
    }

    // 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;
}

// returns 1 if given node has any children
int haveChildren(struct Trie* curr)
{
    for (int i = 0; i < CHAR_SIZE; i++)
        if (curr->character[i])
            return 1;   // child found

    return 0;
}

// Recursive function to delete a string in Trie
int deletion(struct Trie **curr, char* str)
{
    // return if Trie is empty
    if (*curr == NULL)
        return 0;

    // if we have not reached the end of the string
    if (*str)
    {
        // recur for the node corresponding to next character in
        // the string and if it returns 1, delete current node
        // (if it is non-leaf)
        if (*curr != NULL && (*curr)->character[*str - 'a'] != NULL &&
            deletion(&((*curr)->character[*str - 'a']), str + 1) &&
            (*curr)->isLeaf == 0)
        {
            if (!haveChildren(*curr))
            {
                free(*curr);
                (*curr) = NULL;
                return 1;
            }
            else {
                return 0;
            }
        }
    }

    // if we have reached the end of the string
    if (*str == '\0' && (*curr)->isLeaf)
    {
        // if current node is a leaf node and don't have any children
        if (!haveChildren(*curr))
        {
            free(*curr); // delete current node
            (*curr) = NULL;
            return 1; // delete non-leaf parent nodes
        }

        // if current node is a leaf node and have children
        else
        {
            // mark current node as non-leaf node (DON'T DELETE IT)
            (*curr)->isLeaf = 0;
            return 0;      // don't delete its parent nodes
        }
    }

    return 0;
}

// Trie Implementation in C - Insertion, Searching and Deletion
int main()
{
    struct Trie* head = getNewTrieNode();

    insert(head, "hello");
    printf("%d ", search(head, "hello"));       // print 1

    insert(head, "helloworld");
    printf("%d ", search(head, "helloworld"));  // print 1

    printf("%d ", search(head, "helll"));       // print 0 (Not present)

    insert(head, "hell");
    printf("%d ", search(head, "hell"));        // print 1

    insert(head, "h");
    printf("%d \n", search(head, "h"));         // print 1 + newline

    deletion(&head, "hello");
    printf("%d ", search(head, "hello"));       // print 0 (hello deleted)
    printf("%d ", search(head, "helloworld"));  // print 1
    printf("%d \n", search(head, "hell"));      // print 1 + newline

    deletion(&head, "h");
    printf("%d ", search(head, "h"));           // print 0 (h deleted)
    printf("%d ", search(head, "hell"));        // print 1
    printf("%d\n", search(head, "helloworld")); // print 1 + newline

    deletion(&head, "helloworld");
    printf("%d ", search(head, "helloworld"));  // print 0
    printf("%d ", search(head, "hell"));        // print 1

    deletion(&head, "hell");
    printf("%d\n", search(head, "hell"));       // print 0 + newline

    if (head == NULL)
        printf("Trie empty!!\n");               // Trie is empty now

    printf("%d ", search(head, "hell"));        // print 0




//HERE IS WHERE THE SEGMENTATION FAULT ISSUE STARTS

    char str[100];
    int i=0;
    scanf("%s",str);
    for(i=0;i<strlen(str);i++)
    str[i]=tolower(str[i]);
    puts(str);
    //SEGMENTATION FAULT OCCURS IN LINE BELOW
    insert(head,str);

}
```:
4

1 回答 1

2

当你从树中删除最后一个字符串时，你删除了它的所有祖先，包括根节点。这使得headNULL。然后你传递head给insertwhich 取消引用它。

您可以安排不删除根节点（并更改检测空树的方式），但解决此问题的另一种方法是除了中间节点之外还自动激活根节点insert 。

void insert(struct Trie **curr, const char* str) {
    while (1) {
        if (!*curr)
            *curr = getNewTrieNode();

        if (!*str)
            break;

        curr = &( curr->character[*str - 'a'] );
        ++str;
    }

    (*curr)->isLeaf = 1;
}

这将允许您更换

struct Trie* head = getNewTrieNode();

和

struct Trie* head = NULL;
于 2019-11-17T05:50:35.600 回答