数据结构习题解析与实训 第七章Word文档格式.docx
《数据结构习题解析与实训 第七章Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构习题解析与实训 第七章Word文档格式.docx（28页珍藏版）》请在冰点文库上搜索。
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 <
stdio.h>
malloc.h>
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<
adjg.vexnum;
i++）
l79
{printf（″输入顶点%d的值:
″,i+1）;
scanf（″%d″,&
adjg.adjlist[i].vertex）;
/＊输入顶点的值＊/
fflush（stdin）;
adjg.adjlist[i].link=NULL;
}
adjg.arcnum;
{printf（″输入第%d条边的起始顶点和终止顶点（用逗号隔开）:
scanf（″%d,%d″,&
/＊输入边的起始顶点和终止顶点＊/
while（s<
1||s>
adjg.vexnum||d<
1||d>
adjg.vexnum）
{printf（″输入错,重新输入:
s--;
d--;
p=malloc（sizeof（EDGENODE））;
/＊建立一个和边相关的结点＊/
p->
adjvex=d;
next=adjg.adjlist[s].link;
/＊挂到对应的单链表上＊/
adjg.adjlist[s].link=p;
/＊建立另一个和边相关的结点＊/
adjvex=s;
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
rear）->
next=malloc（sizeof（LINKQLIST））;
rear=（q->
next;
（q->
data=x;
DATATYPE1dellinkqueue（LINKQUEUE＊q）
{/＊删除队头元素＊/
LINKQLIST＊p;
DATATYPE1v;
if（emptylinkqueue（q）） {printf（″队列空.\n″）;
v=0;
else
{p=（q->
（q->
next=p->
if（p->
next==NULL） q->
v=p->
data;
free（p）;
voidbfs（ADJGRAPHadjg, intvi）
{/＊连通图的广度优先遍历算法:
从vi顶点出发＊/
intvisited[MAXLEN];
inti,v;
LINKQUEUE que,＊q;
q=&
que;
initlinkqueue（q）;
i<
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）;
l81
enlinkqueue（q,（p->
adjvex）+1）;
} /＊遍历到的未访问过的结点编号入队列＊/
p=p->
}
main（）
{ ADJGRAPHag;
int j;
printf（″\n连通图的广度遍历\n″）;
ag=creat_adjgraph（）;
/＊建立连通图的邻接链表结构＊/
printf（″\n\n输入广度优先遍历起始顶点（1－－%d）:
″,ag.vexnum）;
j）;
printf（″\n\n广度优先遍历结果序列:
bfs（ag,j）;
/＊连通图的广度遍历算法＊/
printf（″\n\n″）;
2
】 连通图上实现深度优先遍历
在以邻接链表为存储结构的无向图上,实现无向图深度优先遍历算法。
同上题。
数据输入过程及输出结果如图7．4所示
图7.4 输入及输出
l82
ADJGRAPHcreat_adjgraph（）
{ EDGENODE＊p;
ADJGRAPH adjg;
/＊存放顶点数在adjg.vexnum中＊/
i++）/＊输入顶点的值＊/
″, i+1）;
printf（″\n″）;
{printf（″输入错,重新输入:
l83
voiddfs（ADJGRAPHadjg,intv）{
/＊连通图的深度优先遍历算法:
从v顶点出发＊/
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->
/＊递归调用深度优先遍历算法＊/
p=p->
}/＊取单链表的下一个结点＊/
{
ADJGRAPHag;
int i;
printf（″\n连通图的深度遍历\n″）;
ag=creat_adjgraph（）;
ag.vexnum;
i++）/＊visited数组初始化,均置0＊/
visited[i]=0;
printf（″\n\n输入深度优先遍历起始顶点（1--%d）:
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″datastru.h″
{/＊建立有向图的邻接链表结构＊/
EDGENODE＊p;
inti,s,d;
ADJGRAPHadjg;
adjg.kind=1;
printf（″\n\n输入顶点数和边数（用逗号隔开）:
adjg.vexnum=s;
adjg.arcnum=d;
for（i=0;
i++）/＊邻接链表顶点初始化＊/
{printf（″输入顶点%d的值:
scanf（″%d″,&
l85
fflush（stdin）;
adjg.adjlist[i].link=NULL;
adjg.adjlist[i].id=0;
printf（″\n\n″）;
{printf（″输入第%d条有向弧的起始顶点和终止顶点（用逗号隔开）:
scanf（″%d,%d″,&
/＊输入弧的起始顶点和终止顶点＊/
while（s<
scanf（″%d,%d″,&
s--;
d--;
p=malloc（sizeof（EDGENODE））;
/＊每条弧对应生成一个结点＊/
p->
/＊结点插入对应的单链表上＊/
adjg.adjlist[s].link=p;
adjg.adjlist[d].id++;
}/＊弧的终端顶点入度加1＊/
voidtopsort（ADJGRAPHag）
{ inti,j,k,m,n,top;
n=ag.vexnum;
top=-1;
/＊拓扑排序中用到的栈初始化＊/
n;
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
=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->
}}
if（m<
n）
printf（″\n\n有向图中有环路!
\n\n″）;
/＊拓扑排序过程中输出的顶点数小于有向图的顶
点数＊/
{DJGRAPHag;
printf（″\n有向图的拓扑排序\n″）;
/＊建立有向图的邻接链表结构＊/
topsort（ag）;
/＊进行拓扑排序＊/
4
】 求最短路径
在以邻接矩阵为存储结构的有向图上,求单源点到其他顶点的最短路径。
#define ADJTYPE int
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所示。
l87
图7.7 有向图2
图7.8 输入
图7.9 结果
l88
#defineMAX10000
MGRAPHcreate_mgraph（）{
/＊建立有向图的邻接矩阵结构＊/
inti,j,k,h;
MGRAPHmg;
mg.kind=3;
i,&
mg.vexnum=i;
/＊存放顶点数在mg.vexnum中＊/
mg.arcnum=j;
/＊存放边点数在mg.arcnum中＊/
mg.vexnum;
mg.vexs[i]）;
i++）/＊邻接矩阵初始化＊/
for（j=0;
j<
j++）
mg.arcs[i][j]=MAX;
for（k=1;
k<
=mg.arcnum;
k++）
{printf（″输入第%d条边的起始顶点和终止顶点（用逗号隔开）:
″,k）;
while（i<
1||i>
mg.vexnum||j<
1||j>
mg.vexnum）
printf（″输入此边权值:
/＊输入弧上之权值＊/
h）;
mg.arcs[i-1][j-1]=h;
returnmg;
MGRAPHmg;
intcost[MAXLEN][MAXLEN];
l89
intpath[MAXLEN],s[MAXLEN];
intdist[MAXLEN];
inti,j,n,v0,min,u;
printf（″\n求有向图单源点最短路径\n″）;
mg=create_mgraph（）;
printf（″\n\n起始顶点为:
/＊有向图中顶点的编号从1编起＊/
v0）;
v0--;
n=mg.vexnum;
for（i=0;
i++）/＊cost矩阵初始化＊/
{for（j=0;
cost[i][j]=mg.arcs[i][j];
cost[i][i]=0;
{dist[i]=cost[v0][i];
/＊dist数组初始化＊/
if（dist[i]<
MAX&
&
dist[i]>
0）/＊path数组初始化＊/
path[i]=v0;
i++）/＊s数组初始化＊/
s[i]=0;
s[v0]=1;
i++）/＊按最短路径递增算法计算＊/
{ min=MAX;
u=v0;
for（j=0;
if（s[j]==0&
dist[j]<
min）
{min=dist[j];
u=j;
s[u]=1;
/＊u顶点是求得最短路径的顶点编号＊/
dist[u]+cost[u][j]<
dist[j]） /＊调整dist＊/
{dist[j]=dist[u]+cost[u][j];
path[j]=u;
}/＊path记录了路径经过的顶点＊/
}
i++）/＊打印结果＊/
if（s[i]==1）
升级会员 