求關(guān)鍵路徑設(shè)計報告 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計畢業(yè)設(shè)計word格式-文庫吧
2024-11-12 06:44 本頁面
【正文】 圖類型 ／／以下為堆棧結(jié)構(gòu) typedef struct { int *base,*top。 ／／棧底和棧頂 int stacksize。 ／／棧的大小 }Sqstack。 ／／棧的類型 圖的基本操作： void Creat_ALGraph(ALGraph amp。G)； ／／創(chuàng)建一個帶權(quán)的有向圖。 void DFS(ALGraph amp。G,int v)。 ／／從ｖ點深度遍歷圖。 void DFSTraverse(ALGraph amp。G)； ／／深度遍歷圖。 void FindIngree(ALGraph G,int b[20])； ／／求圖每個頂點的入度 void FindIngree(ALGraph G,int b[20])； 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 5 ／／對圖進行拓撲排序。 int TopologicalOrder(ALGraph G,Sqstack amp。T)； ／／若Ｇ無回路，則用棧Ｔ返回Ｇ的一個拓撲排序列，且函數(shù)值為１，否則為０； void Criticalpath(ALGraph amp。G)； ／／Ｇ為有向圖，輸出圖的關(guān)鍵路徑。 棧的基本操作： void Inist_stack(Sqstack amp。S)； ／／初始化棧。 int StackEmpty(Sqstack amp。S)； ／／ 判斷棧是否為空 。 void push(Sqstack amp。S,int a)； ／／ 入棧 。 int pop(Sqstack amp。S)； ／／ 出棧 。 ２ .主程序和其他偽代碼算法 void main() { //主程序 ALGraph G。 //定義一個圖 Creat_ALGraph(G)。 //創(chuàng)建一個帶權(quán)的有向無環(huán)圖 DFSTraverse(G)。 //深度優(yōu)先遍歷 TopologicalSort(G)。 //拓撲排序 Criticalpath(G)。 //求關(guān)鍵路徑 }//main void Creat_ALGraph(ALGraph amp。G) { //創(chuàng) 建一個鄰接表結(jié)構(gòu)的圖 cin。 //輸入頂點數(shù) cin。 //輸入邊數(shù) for(int i=0。i。++i) { [i].data=i。 [i].firstarc=NULL。 } //頂點初始化 Arode *p。 //定義一個結(jié)點指針 p for(int j=0。j。++j) { int v,w,u。 cinvwu。 //輸入帶權(quán)的邊 p=new Arode。 padjvex=w。 pinfo=u。 pnextarc=[v].firstarc。 [v].firstarc=p。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 6 } }//Creat_ALGraph void Inist_stack(Sqstack amp。S) { //初始化棧 =new int(MAX)。 //為棧分配一個 MAX 大的空間 =。 //棧頂?shù)扔跅５? =MAX。 //棧的大小 }//Inist_stack int StackEmpty(Sqstack amp。S) { //判斷棧是否為空 if(==) //棧頂?shù)扔跅５?，則為空，返回 0； return 0。 else return 1。 //否則返回 1； }//StackEmpty void push(Sqstack amp。S,int a) { //把元素 a 放入棧 if() //棧沒有滿 { *=a。 ++。 } else //棧已滿 在分配空間 *=a。 ++。 }//push int pop(Sqstack amp。S) { //返回棧頂?shù)闹? if(!=) //棧不為空 { 。 return *。 } }//pop void DFS(ALGraph amp。G,int v) { //從第 v 個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖 G visited[v]=1。 //已被訪問 coutv 。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 7 Arode *q。 for(q=[v].firstarc。q。q=qnextarc) { int u。 u=qadjvex。 if(!visited[u])DFS(G,u)。 } }//DFS void DFSTraverse(ALGraph amp。G) { //深度優(yōu)先遍歷圖 G for(int i1=0。i1。++i1) { visited[i1]=0。 //把所有頂點表示成未訪問 } for(int j1=0。j1。++j1) { if(!visited[j1])DFS(G,j1)。 //沒有訪問就調(diào)用函數(shù) DFS } }//DFSTraverse void FindIngree(ALGraph G,int b[20]) { //計算圖中每個頂點的入度 for(int j=0。j20。++j) { b[j]=0。 //把數(shù)組全部置零 } for(int i=0。i。++i) { Arode *p。 //定義一個結(jié)點指針 for(p=[i].firstarc。p。p=pnextarc) { ++b[padjvex]。 //各點入度加一 } } }//FindIngree void TopologicalSort(ALGraph am
公司管理相關(guān)推薦
鄂ICP備17016276號-1