数据结构说明书

引言 错误!未定义书签。一、 设计要求 错误!未定义书签。TOC\o"1-5"\h\z二、 算法原理及思想 11、 遍历概念 12、 遍历方案 22.1遍历方案 22.2三种遍历的命名 23、 二叉树的链式存储结构 23.1、 结点的结构 23.2、 结点的类型说明 33.3、 二叉链表 34、 二叉树的非递归遍历（用栈实现） 44.1先序非递归算法 44.2中序非递归算法 54.3后序非递归算法 6三、 遍历过程 6四、 程序测试 8五、 实验总结 8六、 参考文献 9\o"CurrentDocument"附录：源代码 101选题背景《数据结构》在计算机科学中是一门综合性的专业基础课.数据结构的研究不仅涉及到计算机的硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题.在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方面.因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程.在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起來的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。乂如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树來描述。满二叉树，完全二叉树，排序二叉树。二叉树是树形结构的一个重要类型。许多实际问题抽象出來的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二义树显得特别重要。此程序主要实现二叉树的遍历并且是基于栈的非递归遍历方法。2方案论证2.1遍历概念所谓遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。2.2遍历方案2.2.1遍历方案从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：访问结点本身(N),遍历该结点的左子树(L),遍历该结点的右子树(R)。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL>RLN。2.2.2三种遍历的命名根据访问结点操作发生位置命名:NLR：前序遍历(亦称(PreOiderTiee先序遍历))——访问结点的操作发生在遍历其左右子树之前。LNR:中序遍历(LiOrdeiTiee)——访问结点的操作发生在遍历其左右子树之中(间)。LRN：后序遍历(PostOrdeiTree1)——访问结点的操作发生在遍历其左右子树之后。2.3二叉树的链式存储结构2.3.1结点的结构二叉树的每个结点最多有两个孩子。用链接方式存储二义树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lcluld和［Child,分别指向该结点的左孩子和右孩子。结点的结构为：lchilddatarchild图1链式存储结点结构2.3.2结点的类型说明typedefstmctBiNode{DataTvpedata;//数据域sti-uctBiNode*LCluld;//左孩子stmctBiNode*RCluld;〃右孩子}BiTNode,*BiTree;2.3.3二叉链表在一棵二叉树中，所有类型为BmTNode的结点，再加上一个指向开始结点（即根结点）的BinTree型头指针（即根指针）wot,就构成了二义树的链式存储结构，并将其称为二叉链表。如图2所示：图2二叉链表存储的二叉树注意:一个二叉链表由根指针wot惟一确定。若二叉树为空，则root=NULL：若结点的某个孩子不存在，贝IJ相应的指针为空。具有n个结点的二叉链表中，共有2n个指针域。其中只有ml个用来指示结点的左、右孩子，其余的n十1个指针域为空。〃建立二叉树的二叉链表存贮结构voidCreateBiTree（BiTiee*bt）DataTvpech;ch=getchaiQ;if(ch=='•)*bt=NULL;}else{*bt=(BiTfee)malloc(sizeof(BiTNode));(*bt)->data=ch;CieateBiTree(&((*bt)->LChild));CieateBiTree(&((*bt)->RChild));}}2.4二叉树的非递归遍历(用栈实现)2.4.1先序非递归算法VoidPreOrderTree(BiTreeroot){inttop=-1;BiTNode*Stack[MAX_STACK_SIZE]={NULL};BiTNode*p;p=root:while(p!=NULL||top!=-1){while(p!=NULL){if(top>MAX_STACK_SIZE){return;}top++;Stack[top]二(BiTNode*)malloc(sizeof(BiTMode));if(NULL=Stack[top])return;}Stack[top]=p:printf("%c “，p-〉data);p=p->LChild;}辻(NULL==p&&top!=-1){p=Stack[top];top一-；p=p->RChild;}}}2.4.2中序非递归算法voidInOrderTree(BiTreeroot){inttop=-1;BiTNode*Stack[MAX_STACK_SIZE]={NULL};BiTNode*p;p=root;while(p!=NULL||top!=-1){while(p!=NULL){if(top>MAX_STACK_SIZE){letinn;}tOp-H-；Stack[top]=(BiTNode*)malloc(sizeof(BiTNode));if(NULL=Stack[top])lennn;}Stack[top]=p;p=p->LCluld;}if(NULL=p&&top!=-1){p=Stack[top];top-;prmtf(u%cp->data);p=p->RChild;}}}2.4.3后序非递归算法voidPostOfderTiee(BiTreeloot){mttop=-1;BiTNode*p,*q;BiTieeStack[MAX_STACK_SIZE]={NULL};q=NULL;p=root;wlule(p!=NULL||top!=-1){while(p!=NULL){tOp-H-；if(top>=MAX_STACK_SIZE){pnntfC，栈溢出！\n*');letuin;}Stack[top]=(BiTiee)malloc(sizeof(BiTNode));Stack[top]=p;p=p->LCluld;}if(top>-1)p=Stack[top];if((NULL==p->RChild)||(p->RChild==q))pnntf(H%cp->data);q=p；top—;p=NULL;}printf(,,\nu);}3过程论证4结果分析输入先序遍历序列ABCDEGF,即可得到非递归的先序、中序、后序遍历的结果;如下：口■F:\c♦t\Debug\tree.exe* 卜■倉诗输人先序序列：ABCDEGP用桟实现二叉树的遍历结果如下:先序追历结果为'nBCDEGP中序遍历结果为.C B E G D PA后序迫历结臬为，C G E F D BAPw83anykeytocontinue图4测试结果5实验总结与分析通过这次的设计，我学到了很多。本次设计是一个模块划分比较清晰地程序，分别将三种遍历方式（先序、中序、后序遍历）用三个函数写出來，实现了封装性。本次设计所包含的知识面比较广，所以必须要把所学的知识融会贯通才行；当然，程序也有些许不足之处，比如：有一些模块还没有实现；软件的一些细节性问题还是有待进一步完善。细节问题是很多的，只有动手做时才知道自己学的有多么肤浅，应用不当就出错而且错误很费神，理论与实际差距的确很大，要想作出实际实用的东西來还需多多练习，不断改进，充分发挥所学知识，另外也应加强视野的开拓，现学现卖自己拯救，学会搜索有用的信息，这样才能作出满意的东西来。参考文献《数据结构一C语言描述》耿国华高等教育出版社《数据结构教程（C语言版）》严蔚敏清华大学出版社附录：源代码^include<stdio.h>^include<malloc・h>SdefineMAX_STACK_SIZE50//栈最大长度typedefcharDataType;〃二义树数据结构定义typedefstructBiNode{DataTypedata;structBiNode*LChild;structBiNode*RChild;}BiTNode,*BiTree;〃建立二义树的二义链表存贮结构voidCreateBiTree(BiTree*bt){DataTypech;ch=getchar();if(ch== '){*bt=NULL;}else*bt二(BiTree)malloc(sizeof(BiTNode)):(*bt)->data二ch;CreateBiTree(&((*bt)->LChild));CreateBiTree(&((*bt)->RChild));}}//用栈实现先序遍历voidPreOrderTree(BiTreeroot)inttop=-1;BiTNode*Stack[MAX_STACK_SIZE]={NULL};BiTNode*p;p=root;while(p!=NULL||top!=-1){while(p!=NULL){if(top>MAX_STACK_SIZE){return;}top++;Stack[top]=(BiTNode*)malloc(sizeof(BiTNode)):if(NULL==StackEtop]){return;}Stack[top]=p;printf(”％c“，p-〉data);p=p->LChild;}辻(NULL==p&&top!=-1){p=Stack[top];top一-；p=p->RChild;}}}〃用栈实现中序遍历voidInOrderTree(BiTreeroot){inttop=-1;B辽Node*Stack[MAX_STACK_SIZE]={NULL};BiTNode*p;p=root;wh订e(p!=NULL||top!=-1){while(p!=NULL){if(top>MAX_STACK_SIZE){return;}top++;Stack[top]=(BiTNode*)malloc(sizeof(BiTNode)):if(NULL==StackEtop]){return;}Stack[top]=p;p=p->LChild;}辻(NULL==p&&top!=-1){p=Stack[top];top―;printf("%c “，p-〉data);p=p->RChild;}}}〃用栈实现后序遍历voidPostOrderTree(BiTreeroot)inttop=-1;BiTNode*p,*q;BiTreeStack[MAX_STACK_SIZE]二{NULL}:q=NULL;p=root;while(p!=NULL||top!=-1){while(p!=NULL){top卄；if(top>=MAX_STACK_SIZE){printf(〃栈溢出!\n");return;}Stack[top]=(BiTree)malloc(sizeof(BiTNode)):Stack[top]=p;p=p->LChild;}if(top>-1){p=Stack[top];if((NULL==p->RChild)||(p->RChild==q)){printf("%c ”，p->data);Q=P；t