【數(shù)據(jù)結(jié)構(gòu)】基于緊縮圖的鄰接表的拓撲排序

1、.東北大學信息科學與工程學院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目 基于緊縮圖的鄰接表的拓撲排序課題組長 宋振課題組成員 常玉穎 于紅爽專業(yè)名稱 計算機科學與技術(shù)班級 計1307指導教師 楊雷2015 年 1月:課程設(shè)計任務(wù)書題目：基于緊縮圖的拓撲排序問題描述：緊縮鄰接表將圖的每個頂點的鄰接表緊湊的存儲在兩個向量list和h中。其中向量list依次存儲頂點0，1，n-1的鄰接頂點。向量單元hi存儲頂點i的鄰接表在向量list中的起始位置。設(shè)計要求：設(shè)計基于緊縮圖的鄰接表的拓撲排序程序。（1）采用STL的圖、棧等數(shù)據(jù)結(jié)構(gòu)。（2）實現(xiàn)STL的緊縮鄰接表結(jié)構(gòu)圖類。（3）實現(xiàn)緊縮圖的鄰接表結(jié)構(gòu)的拓撲排序。指導教師簽

2、字：年月日目錄1 課題概述1.1 課題任務(wù)1.2 課題原理1.3 相關(guān)知識2 需求分析2.1 課題調(diào)研2.2 用戶需求分析3 方案設(shè)計3.1 總體功能設(shè)計3.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計3.3 函數(shù)原型設(shè)計3.4 主算法設(shè)計3.5 用戶界面設(shè)計4 方案實現(xiàn)4.1 開發(fā)環(huán)境與工具4.2 程序設(shè)計關(guān)鍵技術(shù)4.3 個人設(shè)計實現(xiàn)（按組員分工）4.3.1 宋振設(shè)計實現(xiàn)5 測試與調(diào)試5.1 個人測試（按組員分工）5.1.1 宋振測試5.2 組裝與系統(tǒng)測試5.3 系統(tǒng)運行6 課題總結(jié)6.1 課題評價6.2 團隊協(xié)作6.3 團隊協(xié)作6.4 個人設(shè)計小結(jié)（按組員分工）6.4.1 宋振設(shè)計小結(jié)7 附錄A 課題任務(wù)分工A-1

3、課題程序設(shè)計分工A-2 課題報告分工 附錄B 課題設(shè)計文檔（光盤）B-1課程設(shè)計報告（電子版）B-2源程序代碼（*.H，*.CPP）B-3工程與可執(zhí)行文件）B-4屏幕演示錄像文件（可選）附錄C 用戶操作手冊（可選）C.1 運行環(huán)境說明C.2 操作說明1課題概述1.1 課題任務(wù)基于緊縮圖的鄰接表的拓撲排序問題【問題描述】緊縮鄰接表將圖的每個頂點的鄰接表緊湊的存儲在兩個向量list和h中。其中向量list依次存儲頂點0，1，n-1的鄰接頂點。向量單元hi存儲頂點i的鄰接表在向量list中的起始位置。【設(shè)計要求】設(shè)計基于緊縮圖的鄰接表的拓撲排序程序。（1）采用STL的圖、棧等數(shù)據(jù)結(jié)構(gòu)。（2）實現(xiàn)ST

4、L的緊縮鄰接表結(jié)構(gòu)圖類。（3）實現(xiàn)緊縮圖的鄰接表結(jié)構(gòu)的拓撲排序。1.2 課題原理將圖的結(jié)點存入兩個向量之中，List用以存放全部結(jié)點，H用以存放結(jié)點間的相互關(guān)聯(lián)關(guān)系，通過輸入一系列結(jié)點信息及其發(fā)出弧的信息，確定每個結(jié)點的入度，進行拓撲排序序列的輸出。拓撲排序算法bool TopologicalSort(ALGraph G) 中，先輸出入度為零的頂點，而后輸出新的入度為零的頂點，此操作可利用棧實現(xiàn)。該算法大體思想為：遍歷有向圖各頂點的入度，將所有入度為零的頂點入棧；棧非空時，輸出一個頂點，并對輸出的頂點數(shù)計數(shù)；該頂點的所有鄰接點入度減一，若減一后入度為零則入棧；重復、，直到棧為空，若輸出的頂點數(shù)

