2

所以我正在尝试进行三元搜索尝试。现在，我只处理插入功能。我已经在线了解了三元搜索树的基本思想。我知道一个根节点有 3 个叶子，如果字符出现在根之前，它会向左，之后 - 右，如果它与根匹配，它会进入中间叶子。所以我的主要目标是制作一个程序，可以为拼写错误的用户输入的单词建议单词。但目前我只是在做三元搜索尝试。我使用 trie 制作字典，使用它检查用户输入的单词以建议下一个最佳选择。但是现在，只是将一些字符输入到三元树中，当我显示它时，它应该按顺序显示。我不是 100% 确定我关于中间叶子的逻辑。现在我的程序在运行时，给我一些与输入的最后一个字符有关的垃圾无限值。我不知道我哪里出错了。有人可以指出我在哪里犯了错误吗？另外，你能告诉我我写的任何逻辑是否错误吗？我的意思是，你不必给我代码或任何东西，因为一旦我知道我哪里出错了，我觉得我有能力自己做，但是如果有人可以帮助我找到我的错误，那会帮助我很多！

整个代码：

#include <stdio.h>
#include <stdlib.h>  //Because usage of malloc gives warnings without this header
typedef struct tstree
{
    struct tstree *lokid;
    struct tstree *hikid;
    struct tstree *eqkid;
    char letter;
}node;
node *head = NULL;
int count = 0;
int insert(char x, node **head)
{
    if (*head==NULL)            //If it's the first element
    {
        *head = malloc(sizeof(node));   
        (*head)->letter = x;
        count++;            
        (*head)->lokid = (*head)->hikid = (*head)->eqkid = NULL;            //Assign all 3 to null initially
    }
    else if ((*head)->letter == x)          //If equal, insert below
    insert(x , &((*head)->eqkid) );
    else if ((*head)->letter > x)   //If inserted char comes before current val, insert to left
    insert(x,&(*head)->lokid);
    else
    insert(x,&(*head)->hikid);              //Else to the right
    return 0;
}
void display(node *head)
{
    if(head)
    {
        display(head->lokid);               //print in infix order
        printf("%c ",head->letter);
        display(head->hikid);
    }
    //return 0;
}
int main()
{   
    int op;
    char num;
    printf("\nWelcome Fabiz. Hope it meets your expectations!\n");
    while(1)
    {
        printf("\n1. To insert an element\n2. Display the tree\n3. Exit\nOption :");
        scanf("%d",&op);
        switch(op)
        {
            case 1:
            {
                system("clear");
                printf("\nEnter the element : ");
                scanf(" %c",&num);
                insert(num,&head);
                break;
            }
            case 2:
            {
                system("clear");
                if(count == 0)
                printf("\nEmpty tree\n");
                else
                {
                    printf("Display in order..\n");
                    display(head);
                }
                break;
            }
            default: exit(0);
        }
    }
    return 0;
}

我正在使用 Geany 文本编辑器，并且在 Linux Mint 上。我遇到了一个问题，当我点击显示功能时，编译器只会打印我无限输入的最后一个字符。任何帮助都会非常有帮助！谢谢！

4

1 回答 1

3

你的显示功能不对。循环条件永远不会计算为假：

while(&(*head)->lokid!=NULL && &(*head)->hikid!=NULL)

这不是你想要的。没有一个&(*head)->lokid或&(*head)->hikid将永远评估为NULL. 如果headis not NULL， then&(*head)->lokid只是相同的地址*head加上 a 中的偏移lokid量struct tstree。请注意，您的循环甚至没有可能使条件为假的更新语句，并且它没有任何break- 它注定要失败。

事实上，你甚至根本不需要循环。要按顺序打印，这就是您所需要的：

void display(node *head) {
    if (head) {
        display(head->lokid);
        printf("%c ", head->letter);
        display(head->hikid);
    }
}

请注意，传递 a node **（我将其更改为 a node *）没有任何目的，返回值应该是void.

更新

你的insert()函数是正确的，但是你在main. 递归基础中的此分配insert()导致意外行为：

temp = *head = malloc(sizeof(node));

请注意，每次遇到基本情况时，都会为 and 分配一个新节点*head，temp从而失去对temp之前存储的任何内容的引用。然后你打电话display(temp)。是的，您构建了 trie，但您从最后插入的节点开始打印它 - 不是您想要的。

相反，您应该display使用全局变量调用head，这是您的 trie 的正确根：

display(head);

调用 insert 时也会发生同样的情况。您不想从最后添加的节点开始插入新字母，而是希望从根节点开始添加它。main()应该有这个：

insert(num, &head);

当我们这样做时，请注意这temp是完全没有必要的。你不需要它。insert通过引用操作全局头部，temp在这里没有用（实际上它引入了一个错误）。

在 main 中更改这 2 行就足够了，在这里进行了测试，它的工作原理就像一个魅力。

于 2014-02-26T17:22:23.497 回答