第一篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
浙江師范大學
實 驗 報 告
學 院： 數(shù)理與信息工程學院 專 業(yè)： 計算機科學與技術(shù) 姓 名： 楊富生 學 號： 201531910137 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 指導教師： 鐘發(fā)榮 實驗時間： 2016-06-15
2016年6月15日
實驗一
1.實驗要求
1.1 掌握數(shù)據(jù)結(jié)構(gòu)中線性表的基本概念。
1.2 熟練掌握線性表的基本操作：創(chuàng)建、插入、刪除、查找、輸出、求長度及合并并運算在順序存儲結(jié)構(gòu)上的實驗。
2.實驗內(nèi)容
2.1 編寫一個函數(shù)，從一個給定的順序表A中刪除元素值在x到y(tǒng)之間的所有元素，要求以較高效率來實現(xiàn)。
#include
A[i-k]=A[i];i++;} return(n-k);} void main(){ int i,j;int a[maxsize];printf(“輸入%d個數(shù):n”,maxsize);for(i=0;i scanf(“%d,”,&a[i]); j=del(a,maxsize,1,3); printf(“輸出刪除后剩下的數(shù):n”); for(i=0;i ”n,a[i]);} 2.2 試寫一個算法，在無頭結(jié)點的動態(tài)單鏈表上實現(xiàn)線性表插入操作INSERT(L,i,b)。 void Insert(Linklist &L,int i,elemtype x){ if(!L){ } L=(Linklist)malloc(sizeof(Lnode));(*L).data=x;(*L).next=NULL;} else { if(i==1){ s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=L;L=s;} else { p=L;j=1; while(p&&j {j++;p=p->next;} if(p||j>i-1) return error; s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=p->next;p->next=s;} } 2.3 生成兩個多項式PA和PB，求他們的和，輸出“和多項式”。typedef struct node {int exp;float coef;struct node *next;}polynode;polynode *polyadd(polynode *pa,polynode *pb){ polynode *p,*q,*pre,*r;float x;p=pa->next;q=pb->next;pre=pa;while((p!=NULL)&&(q!=NULL)) if(p->exp>q->exp) { r=q->next; q->next=p; pre->next=q; pre=q; q=r; } } else if(p->exp==q->exp){ x=p->coef+q->coef; if(x!=0) {p->coef=x; s=p; } else {pre->next=p->next; free(p); } p=pre->next; r=p; q=q->next; free(r);} else if(p->exp { pre=p; p=p->next; } if(q!=NULL) pre->next=q; free(pb);2.4 設(shè)計一個統(tǒng)計選票的算法，輸出每個候選人的得票結(jié)果。 typedef int elemtype typedef struct linknode { elemtype data;struct linknode *next;}nodetype;nodetype *create(){ elemtype d;nodetype h=NULL,*s,*t;int i=1;printf(“建立單鏈表:n”);while(1){ printf(“輸入第%d個結(jié)點數(shù)據(jù)域”,i); scanf(“%d”,&d); if(d==0)break; if(i==1) { h=(nodetype *)malloc(sizeof(nodetype)); h->data=d;h->next=NULL;t=h; } else { s=(nodetype *)malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s; } i++;} return h;} void sat(nodetype *h,int a[]){ nodetype *p=h;while(p!=NULL){ a[p->data]++; p=p->next;} } void main(){ int a[N+1],i;for(i=0;i a[i]=0;nodetype *head;head=create();sat(head,a);printf(“候選人:”);for(i=1;i<=N;i++)printf(“%3d”,i);printf(“n得票數(shù)n”);for(i=1;i<=N;i++) printf(“%3d”,a[i]);printf(“n”);} 3.實驗心得體會 線性表是最簡單的、最常用的一種數(shù)據(jù)結(jié)構(gòu)，是實現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。 實驗二 1.實驗要求 1.1 了解棧和隊列的特性，以便靈活運用。1.2 熟練掌握棧和有關(guān)隊列的各種操作和應(yīng)用。 2.實驗內(nèi)容 2.1 設(shè)一個算術(shù)表達式包括圓括號，方括號和花括號三種括號，編寫一個算法判斷其中的括號是否匹配。#include push(*str,L);else if(*str==')'||*str==']'||*str=='}') if(pop(*str,L)) {puts(“錯誤,請檢查!”); puts(“按回車鍵退出”); getchar();exit(-2); } str++;} if(L->next){puts(“錯誤,請檢查!”);puts(“按任意鍵退出”);getchar();exit(-2);} } void push(char c,list *L){list *p;p=(list *)malloc(sizeof(list));if(!p){ printf(“錯誤!”);exit(-2);} p->str=c;p->next=L->next;L->next=p;} #define check(s)if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);} int pop(char c,list *L){ list *p;if(L->next==NULL)return 1;switch(c){ case')':check('(')break;case']':check('[')break;case'}':check('{')break;} return 1; 實驗三 1.實驗要求 1.1 掌握二叉樹，二叉樹排序數(shù)的概念和存儲方法。1.2 掌握二叉樹的遍歷算法。 1.3 熟練掌握編寫實現(xiàn)樹的各種運算的算法。2.實驗內(nèi)容 2.1 編寫程序，求二叉樹的結(jié)點數(shù)和葉子數(shù)。#include bt=(struct node *)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat();} return bt;} int n=0,n1=0;void preorder(blink bt){ if(bt){ n++; if(bt->lchild==NULL&&bt->rchild==NULL) n1++; preorder(bt->lchild); preorder(bt->rchild);} } void main(){ } blink root;root=creat();preorder(root);printf(“此二叉數(shù)的接點數(shù)有:%dn”,n);printf(“此二叉數(shù)的葉子數(shù)有:%dn”,n1);2.2 編寫遞歸算法，求二叉樹中以元素值為X的結(jié)點為根的子數(shù)的深度。int get_deep(bitree T,int x){ if(T->data==x){ printf(“%dn”,get_deep(T));exit 1;} else { if(T->lchild)get_deep(T->lchild,x);if(T->rchild)get_deep(T->rchild,x);} int get_depth(bitree T){ if(!T)return 0;else { m=get_depth(T->lchild);n=get_depth(T->rchild);return(m>n?m:n)+1;} } 2.3 編寫程序，實現(xiàn)二叉樹的先序，中序，后序遍歷，并求其深度。#include inorder(bt->lchild);printf(“%c”,bt->data);inorder(bt->rchild);} } void postorder(blink bt){ if(bt){ postorder(bt->lchild);postorder(bt->rchild);printf(“%c”,bt->data);} } int max(int x,int y){ if(x>y)return x;else return y;} int depth(blink bt){ if(bt)return 1+max(depth(bt->lchild),depth(bt->rchild));else return 0;} void main(){ blink root;root=creat();printf(“n”);printf(“按先序排列:”);preorder(root);printf(“n”);printf(“按中序排列:”);inorder(root);printf(“n”);printf(“按后序排列:”);postorder(root);printf(“n”);printf(“此二叉數(shù)的深度是:”);printf(“depth=%dn”,depth(root));} 3.實驗心得體會 通過本章學習實驗，對樹有了初步的認識。樹就是一種非線性的數(shù)據(jù)結(jié)構(gòu)，描述了客觀世界中事物之間的層次關(guān)系。這種結(jié)構(gòu)有著廣泛的應(yīng)用，一切具有層次關(guān)系的問題都可以用樹來表示。 #include bt=(Treenode *)malloc(len); bt->data=n;bt->ltag=0;bt->rtag=0; bt->lchild=creat(); bt->rchild=creat();} else bt=null;return bt;} void preorder1(Treenode *t){ if(t!=null){ printf(“%4d”,t->data); preorder1(t->lchild); preorder1(t->rchild);} } void preorder2(Treenode *t){ if(t!=null){ preorder2(t->lchild); printf(“%4d”,t->data); preorder2(t->rchild);} } void preorder3(Treenode *t){ if(t!=null){ preorder3(t->lchild); preorder3(t->rchild); printf(“%4d”,t->data);} } void InThread(Treenode *T){ Treenode *p;p=T;if(p){ InThread(p->lchild);if(!p->lchild){ p->ltag=1;p->lchild=pre;} if(!pre->rchild){ pre->rtag=1;pre->rchild=p;} pre=p;InThread(p->rchild);} } Treenode *inorderthreading(Treenode *T){ Treenode *Thre;Thre=(Treenode *)malloc(sizeof(Treenode)Thre->lchild=T;Thre->rchild=Thre;pre=Thre;InThread(T);pre->rtag=1;pre->rchild=Thre;Thre->rchild=pre;return Thre;} void InThrTravel(Treenode *Thre){ Treenode *p;p=Thre->lchild;while(p!=Thre){ while(p->ltag==0)p=p->lchild;printf(“%4d”,p->data);while(p->rtag==1 && p->rchild!=Thre){ p=p->rchild;printf(“%4d”,p->data);} p=p->rchild;}printf(“n”);} void main(){ Treenode *tree;int i;printf(“建立二叉樹:n”);tree=creat();printf(“請選擇遍歷二叉樹的方法:nn1.先根序遍歷.n2.中根序遍歷.n3.后根序遍歷.n”);scanf(“%d”,&i);while(i>3 && i<1){ scanf(“%d”,&i);} switch(i){ case 1:preorder1(tree);break;case 2:preorder2(tree);break;case 3:preorder3(tree);break;} printf(“n中根序線索遍歷:n”);tree=inorderthreading(tree);InThrTravel(tree) 實驗四 #include tree[i].parent=0; tree[i].llink=0; tree[i].rlink=0;} } void inputweight(node tree[]){ int i;printf(“請輸入各結(jié)點的權(quán)值:n”);for(i=1;i<=n;i++){ printf(“第%d個結(jié)點的權(quán)值:”,i); scanf(“%d”,&tree[i].weight);} } void select(int pre,int *min1,int *min2){ int i;*min1=*min2 = 0;for(i=1;i select(i-1,&x1,&x2); tree[x1].parent=i; tree[x2].parent=i; tree[i].llink=x1; tree[i].rlink=x2; tree[i].weight=tree[x1].weight+tree[x2].weight;} void encode(node tree[],element table[]){ int i,s,f;codetype c;for(i=1;i<=n;i++){ table[i].c=tree[i].weight; c.start=n+1;s=i; while(f=tree[s].parent) { c.bits[--c.start]=(s==tree[f].llink)?'0':'1';s=f;} table[i].code=c;} void main(){ int i;element table[n+1];sethuftree(tree);encode(tree,table);printf(“n輸出Huffman編碼n”);for(i=1;i<=n;i++){ printf(“n %c :”,table[i].c);puts(table[i].code.bits);} } 實驗五 #include for(j=0;j if(i==j)g->edges[i][j]=0; else g->edges[i][j]=MAX; for(k=0;k printf(“Input i,j,w:(eg.0,1,5)n”); scanf(“%d,%d,%d”,&i,&j,&w); g->edges[i][j]=w; printf(“nThe graph is: nn”); printf(“t ”); for(k=0;k printf(“%3c”,g->vexs[k]); if(k==g->n-1)printf(“nn”); } for(i=0;i printf(“t%c ”,g->vexs[i]); for(j=0;j if(g->edges[i][j]==MAX)printf(“%3c”,MAX-923); else printf(“%3d”,g->edges[i][j]); printf(“n”); } void main(){ MGraph *g;g=(MGraph *)malloc(sizeof(MGraph));createmgraph(g);getchar();} 實驗六 1.實驗要求 1.1 熟悉圖的各種存儲方法。 1.2 掌握遍歷圖的遞歸和非遞歸的算法。1.3 理解圖的有關(guān)算法。 2.實驗內(nèi)容 2.1 寫出將一個無向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。void mattolist(int a[][],adjlist b[],int n) { for(i=0;i for(i=0;i for(j=n-1;j>=0;j--) if(a[i][j]!=0) {p=(arcnodetp *)malloc(sizeof(arcnodetp)); p->adjvex=j; p->nextare=b[i].firstare; b[i].firstarc=p; } } 2.2 以鄰接表作存儲結(jié)構(gòu)，給出拓撲排序算法的實現(xiàn)。typedef struct vexnode { VertexType vertex;int in;ArecNodeTp * fristarc;}AdjList[vnum];typedef struct graph { AdjList adjlist;int vexnum,arcnum;}GraphTp;Top_Sort(GraphTp g){ LstackTp *p;int m,i,v;initStack(S);for(i=0;i if(g.adjlist[i].in==0)/*if(w的入度==0)*/ push(S,&v);/*w入S棧*/ } } m=0;whlie(!EmptyStack(S)){ Pop(S,&v)//S出棧->v printf(“%d”,v);/*輸出v*/ m++;p=g.adjlist[i].fristarc;/*p=圖g中頂點v的第一個鄰接點*/ while(p!=NULL){//p存在 (g.adjlist[p->adjvex].in)--;/*p的入度--*/ if(g.adjlist[p->adjvex].in==0)/*if(p的入度==0)*/ Push(S,p->adjvex);/*p入S棧*/ p=p->nextarc;/*p=圖g中的頂點v的下一個鄰接點*/ } } if(m 實驗七 #include if(t->right==NULL) { p=(dnode *)malloc(sizeof(dnode)); p->data=c; p->left=NULL;p->right=NULL; t->right=p; } else sort(t->right,c);if(c if(t->left==NULL) { p=(dnode *)malloc(sizeof(dnode)); p->data=c;p->left=NULL;p->right=NULL;t->left=p; } else sort(t->left,c)dnode *creat(){ dnode *ht;int x;ht=(dnode *)malloc(sizeof(dnode));printf(“創(chuàng)建二叉排序樹(以0結(jié)束輸入):”);scanf(“%d”,&x);ht->data=x;n++;ht->left=NULL;ht->right=NULL;scanf(“%d”,&x);while(x>0){ sort(ht,x);n++; scanf(“%d”,&x);} return ht;} int find(dnode *b,int x,dnode *a[]){ dnode *stack[maxsize],*p;int top;a[1]=NULL; if(b!=NULL){ top=1;stack[top]=b;while(top>0){ p=stack[top];top--;if(p->left->data==x || p->right->data==x)a[1]=p;if(p->data==x){a[0]=p;return 1;} if(p->right!=NULL){ top++;stack[top]=p->right;} if(p->left!=NULL){ top++;stack[top]=p->left;} } } a[0]=p;} dnode *delet(dnode *t){ dnode *p,*q,*s,*f,*a[2];int flag=0,x;p=(dnode *)malloc(sizeof(dnode));f=(dnode *)malloc(sizeof(dnode));printf(“請輸入要刪除的結(jié)點:”);scanf(“%d”,&x);find(t,x,a);p=a[0];f=a[1];if(p==NULL){printf(“NO FIND!n”);exit(0);} if(p->left==NULL)s=p->right;else if(t->right=NULL)s=p->left;else{ q=p;s=p->left;while(s->right!=NULL) {q=s;s=s->right;} if(q==p)q->left=s->left; else q->right=s->left;p->data=s->data;free(s);flag=1;if(flag==0){ if(f==NULL)t=s;else if(f->left==p)f->left=s; else f->right=s;} return t;} void inorder(dnode *t){ if(t!=NULL){ inorder(t->left);printf(“%4d”,t->data);inorder(t->right);} } void main(){ dnode *h;h=creat();printf(“中序遍歷二叉排序樹:”);inorder(h);printf(“n”);h=delet(h); inorder(h);printf(“n”);} 實驗八 1.實驗要求 1.1 掌握順序查找、二分法查找、分塊查找和哈希表查找的算法。1.2 能運用線性表的查找方法解決實際問題。2.實驗內(nèi)容 2.1 編寫一個算法，利用二分查找算法在一個有序表中插入一個元素X，并保持表的有序性。 #include printf(“%3d”,*(data+insert));getch();} /*********************************************************/ int input(int *data){ int i,m;printf(“nInput the max num:”);scanf(“%d”,&m);printf(“input datan”);for(i=1;i<=m;i++) scanf(“%d”,data+i);return m;} /**********************************************************/ int search(int *data,int low,int high)/*遞歸查找插入位置*/ { int mid;if(low>high)return low;/*沒有找到插入數(shù)據(jù)，返回low*/ else{ mid=(low+high)/2; if(*(data+mid)==*data)retun mid;/*找到插入數(shù)據(jù)，返回mid*/ else if(*(data+mid)<*data) else if(*()data+mid)>*data)} search(data,low,high);} /**********************************************************/ void plug(int *data,int insert,int m){ int i;for(i=m;i>insert;i--) *(data+i+1)=*(data+i);*(data+insert)=*data } 2.2 根據(jù)給定的數(shù)據(jù)表，先建立索引表，然后進行分塊查找。 #include (p+k)->key=dat a[m*k]; (p+k)->addr=m*k; for(j=m*k;j if(data[j]>(p+k)->key) (p+k)->key=data[j];/*塊的最大關(guān)鍵字*/ } return p;} int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分塊查找*/ { int low=0,high=m-1,mid,i;int b=n/m;/*每塊有b個元素*/ while(low<=high){/*塊間折半查找*/ mid=(low+high)/2; if((list+mid)->key>=k) high=mid+1; else low=mid+1;} if(low for(i=(list+low)->addr;i<=(list+low)->adder+b-1&&rectab[i]!=k;i++); if(i<=(list+low)->addr+b-1) return i; else return-1;} return-1;} void main(){ int record[N]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};int key;index *list;printf(“please input key:n”);scanf(“%d”,&key);list=CreateList(record,N);printf(“data postion id %dn”,BlockSearch(list,record,N,BlockNum,key));} 3.實驗心得體會 通過本章的學習，對排序有較高層次的理解與認識，從平時的練習中可以看出排序是數(shù)據(jù)處理中經(jīng)常用到的重要運算。有序的順序表可以采用查找效率較高的折半查找法，而無序的順序表只能用效率較低的順序查找法。 注意：實驗結(jié)束后提交一份實驗報告電子文檔 電子文檔命名為“學號+姓名”，如：E01214058宋思怡 《數(shù)據(jù)結(jié)構(gòu)》實驗報告 （一）學號：姓名：專業(yè)年級： 實驗名稱：線性表 實驗日期：2014年4月14日 實驗?zāi)康模?/p> 1、熟悉線性表的定義及其順序和鏈式存儲結(jié)構(gòu)； 2、熟練掌握線性表在順序存儲結(jié)構(gòu)上實現(xiàn)基本操作的方法； 3、熟練掌握在各種鏈表結(jié)構(gòu)中實現(xiàn)線性表基本操作的方法； 4、掌握用 C/C++語言調(diào)試程序的基本方法。 實驗內(nèi)容： 一、編寫程序?qū)崿F(xiàn)順序表的各種基本運算，并在此基礎(chǔ)上設(shè)計一個主程序完成如下功能： （1）初始化順序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）輸出順序表L； （4）輸出順序表L長度； （5）判斷順序表L是否為空； （6）輸出順序表L的第3個元素； （7）輸出元素24的位置； （8）在L的第4個元素前插入元素0； （9）輸出順序表L； （10）刪除L的第5個元素； （11）輸出順序表L。 源代碼 調(diào)試分析（給出運行結(jié)果界面） 二、編寫程序?qū)崿F(xiàn)單鏈表的各種基本運算，并在此基礎(chǔ)上設(shè)計一個主程序完成如下功能： ???? ???? 小結(jié)或討論: （1）實驗中遇到的問題和解決方法 （2）實驗中沒有解決的問題 （3）體會和提高 南京信息工程大學實驗（實習）報告 實驗（實習）名稱數(shù)據(jù)結(jié)構(gòu)實驗（實習）日期 2011-11-2得分指導教師周素萍 系公共管理系專業(yè)信息管理與信息系統(tǒng)年級10級班次1姓名常玲學號2010230700 3實驗一順序表的基本操作及C語言實現(xiàn) 【實驗?zāi)康摹?/p> 1、順序表的基本操作及 C 語言實現(xiàn) 【實驗要求】 1、用 C 語言建立自己的線性表結(jié)構(gòu)的程序庫，實現(xiàn)順序表的基本操作。 2、對線性表表示的集合，集合數(shù)據(jù)由用戶從鍵盤輸入（數(shù)據(jù)類型為整型），建立相應(yīng)的順序表，且使得數(shù)據(jù)按從小到大的順序存放，將兩個集合的并的結(jié)果存儲在一個新的線性表集合中，并輸出。 【實驗內(nèi)容】 1、根據(jù)教材定義的順序表機構(gòu)，用 C 語言實現(xiàn)順序表結(jié)構(gòu)的創(chuàng)建、插入、刪除、查找等操作； 2、利用上述順序表操作實現(xiàn)如下程序：建立兩個順序表表示的集合（集合中無重 復的元素），并求這樣的兩個集合的并。 【實驗結(jié)果】 [實驗數(shù)據(jù)、結(jié)果、遇到的問題及解決] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的編號從0開始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 將合并逆置后的結(jié)果放在C表中，并刪除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅(qū)指針 // 保存pb的前驅(qū)指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當前最小結(jié)點插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當前最小結(jié)點插入A表表頭 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 順序表就是把線性表的元素存儲在數(shù)組中，元素之間的關(guān)系直接通過相鄰元素的位置來表達。 優(yōu)點：簡單，數(shù)據(jù)元素的提取速度快； 缺點：（1）靜態(tài)存儲，無法預(yù)知問題規(guī)模的大小，可能空間不足，或浪費存儲空間；（2）插入元素和刪除元素時間復雜度高——O（n） 求兩個集合的并集 該算法是求兩個集合s1和s2的并集，并將結(jié)果存入s引用參數(shù)所表示的集合中帶回。首先把s1集合復制到s中，然后把s2中的每個元素依次插入到集合s中，當然重復的元素不應(yīng)該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應(yīng)的實際參數(shù)集合中得到并集。 數(shù)據(jù)結(jié)構(gòu)實驗報告 一． 題目要求 1）編程實現(xiàn)二叉排序樹，包括生成、插入，刪除； 2）對二叉排序樹進行先根、中根、和后根非遞歸遍歷； 3）每次對樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數(shù)組去存儲一個班(50人以上)的成員信息(至少包括學號、姓名、成績3項),對比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案 對于前三個題目要求，我們用一個程序?qū)崿F(xiàn)代碼如下 #include typedefintElemType; //數(shù)據(jù)類型 typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數(shù) if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//創(chuàng)建二叉樹函數(shù) BiTreebst=NULL;inti=0;while(i //數(shù)據(jù)域 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指向被刪除結(jié)點的前驅(qū) if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //刪除函數(shù)，在T中刪除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) 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(){//主函數(shù) printf(“ ---------------------二叉排序樹的實現(xiàn)-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節(jié)點個數(shù):”);scanf(“%d”,&num);printf(“依次輸入這些整數(shù)（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創(chuàng)建成功!”);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:插入節(jié)點 2:刪除節(jié)點 3:打印二叉樹 4:非遞歸遍歷二叉樹 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“輸入要插入的節(jié)點:”); scanf(“%d”,&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);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(“程序執(zhí)行完畢!”); return 0;} goto loop;} return 0;對于第四小問，要儲存學生的三個信息，需要把上面程序修改一下，二叉樹結(jié)構(gòu)變?yōu)?typedefintElemType; //數(shù)據(jù)類型 typedefstring SlemType; typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //數(shù)據(jù)域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數(shù)不是key,而是另外三個 intInsertBST(BiTree&T,intno,intscore,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 InsertBST(T->rChild,no,score,name);} else return 0;} 其他含參函數(shù)也類似 即可完成50個信息存儲 用數(shù)組存儲50個信息，查看以往代碼 #include int main(){ cout<<“ 歡迎來到學生管理系統(tǒng)”< cout<<“該學號信息已經(jīng)存在，添加失敗”< break;} cout<<“重新輸入添加的學號”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“謝謝使用”< 二叉排序樹儲存數(shù)據(jù)界面（儲存學生信息略） 創(chuàng)建二叉樹： 插入節(jié)點： 刪除節(jié)點： 非遞歸遍歷： 退出： 數(shù)組儲存學生信息界面 分析查找效率： 因為二叉樹查找要創(chuàng)建二叉樹，而數(shù)組查找只創(chuàng)建一個數(shù)組，二叉樹的創(chuàng)建時間比較長，所以對于數(shù)據(jù)量較少的情況下數(shù)組的查找效率比較高。但當數(shù)據(jù)量增加時，二叉樹的查找優(yōu)勢就顯現(xiàn)出來。所以數(shù)據(jù)量越大的時候，二叉樹的查找效率越高。 四． 總結(jié)與改進 這個實驗工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進。 一開始打算用棧實現(xiàn)非遞歸，但是根據(jù)書里面的偽代碼發(fā)現(xiàn)部分是在C++編譯器里運行不了的（即使補充了頭文件和數(shù)據(jù)的定義），所以之后參考了網(wǎng)上的數(shù)組非遞歸，發(fā)現(xiàn)其功能和棧相似。 遞歸遍歷的實現(xiàn)比非遞歸的遍歷真的簡單很多。 開始時只看到前三問，所以沒有寫到儲存學生數(shù)據(jù)的代碼，里面還可以用clock（）函數(shù)加一個計算查找所要數(shù)據(jù)時間的代碼，讓二叉樹查找與數(shù)組查找到效率比較更加直觀。 實驗報告4 排序 一、實驗?zāi)康?/p> 1、掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法。 2、深刻理解排序的定義和各種排序方法的特點，并能加以靈活應(yīng)用。 3、了解各種方法的排序過程及其依據(jù)的原則，并掌握各種排序方法的時間復雜度的分析方法。 二、實驗要求及內(nèi)容 要求編寫的程序所能實現(xiàn)的功能包括： 1、從鍵盤輸入要排序的一組元素的總個數(shù) 2、從鍵盤依次輸入要排序的元素值 3、對輸入的元素進行快速排序 4、對輸入的元素進行折半插入排序 三、實驗代碼及相關(guān)注釋 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的結(jié)構(gòu)體 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的結(jié)構(gòu)體 int Partition(SqList &L, int low, int high) //1 尋找基準 { L.r[0]=L.r[low];//子表的第一個記錄作基準對象 int pivotkey = L.r[low].key;//基準對象關(guān)鍵字 while(low while(low L.r[low] = L.r[high];//小于基準對象的移到區(qū)間的左側(cè) while(low L.r[high] = L.r[low];//大于基準對象的移到區(qū)間的右側(cè) } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列l(wèi)ow-high中遞歸地進行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //尋找基準 QuickSort(L, low, pivotloc-1);//對左序列同樣遞歸處理 QuickSort(L, pivotloc+1, high);//對右序列同樣遞歸處理 } } Sequenlist *Sqlset() //2 輸入要折半插入排序的一組元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“請輸入要排序的所有元素的總個數(shù)：”; cin>>i; cout< cout<<“請依次輸入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入點在前半?yún)^(qū) else low=mid+1;//插入點在后半?yún)^(qū) } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“請選擇功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“請輸入要排序的所有元素的總個數(shù)：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后為：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函數(shù)功能說明 1、Sequenlist *Sqlset() 輸入要折半插入排序的一組元素 2、int Partition(SqList &L, int low, int high) 尋找快速排序的基準 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序運行結(jié)果 下圖僅為分別排序一次，可多次排序，后面有相關(guān)截圖： 六、實驗中遇到的問題、解決及體會 1、起初編寫快速排序的程序時，我是完全按照老師PPT上的算法敲上去的，然后建立了一個SqList的結(jié)構(gòu)體，調(diào)試運行時出現(xiàn)錯誤，仔細查看才意識到Partition函數(shù)中L中應(yīng)該包含元素key，而我建立結(jié)構(gòu)體時沒有注意，然后我將key這個元素補充進去，繼續(xù)調(diào)試，又出現(xiàn)錯誤，提示我Partition沒有定義，我就覺得很奇怪，我明明已經(jīng)寫了函數(shù)定義，為什么會這樣，當我又回過頭來閱讀程序時，我發(fā)現(xiàn)QuickSort函數(shù)中調(diào)用了Partition函數(shù)，但是我的Partition函數(shù)的定義在QuickSort函數(shù)的后面，于是我將Partition函數(shù)放到了QuickSort函數(shù)的前面，再次調(diào)試運行，就可以正常運行，得出結(jié)果了。這讓我懂得，編程一定要認真仔細，不可大意馬虎，否則又會花很多時間回過頭來檢查修改程序，得不償失。 運行程序錯誤截圖： 2、本來我是編寫了兩個程序，分別實現(xiàn)快速排序和折半插入排序的功能，但我后來想我是否可以將其合二為一，于是我想到用if選擇語句用來實現(xiàn)不同的功能，從鍵盤輸入功能選項m，if（m==1），可以進行快速排序，if（m==2），可以進行折半插入排序，于是我繼續(xù)思考，我是否可以在一次運行程序中，多次對含有不同元素的序列進行排序，于是我用了goto語句，每次排序一次后，自動循環(huán)到選擇語句，當不需要在排序的時候，可以從鍵盤輸入3，退出程序，這樣一來，程序變得更加實用和清晰明朗。這讓我懂得，想要編出好的程序，要善于思考，在實現(xiàn)所需功能的前提下，多想問題，看是否能使程序更加實用簡便。 修改程序前兩個運行結(jié)果截圖 （兩個程序，調(diào)試運行兩次，每次只能進行一次排序） 1、快速排序程序運行結(jié)果截圖： 2、折半插入排序程序結(jié)果截圖： 程序重要模塊修改截圖： 修改程序后運行截圖： （一個程序，調(diào)試運行一次，可多次進行不同序列的不同排序）第二篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
第三篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
第四篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
第五篇：數(shù)據(jù)結(jié)構(gòu)實驗報告
點擊咨詢 