英语检索系统.doc

一、需求分析1实验题目及功能要求：英语词典检索，建立英语词汇表，通过辨别输入是否合法后能够实现快速查询、插入、删除，所以建树即确定程序的数据结构时本程序的基础和关键。2输入为小写字母时为合法输入，输出结果包含单词的英语形式和汉语释义以及发音3测试数据（附后）二、概要设计1抽象数据类型的定义ADT DynamicSearchTable数据对象D: 是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可唯一表识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P： InitDSTable(&DT); 操作结果：构造一个空的动态查找表DT. DestroyDSTable(&DT);初始条件：动态查找表DT存在。操作结果：销毁动态查找表DT。 SearchDSTable(DT，key)； 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。InsertDSTable(&DT，e)； 初始条件：动态查找表DT存在，e为待输入的数据元素。 操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。DeleteDSTable(&DT,key)； 初始条件：动态查找表DT存在，key为和关键字类型相同的定值。 操作结果：若DT中存在其关键字等于key的数据元素，则删除之。TraverseDSTable(DT，Visit()； 初始条件：动态查找表DT存在，Visit是对结点操作的应用函数。 操作结果：按某种次序对的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败。则操作失败。ADT DynamicSearchTable2主程序Void main()初始化；do 接受命令（选择要使用的功能）； 处理命令； 判断是否继续操作；while(命令”= =”继续”)；3本程序有5个模块，Trie树的建立、查询、插入、删除、主函数，主函数运行时依次分别调用其他模块程序。 查找Search Trie创建Trie树CreatTrieMain 函数插入Insert Trie删除Delete Trie三、详细设计1Trie树结构图 Trie树为多叉树，从头结点到关键字K的叶子结点按指针逐层向下，trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。创建一个头结点 i=0输入单词并计算单词长度判断合法性寻找插入位置判断是否继续关键字相应位置指针为空创建一个分支结点，i+i=关键字输入结束单词不合法，重新输入i+叶子结点插入到分支结点的第一个指针域开始创建一个关键字为K的叶子结点2关键字、结点类型#define MAXKEYLEN 16 /*关键字的最大长度*/ typedef struct char chMAXKEYLEN; /*关键字*/ int num; /*关键字长度*/ KeysType; /*关键字类型*/typedef enum LEAF,BRANCHNodeKind; /*点种类：叶子，分支*/typedef struct Record char voi16; /*单词发音*/ char che100; /*单词汉语解释*/ Record; /*叶子结点中的记录类型*/typedef struct TrieNode /*Trie树结点*/ NodeKind kind; union structKeysType k;Record *infoptr;lf; /*叶子结点*/ structstruct TrieNode *ptr27;int num;bh;/*分支结点*/ m;TrieNode,*TrieTree; /*键树类型*/TrieTree Create_Branch() /*创建一个空分支结点*/ TrieNode *p; int i; p=(TrieNode*)malloc(sizeof(TrieNode);/*生成一个分支结点*/ p-kind=BRANCH;/*结点类型*/ for(i=0;im.bh.ptri=NULL; p-m.bh.num=0; return(p);/*Create_Banch*/3建树模块及算法：Void InitDSTable(&DT); /*构造一个空的动态查找表DT.*/Void SearchDSTable(DT，key) /*动态查找表DT存在，key为和关键字类型相同的给定值*/Void InsertDSTable(&DT，e) /*动态查找表DT存在，e为待输入的数据元素*/Void TraverseDSTable(DT，Visit() /*动态查找表DT存在，Visit是对结点操作的应用函数。*/其中部分操作的算法如下： TrieTree CreateTree() /*创建一个键树，返回头指针T*/ T=Create_Branch(); /*创建头结点*/ while(1) /*创建T树的输入控制语句*/ TrieNode *S; S=(TrieNode *)malloc(sizeof(TrieNode); /*分配空间*/ S-kind=LEAF; /*输入结点类型*/ scanf(%s,S-m.lf.k.ch); /*输入一个单词*/ while(1) /*判断输入是否合法语句*/ if(English(S-m.lf.k.ch,S-m.lf.k.num) /*合法则跳出判断合法语句while*/break; else /*输入不和法*/ if(strcmp(S-m.lf.k.ch,$)=0) break; /*输入为$跳出判断合法语句while*/ else free(S); /*释放空间*/ S=(TrieNode *)malloc(sizeof(TrieNode); /*重新分配空间*/ scanf(%s,S-m.lf.k.ch); /*重新输入*/ /* else*/ /*else*/ /*while*/ if(strcmp(S-m.lf.k.ch,$)=0) free(S);break; /*输入为$创建T树的输入控制语句输入结束*/ scanf(%s%s,S-ptr-voi,S-ptr-che); /*输入单词发音和释义*/ for(P=T,i=0;im.lf.k.num;P=P-m.bh.ptrord(S-m.lf.k.chi),+i)/*寻找插入位置*/ if(!P-m.bh.ptrord(S-m.lf.k.chi) P-m.bh.ptrord(S-m.lf.k.chi)=Create_Branch(); +(P-m.bh.num); /*if*/ P-m.bh.ptr0=S; /*插入叶子结点*/ /*while*/return(T); /*返回头指针*/*CreateTrie*/四、程序设计与程序调试：1程序设计：本程序分为五个模块，分别为：建树模块，查找模块，插入模块，删除模块和主程序模块。因为还需要自己建立词汇表，所以开始考虑程序所用数据结构时，又从快速查找且便于插入和删除的角度看，为了尽量减少时间复杂度，采用便于检索的Trie树结构。在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。如：若关键字长度最大是5，则利用trie树，利用5次比较可以从26511881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行log2265=23.5次比较。2程序调试： 在程序调试过程中，除了一些输入性错误外，出现模块调试没有错误，总程序调试出现错误的情况，发现是有些前后变量定义出错；后来在程序大致可以运行时加入判断输入单词合法与否的程序，中间有输入非法字符不识别或者不跳出的情况，又有输入跳出标示符，但是回不到主函数的情况，后来设计两个循环，在一个循环下判断出非法字符后再判断是否跳出，输入跳出标示符时运行两次跳出，先跳出循环，再跳出建树进入主函数；主函数中开始的选择是否继续操作时，没有停顿直接结束，后来getchar()操作改为scanf()操作，且将while()语句的循环条件从非改为等于，就出现了判断是否继续操作的命令。五、测试结果:1本模块测试结果：输入单词 an 输入输入单词发音和释义an yige输入单词 be 输入输入单词发音和释义 bi shi 输入单词 car 输入输入单词发音和释义ka qiche 2.总程序测试输入单词 an 输入输入单词发音和释义an yige输入单词 be 输入输入单词发音和释义 bi shi 输入单词 car 输入输入单词发音和释义ka qiche 输入1（或其他非小写字母外字符），此单词不合法,请重新输入。输入，请输入要使用的功能：1：查询、2：插入、3:删除 继续输入1（或其他非小写字母外字符）输入要查找的单词； 继续输入一个单词，若存在则输出为：它的发音和释义； 若不存在输出为：查无此词。 然后就会弹出：是否要继续操作：Y/N? 输入Y则输出：请输入要使用的功能：1：查询、2：插入、3：删除 输入其他则执行结束。六、实验总结： 检索系统运用Trie树结构，可以便于进行插入和删除，只需要相应地增加和删除一些分支结点。在设计当中增加了一些判断输入字符是否合法的程序可以对检索系统进行完善。 通过这次实验，我不仅又对学过的知识进行了回顾，并且又学会了不太了解的Trie树，在不断的思路更新中也进一步了解了平衡二叉树和二叉排序树等内容。 对于此英语检索系统，还不能进行大量的词汇库建立和词汇调用，还不能进行双语查询。七、附录：#define MAXKEYLEN 16 /*关键字的最大长度*/ typedef struct char chMAXKEYLEN; /*关键字*/ int num; /*关键字长度*/ KeysType; /*关键字类型*/typedef enum LEAF,BRANCHNodeKind; /*点种类：叶子，分支*/typedef struct Record char voi16; /*单词发音*/ char che100; /*单词汉语解释*/ Record; /*叶子结点中的记录类型*/typedef struct TrieNode /*Trie树结点*/ NodeKind kind; union structKeysType k;Record *infoptr;lf; /*叶子结点*/ structstruct TrieNode *ptr27;int num;bh;/*分支结点*/ m;TrieNode,*TrieTree; /*键树类型*/int ord(char t)/*计算t在含（）的27个字符表中的位置*/ int n; n=t-96; return(n);/*ord*/int English(char *s,int n) /*判断输入是否合法*/ int i; for(i=0;in&si=97;i+); if(i!=n) return(0); else return(1); /*English*/TrieTree Create_Branch() /*创建一个空分支结点*/ TrieNode *p; int i; p=(TrieNode*)malloc(sizeof(TrieNode);/*生成一个分支结点*/ p-kind=BRANCH;/*结点类型*/ for(i=0;im.bh.ptri=NULL; p-m.bh.num=0; return(p);/*Create_Banch*/TrieTree CreateTree() /*创建一个键树*/ TrieNode *P, *T; int i ; T=Create_Branch(); /*创建头结点*/ while(1) TrieNode *S; S=(TrieNode *)malloc(sizeof(TrieNode); S-kind=LEAF; /*结点类型*/ printf(输入一个单词:n); scanf(%s,S-m.lf.k.ch); while(1) S-m.lf.k.num=strlen(S-m.lf.k.ch)； / *计算单词长度*/ if(English(S-m.lf.k.ch,S-m.lf.k.num) /*判断输入是否合法*/ break; else if(strcmp(S-m.lf.k.ch,)=0) break; /*输入为输入结束*/ else free(S); S=(TrieNode *)malloc(sizeof(TrieNode); printf(此单词不合法,请重新输入n); scanf(%s,S-m.lf.k.ch); if(strcmp(S-m.lf.k.ch,)=0) free(S);break; /*输入为输入结束*/ printf(输入单词发音和释义:n);