数据结构实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告总”。
数据结构实验报告
一． 题目要求
1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历；
3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二． 解决方案
对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include “Stack.h”//栈的头文件，没有用上
typedefintElemType;
//数据类型 typedefint Status;
//返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType
data;
structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉树函数
if(T==NULL){
T =(BiTree)malloc(sizeof(BiTNode));
T->data=key;
T->lChild=T->rChild=NULL;
return 1;} else if(keydata){ InsertBST(T->lChild,key);} else if(key>T->data){
InsertBST(T->rChild,key);} else
return 0;} BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL;inti=0;while(i
//数据域
InsertBST(bst,a[i]);
i++;} returnbst;} int Delete(BiTree&T)
{
BiTreeq,s;
} if(!(T)->rChild){ //右子树为空重接它的左子树
q=T;T=(T)->lChild;free(q);}else{
if(!(T)->lChild){ //若左子树空则重新接它的右子树
q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){
q=s;s=s->rChild;}
(T)->data=s->data;//s指向被删除结点的前驱
if(q!=T)
q->rChild=s->lChild;
else
q->lChild=s->lChild;
free(s);} } return 1;
//删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{
if(key==(T)->data)return Delete(T);
else{
if(keydata)
returnDeleteBST(T->lChild,key);
else
returnDeleteBST(T->rChild,key);
} } } intPosttreeDepth(BiTree T){//求深度
inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else
return 0;
} void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i
“);} printf(”%dn“,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){
while(NULL!=p)
{
printf(”%d “,p->data);
stack[num++]=p;
p=p->lChild;
}
num--;
p=stack[num];
p=p->rChild;} printf(”n“);} void InOrderNoRec(BiTree root)//中序非递归遍历 { BiTree p=root;
} intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){
stack[num++]=p;
p=p->lChild;} num--;p=stack[num];printf(”%d “,p->data);p=p->rChild;} printf(”n“);void PostOrderNoRec(BiTree root)//后序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL;
while(NULL!=p||num>0){
while(NULL!=p)
{
stack[num++]=p;
p=p->lChild;
}
p=stack[num-1];
if(NULL==p->rChild||have_visited==p->rChild)
{
printf(”%d “,p->data);
num--;
have_visited=p;
p=NULL;
}
else
{
p=p->rChild;
} } printf(”n“);}
int main(){//主函数
printf(”
---------------------二叉排序树的实现-------------------“);printf(”n“);int layer;inti;intnum;printf(”输入节点个数:“);scanf(”%d“,&num);printf(”依次输入这些整数（要不相等）“);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i
scanf(”%d“,arr+i);} BiTreebst=CreateBST(arr,num);printf(”n“);printf(”二叉树创建成功!“);printf(”n“);layer=PosttreeDepth(bst);printf(”树状图为:n“);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(”n“);printf(”
***********************按提示输入操作符************************:“);printf(”n“);printf(”
1:插入节点
2:删除节点
3:打印二叉树
4:非递归遍历二叉树
5:退出“);scanf(”%d“,&j);
switch(j){
case 1:
printf(”输入要插入的节点:“);
scanf(”%d“,&T);
InsertBST(bst,T);
printf(”插入成功!“);printf(”树状图为:n“);
printtree(bst,layer);
break;
case 2:
}
printf(”输入要删除的节点“);scanf(”%d“,&K);DeleteBST(bst,K);printf(”删除成功!“);printf(”树状图为:n“);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4:
printf(”非递归遍历二叉树“);printf(”先序遍历:n“);PreOrderNoRec(bst);printf(”中序遍历:n“);InOrderNoRec(bst);
printf(”后序遍历:n“);
PostOrderNoRec(bst);
printf(”树状图为:n“);
printtree(bst,layer);
break;case 5:
printf(”程序执行完毕!");
return 0;} goto loop;} return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为 typedefintElemType;
//数据类型 typedefstring SlemType;
typedefint Status;
//返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no;
//数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;参数不是key,而是另外三个
intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数
if(T==NULL){
T =(BiTree)malloc(sizeof(BiTNode));
T->no=no;T->name=name;T->score=score;
T->lChild=T->rChild=NULL;
return 1;} else if(nono){ InsertBST(T->lChild,no,score,name);} else if(key>T->data){
InsertBST(T->rChild,no,score,name);} else
return 0;} 其他含参函数也类似 即可完成50个信息存储
用数组存储50个信息，查看以往代码
#include #include using namespace std;cla student{ private: intnum;string name;int ob1;int ob2;intara;public: void set(inta,stringb,intc,int d);void show();int average();};void student ::set(inta,stringb,intc,int d){ num=a;name=b;ob1=c;ob2=d;ara=(c+d)/2;} void student::show(){ cout
int main(){ cout>numlock;switch(numlock){ case 0: cout>i;if(i==j){ cout>j;delete[j]ptr;cout>k;if(k!=j){
cout
break;} cout>q;cout>w;cout>e;cout>r;ptr[k].set(q,w,e,r);break;case 3: for(m=1;m
for(int n=m+1;n
if(ptr[m].average()
student a;
a=ptr[m];
ptr[m]=ptr[n];
ptr[n]=a;
}}
ptr[m].show();} break;case 4: cout
二叉排序树储存数据界面（储存学生信息略）
创建二叉树：
插入节点：
删除节点：
非递归遍历：
退出：
数组储存学生信息界面
分析查找效率：
因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。
四． 总结与改进
这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。
一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。
递归遍历的实现比非递归的遍历真的简单很多。
开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。
刀豆文库小编为你整合推荐8篇数据结构实验报告，也许这些就是您需要的文章，但愿刀豆文库能带给您一些学习、工作上的帮助。......
注意：实验结束后提交一份实验报告电子文档电子文档命名为“学号+姓名”，如：E01214058宋思怡《数据结构》实验报告（一）学号：姓名：专业年级：实验名称：线性表实验日期：2014年4月14日实验......
数据结构实验报告想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是本站小编给大家整理收集的数据结构实验报告，供大家阅读参考。数据结构实验报告1一、......
数据结构实验报告（精选16篇）由网友“coco2008”投稿提供，下面是小编为大家推荐的数据结构实验报告，欢迎大家分享。篇1：数据结构实验报告 一、实验目的及要求1)掌握栈和队列这两种......
实验报告4 排序一、实验目的1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。3、了解各种方法的......
