英语检索系统.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 DynamicSearchTable 2．主程序 Void main() { 初始化； do{ 接受命令（选择要使用的功能）； 处理命令； 判断是否继续操作； }while(命令”= =”继续”)； } 3．本程序有5个模块，Trie树的建立、查询、插入、删除、主函数，主函数运行时依次分别调用其他模块程序。 三、详细设计 1．Trie树结构图 Trie树为多叉树，从头结点到关键字K的叶子结点按指针逐层向下，trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。 2．关键字、结点类型 #define MAXKEYLEN 16 /*关键字的最大长度*/ typedef struct { char ch[MAXKEYLEN]; /*关键字*/ int num; /*关键字长度*/ }KeysType; /*关键字类型*/ typedef enum {LEAF,BRANCH}NodeKind; /*点种类：{叶子，分支}*/ typedef struct Record{ char voi[16]; /*单词发音*/ char che[100]; /*单词汉语解释*/ }Record; /*叶子结点中的记录类型*/ typedef struct TrieNode{ /*Trie树结点*/ NodeKind kind; union{ struct{KeysType k;Record *infoptr;}lf; /*叶子结点*/ struct{struct TrieNode *ptr[27];int num;}bh;/*分支结点*/ }m; }TrieNode,*TrieTree; /*键树类型*/ TrieTree Create_Branch(){ /*创建一个空分支结点*/ TrieNode *p; int i; p=(TrieNode*)malloc(sizeof(TrieNode));/*生成一个分支结点*/ p-kind=BRANCH;/*结点类型*/ for(i=0;i27;i++) p-m.bh.ptr[i]=NULL; p-m.bh.num=0; return(p); }/*Create_Banch*/ 3．建树模块及算法： Void InitDSTable(DT);