图的邻接表以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM];

typedef char StrARR[100][MAX_VERTEX_NUM+1]; typedef char VertexType; typedef struct ArcNode { int adjvex;

struct ArcNode *nextarc; } ArcNode;

typedef struct VNode { VertexType data; ArcNode *firstarc;

} VNode, AdjList[MAX_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' */

void 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); visited[j]=1; A[d++]=sv;

if(sv==tv) { m=0;

for(n=0;n

for(p=g.vertices[j].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

AllPath2(g,g.vertices[l].data,tv,path,i,d,A); }

visited[j]=0;

d--; }

void AllPath(ALGraph g, VertexType sv, VertexType tv, StrARR &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 A[MAX_VERTEX_NUM],B[MAX_VERTEX_NUM]; for(l=0;l<5;l++) {

strcpy(B,path[l]);

for(j=0;j

AllPath2(g,sv,tv,path,i,d,A); }

7.31③ 试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。

实现下列函数：

void StronglyConnected(OLGraph dig, StrARR &scc, int &n); /* Get all the strongly connected components in the digraph dig, */ /* and put the ith into scc[i] which is a string. */

图的十字链表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; int finished[MAX_VERTEX_NUM];

typedef char StrARR[MAX_VERTEX_NUM][MAX_VERTEX_NUM+1]; // 记录各强连通分量 typedef struct ArcBox { int tailvex,headvex;

struct ArcBox *hlink,*tlink; } ArcBox;

typedef struct VexNode { VertexType data;

ArcBox *firstin,*firstout; } VexNode;

typedef struct {

VexNode xlist[MAX_VERTEX_NUM]; int vexnum, arcnum; } OLGraph;

int count;

void DFS1(OLGraph dig,int v);

void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k);

void StronglyConnected(OLGraph dig, StrARR &scc, int &n) /* Get all the strongly connected components in the digraph dig, */ /* and put the ith into scc[i] which is a string. */ {

int i,k=0,v; count=0;

for(v=0;v

for(v=0;v

for(i=dig.vexnum-1;i>=0;i--) {

v=finished[i]; if(!visited[v]) {

DFS2(dig,v,scc,n,k);

n++; } } }

void DFS1(OLGraph dig,int v) {

int w;

ArcBox *p; visited[v]=1;

for(p=dig.xlist[v].firstout;p;p=p->tlink) { w=p->headvex;

if(!visited[w]) DFS1(dig,w); }

finished[count++]=v; }

void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k) {

int w;

ArcBox *p; visited[v]=1;

scc[j][k++]=dig.xlist[v].data;

for(p=dig.xlist[v].firstin;p;p=p->hlink) {

w=p->tailvex; if(!visited[w])

DFS2(dig,w,scc,j,k); } }

7.29⑤ 试写一个算法，在以邻接矩阵方式存储的 有向图G中求顶点i到顶点j的不含回路的、长度为k 的路径数。

实现下列函数：

int SimplePath(MGraph G, int i, int j, int k);

/* 求有向图G的顶点i到j之间长度为k的简单路径条数 */

图的邻接矩阵存储结构的类型定义如下：

typedef enum {DG,DN,AG,AN} GraphKind; // 有向图,有向网,无向图,无向网

typedef struct {

VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； // 对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针(可无)

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {

AdjMatrix arcs; // 邻接矩阵

VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 int vexnum,arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 }MGraph;

int SimplePath(MGraph G, int i, int j, int k)

/* 求有向图G的顶点i到j之间长度为k的简单路径条数 */ {

int sum=0,v;

if( G.arcs[i][j].adj &&k==1 && !visited[j])

sum=1; else

if(k>1)

{ visited[i]=1;

for(v=0;v

if(G.arcs[i][v].adj && !visited[v])

sum+=SimplePath(G,v,j,k-1); }

visited[i]=0; }

return sum; }

实现下列函数：

int Search(SSTable s, KeyType k); /* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */

静态查找表的类型SSTable定义如下： typedef struct { KeyType key;

... ... // 其他数据域 } ElemType;

typedef struct {

ElemType *elem; int length; } SSTable;

int Search(SSTable a, KeyType k)

/* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */ {

int i;

for(i=1;i<=a.length;i++)

if(a.elem[i].key==k)return i; return 0; }