数据结构实验报告三

PAGEPAGE4数据结构实验报告实验题目：二叉排序树班级：计算机141（专升本）姓名：黄跃翔学号：14501111完成日期：2015年6月12日需求分析（说明实验任务，包括输入、输出、功能、测试数据等）1.问题描述（ProblemDescription）：输入一个整数关键字序列L，生成一棵用链式存储结构存储的二叉排序树，对该二叉排序树能进行查找和插入结点的操作，并对该二叉排序树中结点的关键字按递增和递减顺序输出。具体要求：输入数据的第一行为一个正整数T,表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行输入正整数n(5≤n≤20)，第二行输入n个整数，要求依次完成以下工作：(1)以这n个整数生成(建立)一棵用链式存储结构存储的二叉排序树；(2)按递增顺序输出该二叉排序树中的整数(关键字)；(3)输入一个整数key，对该二叉排序树进行查找，若在该二叉排序树中存在这个整数key，则输出find，否则输出notfind。(4)输入一个整数key，若该二叉排序树中不存在这个整数key，则将key插入到该二叉排序树中，使插入后仍为原性质的二叉排序树；否则不必插入；(5)在(4)的基础上，按递减顺序输出该二叉排序树中的整数(关键字)。2.对于输入输出的要求：Input（输入）输入数据的第一行为一个正整数T,表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行输入正整数n(5≤n≤20)，第二行输入n个整数，第三和第四行均输入整数key。Output（输出）每组输出的第一行为按递增顺序输出该二叉排序树中的整数(关键字)，每两个整数之间一个空格；第二行为find或notfind；第三行为按递减顺序输出该二叉排序树中的整数(关键字)。4.测试数据总共有两组：第一组81079681437526694369第二组10942225242042397153578815.测试数据结果输出：第一组：610264369757981find817975694326106第二组：20222425394253577194notfind947157534239252422201概要设计(数据类型的定义、算法思想、主程序和子程序(或功能)模块的说明及各程序模块之间的层次(调用)关系)1.数据结构typedefstructnode//二叉排序树中的结点结构{intdata;//整数(关键字)数据域structnode*lchild,*rchild;//指向左右孩子的指针}nodeb,*bitree;算法思想第一部分：建立二叉排序树。其关键字要求是各不相同的，则对于输入的关键字序列中的每一个整数，要在正在建立的二叉排序树中去查找是否已经存在该整数，不存在时，由查找模块返回要插入的结点位置的双亲结点，根据要建立的二叉排序树的性质，当要增加的整数比双亲结点的整数小的话就插到其左孩子的位置，否则插到其右孩子的位置。这样重复，直到输入结束(输入的整数为-1)为止。第二部分：查找算法是从二叉排序树的根结点开始，根据要查找的整数，若比其当前二叉排序树结点中的整数小就进入其左孩子所在的左子树中继续搜索，否则进入其右左孩子所在的右子树中继续搜索，这过程中，每进入子树前，保存当前结点，以便带回要插入结点的双亲结点。搜索直至找到要查找的整数，用一指针带回；或搜索直至叶子结点的下方，找不到要查找的整数而使空指针带回，以便判断要查找的整数是否找到。第三部分：按递增顺序输出该二叉排序树中的整数(关键字)，可直接用某种二叉树的遍历算法实现；按递减顺序输出该二叉排序树中的整数(关键字)，只要对某种二叉树的遍历算法稍作修改即可。同时插入算法思路和建立二叉排序树时增加一个整数的思路是一样的。主程序intmain(){重复m组：调用createbintree()算法建立二叉排序树t；调用某种二叉树遍历算法按递增顺序输出该二叉排序树中的整数(关键字)；输入要查找的整数，调用searchbst()算法查找要查找的整数；根据查找的结果输出相应的信息；输入要插入的整数，调用insertbst()算法将整数插入到二叉排序树中；根据插入的结果输出相应的信息；调用稍作修改的某种二叉树遍历算法按递减顺序输出该二叉排序树中的整数(关键字)；}4.子程序(或功能)模块①建立二叉排序树算法bitreecreatebintree(intn)建立有n个整数的二叉排序树，其二叉排序树t，用函数值返回树{定义几个树；定义2个int变量；置t为空树；for(n次){置上面某一数为空树输入整数；查找该整数；if(该整数在当前的二叉排序树中不存在){申请结点；对该结点赋以该整数；该结点的左右指针赋空值；根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置//注意当二叉排序树还是空树时情况的处理}}返回建好的二叉排序树t；}②查找算法voidsearchbst(bitreet,bitree*f,bitree*p,intkey)//在二叉排序树t中查找整数为key的结点，若找到，则p指向该结点，否则p为空。f为指向双亲结点的{while(t不空且t中的整数不是要找的整数key){用f记录当前结点；if(要找的整数key小于t中的整数)t进入其左孩子所在的左子树；elset进入其右孩子所在的右子树；}}③插入(增加)整数算法intinsertbst(bitree*t,intkey)//在二叉排序树t中插入整数key的结点，是否插入成功用函数值返回{在二叉排序树t中查找整数key；if(整数key在二叉排序树t中不存在){申请结点；对该结点赋以该整数；该结点的左右指针赋空值；根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置//注意当二叉排序树还是空树时情况的处理}else插入不成功；}详细设计(实现概要设计中定义的数据类型，对主程序和其他模块写出算法，说明子模块的调用关系)首先是对这次实现的二叉树建立，代码如下：typedefstructnode//二叉排序树中的结点结构{ intdata;//整数(关键字)数据域 structnode*lchild,*rchild;//指向左右孩子的指针}nodeb,*bitree;然后是查询KEY的树节点操作代码：voidsearchbst(bitreet,bitree*f,bitree*p,intkey){ *p=t;*f=NULL; //在二叉排序树t中查找整数为key的结点，若找到，则p指向该结点，否则p为空。f为 //指向双亲结点的 while(*p!=NULL&&((*p)->data!=key)) { *f=*p; if(key<(*p)->data)*p=(*p)->lchild; else(*p)=(*p)->rchild; }}接着是建立二叉树算法：bitreecreatebintree(intn)//建立二叉树算法{ bitreep,q,f,t; inti,d; t=NULL; for(i=0;i<n;i++) { p=NULL; cin>>d; searchbst(t,&f,&p,d); if(!p) { q=newnodeb; q->data=d; q->lchild=q->rchild=NULL; if(f==NULL)t=q; elseif(d<f->data)f->lchild=q; elsef->rchild=q; } } returnt;}最后一个子模块插入整数算法：intinsertbst(bitree*t,intkey)/*在二叉排序树t中插入整数key的结点，是否插入成功用函数值返回*/{ bitreep,f,s; searchbst(*t,&f,&p,key); if(!p) { s=newnodeb; s->data=key; s->lchild=s->rchild=NULL; if(!f)*t=s; elseif(key<f->data)f->lchild=s; elsef->rchild=s; return1; } elsereturn0;}voidinordertraverse(bitreet,int*i){ if(t) { inordertraverse(t->lchild,i); (*i)++; if(*i==1)printf("%d",t->data); elseprintf("%d",t->data); inordertraverse(t->rchild,i); }}voidpostordertraverse(bitreet,int*i){ if(t) { postordertraverse(t->rchild,i); (*i)++; if(*i==1)printf("%d",t->data); elseprintf("%d",t->data); postordertraverse(t->lchild,i); }}主函数中的模块的调用如下代码：intmain(){ bitreet,p,f; intd,j,n,key,i; cin>>d; for(j=0;j<d;j++) { cin>>n; t=createbintree(n); i=0;inordertraverse(t,&i);printf("\n"); cin>>key; searchbst(t,&f,&p,key); if(p)printf("find\n"); elseprintf("notfind\n"); cin>>key; insertbst(&t,key); i=0;postordertraverse(t,&i);printf("\n"); } return1;}调试分析(调试过程中遇到的问题是如何解决的、对设计与实现简要回顾或分析、经验和体会、经验和不足等，至少写三条)1.二叉排序树的结点的构造，有数据域和只想左右孩子的指针。2.对已经构造好的二叉排序树进行遍历，由二叉排序树的性质可知，要升序遍历可采用中序遍历二叉树的方法，而要降序遍历时，则需要采用递归先遍历右子树，再根结点，最后遍历左子树。3.二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题回顾整个实验过程，大整数的加法可以通过用不同的储存结构对其进行存储再运算得到（可以推广到其他问题）。而本次实验我试验了2种存储结构，即链式存储方式和顺序存储方式，对于用链表作为存储结构，感觉到这种方式可以适应不定长度的大数的好处。唯一遗憾的就是没有进一步去研究其他的运算方式，如“减乘除”，或者更繁杂的开根号，N次方等。以后有空余时间一定要去好好了解一下。通过本次课程设计，我对大整数的理解和认识又有了进一步的提高，对