数据结构报告正文

第一章1.1数据构造课程设计规定。1.1.1数据构造课程设计问题描述。从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。1.1.2数据构造课程设计基本规定。建立二叉排序树并对其进行查找，涉及成功和不成功两种状况，并给出查找长度。1.2.1数据构造课程设计测试数据。由学生根据软件工程的测试技术自己拟定。注意测试边界数据。1.2.2数据构造课程设计的选作内容。实现二叉排序树的插入、删除操作。第二章2.1数据构造课程设计的算法思想。为了实现任务书的几个规定，本次课程设计的算法思想重要涉及下列三部分。2.1.1主菜单设计。为了方便对二叉排序树的基本操作，设计一种包含多个菜单选项的主菜单以实现对二叉排序树的各个操作。本系统的主菜单界面如图1所示。图1.二叉排序树操作的主菜单2.1.2存储构造的设计。本程序重要采用二叉树构造类型来表达二叉排序树。其中二叉树节点由1个表达核心字的key表达，尚有指向该左孩子和右孩子的指针，通过key<p->key的if语句来判断，其中p表达二叉排序树。2.2.1系统功效的设计。本程序设立了5个子功效菜单，其设计以下。（1)建立二叉排序树。重要通过BstreeCreate()函数来实现。根据系统提示，输入节点的核心字，二叉树上面的各个元素，并以-1作为结束的标记符。（2)往二叉树当中插入数据。重要通过BstreeInsert(y)函数实现。While语句对二叉树状态的判断，通过key<p->key，以及key==p->key，对二叉树的左右之树进行定义，其中p表达二叉排序树，每次只能够插入一种新的数据，不能插入已经存在的元素。（3)二叉树当中查找某数据。重要通过BstreeSearch()函数实现。每次进行查询，成功则显示“查询到该节点”，不成功则“显示查询不到该节点，通过if语句对结点在二叉树当中左右子树进行判断。（4)遍历该二叉排序树。重要通过voidTraverse()函数实现。遍历二叉排序树能够显示该二叉排序树的全部节点信息。如果一开始没有发明二叉树，还会提示你先创立树在进行遍历。（5)删除二叉排序树当中某个数据。重要通过BstreeDelete()函数实现。能够对二叉排序树中不需要的节点进行删除，通过对输入核心字的查找进行删除的操作，重要运用了队列的知识，头尾指针的定义来查找有关的数据。（6）树状打印二叉排序树。重要通过voidTranslevelPrint(Bstreebt)函数实现。通过队列当中的头尾指针定义到树的结点以及结点所在的层次。从而拟定打印之后结点应当到的位置。While语句重要对结点深度进行横向控制，使打印图形比较美观。从而树状输出你定义的二叉排序树。第三章3.1模块划分。3.1.1主程序与子程序之间的对应关系。本程序重要分为两部分：主程序模块以及二叉树各个操作模块。主程序模块——————>二叉树各个操作模块图2.本设计当中主程序与子程序之间的重要调用关系注释：(1) BstreeCreate()；//创立二叉排序树(2)BstreeInsert(Bstreetree,intkey)；//插入(3)BstreeSearch(Bstreetree,intkey)；//查找(4)voidTraverse(Bstreetree)；//遍历(5)BstreeDelete(Bstreetree,intkey)；//删除信息（6）voidTranslevelPrint(Bstreebt)；//树状打印输出3.1.2子程序的具体设计以下：（1）BstreeCreate二叉排序树的创立函数，重要用来创立二叉树进而进行操作。BstreeCreate(){intkey; Bstreetree=NULL;//初始化空树 scanf("%d",&key); while(key!=0)//如果二叉排序树非空 { tree=Insert(tree,key);//插入根节点 scanf("%d",&key); } returntree;}//初始化创立二叉排序树（2）BstreeInsert(Bstreetree,intkey)二叉排序树的插入函数，重要用来对二叉树插入某个元素的操作。BstreeInsert(Bstreetree,intkey){ Bstreep=tree;//二叉树用P表达 Bstrees,f; while(p!=NULL)//判断二叉排序树与否为空 { f=p; if(key==p->key)returntree; if(key<p->key)p=p->lchild; elsep=p->rchild;//判断是二叉排序树的左孩子还是右孩子 } s=(Bstree)malloc(sizeof(Bstnode)); s->key=key; s->lchild=NULL; s->rchild=NULL; if(tree==NULL)returns;//新节点为二叉排序树的根 if(key<f->key)f->lchild=s; elsef->rchild=s; returntree;}//往二叉树当中插入数据（3）BstreeSearch(Bstreetree,intkey)二叉排序树的查询函数，重要用来对二叉树当中的元素进行查询。BstreeSearch(Bstreetree,intkey){ Bstreep=tree;intflag=0;while(p!=NULL) { if(p->key==key)//如果二叉树当中存在所要寻找的结点 { printf("查询到该节点！"); flag=1; return(p); break; } if(key<p->key)p=p->lchild;//往二叉树左孩子处查找 elsep=p->rchild;//往二叉树右孩子处查找 } if(flag==0) { printf("查询不到核心字为%d的节点！",key); //returnNULL; }}//查找二叉树当中某个元素与否存在（4）voidTraverse(Bstreetree)二叉排序树的遍历函数，重要用来对二叉排序树的遍历。inti=1;//避免递归时多次输出做得标志voidTraverse(Bstreetree){ if(tree==NULL&&i)//如果树为空不存在 { printf("请先创立二叉树，在进行遍历操作!"); return; } if(tree) { i=0; Traverse(tree->lchild);//遍历二叉树的左孩子 printf("%4d",tree->key); Traverse(tree->rchild);//遍历二叉树的右孩子 }}//遍历二叉排序树（5）BstreeDelete(Bstreetree,intkey)二叉排序树的删除函数，重要用来对二叉排序树当中某个元素进行删除。BstreeDelete(Bstreetree,intkey){ Bstreep=tree;Bstreef,s,q;f=NULL; while(p) {//查找核心字为key的节点 if(p->key==key)break; f=p; if(p->key>key)p=p->lchild; elsep=p->rchild; } if(p==NULL)returntree; if((p->lchild==NULL)||(p->rchild==NULL))//如果二叉排序树的左右孩子一方为空 { if(f==NULL) if(p->lchild==NULL)tree=p->rchild;//如果左孩子为空，则查找右孩子 elsetree=p->lchild; elseif(p->lchild==NULL) if(f->lchild==p)f->lchild=p->rchild; elsef->rchild=p->rchild; elseif(f->lchild==p)f->lchild=p->lchild; elsef->lchild=p->lchild; free(p); } else{ q=p;s=p->lchild; while(s->rchild) { q=s;s=s->rchild; } if(q==p)q->lchild=s->lchild; p->key=s->key; free(s); }//查找到所要删除的元素 returntree;}//删除二叉树当中某一种数据（6）voidTranslevelPrint(Bstreebt)二叉排序树的打印函数，重要用来对二叉排序树进行树状打印输出。voidTranslevelPrint(Bstreebt) {//本算法实现二叉树的按层打印 structnode { Bstreevec[MAXLEN]; //寄存树结点 intlayer[MAXLEN]; //结点所在的层 intlocate[MAXLEN]; //打印结点的位置 intfront,rear; }q; //定义队列q inti,j=1,k=0,nLocate; q.front=0;q.rear=0; //初始化队列q队头，队尾 printf(""); q.vec[q.rear]=bt; //将二叉树根结点如队列 q.layer[q.rear]=1; q.locate[q.rear]=20; q.rear=q.rear+1; while(q.front<q.rear) { bt=q.vec[q.front]; i=q.layer[q.front]; nLocate=q.locate[q.front]; if(j<i) //进层打印时换行 { printf("\n\n\t");printf("\n\n"); j=j+1;k=0; while(k<nLocate) { printf("");k++; } } while(k<(nLocate+3))//运用结点深度控制横向位置 { printf("");k++; } printf("%d",bt->key); q.front=q.front+1; if(bt->lchild!=NULL)//寄存在左子树，将左子树根结点如队列 { q.vec[q.rear]=bt->lchild; q.layer[q.rear]=i+1; q.locate[q.rear]=(int)(nLocate-pow(2,NLAYER-i)); q.rear=q.rear+1; } if(bt->rchild!=NULL)//寄存右子树，将右子树根结点入队列 { q.vec[q.rear]=bt->rchild; q.layer[q.rear]=i+1; q.locate[q.rear]=(int)(nLocate+pow(2,NLAYER-i)); q.rear=q.rear+1; } }//树状打印输出二叉排序树第四章4.1数据构造4.1.1数据类型定义对二叉排序树的存储类型定义以下：typedefstructBstnode{ intkey; structBstnode*lchild,*rchild;}Bstnode,*Bstree;4.1.2具体问题得数据类型定义。(1)/*创立二叉排序树*/BstreeCreate(){intkey;Bstreetree=NULL;}returntree;(2)/*往二叉树当中插入数据*/BstreeInsert(Bstreetree,intkey){ Bstreep=tree;//二叉树用P表达 Bstrees,f;}returntree(3)/*查找二叉树当中某个元素与否存在*/BstreeSearch(Bstreetree,intkey){ Bstreep=tree;intflag=0;}returntree(4)/*删除二叉树当中某一种数据*/BstreeDelete(Bstreetree,intkey){ Bstreep=tree;Bstreef,s,q;}returntree(5)/*打印二叉排序树*/structnode { Bstreevec[MAXLEN]; //寄存树结点 intlayer[MAXLEN]; //结点所在的层 intlocate[MAXLEN]; //打印结点的位置 intfront,rear; }q; returntree4.2源程序的清单（*****见报告附页）第五章5.1测试数据及其状况。创立二叉排序树18，19,10,4,23,29,1,14对编写好的程序进行测试与否达成了课程设计的规定。5.1.1二叉树的创立。图1：按照屏幕提示输入18，19,10,4,23,29,1,14创立二叉排序树，以0结束。图2：往二叉树当中插入5。图3二叉树当中找到结点5.图4.对二叉树进行遍历。图5.删除二叉树当中5这个元素。图6.树状打印输出二叉排序树。通过实验成果能够发现，测试成果符合课程设计报告书的规定，达成了实验的预期目的。从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。建立二叉排序树并对其进行查找，涉及成功和不成功两种状况，并给出查找长度。还能实现二叉排序树的插入、删除操作。课程设计圆满完毕！第六章6.1总结和体会。通过查阅资料以及请假同窗之后，能够通过C语言程序的编写对从键盘输入的一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等操作，查找过程当中还能进行判断，涉及成功不成功两种状况，并给出其长度，还完毕了二叉树的插入，删除等选作内容。通过typedefstructBstnode函数，能够对二叉树进行存储类型的定义。以及/*创立二叉排序树*/BstreeCreate()；/*插入数据*/BstreeInsert(Bstreetree,intkey)；/*二叉树当中查找数据*/BstreeSearch(Bstreetree,intkey)；/*遍历二叉排序树素*/voidTraverse(Bstreetree)；/*删除二叉排序树当中的数据*/BstreeDelete(Bstreetree,intkey)；/*树状打印输出二叉排序树voidTranslevelPrint(Bstreebt)；等函数的应用。多次运用到了队列的头尾指针的知识，也有助于这方便内容得掌握。懂得了各个操作的编程的构成要素。通过这次的实验，我认识到：理论与实际结合的重要性。在实际操作时，经常碰到过某些问题，程序语句的不规范，语句语法的错误啊，自己看不懂，更无法解决。但是，通过自己不停的思考，尝试着去解决代码中出现的问题。即使开始很困难，但在老师和同窗的协助下，我逐步的熟悉了许多操作，为后继工作的顺利进行做了准备。可能，我们能够说，编一种程仅仅是开始，调试和运行相比之下更难。实践中收获的远比想象的多。通过这次实验通过VisualC++这个平台，也更加激发了我们对于数据构造这门课程的学习爱好。将来在数据构造的学习上面我们也将更加进一步的去探索争取获得更多的进步！附录：数据构造课程设计源程序#include<malloc.h>#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<math.h>#defineMAXLEN100#defineNLAYER3typedefstructBstnode{ intkey; structBstnode*lchild,*rchild;}Bstnode,*Bstree;//二叉树的数据构造BstreeCreate();//创立二叉排序树BstreeInsert(Bstreetree,intkey);//插入数据BstreeSearch(Bstreetree,intkey);//查找数据voidTraverse(Bstreetree);//遍历二叉树BstreeDelete(Bstreetree,intkey);//删除数据voidTranslevelPrint(Bstreebt);//树状打印BstreeCreate(){intkey; Bstreetree=NULL;//初始化空树 scanf("%d",&key);//如果二叉排序树非空 while(key!=0) { tree=Insert(tree,key);//插入节点 scanf("%d",&key); } returntree;}//创立二叉排序树 while(p!=NULL)//判断二叉排序树与否为空 { f=p; if(key==p->key)returntree; if(key<p->key)p=p->lchild; elsep=p->rchild;//判断是二叉排序树的左孩子还是右孩子 } s=(Bstree)malloc(sizeof(Bstnode)); s->key=key; s->lchild=NULL; s->rchild=NULL; if(tree==NULL)returns;//新节点为二叉排序树的根 if(key<f->key)f->lchild=s; elsef->rchild=s; returntree;}//往二叉树当中插入数据BstreeSearch(Bstreetree,intkey){ Bstreep=tree;intflag=0;while(p!=NULL) { if(p->key==key)//如果二叉树当中存在所要寻找的结点 { printf("查询到该节点！"); flag=1; return(p); break; } if(key<p->key)p=p->lchild;//往二叉树左孩子处查找 elsep=p->rchild;//往二叉树右孩子处查找 } if(flag==0) { printf("查询不到核心字为%d的节点！",key); //returnNULL; }}//查找二叉树当中某个元素与否存在inti=1;//避免递归时多次输出做得标志voidTraverse(Bstreetree){ if(tree==NULL&&i)//如果树为空不存在 { printf("请先创立二叉树，在进行遍历操作!"); return; } if(tree) { i=0; Traverse(tree->lchild);//遍历二叉树的左孩子 printf("%4d",tree->key); Traverse(tree->rchild);//遍历二叉树的右孩子 }}//遍历二叉排序树BstreeDelete(Bstreetree,intkey){ Bstreep=tree;Bstreef,s,q;f=NULL; while(p) {//查找核心字为key的节点 if(p->key==key)break; f=p; if(p->key>key)p=p->lchild; elsep=p->rchild; } if(p==NULL)returntree; if((p->lchild==NULL)||(p->rchild==NULL))//如果二叉排序树的左右孩子一方为空 { if(f==NULL) if(p->lchild==NULL)tree=p->rchild;//如果左孩子为空，则查找右孩子 elsetree=p->lchild; elseif(p->lchild==NULL) if(f->lchild==p)f->lchild=p->rchild; elsef->rchild=p->rchild; elseif(f->lchild==p)f->lchild=p->lchild; elsef->lchild=p->lchild; free(p); } else{ q=p;s=p->lchild; while(s->rchild) { q=s;s=s->rchild; } if(q==p)q->lchild=s->lchild; p->key=s->key; free(s); }//查找到所要删除的元素 returntree;}//删除二叉树当中某一种数据voidTranslevelPrint(Bstreebt) {//本算法实现二叉树的按层打印 structnode { Bstreevec[MAXLEN]; //寄存树结点 intlayer[MAXLEN]; //结点所在的层 intlocate[MAXLEN]; //打印结点的位置 intfront,rear; }q; //定义队列q inti,j=1,k=0,nLocate; q.front=0;q.rear=0; //初始化队列q队头，队尾 printf(""); q.vec[q.rear]=bt; //将二叉树根结点如队列 q.layer[q.rear]=1; q.locate[q.rear]=20; q.rear=q.rear+1; while(q.front<q.rear) { bt=q.vec[q.front]; i=q.layer[q.front]; nLocate=q.locate[q.front]; if(j<i) //进层打印时换行 { printf("\n\n\t");printf("\n\n"); j=j+1;k=0; while(k<nLocate) { printf("");k++; } } while(k<(nLocate+3))//运用结点深度控制横向位置 { printf("");k++; } printf("%d",bt->key); q.front=q.front+1; if(bt->lchild!=NULL)//寄存在左子树，将左子树根结点如队列 { q.vec[q.rear]=bt->lchild; q.layer[q.rear]=i+1; q.locate[q.rear]=(int)(nLocate-pow(2,NLAYER-i)); q.rear=q.rear+1; } if(bt->rchild!=NULL)//寄存右子树，将右子树根结点入队列 { q.vec[q.rear]=bt->rchild; q.layer[q.rear]=i+1; q.locate[q.rear]=(int)(nLocate+pow(2,NLAYER-i)); q.rear=q.rear+1; } }//树状打印输出二叉排序树voidmain(){ Bstreetree,p; intkey1,key2,key3; intselect,flag; printf("———————斯乐兵的二叉排序树———————\n"); printf("菜单\n"); printf("1.创立二叉排序树\n"