5、與圖的頂點數(shù)相等則該圖可拓撲排序，否則圖中有環(huán)。1.3相關(guān)知識數(shù)據(jù)結(jié)構(gòu)：棧，拓撲排序。程序語言：C+。STL中的向量模板。2需求分析2.1課題調(diào)研對一個有向無環(huán)圖 G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓撲次序的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。我們小組內(nèi)通過查閱書籍課本和網(wǎng)上資料，了解到拓撲排序的概念。 2.2 用戶需求分析 拓撲排序在大型工程中有廣泛的應(yīng)用拓撲排序常用來確定一個依賴關(guān)系集中，事物發(fā)生的順序

6、。例如，在日常工作中，可能會將項目拆分成A、B、C、D四個子部分來完成，但A依賴于B和D，C依賴于D。為了計算這個項目進行的順序，可對這個關(guān)系集進行拓撲排序，得出一個線性的序列，則排在前面的任務(wù)就是需要先完成的任務(wù)。用戶需求如下：用戶可以通過輸入每個結(jié)點和弧的信息講結(jié)點放入圖中，再通過棧實現(xiàn)拓撲排序序列的輸出；可以在拓撲排序時同時輸出結(jié)點信息；該程序應(yīng)該有對用戶錯誤輸入的辨別糾錯功能；程序應(yīng)具有演示功能和調(diào)試功能；程序應(yīng)具有良好的人機接口。程序應(yīng)能所見即所得的輸入數(shù)據(jù)。這就如同在VS中可視化的開發(fā)圖形界面一樣。程序應(yīng)能精確的輸入數(shù)據(jù)。每一個點的坐標，每條弧的權(quán)值都應(yīng)能由用戶精確控制。程序應(yīng)能友

7、好的展現(xiàn)結(jié)果。程序應(yīng)能顯示制作者的信息。3方案設(shè)計3.1 總體功能設(shè)計第一部分是根據(jù)輸入的邊的信息情況對各個點進行入度統(tǒng)計；第二部分是實現(xiàn)拓撲排序功能設(shè)計的流程圖如下：開始設(shè)輔助數(shù)組indegree記錄圖的各頂點的入度值，并將indegree數(shù)組各變量賦初值。輸入圖的頂點數(shù)、邊數(shù)建立一個棧，存儲圖的頂點的序號用鄰接表法建圖，并計算出indegree數(shù)組中各變量值根據(jù)indegree數(shù)組將入度為0的頂點入棧count對輸出頂點計數(shù)0=>count棧不空刪除棧頂元素,賦給icount+將與第i個頂點鏈接的各頂點入度減1輸出第i個頂點值頂點入度為0頂點序號入棧count<G.vexnum

8、輸出“拓撲排序成功”輸出“拓撲排序不成功”結(jié)束3.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計向量結(jié)構(gòu)，用以存儲結(jié)點順序及關(guān)系；圖類結(jié)構(gòu)，主要用以對用戶輸入的結(jié)點信息進行存儲；棧結(jié)構(gòu)，用來根據(jù)圖的入度機型拓撲排序輸出。3.3 函數(shù)原型設(shè)計函數(shù)原型參數(shù)說明功能描述bool TopologicalSort(Graph v,vector <int> indegree)兩向量存儲的圖v和存儲入度indegree的向量在函數(shù)中實現(xiàn)拓撲排序，返回是否存在環(huán)bool IsDigit(string &str)字符類型的&str判斷str是否為數(shù)字3.4主算法設(shè)計 在建立鄰接表輸入之前，表頭向量的每個結(jié)點的初始

9、狀態(tài)為數(shù)據(jù)域VEX（入度）為零，指針域NXET為空，每輸入一條弧<J,K>建立鏈表的一個結(jié)點，同時令k的入度加1，因此在輸入結(jié)束時，表頭的兩個域分別表示頂點的入度和指向鏈表的第一個結(jié)點指針。   在拓撲排序的過程之中，輸入入度為零（即沒有前趨）的頂點，同時將該頂點的直接后繼的入度減1。 （1） 查鄰接表中入度為零的頂點，并進棧。 （2） 當棧為空時，進行拓撲排序。  退棧，輸出棧頂元素V。  在鄰接表中查找Vj的直接后繼Vk，將Vk的入度減一，并令入度減至零的頂點進棧。 （3）若?？諘r輸出的頂點數(shù)不是N個則說明有

