还剩22页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
长沙理工大学《数据结构》课程设计报告何松柏学院城南学院专业计算机科学与技术班级计算机0701班学号200786250119学生姓名何松柏指导教师肖增良课程成绩完成日期2009年9月16日课程设计成绩评定学院计算机与通信工程专业计算机科学与技术班级计算机07-01学号200786250119学生姓名何松柏指导教师肖增良课程成绩完成日期2009年09月16日指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩指导教师签字年月日课程设计任务书城南学院计算机科学与技术专业课程名称二叉树的建立和后序遍历的演示时间2009~20010学年第1学期1~2周学生姓名何松柏指导老师肖增良题目二叉树的建立和后序遍历的演示主要内容建立一个链式存储结构的栈,存放二叉树的节点,并利用二叉树的后序非递归算法,实现基本的插入,删除,查找等功能,并实现二叉树的后序遍历算法要求
(1)通过实际项目的分析、设计、编码、测试等工作,掌握用C语言来开发和维护软件
(2)按要求编写课程设计报告书,能正确编写分析、设计、编码、测试等技术文档和用户使用手册应当提交的文件
(1)课程设计学年论文
(2)课程设计附件(主要是源程序)二叉树的建立和后序遍历的演示学生姓名何松柏指导老师肖增良摘要二叉树是每个结点最多有两个子树的有序树通常节点的子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示后序遍历是先按遍历左子树,然后遍历右子树,最后访问根节点而访问下一层节点是,必须记录上一层的节点信息,便于访问结束后退回上一层节点,所以用栈才存储节点信息 Abstract:Binarytreeisanorderlytreethateachnodehavanomorethantwosub-trees.Subtreenodeisusuallyreferredtoastheleftsub-treeandtherightsub-tree.Traversalofatreeisthemostbasiccomputingtheso-calledbinarytreetraversalthatisaccordingtocertainrulesandorderofeverytreeofallnodesandeachnodehavebeenvisitedonce.Binarytreestructureasaresultofnon-linearthereforethetreeistotraversealltreenodescanconvertedintoalinearsequencetoexpress.Afterthetraversalistotheirleftsubtreetraversalandthentraversetherightsubtreeandfinallyvisittherootnode.Thevisittothenextlayerofnodesistheneedtorecordit’spreviouslayer’sinformationtofacilitatereturnvisitsaftertheendofthelayerofnodessowecanusestackstoragenodeinformation.关键词二叉树递归后序遍历非递归后序遍历栈Keywords:BinarytreeAftertherecursivetraversalAfterthenon-recursivetraversal1引言在计算机科学中,二叉树是每个结点最多有两个子树的有序树通常子树的根被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)二叉树常被用作二叉查找树和二叉堆后序遍历是二叉树遍历的一种后序遍历指在访问根结点、遍历左子树与遍历右子树三者中,首先遍历左子树,然后遍历右子树,最后遍历访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点后序遍历有递归算法和非递归算法两种栈(stack)在计算机科学中是限定仅在表尾进行插入或删除操作的线形表它是是一种数据结构,它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)所以它非常适合存储二叉树的节点信息
1.1课题背景自1946年第一台计算机问世以来计算机产业的飞速发展已远远超出人们对它的预料,在某些生产线上,甚至几秒钟就能生产出一台微型计算机,产量猛增,价格低廉,这就使它的应用范围迅速扩展如今,计算机已深入到人类社会的各个领域计算机的应用已不再局限于科学计算,而更多地用于控制管理用数据处理等非数值计算的处理工作《数据结构》作为一门独立的课程最早是美国的一些大学开设的,1968年美国唐·欧·克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作从60年代末到70年代初,出现了大型程序,软件也相对独立,结构程序设计成为程序设计方法学的主要内容,人们就越来越重视数据结构,认为程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法从70年代中期到80年代初,各种版本的数据结构著作就相继出现目前在我国,《数据结构》也已经不仅仅是计算机专业的教学计划中的核心课程之一,而且是其它非计算机专业的主要选修课程之一“数据结构”在计算机科学中是一门综合性的专业基础课“数据结构”的研究不仅涉及到计算机的硬件的研究范围,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉及到数据元素在存储中的分配问题在研究信息检索时也必须考虑如何组织数据,以便查找和存取数据元素更为方便因此,可以认为“数据结构”是介于数学,计算机硬件和计算机软件三者之间的一门核心课程在计算机科学中,“数据结构”不仅是一般的程序设计(特别是非数值计算的程序)的基础,而且是设计和实现编译程序、操作系统、数据库系统用其他系统程序和大型应用程序的重要基础“数据结构”的发展并未终结,一方面,面向各专门领域中特殊问题的数据结构得到研究和发展,如多维图形数据结构等;另一方面,从抽象数据类型的观点来讨论数据,已成为一种新的趋势,越来越被人们所注视
1.2课题研究的目的和意义
(1)在此过程中我们将会了解编程的一些方法和技巧,认识到实现一个问有提出问题、分析问题、设计问题、实现等环节此实践过程会是大家熟练掌握基本的数据结构和常用的算法,并最终设计一个能够解决实际问题并具有一定规模的大学数据课程设计
(2)这次做程序设计目的是为更好地掌握C语言编写数据结构程序的方法和技巧,了解C语言的强大的功能,更好地学习C语言,并且在这个过程中更好地锻炼自己的动手能力和实践能力
(3)通过对此次数据结构大型作业内容的分析,锻炼学生分析与编写大型软件代码的能力通过与同组同学的合作,锻炼协作的能力
1.3需求分析二叉树一种数据结构,用于保存和处理树状的数据,比如家谱他的应用极为广泛,因为根据数据结构的理论,任何复杂的树够可以转换为二叉中并进行处理,二叉树在排序、查找、大规模数据索引方面有很多很多应用而且二叉树排序是简单算法排序中速度最快的在二叉树的一些应用中,常常要求在树中查找具有某种特征的节点,或者对树中全部节点逐一进行某种处理这就提出了遍历二叉树根据遍历的方向的选择,就有了后序遍历二叉树因此掌握二叉树的后序遍历二叉树算法非常重要,而且高效的后序遍历算法能够节省很多成本2设计思路与方案
2.1设计思路类是所有面向对象语言的共同特征,因此类是C++中十分重要的概念,是实现面向对象程序设计的基础是C++的灵魂C++支持面向过程的程序设计,也支持基于对象的程序设计,又支持面向对象的程序设计基于对象就是基于类,与面向过程的程序不同,基于对象的程序是以类和对象为基础的,程序的操作是围绕对象进行的在此基础上利用了继承机制和多态性,就成为面向对象的程序设计C++中对象的类型称为类,类代表了某一批对象的共性和特征,类是对象的抽象,而对象是类的具体实例在类体中是类的成员列表,列出类中的全部成员它是一种广义的数据类型,除了数据部分以外,还包括了对这些数据操作的函数这体现了把数据和操作封装在一起
2.2设计方案下面分2个部分来说明
(1)栈的数据结构设计采用线性存储结构templateclassDataTypeclassStack{private:DataType*base;//栈尾DataType*top;//栈顶intstacksize;//栈分配的长度};
(2)二叉树的存储结构设计二叉树的节点类型,并作为二叉树的友元类便于二叉树进行操作templateclassDataTypeclassTreeNode{TreeNode:lchildNULLrchildNULL{}friendclassBiTreeDataType;private:DataTypedata;TreeNode*lchild*rchild;};二叉树的存储结构templateclassDataTypeclassBiTree{private:TreeNodeDataType*root;//树根DataTypetemp;//代表元素为空的符号,便于输入时使用};3系统实现本程序主要包括栈头文件和二叉树头文件,其中栈头文件包括栈的建立,插入元素,删除元素二叉树头文件主要阐述了非递归后序算法,具体情况如下图
3.1所示图
3.1系统流程图系统采用链栈为栈的存储结构链栈采用链表作为存储结构为便于操作,采用带头结点的单链表实现栈由于栈的插入和删除操作仅限制在表头位置进行,所以链表的表头指针就作为栈顶指针,如图
3.2所示图
3.2链栈示意图
3.1栈的建立分配一块空间给栈底,栈顶指针指向最上面元素的上端,当栈的空间不够用时,追加空间以下为具体实现代码StackDataType::Stack{if!base=DataType*mallocSTACK_INIT_SIZE*sizeofDataTypeexit1;top=base;stacksize=STACK_INIT_SIZE;}
3.2插入栈顶元素由于栈的存储结构为先进后出,所以当插入新元素e后,e处于这个栈的栈顶具体实现下图
3.3所示图
3.3栈的结构示意图以下为具体实现代码templateclassDataTypevoidStackDataType::PushDataTypee{iftop-base=stacksize{if!base=DataType*reallocbasestacksize+STACKINCREMENT*sizeofDataTypeexit1;top=base+stacksize;stacksize+=STACKINCREMENT;}*top++=e;}
3.3删除栈顶元素当栈为空时,返回0;否则将栈顶指针向下移一个单位如下图
3.4所示图
3.4删除栈底示意图以下为具体实现代码templateclassDataTypeintStackDataType::PopDataTypee{iftop==basereturn0;e=*--top;return1;}
3.4二叉树非递归后序算法先访问左子树,并进栈,直到为空,最后一个元素退栈,访问该节点,然后访问右子树,并用一个标志域标记下来,当右子树为空时,访问该节点具体实现流程图如下图
3.5所示图
3.5二叉树的后序非递归算法以下为具体实现代码templateclassDataTypevoidBiTreeDataType::PosOrderTraverse{StackTreeNodeDataType*S;TreeNodeDataType*p;TreeNodeDataType*r;//使用r节点表示访问了右子树替代标志域p=root;whilep||!S.StackEmpty{ifp{S.Pushp;p=p-lchild;}else{S.GetTopp;ifp-rchildp-rchild!=r{p=p-rchild;S.Pushp;p=p-lchild;}else{S.Popp;coutp-data;r=p;p=NULL;}}}S.DestroyStack;}4系统测试与运行当把系统的界面模块设计好以及编好了相应的功能模块的程序后最重要的就是调试程序的运行与测试程序的结果
4.1调试编好程序后,用各种手段进行查错和排错的过程作为程序的正确性不仅仅表现在正常功能的完成上,更重要的是对意外情况的正确处理经修改后调试显示如下--------------------Configuration:tg-Win32Debug--------------------CommandLinesCreatingtemporaryfileC:\DOCUME~1\hp\LOCALS~1\Temp\RSP
16.tmpwithcontents[/nologo/MLd/W3/Gm/GX/ZI/Od/DWIN32/D_DEBUG/D_CONSOLE/D_MBCS/FpDebug/tg.pch/YX/FoDebug//FdDebug//FD/GZ/cD:\MicrosoftVisualStudio\MyProjects\as\tg.cpp]Creatingcommandlinecl.exe@C:\DOCUME~1\hp\LOCALS~1\Temp\RSP
16.tmpCreatingtemporaryfileC:\DOCUME~1\hp\LOCALS~1\Temp\RSP
17.tmpwithcontents[kernel
32.libuser
32.libgdi
32.libwinspool.libcomdlg
32.libadvapi
32.libshell
32.libole
32.liboleaut
32.libuuid.libodbc
32.libodbccp
32.lib/nologo/subsystem:console/incremental:yes/pdb:Debug/tg.pdb/debug/machine:I386/out:Debug/tg.exe/pdbtype:sept.\Debug\tg.obj]Creatingcommandlinelink.exe@C:\DOCUME~1\hp\LOCALS~1\Temp\RSP
17.tmpOutputWindowCompiling...MH.cppLinking...Resultstgexe-0errors0warnings调试成功
4.2测试运行本程序包括2个头文件,分别为Stack.h栈头文件和BiTree.h二叉树头文件,因此应在工程栏里选择C/C++HeaderFile并在文件名中分别输入Stack.h和BiTree.h待所有程序调试完毕后,运行结果如下图
4.1所示图
4.1运行初始界面把代表元素为空的符号设为0,输入ABC00D00E00F,得出的结果如下图
4.2所示图
4.2运行结果5结束语在二叉树的创建过程中没有利用到构造函数来直接构造一个二叉树,这样就不用每次创建一个二叉树时候还要再重新使用一个函数来生成相关的节点另外在栈中,释放内存也没有用析构函数来完成此功能,还用了一个另外一个函数,实在有点费事在二叉树算法的设计中,不仅让我更加理解了二叉树的特点,更加让我锻炼了C++的程序设计能力,并学到了一些常用的程序设计技巧,深刻明白了程序的可读性和健壮性的重大作用以下是本人在编写此过程中的一些心得
1、在程序设计中,经常没有申请内存就开始使用,造成了很大的错误
2、往往在一块内存使用完了之后没有及时释放其内存,虽然在这里没有出现什么错误,但是为以后写其他程序造成了隐患
3、在程序中,使用模板类方便各种数据类型都可以操作,提供了很大方便
4、在输入时,采用用户自定义空标记,方便数据的快速输入
5、在非递归后序遍历中只使用一个节点作为标志域,避免每一个节点都用一个标志域而申请过多的内存造成浪费
6、二叉树的节点申明为友元类便于操作,而不使用结构体更加符合C++语言的思想
7、在递归算法中,用一个无参数的函数调用有参数的函数,更加方便更加合理参考文献
[1]《C++程序设计教程》闵联营何克右主编武汉理工大学出版社
2005.7
[2]《数据结构(C语言版)》严蔚敏吴伟明编著清华大学出版社
2006.8
[3]《数据结构与算法》赵文静祁飞编著科学出版社
2006.8
[4]《C++程序设计实践教程》刘维富等编著清华大学出版社,2007,2
[5]《数据结构(C语言版)》严蔚敏,吴伟民等编著清华大学出版社2007,2
[6]《数据结构》徐孝凯、魏荣等编著 机械工业出版社2004,1
[7]《C语言程序设计教程》秦友淑、曹化工等编著华中科技大学出版社2003,8附录源程序代码/*////////////////////////////////////////////////////////////////////////////////名称UnitName:Stack.h栈头文件//作者Author:Hector何松柏//备注Remarks://////////////////////////////////////////////////////////////////////////////*/#ifndef_STACK_H#define_STACK_H#defineSTACK_INIT_SIZE100//初始栈的最大长度#defineSTACKINCREMENT10//每次新增的栈的长度templateclassDataTypeclassStack{public:Stack;voidPushDataTypee;//插入为e的新栈顶元素intPopDataTypee;//删除栈顶元素intGetTopDataTypee;//取出栈顶元素intStackEmpty;//判断栈是否为空空返回voidDestroyStack;//栈被销毁private:DataType*base;//栈尾DataType*top;//栈顶intstacksize;};/*------------构造函数,创建一个新的空栈--------------*/templateclassDataTypeStackDataType::Stack{if!base=DataType*mallocSTACK_INIT_SIZE*sizeofDataTypeexit1;top=base;stacksize=STACK_INIT_SIZE;}/*--------插入为e的新栈顶元素--------------*/templateclassDataTypevoidStackDataType::PushDataTypee{iftop-base=stacksize{if!base=DataType*reallocbasestacksize+STACKINCREMENT*sizeofDataTypeexit1;top=base+stacksize;stacksize+=STACKINCREMENT;}*top++=e;}/*--------删除栈顶元素--------------*/templateclassDataTypeintStackDataType::PopDataTypee{iftop==basereturn0;e=*--top;return1;}/*--------取出栈顶元素--------------*/templateclassDataTypeintStackDataType::GetTopDataTypee{iftop==basereturn0;e=*top-1;return1;}/*------------判断栈是否为空空返回--------------*/templateclassDataTypeintStackDataType::StackEmpty{returntop==base1:0;}/*------------销毁栈--------------*/templateclassDataTypevoidStackDataType::DestroyStack{freebase;}#endif/*////////////////////////////////////////////////////////////////////////////////名称UnitName:BiTree.h二叉树头文件//作者Author:Hector何松柏//备注Remarks://////////////////////////////////////////////////////////////////////////////*/#ifndef_BITREE_H#define_BITREE_H#includeStack.htemplateclassDataTypeclassBiTree;//友元类引用申明/*--------树的节点定义,将BiTree定义为友元类,便于对其操作-----------*/templateclassDataTypeclassTreeNode{TreeNode:lchildNULLrchildNULL{}friendclassBiTreeDataType;private:DataTypedata;TreeNode*lchild*rchild;};/*--------二叉树树开始-----------*/templateclassDataTypeclassBiTree{public:voidCreateBiTree;//创建根节点------主过程voidCreateBiTreeTreeNodeDataType*p;//创建节点函数----子过程voidPosROrderTraverse;//递归------后序遍历二叉树---主过程voidPosROrderTraverseTreeNodeDataType*p;//递归------后序遍历二叉树---子过程voidPosOrderTraverse;//非递归------后序遍历二叉树private:TreeNodeDataType*root;//树根DataTypetemp;//代表元素为空的符号};/*--------创建根节点----主过程--------------*/templateclassDataTypevoidBiTreeDataType::CreateBiTree{cout请输入代表元素为空的符号:;cintemp;if!root=TreeNodeDataType*mallocsizeofTreeNodeDataTypeexit1;cout请输入数据:endl;CreateBiTreeroot;}/*--------创建节点函数----子过程--------------*/templateclassDataTypevoidBiTreeDataType::CreateBiTreeTreeNodeDataType*p{TreeNodeDataType*px;if!px=TreeNodeDataType*mallocsizeofTreeNodeDataTypeexit1;cinpx-data;ifpx-data==temp{p=NULL;freepx;}else{p=px;CreateBiTreepx-lchild;CreateBiTreepx-rchild;}}/*--------递归------后序遍历二叉树---主过程--------------*/templateclassDataTypevoidBiTreeDataType::PosROrderTraverse{PosROrderTraverseroot;}/*--------递归------后序遍历二叉树---子过程--------------*/templateclassDataTypevoidBiTreeDataType::PosROrderTraverseTreeNodeDataType*p{ifp{PosROrderTraversep-lchild;PosROrderTraversep-rchild;coutp-data;}}/*--------非递归------后序遍历二叉树(没有使用标志域)--------------*/templateclassDataTypevoidBiTreeDataType::PosOrderTraverse{StackTreeNodeDataType*S;TreeNodeDataType*p;TreeNodeDataType*r;//使用r节点表示访问了右子树替代标志域p=root;whilep||!S.StackEmpty{ifp{S.Pushp;p=p-lchild;}else{S.GetTopp;ifp-rchildp-rchild!=r{p=p-rchild;S.Pushp;p=p-lchild;}else{S.Popp;coutp-data;r=p;p=NULL;}}}S.DestroyStack;}#endif/*----------------基本测试文件-------Author:Hector-------*/#includeiostream#includeBiTree.husingnamespacestd;intmain{BiTreecharmy;my.CreateBiTree;my.PosROrderTraverse;coutendl;my.PosOrderTraverse;return0;}系统实现栈的建立插入元素删除元素后序算法niltop栈顶datenext栈底ana1进栈出栈栈顶栈底查找栈顶和栈底的位置判断位置是否相等NY删除栈顶元素不做任何操作开始将当前节点指针指向根节点获取当前节点的下一个子节点是否获得将当前节点压入栈中,然后将当前节点指针指向获得的节点将当前节点指针指向弹出节点对当前节点进行操作从栈中弹出一个节点是否为空结束是否是否。