上傳人：1***

認(rèn)證信息

認(rèn)證類(lèi)型：個(gè)人認(rèn)證

認(rèn)證主體：雷**（實(shí)名認(rèn)證）

IP屬地：湖北

IP屬地：湖北 上傳時(shí)間：2021-11-20 格式：DOCX 頁(yè)數(shù)：25 大?。?81.61KB 積分：28 舉報(bào) 版權(quán)申訴

1、武漢理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名： 專(zhuān)業(yè)班級(jí)： 指導(dǎo)教師： 工作單位： 計(jì)算機(jī)科學(xué)系 題 目: 拓?fù)渑判?初始條件：（1）采用鄰接表作為有向圖的存儲(chǔ)結(jié)構(gòu)；（2）給出所有可能的拓?fù)湫蛄小＃?）測(cè)試用例見(jiàn)嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語(yǔ)言版)p48題7.9圖要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）課程設(shè)計(jì)報(bào)告按學(xué)校規(guī)定格式用A4紙打?。〞?shū)寫(xiě)），并應(yīng)包含如下內(nèi)容： 1. 問(wèn)題描述簡(jiǎn)述題目要解決的問(wèn)題是什么。2. 設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)、主要算法設(shè)計(jì)（用類(lèi)C/C+語(yǔ)言或用框圖描述）、測(cè)試用例設(shè)計(jì)；3. 調(diào)試報(bào)告調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的；對(duì)設(shè)計(jì)和編

2、碼的討論和分析。4. 經(jīng)驗(yàn)和體會(huì)（包括對(duì)算法改進(jìn)的設(shè)想）5. 附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測(cè)試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測(cè)試數(shù)據(jù)和運(yùn)行輸出。說(shuō)明：1. 設(shè)計(jì)報(bào)告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績(jī)均為0分。2. 凡拷貝往年任務(wù)書(shū)或課程設(shè)計(jì)充數(shù)者，成績(jī)一律無(wú)效，以0分記。時(shí)間安排：1第17周完成，驗(yàn)收時(shí)間由指導(dǎo)教師指定2驗(yàn)收地點(diǎn)：實(shí)驗(yàn)中心3驗(yàn)收內(nèi)容：可執(zhí)行程序與源代碼、課程設(shè)計(jì)報(bào)告書(shū)。指導(dǎo)教師簽名： 2013年6月14日系主任（或責(zé)任教師）簽名： 年 月 日拓?fù)渑判蚰夸?問(wèn)題描述2具體設(shè)計(jì)2.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)2.2主要算法設(shè)計(jì) 2.2.1拓?fù)渑判虻乃惴傮w

3、設(shè)計(jì)2.2.2將有向圖表示為鄰接表2.2.3拓?fù)渑判蚝瘮?shù)的設(shè)計(jì)2.2.4順序表的運(yùn)算設(shè)計(jì)2.3測(cè)試用例設(shè)計(jì)3調(diào)試報(bào)告 3.1設(shè)計(jì)和編碼的分析3.2調(diào)試過(guò)程問(wèn)題及解決4經(jīng)驗(yàn)與體會(huì)5用戶(hù)使用說(shuō)明6參考文獻(xiàn)7附錄源代碼與運(yùn)行結(jié)果1問(wèn)題描述題目：拓?fù)渑判蛉绻糜邢驁D表示一個(gè)工程，在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊<vi,vj>表示活動(dòng)vi必須先于活動(dòng)vj進(jìn)行，這種有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)，記作AOV網(wǎng)絡(luò)。對(duì)一個(gè)有向無(wú)環(huán)圖G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個(gè)線(xiàn)性序列，使得AOV網(wǎng)絡(luò)中的所有應(yīng)存在前驅(qū)和后繼的關(guān)系都能得到滿(mǎn)足，這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算叫做拓?fù)?/p>