10、向回路，否則拓撲排序結(jié)束。為建立存放入度為零的頂點的棧，不需要另分配存儲單元，即可借入入度為零的數(shù)據(jù)域。一方面，入度為零的頂點序號即為表頭結(jié)點的序號，另一方面，借用入度為零的數(shù)據(jù)域存放帶鏈棧的指針域（下一個入度的頂點號）。3.5 用戶界面設(shè)計本程序使用控制臺DOS設(shè)計:4 方案實現(xiàn)4.1 開發(fā)環(huán)境與工具主要編程環(huán)境：Code:Blocks ，Microsoft Visual Studio C+6.0編程工具：C+。4.2 程序設(shè)計關(guān)鍵技術(shù)基于緊縮圖的拓撲排序：拓撲排序算法bool TopologicalSort(ALGraph G) 中，先輸出入度為零的頂點，而后輸出新的入度為零的頂點，此操作

11、可利用棧實現(xiàn)。該算法大體思想為：遍歷有向圖各頂點的入度，將所有入度為零的頂點入棧；棧非空時，輸出一個頂點，并對輸出的頂點數(shù)計數(shù)；該頂點的所有鄰接點入度減一，若減一后入度為零則入棧；重復、，直到棧為空，若輸出的頂點數(shù)與圖的頂點數(shù)相等則該圖可拓撲排序，否則圖中有環(huán)。4.3 個人設(shè)計實現(xiàn)（按組員分工）4.3.1宋振設(shè)計實現(xiàn)主程序的實現(xiàn)，定義結(jié)構(gòu)體，根據(jù)輸入的信息計算節(jié)點的入度include <iostream>#include <vector>#include <stack>#include <string>#include <stdlib.h&

12、gt;#include <stdio.h>using namespace std;struct Vnode string vernum;struct Graph vector<Vnode>Node; vector<int> List; /存所有節(jié)點信息 vector<int> H; /存i的鄰接節(jié)點 int NodeNum; /節(jié)點數(shù);int main() static int m; Graph v; Vnode n; int num; int countN,i,j; string Node; vector <int> indegre

13、e; Clock *clock=new Clock(); cout<<"當前進行拓撲排序的時間為:"<<*clock<<endl;cout<<"-拓撲排序-"<<endl;cout<<"| |"<<endl;cout<<"| 基于緊縮圖的鄰接表的拓撲排序問題 |"<<endl;cout<<"| |"<<endl; cout<<"| |"

