数据结构课程设计课程题目：电子小字典姓名：. 小组成员： . 系别：计算机科学系专业：. 学号：. 指导老师：仓老师贵州航天职业技术学院名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 目录1.引言.1.1 2.题目.2.1 3.设计思想 .3.1 问题描述 .3.1.1 系统设计说明 .3.1.2 4.设计功能 .4.1 5.功能实现 .5.1 6.测试.6.1 7.小结.7.1 8.参考文献 .8.1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 1.引言目前由于电子小字典具有查找快速，删除、添加等操作等功能，电子小字典的需求越来越大，电子字典要求存储器的容量非常大，因此，合理的数据结构是十分必要的。本次试验在开发多功能电子字典产品中对字典数据存储方法做了全面的研究，提出了使用二叉排序树结构和查找的方法，并在微型计算机上用c 语言实现该结束。2.题目电子小字典设计要求：利用字典的下标运算建立一个微型电子字典，实现字典的加入、查找、删除等操作，并能在屏幕上输出操作前后的结果。3.设计思想一、问题描述基本要求：1) 本系统要能够实现字典的加入、查找、删除等操作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - 2) 作为一个完整的系统，应具有友好的界面和较强的容错能力。二、系统设计说明1、数据结构设计(1) 系统用到哪些数据类型。系统用到的数据类型有：1、基本数据类型：整型；2、构造数据类型：数组、结构。(2) 系统包括哪些功能模块， 模块功能描述， 各模块间的层次结构 （即相互调用关系）以及模块之间的信息交换问题。系统由一个 main 函数、多个标准库函数和五个自定义函数组成。函数 InsertBST 、CreateBST、inOrder 、SearchBST 、DelBST由主函数 main 调用，编译成功后执行代码，在显示的菜单中首先选择建立字典，然后可以选择中序遍历，查找节点，删除节点，插入节点等操作，完成查找，添加，删除等操作。2、算法设计各个模块内部的具体算法，包括输入、处理和输出，相当于C语言的过程或函数设计。整体算法描述：首先建立一棵二叉树, 然后再按要求通过调用各个函数对内部的数据进行操作及处理。各个分函数算法描述：主函数 int main调用 CreateBST() 建立字典主函数 int main调用 inOrder() 中序遍历主函数 int main调用 InsertBST() 插入节点主函数 int main调用 SearchBST() 查找节点主函数 int main调用 DelBST() 删除节点调用函数通过switch 语句实现，根据自己的要求选择所需的序列，完成自己想要的功能。完成后通过按退出函数，退出程序。4. 设计功能编写一个电子小字典的系统，本系统应完成以下几个方面的功能：1）建立电子小字典 CreateBST() ；2）中序遍历 inOrder()；3）插入节点 InsertBST() ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 4）查找节点 SearchBST()；5）删除节点 DelBST()；包含的功能：1、建立字典此模块主要的功能是实现电子小字典数据的创建，当树为空时，就通过键盘输入数据，从而创建一棵树出来。代码如下：void CreateBST(BSTNode *bst) /*从键盘输入记录的值， 创建相应的二叉排序树*/ int key; *bst=NULL; scanf(%d, &key); while (key!=0) /*输入 0 时结束 */ InsertBST(bst, key); scanf(%d, &key); 2、中序遍历此模块主要的功能是实现把建立的电子字典通过中序遍历的方法在显示器上输出， 中序遍历是可以把数据按照从小到大的序列进行排序。代码如下：void inOrder(BSTNode *root) /*中序遍历二叉树 , root为指向二叉树根结点的指针 */ if (root!=NULL) inOrder(root-lchild); /*中序遍历左子树 */ printf(%d ,root-key); /*输出结点 */ inOrder(root-rchild); /*中序遍历右子树 */ 3、插入节点此模块主要的功能是将需要插入的节点插入到已创建好的电子字典中，然后以中序遍历的方法输出。代码如下: void InsertBST(BSTNode *bst, int key) /* 若在二叉排序树中不存在关键字等于key 的记录，插入该记录 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - BSTNode * s; if (*bst = NULL)/*递归结束条件 */ s=(BSTNode *)malloc(sizeof(BSTNode); /*申请新的结点 s*/ s- key=key; s-lchild=NULL; s-rchild=NULL; *bst=s; else if (keykey) InsertBST(&(*bst)-lchild), key); /*将 s 插入左子树 */ else if (key (*bst)-key) InsertBST(&(*bst)-rchild), key); /*将 s 插入右子树 */ 4、查找节点此模块的主要功能是， 在提示信息下输入需要查找的节点，如果在创建好的字典中存在需要查找的节点，就会显示要查找的值存在，如果不存在就会提示该记录不存在，只能进行插入操作。代码如下：BSTNode *SearchBST(BSTNode *bst, int key) /* 在根指针 bst 所指二叉排序树中，递归查找某关键字等于key 的记录，若查找成功，返回指向该记录结点指针，否则返回空指针*/ if (!bst) return NULL; else if(bst-key=key) return bst; /*查找成功 */ else if(bst-keykey) return SearchBST(bst-lchild, key);/*在左子树继续查找 */ else return SearchBST(bst-rchild, key);/*在右子树继续查找 */ 5、删除节点此模块的功能主要是，在提示信息下输入需要删除的节点，删除后，系统会以中序遍历的方法输出已剩的数据。代码如名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 下：BSTNode *DelBST(BSTNode *t, int k) /*在二叉排序树t 中删去关键字为k的结点 */ BSTNode *p, *f,*s ,*q; p=t; f=NULL; while(p) /*查找关键字为 k 的待删结点 p*/ if(p-key=k ) break; /*找到则跳出循环 */ f=p; /*f指向 p结点的双亲结点 */ if(p-keyk) p=p-lchild; else p=p-rchild; if(p=NULL) return t; /*若找不到，返回原来的二叉排序树*/ if(p-lchild=NULL) /*p无左子树 */ if(f=NULL) t=p-rchild; /*p是原二叉排序树的根 */ else if(f-lchild=p) /*p是 f 的左孩子 */ f-lchild=p-rchild ; /*将 p 的右子树链到 f 的左链上 */ else /*p是 f 的右孩子 */ f-rchild=p-rchild ; /*将 p 的右子树链到 f 的右链上 */ free(p); /*释放被删除的结点 p*/ else /*p有左子树 */ q=p; s=p-lchild; while(s-rchild) /*在 p 的左子树中查找最右下结点*/ q=s; s=s-rchild; if(q=p) q-lchild=s-lchild ; /*将 s 的左子树链到 q 上*/ else q-rchild=s-lchild; p-key=s-key; /*将 s 的值赋给 p*/ free(s); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - return t; 系统整体流程图如下：5、功能实现所有代码如下：头文件 lx.h typedef struct node int key ; /*定义关键字，假定为整型*/ struct node *lchild,*rchild; /*左右指针 */ BSTNode; void InsertBST(BSTNode *bst, int key); void CreateBST(BSTNode *bst); void inOrder(BSTNode *root); BSTNode *SearchBST(BSTNode *bst, int key); BSTNode *DelBST(BSTNode *t, int k); 实现函数 sx.cpp 开始在菜单中选择建立电子小字典中序遍历插入节点查找节点删除节点退出程序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - #include #include #includelx.h void InsertBST(BSTNode *bst, int key) /*若在二叉排序树中不存在关键字等于key 的记录，插入该记录 */ BSTNode * s; if (*bst = NULL)/* 递归结束条件 */ s=(BSTNode *)malloc(sizeof(BSTNode); /* 申请新的结点 s*/ s- key=key; s-lchild=NULL; s-rchild=NULL; *bst=s; else if (keykey) InsertBST(&(*bst)-lchild), key); /* 将 s插入左子树 */ else if (key (*bst)-key) InsertBST(&(*bst)-rchild), key); /* 将 s插入右子树 */ void CreateBST(BSTNode *bst) /*从键盘输入记录的值， 创建相应的二叉排序树*/ int key; *bst=NULL; scanf(%d, &key); while (key!=0) /*输入 0 时结束 */ InsertBST(bst, key); scanf(%d, &key); void inOrder(BSTNode *root) /* 中序遍历二叉树 , root 为指向二叉树根结点的指针*/ if (root!=NULL) inOrder(root-lchild); /*中序遍历左子树 */ printf(%d ,root-key); /*输出结点 */ inOrder(root-rchild); /*中序遍历右子树 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - BSTNode *SearchBST(BSTNode *bst, int key) /*在根指针 bst 所指二叉排序树中，递归查找某关键字等于key 的记录，若查找成功，返回指向该记录结点指针，否则返回空指针*/ if (!bst) return NULL; else if(bst-key=key) return bst; /*查找成功 */ else if(bst-keykey) return SearchBST(bst-lchild, key);/*在左子树继续查找 */ else return SearchBST(bst-rchild, key);/*在右子树继续查找 */ BSTNode *DelBST(BSTNode *t, int k) /*在二叉排序树 t 中删去关键字为 k 的结点*/ BSTNode *p, *f,*s ,*q; p=t; f=NULL; while(p) /*查找关键字为 k 的待删结点 p*/ if(p-key=k ) break; /*找到则跳出循环 */ f=p; /*f 指向 p 结点的双亲结点 */ if(p-keyk) p=p-lchild; else p=p-rchild; if(p=NULL) return t; /*若找不到，返回原来的二叉排序树*/ if(p-lchild=NULL) /*p 无左子树 */ if(f=NULL) t=p-rchild; /*p 是原二叉排序树的根 */ else if(f-lchild=p) /*p 是 f 的左孩子 */ f-lchild=p-rchild ; /* 将 p 的右子树链到 f 的左链上 */ else /*p 是 f 的右孩子 */ f-rchild=p-rchild ; /*将 p 的右子树链到 f 的右链上 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - free(p); /*释放被删除的结点p*/ else /*p 有左子树 */ q=p; s=p-lchild; while(s-rchild) /*在 p 的左子树中查找最右下结点*/ q=s; s=s-rchild; if(q=p) q-lchild=s-lchild ; /* 将 s 的左子树链到 q 上*/ else q-rchild=s-lchild; p-key=s-key; /*将 s的值赋给 p*/ free(s); return t; 主函数 m.cpp #include #include #includelx.h. int main() BSTNode *T; int k,rec; BSTNode *result; int i; do printf(nnnntttt- 电子小字典 -); printf(ntt*); printf(ntt* 1-建立 字典*); printf(ntt* 2-中序遍历*); printf(ntt* 3-查找结点*); printf(ntt* 4-删除结点*); printf(ntt* 5-插入结点*); printf(ntt* 0-退出*); printf(ntt*); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - printf(ntt 请选择菜单号 (0-5): ); scanf(%d,&i); switch(i) case 1:printf(建立二叉排序树，请输入序列(输入 0 结束):n); CreateBST(&T);break; case 2:printf(二叉排序树中序遍历序列为:n); inOrder(T);break; case 3:printf(n 请输入要查找的记录 :); scanf(%d,&k); result=SearchBST(T,k); if (result!=NULL) printf( 要查找的记录存在，值为 %dn,result-key); result=DelBST(T,k); else printf( 该记录不存在 !，只能进行插入操作 );break; case 4:printf(n 请输入要删除的记录 :); scanf(%d,&k); result=DelBST(T,k); if(result!=NULL) printf( 删除后的二叉排序树的中序序列: n); inOrder(result); break; case 5:printf(n 输入要插入的记录 :); scanf(%d,&rec); InsertBST(&T,rec); printf( 插入记录后二叉排序树的中序序列：n); inOrder(T);break; case 0:return 0;break; default:printf(tt 输入错误！请重新输入！ ntt); while(i=5); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - 6、测试1、主菜单2、建立电子小字典3、中序遍历4、查找节点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - 5、删除节点6、退出名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - 7、小结名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - 8、参考文献1、严蔚敏、吴伟民编著， 数据结构（C 语言版），清华大学出版2、张乃孝，数据结构基础，北京大学出版社，1993。3、傅清祥、王晓东，算法与数据结构，电子工业出版社，1993。4、刘大有，数据结构，高教出版社2001。5、王若梅，数据结构，中山大学出版社。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -