數(shù)據(jù)結(jié)構(gòu)實驗報告

1、數(shù)據(jù)結(jié)構(gòu)實驗報告一 題目要求1） 編程實現(xiàn)二叉排序樹，包括生成、插入，刪除；2） 對二叉排序樹進行先根、中根、和后根非遞歸遍歷；3） 每次對樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數(shù)組去存儲一個班(50人以上)的成員信息(至少包括學號、姓名、成績3項),對比查找效率，并說明在什么情況下二叉排序樹效率高,為什么?二 解決方案對于前三個題目要求，我們用一個程序?qū)崿F(xiàn)代碼如下#include<windows.h>#include <stdio.h>#include <malloc.h>#include "St

2、ack.h" /棧的頭文件，沒有用上typedef int ElemType; /數(shù)據(jù)類型typedef int Status; /返回值類型/定義二叉樹結(jié)構(gòu)typedef struct BiTNode ElemType data; /數(shù)據(jù)域 struct BiTNode *lChild, *rChild;/左右子樹域BiTNode, *BiTree;int InsertBST(BiTree &T,int key)/插入二叉樹函數(shù)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)/創(chuàng)建二叉樹函數(shù) 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指向被刪除結(jié)點的前驅(qū)if(q!=T)q->rChild=s->lChild; elseq->lChild=s->lChild;free(s);return

5、1; /刪除函數(shù)，在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()/主函數(shù)printf(" -二叉排序樹的實現(xiàn)-");printf("n");int layer;int i;int num;printf("輸入節(jié)點個數(shù):"

10、);scanf("%d",&num);printf("依次輸入這些整數(shù)（要不相等）");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("二叉樹創(chuàng)建成功!"); 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:插入節(jié)點 2:刪除節(jié)點 3:打印二叉樹 4:非遞歸遍歷二叉樹 5:退出");scanf("%d",&j);switch(j)case 1:printf("輸入要插入的節(jié)點:");scanf("%d",&

12、;T);InsertBST(bst,T);printf("插入成功!");printf("樹狀圖為:n");printtree(bst,layer);break;case 2:printf("輸入要刪除的節(jié)點");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("程序執(zhí)行完畢!");return 0;goto l

14、oop;return 0;對于第四小問，要儲存學生的三個信息，需要把上面程序修改一下，二叉樹結(jié)構(gòu)變?yōu)閠ypedef int ElemType; /數(shù)據(jù)類型typedef string SlemType; typedef int Status; /返回值類型/定義二叉樹結(jié)構(gòu)typedef struct BiTNode SlemTypename; ElemTypescore;ElemTypeno; /數(shù)據(jù)域 struct BiTNode *lChild, *rChild;/左右子樹域BiTNode, *BiTree;參數(shù)不是key,而是另外三個 int InsertBST(BiTree &

15、T,int no,int score,string name)/插入二叉樹函數(shù)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;其他含參函數(shù)也類似即可完成50個信息存儲用數(shù)組存儲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<<" 歡迎來到學生管理系統(tǒng)"<<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<<"該學號信息已經(jīng)存在，添加失敗"<<endl; break; cout<<"重新輸入添加的學號"<<endl; cin>>q; cout<<"輸入姓名"<<endl; cin>>w; cout<<"輸入科目一的成績"<<endl; cin>>e; cout<<&q