数据结构试题库集及答案

导读:严蔚敏《数据结构习题集》解答,存在一条回路;扫描路径向量path可以获得这条回路上的所有结点.把结点序列(例如,voidGet_SGraph(OLGraphG)//求十字链表结构储存的有向图G,第82页共124页分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考所以从第一个结点出发一定能够访问到所有结点.7.25见书后解答.7.26StatusTopoNo(ALGraphG)//按

数据结构试题库集及答案

第 82 页 共 124 页

分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考

所以从第一个结点出发一定能够访问到所有结点.

7.25

见书后解答.

7.26

Status TopoNo(ALGraph G)//按照题目要求顺序重排有向图中的顶点

{

int new[MAXSIZE],indegree[MAXSIZE]; //储存结点的新序号

n=G.vexnum;

FindInDegree(G,indegree);

InitStack(S);

for(i=1;i<G.vexnum;i++)

if(!indegree[i]) Push(S,i); //零入度结点入栈

count=0;

while(!StackEmpty(S))

{

Pop(S,i);

new[i]=n--; //记录结点的拓扑逆序序号

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

6.37.由于是强连通图, count++;

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

{

k=p->adjvex;

if(!(--indegree[k])) Push(S,k);

}//for

}//while

if(count<G.vexnum) return ERROR; //图中存在环

for(i=1;i<=n;i++) printf("Old No:%d New No:%d\n",i,new[i])

return OK;

}//TopoNo

分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵.

7.27

int visited[MAXSIZE];

第 83 页 共 124 页

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G 的顶点i 到j 是 否存在长度为k 的简单路径

{

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求

else if(k>0)

{

visited[i]=1;

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

{

l=p->adjvex;

if(!visited[l])

}//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中

}//else

return 0; //没找到

}//exist_path_len

7.28

int path[MAXSIZE],visited[MAXSIZE]; //暂存遍历过程中的路径

int Find_All_Path(ALGraph G,int u,int v,int k)//求有向图G 中顶点u 到v 之间的所有简单路径,k 表示当前路径长度

{

path[k]=u; //加入当前路径中

visited[u]=1;

if(u==v) //找到了一条简单路径

{

printf("Found one path!\n");

for(i=0;path[i];i++) printf("%d",path[i]); //打印输出

}

else

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

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

{

l=p->adjvex;

if(!visited[l]) Find_All_Path(G,l,v,k+1); //继续寻找

}

visited[u]=0;

path[k]=0; //回溯

}//Find_All_Path

main()

{

...

Find_All_Path(G,u,v,0); //在主函数中初次调用,k 值应为0

...

}//main

7.29

第 84 页 共 124 页

int GetPathNum_Len(ALGraph G,int i,int j,int len)//求邻接表方式存储的有向图G 的顶点i 到j 之间长度为len 的简单路径条数

{

if(i==j&&len==0) return 1; //找到了一条路径,且长度符合要求

else if(len>0)

{

sum=0; //sum 表示通过本结点的路径数

visited[i]=1;

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

{

l=p->adjvex;

sum+=GetPathNum_Len(G,l,j,len-1)//剩余路径长度减一

}//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中

}//else

return sum;

}//GetPathNum_Len

7.30

int visited[MAXSIZE];

int path[MAXSIZE]; //暂存当前路径

int cycles[MAXSIZE][MAXSIZE]; //储存发现的回路所包含的结点

int thiscycle[MAXSIZE]; //储存当前发现的一个回路

int cycount=0; //已发现的回路个数

void GetAllCycle(ALGraph G)//求有向图中所有的简单回路

{

for(v=0;v<G.vexnum;v++) visited[v]=0;

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

if(!visited[v]) DFS(G,v,0); //深度优先遍历

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

}//DFSTraverse

void DFS(ALGraph G,int v,int k)//k 表示当前结点在路径上的序号

{

visited[v]=1;

path[k]=v; //记录当前路径

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

{

w=p->adjvex;

if(!visited[w]) DFS(G,w,k+1);

else //发现了一条回路

{

for(i=0;path[i]!=w;i++); //找到回路的起点

for(j=0;path[i+j];i++) thiscycle[j]=path[i+j];//把回路复制下来

第 85 页 共 124 页

if(!exist_cycle()) cycles[cycount++]=thiscycle;//如果该回路尚未被记录过,就添加到记录中 for(i=0;i<G.vexnum;i++) thiscycle[i]=0; //清空目前回路数组

}//else

}//for

path[k]=0;

visited[k]=0; //注意只有当前路径上的结点visited 为真.因此一旦遍历中发现当前结点visited 为真,即表示发现了一条回路

}//DFS

int exist_cycle()//判断thiscycle 数组中记录的回路在cycles 的记录中是否已经存在

{

int temp[MAXSIZE];

for(i=0;i<cycount;i++) //判断已有的回路与thiscycle 是否相同

{ //也就是,所有结点和它们的顺序都相同

j=0;c=thiscycle&#0;; //例如,142857 和857142 是相同的回路

第一个结点的元素

if(cycles[i][k]) //有与之相同的一个元素

{

for(m=0;cycles[i][k+m];m++)

temp[m]=cycles[i][k+m];

for(n=0;n<k;n++,m++)

temp[m]=cycles[i][n]; //调整cycles 中的当前记录的循环相位并放入temp 数组中 if(!StrCompare(temp,thiscycle)) //与thiscycle 比较

return 1; //完全相等

for(m=0;m<G.vexnum;m++) temp[m]=0; //清空这个数组

}

}//for

return 0; //所有现存回路都不与thiscycle 完全相等

}//exist_cycle

分析:这个算法的思想是,在遍历中暂存当前路径,当遇到一个结点已经在路径之中时就表明

存在一条回路;扫描路径向量path 可以获得这条回路上的所有结点.把结点序列(例如,142857) 严蔚敏《数据结构习题集》解答

第 86 页 共 124 页

存入 thiscycle 中;由于这种算法中,一条回路会被发现好几次,所以必须先判断该回路是否已 经在cycles 中被记录过,如果没有才能存入cycles 的一个行向量中.把cycles 的每一个行向量 取出来与之比较.由于一条回路可能有多种存储顺序,比如 142857 等同于285714 和571428, 所以还要调整行向量的次序,并存入temp 数组,例如,thiscycle 为142857 第一个结点为1,cycles 的当前向量为857142,则找到后者中的1,把1 后部分提到1 前部分前面,最终在temp 中得到

142857,与thiscycle 比较,发现相同,因此142857 和857142 是同一条回路,不予存储.这个算法 太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法.

7.31

int visited[MAXSIZE];

int finished[MAXSIZE];

int count; //count 在第一次深度优先遍历中用于指示finished 数组的填充位置

void Get_SGraph(OLGraph G)//求十字链表结构储存的有向图G 的强连通分量

{

count=0;

for(v=0;v<G.vexnum;v++) visited[v]=0;

for(v=0;v<G.vexnum;v++) //第一次深度优先遍历建立finished 数组

if(!visited[v]) DFS1(G,v);

for(v=0;v<G.vexnum;v++) visited[v]=0; //清空visited 数组

for(i=G.vexnum-1;i>=0;i--) //第二次逆向的深度优先遍历

{

v=finished(i);

if(!visited[v])

{

printf("\n"); //不同的强连通分量在不同的行输出

DFS2(G,v);

}

}//for

}//Get_SGraph

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

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