数据结构作业系统第七章答案计算机数据结构与算法_计算机-数据结构与算法.pdf

《数据结构作业系统第七章答案计算机数据结构与算法_计算机-数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《数据结构作业系统第七章答案计算机数据结构与算法_计算机-数据结构与算法.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶 点 vi 到顶点 vj 的路径(i j)。注意：算法中涉及 的图的基本操作必须在此存储结构上实现。实现下列函数：Status DfsReachable(ALGraph g,int i,int j);/*Judge if it exists a path from vertex i to */*vertex j in digraph g.*/*Array visited has been initialed to false.*/图的邻接表以及相关类型和辅助变量定义如下：Status visitedMAX_VERT

2、EX_NUM;typedef char VertexType;typedef struct ArcNode int adjvex;struct ArcNode*nextarc;ArcNode;typedef struct VNode VertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;ALGraph;Status DfsReachable(ALGraph g,int i,int j)/*Judge if it exists

3、a path from vertex i to */*vertex j in digraph g.*/*Array visited has been initialed to false.*/int k;ArcNode*p;visitedi=1;for(p=i.firstarc;p;p=p-nextarc)if(p)k=p-adjvex;if(k=j)return 1;if(visitedk!=1)if(DfsReachable(g,k,j)return 1;return 0;同题要求。试基于图的广度优先搜索策略写一算法。实现下列函数：Status BfsReachable(ALGraph g

4、,int i,int j);/*Determine whether it exists path from vertex i to*/*vertex j in digraph g with Breadth_First Search.*/*Array visited has been initialed to false.*/图的邻接表以及相关类型和辅助变量定义如下：Status visitedMAX_VERTEX_NUM;typedef char VertexType;typedef struct ArcNode int adjvex;struct ArcNode*nextarc;ArcNod

5、e;typedef struct VNode VertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;ALGraph;Status InitQueue(Queue&q);Status EnQueue(Queue&q,int e);Status DeQueue(Queue&q,int&e);Status QueueEmpty(Queue q);Status GetFront(Queue q,int&e);Status BfsRea

6、chable(ALGraph g,int i,int j)/*Determine whether it exists path from vertex i to*/*vertex j in digraph g with Breadth_First Search.*/*Array visited has been initialed to false.*/Queue q;中涉及的图的基本操作必须在此存储结构上实现实现下列函数图的邻接表以及相关类型和辅助变量定义如下同题要求试基于图的广度优先搜索策略写一算法实现下列函数图的邻接表以及相关类型和辅助变量定义如下试利用栈的基本一种抽象的数据类型实现下列

7、函数图以及相关类型函数和辅助变量定义如下图的邻接表以及相关类型函数和辅助变量定义如下已知有向图和图中两个顶点和试编写算法求有向图中从到的所有简单路径实现下列函数图的邻接表以及相十字链表以及相关类型和辅助变量定义如下试写一个算法在以邻接矩阵方式存储的有向图中求顶点到顶点的不含回路的长度为的路径数实现下列函数求有向图的顶点到之间长度为的简单路径条数图的邻接矩阵存储结构的类型定义如 int k,n;ArcNode*p;InitQueue(q);EnQueue(q,i);while(!QueueEmpty(q)DeQueue(q,k);visitedk=1;for(p=k.firstarc;p;p=p

8、-nextarc)n=p-adjvex;if(n=j)return 1;if(visitedn!=1)EnQueue(q,n);return 0;试利用栈的基本操作编写，按深度优先搜索策略 遍历一个强连通图的非递归形式的算法。算法中不规定具 体的存储结构，而将图 Graph 看成是一种抽象的数据类型。实现下列函数：void Traverse(Graph dig,VertexType v0,void(*visit)(VertexType);/*Travel the digraph dig with Depth_First Search.*/图以及相关类型、函数和辅助变量定义如下：Status v

9、isitedMAX_VERTEX_NUM;int LocateVex(Graph g,VertexType v);VertexType GetVex(Graph g,int i);int FirstAdjVex(Graph g,int v);int NextAdjVex(Graph g,int v,int w);void visit(char v);Status InitStack(SStack&s);Status Push(SStack&s,SElemType x);Status Pop(SStack&s,SElemType&x);Status StackEmpty(SStack s);St

10、atus GetTop(SStack s,SElemType&e);void Traverse(Graph dig,VertexType v0,void(*visit)(VertexType)int i,v,flag;SStack s;VertexType p;*/中涉及的图的基本操作必须在此存储结构上实现实现下列函数图的邻接表以及相关类型和辅助变量定义如下同题要求试基于图的广度优先搜索策略写一算法实现下列函数图的邻接表以及相关类型和辅助变量定义如下试利用栈的基本一种抽象的数据类型实现下列函数图以及相关类型函数和辅助变量定义如下图的邻接表以及相关类型函数和辅助变量定义如下已知有向图和图中两个顶

11、点和试编写算法求有向图中从到的所有简单路径实现下列函数图的邻接表以及相十字链表以及相关类型和辅助变量定义如下试写一个算法在以邻接矩阵方式存储的有向图中求顶点到顶点的不含回路的长度为的路径数实现下列函数求有向图的顶点到之间长度为的简单路径条数图的邻接矩阵存储结构的类型定义如图的邻接表以及相关类型、函数和辅助变量定义如下：Status visitedMAX_VERTEX_NUM;typedef char StrARR100MAX_VERTEX_NUM+1;typedef char VertexType;typedef struct ArcNode int adjvex;struct ArcNode

12、*nextarc;ArcNode;typedef struct VNode VertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;ALGraph;int LocateVex(Graph g,VertexType v);void inpath(char*&path,VertexType v);/*Add vertex v to path*/void depath(char*&path,VertexType v);/*Remove

13、 vertex v from path*/Status SinglePath(ALGraph g,VertexType sv,VertexType tv,int k,char*sp)/*Judge whether it exists a path from sv to tv with length k*/*in graph g,return path using string sp if exists.*/int i,j,l;ArcNode*p;if(sv=tv&k=0)inpath(sp,tv);return OK;else i=LocateVex(g,sv);visitedi=1;inpa

14、th(sp,sv);for(p=i.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl)中涉及的图的基本操作必须在此存储结构上实现实现下列函数图的邻接表以及相关类型和辅助变量定义如下同题要求试基于图的广度优先搜索策略写一算法实现下列函数图的邻接表以及相关类型和辅助变量定义如下试利用栈的基本一种抽象的数据类型实现下列函数图以及相关类型函数和辅助变量定义如下图的邻接表以及相关类型函数和辅助变量定义如下已知有向图和图中两个顶点和试编写算法求有向图中从到的所有简单路径实现下列函数图的邻接表以及相十字链表以及相关类型和辅助变量定义如下试写一个算法在以邻接矩阵方式

15、存储的有向图中求顶点到顶点的不含回路的长度为的路径数实现下列函数求有向图的顶点到之间长度为的简单路径条数图的邻接矩阵存储结构的类型定义如 if(SinglePath(g,l.data,tv,k-1,sp)return OK;else depath(sp,l.data);visitedi=0;已知有向图和图中两个顶点 u 和 v，试编写算法求 有向图中从 u 到 v 的所有简单路径。实现下列函数：void AllPath(ALGraph g,VertexType sv,VertexType tv,StrARR&path,int&i);/*Get all the paths from vertex

16、 sv to tv,save them*/*into Array path which contains string components.*/*Return the number of path using i */图的邻接表以及相关类型、函数和辅助变量定义如下：Status visitedMAX_VERTEX_NUM;typedef char StrARR100MAX_VERTEX_NUM+1;typedef char VertexType;typedef struct ArcNode int adjvex;struct ArcNode*nextarc;ArcNode;typedef s

17、truct VNode VertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;ALGraph;int LocateVex(Graph g,VertexType v);void inpath(char*path,VertexType v);/*Add vertex v to path*/void depath(char*path,VertexType v);/*Remove vertex v from path*/中涉及的图的基

18、本操作必须在此存储结构上实现实现下列函数图的邻接表以及相关类型和辅助变量定义如下同题要求试基于图的广度优先搜索策略写一算法实现下列函数图的邻接表以及相关类型和辅助变量定义如下试利用栈的基本一种抽象的数据类型实现下列函数图以及相关类型函数和辅助变量定义如下图的邻接表以及相关类型函数和辅助变量定义如下已知有向图和图中两个顶点和试编写算法求有向图中从到的所有简单路径实现下列函数图的邻接表以及相十字链表以及相关类型和辅助变量定义如下试写一个算法在以邻接矩阵方式存储的有向图中求顶点到顶点的不含回路的长度为的路径数实现下列函数求有向图的顶点到之间长度为的简单路径条数图的邻接矩阵存储结构的类型定义如 voi

19、d AllPath2(ALGraph g,VertexType sv,VertexType tv,StrARR&path,int&i,int&d,VertexType A)int j,k,l,m,n;ArcNode*p;j=LocateVex(g,sv);visitedj=1;Ad+=sv;if(sv=tv)m=0;for(n=0;nnextarc)l=p-adjvex;if(!visitedl)AllPath2(g,l.data,tv,path,i,d,A);visitedj=0;d-;void AllPath(ALGraph g,VertexType sv,VertexType tv,St

20、rARR&path,int&i)/*Get all the paths from vertex sv to tv,save them*/*into Array path which contains string components.*/*Return the number of path using i */int d=0,j,l;VertexType AMAX_VERTEX_NUM,BMAX_VERTEX_NUM;for(l=0;l5;l+)strcpy(B,pathl);for(j=0;jstrlen(pathl);j+)depath(pathl,Bj);AllPath2(g,sv,t

21、v,path,i,d,A);中涉及的图的基本操作必须在此存储结构上实现实现下列函数图的邻接表以及相关类型和辅助变量定义如下同题要求试基于图的广度优先搜索策略写一算法实现下列函数图的邻接表以及相关类型和辅助变量定义如下试利用栈的基本一种抽象的数据类型实现下列函数图以及相关类型函数和辅助变量定义如下图的邻接表以及相关类型函数和辅助变量定义如下已知有向图和图中两个顶点和试编写算法求有向图中从到的所有简单路径实现下列函数图的邻接表以及相十字链表以及相关类型和辅助变量定义如下试写一个算法在以邻接矩阵方式存储的有向图中求顶点到顶点的不含回路的长度为的路径数实现下列函数求有向图的顶点到之间长度为的简单路径条

22、数图的邻接矩阵存储结构的类型定义如 试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。实现下列函数：void StronglyConnected(OLGraph dig,StrARR&scc,int&n);/*Get all the strongly connected components in the digraph dig,*/*and put the ith into scci which is a string.*/图的十字链表以及相关类型和辅助变量定义如下：Status visitedMAX_VERTEX_NUM;int finishedMAX_VERTEX_NUM;typ

23、edef char StrARRMAX_VERTEX_NUMMAX_VERTEX_NUM+1;*/int i,k=0,v;count=0;for(v=0;v;v+)if(!visitedv)DFS1(dig,v);for(v=0;v=0;i-)v=finishedi;if(!visitedv)DFS2(dig,v,scc,n,k);n+;void DFS1(OLGraph dig,int v)int w;ArcBox*p;visitedv=1;for(p=v.firstout;p;p=p-tlink)w=p-headvex;if(!visitedw)DFS1(dig,w);finishedco

24、unt+=v;中涉及的图的基本操作必须在此存储结构上实现实现下列函数图的邻接表以及相关类型和辅助变量定义如下同题要求试基于图的广度优先搜索策略写一算法实现下列函数图的邻接表以及相关类型和辅助变量定义如下试利用栈的基本一种抽象的数据类型实现下列函数图以及相关类型函数和辅助变量定义如下图的邻接表以及相关类型函数和辅助变量定义如下已知有向图和图中两个顶点和试编写算法求有向图中从到的所有简单路径实现下列函数图的邻接表以及相十字链表以及相关类型和辅助变量定义如下试写一个算法在以邻接矩阵方式存储的有向图中求顶点到顶点的不含回路的长度为的路径数实现下列函数求有向图的顶点到之间长度为的简单路径条数图的邻接矩阵

25、存储结构的类型定义如void DFS2(OLGraph dig,int v,StrARR&scc,int j,int k)int w;ArcBox*p;visitedv=1;sccjk+=v.data;for(p=v.firstin;p;p=p-hlink)w=p-tailvex;if(!visitedw)DFS2(dig,w,scc,j,k);试写一个算法，在以邻接矩阵方式存储的 有向图 G中求顶点 i 到顶点 j 的不含回路的、长度为 k 的路径数。实现下列函数：int SimplePath(MGraph G,int i,int j,int k);/*求有向图 G的顶点 i 到 j 之间长

26、度为 k 的简单路径条数*/图的邻接矩阵存储结构的类型定义如下：typedef enum DG,DN,AG,AN GraphKind;dj&k=1&!visitedj)sum=1;else if(k1)visitedi=1;for(v=0;v;v+)ifiv.adj&!visitedv)sum+=SimplePath(G,v,j,k-1);visitedi=0;return sum;实现下列函数：int Search(SSTable s,KeyType k);/*Index the element which key is k*/*in StaticSearchTable s.*/*Retur

27、n 0 if x is not found.*/中涉及的图的基本操作必须在此存储结构上实现实现下列函数图的邻接表以及相关类型和辅助变量定义如下同题要求试基于图的广度优先搜索策略写一算法实现下列函数图的邻接表以及相关类型和辅助变量定义如下试利用栈的基本一种抽象的数据类型实现下列函数图以及相关类型函数和辅助变量定义如下图的邻接表以及相关类型函数和辅助变量定义如下已知有向图和图中两个顶点和试编写算法求有向图中从到的所有简单路径实现下列函数图的邻接表以及相十字链表以及相关类型和辅助变量定义如下试写一个算法在以邻接矩阵方式存储的有向图中求顶点到顶点的不含回路的长度为的路径数实现下列函数求有向图的顶点到之

28、间长度为的简单路径条数图的邻接矩阵存储结构的类型定义如 静态查找表的类型 SSTable 定义如下：typedef struct KeyType key;.*/*Return 0 if x is not found.*/int i;for(i=1;i=;i+)ifi.key=k)return i;return 0;中涉及的图的基本操作必须在此存储结构上实现实现下列函数图的邻接表以及相关类型和辅助变量定义如下同题要求试基于图的广度优先搜索策略写一算法实现下列函数图的邻接表以及相关类型和辅助变量定义如下试利用栈的基本一种抽象的数据类型实现下列函数图以及相关类型函数和辅助变量定义如下图的邻接表以及相关类型函数和辅助变量定义如下已知有向图和图中两个顶点和试编写算法求有向图中从到的所有简单路径实现下列函数图的邻接表以及相十字链表以及相关类型和辅助变量定义如下试写一个算法在以邻接矩阵方式存储的有向图中求顶点到顶点的不含回路的长度为的路径数实现下列函数求有向图的顶点到之间长度为的简单路径条数图的邻接矩阵存储结构的类型定义如