4、排序。在AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，用拓?fù)渑判蚓涂梢耘袛嗑W(wǎng)中是否有環(huán)，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV-網(wǎng)必定不存在環(huán)。進(jìn)行拓?fù)渑判虿襟E如下：1、輸入AOV網(wǎng)絡(luò)即有向圖。令n為頂點(diǎn)個(gè)數(shù)。2、從有向圖上選擇一個(gè)沒(méi)有入度的節(jié)點(diǎn)并輸出。3、從網(wǎng)中刪去該點(diǎn)，同時(shí)刪去從該頂點(diǎn)發(fā)出的全部有向邊。4、重復(fù)上述2，3，直到（1）、全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?。?）、圖中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說(shuō)明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了，這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。要求：（1）、采用鄰接表作為有向圖的存儲(chǔ)結(jié)構(gòu)；（2）、給出所有

5、可能的拓?fù)湫蛄小?具體設(shè)計(jì)2.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本問(wèn)題中，我將采用三種數(shù)據(jù)結(jié)構(gòu)：鄰接表，順序表和數(shù)組。<1>鄰接表：鄰接表是圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，在鄰接表的存儲(chǔ)結(jié)構(gòu)中，圖中的每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)單鏈表。從拓?fù)渑判虻牟襟E個(gè)方法來(lái)看，在整個(gè)排序過(guò)程中需要頻繁地檢查頂點(diǎn)的前驅(qū)以及作刪除頂點(diǎn)和邊的操作、恢復(fù)頂點(diǎn)和頂點(diǎn)前驅(qū)入度的操作。所以，可以采用鄰接表作為有向無(wú)環(huán)圖的存儲(chǔ)結(jié)構(gòu)。為了快速的判斷頂點(diǎn)是否有前驅(qū)，可以在表頭結(jié)點(diǎn)中增加一個(gè)“入度域（into）”用來(lái)指示頂點(diǎn)當(dāng)前的入度。當(dāng)into域的值為0時(shí)，表明該頂點(diǎn)沒(méi)有前驅(qū)，可以加入到結(jié)果序列中。而刪除頂點(diǎn)及以它為起點(diǎn)的邊操作時(shí)，可以通過(guò)把該頂點(diǎn)的所有鄰接點(diǎn)

6、的入度域減一來(lái)完成，恢復(fù)則入度域加一。鄰接表的定義如下：typedef struct ARCNODE /表結(jié)點(diǎn)int adjvex; /鄰接點(diǎn)的位置ARCNODE *nextarc;/指向下一個(gè)結(jié)點(diǎn)ARCNODE; /鄰接表中的結(jié)點(diǎn)類(lèi)型typedef struct VEXNODE /頭結(jié)點(diǎn)int vexdata; /頂點(diǎn)信息int into; /每個(gè)頂點(diǎn)的入度ARCNODE *firstarc; /指向第一個(gè)鄰接結(jié)點(diǎn)VEXNODE,AdjListMAX;/鄰接表的表頭結(jié)點(diǎn)類(lèi)型typedef structAdjList vexs; /表頭結(jié)點(diǎn)數(shù)組int vexnum,arcnum;/頂點(diǎn)數(shù)、邊數(shù)

7、ALGraph; /鄰接表類(lèi)型<2>順序表：在整個(gè)拓?fù)渑判虻倪^(guò)程中，把滿(mǎn)足條件（在此輪中未訪(fǎng)問(wèn)過(guò)visitedi=0以及入度為0）的頂點(diǎn)加入到順序表的末尾，使last加1。當(dāng)一輪排序結(jié)束后，輸出順序表中的排序。接著，是恢復(fù)部分，每恢復(fù)一步，都要把visiti置0并且相應(yīng)的入度加1，把這個(gè)頂點(diǎn)從順序表中刪除，重新加入到圖中，進(jìn)行下一輪的拓?fù)渑判?。鄰接表的順序表定義如下：typedef struct VEXNODE dataMAX;int last;Sequenlist; /順序表類(lèi)型<2>數(shù)組：產(chǎn)生所有的拓?fù)渑判蚴且粋€(gè)遞歸（回溯）過(guò)程。其中，定義的visitedMAX數(shù)組

