数据结构实验题答案

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-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-n