数据结构全套配套课件C语言版李刚电子资源第7章.doc

《数据结构全套配套课件C语言版李刚电子资源第7章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章一、填空题1、n(n-1)/22、极大连通子图3、深度优先广度优先4、普里姆方法克鲁斯卡尔方法二、选择题1、B2、C3、C4、A5、B三、应用题1、2、3、四、算法设计题1、#include"stdio.h"#include"stdlib.h"typedefstructnode//邻接表结点结构定义{intadjvex;structnode*next;}Anode;typedefstruct//顶点数组元素结点结构定义{charvertex;Anode*link;}Vnode;typedefstruct{Vnodeadjlist[100];intvexnum,arcnum;}A

2、djgraph;Adjgraphcreat(){Anode*p;inti,s,d;Adjgraphag;printf("请输入顶点和边的数量：");scanf("%d,%d",&ag.vexnum,&ag.arcnum);getchar();//吸收回车符for(i=0;i

3、nf("%d,%d",&s,&d);//前插法p=(Anode*)malloc(sizeof(Anode));p->adjvex=d;p->next=ag.adjlist[s].link;ag.adjlist[s].link=p;p=(Anode*)malloc(sizeof(Anode));p->adjvex=s;p->next=ag.adjlist[d].link;ag.adjlist[d].link=p;}returnag;}intcount(Adjgraphag){Anode*p;intsum=0,n,i;for(i=0;i

4、djlist[i].link;while(p!=NULL){n++;p=p->next;}if(n==2)sum++;}returnsum;}main(){Adjgraphag;intsum;ag=creat();sum=count(ag);printf("%d",sum);}2、#include"stdio.h"#include"stdlib.h"intvisited[10];typedefstruct{charvexs[10];intedges[10][10];intn,e;//分别代表图的顶点数和边数}MGraph;//结构体类型voidCreateMGraph(MGraph*

5、G){inti,j,k;scanf("%d,%d",&G->n,&G->e);//输入顶点数和边数getchar();for(i=0;in;i++)G->vexs[i]=getchar();//输入顶点信息for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;//邻接矩阵初始化printf("请输入一对顶点的序号:");for(k=0;ke;k++){scanf("%d,%d",&i,&j);//输入边的一对顶点序号G->edges[i][j]=1;G->edges[j][i]=1;}}voiddfs(MGr

6、aph*G,inti){intj;printf("%c",G->vexs[i]);visited[i]=1;for(j=0;jn;j++)if(G->edges[i][j]==1&&visited[j]==0)dfs(G,j);}voiddfstraverse(MGraph*G){inti;for(i=0;in;i++)visited[i]=0;//初始化都未曾访问过for(i=0;in;i++)if(visited[i]==0)//未曾访问过dfs(G,i);}main(){MGraph*G,ag;G=&ag;CreateMGraph(G);dfstrave

7、rse(G);}