8、是一個(gè)輔助變量，數(shù)組元素的初值為0，當(dāng)?shù)趇個(gè)頂點(diǎn)被訪(fǎng)問(wèn)后，便置visitedi為1.記錄該頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)。VisitedMAX；2.2主要算法設(shè)計(jì) 2.2.1拓?fù)渑判虻乃惴傮w設(shè)計(jì) 因?yàn)檫@個(gè)課程設(shè)計(jì)題目是讓AOV網(wǎng)絡(luò)產(chǎn)生所有的拓?fù)渑判?，所以我想必然要用到遞歸或者回溯的思想。 考慮到要不斷的對(duì)數(shù)據(jù)進(jìn)行刪除，恢復(fù)，所以考慮了順序表，單鏈表，堆棧，發(fā)現(xiàn)用順序表刪除和插入都很簡(jiǎn)單，好實(shí)施，只要在表尾插入或是刪除即可。在整個(gè)過(guò)程中主要用到三部分：一、從圖中刪除，添加到順序表中；二、遞歸；三、把刪除的頂點(diǎn)和邊恢復(fù)到圖中并從順序表中刪除。首先，在整個(gè)圖中搜索即沒(méi)有被訪(fǎng)問(wèn)過(guò)而且入度為0 的頂點(diǎn)Vi，進(jìn)行拓?fù)?/p>

9、排序。在拓?fù)渑判虻暮瘮?shù)里，首先將這個(gè)頂點(diǎn)加入到順序表中，然后將這個(gè)頂點(diǎn)標(biāo)志為被訪(fǎng)問(wèn)過(guò)，即Visitedi=1。把以這個(gè)頂點(diǎn)為起點(diǎn)的鄰接點(diǎn)的入度均減1.然后，判斷順序表的表長(zhǎng)是否等于圖的頂點(diǎn)數(shù)。如果不相等的話(huà)，則繼續(xù)判斷圖中是否還存在滿(mǎn)足拓?fù)渑判驐l件的頂點(diǎn)，若存在就再次調(diào)用拓?fù)渑判蚝瘮?shù)。接下來(lái)，就是使剛排序過(guò)的頂點(diǎn)Vi的標(biāo)志恢復(fù)到原始狀態(tài)0，每個(gè)以Vi為起點(diǎn)的鄰接點(diǎn)的入度加1，恢復(fù)到原來(lái)的狀態(tài)。把頂點(diǎn)Vi從順序表中刪除。如果，順序表的表長(zhǎng)等于圖的頂點(diǎn)數(shù)，那么就輸出這一種拓?fù)渑判蛐蛄?。?jì)數(shù)器count加1之后，就是采用遞歸，不斷的調(diào)用拓?fù)渑判蚝瘮?shù)，不斷的恢復(fù)、刪除，直到排出所有的拓?fù)湫蛄小?最后，

10、如果count大于0的話(huà)，那么就輸出有count種拓?fù)渑判?。否則，輸出此圖不是AOV網(wǎng)，無(wú)拓?fù)渑判蛐蛄挟a(chǎn)生。開(kāi)始置空順序表A，表長(zhǎng)賦初值0用鄰接表建立圖G，調(diào)用G=creat_AdjlistGraph();或者 i賦初值0初始化標(biāo)志數(shù)組，visitedi置0i的值遞增1i<G.頂點(diǎn)數(shù)?J賦初值0Visitedj=0且Vj入度為0？調(diào)用函數(shù)Topusort(G, L, i);j的值遞增1j<G.頂點(diǎn)數(shù)？Count > 0？此圖不是AOV網(wǎng)，無(wú)拓?fù)渑判蛐蛄薪Y(jié)束YNNY該圖有count種排序YNYN2.2.2將有向圖表示為鄰接表在產(chǎn)生拓?fù)渑判虻乃惴ㄔO(shè)計(jì)中，首先要將有向圖用鄰接表表示

