数据结构实验报告
数据结构实验报告
一． 题目要求
1） 编程实现二叉排序树，包括生成、插入，删除；
2） 对二叉排序树进行先根、中根、和后根非递归遍历；
3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?
二． 解决方案
对于前三个题目要求，我们用一个程序实现代码如下
#include<windows.h>
#include <stdio.h>
#include <malloc.h>
#include "Stack.h" //栈的头文件，没有用上
typedef int ElemType; //数据类型
typedef int Status; //返回值类型
//定义二叉树结构
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lChild, *rChild;//左右子树域
}BiTNode, *BiTree;
int InsertBST(BiTree &T,int key){//插入二叉树函数
if(T==NULL)
{
T = (BiTree)malloc(sizeof(BiTNode));
T->data=key;
T->lChild=T->rChild=NULL;
return 1;
}
else if(key<T->data){
InsertBST(T->lChild,key);
}
else if(key>T->data){
InsertBST(T->rChild,key);
}
else
return 0;
}
BiTree CreateBST(int a[],int n){//创建二叉树函数
BiTree bst=NULL;
int i=0;
while(i<n){
InsertBST(bst,a[i]);
i++;
}
return bst;
}
int Delete(BiTree &T)
{
BiTree q,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元素
int DeleteBST(BiTree &T,int key){
if(!T) return 0;
else{
if(key==(T)->data) return Delete(T);
else{
if(key<(T)->data)
return DeleteBST(T->lChild,key);
else
return DeleteBST(T->rChild,key);
}
}
}
int PosttreeDepth(BiTree T){//求深度
int hr,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(BiTree T,int nlayer){//打印二叉树
if(T==NULL) return ;
printtree(T->rChild,nlayer+1);
for(int i=0;i<nlayer;i++){
printf(" ");
}
printf("%d\n",T->data);
printtree(T->lChild,nlayer+1);
}
void PreOrderNoRec(BiTree root)//先序非递归遍历
{
BiTree p=root;
BiTree stack[50];
int num=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;
int num=0;
BiTree stack[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;
BiTree stack[50];
int num=0;
BiTree have_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;
int i;
int num;
printf("输入节点个数:");
scanf("%d",&num);
printf("依次输入这些整数（要不相等）");
int *arr=(int*)malloc(num*sizeof(int));
for(i=0;i<num;i++){
scanf("%d",arr+i);
}
BiTree bst=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;
}
对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为
typedef int ElemType; //数据类型
typedef string SlemType;
typedef int Status; //返回值类型
//定义二叉树结构
typedef struct BiTNode{
SlemType name;
ElemType score;
ElemType no; //数据域
struct BiTNode *lChild, *rChild;//左右子树域
}BiTNode, *BiTree;
参数不是key,而是另外三个
int InsertBST(BiTree &T,int no,int score,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(no<T->no){
InsertBST(T->lChild,no,score,name);
}
else if(key>T->data){
InsertBST(T->rChild, no,score,name);
}
else
return 0;
}
其他含参函数也类似
即可完成50个信息存储
用数组存储50个信息，查看以往代码
#include<iostream>
#include<string>
using namespace std;
class student{
private:
int num;
string name;
int ob1;
int ob2;
int ara;
public:
void set(int a,string b,int c,int d);
void show();
int average();
};
void student ::set(int a,string b,int c,int d){
num=a;
name=b;
ob1=c;
ob2=d;
ara=(c+d)/2;
}
void student::show(){
cout<<"学号："<<num<<" 姓名："<<name<<" 科目一："<<ob1<<" 科目二："<<ob2<<" 平均成绩："<<ara<<endl;}
int student::average(){
return ara;}
int main(){
cout<<" 欢迎来到学生管理系统"<<endl;
cout<<" 0.查询学号信息："<<endl;
cout<<" 1.删除学号信息："<<endl;
cout<<" 2.添加学号新信息"<<endl;
cout<<" 3.按平均分降序显示所有学生信息"<<endl;
cout<<" 4. 退出"<<endl;
student *ptr=new student[21];
ptr[1].set(1,"小明",88,67);//已存入的学生信息
ptr[2].set(2,"小李",68,82);
ptr[3].set(3,"小王",68,62);
ptr[4].set(4,"小陈",79,82);
ptr[5].set(5,"小张",63,82);
ptr[6].set(6,"小红",68,73);
ptr[7].set(7,"小木",62,77);
ptr[8].set(8,"小添",65,86);
ptr[9].set(9,"小天",68,82);
ptr[10].set(10,"张三",88,82);
ptr[11].set(11,"李四",98,82);
ptr[12].set(12,"王五",88,81);
ptr[13].set(13,"小月",58,82);
ptr[14].set(14,"小鑫",78,80);
ptr[15].set(15,"小良",68,92);
ptr[16].set(16,"小成",68,82);
ptr[17].set(17,"小敏",98,92);
ptr[18].set(18,"小问",88,88);
ptr[19].set(19,"小文",48,82);
ptr[20].set(20,"小瑞",98,62);//已存入的学生信息
int numlock;
int j=0;
int i,k,m;
int q,e,r;
string w;
while(1){
cout<<" 按0,1,2,3,4进行操作"<<endl;
cin>>numlock;
switch(numlock){
case 0:
cout<<"输入想查询的学号"<<endl;
cin>>i;
if(i==j){
cout<<"该学号信息已被删除"<<endl;
break;}
ptr[i].show();
break;
case 1:
cout<<"输入想删除的学号"<<endl;
cin>>j;
delete[j]ptr;
cout<<"删除成功"<<endl;
break;
case 2:
cout<<"输入想添加的学号信息"<<endl;
cin>>k;
if(k!=j){
cout<<"该学号信息已经存在，添加失败"<<endl;
break;
}
cout<<"重新输入添加的学号"<<endl;
cin>>q;
cout<<"输入姓名"<<endl;
cin>>w;
cout<<"输入科目一的成绩"<<endl;
cin>>e;
cout<<"输入科目二的成绩"<<endl;
cin>>r;
ptr[k].set(q,w,e,r);
break;
case 3:
for( m=1;m<20;m++){
for(int n=m+1;n<20;n++){
if(ptr[m].average()<ptr[n].average()){
student a;
a=ptr[m];
ptr[m]=ptr[n];
ptr[n]=a;
}}
ptr[m].show();
}
break;
case 4:
cout<<"谢谢使用"<<endl;
return 0;
default:
cout<<"number out of 0 to 4"<<endl;
break;
}}
return 0;
}
三． 测试结果
二叉排序树储存数据界面（储存学生信息略）
创建二叉树：
插入节点：
删除节点：
非递归遍历：
退出：
数组储存学生信息界面
分析查找效率：
因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。
四． 总结与改进
这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。
一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。
递归遍历的实现比非递归的遍历真的简单很多。
开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。
-
数据结构实验报告
实验报告实验课程：数据结构实验项目：实验专业：计算机科学与技术姓名：**学号：***指导教师：**实验时间：20**-12-7重庆…
-
数据结构实验报告(C语言)(强力推荐)
数据结构实验实验内容和目的掌握几种基本的数据结构集合线性结构树形结构等在求解实际问题中的应用以及培养书写规范文档的技巧学习基本的查…
-
数据结构实验———图实验报告
数据结构实验报告目的要求掌握图的存储思想及其存储实现掌握图的深度广度优先遍历算法思想及其程序实现掌握图的常见应用算法的思想及其程序…
-
数据结构实验报告格式
数据结构实验报告格式实验11顺序表的基本操作一实验目的1掌握使用VC上机调试线性表的基本方法2掌握线性表的基本操作插入删除查找等运…
-
数据结构实验报告5
计算机科学与工程系计算机科学与工程系2计算机科学与工程系附录可包括源程序清单或其它说明includeltiostreamgtinc…
-
数据结构综合实验心得体会
心得体会：做了一个星期的程序设计终于做完了，在这次程序设计课中，真是让我获益匪浅。对大一学习的C语言和这学期开的数据结构，并没有掌…
-
数据结构基础__实验总结
数据结构基础实验总结本学期开设的《数据结构基础》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面…
-
华中科技大学·计算机13级·数据结构实验报告
课程设计报告课程名称专业班级CS1308学号姓名陈劲龙指导教师报告日期计算机科学与技术目录实验一基于顺序结构的线性表实现11问题描…
-
数据结构课程设计报告
CENTRALSOUTHUNIVERSITY数据结构课程设计报告题目学生姓名指导教师学院专业班级完成时间交通旅游图的最短路径问题摘…
-
数据结构课程设计 实验报告 心得体会 链表 C语言
数据结构课程设计设计题目:两个链表的交叉合并专业班级:08软件工程3班姓名：**学号：***设计时间：20XX/9/25指导教师：…