精品资料
精品资料
《数据结构》
第六次实验报告
学生姓名
学生班级
学生学号
指导老师
一、实验内容
1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。
2) 输出树的深度，最大元，最小元。
二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。
递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子 递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结 束一层递归调用。直到递归全部结束。
下面重点来讲述非递归方法：
首先介绍先序遍历： 先序遍历的顺序是根 左 右，也就是说先访问根结点然后访问其左子再然后 访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈， 输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左 子树访问结束， 栈顶结点指针出栈， 指针指向其右子， 对其右子树进行访问， 如此循环，直至结点指针和栈均为空时，遍历结束。
再次介绍中序遍历：
中序遍历的顺序是左 根 右，中序遍历和先序遍历思想差不多，只是打印顺 序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指 向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并 输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循 环直至结点指针和栈均为空，遍历结束。
最后介绍后序遍历： 后序遍历的顺序是左 右 根，后序遍历是比较难的一种，首先需要建立两个 栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点， 如果结点的指针不为空， 根结点入栈，与之对应的标志位也随之入标志位栈， 并赋值 0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结 点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出 栈，如果相应的标志位值为 0，表示右子树还没有访问，指针指向其右子， 父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为 1，表示
右子访问过。如果相应的标志位值为 1，表示右子树已经访问完成，此时要 输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和 栈均为空，遍历结束。
三、详细设计
源代码：
#include<stdio.h>
#define MAX 100 // 表示栈的最大容量
#define FULL 99// 表示栈满
#define EMPTY -1// 表示栈空
typedef struct Tnode // 定义结点 {
char data;// 存储结点数据
struct Tnode *left;// 定义结点左子指针
struct Tnode *right;// 定义右子指针
}Tnode,*Pnode;// 声明 Tnode 类型的变量和指针 typedef struct Stack// 定义栈 {
Pnode pnode[MAX];// 存放数据
int p;// 栈顶指针 }Stack,*Pstack;// 定义 Stack 类型的变量和指针 void Push (Pstack pstack,Pnode pnode)// 入栈
{
pstack->p ++;
pstack->pnode[pstack->p] = pnode;// 赋值
}
Pnode Pop(Pstack pstack)// 出栈
{
return pstack->pnode[pstack->p--];
}
Pnode Top (Pstack pstack)// 看栈顶元素
{
return pstack->pnode[pstack->p];
}
int Isempty (Pstack pstack)// 栈判空
{
if(pstack->p==EMPTY)
return 1;
else
return 0;;
}
int Isfull (Pstack pstack )// 栈满
{
if (pstack ->p==FULL)
return 1;
else
return 0;
}
void Initstack (Pstack pstack)// 初始化栈
pstack->p=EMPTY;
}
void Inittnode(Pnode root,Pnode left,Pnode right,char data)// 初始化结点 {
root->left=left;
root->right = right;
root->data = data;
}
void PreorderR(Pnode proot)// 递归先序遍历算法
{
if(proot)
{
printf("%2c",proot->data);
PreorderR(proot->left);
PreorderR(proot->right);
}
}
void InorderR(Pnode proot)// 递归中序遍历算法
{
if(proot)
{
InorderR(proot->left);
printf("%2c",proot->data);
InorderR(proot->right);
}
}
void PostorderR(Pnode proot)// 递归后序遍历算法
{
if(proot)
{
PostorderR(proot->left);
PostorderR(proot->right);
printf("%2c",proot->data);
}
}
void PreorderI(Pnode proot,Pstack pstack)// 非递归先序遍历算法
{
Initstack(pstack);// 初始化栈
while(proot||!Isempty(pstack))// 如果栈空并且结点指针空，则结束循环 {
if(proot)
{
printf("%2c",proot->data);
if(Isfull(pstack))// 如果栈满不能执行入栈操作 {
printf(" 栈满，不能执行入栈操作！！ "); return;
}
Push(pstack,proot);// 入栈 proot=proot->left;// 指针指向左子
}
else
{
if(Isempty(pstack))// 栈空时不能出栈
{
printf(" 栈空，不能执行出栈操作！！ ");
return;
}
proot = Pop(pstack);// 执行出栈操作
proot=proot->right;// 指针指向右子
}
非递归中序遍历算法}
非递归中序遍历算法
void InorderI(Pnode proot,Pstack pstack)//
{
Initstack(pstack);// 初始化栈
while(proot||!Isempty(pstack))// 循环结束条件
{ if(proot)
{
if(Isfull(pstack))
{
printf(" 栈满，不能执行入栈操作！！ "); return;
}
Push(pstack,proot);// 执行入栈操作
proot = proot->left;// 指针指向左子
}
else
{
if(Isempty(pstack))
{
printf(" 栈空，不能执行出栈操作！！ "); return ;
}
proot = Pop(pstack);// 出栈 printf("%2c",proot->data);// 打印数据
proot=proot->right;//
指针指向右子
}
}
void PostorderI(Pnode proot,Pstack pstack)// 非递归后续遍历算法
{
int flags[MAX];// 定义标志位栈
int p =-1;// 初始化标志位栈
int flag;// 存放标志位
Initstack(pstack);// 初始化栈 while(proot||!Isempty(pstack))// 循环结束条件
{
if(proot)
{
if(Isfull(pstack))
{
printf(" 栈满，不能执行入栈操作！！ "); return ;
}
flags[++p] = 0;// 标志位置 0，并入栈
Push(pstack,proot);// 结点入栈 proot=proot->left;// 指针指向左子 }
else
{
proot = Pop(pstack);// 指针出栈
flag = flags[p--];// 相应标志位出栈
if(flag==0)// 如果标志位为 0 表示右子还未访问过 {
flag =1;// 将标志位置 1，右子已访问 flags[++p] = flag;// 标志位入栈 Push(pstack,proot);// 结点入栈
proot = proot->right;// 指针指向右子
} else
{
printf("%2c",proot->data);// 打印数据 proot = NULL;// 将结点指针置空
}
}
}
}
void main ()
Tnode A,B,C,D,E,F,G;// 声明结点变量
Stack stack;// 声明栈
Inittnode(&A,&B,&C,'A');// 初始化结点 Inittnode(&B,NULL,&D,'B');
Inittnode(&C,&E,&F,'C');
Inittnode(&D,NULL,NULL,'D');
Inittnode(&E,NULL,NULL,'E'); Inittnode(&F,&G,NULL,'F');
Inittnode(&G,NULL,NULL,'G');
printf(" 你定义的树的结构是： \n");
/* 一下是调用相应的函数输出遍历结果 */
printf("A(B(D)C(E F(G)))\n");
printf("===================== 下面是遍历结果 ====================\n"); printf("===================== 递归先序遍历： ====================\n"); PreorderR(&A);
printf("\n");
printf("===================== 非递归先序遍历： ==================\n"); PreorderI(&A,&stack);
printf("\n");
printf("===================== 递归中序遍历： ====================\n"); InorderR(&A);
printf("\n");
printf("===================== 非递归中序遍历： ==================\n"); InorderI(&A,&stack);
printf("\n");
printf("===================== 递归后序遍历： ====================\n"); PostorderR(&A);
printf("\n");
printf("===================== 非递归后序遍历： ==================\n"); PostorderI(&A,&stack);
printf("\n");
}
五、遇到的问题及解决办法 这部分我主要遇到如下两个问题，其内容和解决方法如下所列： 执行程序时程序停止运行，其效果如图：
解决方法：看到程序停止运行，推测可能的原因：遇到死循环、参数设置不合 理或者结构体没有造好。首先对结构体进行了检查，各个成员声明正常无误，在 对程序进行调试，程序正常跳出循环，因此最可能是自定义函数的参数设置的不 合理，因此对调用的自定义函数进行相应的改动， 将参数由具体类型改为指针类 型后，程序正常运行。
程序不停的输出同一个结点的数据，其效果入图：
DDDODLDDDDDDDDCDDDDDDDDDDDDD^DODEDDDDDDDDCnDDDDBDODEDDDDDDDEBBD珈DDDDDDDDDDDODD *
IDDDDDDrDDD^DTEDDDDDDDDOEDDDDDDDDrDTiDDDDDCDrDDDDDDDDrDDDDDTCDDDDDDDDOEEDDDOD? ■■DODDDIlDDDDDDDDCDDDDDDDDDDDDDDDmDLDIWDDDDCnDDDDDEmDDIWDDOECDrDDDDDDDDDDDDDDDD
DMDDDDDDEDDDDDDDDDDDDDDDDDMFHTDDDDDDDITDDDDDDDDDDDDDDDDDDDMDDDJDDDDDDDJDmD
Dl?DOljlJDDDDDDUlXJLiBDi)DiJDUl'lJDDDJDJUlJDBDDDDD￡l[lDDDD])LJDlJlJDDBDDJDLlJLiDDDDJLJUDlJDDDJDJDD hDDDDDDDDDDDDDDDDDDDDDDDDDDDMDDDDDDDDDDD 師 DDDDDDDDDDDDMDDDDDEDDDDDDDDDDDDJDODD ” DJDODDDDDDIWDCDDDDDODODDDDDDDODDDDDDJDDDCDDEDDDDDIXDDDDDDCIDDDDDDDDODDDDDDDDDD joJDCDDDDDDIWDCDDDDDCDtBDDDDDDOnDDDBDDDnDCDDDDDDDDDCDDDDDDODCDDDDDODDDDDDDDDOnD pi?DDDCDDDDDDDECDDDDDDDDDDDDD^DODDDDDDDDDECDDDDDDDDEl]DDDDDDDK)DDDDDDDDDCDDDDX)DD tDDDODrDDnDDDDDIlDBDnDnDDnrDDDOmnrDDDDDDDEIinDDDDBDODnDDnDDDnnirinDDD^DDnPDDromnD
I)D3XDCEDDDDDDDDDDDDDDXDDDDDJ[>DDDDDDDDDDDELDDDDDXDDDDDDDDDDDDDDDDD?DCDDD3I>DDD pDODDDrDDDDDOODCDDDDUDDDDDDDDDDDDWDBDBDDDCDDDDDBDDDDDDDDDDDIXDDDDDDDDDBDDDiDBDDDr； pDDDDDDDEDDDOliDDDDDDDDDCDDDDDDDDDimDDDDDDDDDDDDDDDinDDDDimXDDDD 血 DDnDDDDDDUJD 叵 ■DD0DC'LrPDD3DDDEEDDDDDDD0rPDDD^D3ErTiriDDD3DrrrDDDDDDGDrDEDDDDDCEDI)DDDDDC[riDDD3D3Er
ED0DDDLDDDDDDE'EEDDD[)DDDOrDDEDDDODL!DHDDDDDCD[DDDD])D[jDCDDDDDDDCEDDDDDDDO[LiDDDBDODD bDODCmDDDDDDnffiDDDDDDDDDDDDDDDDDDDDDDDDDDCDDDDDDDCnCDDDDDDDDCDDDDDDDnDIinDDDDnDD DDDDLlLLiDDJDJDEEDDDBDDDOLUDDDDDJElDLiDDDJDLlJLlJDDDUDOLLLiDDDDJDLEDDDBDDDOLLiDDDBDJrE pDDMrDDDDDOrroDDDDDtWDDDDDDDDCEDDDDDDDrcrDDDDIJDDDDDDDDDDDrEDDDDDDDDDEDrD^DTD Fdjdoddddddjmtu 讪 dddddeddddddddddddddddddcdddddddddddddddocdcdddddodddddddddddd
解决方法：分析运行结果可知， 第一不停的输出证明遇到了死循环， 第二输出的是同一
个结点的数据，表示指针没有按预期进行指向， 首先对程序进行调试， 发现程序没有添加循 环结束条件，添加循环结束条件后，只能输出树的部分结点的数据，对标志位进行修改后, 程序运行正常，也能正确输出遍历结果。
六、心得体会
通过这次作业真的受益匪浅，感触良多：
首先，要提高编程能力，必须多动手，多实践，而不是仅仅局限在书本上，更不能 眼高手低。眼高手低，懒得动手，这就犯了编程人员的大忌。
大一我们开始接触 C语言， 这是我们接触到的第一种编程语言， 但是当时徒有对编程的兴趣， 却没有付诸行动， 动
手少，结果考试险过，通过这次作业，我再次看了 C语言课本，边看边写代码，理解快， 印象深刻，思维也活跃许多，状态也好，真正的意识到，编程能力需要靠实践来提升。
当自己写出意想的程序后，真的有些成就感。 再者，在吴老师的指导和要求下，我们改
掉了很多的编程坏习惯的同时也养成了良好的编程习惯，另一方面我们态度端正了很 多，认真完成好每一项任务， 这样无形中提高了对自己的要求， 同时也增强了我们的动
手能力和编程能力。
七、附录 运行结果截图
Welcome To
Download !!!
欢迎您的下载，资料仅供参考！