11、，主要流程如下：開(kāi)始定義表頭結(jié)點(diǎn)數(shù)組 al輸入頂點(diǎn)數(shù)n和邊數(shù)e輸入e條邊的起點(diǎn)值j 和終點(diǎn)值 k將Vk的入度加一，并將結(jié)點(diǎn)Vk加入到鏈表中；邊數(shù)從0到e初始化al 的各項(xiàng)值：ali.vexdata=i; o=0; ali.firstarc=NULL;（i=0 to 圖的頂點(diǎn)數(shù)）定義圖 algn = alg.vexnum 頂點(diǎn)數(shù)；e = alg.arcnum 邊數(shù) i賦初值0將al中的值、入度、指針 分別賦給圖alg中數(shù)組vexs的.各值；i的值遞增1i<結(jié)點(diǎn)數(shù)n？NY結(jié)束2.2.3拓?fù)渑判蚝瘮?shù)的設(shè)計(jì)開(kāi)始插入SqLinsert( L, vexsi)標(biāo)志數(shù)visitedi賦初值

12、0Vi 指向第一個(gè)結(jié)點(diǎn)指針PP !=NULL？P 指向頂點(diǎn) VjVj 的入度減 1P 指向鏈表下一結(jié)點(diǎn)順序表長(zhǎng)=頂點(diǎn)數(shù)？輸出Output (L )計(jì)數(shù)器Count加1;K賦初值0調(diào)用函數(shù)Topusort( L, G, k );Visitedk= =0且Vk 入度為0？ K的值遞增1k<頂點(diǎn)數(shù)？NYYNVi 指向的第一個(gè)結(jié)點(diǎn)的指針 PP！=NULL ？P 指向頂點(diǎn) VjVj 的入度加 1P指向鏈表下一結(jié)點(diǎn)調(diào)用刪除函數(shù)SqLdelete( L, vexsi )結(jié)束YN2.2.4順序表的運(yùn)算設(shè)計(jì)開(kāi)始定義順序表 A順序表置空：setnull()表長(zhǎng)L->last+1賦初值0插入：SqLin

13、sert(L,vexsi)刪 除：SqLdelete(L,vexsi);輸出：output(L);表長(zhǎng)加 1 即L->last+1把結(jié)點(diǎn)X賦給順序表最后一位L->rL->last表長(zhǎng)減 1；L->last-1I賦初值0輸出Vi I的值遞增1i<表長(zhǎng)?結(jié)束NY2.3測(cè)試用例設(shè)計(jì)1234圖11234圖23416752圖3312456 圖4 3調(diào)試報(bào)告 3.1設(shè)計(jì)和編碼的分析 1、鄰接表實(shí)現(xiàn)拓?fù)湫蛄衧hixian()在本函數(shù)里，首先定義一個(gè)順序表，然后把它置空。接著，以鄰接表創(chuàng)建一個(gè)圖，并且把它賦給圖G。接著，把全局變量數(shù)組visited初始化。對(duì)于整個(gè)圖中，沒(méi)被訪(fǎng)問(wèn)過(guò)

14、的而且入度為0的頂點(diǎn)進(jìn)行拓?fù)渑判颉Ｈ绻Ａ縞ount等于0的話(huà)，說(shuō)明圖有回路，不能拓?fù)渑判?。否則，在拓?fù)渑判蚝瘮?shù)中會(huì)輸出所有的拓?fù)渑判蛐蛄?。void shixian() Sequenlist A,*L=&A; L=(Sequenlist *)malloc(sizeof(Sequenlist); Setnull(L); ALGraph G; G=creatGraph(); for(int n=1;n<=G.vexnum;n+) visitedn=0; int i; cout<<"該圖的所有拓?fù)渑判驗(yàn)椋?quot;<<endl; for(i=1;i&

15、lt;=G.vexnum;i+) if(G.o=0)&&(visitedi=0) topusort(L,G,i);if(count<=0)cout<<"您輸入的圖不是有向無(wú)環(huán)圖，故無(wú)拓?fù)渑判蛐蛄挟a(chǎn)生."<<endl;else cout<<"此圖有"<<count<<"種拓?fù)渑判騨n" count=0;2、 鄰接表的主要算法拓?fù)渑判騮opusort()void topusort(Sequenlist *L,ALGraph G,int i)

