数据结构实验报告

1、数据结构实验报告一 题目要求1） 编程实现二叉排序树，包括生成、插入，删除；2） 对二叉排序树进行先根、中根、和后根非递归遍历；3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?二 解决方案对于前三个题目要求，我们用一个程序实现代码如下#include<windows.h>#include <stdio.h>#include <malloc.h>#include "St

2、ack.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

3、->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,ai);i+;return bst;int Delete(BiTree &T) BiTree q,s;if(!(T)

4、->rChild) /右子树为空 重接它的左子树q=T;T=(T)->lChild;free(q);elseif(!(T)->lChild) /若左子树空 则重新接它的右子树 q=T;T=(T)->rChild;elseq=T;s=(T)->lChild;while(s->rChild) q=s; s=s->rChild;(T)->data=s->data; /s指向被删除结点的前驱if(q!=T)q->rChild=s->lChild; elseq->lChild=s->lChild;free(s);return

5、1; /删除函数，在T中 删除key元素int DeleteBST(BiTree &T,int key)if(!T) return 0;elseif(key=(T)->data) return Delete(T);elseif(key<(T)->data) return DeleteBST(T->lChild,key);elsereturn DeleteBST(T->rChild,key);int PosttreeDepth(BiTree T)/求深度int hr,hl,max;if(!T=NULL)hl=PosttreeDepth(T->lChil

6、d);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;elsereturn 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("%dn",T->data); printtree(T->lChild,nlayer+1);void Pre

7、OrderNoRec(BiTree root)/先序非递归遍历BiTree p=root;BiTree stack50;int num=0;while(NULL!=p|num>0)while(NULL!=p)printf("%d ",p->data);stacknum+=p;p=p->lChild;num-;p=stacknum;p=p->rChild;printf("n");void InOrderNoRec(BiTree root)/中序非递归遍历BiTree p=root;int num=0;BiTree stack50;w

8、hile(NULL!=p|num>0)while(NULL!=p)stacknum+=p;p=p->lChild;num-;p=stacknum;printf("%d ",p->data);p=p->rChild;printf("n");void PostOrderNoRec(BiTree root)/后序非递归遍历BiTree p=root;BiTree stack50;int num=0;BiTree have_visited=NULL;while(NULL!=p|num>0)while(NULL!=p)stacknum

9、+=p;p=p->lChild;p=stacknum-1;if(NULL=p->rChild|have_visited=p->rChild)printf("%d ",p->data);num-;have_visited=p;p=NULL;elsep=p->rChild;printf("n");int main()/主函数printf(" -二叉排序树的实现-");printf("n");int layer;int i;int num;printf("输入节点个数:"

10、);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("树

11、状图为: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",&

12、;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);print

13、tree(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 l

14、oop;return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为typedef int ElemType; /数据类型typedef string SlemType; typedef int Status; /返回值类型/定义二叉树结构typedef struct BiTNode SlemTypename; ElemTypescore;ElemTypeno; /数据域 struct BiTNode *lChild, *rChild;/左右子树域BiTNode, *BiTree;参数不是key,而是另外三个 int InsertBST(BiTree &

15、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);els

16、e return 0;其他含参函数也类似即可完成50个信息存储用数组存储50个信息，查看以往代码#include<iostream>#include<string>using namespace std;class studentprivate: 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

17、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(

18、)cout<<" 欢迎来到学生管理系统"<<endl;cout<<" 0.查询学号信息："<<endl; cout<<" 1.删除学号信息："<<endl; cout<<" 2.添加学号新信息"<<endl; cout<<" 3.按平均分降序显示所有学生信息"<<endl; cout<<" 4. 退出"<<endl; student

19、*ptr=new student21; ptr1.set(1,"小明",88,67);/已存入的学生信息 ptr2.set(2,"小李",68,82); ptr3.set(3,"小王",68,62); ptr4.set(4,"小陈",79,82); ptr5.set(5,"小张",63,82); ptr6.set(6,"小红",68,73); ptr7.set(7,"小木",62,77); ptr8.set(8,"小添",65,86);

20、 ptr9.set(9,"小天",68,82); ptr10.set(10,"张三",88,82); ptr11.set(11,"李四",98,82); ptr12.set(12,"王五",88,81); ptr13.set(13,"小月",58,82); ptr14.set(14,"小鑫",78,80); ptr15.set(15,"小良",68,92); ptr16.set(16,"小成",68,82); ptr17.set(17,

21、"小敏",98,92); ptr18.set(18,"小问",88,88); ptr19.set(19,"小文",48,82); ptr20.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:

22、cout<<"输入想查询的学号"<<endl; cin>>i; if(i=j) cout<<"该学号信息已被删除"<<endl; break; ptri.show(); break; case 1: cout<<"输入想删除的学号"<<endl; cin>>j; deletejptr; cout<<"删除成功"<<endl; break; case 2: cout<<"输入想

23、添加的学号信息"<<endl; cin>>k; if(k!=j) cout<<"该学号信息已经存在，添加失败"<<endl; break; cout<<"重新输入添加的学号"<<endl; cin>>q; cout<<"输入姓名"<<endl; cin>>w; cout<<"输入科目一的成绩"<<endl; cin>>e; cout<<&q