返回信息流#define OK 1
#define ERROR 0
#define MAXKEYLEN 20 /*关键字最大长度+1*/
typedef struct KeysType /*定义关键字结点*/
{
char ch[MAXKEYLEN]; /*关键字数组*/
int length; /*关键字长度*/
}KeysType;
typedef struct Record /*定义叶子结点的指针指向的记录*/
{
KeysType key;
char noun[20];
char mean[30];
}Record;
typedef enum {LEAF,BRANCH} NodeKind; /*结点种类：{叶子，分支}*/
typedef struct TrieNode /*Trie键树类型*/
{
NodeKind kind;
union
{
struct ////////////////////*叶子结点*///////////////////////////
{
KeysType key; /*关键字数组*/
Record *infoptr; /*叶子结点的记录指针*/
}lf;
struct ////////////////////*分支结点*//////////////////////////
{
int num; /*本结点关键码个数*/
TrieNode *ptr[26]; /*指针数组*/
}bh;
};//union
}TrieNode,*TrieTree; //Trie树类型定义
/*-----------------------常规调用函数---------------------------*/
int order(char ch) /*子函数：字符&位置交接函数 */
{
if(ch>='a'&&ch<='z')
return ch-'a';
else if(ch>='A'&&ch<='Z')
return ch-'A';
else
return -1;/*不合法输入*/
}//order
/*-----------------------------操作一：插入单词------------------------------*/
void Insert(TrieTree &T){
FILE *fp;
Record *new_word=new Record;
KeysType k,k1;
TrieTree p,q,ap;
int i,j;
system("cls");
if((fp=fopen("word_lib","a"))==NULL){ /*若文件不存在，先建立一个新文件*/
printf("\n词库建立失败!\n");
getchar();
exit(1);
}
printf("\n请输入一个新单词:");
scanf("%s",new_word->key.ch);
new_word->key.length=strlen(new_word->key.ch);
printf("\n\n请输入新单词的音标:");
scanf("%s",new_word->noun);
printf("\n\n请输入新单词的解释:");
scanf("%s",new_word->mean);
k=new_word->key;
if(T==NULL) /*--------------------------空树--------------------------*/
{
T=(TrieTree)malloc(sizeof(TrieNode));
T->kind=BRANCH;
for(i=0;i<26;i++) /*初始化指针*/
T->bh.ptr[i]=NULL;
p=T->bh.ptr[order(k.ch[0])]=(TrieTree)malloc(sizeof(TrieNode));
p->kind=LEAF;
p->lf.key=k;
p->lf.infoptr=new_word;
}
else /*else0*/ /*---------------------------非空树---------------------------*/
{
for(p=T,i=0;p&&p->kind==BRANCH&&i<k.length;i++)
{
q=p;
p=p->bh.ptr[order(k.ch[i])];
}
i--;
if(p&&p->kind==LEAF&&(p->lf.key.length==k.length)&&(strcmp(p->lf.key.ch,k.ch)==0)){
printf("\n该单词已经存在!\n"); /*遇到叶子结点，T中存在该关键字*/
}
else{ /*else1*/ /*T中不存在该关键字，则执行插入操作*/
if(!p) /*情况一：分支为空*/
{
p=(TrieTree)malloc(sizeof(TrieNode));
q->bh.ptr[order(k.ch[i])]=p;
p->kind=LEAF;
p->lf.infoptr=NULL;
p->lf.key=k;
p->lf.infoptr=new_word;
}
else if(p->kind==LEAF) /*情况二：有不完全相同的叶子*/
{
k1=p->lf.key;
do
{
ap=q->bh.ptr[order(k.ch[i])]=(TrieTree)malloc(sizeof(TrieNode));
ap->kind=BRANCH;
for(j=0;j<26;j++) /*初始化指针*/
ap->bh.ptr[j]=NULL;
q=ap;
i++;
}while(order(k.ch[i])==order(k1.ch[i])); /*当单词前部分匹配时不断开拓分支，直到字母不匹配*/
q->bh.ptr[order(k1.ch[i])]=p;/*将原存在的前部分与输入单词字母相同的叶子关键点接到树上*/
p=q->bh.ptr[order(k.ch[i])]=(TrieTree)malloc(sizeof(TrieNode));
p->kind=LEAF;
p->lf.key=k;
p->lf.infoptr=new_word;
}//end elseif
}//end else1
}//end else0
if((fwrite(p->lf.infoptr,sizeof(Record),1,fp))!=1){
printf("\n文件写入错误！");
exit(1);
}
else
printf("\n保存成功!\n");
fclose(fp);
}//Insert
这是一条镜像帖。来源：北邮人论坛 / cpp / #29690同步于 2009/10/10
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
大家帮忙看看，下面关于trie树插入的算法正确吗？
camelBUPT
2009/10/10镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。