C數(shù)據(jù)結(jié)構(gòu)以鄰接矩陣方式確定有向網(wǎng)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目：以鄰接矩陣方式確定有向網(wǎng)班級:姓名:心口 子:完成日期:一、需求分析1、運(yùn)行環(huán)境(軟、硬件環(huán)境)：處理器：英特爾酷睿(Core) i5-2410M CPU 2.30GHz物理內(nèi)存：2G操作系統(tǒng)：Microsoft Windowns 7開發(fā)環(huán)境：Microsoft Visual Studio 20082、程序所實現(xiàn)的功能：(1)建立并顯示出它的鄰接鏈表；(2)以非遞歸的方式進(jìn)行深度優(yōu)先遍歷，顯示遍歷的結(jié)果,(并隨時顯示棧的入、出情況)；(3)對改圖進(jìn)行拓?fù)渑判颍@示拓?fù)渑判虻慕Y(jié)果，并隨時顯示入度域的變化情況；(4)給出某一確定頂點到所有其他頂點的最短路徑；3、程序的

2、輸入，包含輸入的數(shù)據(jù)格式和說明：(1)輸入節(jié)點數(shù)個數(shù)(2)輸入頂點信息(空格隔開)(3)輸入權(quán)值信息(以弧尾值 弧頭值 權(quán)值信息，空格隔開0 0 0結(jié)束；)4、程序的輸出，程序輸出的形式：(1)鄰接鏈表輸出(2)深度優(yōu)先遍歷輸出 (3)拓?fù)渑判蜉敵?4)最短路徑輸出5、測試數(shù)據(jù)：(1)節(jié)點個數(shù)：5個(2)頂點信息：a b c d e(3)權(quán)值信息：a b 1 b c 2 c d 3 d e 4 a d 5 d c 6 0 0 0二、設(shè)計說明1、算法設(shè)計的思想：建程序主要是通過建立一個圖的模板類來調(diào)用相應(yīng)的構(gòu)造函數(shù)以及相應(yīng)的成員函數(shù)來實現(xiàn)其功能，首先用結(jié)構(gòu)體來存儲邊節(jié)點和頂點節(jié)點， 用鄰接矩陣來

3、 存儲此有向圖，遍歷的過程采用雙從循環(huán)來使得遍歷達(dá)到最底端， 最短路徑采用 了遞歸的思想循環(huán)調(diào)用最短路徑函數(shù)來完成最短路徑的查找， 拓?fù)渑判蛑惺紫葍?yōu) 先輸出入度為零的節(jié)點，然后通過刪除該節(jié)點繼續(xù)此過程進(jìn)行排序。2、主要的數(shù)據(jù)結(jié)構(gòu)設(shè)計說明：圖的鄰接矩陣結(jié)構(gòu)設(shè)計：頂點數(shù)、弧數(shù)、矩陣數(shù)組、和點數(shù)組棧結(jié)構(gòu)：包括棧頂和棧底點結(jié)構(gòu)：包括頂點和弧相關(guān)的指針信息。3、程序的主要流程圖：有向圖輸 出 鄰 接 表最短路徑4、主要模塊和函數(shù)：1、鄰接矩陣創(chuàng)建有向網(wǎng)void CreatGraph(MGraph *g)偽碼：依次存儲節(jié)點數(shù)、頂點信息、權(quán)值2、打印有向網(wǎng)的鄰接矩陣 void PrintGraph(MGra

4、ph *g)偽碼：依次打印鄰接矩陣3、打印有向網(wǎng)的鄰接表void PrintList(MGraph *g)偽碼：輸出矩陣每行不為零值縱坐標(biāo)對應(yīng)的節(jié)點4、非遞歸深度優(yōu)先遍歷void DFSTraverse(MGraph *g)偽碼：1.從右向左依次把鄰接矩陣第一行非零值縱坐標(biāo)對應(yīng)的節(jié)點數(shù)入棧,并 將最后入棧值出棧；.再將最后入棧值定為橫坐標(biāo)，重復(fù)上述操作，直到空；.出棧，重復(fù)第二步操作；.重復(fù)第三部操作，直到?？?；5、獲取每個節(jié)點的入度void FindInDegree ()偽碼：獲取鄰接矩陣每行非零值個數(shù)6、拓?fù)渑判騣nt TopologicalSort(MGraph *g)偽碼：1.先將度為

5、零節(jié)點入棧.出棧，對i號節(jié)點的每個鄰接點入度減1.若入度減為0,則入棧.重復(fù)2, 3步，直至?？?、任意兩點最短距離void ShortestPath_FLOYD(MGraph *g)偽碼：先看兩點之間有無直接路徑，若有，則看有無通過中間點更短若無，則看有無中間點連通三、源程序代碼：#include #include#include/最大頂點個數(shù)/存儲空間初始分配量/存儲空間分配增量using namespace std;#define MAX_VERTEX_NUM 20 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10define O

