数据结构试题库集及答案

导读:严蔚敏《数据结构习题集》解答,第78页共124页StatusDelete_Arc(AMLGraph&G,charv,charw)////在邻接多重表表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.adjmulist[i].firste

数据结构试题库集及答案

第 78 页 共 124 页

Status Delete_Arc(AMLGraph &G,char v,char w)////在邻接多重表表示的图G 上删除边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR;

if((j=LocateVex(G,w))<0) return ERROR;

if(G.adjmulist[i].firstedge->jvex==j)

G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink;

else

{

for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink);

if (!p) return ERROR; //未找到

p->ilink=p->ilink->ilink;

} //在i 链表中删除该边

if(G.adjmulist[j].firstedge->ivex==i)

G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink;

else

{

for(p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!=i;p=p->jlink);

if (!p) return ERROR; //未找到

q=p->jlink;

p->jlink=q->jlink;

free(q);

} //在i 链表中删除该边

严蔚敏《数据结构习题集》解答

G.arcnum--;

return OK;

}//Delete_Arc

7.19

第 79 页 共 124 页

Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建 立邻接多重表

{

InitAMLGraph(G);

scanf("%d",&v);

if(v<0) return ERROR; //顶点数不能为负

G.vexnum=v;

scanf(%d",&a);

if(a<0) return ERROR; //边数不能为负

G.arcnum=a;

for(m=0;m<v;m++)

G.adjmulist[m].data=getchar(); //输入各顶点的符号

for(m=1;m<=a;m++)

{

t=getchar();h=getchar(); //t 为弧尾,h 为弧头

if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到

p->ivex=i;p->jvex=j;

p->ilink=NULL;p->jlink=NULL; //边结点赋初值

if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p;

else

{

q=G.adjmulist[i].firstedge;

while(q)

{

r=q;

if(q->ivex==i) q=q->ilink;

else q=q->jlink;

}

if(r->ivex==i) r->ilink=p;//注意i 值既可能出现在边结点的ivex 域中,

else r->jlink=p; //又可能出现在边结点的jvex 域中

}//else //插入i 链表尾部

if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p;

else

{

q=G.adjmulist[i].firstedge;

while(q)

{

r=q;

严蔚敏《数据结构习题集》解答

if(q->jvex==j) q=q->jlink;

else q=q->ilnk;

}

if(r->jvex==j) r->jlink=p;

else r->ilink=p;

}//else //插入j 链表尾部

}//for

return OK;

}//Build_AdjList

7.20

第 80 页 共 124 页

int Pass_MGraph(MGraph G)//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回否则返回0

{

for(x=0;x<G.vexnum;x++)

for(y=0;y<G.vexnum;y++)

if(G.arcs[x][y])

{

for(z=0;z<G.vexnum;z++)

if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0;//图不可传递的条件

}//if

return 1;

}//Pass_MGraph 1,

7.21

int Pass_ALGraph(ALGraph G)//判断一个邻接表存储的有向图是不是可传递的,是则返回 1, 否则返回0

{

for(x=0;x<G.vexnum;x++)

for(p=G.vertices[x].firstarc;p;p=p->nextarc)

{

y=p->adjvex;

for(q=G.vertices[y].firstarc;q;q=q->nextarc)

{

z=q->adjvex;

if(z!=x&&!is_adj(G,x,z)) return 0;

}//for

}//for

}//Pass_ALGraph

int is_adj(ALGraph G,int m,int n)//判断有向图G 中是否存在边(m,n),是则返回1,否则返回0 {

for(p=G.vertices[m].firstarc;p;p=p->nextarc)

if(p->adjvex==n) return 1;

return 0;

}//is_adj

严蔚敏《数据结构习题集》解答

7.22

int visited[MAXSIZE]; //指示顶点是否在当前路径上

第 81 页 共 124 页

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G 中顶点i 到顶点j 是否有路 径,是则返回1,否则返回0

{

if(i==j) return 1; //i 就是j

else

{

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

{

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i 下游的顶点到j 有路径

}//for

}//else

}//exist_path_DFS

7.23

int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G 中顶点i 到顶点j 是否有路径, 是则返回1,否则返回0

{

int visited[MAXSIZE];

InitQueue(Q);

EnQueue(Q,i);

{

DeQueue(Q,u);

visited[u]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

{

k=p->adjvex;

if(k==j) return 1;

if(!visited[k]) EnQueue(Q,k);

}//for

}//while

return 0;

}//exist_path_BFS

7.24

void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G {

int visited[MAXSIZE];

InitStack(S);

Push(S,GetVex(S,1)); //将第一个顶点入栈

visit(1);

visited =1;

严蔚敏《数据结构习题集》解答

while(!StackEmpty(S))

{

while(Gettop(S,i)&&i)

{

j=FirstAdjVex(G,i);

if(j&&!visited[j])

{

visit(j);

visited[j]=1;

Push(S,j); //向左走到尽头

}

}//while

if(!StackEmpty(S))

{

Pop(S,j);

Gettop(S,i);

k=NextAdjVex(G,i,j); //向右走一步

if(k&&!visited[k])

{

visit(k);

visited[k]=1;

Push(S,k);

}

}//if

}//while

五星文库wxphp.com包含总结汇报、办公文档、IT计算机、考试资料、文档下载、党团工作、资格考试、教程攻略、计划方案、教学研究以及数据结构试题库集及答案等内容。

本文共54页1<<41424344454647>>54