《数据结构实验题答案.doc》由会员分享，可在线阅读，更多相关《数据结构实验题答案.doc（12页珍藏版）》请在三一文库上搜索。
1、实验四.稀疏矩阵的三元组顺序表示方法及基本操作的实现（建立、输出、转置）并实现一个主菜单来实现。#include#define maxsize 50#define maxrow 10#define maxcol 10typedef struct int i,j; int data;triple;typedef struct triple elemmaxsize+1; int mu,nu,tu;tsmatrix;void createsmatrix (tsmatrix *t) t=(tsmatrix*)malloc(sizeof(tsmatrix); if(!t) exit(0); t-mu=0
2、; t-nu=0; t-tu=0;void transposesmatrix(tsmatrix m,tsmatrix*t) int q=1,col,p; t-mu=m.nu;t-nu=m.mu;t-tu=m.tu; if(t-tu) q=1; for(col=1;col=m.nu;col+) for(p=1;pelemq.i=m.elemp.j; t-elemq.j=m.elemp.i; t-elemq.data=m.elemp.data; +q; void scanftsmatrix(tsmatrix *t) int count; printf(enter the nums of matri
3、xs rows:n); scanf(%d,&t-mu); printf(enter the nums of matrixs columns:n); scanf(%d,&t-nu); printf(enter the nums of matrixs datas:n); scanf(%d,&t-tu); for(count=1;counttu;count+) printf(enter the non-zero numsrow,column,data:n); scanf(%d%d%d,&t-elemcount.i,&t-elemcount.j,&t-elemcount.data); /*void p
4、rintftsmatrix(tsmatrix*t) int counter,col; printf(the xishu juzheng is :n); for(counter=1;countertu;) for(col=1;colnu;col+) if(t-elemcounter.j=col) printf(%dt,t-elemcounter.data); counter+; if(t-elemcounter.i=t-elemcounter-1.i) ; else if(col=t-nu) printf(n); else for(col+;colnu;col+)printf(*t); prin
5、tf(n); else printf(*t); */void printftsmatrix(tsmatrix*t) int counter,amaxrowmaxcol=0,row,col; int*p; p=&a; printf(the sparse matrix is :n); for(counter=1;countertu;counter+) at-elemcounter.i-1t-elemcounter.j-1=t-elemcounter.data; for(row=1;rowmu;row+) for(col=1;colnu;col+) printf(%dt,*p); p+; print
6、f(n); p=p+maxcol-col+1; void main() tsmatrix T,M;int x;char character/*zifu*/,n; createsmatrix(&T); scanftsmatrix(&T); while(character!=#) printf(choice:1-transposesmatrix;2-printftsmatrixn); printf(enter the num for your choicen); scanf(%d,&x); switch(x) case 1:transposesmatrix(T,&M); printftsmatri
7、x(&M); break; case 2:printftsmatrix(&T); break; n=getchar(); printf(enter one char# for your choice to quit:n); scanf(%c,&character); getch(); 实验五 树及二叉树实验1) 按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，后按先序、中序、后序顺序分别遍历这棵二叉树。2) 编写一个求二叉树叶子结点数的算法。3) 交换左右孩子。#include #define NULL 0typedef struct bitnode int data;
8、struct bitnode *lchild, *rchild;bitnode,*bitree;void createbitree(bitree *t) char ch,zifu; scanf(%c,&ch); zifu=getchar(); if(ch=#) *t=NULL; else if(!(*t)=(bitree)malloc(sizeof(bitnode) ;/* if(!(*t=(bitnode*)malloc(sizeof(bitnode) ;*/ (*t)-data=ch; printf(enter the lchildn); createbitree(&(*t)-lchild
9、); printf(enter the rchildn); createbitree(&(*t)-rchild); void preorder(bitree *t) if(*t!=NULL) printf(%ct,(*t)-data); preorder(&(*t)-lchild); preorder(&(*t)-rchild); void inorder(bitree *t) if(*t!=NULL) inorder(&(*t)-lchild); printf(%ct,(*t)-data); inorder(&(*t)-rchild); void postorder(bitree *t) i
10、f(*t!=NULL) postorder(&(*t)-lchild); postorder(&(*t)-rchild); printf(%ct,(*t)-data); int leafcount(bitree *t) int num,num1,num2; if(*t=NULL) num=0; else if(*t)-lchild=NULL)&(*t)-rchild=NULL) num=1; else num1=leafcount(&(*t)-lchild); num2=leafcount(&(*t)-rchild); num=num1+num2; return num;void change
11、leaf(bitree *t) bitree p,q; if(*t!=NULL) p=(*t)-rchild; (*t)-rchild=(*t)-lchild; (*t)-lchild=p; changeleaf(&(*t)-lchild); changeleaf(&(*t)-rchild); void instruction(void)printf(nEnter your choice:n 1 to preordern 2 to inordern 3 to postordern 4 to change the leafn 5 to leafcountn 6 to endn); void ma
12、in() bitree t; int choice; printf(Enter the root of the treen); createbitree(&t); instruction(); scanf(%d,&choice); while (choice!=6) switch (choice) case 1: printf(The perorder of the tree is:n); preorder(&t); instruction(); scanf(%d,&choice); break; case 2: printf(The ororder is:n); inorder(&t); i
13、nstruction(); scanf(%d,&choice); break; case 3: printf(The postorder is:n); postorder(&t); instruction(); scanf(%d,&choice); break; case 5: printf(The leafs is %dn,leafcount(&t); instruction(); scanf(%d,&choice); break; case 4: changeleaf(&t); printf(After change the tree is:n); preorder(&t); instru
14、ction(); scanf(%d,&choice); break; default: printf(Errorn); break; printf(End of runn); getch();实验六1) 建立无向图和有向图的邻接矩阵存储，计算顶点的度，并按要求输出图的基本信息。2) 建立有向图的邻接表存储表示，并根据存储计算顶点的出度和入度，然后按照要求输出图的基本信息。1）/*邻接矩阵存储*/#include#define infinity -#define max_vertex_num 20typedef enumUDG=1,DGgraphkind;typedef struct arcce
15、ll char adj; arccell,adjmatrixmax_vertex_nummax_vertex_num;typedef struct char vexsmax_vertex_num; adjmatrix arcs; int vexnum,arcnum; graphkind kind; mgraph;int locatevex(mgraph*g,char*arc1) int i; for(i=0;ivexnum;i+) if(g-vexsi=*arc1) return i; void createDG(mgraph*g) int i,j,k;char*tarc,*harc,zifu
16、; printf(enter the num for Gs vexnum,arcnum,and graphkind:n); scanf(%d%d%d,&g-vexnum,&g-arcnum,&g-kind); for(i=0;ivexnum;i+) printf(enter the vexn); zifu=getchar(); scanf(%c,&g-vexsi); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-arcsij.adj=0; for(k=0;karcnum;k+) zifu=getchar(); printf(enter one arcvex
17、n); scanf(%c,tarc); zifu=getchar(); scanf(%c,harc); i=locatevex(g,tarc);j=locatevex(g,harc); g-arcsij.adj=1; void createUDG(mgraph*g) int i,j,k,x,y;char*arc1,*arc2,zifu; printf(enter the num for Gs vexnum,arcnum,and graphkind:n); scanf(%d%d%d,&g-vexnum,&g-arcnum,&g-kind); for(i=0;ivexnum;i+) printf(
18、enter the vexn); zifu=getchar(); scanf(%c,&g-vexsi); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-arcsij.adj=0; for(k=0;karcnum;k+) zifu=getchar(); printf(enter one arcvexn); scanf(%c,arc1); zifu=getchar(); scanf(%c,arc2); x=locatevex(g,arc1);y=locatevex(g,arc2); g-arcsxy.adj=1; g-arcsyx.adj=1;void deg
19、ree(mgraph*g) int i,j,counter=0,sum=0; if(g-kind=DG) for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) if(g-arcsij.adj=1) counter+; printf(the outdegree of %c is %dn,g-vexsi,counter); for(j=0;jvexnum;j+) if(g-arcsji.adj=1) counter+; printf(the degree of %c is %dn,g-vexsi,counter); counter=0; if(g-kind=UDG) fo
20、r(i=0;ivexnum;i+) for(j=0;jvexnum;j+) if(g-arcsij.adj=1) sum+; printf(the degree of %c is %dn,g-vexsi,sum); sum=0; void print(mgraph*g) int i,j; printf(the graph is n); for(i=0;ivexnum;i+) printf(t%c,g-vexsi); printf(n); for(i=0;ivexnum;i+) printf(%ct,g-vexsi); for(j=0;jvexnum;j+) printf(%ct,g-arcsi
21、j.adj); printf(n); main() int k,m,n;mgraph G;char biao,sign; while(biao!=#) printf(please make your chioce:1-createUDG;2-createDGn); scanf(%d,&k); switch(k) case 1: createUDG(&G); print(&G); degree(&G); break; case 2: createDG(&G); print(&G); degree(&G); break; sign=getchar(); printf(enter your choi
22、ce* for quitn); scanf(%c,&biao); getch();2）/*邻接表存储*/#include#define null 0#define max_vertex_num 20typedef enumDG=1graphkind;typedef struct arcnode int adjvex; struct arcnode *nextarc; arcnode;/*顶点结点*/typedef struct vnode char data; arcnode *firstarc; vnode,adjlistmax_vertex_num;typedef struct adjli
23、st vertices; int vexnum,arcnum; graphkind kind; algraph;void createDG(algraph*g) int i,j;arcnode*p,*q;char over=h,biao; printf(please enter num for Gs vexnum,arcnum,kind:n); scanf(%d%d%d,&g-vexnum,&g-arcnum,&g-kind); for(i=0;ivexnum;i+) printf(enter the vexn); biao=getchar(); scanf(%c,&g-verticesi.d
24、ata); g-verticesi.firstarc=null; for(i=0;ivexnum;i+) printf(please create the %d single link of %cn,i+1,g-verticesi.data); over=h; while(over!=*) if(g-verticesi.firstarc=null) printf(if the single link has no degree please input *n); biao=getchar(); scanf(%c,&over); if(over=*) break; else p=(arcnode
25、*)malloc(sizeof(arcnode); printf(enter the position of firstadjvex:n); scanf(%d,&p-adjvex); g-verticesi.firstarc=p; p-nextarc=null; else q=(arcnode*)malloc(sizeof(arcnode); printf(enter the position of nextadjvex:n); scanf(%d,&q-adjvex); p-nextarc=q; q-nextarc=null; printf(enter * to quit the single
26、 link because it has no dajvexn); biao=getchar(); scanf(%c,&over); getch(); void outdegree(algraph*g) int count=0,i; arcnode*ptr; for(i=0;ivexnum;i+) if(g-verticesi.firstarc!=null) count+; ptr=g-verticesi.firstarc; for(;ptr-nextarc!=null;) ptr=ptr-nextarc; count+; printf(the outdegree of %c is %dn,g
27、-verticesi.data,count); count=0; else printf(the outdegree of %c is %dn,g-verticesi.data,count); void indegree(algraph*g) int count=0,i; arcnode*ptr; for(i=0;ivexnum;i+) if(g-verticesi.firstarc!=null) count+; ptr=g-verticesi.firstarc; for(;ptr-nextarc!=null;) ptr=ptr-nextarc; count+; printf(the inde
28、gree of %c is %dn,g-verticesi.data,count); count=0; else printf(the indegree of %c is %dn,g-verticesi.data,count); void print(algraph*g) int i; arcnode*ptr; for(i=0;ivexnum;i+) if(g-verticesi.firstarc!=null) printf(%ct-,g-verticesi.data); ptr=g-verticesi.firstarc; for(;ptr-nextarc!=null;) printf(%ct
29、-,g-verticesptr-adjvex.data); ptr=ptr-nextarc; printf(%c,g-verticesptr-adjvex.data); printf(n); else printf(%cn,g-verticesi.data); main() int m;algraph G; printf(please create DG according to the turn of outdegree n); createDG(&G); printf(the algraph isn); print(&G); outdegree(&G); printf(please create DG according to the turn of indegree n); createDG(&G); printf(the algraph isn); print(&G); indegree(&G); getch();实验七 查找与排序实验目的要求：1) 学生在实习中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效算法的可能性和寻找、构造高效算法的方法。实验内容：1) 实现二分查找算法，并计算相应的ASL。2) 实现插入排序或选择排序算法。