數(shù)據(jù)結(jié)構(gòu)作業(yè)系統(tǒng)第七章答案(參考版)
2025-06-25 15:17本頁面
【正文】 return 0。i=。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。 int length。 ... ... // 其他數(shù)據(jù)域} ElemType。}實現(xiàn)下列函數(shù)：int Search(SSTable s, KeyType k)。 } visited[i]=0。amp。v。 else if(k1) { visited[i]=1。amp。amp。int SimplePath(MGraph G, int i, int j, int k)/* 求有向圖G的頂點i到j(luò)之間長度為k的簡單路徑條數(shù) */{ int sum=0,v。 // 圖的當(dāng)前頂點數(shù)和弧數(shù) GraphKind kind。 // 鄰接矩陣 VertexType vexs[MAX_VERTEX_NUM]。 // 該弧相關(guān)信息的指針(可無)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 // 頂點關(guān)系類型。/* 求有向圖G的頂點i到j(luò)之間長度為k的簡單路徑條數(shù) */圖的鄰接矩陣存儲結(jié)構(gòu)的類型定義如下：typedef enum {DG,DN,AG,AN} GraphKind。 }}⑤ 試寫一個算法，在以鄰接矩陣方式存儲的有向圖G中求頂點i到頂點j的不含回路的、長度為k的路徑數(shù)。p=phlink) { w=ptailvex。 for(p=[v].firstin。 visited[v]=1。scc,int j,int k) { int w。 } finished[count++]=v。p=ptlink) { w=pheadvex。 for(p=[v].firstout。 ArcBox *p。 n++。i) { v=finished[i]。 for(i=。v。v++) if(!visited[v]) DFS1(dig,v)。 for(v=0。n)/* Get all the strongly connected ponents in the digraph dig, *//* and put the ith into scc[i] which is a string. */{ int i,k=0,v。void StronglyConnected(OLGraph dig, StrARR amp。void DFS2(OLGraph dig,int v,StrARR amp。int count。 int vexnum, arum。} VexNode。typedef struct VexNode { VertexType data。 struct ArcBox *hlink,*tlink。typedef char StrARR[MAX_VERTEX_NUM][MAX_VERTEX_NUM+1]。/* Get all the strongly connected ponents in the digraph dig, *//* and put the ith into scc[i] which is a string. */圖的十字鏈表以及相關(guān)類型和輔助變量定義如下：Status visited[MAX_VERTEX_NUM]。scc, int amp。 }③ 試完成求有向圖的強連通分量的算法，并分析算法的時間復(fù)雜度。j++) depath(path[l],B[j])。 for(j=0。l5。 VertexType A[MAX_VERTEX_NUM],B[MAX_VERTEX_NUM]。path, int amp。 d。 if(!visited[l]) AllPath2(g,[l].data,tv,path,i,d,A)。p。 i++。nd。 if(sv==tv) { m=0。 visited[j]=1。 ArcNode *p。i,int amp。 */void AllPath2(ALGraph g, VertexTy
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1