




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、河南城建学院课程设计报告书专 业:计算机科学与技术 课程设计名称:用顺序和二叉链表作存储结构实现二叉排序树题 目:班 级:学号:姓名:同 组 人 员:指 导 老 师:完 成 时 间:摘要数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设中的二叉排序树,可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树,一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。关键词:二叉排序树;中序遍历;搜索结点;删除结点;CC+目录目录2第一章课程设计题目及要求31.1C语言简介31.2 课程设计题目31.3 课程设计要
2、求3第二章 算法思想42.1 二叉排序树的定义42.2 二叉排序树的实现42.2.1 建立二叉排序树52.2.2 二叉排序树的中序遍历52.2.3 二叉排序树中元素的查找52.2.4 二叉排序树中元素的删除.5 第三章算法实现73.1 程序设计思想73.2 程序模块73.3 流程图103.4 源程序代码11第四章测试与分析174.1 程序调试174.2 调试结果分析19总 结20心得体会21参考文献22第一章 课程设计题目及要求1.1 C/ C +语言简介C语言是一种结构化语言。它层次清晰,便于按模块化方式组织程序,易于调试和维护。语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型
3、,便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址,进行位(bit)一级的操作。由于语言实现了对硬件的编程操作,因此语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发,也适合于应用软件的开发。C是C+的基础,C+语言和语言在很多方面是兼容的,C+程序员可以利用C+与C的兼容性而直接并有效的使用大量现成的程序库,从而开发出更简洁更高效的系统。1.2 课程设计题目用顺序和二叉链表作存储结构实现二叉排序树:(1)以回车(n)为输入结束标志,输入数列L,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历,输出结果;(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点
4、,并作中序遍历(执行操作2);否则输出信息“无x”。1.3课程设计要求在处理题目时,要求从分析题目的需求入手,按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目,最终写出完整的分析报告。对于稍复杂的程序设计,要充分利用模块化程序设计方法,自顶向下,逐步细化,在整体思路确定的情况下,考虑所需模块数,各模块完成功能以及模块之间的数据联系和调用关系。给出主要模块的算法描述,用流程图或伪代码表示。说明:在设计的过程中,步骤1-步骤4往往是反复进行,在后续步骤中发现问题,往往需要从头重新分析、设计。 第二章 算法思想2.1二叉排序树的定义 二叉排序树的定义:
5、二叉排序树或者是一棵空树,或者是一棵具有如下性质的二叉树:(1)每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码互不相同;(2) 若它的左子树非空,则左子树上所有结点的值均小于根结点的值;(3) 若它的右子树非空,则右子树上所有结点的值均大于根结点的值;(4) 左、右子树本身又各是一棵二叉排序树2.2二叉排序树的实现2.2.1建立二叉排序树建二叉树的结点至少应当包含三个域,分别存放结点的数据data,左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针,它指向二叉树的根结点,其作用是当作树的访问点从空的二叉排序树开始,经过一系列
6、的查找插入操作以后,生成了一棵二叉排序树。根据二叉排序树的定义,建立一棵二叉排序树的过程是按照待排序序列元素的先后次序,不断动态生成二叉树的结点,逐个插入到二叉树中。若p为根结点指针,b为当前待插入元素,其过程可以描述为:若为空树(p=nil),动态生成一个结点,其数据域为当前待插入元素b,左、右指针域为“空”,p指向该结点。若非空树,比较b与根结点数据data(p)如果bdata)*p=t;return (1); else if(keydata) searchBST(t-lchild,key,t,p); elsesearchBST(t-rchild,key,t,p); 对二叉排序树进行中序遍
7、历:inorderTraverse(node *t)if(*t)if(inorderTraverse(&(*t)-lchild)printf(%d,(*t)-data);if(inorderTraverse(&(*t)-rchild); return(1) ;删除节点node Delete(node t,intkey) /*删除函数*/nodep=t,q=NULL,s,f; while(p!=NULL) /*查找要删除的点*/if(p-data=key) break;q=p;if(p-datakey) p=p-lchild;else p=p-rchild;if(p=NULL)returnt;/
8、*查找失败*/if(p-lchild=NULL) /*p指向当前要删除的结点*/if(q=NULL) t=p-rchild;/*q指向要删结点的父母*/else if(q-lchild=p)q-lchild=p-rchild;/*p为q的左孩子*/else q-rchild=p-rchild;/*p为q的右孩子*/free(p);else /*p的左孩子不为空*/f=p;s=p-lchild;while(s-rchild) /*左拐后向右走到底*/f=s;s=s-rchild;if(f=p)f-lchild=s-lchild;/*重接f的左子树*/elsef-rchild=s-lchild;
9、/*重接f的右子树*/p-data=s-data;free (s);returnt;3.3流程图初始化输入数据无X查找函数中序遍历遍历结果插入节点X1 2删除节点存在含x的结点不存在输出遍历结果3.4源程序代码用顺序存储实现:#include#includetypedef struct Tnodeint data; /*输入的数据*/structTnode*lchild,*rchild; /*结点的左右指针,分别指向结点的左右孩子*/*node,BSTnode;searchBST(node t,int key,node f,node *p) /*查找函数*/if(!t)*p=f;return
10、(0); /*查找不成功*/else if(key=t-data)*p=t;return (1); /*查找成功*/else if(keydata) searchBST(t-lchild,key,t,p); /*在左子树中继续查找*/elsesearchBST(t-rchild,key,t,p); /*在右子树中继续查找*/insertBST(node *t,int key)/*插入函数*/node p=NULL,s=NULL;if(!searchBST(*t,key,NULL,&p) /*查找不成功*/s=(node)malloc(sizeof(BSTnode);s-data=key;s-l
11、child=s-rchild=NULL;if(!p)*t=s; /*被插结点*s为新的根结点*/else if(keydata) p-lchild=s;/*被插结点*s为左孩子*/elsep-rchild=s;/*被插结点*s为右孩子*/return (1);else return (0);/*树中已有关键字相同的结点,不再插入*/inorderTraverse(node *t)/*中序遍历函数*/if(*t)if(inorderTraverse(&(*t)-lchild)/*中序遍历根的左子树*/printf(%d,(*t)-data);/*输出根结点*/if(inorderTraverse
12、(&(*t)-rchild); /*中序遍历根的右子树*/return(1) ;node Delete(node t,intkey) /*删除函数*/nodep=t,q=NULL,s,f; while(p!=NULL) /*查找要删除的点*/if(p-data=key) break;q=p;if(p-datakey) p=p-lchild;else p=p-rchild;if(p=NULL)returnt;/*查找失败*/if(p-lchild=NULL) /*p指向当前要删除的结点*/if(q=NULL) t=p-rchild;/*q指向要删结点的父母*/else if(q-lchild=p
13、)q-lchild=p-rchild;/*p为q的左孩子*/else q-rchild=p-rchild;/*p为q的右孩子*/free(p);else /*p的左孩子不为空*/f=p;s=p-lchild;while(s-rchild) /*左拐后向右走到底*/f=s;s=s-rchild;if(f=p)f-lchild=s-lchild;/*重接f的左子树*/elsef-rchild=s-lchild; /*重接f的右子树*/p-data=s-data;free (s);returnt;void main()nodeT=NULL;int num;int s=0,j=0,i=0;int ch
14、=0;nodep=NULL;printf(输入一串数,每个数以空格分开:);doscanf(%d,&num);if(!num) printf(完成输入!n);elseinsertBST(&T,num);while(num);printf(n1:中序输出); printf(n2:输入元素);while(ch=ch) scanf(%d,&ch);switch(ch)case 0:exit(0);/*0退出*/case 1: printf( 中序遍历输出结果为:n );inorderTraverse(&T); /*1中序遍历*/break; case 2: printf( 输入元素x,查找二叉排序树
15、T,若存在含x的结点,则删除该结点,并作中序遍历,否则输出无x :);scanf(%d,&num);/*3删除某个结点*/ if(searchBST(T,num,NULL,&p)T=Delete(T,num);printf( 删除成功!中序遍历输出:n );inorderTraverse(&T);elseprintf( 无%d,num);break; default:printf(无此结点n);break; /*输入无效字符*/二叉链表做存储结构:#include using namespace std;class nodepublic: node(int i):data(i),left(NU
16、LL),right(NULL) void inorder(node *&root) /中序遍历,符合升序输出 if(root!=NULL) inorder(root-left); coutdataright); void insert(node *&ptr,int item) /在查找树中插入元素 if(ptr=NULL) ptr=new node(item); else if(itemdata) insert(ptr-left,item); else insert(ptr-right,item); node *find(node *&ptr,int item) /在查找树中查找元素,找到返回
17、所在结点指针,找不到返回空指针。 if(ptr=NULL) return NULL; if(ptr-data=item) return ptr; else if(itemdata) find(ptr-left,item); else find(ptr-right,item); node *&findy(node *&ptr,int item) /在查找树中查找肯定存在的元素,并返回其引用 if(ptr-data=item) return ptr; else if(itemdata) findy(ptr-left,item); else findy(ptr-right,item); node*
18、rl()return left; node* rr()return right; void dele(node *&ptr) /删除值为item所在结点 if(ptr-rl()=NULL&ptr-rr()=NULL) ptr=NULL; else if(ptr-rr()=NULL) ptr=ptr-rl(); else ptr=ptr-rr(); private: int data; node *left; /左孩子结点 node *right; /右孩子结点;int main() int t,i=0,j; coutt; cout输入tj; node *x=new node(j); for(;
19、ij; x-insert(x,j); coutinorder(x); /作中序遍历 coutn输入操作(当输入-1时程序结束):j; while(j!=-1) node *t=x-find(x,j); /定位结点 if(t!=NULL) node *&y=x-findy(x,j); x-dele(y); coutinorder(x); else cout无j; coutn输入操作(当输入-1时程序结束):j; return 0;第四章 测试与分析4.1程序调试(1) 顺序存储(2)二叉链表储存4.2测试结果分析输入一串数据,进行中序遍历,输入元素x,查找二叉排序树T,若存在含x的结点,则删除该
20、结点,并作中序遍历(执行操作2);否则输出信息“无x”。验证结果正确,说明其符合算法设计的要求:(1)正确性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法,就必须考虑其时间复杂度(它表示随问题的规模n的增大,算法执行时间的增长率和f(n)的增长率相同)和空间复杂度。遍历二叉树的算法中的基本操作是访问结点,则不论按那一次次序进行遍历,对含n个结点的二叉树,其时间复杂度为O(n)。所需辅助空间为遍历过程中栈的最大容量,即树的深度,最坏情况下为n,则空间复杂度也为O(n)。总结这次课程设计使我对数据结构认识深刻了许多,其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树,同时也加深了对二
21、叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、删除二叉排序树中某个结点,。在进行搜索时,还可以采用更好的搜索结构即动态搜索结构。当没有找到时,可以将其插入,而不是仅仅提示未找到。通过一周的课程设计,我已经会用二叉链表存储结构实现对二叉排序树的的创建,中序遍历,查找和某个删除结点等基本操作。但我同时也发现了自己许多不足之处 。首先,对数据结构的掌握还不够。虽然完成了程序,但是只用到了基本的结点以及链表,在数据结构的选择上避重就轻,覆盖面较小,不能很好的体现各种数据结构的掌握度,同时也缺少了适当的锻炼,在这方面还需要自己主动去提高。其次,在程序整体的设计上还不够完善,各模块可以适当增加内容,界面还可以更加的人性化些,这样整个程序才具有更强的美观性与实用性。总而言之,这次课程设计给了我很大启发,我明白了,不管遇到什么问题,只要抓住根源,不气馁,从不同方面去攻破它,终究
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五年DJ培训机构聘用教师合同
- 二零二五年度新能源汽车采购及充电设施建设合同
- 二零二五年度环保型供电工程总承包合同范本
- 2025版太阳能热水系统安装与售后服务合同范本
- 2025版汽车配件展摊位租赁合同范本
- 二零二五年度家居用品采购定制协议
- 二零二五年度生物制药研发成果转让合同
- 二零二五年度汽车租赁与维修连锁承包合同范本
- 2025版动画电影编剧聘请合同范文
- 2025版卞巧离婚协议书及双方未来共同生活费用预算
- 外贸业务入职培训
- 生蚝收购合同协议
- 2025年财会业务知识竞赛题库及答案(220题)
- 轨道交通施工安全管理与风险防范措施
- 2025年体检科工作计划一
- 《全断面岩石掘进机法水工隧洞工程技术规范》
- 有限空间监理实施细则
- 【MOOC】探秘移动通信-重庆电子工程职业学院 中国大学慕课MOOC答案
- 数字图像处理课件
- DB11∕T 2000-2022 建筑工程消防施工质量验收规范
- 十万吨聚丙烯装置工艺技术操作规程
评论
0/150
提交评论