数据结构课程设计.doc

数据结构课程设计目 录1.需求分析12.概要设计22.1 功能设计22.2 算法流程图33.详细设计43.1创建二叉树43.2二叉树的递归遍历算法（前、中、后）43.3二叉树的层次遍历算法43.4二叉树的非递归遍历算法（前、中、后）43.5退出54.测试数据与分析64.1测试数据以及结果预测64.2程序运行界面64.3算法分析85.设计体会及今后的改进意见9参 考 文 献101.需求分析数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业基础课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。数据结构只要研究四个方面的问题：(1)数据的逻辑结构，即数据之间的逻辑关系；(2)数据的物理结构，即数据在计算机内的存储方式；(3)对数据的加工，即基于某种存储方式的操作算法；(4)算法的分析；即评价算法的优劣。本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。本程序用VC+6.0编写，可以实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及 能查找任一结点在某种遍历序列中的前驱和后继。根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。(1) 先创建二叉树：按先序次序输入，构造二叉链表表示的二叉树。(2) 设计算法：先序遍历,中序遍历,后序遍历. 在做到层序遍历时，应注意算法如下：根结点入队，队头元素出队，左孩子不为空入队右孩子不为空入队的顺序进行。(3) 设计main()函数调用以上步骤实现相关功能。2.概要设计2.1 功能设计（1）typedef struct BTNode定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。和单链表类似，一个二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空。并且结点内容的数据类型为字符型。（2）CreateBiTree(BiTree &T)此函数的功能是构建二叉树。从键盘上按先序次序输入字符构造二叉链表表示的二叉树T，其中用星号表示空树 。（3）NRPreOrder(BiTree bt) 此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。（4）NRInOrder(BiTree bt)此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。（5）NRPostOrder(BiTree bt)此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈1：遍历左子树的现场保护，2：遍历右子树前的现场保护。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。（6）PreOrderTraverse(BiTree T) 函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。（7）InOrderTraverse(BiTree T)函数功能是用递归的方法对二叉树进行中序遍历，调用此函数可以获得二叉树的递归的中序遍历的结果。（8）PostOrderTraverse(BiTree T)函数功能是用递归的方法对二叉树进行后序遍历，调用此函数可以获得二叉树的递归的后序遍历的结果。（9）main()主函数用while()与switch(select)语句对二叉树的操作的算法进行了设计。可以实现以上函数的功能，并能退出程序。2.2 算法流程图 先设计出二叉树的一些算法的函数，如非递归遍历、递归遍历、层次遍历等一些算法。然后在主函数中逐一调用。其中，在求任意结点在中序遍历前驱后继算法时利用了递归的中序遍历的算法。 算法流程图如图1所示。Main()CreateBiTree ()构造二叉树PreOrderTraverse()NRPreOrder（）分别输出递归与非递归先序遍历结果InOrderTrave（）NRInOrder（）分别输出中序递归与非递归遍历结果PostOrderTravesr()NRPostOrder（）分别输出递归与非递归的后序遍历结果求结点的中序前驱后继中序InOrderTraver（） 图 2-1 算法流程图3.详细设计3.1创建二叉树(1)定义二叉树结点值的类型为字符型。(2)结点个数不超过10个。(3)按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。3.2二叉树的递归遍历算法（前、中、后）DLR(1)访问根结点。(2)先序遍历根结点的左子数。(3)先序遍历根结点的右子数。LDR(1)先序遍历根结点的左子数。(2)访问根结点。(3)先序遍历根结点的右子数。LRD(1)先序遍历根结点的左子数。(2)先序遍历根结点的右子数。(3)访问根结点。3.3二叉树的层次遍历算法(1)访问该元素所指结点。(2)若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。3.4二叉树的非递归遍历算法（前、中、后）(1)非递归的先序遍历算法a.访问结点的数据域。b.指针指向p的左孩子结点。c.从栈中弹出栈顶元素。d.指针指向p的右孩子结点。(2)非递归的中序遍历算法a.指针指向p的左孩子结点。b.从栈中弹出栈顶元素。c.访问结点的数据域。d.指针指向p的右孩子结点。(3)非递归的后序遍历算法bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。3.5退出4.测试数据与分析4.1测试数据以及结果预测（1）预测数据如图2所示（2）结果预测：递归遍历：先序遍历：a b d e c f g图 4-1 预测数据中序遍历：d b e a f c g后序遍历：d e b f g c a层次遍历层序遍历：a b c d e f g非递归遍历：先序遍历：abdecgf中序遍历：dbeafcg后序遍历：debfgca4.2程序运行界面（1）开始界面 图4-2 开始界面（2）建树界面图4-3 建树界面(3)二叉树的递归遍历算法执行界面图4-4 二叉树的递归遍历算法执行界面（4）二叉树的层次遍历算法运行界面 图4-5 二叉树的层次遍历算法运行界面(5)二叉树的非递归遍历算法执行界面 图4-6二叉树的非递归遍历算法执行界面（6）退出界面图4-7 退出界面（7）输入错误界面 图4-8 输入错误界面4.3算法分析本程序按递归遍历所耗费的时间复杂度为O（n），其所耗费的空间复杂度也为O（n）。5.设计体会及今后的改进意见 通过这几天的课程设计实验，我对二叉树、二叉树的遍历等相关知识有了更为深入的了解，同时对于C语言中那句“程序=算法+数据结构”有了真切的体会，也对C语言有了更为全面的认识。当然自己在C语言编程能力上的提高时很明显的。虽然这几天的实验不是很顺利，经常出错，但是通过和同学们的讨论，在同学们的帮助都得到了解决。几天的时间，在知识方面有了提高。参 考 文 献1 耿国华. 数据结构C语言描述.北京:高等教育出版社,2005 2 何钦铭.C语言程序设计.北京:高等教育出版社，2008附录：实验源程序#include iostream.h#include stdlib.h#include stdio.htypedef char ElemType;/定义二叉树结点值的类型为字符型const int MaxLength=10;/结点个数不超过10个typedef struct BTNode ElemType data; struct BTNode *lchild,*rchild;BTNode,* BiTree;void CreateBiTree(BiTree &T)/按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树/ if(T) return; char ch; ch=getchar(); /不能用cin来输入，在cin中不能识别空格。 if(ch= ) T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) coutdata=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); void PreOrderTraverse(BiTree T)/先序遍历 if(T) coutdatalchild); PreOrderTraverse(T-rchild); void InOrderTraverse(BiTree T)/中序遍历 if(T) InOrderTraverse(T-lchild); coutdatarchild); void PostOrderTraverse(BiTree T)/后序遍历 if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutdata ; void LevelOrderTraverse(BiTree T)/层序遍历 BiTree QMaxLength; int front=0,rear=0; BiTree p; if(T) /根结点入队 Qrear=T; rear=(rear+1)%MaxLength; while(front!=rear) p=Qfront; /队头元素出队 front=(front+1)%MaxLength; coutdatalchild) /左孩子不为空，入队 Qrear=p-lchild; rear=(rear+1)%MaxLength; if(p-rchild) /右孩子不为空，入队 Qrear=p-rchild; rear=(rear+1)%MaxLength; /非递归的先序遍历算法void NRPreOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top0) while(p!=NULL) coutdata; stacktop=p; top+; p=p-lchild; if (top0) top-; p=stacktop; p=p-rchild; /非递归的中序遍历算法void NRInOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top0) while(p!=NULL) stacktop=p; top+; p=p-lchild; if (top0) top-; p=stacktop;coutdata; p=p-rchild; /非递归的后序遍历算法typedef struct BiTree ptr; int tag;stacknode;void NRPostOrder(BiTree bt) stacknode sMaxLength,x; BiTree p=bt; int top; if(bt!=NULL) top=0;p=bt; do while (p!=NULL) /遍历左子树 stop.ptr = p; stop.tag = 1; /标记为左子树 top+; p=p-lchild; while (top0 & stop-1.tag=2) x = s-top; p = x.ptr; coutdata; /tag为R，表示右子树访问完毕，故访问根结点 if (top0) stop-1.tag =2; /遍历右子树 p=stop-1.ptr-rchild; while (top0);/PostOrderUnrecvoid main() BiTree T; T=NULL; int select; /cout请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):endl;/ CreateBiTree(T); while(1) coutnn请选择要执行的操作:n; cout1.创建二叉树n; cout2.二叉树的递归遍历算法（前、中、后）n; cout3.二叉树的层次遍历算法n;cout4.二叉树的非递归遍历算法（前、中、后）n; coutselect; switch(select) case 0:return; case 1: cout请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):endl; CreateBiTree(T); break; case 2: if(!T) cout未建立树，请先建树！; else coutn先序遍历:n; PreOrderTraverse(T); coutn中序遍历:n