16、 int j,k; SqLinsert(L,G.vexsi); /把頂點(diǎn)Vi加入到順序表中 P=G.vexsi.firstarc; visitedi=1; /把排序過(guò)的點(diǎn)標(biāo)記 while(P!=NULL) j=P->adjvex; G.o-; /把以Vi為頭的終止結(jié)點(diǎn)入度減1 P=P->nextarc; for(k=1;k<=G.vexnum;k+) if(visitedk=0)&&(G.o=0)/ 如果Vk在此輪中未被訪(fǎng)問(wèn)過(guò)且入度為0 topusort(L,G,k); if(L->last=G.vexnum) /判斷

17、順序表中一種拓?fù)渑判蛲瓿?output(L); cout<<endl; count+; visitedi=0; /使Vi恢復(fù)為未訪(fǎng)問(wèn) while(P!=NULL) j=P->adjvex; G.o+; /使Vj的入度恢復(fù) P=P->nextarc; SqLdelete(L,G.vexsi);3、順序表函數(shù) 在這個(gè)設(shè)計(jì)中，只有順序表的簡(jiǎn)單應(yīng)用，置空，插入，刪除和輸出。插入和刪除都只是在表尾插入和刪除。即只要把表長(zhǎng)加1或是減1.Sequenlist *Setnull(Sequenlist *L)/順序表置空 L->last=0; return(L);

18、void SqLinsert(Sequenlist *L,VEXNODE x)/在順序表尾插入新接點(diǎn) L->last=L->last+1; L->dataL->last=x;void SqLdelete(Sequenlist *L,VEXNODE x)/刪除順序表中的最后一個(gè)節(jié)點(diǎn) L->last=L->last-1;int count=0;void output(Sequenlist *L) /輸出順序表中的元素 int i; for(i=1;i<=L->last;i+) if(i<L->last) cout<<"

19、;V"<<L->datai.vexdata<<"->" else cout<<"V"<<L->datai.vexdata; cout<<endl<<endl;3.2調(diào)試過(guò)程問(wèn)題及解決在調(diào)試的過(guò)程中出現(xiàn)了很多語(yǔ)法錯(cuò)誤，如：開(kāi)始沒(méi)有申明iostream頭文件，導(dǎo)致所有的<<，>>輸入輸出流都是錯(cuò)誤的，還有error C2562: 'main' : 'void' function returning a v

20、alue，發(fā)現(xiàn)main函數(shù)被我定義為了void返回類(lèi)型，可是我在函數(shù)語(yǔ)句里又使用了return 0；把main函數(shù)的返回值改成int即可，還有其他的語(yǔ)法錯(cuò)誤都根據(jù)提示一一改進(jìn)了。接著，我發(fā)現(xiàn)無(wú)論如何輸出的結(jié)果都是零種排序，于是找到了ALGraph creatGraph()函數(shù)的一組賦值語(yǔ)句，開(kāi)始我是這樣寫(xiě)的“G.vexs=al;”后來(lái)改成 for(i=0;i<alg.vexnum;i+) alg.vexsi.vexdata=ali.vexdata;alg.vexsi.indegree=ali.indegree; alg.vexsi.firstarc=ali.firstarc;再次運(yùn)行時(shí)，

