实验报告May 14 2015
姓名:陈斌学号:E11314079 专业:13计算机科学与技术数据结构第三次实验
学号E11314079专业计算机科学与技术姓名陈斌
实验日期2015.05.14教师签字成绩
实验报告
【实验名称】树和二叉树(一)
【实验目的】
1.掌握二叉树的二叉链表存储表示;
2.掌握二叉树的遍历算法;
3.运用遍历算法求解有关问题。
【实验内容】
1.必做内容
任务1:以算法6.4创建二叉树的存储结构,树的具体形态自定。
任务2:对任务1中的二叉树分别实现先序、中序、后序遍历(递归实现)和中序遍历的非递归实现以及层序遍历;
任务3:统计1中树的结点总数、叶子结点总数以及树的高度;
源代码:
head.h:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//OVERFLOW 在math.h 中已定义为3
typedef int Status;
typedef int Boolean; // 布尔类型
head2.h:
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针*/
}LinkQueue;
Status InitStack(SqStack &S)
{ /* 构造一个空栈S */
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); /* 存储分配失败*/
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack &S)
{ /* 若栈S为空栈,则返回TRUE,否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
Status GetTop(SqStack &S,QElemType &e)
{ /* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */
if(S.top>S.base)
{
e=*(S.top-1);
return OK;
}
else
return ERROR;
}
Status Push(SqStack &S,QElemType &e)
{ /* 插入元素e为新的栈顶元素*/
if(S.top-S.base>=S.stacksize) /* 栈满,追加存储空间*/
{
S.base=(SElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); /* 存储分配失败*/
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,QElemType &e)
{ /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status InitQueue(LinkQueue &Q)
{ /* 构造一个空队列Q */
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
Status QueueEmpty(LinkQueue &Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
Status EnQueue(LinkQueue &Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素*/
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败*/
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */ QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return OK;
}
main.cpp:
typedef char TElemType;
#include"head.h"
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree QElemType; /* 设队列元素为二叉树的指针类型*/
typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型*/
#include"head2.h"
Status InitBiTree(BiTree &T)
{ /* 操作结果: 构造空二叉树T */
T=NULL;
return OK;
}
Status CreateBiTree(BiTree &T)
{ // 算法6.4:按先序次序输入二叉树中结点的值(字符型),构造二叉链表表示的二叉树T。
TElemType ch;
scanf("%c",&ch);
if(ch==' ') /* 空*/
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data=ch; /* 生成根结点*/
CreateBiTree(T->lchild); /* 构造左子树*/
CreateBiTree(T->rchild); /* 构造右子树*/
}
return OK;
}
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。算法6.1 */ /* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次*/
if(T) /* T不空*/
{
if(Visit(T->data)) /* 先访问根结点*/
if(PreOrderTraverse(T->lchild,Visit)) /* 再先序遍历左子树*/
if(PreOrderTraverse(T->rchild,Visit)) /* 最后先序遍历右子树*/
return OK;
return ERROR;
}
else
return OK;
}
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数*/
/* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次*/
if(T)
{
if(InOrderTraverse(T->lchild,Visit)) /* 先中序遍历左子树*/
if(Visit(T->data)) /* 再访问根结点*/
if(InOrderTraverse(T->rchild,Visit)) /* 最后中序遍历右子树*/
return OK;
return ERROR;
}
else
return OK;
}
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数*/
/* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次*/ if(T) /* T不空*/
{
if(PostOrderTraverse(T->lchild,Visit)) /* 先后序遍历左子树*/
if(PostOrderTraverse(T->rchild,Visit)) /* 再后序遍历右子树*/
if(Visit(T->data)) /* 最后访问根结点*/
return OK;
return ERROR;
}
else
return OK;
}
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType))
{ /* 采用二叉链表存储结构,Visit是对数据元素操作的应用函数。*/
/* 中序遍历二叉树T的非递归算法(利用栈),对每个数据元素调用函数Visit */ SqStack S;
InitStack(S);
while(T||!StackEmpty(S))
{
if(T)
{ /* 根指针进栈,遍历左子树*/
Push(S,T);
T=T->lchild;
}
else
{ /* 根指针退栈,访问根结点,遍历右子树*/
Pop(S,T);
if(!Visit(T->data))
return ERROR;
T=T->rchild;
}
}
printf("\n");
return OK;
}
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType))
{ /* 采用二叉链表存储结构,Visit是对数据元素操作的应用函数。算法6.2 */ /* 中序遍历二叉树T的非递归算法(利用栈),对每个数据元素调用函数Visit */ SqStack S;
BiTree p;
InitStack(S);
Push(S,T); /* 根指针进栈*/
while(!StackEmpty(S))
{
while(GetTop(S,p)&&p)
Push(S,p->lchild); /* 向左走到尽头*/
Pop(S,p); /* 空指针退栈*/
if(!StackEmpty(S))
{ /* 访问结点,向右一步*/
Pop(S,p);
if(!Visit(p->data))
return ERROR;
Push(S,p->rchild);
}
}
printf("\n");
return OK;
}
void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件:二叉树T存在,Visit是对结点操作的应用函数*/
/* 操作结果:层序递归遍历T(利用队列),对每个结点调用函数Visit一次且仅一次*/
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);
EnQueue(q,T);
while(!QueueEmpty(q))
{
DeQueue(q,a);
Visit(a->data);
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
printf("\n");
}
}
Status visitT(TElemType e)
{
printf("%c ",e);
return OK;
}
Status BiTreeNodeNum(BiTree T)//结点总个数
{
if(T)
return BiTreeNodeNum(T->lchild)+BiTreeNodeNum(T->rchild)+1;
else
return 0;
}
Status BiTreeLeafNodeNum(BiTree T)//叶子结点个数
{
if(T)
{
if(!T->lchild&&!T->rchild)
return 1;
else
return BiTreeLeafNodeNum(T->lchild)+BiTreeLeafNodeNum(T->rchild);
}
else return 0;
}
Status BiTreeDepth(BiTree T)//树的深度
{
if(!T)
return 0;
else
return
(BiTreeDepth(T->lchild)>BiTreeDepth(T->rchild)?BiTreeDepth(T->lchild):BiTreeDepth(T->rc hild))+1;
}
void main()
{
BiTree T;
InitBiTree(T);
cout<<"请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树):"< CreateBiTree(T); cout<<"先序遍历序列:"< PreOrderTraverse(T,visitT); cout< cout<<"中序遍历序列:"< InOrderTraverse(T,visitT); cout< cout<<"后序遍历序列:"< PostOrderTraverse(T,visitT); cout< cout<<"中序遍历的非递归实现1(利用栈):"< InOrderTraverse1(T,visitT); cout<<"中序遍历的非递归实现2(利用栈):"< InOrderTraverse2(T,visitT); cout<<"层序遍历(利用队列):"< LevelOrderTraverse(T,visitT); cout<<"树的结点总数为:"< cout<<"树的叶子结点总数为:"< cout<<"树的深度为:"< } 运行结果: 先序输入:ABG CDE H F ( “”代表空格) 2.选做内容 任务4:修改算法6.4(结点及二叉树类型分别用BiThrNode,BiThrTree,创建 根结点的语句也要进行修改),然后对所创建的二叉树进行中序线索化; 任务5:对任务4得到的中序线索化树进行中序遍历。 源代码: head.h: #include #include #include #include #include #include #include #include #include #include //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 //OVERFLOW 在math.h 中已定义为3 typedef int Status; typedef int Boolean; // 布尔类型 head2.h: typedef char TElemType; typedef enum{Link,Thread}PointerTag; /* Link(0):指针,Thread(1):线索*/ typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; /* 左右孩子指针*/ PointerTag LTag,RTag; /* 左右标志*/ }BiThrNode,*BiThrTree; main.cpp: #include"head.h" #include"head2.h" Status CreateBiThrTree(BiThrTree &T) { /* 按先序输入二叉线索树中结点的值,构造二叉线索树T */ /* 空格表示空结点*/ TElemType h; scanf("%c",&h); if(h==' ') T=NULL; else { T=(BiThrTree)malloc(sizeof(BiThrNode)); if(!T) exit(OVERFLOW); T->data=h; /* 生成根结点(先序) */ CreateBiThrTree(T->lchild); /* 递归构造左子树*/ if(T->lchild) /* 有左孩子*/ T->LTag=Link; CreateBiThrTree(T->rchild); /* 递归构造右子树*/ if(T->rchild) /* 有右孩子*/ T->RTag=Link; } return OK; } BiThrTree pre; void InThreading(BiThrTree p) { /* 中序遍历进行中序线索化。算法6.7 */ if(p) { InThreading(p->lchild); /* 递归左子树线索化*/ if(!p->lchild) /* 没有左孩子*/ { p->LTag=Thread; /* 前驱线索*/ p->lchild=pre; /* 左孩子指针指向前驱*/ } if(!pre->rchild) /* 前驱没有右孩子*/ { pre->RTag=Thread; /* 后继线索*/ pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */ } pre=p; /* 保持pre指向p的前驱*/ InThreading(p->rchild); /* 递归右子树线索化*/ } } Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) { /* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点。算法6.6 */ Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); if(!Thrt) exit(OVERFLOW); Thrt->LTag=Link; /* 建头结点*/ Thrt->RTag=Thread; Thrt->rchild=Thrt; /* 右指针回指*/ if(!T) /* 若二叉树空,则左指针回指*/ Thrt->lchild=Thrt; else { Thrt->lchild=T; pre=Thrt; InThreading(T); /* 中序遍历进行中序线索化*/ pre->rchild=Thrt; pre->RTag=Thread; /* 最后一个结点线索化*/ Thrt->rchild=pre; } return OK; } Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType)) { /* 中序遍历二叉线索树T(头结点)的非递归算法。算法6.5 */ BiThrTree p; p=T->lchild; /* p指向根结点*/ while(p!=T) { /* 空树或遍历结束时,p==T */ while(p->LTag==Link) p=p->lchild; if(!Visit(p->data)) /* 访问其左子树为空的结点*/ return ERROR; while(p->RTag==Thread&&p->rchild!=T) { p=p->rchild; Visit(p->data); /* 访问后继结点*/ } p=p->rchild; } return OK; } Status visitT(TElemType c) { printf("%c ",c); return OK; } void main() { BiThrTree H,T; cout<<"请按先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树):"< CreateBiThrTree(T); /* 按先序产生二叉树*/ InOrderThreading(H,T); /* 中序遍历,并中序线索化二叉树*/ cout<<"中序遍历(输出)二叉线索树:"< InOrderTraverse_Thr(H,visitT); /* 中序遍历(输出)二叉线索树*/ cout< } 运行结果:(树的形状和任务1一致) 【小结或讨论】 通过本次实验,掌握了二叉树的二叉链表存储表示以及二叉树的遍历算法,并且能够运用遍历算法求解有关问题。学会了用先序次序输入二叉树中结点的值来创建二叉树的方法,还可以对二叉树进行中序线索化,并中序遍历二叉线索树,对二叉树的存储与遍历输出有了深刻的理解。 每一次编写程序都会遇到各种问题,有时候错误是比较明显的,编译器可以帮助指正,比如因为输入错误等,但有时候就没有那么幸运了,编译通过,执行程序的时候出现错误,这个时候就要进行调试,看看程序执行到哪里崩溃了,然后再仔细推敲一下。在本次实验中就遇到了这种情况,就因为在CreateBiThrTree(BiThrTree &T)函数中,形参忘记用引用类型了,导致树并没有被创建,或者说在执行CreateBiThrTree函数时创建了一棵树,但该函数运行结束后,这课树也就不存在了。 最后,要记住的一点就是,在程序中用到指针的地方一定要多加小心。 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法,并做了相应的性能分析和比较,课程内容丰富,理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: 1)理论艰深,方法灵活,给学习带来困难; 2)内容丰富,涉及的知识较多,学习有一定的难度; 3)侧重于知识的实际应用,要求学生有较好的思维以及较强的分析和解决问题的能力,因而加大了学习的难度; 根据《数据结构》课程本身的特性,通过实验实践内容的训练,突出构造性思维训练的特征,目的是提高学生分析问题,组织数据及设计大型软件的能力。 课程上机实验的目的,不仅仅是验证教材和讲课的内容,检查自己所编的程序是否正确,课程安排的上机实验的目的可以概括为如下几个方面: (1)加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实验题中的问题比平时的习题复杂得多,也更接近实际。实验着眼于原理与应用的结合点,使学生学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的动手能力;另一方面,能使书上的知识变" 活" ,起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时,觉得无从下手。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出 现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法,而实验题是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧,多人合作,以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点,使学生学会如何把书本上和课堂上学到的知识用于解决实际问题,从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境,学习上机调试程序一个程序从编辑,编译,连接到运行,都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件,软件条件,只有学会使用这些环境,才能进行 程序开发工作。通过上机实验,熟练地掌握程序的开发环境,为以后真正编写计算机程序解决实际问题打下基础。同时,在今后遇到其它开发环境时就会触类旁通,很快掌握新系统的使用。 完成程序的编写,决不意味着万事大吉。你认为万无一失的程序,实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误,也能够顺利运行,但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误,只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作,尽快掌握程序调试方法是非常重要的。分析问题,选择算法,编好程序,只能说完成一半工作,另一半工作就是调试程序,运行程序并得到正确结果。 二、实验要求 常用的软件开发方法,是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高,但为了培养一个软件工作者所应具备的科学工作的方法和作风,也应遵循以下五个步骤来完成实验题目: 1) 问题分析和任务定义 在进行设计之前,首先应该充分地分析和理解问题,明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。例如:输入数据的类型、值的范围以及输入的 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时) 实验三二叉树的遍历 一、实验目的 1、熟悉二叉树的结点类型和二叉树的基本操作。 2、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解,逐步培养解决实际问题的编程能力。 二、实验环境 运行C或VC++的微机。 三、实验内容 1、依次输入元素值,以链表方式建立二叉树,并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题,我的设计思路是先做好各个分部函数,然后在主函数中进行顺序排列,以此完成实验要求 2.二叉树采用动态数组 3.二叉树运用9个函数,主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数,关键在于访问节点 五、程序代码 #include int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败!!TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数,构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数,构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数,销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数,销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); } 线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) { 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 实验六:二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构,本单元的实验达到熟悉二叉树的存储结构的特性,以及如何应用树结构解决具体问题。 二、问题描述 首先,掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次,以二叉树表示算术表达式的基础上,设计一个十进制的四则运算的计算器。 如算术表达式:a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树,分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树; 2、设计求叶子结点个数算法和树的深度算法; 3、根据表达式建立相应的二叉树,生成表达式树的模块; 4、根据表达式树,求出表达式值,生成求值模块; 5、程序运行效果,测试数据分析算法。 六、测试数据 1、输入数据:*(+)3 正确结果: 2、输入数据:(1+2)*3+(5+6*7); 正确输出:56 七、表达式求值 由于表达式求值算法较为复杂,所以单独列出来加以分析: 1、主要思路:由于操作数是任意的实数,所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来,并以字符串的形式保存;然后再将其转换为后缀表达式的顺序,后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式: a+b-c 转换成后缀表达式为: ab+c- 然后分别按从左到右放入栈中,如果碰到操作符就从栈中弹出两个操作数进行运算,最后再将运算结果放入栈中,依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中,然后碰到操作符“+”,则从栈中弹出a 和b 进行a+b 的运算,并将其结果d(假设为d)放入栈中,然后再将c 放入栈中,最后是操作符“-”,所以再弹出d和c 进行d-c 运算,并将其结果再次放入栈中,此时表达式结束,则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键,要同时考虑操作符的优先级以及对有括号的情况下的处理,相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来,并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式,即调整各项字符串的顺序,并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号,保存在队列中,以本实验中的数据为例,分解完成后队列中的保存顺序如下图所示: #include return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码:\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); } 数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 6.0上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表,由用户输入各结点data域之值,//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师 一、实验内容 1) 采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序 以及按层次遍历的操作,求所有叶子及结点总数的操作。 2) 输出树的深度,最大元,最小元。 二、需求分析 遍历二叉树首先有三种方法,即先序遍历,中序遍历和后序遍历。 递归方法比较简单,首先获得结点指针如果指针不为空,且有左子,从左子递归到下一层,如果没有左子,从右子递归到下一层,如果指针为空,则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法: 首先介绍先序遍历: 先序遍历的顺序是根左右,也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下:如果结点的指针不为空,结点指针入栈,输出相应结点的数据,同时指针指向其左子,如果结点的指针为空,表示左子树访问结束,栈顶结点指针出栈,指针指向其右子,对其右子树进行访问,如此循环,直至结点指针和栈均为空时,遍历结束。 再次介绍中序遍历: 中序遍历的顺序是左根右,中序遍历和先序遍历思想差不多,只是打印顺序稍有变化。具体实现算法如下:如果结点指针不为空,结点入栈,指针指向其左子,如果指针为空,表示左子树访问完成,则栈顶结点指针出栈,并输出相应结点的数据,同时指针指向其右子,对其右子树进行访问。如此循环直至结点指针和栈均为空,遍历结束。 最后介绍后序遍历: 后序遍历的顺序是左右根,后序遍历是比较难的一种,首先需要建立两个栈,一个用来存放结点的指针,另一个存放标志位,也是首先访问根结点,如果结点的指针不为空,根结点入栈,与之对应的标志位也随之入标志位栈,并赋值0,表示该结点的右子还没有访问,指针指向该结点的左子,如果结点指针为空,表示左子访问完成,父结点出栈,与之对应的标志位也随之出栈,如果相应的标志位值为0,表示右子树还没有访问,指针指向其右子,父结点再次入栈,与之对应的标志位也入栈,但要给标志位赋值为1,表示右子访问过。如果相应的标志位值为1,表示右子树已经访问完成,此时要输出相应结点的数据,同时将结点指针赋值为空,如此循环直至结点指针和栈均为空,遍历结束。 三、详细设计 源代码: 顺序表的基本操作 #include int j=0; while(L.data[j]!=x) j++; if(j==https://www.sodocs.net/doc/074789352.html,st) { cout<<"所查找值不存在!"< 2009级数据结构实验报告 实验名称:约瑟夫问题 学生姓名:李凯 班级:21班 班内序号:06 学号:09210609 日期:2010年11月5日 1.实验要求 1)功能描述:有n个人围城一个圆圈,给任意一个正整数m,从第一个人开始依次报数,数到m时则第m个人出列,重复进行,直到所有人均出列为止。请输出n个人的出列顺序。 2)输入描述:从源文件中读取。 输出描述:依次从显示屏上输出出列顺序。 2. 程序分析 1)存储结构的选择 单循环链表 2)链表的ADT定义 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系:R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作: ListInit(&L);//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表,若是,则返回1,否则返回0. ListLength(L); //求单链表L的长度 GetElem(L,i);//返回链表L中第i个数据元素的值; ListSort(LinkList [内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template ******************************* 实验题目:二叉树的操作 实验者信息:班级13007102,姓名庞文正,学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构,试编写按层次遍历二叉树的算法。(所谓层次遍历,是指从二叉树的根结点开始从上到下逐层遍历二叉树,在同一层次中从左到右依次访问各个节点。)调试程序并对相应的输出作出分析;修改输入数据,预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识,实现理论与实践相结合。总结尽量简明扼要,并与本次实验密切相关,最好能加上自己的解释。 本算法要采用一个循环队列que,先将二叉树根结点入队列,然后退队列,输出该结点;若它有左子树,便将左子树根结点入队列;若它有右子树,便将右子树根结点入队列,直到队列空为止。因为队列的特点是先进先出,从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述,程序模块、功能及调用关系 #include 学生实验报告 学院:软通学院 课程名称:数据结构与算法 专业班级:软件142 班 姓名:邹洁蒙 学号: 0143990 学生实验报告 (二) 一、实验综述 1、实验目的及要求 目的:1)掌握树与二叉树的基本概念; 2)掌握二叉树的顺序存储,二叉链表的先序遍历中序遍历和后序遍历算法; 3)掌握树的双亲表示法。 要求:1)编程:二叉树的顺序存储实现; 2)编程:二叉链表的先序遍历中序遍历和后序遍历实现; 3)编程:树的双亲表示法实现。 2、实验仪器、设备或软件 设备:PC 软件:VC6 二、实验过程(编程,调试,运行;请写上源码,要求要有注释) 1.编程:二叉树的顺序存储实现 代码: BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图: 2.编程:二叉链表的先序遍历中序遍历和后序遍历实现代码: void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图: #include 算法与数据结构》课程实验报告 一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 (1)数据方面:该二叉树数据元素采用字符char 型,并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 (2)功能方面:能够实现二叉树的一些基本操作,主要包括: 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 (1)设计的主要思路 二叉树是的结点是一个有限集合,该集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求,以及课上老师对于二叉树存储结构、基本应用的讲解,同时课后研究书中涉及二叉树代码完成二叉树模板类,并将所需实现各个功能代码编写完成,在建立菜单对功能进行调试。 (2)数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间,故在此选用链表存储,提高存储空间的利用率。根据二叉树的定义,二叉 1、直接插入排序 2、希尔排序 3、2-路归并排序 4、折半插入排序 5、冒泡排序 6、快速排序 7、堆排序 /*---------------------------------------- * 07_排序.cpp -- 排序的相关操作 * 对排序的每个基本操作都用单独的函数来实现 * 水上飘2011年写 ----------------------------------------*/ // ds07.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "stdio.h" #include int i, j; for (i = dk + 1; i <= L.length; i++) { if (L.arr[i].key 2011~2012第一学期数据结构实验报告 班级:信管一班 学号:201051018 姓名:史孟晨 实验报告题目及要求 一、实验题目 设某班级有M(6)名学生,本学期共开设N(3)门课程,要求实现并修改如下程序(算法)。 1. 输入学生的学号、姓名和 N 门课程的成绩(输入提示和输出显示使用汉字系统), 输出实验结果。(15分) 2. 计算每个学生本学期 N 门课程的总分,输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次,总分相同者同名次。 二、实验要求 1.修改算法。将奇偶排序算法升序改为降序。(15分) 2.用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法;。(45分)) 3.编译、链接以上算法,按要求写出实验报告(25)。 4. 修改后算法的所有语句必须加下划线,没做修改语句保持按原样不动。 5.用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义,每种排序算法数据要求均不重复。 (1) 实验题目:《N门课程学生成绩名次排序算法实现》; (2) 实验目的:掌握各种排序算法的基本思想、实验方法和验证算法的准确性; (3) 实验要求:对算法进行上机编译、链接、运行; (4) 实验环境(Windows XP-sp3,Visual c++); (5) 实验算法(给出四种排序算法修改后的全部清单); (6) 实验结果(四种排序算法模拟运行后的实验结果); (7) 实验体会(文字说明本实验成功或不足之处)。 三、实验源程序(算法) Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i数据结构课程实验指导书
数据结构实验报告格式
数据结构二叉树实验报告
数据结构实验报告代码
数据结构实验报告
数据结构实验二叉树
数据结构实验一的源代码
数据结构实验报告全集
数据结构实验报告-二叉树的实现与遍历
数据结构实验程序
数据结构实验报告模板
数据结构实验-二叉树的操作
数据结构实验报告之树与二叉树
数据结构上机实验线性表单链表源代码
数据结构实验报告—二叉树
数据结构实验(七种排序算法的实现)题目和源程序
数据结构实验报告及心得体会