数据结构习题解析与实训 第七章.docx
- 文档编号:5711847
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:28
- 大小:291.13KB
数据结构习题解析与实训 第七章.docx
《数据结构习题解析与实训 第七章.docx》由会员分享,可在线阅读,更多相关《数据结构习题解析与实训 第七章.docx(28页珍藏版)》请在冰点文库上搜索。
数据结构习题解析与实训第七章
第
7
章图
图是另一种重要的非线性结构,它比树的结构更复杂,更灵活。
习题中涉及到图的两
种常用的存储结构即图的邻接矩阵和邻接链表。
这些习题的目的主要让读者掌握图的深
度遍历和广度遍历的算法,同时加深对图的几个应用问题的算法的理解。
7.1
习题解析
【习题
1
】 连通图上实现广度优先遍历
题目要求:
在以邻接链表为存储结构的无向图上,实现无向图的广度优先遍历算法。
【习题1】和【习题2】是在连通图上实现图的广度优先遍历算法和深度优先遍历算法。
这
两个算法同样适用于对非连通图的遍历,稍加分析和设计,就可计算出非连通图上有几个
连通分量并给出对每个连通分量的遍历结果。
程序的实现留给读者自己完成。
结构说明:
#define VEXTYPE int
#define MAXLEN 40
typedefstructnode3 /*表结点结构*/
{ int adjvex;/*存放与表头结点相邻接的顶点在数组中的序号*/
struct node3*next;/*指向与表头结点相邻接的下一个顶点的表结点*/
}EDGENODE;
typrdefstruct
{EXTYPE vertex;/*存放图中顶点的信息*/
EDGENODE *
link
;/*指针指向对应的单链表中的表结点*/
}VEXNODE;
typedefstruct
第7章 图
l77
{EXNODE adjlist[MAXLEN];/*邻接链表表头向量*/
int vexnum,arcnum;/*顶点数和边数*/
int kind;/*图的类型*/
}ADJGRAPH;
举例说明:
设有连通图如图7.1所示,顶点值设定为V1=100,V2=200,V3=300,V4=
400,V5=500,V6=600,V7=700,V8=800,8个顶点和9条边的编号如图7.1所示
。
图7.1 连通图
数据输入过程如图7.2所示
。
图7.2 数据输入
输出结果如图7.3所示。
l78
数据结构习题解析与实训
图7.3 输出结果
注意:
此连通图邻接链表结构的建立过程是依赖于图7.1中8个顶点和9条边的编
号。
顶点和边的编号可以预先规定,编法不同,则数据输入的过程和输出的结果也会不
同,但广度优先遍历算法的结果都是正确的。
【解答】
#include ″datastru.h″
#include
#include
ADJGRAPHcreat_adjgraph(){
EDGENODE*p;
int i,s,d;
ADJGRAPHadjg;
adjg.kind=2;
printf(″\n\n输入顶点数和边数(用逗号隔开):
″);
scanf(″%d,%d″,&s,&d);fflush(stdin);
adjg.vexnum=s; /*存放顶点数在adjg.vexnum中*/
adjg.arcnum=d;/*存放边点数在adjg.arcnum中*/
printf(″\n\n″);
for(i=0;i 第7章 图 l79 {printf(″输入顶点%d的值: ″,i+1); scanf(″%d″,&adjg.adjlist[i].vertex);/*输入顶点的值*/ fflush(stdin); adjg.adjlist[i].link=NULL;} printf(″\n\n″); for(i=0;i {printf(″输入第%d条边的起始顶点和终止顶点(用逗号隔开): ″,i+1); scanf(″%d,%d″,&s,&d);/*输入边的起始顶点和终止顶点*/ fflush(stdin); while(s<1||s>adjg.vexnum||d<1||d>adjg.vexnum) {printf(″输入错,重新输入: ″); scanf(″%d,%d″,&s,&d);} s--; d--; p=malloc(sizeof(EDGENODE));/*建立一个和边相关的结点*/ p->adjvex=d; p->next=adjg.adjlist[s].link;/*挂到对应的单链表上*/ adjg.adjlist[s].link=p; p=malloc(sizeof(EDGENODE));/*建立另一个和边相关的结点*/ p->adjvex=s; p->next=adjg.adjlist[d].link;/*挂到对应的单链表上*/ adjg.adjlist[d].link=p;} returnadjg; } voidinitlinkqueue(LINKQUEUE*q) {/*初始化广度优先遍历算法中用到的链队列*/ q->front=malloc(sizeof(LINKQLIST)); (q->front)->next=NULL;q->rear=q->front; } intemptylinkqueue(LINKQUEUE*q) {/*判队空? */ intv; if(q->front==q->rear)v=1; else v=0; returnv; } voidenlinkqueue(LINKQUEUE*q,DATATYPE1x) {/*元素x入队列*/ l80 数据结构习题解析与实训 (q->rear)->next=malloc(sizeof(LINKQLIST)); q->rear=(q->rear)->next;(q->rear)->data=x; (q->rear)->next=NULL; } DATATYPE1dellinkqueue(LINKQUEUE*q) {/*删除队头元素*/ LINKQLIST*p; DATATYPE1v; if(emptylinkqueue(q)) {printf(″队列空.\n″); v=0;} else {p=(q->front)->next; (q->front)->next=p->next; if(p->next==NULL) q->rear=q->front; v=p->data; free(p);} returnv; } voidbfs(ADJGRAPHadjg, intvi) {/*连通图的广度优先遍历算法: 从vi顶点出发*/ intvisited[MAXLEN]; inti,v; EDGENODE*p; LINKQUEUE que,*q; q=&que; initlinkqueue(q); for(i=0; i visited[i]=0;/*visited数组初始化,均置0*/ visited[vi-1]=1;/*从编号为vi的顶点出发,visited数组对应位置1*/ printf(″%d″,adjg.adjlist[vi-1].vertex);/*输出vi顶点*/ enlinkqueue(q,vi);/*vi顶点入队列*/ while(! emptylinkqueue(q))/*队列不空,继续进行遍历*/ {v=dellinkqueue(q);/*取队头元素放入v变量中*/ v--; p=adjg.adjlist[v].link; while(p! =NULL)/*对应单链表不空,进行广度优先遍历*/ {if(visited[p->adjvex]==0) {visited[p->adjvex]=1; printf(″%d″,adjg.adjlist[p->adjvex].vertex); 第7章 图 l81 enlinkqueue(q,(p->adjvex)+1);} /*遍历到的未访问过的结点编号入队列*/ p=p->next;} } } main() { ADJGRAPHag; int j; printf(″\n连通图的广度遍历\n″); ag=creat_adjgraph();/*建立连通图的邻接链表结构*/ printf(″\n\n输入广度优先遍历起始顶点(1--%d): ″,ag.vexnum); scanf(″%d″,&j); printf(″\n\n广度优先遍历结果序列: ″); bfs(ag,j);/*连通图的广度遍历算法*/ printf(″\n\n″); } 【习题 2 】 连通图上实现深度优先遍历 题目要求: 在以邻接链表为存储结构的无向图上,实现无向图深度优先遍历算法。 结构说明: 同上题。 举例说明: 数据输入过程及输出结果如图7.4所示 。 图7.4 输入及输出 l82 数据结构习题解析与实训 【解答】 #include #include ″datastru.h″ #include intvisited[MAXLEN]; ADJGRAPHcreat_adjgraph() { EDGENODE*p; int i,s,d; ADJGRAPH adjg; adjg.kind=2; printf(″\n\n输入顶点数和边数(用逗号隔开): ″); scanf(″%d,%d″,&s,&d);fflush(stdin); adjg.vexnum=s; /*存放顶点数在adjg.vexnum中*/ adjg.arcnum=d;/*存放边点数在adjg.arcnum中*/ printf(″\n\n″); for(i=0; i {printf(″输入顶点%d的值: ″, i+1); scanf(″%d″,&adjg.adjlist[i].vertex); fflush(stdin); adjg.adjlist[i].link=NULL;} printf(″\n″); for(i=0; i {printf(″输入第%d条边的起始顶点和终止顶点(用逗号隔开): ″,i+1); scanf(″%d,%d″,&s,&d);/*输入边的起始顶点和终止顶点*/ fflush(stdin); while(s<1||s>adjg.vexnum||d<1||d>adjg.vexnum) {printf(″输入错,重新输入: ″); scanf(″%d,%d″,&s,&d);} s--; d--; p=malloc(sizeof(EDGENODE));/*建立一个和边相关的结点*/ p->adjvex=d; p->next=adjg.adjlist[s].link;/*挂到对应的单链表上*/ adjg.adjlist[s].link=p; p=malloc(sizeof(EDGENODE));/*建立另一个和边相关的结点*/ p->adjvex=s; p->next=adjg.adjlist[d].link;/*挂到对应的单链表上*/ adjg.adjlist[d].link=p;} 第7章 图 l83 returnadjg; } voiddfs(ADJGRAPHadjg,intv){ /*连通图的深度优先遍历算法: 从v顶点出发*/ EDGENODE*p; visited[v-1]=1;/*从编号为v的顶点出发,visited数组对应位置1*/ v--; printf(″%d″,adjg.adjlist[v].vertex);/*输出v顶点*/ p=adjg.adjlist[v].link;/*取单链表的第一个结点*/ while(p! =NULL)/*对应单链表不空,进行遍历*/ {f(visited[p->adjvex]==0)/*如果有未被访问过的结点*/ dfs(adjg,(p->adjvex)+1);/*递归调用深度优先遍历算法*/ p=p->next;}/*取单链表的下一个结点*/ } main() { ADJGRAPHag; int i; printf(″\n连通图的深度遍历\n″); ag=creat_adjgraph();/*建立连通图的邻接链表结构*/ for(i=0; i visited[i]=0; printf(″\n\n输入深度优先遍历起始顶点(1--%d): ″,ag.vexnum); scanf(″%d″,&i); printf(″\n\n深度优先遍历结果序列: ″); dfs(ag,i);/*连通图的深度优先遍历算法*/ printf(″\n\n″ ); 图7.5 有向图1 } 【习题 3 】 拓扑排序 题目要求: 在以邻接链表为存储结构的有向图上,实现有 向图的拓扑排序。 结构说明: 同上题。 举例说明: 设有向图如图7.5所示,顶点值设定为V1= 100,V2=200,V3=300,V4=400,V5=500,V6=600,6个顶点 和8条边的编号如图7.5所示。 数据输入过程及输出结果如图7.6所示。 l84 数据结构习题解析与实训 图7.6 对应输入的结果 【解答】 #include #include #include″datastru.h″ ADJGRAPHcreat_adjgraph() {/*建立有向图的邻接链表结构*/ EDGENODE*p; inti,s,d; ADJGRAPHadjg; adjg.kind=1; printf(″\n\n输入顶点数和边数(用逗号隔开): ″); scanf(″%d,%d″,&s,&d);fflush(stdin); adjg.vexnum=s; /*存放顶点数在adjg.vexnum中*/ adjg.arcnum=d;/*存放边点数在adjg.arcnum中*/ printf(″\n\n″); for(i=0; i {printf(″输入顶点%d的值: ″,i+1); scanf(″%d″,&adjg.adjlist[i].vertex);/*输入顶点的值*/ 第7章 图 l85 fflush(stdin); adjg.adjlist[i].link=NULL; adjg.adjlist[i].id=0;} printf(″\n\n″); for(i=0;i {printf(″输入第%d条有向弧的起始顶点和终止顶点(用逗号隔开): ″,i+1); scanf(″%d,%d″,&s,&d);/*输入弧的起始顶点和终止顶点*/ fflush(stdin); while(s<1||s>adjg.vexnum||d<1||d>adjg.vexnum) {printf(″输入错,重新输入: ″); scanf(″%d,%d″,&s,&d);} s--; d--; p=malloc(sizeof(EDGENODE));/*每条弧对应生成一个结点*/ p->adjvex=d; p->next=adjg.adjlist[s].link;/*结点插入对应的单链表上*/ adjg.adjlist[s].link=p; adjg.adjlist[d].id++;}/*弧的终端顶点入度加1*/ returnadjg; } voidtopsort(ADJGRAPHag) { inti,j,k,m,n,top; EDGENODE*p; n=ag.vexnum; top=-1;/*拓扑排序中用到的栈初始化*/ for(i=0;i if(ag.adjlist[i].id==0)/*入度为0的结点压入一链栈,top指向栈顶结 点*/ {g.adjlist[i].id=top; top=i;} m=0; printf(″\n\n有向图拓扑排序结果: ″); while(top! =-1)/*栈不空,进行拓扑排序*/ {j=top;/*取栈顶元素*/ top=ag.adjlist[top].id;/*删除一个栈顶元素*/ printf(″%d″,ag.adjlist[j].vertex);/*输出一个拓扑排序结点即栈顶元素*/ m++;/*拓扑排序结点计数加1*/ p=ag.adjlist[j].link; l86 数据结构习题解析与实训 while(p! =NULL)/*如果拓扑排序结点有出度*/ {k=p->adjvex; ag.adjlist[k].id--;/*删除相关的弧,即弧终点结点的入度减1*/ if(ag.adjlist[k].id==0)/*出现新的入度为0的顶点,将其入栈*/ {g.adjlist[k].id=top; top=k;} p=p->next;}} if(m printf(″\n\n有向图中有环路! \n\n″);/*拓扑排序过程中输出的顶点数小于有向图的顶 点数*/ } main() {DJGRAPHag; printf(″\n有向图的拓扑排序\n″); ag=creat_adjgraph();/*建立有向图的邻接链表结构*/ topsort(ag);/*进行拓扑排序*/ printf(″\n\n″); } 【习题 4 】 求最短路径 题目要求: 在以邻接矩阵为存储结构的有向图上,求单源点到其他顶点的最短路径。 结构说明: #define VEXTYPE int #define ADJTYPE int #define MAXLEN 40 typedef struct { otherdata…; /*图中边的信息,在下面的分析和讨论中忽略不考 虑*/ VEXTYPE vexs[MAXLEN];/*图中顶点的信息*/ ADJTYPE arcs[MAXLEN][MAXLEN];/*邻接矩阵*/ int vexnum,arcnum;/*顶点数和边数*/ int kind;/*图的类型*/ }MGRAPH; 举例说明: 设有向图如图7.7所示,顶点值设定为V1=100,V2=200,V3=300, V4=400,V5=500,V6=600,V7=700,7个顶点和11条边的编号如图7.7所示。 数据输入过程如图7.8所示,输出结果如图7.9所示。 第7章 图 l87 图7.7 有向图2 图7.8 输入 图7.9 结果 l88 数据结构习题解析与实训 【解答】 #include″datastru.h″ #include #include #defineMAX10000 MGRAPHcreate_mgraph(){ /*建立有向图的邻接矩阵结构*/ inti,j,k,h; MGRAPHmg; mg.kind=3; printf(″\n\n输入顶点数和边数(用逗号隔开): ″); scanf(″%d,%d″,&i,&j); mg.vexnum=i; /*存放顶点数在mg.vexnum中*/ mg.arcnum=j;/*存放边点数在mg.arcnum中*/ fflush(stdin); for(i=0;i {printf(″输入顶点%d的值: ″,i+1);/*输入顶点的值*/ scanf(″%d″,&mg.vexs[i]); fflush(stdin);} for(i=0;i for(j=0;j mg.arcs[i][j]=MAX; for(k=1;k<=mg.arcnum;k++) {printf(″输入第%d条边的起始顶点和终止顶点(用逗号隔开): ″,k); scanf(″%d,%d″,&i,&j);/*输入弧的起始顶点和终止顶点*/ fflush(stdin); while(i<1||i>mg.vexnum||j<1||j>mg.vexnum) {printf(″输入错,重新输入: ″); scanf(″%d,%d″,&i,&j);} printf(″输入此边权值: ″);/*输入弧上之权值*/ scanf(″%d″,&h); mg.arcs[i-1][j-1]=h;} returnmg; } main() { MGRAPHmg; intcost[MAXLEN][MAXLEN]; 第7章 图 l89 intpath[MAXLEN],s[MAXLEN]; intdist[MAXLEN]; inti,j,n,v0,min,u; printf(″\n求有向图单源点最短路径\n″); mg=create_mgraph();/*建立有向图的邻接矩阵结构*/ printf(″\n\n起始顶点为: ″);/*有向图中顶点的编号从1编起*/ scanf(″%d″,&v0); v0--; n=mg.vexnum; for(i=0;i {for(j=0;j cost[i][j]=mg.arcs[i][j]; cost[i][i]=0;} for(i=0;i {dist[i]=cost[v0][i];/*dist数组初始化*/ if(dist[i] path[i]=v0;} for(i=0;i s[i]=0; s[v0]=1; for(i=0;i { min=MAX; u=v0; for(j=0;j if(s[j]==0&&dist[j] {min=dist[j]; u=j;} s[u]=1;/*u顶点是求得最短路径的顶点编号*/ for(j=0;j if(s[j]==0&&dist[u]+cost[u][j] {dist[j]=dist[u]+cost[u][j]; path[j]=u;}/*path记录了路径经过的顶点*/ } for(i=0;i if(s[i]==1)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构习题解析与实训 第七章 数据结构 习题 解析 第七