6、VERFLOW 0define ERROR 0define OK 1define INFINITY 100typedef struct ArcCell/圖的鄰接矩陣結(jié)構(gòu)定義(char adj;/ 頂點int *info;/弧相關(guān)信息指針VertexNode;typedef struct/頂點向量/鄰接矩陣(VertexNode vexsMAX_VERTEX_NUM;int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vexnum,arcnum;/定點數(shù)和弧數(shù)MGraph;typedef struct(int *base; /棧底指針int *top;/棧頂指針in

7、t stacksize;存儲空間SqStack;/*函數(shù)名稱：findnode函數(shù)功能描述：返回結(jié)點在數(shù)組位置函數(shù)調(diào)用之前的預(yù)備條件：定義并賦值結(jié)點數(shù)組返回后的處理：返回值(如果有的話)：int函數(shù)的輸入?yún)?shù)：SqStack &S ,結(jié)點字符函*/int findnode(char a,MGraph *S)(for(int i=1;ivexnum+1);i+)if (S-vexsi.adj =a)return i;return -1;/*函數(shù)名稱：InitStack函數(shù)功能描述：構(gòu)造一個空棧函數(shù)調(diào)用之前的預(yù)備條件：定義鄰接矩陣結(jié)構(gòu)體返回后的處理：返回值(如果有的話)：OVERFLOW或OK函數(shù)

8、的輸入?yún)?shù):SqStack &S函數(shù)的輸出參數(shù)：函數(shù)的抽象算法(偽碼)：存儲分配*/int InitStack(SqStack &S)/ 構(gòu)造一個空棧(S.base = (int *)malloc(STACK_INIT_SIZE *sizeof(int);if(!S.base)/存儲分配失敗return OVERFLOW;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/*函數(shù)名稱：StackEmpty函數(shù)功能描述：判斷棧是否為空棧函數(shù)調(diào)用之前的預(yù)備條件：已構(gòu)造一個棧返回后的處理：返回值(如果有的話)： OK或ERROR函數(shù)的輸入?yún)?shù)：Sq

9、Stack &S函數(shù)的輸出參數(shù)：函數(shù)的抽象算法(偽碼)：棧底與棧頂比較*/int StackEmpty(SqStack &S)(if(S.top=S.base)/ 空棧return OK;elsereturn ERROR;/*函數(shù)名稱：Push函數(shù)功能描述：插入新的棧頂元素函數(shù)調(diào)用之前的預(yù)備條件：已構(gòu)造一個棧返回后的處理：返回值(如果有的話)：OK函數(shù)的輸入?yún)?shù)：SqStack &S,int e函數(shù)的輸出參數(shù)：函數(shù)的抽象算法(偽碼)：指針移動*/int Push(SqStack &S,int e)/ 插入新的棧頂元素(if(S.top-S.base=S.stacksize)/ 棧滿，追加存儲空

10、間S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(int);if(!S.base)/存儲分配失敗return(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/*函數(shù)名稱：GetTop函數(shù)功能描述：獲取的棧頂元素函數(shù)調(diào)用之前的預(yù)備條件：已構(gòu)造一個棧返回后的處理：返回值(如果有的話)：e或ERROR函數(shù)的輸入?yún)?shù)：SqStack &S,int e函數(shù)的輸出參數(shù)：函數(shù)的抽象算法(偽碼)：指針移動*/

11、int GetTop(SqStack &S,int &e)if(S.top=S.base)return ERROR;e=*（S.top-1）;return e;）/*函數(shù)名稱：函數(shù)功能描述：函數(shù)調(diào)用之前的預(yù)備條件:返回后的處理：返回值（如果有的話）：函數(shù)的輸入?yún)?shù)：函數(shù)的輸出參數(shù)：函數(shù)的抽象算法（偽碼）*/Pop刪除棧頂元素已構(gòu)造一個棧eSqStack &S,int &e e:指針移動int Pop(SqStack &S,int &e)if(S.top=S.base)return ERROR;e=*-S.top;return e;)/*/刪除棧頂元素函數(shù)名稱:CreatGraph函數(shù)功能描述：

12、鄰接矩陣創(chuàng)建有向網(wǎng)函數(shù)調(diào)用之前的預(yù)備條件：定義鄰接矩陣結(jié)構(gòu)體返回后的處理：返回值(如果有的話)：函數(shù)的輸入?yún)?shù)：MGraph *g函數(shù)的輸出參數(shù)：函數(shù)的抽象算法(偽碼)：依次存儲節(jié)點數(shù)、頂點信息、權(quán)值*/void CreatGraph(MGraph *g)/鄰接矩陣創(chuàng)建有向網(wǎng)(int i,j,m,o, p;char r1,r2;/m 權(quán)值coutg-vexnum;/ 獲取節(jié)點數(shù)cout請輸入有向網(wǎng)頂點信息(空格間開)：n;for(i=1;ivexnum;i+)/ 獲取頂點信息(cing-vexsi.adj;for(i=1;ivexnum;i+)/ 初始化鄰接矩陣for( j=1;jvexnum

13、;j+)g-arcsij=0;/*cinr1r2m;/權(quán)值信息while(r1!=0&r2!=0&m!=0)/生成鄰接矩陣轉(zhuǎn)o=findnode(r1,g);p=findnode(r2,g);g-arcsop=m;cinr1r2m;函數(shù)名稱:PrintList函數(shù)功能描述:打印有向網(wǎng)的鄰接表函數(shù)調(diào)用之前的預(yù)備條件：已創(chuàng)建有向網(wǎng)CreatGraph返回后的處理:返回值（如果有的話）函數(shù)的輸入?yún)?shù):MGraph *g函數(shù)的輸出參數(shù):g-vexs j.adj函數(shù)的抽象算法（偽碼）：輸出矩陣每行不為零值縱坐標(biāo)對應(yīng)的節(jié)點*/cout請輸入權(quán)值信息（以弧尾值 弧頭值 權(quán)值順序，空格間開，0 0 0結(jié)束）:

14、n;void PrintList(MGraph *g)/ 打印有向網(wǎng)的鄰接表(int i,j;for(i=1;ivexnum;i+)(coutvexsi.adj);for( j=1;jvexnum;j+)(if(g-arcsi j!=0)/ 獲取非零值(coutvexsj.adj);coutNULLn; / 一行結(jié)束，打印空/*函數(shù)名稱：DFSTraverse函數(shù)功能描述：非遞歸深度優(yōu)先遍歷函數(shù)調(diào)用之前的預(yù)備條件：已創(chuàng)建有向網(wǎng)CreatGraph返回后的處理： 返回值（如果有的話）函數(shù)的輸入?yún)?shù)：MGraph *g函數(shù)的輸出參數(shù)：g-vexsi.adj函數(shù)的抽象算法(偽碼)：1.從右向左依次把

15、鄰接矩陣第一行非零值縱坐標(biāo)對應(yīng)的節(jié)點數(shù)入 棧，并將最后入棧值出棧；.再將最后入棧值定為橫坐標(biāo)，重復(fù)上述操作，直到空；.出棧，重復(fù)第二步操作；.重復(fù)第三部操作，直到?？眨?/void DFSTraverse(MGraph *g)/非遞歸深度優(yōu)先遍歷int visitedMAX_VERTEX_NUM,i=1,j,e=1;/visited 標(biāo)記向量，e 出棧值SqStack s;InitStack(s);Push(s,i);/首節(jié)點入棧cout 插入棧頂元素：ni;coutvexsi.adjvexnum;j=1;j-) /(if(g-arcsi j&(visitedj!=1)/ 非零即入棧(Push

16、(s,j);cout插入棧頂元素：jendl;Pop(s,e);/該行最左非零值入棧cout刪除棧頂元素：eendl;if(visitede!=1)/ 未被標(biāo)記(coutvexse.adjendl;visitede=1;/*函數(shù)名稱：FindInDegree數(shù)組中函數(shù)功能描述：獲取每個節(jié)點的入度，并存儲在indegree函數(shù)調(diào)用之前的預(yù)備條件：已創(chuàng)建有向網(wǎng)CreatGraph返回后的處理：返回值（如果有的話）：函數(shù)的輸入?yún)?shù)：MGraph *g函數(shù)的輸出參數(shù)：indegree口函數(shù)的抽象算法（偽碼）：獲取鄰接矩陣每行非零值個數(shù)*/void FindInDegree(MGraph *g,int

17、indegreeMAX_VERTEX_NUM) / 獲取每個節(jié)點的入度，并存儲在indegree數(shù)組中int i,j,n;/n 入度for(i=1;ivexnum;i+)n=0;for( j=1;jvexnum;j+)if(g-arcsji)/每行非零值個數(shù)n+;indegreei=n;/ 存儲入度/*函數(shù)名稱：TopologicalSort函數(shù)功能描述：拓?fù)渑判蚝瘮?shù)調(diào)用之前的預(yù)備條件：已創(chuàng)建有向網(wǎng)CreatGraph ;獲取每個節(jié)點的入度 FindInDegree返回后的處理：返回值（如果有的話）：函數(shù)的輸入?yún)?shù)：MGraph *g函數(shù)的輸出參數(shù)：g-vexsi.adj函數(shù)的抽象算法（偽碼）

18、：1.先將度為零節(jié)點入棧.出棧，對i號節(jié)點的每個鄰接點入度減1.若入度減為0,則入棧.重復(fù)2, 3步，直至?？?/int TopologicalSort(MGraph *g)/ 拓?fù)渑判騣nt indegreeMAX_VERTEX_NUM,i,j,k,count;/count 輸出頂點計數(shù)SqStack S;FindInDegree(g,indegree); / 對各頂點求入度InitStack(S);for(i=1;ivexnum;i+)/ 建立零入度頂點棧if(!indegreei) /入度為零入棧Push(S,i);count=0;while(!StackEmpty(S)Pop(S,i)

19、;coutvexsi.adj;+count;for( j=1;jvexnum;j+) (if(g-arcsi j) (k=j;if(!(-indegreek) Push(S,k);若入coutt 此時vexsk.adj入度：indegreek;度減為零，入棧 if (countvexnum)/ 有回路return ERROR;else return OK;/*函數(shù)名稱:ShortestPath_FLOYD函數(shù)功能描述：任意兩點最短距離函數(shù)調(diào)用之前的預(yù)備條件：已創(chuàng)建有向網(wǎng)CreatGraph返回后的處理：返回值(如果有的話)：函數(shù)的輸入?yún)?shù)：MGraph *g函數(shù)的輸出參數(shù)：disti j函數(shù)的

20、抽象算法(偽碼)：先看兩點之間有無直接路徑，若有，則看有無通過中間點更短 若無，則看有無中間點連通*/void ShortestPath_FLOYD(MGraph *g)/任意兩點最短距離(int distMAX_VERTEX_NUMMAX_VERTEX_NUM;dist口兩點間路徑長度int i,j,k;for(i=1;ivexnum;i+)初始化for( j=1;jvexnum;j+)distij=g-arcsij;for(i=1;ivexnum;i+)(for( j=1;jvexnum;j+)coutvexsi.adjvexsj.adj:t;for(k=1;kvexnum;k+)if(i

21、!=j&i!=k&j!=k)/ 三點互不相同(if(disti j)/ 有直接路徑(if(distik&distkj)j) /有中間更短路徑j(luò);j;/取中間路徑if(disti jdistik+distkdisti j=distik+distk else (if(distik&distkj) disti j=distik+distkcoutdisti jendl;coutendl;void main()/ 主函數(shù)MGraph *g=(MGraph *)malloc(sizeof(MGraph);CreatGraph(g);cout*n鄰接鏈表輸出:n”;PrintList(g);cout*n深

22、度優(yōu)先遍歷:n”;DFSTraverse(g);cout*n拓?fù)渑判?TopologicalSort(g);coutbdMULLbcNULLcdHULLd-eeNULL e-MULL度度 b C此時日入度！ 1研排序IA此-b此五：上機(jī)結(jié)果及體會1、實際完成情況說明：本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，在同學(xué)以及老師的幫助下，完成了實驗題目所要 求的（1）建立并顯示出它的鄰接鏈表；（2）以非遞歸的方式進(jìn)行深度優(yōu)先遍歷， 顯示遍歷的結(jié)果，（并隨時顯示棧的入、出情況）（3）對該圖進(jìn)行拓?fù)渑判?，顯 示拓?fù)渑判虻慕Y(jié)果，并隨時 顯示入度域的變化情況；（4）給出某一確定頂點到所有其他頂點的最短路徑；四個基本功能要求。雖然在算法的選擇上可能還有不 足之處，但總體完成情況和進(jìn)度還行，所以本次課程設(shè)計總體上還是成功的。2、課程設(shè)計遇到的問題及解決方法：.語法錯誤太多，由于大部分函數(shù)都是按照書上的思想進(jìn)行設(shè)計的，思想是沒 問題的，可是書上存在印刷錯誤，語法錯誤比較容易，只需要根據(jù)說明逐個修改 即可，此外還有大括號匹配錯誤。.出現(xiàn)了死循環(huán)，在輸出鄰接表的過程中出現(xiàn)了死循環(huán)，主要是循環(huán)過程中 的條件出現(xiàn)了問題，修改后已經(jīng)解決了，還要注意的是：必須按照輸入格式進(jìn)行輸入，不然也可能出現(xiàn)錯誤。.拓?fù)渑判驎r，剛開時出現(xiàn)錯誤，由于不能利用遞