21、輸出結(jié)果還是不對(duì)。最后發(fā)現(xiàn)在for語(yǔ)句前少了alg.vexnum=n;alg.arcnum=e;賦值語(yǔ)句。在topusort函數(shù)中下列語(yǔ)句使得運(yùn)行結(jié)果一直為您輸入的圖不是有向無(wú)環(huán)圖，故無(wú)拓?fù)渑判蛐蛄挟a(chǎn)生.for(k=1;k<=G.vexnum;k+) if(visitedk=0)&&(G.o=0)/ 如果Vk在此輪中未被訪(fǎng)問(wèn)過(guò)且入度為0 if(L->last=G.vexnum) /判斷順序表中一種拓?fù)渑判蛲瓿?output(L); cout<<endl; count+; topusort(L,G,k); 改成如下代碼即可：for(k=1

22、;k<=G.vexnum;k+) if(visitedk=0)&&(G.o=0)/ 如果Vk在此輪中未被訪(fǎng)問(wèn)過(guò)且入度為0 topusort(L,G,k); if(L->last=G.vexnum) /判斷順序表中一種拓?fù)渑判蛲瓿?output(L); cout<<endl; count+; 4經(jīng)驗(yàn)與體會(huì)此次課程設(shè)計(jì)為拓?fù)渑判颍胏+語(yǔ)言實(shí)現(xiàn)的，此算法還有多發(fā)面可以改進(jìn)，比如圖的表示利用的是鄰接表，還可以在代碼中增加鄰接矩陣的表示方法，使得對(duì)于兩種形式表示的圖都可以進(jìn)行拓?fù)渑判?，還有在代碼中并沒(méi)有把鄰接表很直觀的輸出給用戶(hù)，如果可以編寫(xiě)

23、代碼把鄰接表很直觀的輸出，會(huì)更有可讀性。在執(zhí)行的過(guò)程中發(fā)現(xiàn)對(duì)于大量的數(shù)據(jù)，比如邊比較復(fù)雜的情況，程序執(zhí)行就有可能會(huì)崩潰，說(shuō)明程序的健壯性還有待提高。通過(guò)五天的課程設(shè)計(jì)，我鞏固了以前學(xué)過(guò)的知識(shí)，懂得了理論與實(shí)際相結(jié)合的重要性，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，理論知識(shí)是為將來(lái)的實(shí)踐服務(wù)的，理論知識(shí)很重要，實(shí)踐活動(dòng)更重要。通過(guò)課程設(shè)計(jì)我看到自己實(shí)際操作能力的嚴(yán)重不足，知識(shí)理解不夠深刻，掌握不夠牢固，編程基礎(chǔ)薄弱，沒(méi)有耐心。在同學(xué)和相關(guān)資料的幫助下，最終完成了代碼。通過(guò)這次設(shè)計(jì)，我看到自身學(xué)習(xí)方法存在很多錯(cuò)誤，我決心在以后的學(xué)習(xí)過(guò)程中，要多鍛煉自己處理實(shí)際問(wèn)題的能力，要提高獨(dú)立分析問(wèn)題和解決問(wèn)題的能力，多動(dòng)

24、手多上機(jī)操作。并且利用假期時(shí)間進(jìn)一步鞏固數(shù)據(jù)結(jié)構(gòu)課程與C+語(yǔ)言基礎(chǔ)，為今后的學(xué)習(xí)打下比較堅(jiān)實(shí)的基礎(chǔ)。5用戶(hù)使用說(shuō)明運(yùn)行后，根據(jù)提示，“請(qǐng)輸入結(jié)點(diǎn)數(shù)”,即輸入圖的頂點(diǎn)數(shù)目，“請(qǐng)入邊總數(shù)數(shù)”，即輸入圖的邊數(shù)；接著依次輸入每條邊的起始點(diǎn)序號(hào)和終止點(diǎn)序號(hào)即可，輸出結(jié)果就可以一目了然。例如：請(qǐng)輸入頂點(diǎn)數(shù)：4請(qǐng)輸入弧數(shù)：4請(qǐng)輸入邊的信息：請(qǐng)輸入第一條邊：1 2請(qǐng)輸入第二條邊：1 3請(qǐng)輸入第三條邊：2 3請(qǐng)輸入第四條邊：3 46參考文獻(xiàn)：1.嚴(yán)蔚敏，吳偉民。 數(shù)據(jù)結(jié)構(gòu)題集(c語(yǔ)言)。 清華大學(xué)出版社，2011年11月。2.殷人昆。 數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC+語(yǔ)言描述)(第2版)。清華大學(xué)出版社，2007

