使用c ++实现实现 [英] Trie Implementation with c++
本文介绍了使用c ++实现实现的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
你好我的朋友
i有关于实现的问题Trie with C ++
项目包括在内，必须有以下
1。创建空心树的能力
2.能够插入新的字符串树
3.能够在树中搜索特定字符串
4.能够找到以特定子串开头的所有字符串
5.找到包含特定字符串的以下字符串。
6.查找的能力所有以特定子字符串结尾的字符串。
7.列出树中的所有字段
8.查看树
9.退出程序
现在当我运行2个选项时，一个单词包含字符串，数字打印字母和来自未知的数字
下一个问题：使用选项4,5的选项和6做。请在实践中注明
以及如何查看树？
请帮助我，我需要这个代码.tanks
#include< stdio.h>
#include< stdlib.h>
#include< string.h>
#include< malloc.h>
#define ARRAY_SIZE（a）sizeof（a）/ sizeof（a [0]）
// 字母大小（符号数）
#define ALPHABET_SIZE（26 ）
// 将关键当前字符转换为索引// tabdile kelide charachtere jari be index
// 仅使用'a'到'z'和小写// faghat az a ta z va horofe kochak estefade mikonad
＃define CHAR_TO_INDEX（c）（（int）c - （int）'a'）
static int test;
// trie node
typedef struct trie_node trie_node_t;
struct trie_node
{
int 值;
trie_node_t * children [ALPHABET_SIZE];
};
// trie ADT
typedef struct trie trie_t;
struct trie
{
trie_node_t * root;
int count;
};
// 返回新的trie节点（初始化为NULL）// gereye derakhte jadid ra bar migardanad（meghdar dehie avalie ba Null）
trie_node_t * getNode（ void ）
{
trie_node_t * pNode = NULL ;
pNode =（trie_node_t *）malloc（ sizeof （trie_node_t））; // meghdare hafeze dar tire_node_t ra bar hasbe byte ba estefade az malloc be barname takhsis midahad，va noe in eshare gar az node node_trie_t mibashad // 1 Argoman（meghdar fazaye morede niaz）ra bar migardanad（（meghdar fazaye moshakhasi ra barname bar migardanad））
// size of = >如果如果（！pNode） // hich hafezei be pnode takhsis dade nashode
{
printf（ \ n \ n takhsise faza anjam nashod !!）;
return NULL;
}
if （pNode）
{
int 我;
pNode-> value = 0 ;
for （i = 0 ; i < ALPHABET_SIZE; i ++）
{
pNode-> children [i] = NULL;
}
}
return pNode;
}
// 初始化trie（root是虚节点）
void initialize（trie_t * pTrie） // meode meghdar dehie avalie az noe void ba 1 meghdar az noe eshare gar be name pTrie。
{
pTrie-> root = getNode（）;
pTrie-> count = 0 ;
}
// 如果不存在，请将密钥插入trie
// 如果密钥是trie节点的前缀，则只标记叶节点
void insert（trie_t * pTrie， char key []）
{
int 级别;
int length = strlen（key）; // key = arayei az charechter ha，tole key ra dar lengh mirizim
int index;
trie_node_t * pCrawl;
pTrie-> count ++;
pCrawl = pTrie-> root;
for （level = 0 ; level < 长度;级别++）
{
index = CHAR_TO_INDEX（key [level]）;
if （！pCrawl-> children [index]）
{
pCrawl-> children [index] = getNode（ ）;
}
pCrawl = pCrawl-> children [index];
}
// 将最后一个节点标记为叶子// alamat gozarie akharie gereh是onvane barg
pCrawl-> value = pTrie-> count;
}
// 如果密钥出现在trie中，则返回非零
int search（trie_t * pTrie， char key []）
{
int 级别，i;
int length = strlen（key）;
int index;
trie_node_t * pCrawl;
pCrawl = pTrie-> root;
for （level = 0 ; level < 长度;级别++）
{
index = CHAR_TO_INDEX（key [level]）;
if （！pCrawl-> children [index]）
{
返回 0 ;
}
pCrawl = pCrawl-> children [index];
}
return （ 0 ！= pCrawl&& ; pCrawl-> value）;
}
// 让前缀遍历trie的子树以获取并打印建议
void 遍历（trie_node_t * pCrawl， char key []，< span class =code-keyword> int index）
{
int i;
char * temp;
if （！pCrawl）
{
返回;
}
if （pCrawl-> value！= 0&& pCrawl！= NULL）
{
printf（ ％s \ n，key）;
}
for （i = 0 ; i< 26 ; i ++）
{
temp =（ char *）malloc（ sizeof （ char ）* strlen（key）+2）;
strcpy（temp，key）;
temp [strlen（key）] =（ char ）（97 + i）;
temp [strlen（key）+1] = ' &＃92&＃48';
if （pCrawl-> children [i]！= NULL）
traverse（pCrawl-> children [i]，temp，i ）;
free（temp）;
}
}
// 向下走trie到前缀，然后使用遍历函数查找建议
// harkat in derakht ta pishvand va sepas peyda kardane pishnehad ba estefade az tabe'e traverse
int 建议（trie_t * pTrie， char key []） //
{
int 级别，i;
int length = strlen（key）;
int index;
trie_node_t * pCrawl;
pCrawl = pTrie-> root;
if （strcmp（key， ） ）== 0 ）
{
printf（ < span class =code-string>输入为NULL !!）;
return 0 ;
}
for （level = 0 ; level < length; level ++）
{
index = CHAR_TO_INDEX（key [level]）;
if （！pCrawl-> children [index]）
{
printf（< span class =code-string> 前缀不存在）;
return 0 ;
}
pCrawl = pCrawl-> children [index];
}
遍历（pCrawl，key，index）;
}
// 检查字符串是否仅包含小写
/ * int check（char key []）
{
int i，status;
i = 0;
status = -1;
while（key [i]！='&＃92&＃48'）
{
if（！（key [i]< ='z'&& key [i]> ='a'））
{status = 0;
返回状态;
}
i ++;
}
status = 1;
返回1;
} * /
// 驱动程序
int main（）
{
int 我，状态，提示;
char inputString [ 30 ];
prompt = 1 ;
trie_t trie;
initialize（& trie）;
while （prompt！= ' 4' ）
{
printf（ \ n按1将字符串插入数据库\ n按2查找建议\ n按3搜索字符串\\\
Press 4退出\ n）;
scanf（ ％d，& prompt）;
switch （提示）
{
case 1 ：printf（ \ n请输入字符串\ n< /跨度>）;
scanf（ ％s，inputString）;
if （strcmp（inputString， ） ）== 0 ）
{
printf（ < span class =code-string>不允许使用空字符串）;
break ;
}
/ * if（check（inputString）== 0）
{
printf（\ nSorry只允许使用小写字母!! \ n）;
休息;
} * /
insert（& trie，inputString）;
strcpy（inputString， ）;
break ;
case 2 ：printf（ \ n请输入模式\ n）;
scanf（ ％s，inputString）;
if （strcmp（inputString， ） ）== 0 ）
{
printf（ < span class =code-string>不允许使用空字符串）;
break ;
}
/ * if（check（inputString）== 0）
{
printf（\ nSorry只允许使用小写字母!! \ n）;
休息;
} * /
printf（ \ n模式为:: \\ \
）;
建议（& trie，inputString）;
// strcpy（inputString，）;
断裂;
case 3 ：printf（ \ n请输入要搜索的字符串\ n）;
scanf（ ％s，inputString）;
if （strcmp（inputString， ） ）== 0 ）
{
printf（ < span class =code-string>不允许使用空字符串）;
break ;
}
/ * if（check（inputString）== 0）
{
printf（\ nSorry只允许使用小写字母!! \ n）;
休息;
} * /
status = search（& trie，inputString）;
strcpy（inputString， ）;
if （status == 0 ）
printf（ \ n您正在寻找的字符串不存在于数据库中\ n）;
else
printf（ 该字符串存在于数据库）中;
break ;
case 4 ： return 0 ;
默认：printf（ 无效选项！ ！请再试一次!!!! \ n \ n）;
break ;
}
}
return 0 ;
}
解决方案
这不是一个很好的问题。首先，您需要解释您显示的代码与您的问题有什么关系？你试图实现什么，如何，你尝试了什么，你期望什么，你得到了什么，为什么你觉得这是错的。此外，我们无法在不知道您的平台是什么，您正在使用什么UI或图形库，视图需要什么等等的情况下讨论视图树主题。
快速查看代码表明您最好重新开始。首先，你不应该把和I / O放在像树这样的类中，没有printf，就是这样。您需要创建一个不同的树和TreeNode类（请注意，您的标记表示您使用的是C ++编写，而不是！ ），并且所有方法应该是类实例或静态方法，并且这些类应该完全从I / O中抽象出来。例如，您可以使用添加节点的方法，但是注释字符串数据的输入应该在某些测试/演示/调试类或函数中完成。
使用那些案例1，案例2，案例4是不可接受的。他们不会告诉阅读代码的人。至少，使用一些枚举类型。无论如何，它不应该在与树相关的类中。另外，避免所有那些立即常量，除了大多数基本常量，如0,1，null等。所有那些26，'\ 0'，97，硬编码字符串 - 非常糟糕，杀死代码的所有可维护性。至少声明显式的const对象。不要显示所有注释掉的代码，尊重读者...
-SA
告诉你的问题，你在这里展示给我们的代码不是你的，而是别人的代码，而你只是想找一些东西作为你的作业。
但这不像是在这里工作。只给你一段代码，我们不会帮你。如果你可以做你的功课，但只是遇到其中一个问题的特殊问题，那么你可以在这里发帖，并且很可能得到帮助，了解你需要的主题。但是，如果你根本不知道如何解决你的家庭作业，我认为你在这个过程中浪费你的时间，至少在这一刻。重新开始，尝试了解基础知识。从那里开始，处理更复杂的事情。在程序中，没有办法只是一点点理解事物。要么你理解与否 - 如果没有，你永远不会成为一名软件开发人员。
对不起，但在这个阶段没有人可以帮助你，除了你自己
hello my friends
i have a problem about implementation Trie with C++
the project which is included,must have the following
1. Ability to create a hollow tree
2. Ability to insert a new string tree
3. Ability to search for a specific string in a tree
4. The ability to find all the strings that begin with a particular substring
5. Find the following string that contains a specific string.
6. The ability to find all strings that end in a particular substring.
7. List all fields in the tree
8. View tree
9. Exit the program
now when I run 2 options, with a word that contains the string, number printing letters and numbers that come from unknown
next question : What options using option 4, 5 and 6 do. Please indicate in practice
and how can i view tree??
please Help me,I need this code.tanks
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<malloc.h>
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
// Alphabet size (# of symbols)
#define ALPHABET_SIZE (26)
// Converts key current character into index//tabdile kelide charachtere jari be index
// use only 'a' through 'z' and lower case // faghat az a ta z va horofe kochak estefade mikonad
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
static int test;
// trie node
typedef struct trie_node trie_node_t;
struct trie_node
{
int value;
trie_node_t *children[ALPHABET_SIZE];
};
// trie ADT
typedef struct trie trie_t;
struct trie
{
trie_node_t *root;
int count;
};
// Returns new trie node (initialized to NULLs)//gereye derakhte jadid ra bar migardanad ( meghdar dehie avalie ba Null)
trie_node_t *getNode(void)
{
trie_node_t *pNode = NULL;
pNode = (trie_node_t *)malloc(sizeof(trie_node_t));//meghdare hafeze dar tire_node_t ra bar hasbe byte ba estefade az malloc be barname takhsis midahad,va noe in eshare gar az node node_trie_t mibashad//1 Argoman (meghdar fazaye morede niaz) ra bar migardanad ((meghdar fazaye moshakhasi ra be barname bar migardanad))
//size of => tole motaghayer va ya noe motaghayer ra bar hasbe byte mitavan be dast avard.
if(!pNode)//hich hafezei be pnode takhsis dade nashode
{
printf("\n\n takhsise faza anjam nashod !! ");
return NULL;
}
if( pNode )
{
int i;
pNode->value = 0;
for(i = 0; i < ALPHABET_SIZE; i++)
{
pNode->children[i] = NULL;
}
}
return pNode;
}
// Initializes trie (root is dummy node)
void initialize(trie_t *pTrie) // methode meghdar dehie avalie az noe void ba 1 meghdar az noe eshare gar be name pTrie.
{
pTrie->root = getNode();
pTrie->count = 0;
}
// If not present, inserts key into trie
// If the key is prefix of trie node, just marks leaf node
void insert(trie_t *pTrie, char key[])
{
int level;
int length = strlen(key);//key= arayei az charechter ha, tole key ra dar lengh mirizim
int index;
trie_node_t *pCrawl;
pTrie->count++;
pCrawl = pTrie->root;
for( level = 0; level < length; level++ )
{
index = CHAR_TO_INDEX(key[level]);
if( !pCrawl->children[index] )
{
pCrawl->children[index] = getNode();
}
pCrawl = pCrawl->children[index];
}
// mark last node as leaf//alamat gozarie akharie gereh be onvane barg
pCrawl->value = pTrie->count;
}
// Returns non zero, if key presents in trie
int search(trie_t *pTrie, char key[])
{
int level,i;
int length = strlen(key);
int index;
trie_node_t *pCrawl;
pCrawl = pTrie->root;
for( level = 0; level < length; level++ )
{
index = CHAR_TO_INDEX(key[level]);
if( !pCrawl->children[index] )
{
return 0;
}
pCrawl = pCrawl->children[index];
}
return (0 != pCrawl && pCrawl->value);
}
//after having the prefix traverse the sub tree of trie to fetch and print the suggestions
void traverse(trie_node_t *pCrawl, char key[],int index)
{
int i;
char *temp;
if(!pCrawl)
{
return ;
}
if(pCrawl->value!=0&&pCrawl!=NULL)
{
printf("%s\n",key);
}
for(i=0;i<26;i++)
{
temp=(char *)malloc(sizeof(char)*strlen(key)+2);
strcpy(temp,key);
temp[strlen(key)]=(char)(97+i);
temp[strlen(key)+1]='\0';
if(pCrawl->children[i]!=NULL)
traverse(pCrawl->children[i], temp,i);
free(temp);
}
}
//travel down the trie upto the prefix and then look for suggestion using traverse function
// harkat in derakht ta pishvand va sepas peyda kardane pishnehad ba estefade az tabe'e traverse
int suggestions(trie_t *pTrie, char key[]) //
{
int level,i;
int length = strlen(key);
int index;
trie_node_t *pCrawl;
pCrawl = pTrie->root;
if(strcmp(key,"")==0)
{
printf("The input is NULL!!");
return 0;
}
for( level = 0; level < length; level++ )
{
index = CHAR_TO_INDEX(key[level]);
if( !pCrawl->children[index] )
{
printf("Prefix is not present");
return 0;
}
pCrawl = pCrawl->children[index];
}
traverse(pCrawl, key,index);
}
//checks whether the string contains lowercase only
/*int check(char key[])
{
int i,status;
i=0;
status=-1;
while(key[i]!='\0')
{
if(!(key[i]<='z'&&key[i]>='a'))
{ status=0;
return status;
}
i++;
}
status =1;
return 1;
}*/
// Driver
int main()
{
int i,status,prompt;
char inputString[30];
prompt=1;
trie_t trie;
initialize(&trie);
while(prompt!='4')
{
printf("\nPress 1 to insert a string into the database\nPress 2 to look for suggestions\nPress 3 to search a string\nPress 4 to exit\n");
scanf("%d",&prompt);
switch(prompt)
{
case 1 : printf("\nPlease enter the string\n");
scanf("%s",inputString);
if(strcmp(inputString,"")==0)
{
printf("Empty strings are not allowed");
break;
}
/* if(check(inputString)==0)
{
printf("\nSorry Only lower case alphabets are allowed !!\n");
break;
}*/
insert(&trie, inputString);
strcpy(inputString,"");
break;
case 2 : printf("\nPlease enter the pattern\n");
scanf("%s",inputString);
if(strcmp(inputString,"")==0)
{
printf("Empty strings are not allowed");
break;
}
/* if(check(inputString)==0)
{
printf("\nSorry Only lower case alphabets are allowed !!\n");
break;
}*/
printf("\nThe patterns are ::\n");
suggestions(&trie,inputString);
// strcpy(inputString,"");
break;
case 3 : printf("\nPlease enter the string to be searched\n");
scanf("%s",inputString);
if(strcmp(inputString,"")==0)
{
printf("Empty strings are not allowed");
break;
}
/* if(check(inputString)==0)
{
printf("\nSorry Only lower case alphabets are allowed !!\n");
break;
}*/
status=search(&trie,inputString);
strcpy(inputString,"");
if(status==0)
printf("\nThe string you are looking is not present in the databse\n");
else
printf("The string is present in the database");
break;
case 4 : return 0;
default: printf("Invalid option!!Please try again!!!!\n\n");
break;
}
}
return 0;
} 解决方案
This is not a very well posed question. First of all, you need to explain how is the code you show related to your question? What did you try to achieve, how, what did you try, what did you expect and what did you get instead, why do you feel it's wrong. Also, we cannot discuss "view tree" topic without knowing what is your platform, what UI or graphics library you are using, what's required for the view, etc.
The quick look at your code suggests that you should better start over. First of all, you should not put and I/O in the classes like tree, noprintf, nothing like that. You need to create a distinctTreeandTreeNodeclasses (note that your tag says you are writing in C++, not!), and all the methods should be either class instance or static methods, and those classes should be totally abstracted from I/O. For example, you can have a method for adding a node, but the input of the note string data should be done in some test/demo/debug class or function.
Using those "case 1", "case 2", "case 4" is unacceptable. They don't tell anything to the one reading your code. At least, use some enumeration type. Anyway, it should not be in your tree-related classes. Also, avoid all those immediate constants, except most fundamental ones, like 0, 1, null, etc. All those 26, '\0', 97, hard-coded strings — are very bad, kills all the maintainability of your code. At least declare the explicitconstobjects. Don't show all that commented-out code, respect the reader just a bit…
—SA
Telling from your questions, the code you are showing us here is not yours, but somebody else's and you are just looking for something to turn in as your homework.
But that is not like things work here. We would not do you a favor by just giving you a piece of code. If you can do your homework, but just have a particular problem with one of the points, then you can post here and most likely get help understanding the subject you need. If, however, you have no clue at all how to solve your homework, I think you are wasting your time in that course, at least at this moment. Start all over again and try to get an understanding of the basics. From there, work on to more complex things. In program there is no way of understanding things just "a little". Either you understand it or not - and if not, you will never succeed in being a software developer.
Sorry, but at this stage nobody can help you, except yourself.
这篇关于使用c ++实现实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
