三元検索トライインサート機能の問題
-
21-12-2019 - |
質問
だから私は三文字検索トライを作ろうとしています。今、私はインサート機能に働いています。私は30年検索トライのオンラインの基本的な考え方を理解しました。 1つのルートノードに3つの葉があることを知っており、その文字がrootの前に来ると、左、右に、それがrootと一致する場合は中央の葉に行きます。だから私の主な目的は、ミススペルのユーザーが言葉を入力するという言葉を提案できるプログラムを作ることです。しかし現時点では、私は三年検索トライを作ることに取り組んでいます。私はTrieを使ってユーザーをチェックしている辞書を作成して次の最良の代替案を提案することを提案しました。しかし、今すぐは、いくつかの文字を3値トライに入力するのに取り組んでいて、それを表示するときにそれを順番に表示する必要があります。 私は真ん中の葉に関する私の論理を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を使用しています。私はディスプレイ関数を打つときに無限に入力した最後の文字を印刷するだけの問題が発生しました。 どんな助けに役立ちます! ありがとう!
解決
あなたの表示機能は間違っています。ループ状態はFalseに評価されません。
while(&(*head)->lokid!=NULL && &(*head)->hikid!=NULL)
.
これはあなたが望むものではありません。 &(*head)->lokid
または&(*head)->hikid
のどれもNULL
を評価することはできません。 head
がNULL
ではない場合、&(*head)->lokid
は*head
と同じアドレスとlokid
内のstruct tstree
のオフセットです。あなたのループには、条件が偽造される可能性があるアップデートステートメントさえ持っていないことに注意してください、そしてそれがbreak
を持っていない - それは運命づけられています。
実際には、すべてのループを必要としない。順番に印刷するには、これはすべて必要なのです。
void display(node *head) {
if (head) {
display(head->lokid);
printf("%c ", head->letter);
display(head->hikid);
}
}
.
node **
を渡すことは目的はありません(私はnode *
に変更しました)、戻り値はvoid
です。
更新
insert()
関数は正しいですが、main
で誤った変数を使用します。 insert()
からの再帰ベースのこの割り当ては意図しない動作を引き起こしています:
temp = *head = malloc(sizeof(node));
.
基本ケースを打つたびに、新しいノードを*head
とtemp
に割り当てて、以前にtemp
に格納されているものへの参照を失います。それからあなたはdisplay(temp)
を呼び出します。はい、あなたはトライを構築しますが、最後に挿入されたノードから始めて印刷しています - あなたが望むものではありません。
代わりに、Global変数display
を使用してhead
を呼び出す必要があります。これは、Trieの正しいルートです。
display(head);
.
挿入を呼び出すときに同じことが発生します。最後に追加されたノードで開始した新しい文字を挿入したくない場合は、ルートで起動します。代わりにmain()
を持つ必要があります。
insert(num, &head);
.
そして私たちがそれにある間、temp
は完全に不要です。必要ありません。 insert
は参照によってグローバルヘッドを操作します.temp
はここでは使用されていない(そして実際にはバグを導入しました)。
これらの2行をメインで変更するのは十分です。ここでそれをテストし、そしてそれは魅力のように機能します。