14、;<<endl;cout<<"| 制作人：宋振 常玉穎 于紅爽 |"<<endl;cout<<"| |"<<endl; cout<<"|-請輸入節(jié)點的總數(shù)-|"<<endl; cin>>Node; while(1) if(IsDigit(Node) int b=atoi(Node.c_str(); if(b>0) v.NodeNum=b; break; else cout<<"請重新輸入大于0的數(shù)字"&

15、lt;<endl; else cout<<"請輸入數(shù)字"<<endl; cin>>Node; for(i=0;i<v.NodeNum;i+) string temp; cout<<"請輸入第"<<i+1<<"個節(jié)點的信息"<<endl; cin>>temp; if(temp="0") break; n.vernum=temp; v.Node.push_back(n); num=v.Node.size(); f

16、or(i=0;i<num;i+) string n; cout<<"第"<<i+1<<"條邊所發(fā)出的弧,輸入0結(jié)束該節(jié)點的輸入"<<endl; v.H.push_back(m); for(j=0;j+) bool Numequal=false; cin>>n; if(IsDigit(n) int b=atoi(n.c_str(); if(b<=v.Node.size()&&b>=0) if(b!=i+1) for(countN=v.Hi;countN<v.

17、List.size();countN+) if(v.ListcountN=b-1) Numequal=true; if(!Numequal) if(b=0) break; b-; v.List.push_back(b); m+; else cout<<"輸入重復請重新輸入"<<endl; else cout<<"請重新輸入與本節(jié)點不同的節(jié)點編號"<<endl; else cout<<"請輸入編號小于總結(jié)點數(shù)大于0的節(jié)點編號"<<endl; else cout<

18、;<"請輸入數(shù)字"<<endl; for(i=0;i<v.Node.size();i+) int number=0; for(int j=0;j<v.List.size();j+) if(v.Listj=i) number+; indegree.push_back(number); if(TopologicalSort(v,indegree) cout<<endl; cout<<"正常完成！"<<endl; else cout<<"該有向圖有回路！"<

19、<endl; system("pause"); / 結(jié)束前暫停 return 0;4.3.2常玉穎設(shè)計實現(xiàn)拓撲排序函數(shù)stack <int> s;bool TopologicalSort(Graph v,vector <int> indegree) int i,k,m,n=0; for(i=0;i<indegree.size();i+) if(!indegreei)s.push(i); cout<<"結(jié)果為："<<endl; fopen("result.txt","

20、+w"); while(!s.empty() i = s.top(); s.pop(); cout<<i+1; cout<<"|" cout<<v.Nodei.vernum; if(n!=v.Node.size()-1) cout<<"->" n+; if(i=indegree.size()-1) for(m=v.Hi;m<v.List.size();m+) k=v.Listm; indegreek-; if(!indegreek) s.push(k); else for(m=v.Hi

21、;m<v.Hi+1;m+) k=v.Listm; indegreek-; if(!indegreek) s.push(k); if(n<indegree.size() return false; return true;4.3.3于紅爽設(shè)計實現(xiàn)判斷輸入是否為數(shù)字bool IsDigit(string &str) bool flag=true; for(unsigned int i=0 ;i<str.length();i+) if(!isdigit(stri) flag=false; break; return flag;5 測試與調(diào)試5.1 個人測試（按組員分工）5.

22、1.1宋振個人測試#include <iostream>#include <vector>#include <string>#include <stdlib.h>#include <stdio.h>using namespace std;struct Vnode string vernum;struct Graph vector<Vnode>Node; vector<int> List; vector<int> H; int NodeNum;int main() static int m; clas

23、s Graph v; Vnode n; int num;int i,j,countN; string Node; vector <int> indegree; cout<<"請輸入節(jié)點的總數(shù)"<<endl; cin>>v.NodeNum; for(i=0;i<v.NodeNum;i+) string temp; cout<<"請輸入第"<<i+1<<"個節(jié)點的信息"<<endl; cin>>temp; if(temp=&q

24、uot;0") break; n.vernum=temp; v.Node.push_back(n); num=v.Node.size(); for(i=0;i<num;i+) string n; cout<<"第"<<i+1<<"條邊所發(fā)出的弧,輸入0結(jié)束該節(jié)點的輸入"<<endl; v.H.push_back(m); for(j=0;j+) cin>>n; int b=atoi(n.c_str(); if(b=0) break; b-; v.List.push_back(b);

25、 m+; for(i=0;i<v.Node.size();i+) int number=0; for(j=0;j<v.List.size();j+) if(v.Listj=i) number+; indegree.push_back(number); int q; for(q=0;q<v.H.size();q+) cout<<v.Hq<<endl; for(q=0;q<v.List.size();q+) cout<<v.Listq<<endl; for(q=0;q<v.Node.size();q+) cout<

26、<v.Nodeq.vernum<<endl; for(q=0;q<indegree.size();q+) cout<<indegreeq<<endl; return 0;建圖過程：5.1.2常玉穎個人測試#include <iostream>#include <vector>#include <stack>#include <string>#include <stdlib.h>using namespace std;struct Vnode string vernum;class Gra

27、phpublic:bool TopologicalSort(Graph v,vector <int> indegree);vector<Vnode>Node;vector<int> List;vector<int> H;int NodeNum;bool Graph:TopologicalSort(Graph v,vector <int> indegree)stack <int> s;int i,k,m,n=0;for(i=0;i<indegree.size();i+)if(!indegreei)s.push(i);c

28、out<<"結(jié)果為："<<endl;while(!s.empty()i = s.top();s.pop();cout<<i+1;cout<<"|"cout<<v.Nodei.vernum;if(n!=v.Node.size()-1)cout<<"->"n+; if(i=indegree.size()-1)for(m=v.Hi;m<v.List.size();m+)k=v.Listm;indegreek-;if(!indegreek) s.push(k)

29、; else for(m=v.Hi;m<v.Hi+1;m+)k=v.Listm;indegreek-;if(!indegreek) s.push(k);if(n<indegree.size() return false;return true;int main() static int m; class Graph v; Vnode n; int num;int i,j,countN; string Node; vector <int> indegree; cout<<"節(jié)點的總數(shù)："<<endl; cin>>No

30、de; int b=atoi(Node.c_str(); v.NodeNum=b; for(i=0;i<v.NodeNum;i+) v.Node.push_back(n); num=v.Node.size(); for(i=0;i<num;i+) string n; cout<<"第"<<i+1<<"條邊所發(fā)出的弧,輸入0結(jié)束該節(jié)點的輸入"<<endl; v.H.push_back(m); for(j=0;j+) cin>>n; int b=atoi(n.c_str(); if(b=

31、0) break;b-;v.List.push_back(b); m+; for(i=0;i<v.Node.size();i+) int number=0; for(j=0;j<v.List.size();j+) if(v.Listj=i) number+; indegree.push_back(number); if(v.TopologicalSort(v,indegree) cout<<"正常完成！"<<endl; else cout<<"該有向圖有回路！"<<endl;return 0;通

32、過入度進行拓撲排序，調(diào)試結(jié)果為：5.1.3于紅爽個人調(diào)試輸入 #include <string> #include <cctype> #include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std; bool IsDigit(string &str) bool flag=true; for(unsigned int i=0 i<str.length();i+) if(!isdigit(stri) flag=false; brea

33、k; return flag; int main() string a="123w" string b="1" string c="apple w" if(IsDigit(a) cout<<"yes"<<endl; else cout<<"no"<<endl; if(IsDigit(b) cout<<"yes"<<endl; else cout<<"no"<<e

34、ndl; if(IsDigit(c) cout<<"yes"<<endl; else cout<<"no"<<endl; 判斷123w，1，apple w是否為數(shù)字，結(jié)果如下：5.2 組裝與系統(tǒng)測試將所有的函數(shù)組裝好以后，進行測試，如下表5.2.1所示表5.2.1 二進制堆系統(tǒng)的測試記錄操作名稱具體操作操作結(jié)果和輸出運行程序編譯器運行DOS界面顯示，顯示制作人，同時提示輸入節(jié)點數(shù)輸入節(jié)點總數(shù)用戶根據(jù)自己需求輸入節(jié)點總數(shù)提示用戶輸入節(jié)點信息輸入節(jié)點信息，即每個節(jié)點所代表的的事件用戶根據(jù)自己需求輸入節(jié)點信息提示

35、用戶輸入節(jié)點發(fā)出的弧輸入節(jié)點發(fā)出的弧用戶根據(jù)自己需求輸入節(jié)點的弧統(tǒng)計各個節(jié)點的入度情況進行拓撲排序無若無回路，則輸出拓撲序列，顯示正常完成，若有回路，則輸出該有向圖有回路5.3系統(tǒng)運行總體運行進入界面：輸入節(jié)點數(shù)和節(jié)點信息輸入節(jié)點的弧及輸出拓撲序列6 課題總結(jié)6.1 課題評價按照課題的要求，我們組同學進行了分工，實現(xiàn)了其所規(guī)定的設(shè)計要求，并且有所拓展，運用課本上的知識及學習了一些本來未曾接觸的知識，運用陌生的類模板實現(xiàn)了掌握較為熟練的功能。通過這次的實驗設(shè)計后，大家各方面的能力都有所提高6.2 團隊協(xié)作 由于需要學習新的知識-stl類，在完成項目過程中，我們進行了明確的分工，以確保高效，每個人

36、對新知識的學習，之后匯總，按照所學分配任務(wù)，高效地完成了任務(wù)。6.3 下一步工作 下一步工作就是每個人根據(jù)自己的任務(wù)進行編程調(diào)試，更加透徹的理解拓撲排序，提高一種創(chuàng)新和應(yīng)用的能力。6.4 個人設(shè)計心得（按組員分工）6.4.1宋振設(shè)計小結(jié) 緊縮圖的拓撲排序，這個題目聽起來還蠻簡單的，因為在課上老師講過關(guān)于拓撲排序的相關(guān)知識，就是流程的先后順序，但是對于STL函數(shù)模板庫我們卻一無所知。于是便從各種搜索引擎中查找相關(guān)資料。了解的STL是什么東西，并且了解了它的運行機制之后，我們便開始具體的從中尋找我們能用到的數(shù)據(jù)結(jié)構(gòu)。該實驗讓我收獲頗豐，至少懂得了什么叫STL，還有就是關(guān)于棧的抽象數(shù)據(jù)類型里面有這么

37、多我們可以使用的庫函數(shù)，這為我們以后的編程提供的很大的幫助，提高了我們編程的效率。而且這也提醒我們，以后自己編寫的函數(shù)塊可以當作模板儲存到自己的函數(shù)庫里面，若下次程序設(shè)計有類似的算法，可以直接進行調(diào)用，這回大大提高我們編寫程序的速度。 6.4.2常玉穎設(shè)計小結(jié)通過這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗，我對數(shù)據(jù)結(jié)構(gòu)的算法有了更深的了解，也對以前學過的知識進行了鞏固和提高。在這次實驗過程中，雖然遇到了很多困難和新問題，但是我沒有自暴自棄，一遍遍地調(diào)試程序，并主動地采取查閱課本及網(wǎng)上資料等方法自主學習，解決困難，把以前被動的學習過程變成了主動的探索研究的過程。在以后的學習過程中，我一定會多多實踐，充分利用每一次做實驗的機會，查漏補缺，培養(yǎng)自己編程的能力，養(yǎng)成嚴密周到、一絲不茍的編程習慣。同時，我也要認真地學習