数据结构课程设计报告.doc

课程设计任务书2014 2015 学年第 1 学期 计算机与通信 学院（系、部） 专业 班级课程名称： 数据结构 设计题目： 二叉树操作系统 完成期限：自 年 月 日至 年 月 日共 周内容及任务1、完成二叉树的基本操作，具体18项功能看下面的程序运行结果2、利用左右孩子表示法完成二叉排序树的构建、插入、删除、查找3、利用左右孩子表示法完成哈夫曼树构建、编码、译码、广义表表示4、每个部分的功能函数的书写，增强程序的可操作性5、程序控制台界面的美化以及添加主要的程序用户提示和使用6、栈和队列的文件包括以及源文件的书写，增强代码的可读性进度安排起止日期工作内容2014.12.16-2014.12.16对已完成课设进行调整，优化等待老师的检查2014.12.17-2014.12.17辅导班上同学，书写课设报告，复习数据结构2014.12.18-2014.12.18辅导班上同学，书写课设报告，复习数据结构2014.12.19-2014.12.19辅导班上同学，书写课设报告，复习数据结构主要参考资料数据结构及应用-C语言描述数据结构习题解答与实验指导C语言程序设计/何钦铭,颜晖主编C+面向对象程序设计/谭浩强编著C语言程序设计实验与习题指导/颜晖,柳俊主编指导教师（签字）： 年 月 日系（教研室）主任（签字）： 年 月 日1数据结构课程设计设计说明书二叉树操作系统起止日期： 年 月 日 至 年 月 日学生姓名班级学号成绩指导教师(签字)计算机与通信学院（部） 年 月 日目录1 课程设计简介51.1 课程设计的目的51.2 课程设计内容52 数据结构的设计62.1 结构体设计62.1 编译预处理63 数据结构的分析73.1 菜单界面73.2辅助函数和语句73.3创建和遍历83.4查找和删除93.5常用编辑93.6打印输出93.7队列和栈93.8功能菜单103.9文件操作104 程序运行结果104.1二叉树的基本操作104.2二叉树的主要应用114.3各部分效果演示114.4 程序运行解释125 心得体会13参考文献14附部分源代码15.28.1 课程设计简介1.1 课程设计的目的通过对“二叉树操作系统”的深究，使我对问题进行分析和设计的能力获得加强；使我对二叉树的基本操作、以及主要应用得到了深层次的理解，同时复习了自己的C语言知识，加强了自己对代码的可操作性，为以后编写应用程序打下基础。熟悉各类编译器的使用，加深自己对数据结构课本的研读，了解更多的算法思维，结合到生活中的实际应用等。1.2 课程设计内容二叉树操作系统应具备如下的功能： 二叉树基本操作：a) 创建二叉树：采用仿先序遍历方式创建一棵二叉树，引入了外部节点b) 插入左孩子：默认是根节点，其他则查找后执行同样的操作c) 插入右孩子：默认是根节点，其他则查找后执行同样的操作d) 查找某节点：对已存入二叉树的中节点信息进行按元素查找e) 求叶子数目：遍历加判断确定出叶子节点的数目f) 求深度操作：递归求构建的二叉树的深度g) 先中后递归打印：先序、中序、后序遍历二叉树的同时打印节点信息h) 先中后非递归打印：采用栈、队列、数组实现二叉树的非递归遍历打印i) 层次遍历：采用队列实现层次遍历j) 各类节点数：计算构建的二叉树内各类度数节点的数目k) 树左右互换：默认是根节点，其他节点按元素查找并执行同样的操作l) 删除左子树：默认也是根节点，其他节点也是同上方法即可实现m) 删除右子树：默认也是根节点，其他节点也是同上方法即可实现n) 查找指定节点双亲：查找构建的二叉树内任意节点(根节点除外)的双亲o) 查找指定节点孩子：查找构建的二叉树内任意节点(叶子除外)左右孩子p) 查找指定节点子孙：查找任意节点的所有子孙节点信息q) 查找指定节点祖先：查找任意节点的所有祖先节点信息 二叉树的主要应用：a) 二叉排序树：创建二叉、搜索节点、插入节点、删除节点b) 最优二叉树：初始操作、编码操作、译码操作、打印操作 其他辅助的维护调整美化工作。2 数据结构的设计2.1 结构体设计因为涉及到二叉树，我采用的是链式存储方式，以左右孩子指针域存储下整个二叉树的结构，再设置了每个节点应有的数据域存放每个节点的信息。因为涉及到二叉树非递归遍历涉及到队列和栈，所以我又设计了顺序栈和顺序循环队列的结构类型声明定义；因为二叉树的主要应用有二叉排序树和最优二叉树，但是二叉排序树的数据类型我默认是整型，所以二叉排序树结构类型不做重复声明定义，然而我的最优二叉树节点类型是字符型的，所以我另外设置了新的数据类型。具体如下：二叉链表结构类型声明定义：typedef struct BTNode /左右孩子表示法-二叉链表 /为后面的二叉排序树和最优二叉树做准备DataType data; /存放字符型数据ElemType ans; /存放整型数据struct BTNode *lchild; /二叉树的链式存储结构struct BTNode *rchild;BTNode,*BTree;顺序栈结构类型声明定义：#define MaxStackSize 10000 /主要处理先中后非递归遍历typedef structBTree dataMaxStackSize;int top;SqStack;顺序循环队列结构类型声明定义：#define MAX 10000typedef struct /既然顺序队列的话，那么一个这种结构类型的节点就好了 BTree dataMAX; /主要处理先中后非递归遍历以及层次遍历 int front; int rear;int tag;SqQueue,*Squeue; 2.1 编译预处理考虑到可能需要用到的文件名包括以及宏定义、条件编译等原因，做了足够的编译预处理,但是考虑到报告的填写，这里只列出主要用到的，具体如下：#include#include#include#include#include#include#include#includeusing namespace std;typedef int ElemType;typedef char DataType;#includeSqStack.h#includeSqQueue.h#include二叉树基本操作.h#include二叉排序树.h#include哈夫曼树.h3 功能模块（或算法）描述在实现程序的时候并没有完全按照书上给出的函数来进行设计，在实际的过程中用到了将近50个函数，大部分函数是实现核心功能的，还有一部分函数是用来美化控制台的输出操作以及功能菜单(加强用户对程序的可操作性)，期间还涉及到了C+ STL库函数应用操作。3 数据结构的分析3.1 菜单界面main()主函数 Basic_operation(root);显示“二叉树的基本操作”功能界面Fuction_BTree(root); 显示“二叉排序树”功能界面Fuction_HuffumanTree(root); 显示“哈夫曼树”功能界面3.2辅助函数和语句 system(“cls”); /控制台清屏函数system(“pause”); /输出暂停函数system(color 0b); /设置控制台颜色函数Sleep(100); /延时函数fclose() /文件关闭函数fopen() /文件打开函数rewind() /文件指针重定位函数fgetc() /以字符方式进行文件读写函数fputc() /以字符方式进行文件读写函数fprintf() /以格式化方式进行文件读写函数fscanf() /以格式化方式进行文件读写函数 system(mode con:cols=400 lines=30000); /调节控制台大小函数goto语句的使用 /循环设置switch语句 /多路分支语句3.3创建和遍历void CreateBiTree(BTNode *root) /仿先序遍历创建二叉树BTree CreateHuf(ElemType a,int n) /建立哈夫曼树void Create_BTree(BTree *root) /建立二叉排序树void Pre_order_Rec(BTree root) /先序遍历递归版void In_order_Rec(BTree root) /中序遍历递归版void Post_order_Rec(BTree root) /后序遍历递归版void LevelOrder_First(BTree Tree) /层次遍历C+ STL实现void LevelOrder_Second(BTree Tree) /层次遍历 指针数组模拟队列void LevelOrder_Third(BTree root) /C语言自写队列void PreOrder_NonRec_First(BTree root) /先序非递归其一void PreOrder_NonRec_Second(BTree Tree) /先序非递归其二void PreOrder_NonRec_Third(BTree Tree) /先序非递归其三void PreOrder_NonRec_Fouth(BTree Tree) /先序非递归其四void InOrder_NonRec_First(BTree root) /中序非递归其一void InOrder_NonRec_Second(BTree T) /中序非递归其二void InOrder_NonRec_Third(BTree T) /中序非递归其三void PostOrder_NonRec_Second(BTree T) /后序非递归其一void PostOrder_NonRec_Third(BTree T) /后序非递归其二3.4查找和删除void Find_Child_Bnode(BTNode *p,BTNode *p_lchild,BTNode *p_rchild)int Find_Parent_Bnode(BTree root,BTNode *p,BTNode *p_parent)void FindDescendants_Blist(BTNode *p) /查找指定节点子孙void FindAncersors_Blist(BTree root,BTNode *p) /查找祖先节点int Insearch_BTree(BTree root,DataType x,BTree &p) /根据元素指定查找 3.5常用编辑BTree Insert_LeftNode(BTree father,DataType x) /给某节点插入左孩子BTree Insert_RightNode(BTree father,DataType x) /给某节点插入右孩子BTree Delete_LeftTree(BTree Node) /删除左子树BTree Delete_RightTree(BTree Node) /删除右子树void Destroy_BTree(BTree *root) /通过释放节点达到销毁的目的void Exchange_BTree(BTree root) /交换所有节点的左右子树void NodeCount_Rec(BTree root) /基于后序遍历的二叉树各类结点统计递归算法3.6打印输出void In_order_Rec_BST(BTree root) /中序遍历输出二叉排序结果void Print_BTree(BTree root) /以广义表形式显示哈夫曼树的结构3.7队列和栈void Init_Squeue(Squeue &head) /队列初始化void En_Squeue(Squeue head,BTree e) /入队void De_Squeue(Squeue head,BTree *e) /出队int Empty_Squeue(SqQueue head) /队空判断int Full_Squeue(SqQueue head) /队满判断void StackInitiate(SqStack *S) /栈初初始化int StackPush(SqStack *S,BTree x) /入栈int StackPop(SqStack *S,BTree *d) /出栈int StackNotEmpty(SqStack S) /栈空判断3.8功能菜单void Basic_operation(BTree root) /二叉树基本操作功能菜单Fuction_BTree(root); /二叉排序树功能菜单Fuction_HuffumanTree(root); /哈夫曼树功能菜单3.9文件操作void Hufcoding(BTree root,int len,FILE *fp,FILE *fp2) /哈夫曼编码写入文件void Decoding_HuffumanTree(BTree root,FILE *fp1) /哈夫曼译码写入文件4 程序运行结果 4.1二叉树的基本操作 4.2二叉树的主要应用4.2.1 二叉排序树界面4.2.2 最优二叉树界面4.3各部分效果演示4.4 程序运行解释1、输入abc#，构建一颗如下所示的二叉树：代码根据仿先序遍历的思维(引入了外部节点#，实则为NULL)，创建了一棵左斜树。观察图形很容易发现其0度节点数为1,1度节点数为2,2度节点数为0。根据先、中、后序遍历的顺序，得出相应为：abc，cba，cba；层次遍历的顺序很明显是abc。与上面的运行结果一致；其他操作经验证一致，页面有限，这里不做多述。cba2、二叉排序树构建，输入5个节点信息分别为5,3,1,7,8构建一棵如下的树：5初始构建的一棵二叉排序树已在左边显示，很明显经中序(左根右)遍历以后得到1,3,5,7,8递增有序序列，关于二叉排序树的其他操作是在这个树的基础上做出调整后的结果，具体如上述截图，这里不做多述。73183、哈夫曼树的应用，输入6个叶子节点的权值(3,9,5,12,6,15)，构建一棵如下树：150029如左图所示：一棵完整的最优二叉树已经构建完成，我们很清楚的发现，其编码结果和上述的截图结果一致，根据文件中存放的编码结果以及构建的哈夫曼树的结构运行程序得到我们的译码结果也和实际相符，其余操作这里也不做多述。21110091415121108610355 心得体会数据结构可以说是计算机里的一门基础课程，基础一定要学扎实，没有扎实的基础是很难驾驭大型程序的。数据结构需用把理论变为上机实践，平常数据结构上机时间只有短短2小时，但从中确实学到了不少知识。没有经常敲代码的习惯，时间久了，再次捡起是比较困难的。我选的课设是二叉树操作系统，对于这个题目还是有写的价值和挑战程序的，刚开始调试代码的时候有时就是一个很小的错误，导致整个程序不能运行，但我最终找到了状态，一步一步慢慢来，经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然具备的条件！同时，通过此次课程设计使我了解到，硬件语言必不可缺少，要想成为一个有能力的人，必须懂得硬件基础语言。怎么说呢，这算是我大学以来做的超大型程序，代码量快2000行；之前大一上学期也做了C语言课程设计-学生信息管理系统，但是那时的代码量也就400+而已，写得几个函数也不过11个；这次心血来潮想到了关于二叉树的综合设计，花了两三个下午的时间终于完成了整篇课程设计。主要分为二叉树的基本操作、二叉树的主要应用。遍历用到了递归、非递归算法，并采用了多种方式进行设置分析。课设含有队列，栈基本线性结构，复习了C语言，C+，巩固了数据结构，对一些问题进行了深度的研究性学习，基础知识得到了明显的加强提高(尤其是在指针方面，这个挺让人头痛的)。二叉排序树的删除操作也是挺有难度的，但是知道了思维的过程后，敲起代码也是得心应手的；哈夫曼树的译码操作我直接用文件进行处理了，不仅加强了自己对文件操作的把握性还加深了自己对哈夫曼树的理解。在这次课程设计中，虽然不能独立地完美编写一个程序，但是在看程序的过程中，不断的上网查资料以及翻阅相关书籍，通过不断的模索，测试，发现问题，解决问题，终于完成了这次课程设计。课设总有结束的时候，但是我们在这方面的学习还有很长一段路要走，还是那句话，不是自己亲自去敲（完成一段代码），是不会真正体验到这其中的奥妙和乐趣的。做什么事都不是容易的，更何况是自己单独完成，不过做成了，还是有很大的自豪感的，嘿嘿；我虽然没有别人聪明(或者说能力不够)，但是我决心用恒心去超越别人。最后，感谢陈老师一学期以来不辞辛苦的为我们的学习着想，真的学到了挺多的知识，开阔了自己的视野。很喜欢老师耐心、认真的教学态度，希望能再次学到老师的课程。参考文献1 数据结构及应用:C语言描述/沈华等编著.-北京:机械工业出版社,2010,102 C语言程序设计/何钦铭,颜晖主编.-2版.-北京:高等教育出版社,2012.33 C+面向对象程序设计/谭浩强编著.-北京:清华大学出版社,2006,14 C语言程序设计实验与习题指导/颜晖,柳俊主编.-2版.-北京:高等教育出版社,2012,3附部分源代码头文件(二叉树基本操作)部分:void Pre_order_Creat_Btree(BTree *root) /仿先序遍历创建二叉树DataType c;if(c=getchar()=#)*root=NULL;else*root=(BTNode *)malloc(sizeof(BTNode);(*root)-data=c; /别以为把这行代码换下位置就成了中、后序遍历创建方式,肯定是错误的Pre_order_Creat_Btree(&(*root)-lchild);Pre_order_Creat_Btree(&(*root)-rchild); /我们首先创建的是根节点,先序首先操作的是根节点我们才能固定出一棵二叉树void Pre_order_Rec(BTree root) /中后序首先操作不是根节点,if(root)printf(%c ,root-data);Pre_order_Rec(root-lchild);Pre_order_Rec(root-rchild);void In_order_Rec(BTree root)if(root)In_order_Rec(root-lchild);printf(%c ,root-data);In_order_Rec(root-rchild);void Post_order_Rec(BTree root)if(root)Post_order_Rec(root-lchild);Post_order_Rec(root-rchild);printf(%c ,root-data); void LevelOrder_Third(BTree root)Squeue queue;BTNode *p=NULL;if(NULL!=root)p=root;Init_Squeue(queue);En_Squeue(queue,p);while(!Empty_Squeue(*queue)De_Squeue(queue,&p);printf(%c ,p-data);if(p-lchild!=NULL)En_Squeue(queue,p-lchild);if(p-rchild!=NULL)En_Squeue(queue,p-rchild);int BTree_Depth_First(BTree root) /计算二叉树的深度-递归版if(root)int h1=BTree_Depth_First(root-lchild);int h2=BTree_Depth_First(root-rchild);return (h1h2?h1:h2)+1; return 0;void PreOrder_NonRec_Fouth(BTree Tree) /先序遍历的非递归 if(!Tree) return ; stack s; while(Tree) /左子树上的节点全部压入到栈中 s.push(Tree); coutdatalchild; while(!s.empty() BTree temp=s.top()-rchild; / 栈顶元素的右子树 s.pop(); / 弹出栈顶元素 while(temp) /栈顶元素存在右子树，则对右子树同样遍历到最下方 coutdatalchild; /因为先序首先访问的就是每一棵树的根节点 void PostOrder_NonRec_Third(BTree T) /后序遍历的非递归 双栈法 stacks1,s2; BTree curr; /指向当前要检查的节点 s1.push(T); while(!s1.empty() /栈空时结束 curr=s1.top(); s1.pop(); s2.push(curr); if(curr-lchild) /这个方式就更加简单了，具有实际效率 s1.push(curr-lchild); if(curr-rchild) s1.push(curr-rchild); while(!s2.empty() printf(%c , s2.top()-data); s2.pop(); /查找指定节点的孩子的算法void Find_Child_Bnode(BTNode *p,BTNode *p_lchild,BTNode *p_rchild)if(p=NULL)return ;*p_lchild=p-lchild;*p_rchild=p-rchild;return ;typedef BTree Elemtype; /查找指定节点的双亲的算法int Find_Parent_Bnode(BTree root,BTNode *p,BTNode *p_parent)SqStack stack;BTNode *q=NULL;*p_parent=NULL;if(p=root)return 0;stack.top=0;q=root;while(NULL!=q|stack.top0)while(NULL!=q)stack.data+stack.top=q;q=q-lchild;q=stack.datastack.top-;if(p=q-lchild|p=q-rchild)*p_parent=q; /二叉树中一个节点最多只有一个return 1; / 父节点，别以为叫双亲你就以为是两个q=q-rchild;return 0;typedef char DataType; /查找指点节点子孙节点的算法typedef BTree Elemtype;void FindDescendants_Blist(BTNode *p)SqQueue queue; /队列的声明与定义BTNode *q=NULL;int count=0;if(p=NULL)printf(当前输入的节点参数有错!n);return ;if(p-lchild=NULL&p-rchild=NULL)printf(当前输入的节点是叶子节点，无孩子节点!n);return ;queue.front=0;queue.rear=0;printf(%c节点的所有子孙节点如下所示：n,p-data);queue.dataqueue.rear=p;queue.rear=(queue.rear+1)%MAX;while(queue.front!=queue.rear)q=queue.dataqueue.front;queue.front=(queue.front+1)%MAX;if(q!=p)printf(%c ,q-data);count+;if(count=5)printf(n);if(NULL!=q-lchild)queue.dataqueue.rear=q-lchild;queue.rear=(queue.rear+1)%MAX;if(NULL!=q-rchild)queue.dataqueue.rear=q-rchild;queue.rear=(queue.rear+1)%MAX;printf(n);printf(节点%c共有%d个子孙节点.n,p-data,count);return ;/查找指定节点祖先的算法void FindAncersors_Blist(BTree root,BTNode *p) /这样子的所有祖先连起来就是折线BTNode *p_parent=p;BTNode *q=NULL;if(p=root)printf(输入的节点信息是根节点，无祖先可寻!n);return ;while(p_parent!=root)q=p_parent;p_parent=NULL;Find_Parent_Bnode(root,q,&p_parent);printf(节点%c是节点%c的一个祖先节点.n,p_parent-data,p-data);int count_leaf=0;int count_onedegree=0;int count_twodegree=0; /基于后序遍历的二叉树各类结点统计递归算法void NodeCount_Rec(BTree root)if(root!=NULL)NodeCount_Rec(root-lchild);NodeCount_Rec(root-rchild);if(NULL=root-lchild&NULL=root-rchild)count_leaf+;else if(NULL!=root-lchild&NULL!=root-rchild)count_twodegree+;elsecount_onedegree+;BTree Insert_LeftNode(BTree father,DataType x) /给某节点插入左节点BTree p=NULL,q=NULL;if(father=NULL)return NULL; /注意在函数调用时NULL和0的区别（返回值的类型）q=father-lchild;p=(BTNode *)malloc(sizeof(BTNode);p-data=x;p-lchild=q;p-rchild=NULL;father-lchild=p;return father-lchild;BTree Insert_RightNode(BTree father,DataType x) /给某节点插入右节点BTree p=NULL,q=NULL;if(father=NULL)return NULL;q=father-rchild;p=(BTree)malloc(sizeof(BTNode);p-data=x;p-rchild=q;p-lchild=NULL;father-rchild=p;return father-rchild;void Destroy_BTree(BTree *root) /通过释放节点达到销毁的目的if(*root)!=NULL&(*root)-lchild!=NULL)Destroy_BTree(&(*root)-lchild);if(*root)!=NULL&(*root)-rchild!=NULL)Destroy_BTree(&(*root)-rchild);free(*root); BTree Delete_LeftTree(BTree Node) /删除左子树if(NULL=Node-lchild&NULL=Node-rchild) /若要删除的为叶子节点则不删除return NULL;Destroy_BTree(&Node-lchild); /删除该节点的左子树Node-lchild=NULL;return Node;BTree Delete_RightTree(BTree Node) /删除右子树if(NULL=Node-lchild&NULL=Node-rchild) /若要删除的为叶子节点则不删除return NULL;Destroy_BTree(&Node-rchild); /删除该节点的右子树Node-rchild=NULL;return Node;void Exchange_BTree(BTree root) /交换所有节点的左右子树if(root!=NULL)Exchange_BTree(root-lchild);Exchange_BTree(root-rchild); /首先不断的递归到最底层的二叉树，然后再不断的往上交换BTree p=root-lchild;root-lchild=root-rchild;root-rchild=p;void PreOrder(BTree root) /输出后序遍历的逆序序列-想想这样为什么就解决了这个问题if(root)printf(%c ,root-data);PreOrder(root-rchild);PreOrder(root-lchild);int Insearch_BTree(BTree root,DataType x,BTree &p) /查找节点函数if(!root)p=NULL;return 0;elseif(root-data=x)printf(元素已找到,正在返回!n);p=root;return 1;if(Insearch_BTree(root-lchild,x,p) /只要是棵二叉树(只有两个方向),这左右(方向)return 1; /递归函数一起使用就能遍历整个二叉树elsereturn Insearch_BTree(root-rchild,x,p);return 0;头文件(哈夫曼树)部分：int a1000;BTree CreateHuf(ElemType a,int n) /根据数组a中n 个权值建立一棵哈夫曼树，返回树根指针int i,j; BTree *t1,t2; /二级指针 t1=(BTree *)malloc(n*sizeof(BTree); for(i=0;in;i+