25、年6月7附錄源代碼與運(yùn)行結(jié)果源程序代碼（c+語(yǔ)言）#include <stdio.h>#include <string.h>#include <malloc.h>#include <iostream.h>#define NULL 0#define maxlen 100typedef struct ARCNODE /表結(jié)點(diǎn) int adjvex;/接鄰點(diǎn)的位置 ARCNODE *nextarc;/指向下一個(gè)結(jié)點(diǎn)ARCNODE; /鄰接表中的結(jié)點(diǎn)類(lèi)型typedef struct VEXNODE /頭結(jié)點(diǎn) int vexdata;/頂點(diǎn)的位置 int

26、into; /頂點(diǎn)的入度 ARCNODE *firstarc;/指向第一個(gè)鄰接結(jié)點(diǎn)VEXNODE,AdjListmaxlen;/表頭結(jié)點(diǎn)類(lèi)型typedef struct AdjList vexs;/表頭結(jié)點(diǎn)數(shù)組 int vexnum,arcnum;/頂點(diǎn)數(shù)、邊數(shù)ALGraph;/鄰接表類(lèi)型typedef struct VEXNODE datamaxlen; int last;Sequenlist; /順序表類(lèi)型typedef struct int datamaxlen; int last;Seqlist; /順序表ALGraph creatGraph() int n,e,i,j,k; ARCN

27、ODE *p; AdjList al; cout<<endl; cout<<"-拓?fù)渑判?"<<endl<<endl; cout<<"請(qǐng)輸入結(jié)點(diǎn)數(shù): " cin>>n;for(i=1;i<=n;i+) /初始化表頭結(jié)點(diǎn)數(shù)組 ali.vexdata=i; o=0; ali.firstarc=NULL; cout<<"請(qǐng)輸入邊總數(shù): " cin>>e; cout<<"請(qǐng)依次輸入邊的信息:"&l

28、t;<endl; for(i=1;i<=e;i+) cout<<"請(qǐng)輸入第"<<i<<"條邊:" cin>>j>>k; /依次讀入邊的信息 p=(ARCNODE *)malloc(sizeof(ARCNODE); p->adjvex=k; o+; /把終止結(jié)點(diǎn)的入度加1 p->nextarc=alj.firstarc; /用頭插法把p插入到鏈表中 alj.firstarc=p; cout<<endl; ALGraph alg; alg.vexnu

29、m=n; alg.arcnum=e; for(i=1;i<=alg.vexnum;i+) /把頭結(jié)點(diǎn)表頭數(shù)組的值賦給鄰接表表頭數(shù)組 alg.vexsi.vexdata=ali.vexdata; o=o; alg.vexsi.firstarc=ali.firstarc; return alg;Sequenlist *Setnull(Sequenlist *L)/順序表置空 L->last=0; return(L);void SqLinsert(Sequenlist *L,VEXNODE x)/在順序表尾插入新接點(diǎn) L->last=L-&g

30、t;last+1; L->dataL->last=x;void SqLdelete(Sequenlist *L,VEXNODE x)/刪除順序表中的最后一個(gè)節(jié)點(diǎn) L->last=L->last-1;int count=0;void output(Sequenlist *L) /輸出順序表中的元素 int i; for(i=1;i<=L->last;i+) if(i<L->last) cout<<"V"<<L->datai.vexdata<<"->" else cout<<"V"<<L->datai.vexdata; cout<<endl<<endl;ARCNODE *P;int n;int visitedmaxlen;void topusort(Sequenlist *L,ALGraph G,int i) int j,k; SqLinsert(L,G.vexsi); /把頂點(diǎn)Vi加入到順序表中 P=G.vexsi.firstarc; visitedi=1; /把排序過(guò)的點(diǎn)標(biāo)記 while(P!=NULL) j=P->adjvex; G.