数据结构课程设计

图4-1调用关系图其他功能均为单个函数实现，不做流程描述4.详细设计4.1数据存储结构：BTNode*LchildNode(BTNode*p)〃返回*p结点的左孩子结点指针BTNode*RchildNode(BTNode*p)〃返回*p结点的右孩子结点指针voidCreateBTree(BTNode*&b,char*str//创建树intFindNode(BTNode*b,ElemTypex)//查找结点是否存在voidInitQueue(SqQueue*&q) //创建队列boolQueueEmpty(SqQueue*q) //判断队列是否为空boolenQueue(SqQueue*q,BTNode*e)//进队列booldeQueue(SqQueue*&q,BTNode*&e)//出队列voidDestoryBTree(BTNode*&b) //销毁释放二叉树voidDispBTree(BTNode*b)intBTHeight(BTNode*b)voidPreOrder(BTNode*b)voidInOrder(BTNode*b)voidPostOrder(BTNode*b)voidDispLeaf(BTNode*b)intlistleaf(BTNode*b)intlistnode(BTNode*b)intmaxnode(BTNode*b)intlistfloor(BTNode*b,voidInitStack(SqStack*&s)voidDestroyStack(SqStack*&s)//输出二叉树//计算二叉树高度//先序递归遍历算法//中序递归遍历算法//后序递归遍历算法//输出叶子结点//输出叶子结点个数voidDispBTree(BTNode*b)intBTHeight(BTNode*b)voidPreOrder(BTNode*b)voidInOrder(BTNode*b)voidPostOrder(BTNode*b)voidDispLeaf(BTNode*b)intlistleaf(BTNode*b)intlistnode(BTNode*b)intmaxnode(BTNode*b)intlistfloor(BTNode*b,voidInitStack(SqStack*&s)voidDestroyStack(SqStack*&s)//输出二叉树//计算二叉树高度//先序递归遍历算法//中序递归遍历算法//后序递归遍历算法//输出叶子结点//输出叶子结点个数//输出结点个数//输出结点的最大值charx)//输出结点在第几层//初始化栈//销毁栈boolStackEmpty(SqStack*s)//判断栈是否为空boolPush(SqStack*&s,BTNode*e)//进栈boolPop(SqStack*&s,BTNode*&e)//出栈//先序非递归遍历算法//中序非递归遍历算法//后序非递归遍历算法//层次遍历算法boolGetTop(SqStack*s,BTNode*&e)//取栈顶元素//先序非递归遍历算法//中序非递归遍历算法//后序非递归遍历算法//层次遍历算法voidPreOrder1(BTNode*b)voidInOrder1(BTNode*b)voidPostOrder1(BTNode*b)voidLevelOrder(BTNode*b)4.2各模块流程图及算法：4.2.1主函数intmain(){system("cls");system("color00a");BTNode*b;inti,n;charx;cout<<"本程序为二叉树的操作"<<endl;charstr[20];cout<<"请输入你的二叉树"<<endl;cin.getline(str,20);CreateBTree(b,str);cout<<"创建成功！"<<endl;cout<<"是否继续操作继续操作请输入1，否则输入0"<<endl;cin>>i;while(i！=0){cout<<" "<<endlcout<<"输入【0】结束程序"<<endlcout<<"输入【1】输出二叉树"<<endlcout<<"输入【2】计算二叉树高度"<<endlcout<<"输入【3】查找节点是否存在"<<endlcout<<"输入【4】输出所有叶子结点"<<endlcout<<"输入【5】计算叶子节点个数"<<endlcout<<"输入【6】前序遍历输出二叉树"<<endlcout<<"输入【7】中序遍历输出二叉树"<<endlcout<<"输入【8】后序遍历输出二叉树"<<endlcout<<"输入【9】计算结点个数"<<endlcout<<"输入【10】输出该树中结点最大值"<<endlcout<<"输入【11】输出树中结点值为x的层"<<endlcout<<"输入【12】先序非递归算法"<<endlcout << " 输入【13】中序非递归算法 " << endl;cout << " 输入【14】后序非递归算法 " << endl;cout << " 输入【15】层次遍历(队列)算法 " << endl;cout<<" "<<endl;cout<<" >>请输入你的操作<< "<<endl;cin>>i;//以下为功能选择相应的函数，比较繁杂，在此不做展示}}4.2.2输入二叉树voidCreateBTree(BTNode*&b,char*str){//创建二叉链intMaxSize1=50;BTNode*St[MaxSize],*p=NULL;inttop=-1,k=0,j=0;charch=str[j];b=NULL;while(ch!='\0'){//str未扫描完时循环switch(ch){case'(':top++;St[top]=p;k=1;break;//可能有左孩子结点，进栈case')':top--;break;case',':k=2;break;//后面为右孩子default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)b=p;else{switch(k){St[top]->lchild=p;break;St[top]->rchild=p;break;}}}j++;ch=str[j];〃继续扫描str}}4.2.3非递归遍历voidPreOrder1(BTNode*b) //先序非递归遍历算法{

BTNode*p;SqStack*st;InitStack(st);Push(st,b);while(!StackEmpty(st)){Pop(st,p);printf("%c",p->data);〃定义一个顺序栈指针st〃初始化栈st//根节点进栈//栈不为空时循环〃定义一个顺序栈指针st〃初始化栈st//根节点进栈//栈不为空时循环〃退栈节点p并访问它〃访问节点pPush(st,p->rchild);if(p->lchild!=NULL)//有左孩子时将其进栈Push(st,p->lchild);}printf("\n");DestroyStack(st); //销毁栈}voidInOrder1(BTNode*b){BTNode*p;SqStack*st;InitStack(st);if(b!=NULL){voidInOrder1(BTNode*b){BTNode*p;SqStack*st;InitStack(st);if(b!=NULL){p=b;while(!StackEmpty(st)||p{while(p!=NULL){Push(st,p);p=p->lchild;}if(!StackEmpty(st))//中序非递归遍历算法〃定义一个顺序栈指针st〃初始化栈stPop(st,p);printf("%c",p->data);p=p->rchild;!=NULL)〃扫描节点p的所有左下节点并进栈〃节点p进栈//移动到左孩子//若栈不空〃出栈节点p〃访问节点p//转向处理其右子树}}printf("\n");}DestroyStack(st); //销毁栈}//后序非递归遍历算法//后序非递归遍历算法〃定义一个顺序栈指针st〃初始化栈st〃扫描节点p的所有左下节点并进栈〃节点p进栈//移动到左孩子//r指向刚刚访问的节点，初始时为空〃flag为真表示正在处理栈顶节点〃取出当前的栈顶节点p〃若节点p的右孩子为空或者为刚刚访问过的节点〃访问节点p//r指向刚访问过的节点//转向处理其右子树//表示当前不是处理栈顶节点//栈不空循环//销毁栈voidPostOrder1(BTNode*b){BTNode*p,*r;boolflag;SqStack*st;InitStack(st);p=b;do{while(p!=NULL){Push(st,p);p=p->lchild;}r=NULL;flag=true;while(!StackEmpty(st)&&flag){GetTop(st,p);if(p->rchild==r){printf("%c",p->data);Pop(st,p);r=p;}else{p=p->rchild;flag=false;}}}while(!StackEmpty(st));printf("\n");DestroyStack(st);}4.2.4递归遍历oidPreOrder(BTNode*b){//先序遍历if(b!=NULL)cout<<(char)b->data;PreOrder(b->lchild);PreOrder(b->rchild);}}voidInOrder(BTNode*b){//中序遍历if(b!=NULL){InOrder(b->lchild);cout<<(char)b->data;InOrder(b->rchild);}}voidPostOrder(BTNode*b){//后序遍历if(b!=NULL){PostOrder(b->lchild);PostOrder(b->rchild);cout<<(char)b->data;}}4.3算法的效率分析：主函数：函数中并不包含for循环、递归等复杂的算法，时间复杂度为O(1);输入二叉树：函数需要扫描输入的二叉树，所以该算法的时间复杂度为O(n)；非递归类遍历：由于不管是先序遍历还是中序遍历以及后序遍历，我们都需要利用一个辅助栈来进行每个节点的存储打印，所以每个节点都要进栈和出栈，不过是根据那种遍历方式改变的是每个节点的进栈顺序，所以时间复杂度为O(n)，同样空间复杂度也为O(n)，n为结点数；递归类遍历：空间复杂度与系统堆栈有关，系统栈需要记住每个节点的值，所以空间复杂度为O(n)。时间复杂度应该为O(nlogn)，每个节点都要遍历到，需要n次，而且需要将二叉树划分logn次，所以递归版的遍历的空间复杂度为O(nlogn)；层序遍历：层序遍历是通过队列来进行每个节点的存储打印的，所以时间复杂度和空间复杂度都为O(n)，n为结点数。

5.测试即n'lHHiJUn'l川.会金公殳丧.<人天会33333-333JJ01234曰

010^345.H-78-ymlll

5.测试即n'lHHiJUn'l川.会金公殳丧.<人天会33333-333JJ01234曰

010^345.H-78-ymlll

EEmEEEmE2-二E'-一

^.胃睡*弓.史甥形5','.flrivln.Jv.1列图5-1初始化菜单图5-4输出叶子结点8后序递归遍历输出为cbfegda图5-5输出后序递归遍历»请输入你的操作"11青输入你的结点“在据图5-6查找结点所在层»请输入你的操作《»请输入你的操作《14存序非递归遍历输出为cbfegda图5-7输出后续非递归遍历»请输入你的操作它15层次遍历算法输出：abdcegf图5-8层次遍历输出结构经过多次测试与更改，但是无法打破原有的界面格式，使得界面输出不够美观，程序的递归与非递归先序、中序、后序遍历、层次遍历、计算结点个数，计算结点所在层数等功能基本能够流畅地实现，达到了应有的要求；不过在输出二叉树的时候，不知道为什么后面会多出一个括号，经过多次的更改与实验也没有将其更改成功，通过查看相关书籍以及网上搜索算法原理，终于明白了错误所在，并完成了排错。6．课程设计心得改进方案对自己的设计进行评价，指出合理和不足之处，提出改进方案；1)菜单设置方面：运用了if()语句，这样看着没有条理，不适合用在二叉树的遍历上，因为遍历结果显而易见并不十分复杂，没有必要使程序复杂化，故采用的是程序运行输出模式。2)二叉树的创建：采用二叉链表存储的方式，利用扩展先序遍历实现二叉树的创建，这样做相对简单，但是对有些情况下不太实用，所以应该增加一项根据后序中序实现创建的算法，是程序更加完善。3)整体布局：由于存在某两个函数的制约关系，要求必须先执行A在执行B,一旦执行顺序错误就会导致输出结果错误。这样降低了程序的冗错性，不利于用户操作，可以通过添加函数间强制装换关系，强制执行，或者是在后者运行的函数中添加必要语句，使其脱离制约函数的制约。设计心得其实在本程序的设计过程当中，没有很吸引人的关键技术，因为本人的C语言或C++语言都不是学的很好，所以当初设计的时候就只是想把功能都实现就好了，尽可能的把所要求的功能都编进程序，这样就觉得很满足了。所以都是设计的比较简单易懂的语言，这样自己能够更明白一些，所以就没有时间去细细地去设计自己的程序。本程序要说有什么值得说的，那就只有人性化这点了，在设计成学的时候，因为自己怕弄混了，所以添加了很详尽的提示，这样在编程的过程中或调试的时候都能够比较快的运行。还有就是尽可能的应用了do-while语句和switch-case语句，这两个语句在之前不是很常用，所以在这个程序中试炼了一下，虽然在编写的过程中总是出错，但还是成功的用好了，也是程序有条理一些。我也知道这些东西别人可能比我弄得还要好，但是我在我所学的知识中成功的应用了这些，我觉得就是好事，就是进步。唯一的亮点可能就是进入系统是的密码设计了，就这一点小小的设计就花了我好几个小时去调试，因为总能在后面程序的加入及运行时发现一些新的小问题。一周多的课程设计，终于成功的验收了，虽然有些疲惫，但还是有很多的收获的，像计算机组成原理的课设一样，我又一次巩固了所学到的知识，之前的学习只是停留在理论基础上，现在自己动手操作试验后，才是真正的理解及体会。C也学了近一年，有很多知识都是似懂非懂，通过平时上机操作，自己也了解了一些，但让我有了更深的理解和更好的认识，则是在这次的课设上，之前的困惑也通过这次的课设解决了一些，虽然还是不能够全面的理解，但是有进步就很高兴。在课程设计之前，因为有了综合实验的经验与教训，明白了写代码这一步是非常重要的，因为当你把代码输进去之后，并编译让其运行，发现通过不了，再来检查出问题，是很费费力的事情，因此分析和规划代码是很重要的，最重要的是要把逻辑结构写好，这样就不会出现大问题，写代码就要先找出核心的内容，用多种方法来实现核心部分，这样可以尽可能的避免发现逻辑或编译不支持的错误。通过本次论文设计，我初步学会了论文设计的基本方法，学会了怎样去借鉴别人的方法和经验，知道了如何整合资料和处理这些资料的能力，这为以后做毕设的论文打下了基础，使我感觉比较好的是有一种成功的喜悦，虽然在编译的时候会经常因为一些小的错误而心烦意乱，但是也不失为一件好事，失败的越多积累的经验越丰富，对人的考验也比较多，那么在最后编译成功时的喜悦就越浓烈，也是自己的能力有了进一步的提高。由于知识和经验的不足，这个程序编写的不是很尽如人意，但是融合了自己的心血，就觉得是最好的，所以在以后还是需要较多的努力的，还是会在以后的学习过程中不断地提高和改进的。7．参考文献[1]《算法导论》（英文名：IntroductiontoAlgorithm）主编：ThomasH.Cormen、CharlesE.Leiserson等译者:潘金贵、顾铁成出版社:机械工业出版社（第三版）[2]《数据结构与算法》主编：王曙燕 2013年9月第1版人民邮电出版社[3]《C语言程序设计教程》主编：王曙燕2014年9月第1版人民邮电出版社[4]谭浩强.C程序设计（第三版）[M].北京:清华大学出版社，2005.8．附录#include<fstream>#include<iostream>#include<stdlib.h>#include<stdio.h>#include<string>#include"work.h"usingnamespacestd;#defineMaxSize100usingnamespacestd;typedefcharElemType;typedefstructb{ElemTypedata;structb*Ichild,*rchild;//二叉树结构声明}BTNode;typedefstruct{BTNode*data[100];//存放栈中的数据元素inttop; //存放栈顶指针，即栈顶元素在data数组中的下标}SqStack;typedefstruct{BTNode*data[MaxSize];//存放队中元素intfront,rear;//队头队尾指针}SqQueue;intwidth[10]={0};//存放各层宽度的数组BTNode*LchildNode(BTNode*p)/*返回*p结点的左孩子结点指针*/{returnp->lchild;}BTNode*RchildNode(BTNode*p)/*返回*p结点的右孩子结点指针*/{returnp->rchild;}voidCreateBTree(BTNode*&b,char*str){//创建二叉链intMaxSize1=50;BTNode*St[MaxSize],*p=NULL;inttop=-1,k=0,j=0;charch=str[j];b=NULL;while(ch!='\0'){ //str未扫描完时循环switch(ch){case'(':top++;St[top]=p;k=1;break;//可能有左孩子结点，进栈case')':top--;break;case',':k=2;break; //后面为右孩子default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)

b=p;else{switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];〃继续扫描str}}intFindNode(BTNode*b,ElemTypex){intp;if(b==NULL){returnNULL;}elseif(b->data==x){returnx;}elsep=FindNode(b->lchild,x);if(p!=NULL){returnp;}elsereturnFindNode(b->rchild,x);}}///队列的有关操作voidInitQueue(SqQueue*&q){q=(SqQueue*)malloc(sizeof(SqQueue));q->front=q->rear=0;}//判断队列是否为空boolQueueEmpty(SqQueue*q){return(q->front==q->rear);}//进队列boolenQueue(SqQueue*q,BTNode*e){if((q->rear+1)%MaxSize==q->front)//队满溢出returnfalse;q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;returntrue;}//出队列booldeQueue(SqQueue*&q,BTNode*&e){if(q->front==q->rear)//^U断是否队空returnfalse;q->front=(q->front+1)%MaxSize;e=q->data[q->front];returnfalse;}voidDestoryBTree(BTNode*&b){if(b!=NULL)DestoryBTree(b->lchild);DestoryBTree(b->rchild);free(b);}}voidDispBTree(BTNode*b){//输出单链表if(b!=NULL){cout<<(char)b->data<<"";if(b->lchild!=NULL||b->rchild!=NULL){cout<<"(";DispBTree(b->lchild);if(b->rchild!=NULL)cout<<",";DispBTree(b->rchild);cout<<")";}}}intBTHeight(BTNode*b){//树的高度intlchildh,rchildh;if(b==NULL)return(0);lchildh=BTHeight(b->lchild);rchildh=BTHeight(b->rchild);return(lchildh>rchildh)?(lchildh+1):(rchildh+1);}voidPreOrder(BTNode*b){//先序遍历if(b!=NULL){cout<<(char)b->data;PreOrder(b->lchild);returnreturn1;PreOrder(b->rchild);}voidInOrder(BTNode*b){//中序遍历if(b!=NULL){InOrder(b->lchild);cout<<(char)b->data;InOrder(b->rchild);}}voidPostOrder(BTNode*b){//后序遍历if(b!=NULL){PostOrder(b->lchild);PostOrder(b->rchild);cout<<(char)b->data;}}voidDispLeaf(BTNode*b){//递归输出叶子节点if(b!=NULL){if(b->lchild==NULL&b->rchild==NULL)cout<<(char)b->data;DispLeaf(b->lchild);DispLeaf(b->rchild);}}intlistleaf(BTNode*b){//输出叶子结点个数intnum1;if(b==NULL)return0;elseif(b->lchild==NULL&&b->rchild==NULL)num1=listleaf(b->rchild)+listleaf(b->lchild);returnnum1;}intlistnode(BTNode*b){intnum;if(b==NULL)return(0);else{num=listnode(b->lchild)+listnode(b->rchild)+1;}returnnum;}intmaxnode(BTNode*b){if(NULL==b)return0;intmaxLeft=maxnode(b->lchild);intmaxRight=maxnode(b->rchild);intmax=maxLeft>maxRight?maxLeft:maxRight;returnmax>b->data?max:b->data;}intlistfloor(BTNode*b,charx){intnum2,m,n;if(b==NULL)num2=0;elseif(b->data==x)num2=1;else{m=listfloor(b->lchild,x);n=listfloor(b->rchild,x);if(m==0&&n==0)num2=0;elsenum2=((m>n)?m:n)+1;}returnnum2;returnnum2;returnfalse;//栈顶e)//取栈//先序//定义//栈顶e)//取栈//先序//定义//根节intLevel(BTNode*b,ElemTypex,inth){intl;if(b==NULL)return(0);elseif((char)b->data==(char)x)return(h);else{l=Level(b->lchild,x,h+1);//左子树中查找if(l!=0)return(l);//在左子树中找到，返回lelsereturn(Level(b->rchild,x,h+1));//在左子树中未找到再在右子树中查找}}//栈的所有操作如下voidInitStack(SqStack*&s) //初始化栈{s=(SqStack*)malloc(sizeof(SqStack));//分配一个是顺序栈空间，首地址存放在s中s->top=-1;//栈顶指针置为-1}voidDestroyStack(SqStack*&s)//销毁栈{free(s);}boolStackEmpty(SqStack*s) //判断栈是否为空{return(s->top==-1);}boolPush(SqStack*&s,BTNode*e)//进栈{if(s->top==MaxSize-1)//栈满的情况，即栈上溢出s->top++; //栈顶指针增1s->data[s->top]=e;〃元素e放在栈顶指针处returntrue;}boolPop(SqStack*&s,BTNode*&e)//出栈{if(s->top==-1)//栈为空的情况，即栈下溢出returnfalse;e=s->data[s->top];//取栈顶指针元素的元素s->top--;指针减1returntrue;}boolGetTop(SqStack*s,BTNode*&顶元素{if(s->top==-1)//栈为空的情况，即栈下溢出returnfalse;e=s->data[s->top];//取栈顶元素returntrue;}voidPreOrder1(BTNode*b)非递归遍历算法{BTNode*p;SqStack*st;一个顺序栈指钵tInitStack(st);〃初始化栈stPush(st,b);点进栈while(!StackEmpty(st))//栈不为空时循环{Pop(st,p); //退栈节点p并访问它printf("%c",p->data);//访问节点pif(p->rchild!=NULL)//有右孩子时将其进栈Push(st,p->rchild);if(p->lchild!=NULL)//有左孩子时将其进栈Push(st,p->lchild);}printf("\n");DestroyStack(st); //销毁栈}//中序非递归遍历voidInOrder1(BTNode*b)//中序非递归遍历算法{BTNode*p;SqStack*st;〃定义一个顺序栈指针stInitStack(st);〃初始化栈stif(b!=NULL){p=b;while(!StackEmpty(st)||p!=NULL){while(p!=NULL)〃扫描节点p的所有左下节点并进栈{Push(st,p);〃节点p进栈p=p->lchild;//移动到左孩子}if(!StackEmpty(st))//若栈不空{Pop(st,p);〃出栈节点pprintf("%c",p->data);〃访问节点pp=p->rchild;//转向处理其右子树}}printf("\n");}DestroyStack(st); //销毁栈}voidPostOrder1(BTNode*b)//后序非递归遍历算法{BTNode*p,*r;boolflag;SqStack*st;〃定义一个顺序栈指针stInitStack(st);〃初始化栈stp=b;do{while(p!=NULL)〃扫描节点p的所有左下节点并进栈{Push(st,p);〃节点p进栈p=p->lchild;//移动到左孩子}r=NULL;//r指向刚刚访问的节点，初始时为空flag=true;//flag为真表示正在处理栈顶节点while(!StackEmpty(st)&&flag){GetTop(st,p);〃取出当前的栈顶节点pif(p->rchild==r)//若节点p的右孩子为空或者为刚刚访问过的节点{//访问节点pprintf("%c",p->data);Pop(st,p);r=p;//r指向刚访问过的节点}else{p=p->rchild;//转向处理其右子树flag=false;//表示当前不是处理栈顶节点}}}while(!StackEmpty(st));//栈不空循环printf("\n");DestroyStack(st); //销毁栈}voidLevelOrder(BTNode*b){BTNode*p;SqQueue*qu;InitQueue(qu);//初始化队列enQueue(qu,b);//根结点指针进入队列while(!QueueEmpty(qu))//队不为空时循环{deQueue(qu,p);//出队结点pcout<<(char)p->data<<"";if(p->lchild!=NULL)//有{enQueue(qu,p->lchild);}if(p->rchild!=NULL)//有右孩子进队{enQueue(qu,p->rchild);}}}intmain(){system("cls");system("color00a");BTNode*b;inti,n;charx;cout<<"本程序为二叉树的操作"<<endl;charstr[20];cout<<"请输入你的二叉树"<<endl;cin.getline(str,20);CreateBTree(b,str);cout<<”创建成功！"<<endl;cout<<"是否继续操作继续操作请输入1，否则输入0"<<endl;cin>>i;while(i!=0){cout <<〃-"<<endl;cout<<"--输入【0】结束程序"<<endl;cout<<"输入【1】输出二叉树"<<endl;cout<<"输入【2】计算二叉树高度"<<endl;cout<<"输入【3】查找节点是否存在"<<endl;cout<<"输入【4】输出所有叶子结点"<<endl;cout<<"输入【5】计算叶子节点个数"<<endl;cout<<"输入【6】前序遍历输出二叉树"<<endl;cout<<"输入【7】中序遍历输出二叉树"<<endl;cout<<"输入【8】后序遍历输出二叉树"<<endl;cout<<"输入【9】计算结点个数"<<endl;cout<<"输入【10】输出该树中结点最大值"<<endl;cout<<"输入【