拓?fù)渑判蛘n程設(shè)計(jì)--拓?fù)渑判蛩惴ǖ难芯颗c實(shí)現(xiàn)

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告</p><p>　　學(xué) 院 計(jì)算機(jī)與通信工程 專 業(yè) 網(wǎng)絡(luò)工程 </p><p>　　班 級(jí) 網(wǎng)絡(luò)1101班 學(xué) 號(hào) </p><p>　　學(xué)生姓名 指導(dǎo)教師 </p><p>　　課

2、程成績(jī) 完成日期 2013年7月12日</p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　拓?fù)渑判蛩惴ǖ难芯颗c實(shí)現(xiàn)</p><p>　　摘 要 該課程設(shè)計(jì)研究AOV網(wǎng)。研究圖的存儲(chǔ)結(jié)構(gòu)，研究AOV網(wǎng)（活動(dòng)在頂點(diǎn)的網(wǎng)，有向網(wǎng)）的存儲(chǔ)結(jié)構(gòu)與輸入算法，并研究拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)方法，在此基

3、礎(chǔ)上對(duì)該算法進(jìn)行分析。通過(guò)對(duì)拓?fù)渑判騿?wèn)題的分析、設(shè)計(jì)、編碼、測(cè)試等工作，掌握針對(duì)實(shí)際應(yīng)用問(wèn)題設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，結(jié)合C語(yǔ)言解決實(shí)際應(yīng)用問(wèn)題的一般方法和過(guò)程，初步掌握利用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際應(yīng)用問(wèn)題的一般方法。</p><p>　　關(guān)鍵字 AOV網(wǎng)；拓?fù)渑判?；算法設(shè)計(jì)；C語(yǔ)言；數(shù)據(jù)結(jié)構(gòu)</p><p><b>　　目錄</b></p><p><b

4、>　　摘要3</b></p><p><b>　　1 引言5</b></p><p>　　1.1 課程設(shè)計(jì)的目的5</p><p>　　1.2 課程設(shè)計(jì)的內(nèi)容6</p><p>　　1.3 課程設(shè)計(jì)的目標(biāo)6</p><p><b>　　2 設(shè)計(jì)內(nèi)容7&

5、lt;/b></p><p>　　2.1 問(wèn)題描述7</p><p>　　2.2 思路分析7</p><p>　　2.3 過(guò)程演示8</p><p>　　3 算法分析及詳細(xì)實(shí)現(xiàn)9</p><p>　　3.1 算法分析9</p><p>　　3.2 算法中用到的函數(shù)聲明

6、9</p><p>　　3.3 部分程序編寫9</p><p>　　4 程序的運(yùn)行環(huán)境及運(yùn)行結(jié)果11</p><p>　　4.1 程序運(yùn)行的環(huán)境11</p><p>　　4.2 運(yùn)行結(jié)果11</p><p><b>　　5 總結(jié)14</b></p><p>

7、　　5.1 課程設(shè)計(jì)總結(jié)14</p><p>　　5.2 心得與體會(huì)14</p><p><b>　　參考文獻(xiàn)15</b></p><p><b>　　附件16</b></p><p><b>　　1 引言</b></p><p>　　課程設(shè)

8、計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí)，發(fā)現(xiàn)，提出，分析和解決實(shí)際問(wèn)題，鍛煉實(shí)踐能力的重要環(huán)節(jié)，是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程。</p><p>　　數(shù)據(jù)結(jié)構(gòu)是學(xué)習(xí)計(jì)算機(jī)相關(guān)專業(yè)的非常重要的知識(shí)，所謂結(jié)構(gòu)就是組織形式，數(shù)據(jù)的結(jié)構(gòu)就是數(shù)據(jù)怎么組織，即怎么描述，怎么在電腦中存儲(chǔ)。不同類型的數(shù)據(jù)，它們的組織形式（數(shù)據(jù)結(jié)構(gòu)）是不同的，在程序設(shè)計(jì)中，除了應(yīng)精心設(shè)計(jì)算法外，還應(yīng)精心組織數(shù)據(jù)（包括原始數(shù)據(jù)、中間結(jié)果 、最終結(jié)果

9、），使之形成一定的組織形式（數(shù)據(jù)結(jié)構(gòu)），以便讓計(jì)算機(jī)盡可能高效率地處理?！稊?shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與工程的基礎(chǔ)研究之一，掌握該領(lǐng)域的知識(shí)對(duì)于我們進(jìn)一步進(jìn)行高效率的計(jì)算機(jī)程序開(kāi)發(fā)非常重要。無(wú)論在中國(guó)還是在美國(guó)，《數(shù)據(jù)結(jié)構(gòu)》一直是大學(xué)的計(jì)算機(jī)專業(yè)重要的專業(yè)基礎(chǔ)課。</p><p>　　數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)要求學(xué)生熟練掌握數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示，具有分析問(wèn)題的能力，可以根據(jù)問(wèn)題選擇合適的數(shù)據(jù)結(jié)構(gòu)，運(yùn)用該數(shù)據(jù)結(jié)構(gòu)結(jié)合相

10、應(yīng)的算法解決實(shí)際問(wèn)題。</p><p>　　1.1 課程設(shè)計(jì)的目的</p><p>　　為了更好的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，深刻理解數(shù)據(jù)結(jié)構(gòu)在解決實(shí)際問(wèn)題中的應(yīng)用，體會(huì)其重要性，熟練掌握線性表、棧和隊(duì)列、串、數(shù)組、樹(shù)、圖等常用的數(shù)據(jù)結(jié)構(gòu)，熟悉各自的特點(diǎn)和應(yīng)用場(chǎng)合。</p><p>　　同時(shí)鍛煉自己獨(dú)立分析理解問(wèn)題的能力，學(xué)會(huì)根據(jù)不同的問(wèn)題選擇合適的數(shù)據(jù)結(jié)構(gòu)，然后結(jié)合適當(dāng)?shù)乃惴?/p>

11、解決問(wèn)題。鍛煉自己的設(shè)計(jì)和編寫程序的技巧，進(jìn)一步調(diào)試和測(cè)試自己所寫的程序，使其功能更加完善，養(yǎng)成較好的編寫程序習(xí)慣。</p><p>　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力[1]，訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際

12、問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能[2]。</p><p>　　1.2 課程設(shè)計(jì)的內(nèi)容</p><p>　　本次課程設(shè)計(jì)要求對(duì)于給定的AOV網(wǎng)求出它所有拓?fù)湫蛄?。AOV網(wǎng)（是一個(gè)有向無(wú)環(huán)圖（Directed Acycline Graph，DAG圖）[3]。AOV網(wǎng)中，如果頂點(diǎn)Vi表示的活動(dòng)在和頂點(diǎn)Vj表示的活動(dòng)之前進(jìn)行，則稱Vi是Vj的前驅(qū)頂點(diǎn)，Vj是Vi后繼頂點(diǎn)

13、。拓?fù)渑判蚓褪菍⒂邢驘o(wú)環(huán)圖中的各個(gè)頂點(diǎn)排成一個(gè)序列，使得所有的前去后繼關(guān)系都得到滿足。對(duì)于相互之間沒(méi)有次序關(guān)系的頂點(diǎn)，在拓?fù)渑判虻男蛄兄锌梢蕴幵谌我獾奈恢?。因此，拓?fù)渑判虻慕Y(jié)果往往是不唯一的。本次課程設(shè)計(jì)的主要任務(wù)就是將給定的一個(gè)AOV網(wǎng)輸出所有的該種序列[4]。</p><p>　　1.3 課程設(shè)計(jì)的目標(biāo)</p><p>　　通過(guò)對(duì)拓?fù)渑判騿?wèn)題的分析、設(shè)計(jì)、編碼、測(cè)試等工作，掌握針對(duì)實(shí)

14、際應(yīng)用問(wèn)題設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，結(jié)合C語(yǔ)言解決實(shí)際應(yīng)用問(wèn)題的一般方法和過(guò)程，初步掌握利用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際應(yīng)用問(wèn)題的一般方法。</p><p><b>　　2 設(shè)計(jì)內(nèi)容</b></p><p><b>　　2.1 問(wèn)題描述</b></p><p>　　在AOV網(wǎng)中為了更好地完成工程，必須滿足活動(dòng)之間先后關(guān)系，需要將各活動(dòng)排一個(gè)先后

15、次序即為拓?fù)渑判?。拓?fù)渑判蚩梢詰?yīng)用于教學(xué)計(jì)劃的安排，根據(jù)課程之間的依賴關(guān)系，制定課程安排計(jì)劃。按照用戶輸入的課程數(shù)，課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系，程序執(zhí)行后會(huì)給出符合拓?fù)渑判虻恼n程安排計(jì)劃。</p><p><b>　　2.2 思路分析</b></p><p>　　一種拓?fù)湫蛄械纳梢话阌幸幌虏襟E：</p><p>　?。?

16、）、從有向無(wú)環(huán)圖中選擇一個(gè)沒(méi)有前驅(qū)結(jié)點(diǎn)的頂點(diǎn)并加入到結(jié)點(diǎn)的序列中；</p><p>　?。?）、從有向無(wú)環(huán)圖中刪除該頂點(diǎn)以及該頂點(diǎn)為尾的所有的??；</p><p>　?。?）、重復(fù)（1）（2）的步驟。</p><p>　　在整個(gè)拓?fù)渑判虻倪^(guò)程中需要頻繁的檢查頂點(diǎn)的前驅(qū)以及作刪除頂點(diǎn)和弧的操作，在這里我們用兩個(gè)全局變量rudu[max_vertex_num]和visi

17、ted[max_vertex_num]來(lái)分別實(shí)現(xiàn)這兩個(gè)操作，如果rudu[i]為零則表示無(wú)前驅(qū)結(jié)點(diǎn)，如果visited[i]為零則表示沒(méi)有被訪問(wèn)過(guò)。如果每刪除一個(gè)結(jié)點(diǎn)就檢查，那樣的話時(shí)間復(fù)雜度將很大（等于遍歷所有的頂點(diǎn)一遍），因此設(shè)計(jì)一個(gè)堆棧，把檢測(cè)到的入度為零的結(jié)點(diǎn)入棧。每次刪除頂點(diǎn)只要從棧中取出一個(gè)結(jié)點(diǎn)即可。</p><p>　　但是如果需要實(shí)現(xiàn)一個(gè)AOV網(wǎng)所有拓?fù)湫蛄械纳蓜t不止如此。在每找到一個(gè)符合要求的

18、結(jié)點(diǎn)后入棧，從而實(shí)現(xiàn)一種拓?fù)渑判颉Ｔ谝惶送負(fù)渑判蚪Y(jié)束后，應(yīng)該進(jìn)行恢復(fù)刪除的結(jié)點(diǎn)和刪除的弧，并標(biāo)記已經(jīng)有過(guò)的序列，在恢復(fù)某幾個(gè)個(gè)結(jié)點(diǎn)后進(jìn)行下一次的拓?fù)渑判颉?lt;/p><p><b>　　2.3 過(guò)程演示</b></p><p>　　該部分給出了算法執(zhí)行的流程，如圖2-1所示。</p><p>　　圖 2-1 算法流程圖</p>&

19、lt;p>　　3 算法分析及詳細(xì)實(shí)現(xiàn)</p><p><b>　　3.1 算法分析</b></p><p>　　首先建立空棧，并從第一個(gè)頂點(diǎn)開(kāi)始進(jìn)行拓?fù)渑判?。將該結(jié)點(diǎn)初始化為被訪問(wèn)過(guò)，并將圖類的結(jié)點(diǎn)指針指向該編號(hào)的結(jié)點(diǎn)的表頭數(shù)組firstarc域，把該頂點(diǎn)入棧后，將所有的以它為起點(diǎn)的弧都刪掉，即將弧的終點(diǎn)的入度都減一。接著判斷棧里面的數(shù)據(jù)個(gè)數(shù)是否和圖頂點(diǎn)的個(gè)數(shù)

20、一樣，如果一樣，則說(shuō)明已經(jīng)有一次拓?fù)渑判蛲瓿桑舨灰粯?，則往下進(jìn)行遞歸，再將符合條件的頂點(diǎn)入棧，直到一次拓?fù)渑判蛲瓿傻臈l件成立。最后將頂點(diǎn)出棧，恢復(fù)所有結(jié)點(diǎn)的入度，并準(zhǔn)備下一趟拓?fù)渑判颉?lt;/p><p>　　3.2 算法中用到的函數(shù)聲明</p><p>　　在該程序中用到了很多函數(shù)，具體聲明如表3-1所示。</p><p>　　表3-1 算法中用到的函數(shù)聲明<

21、;/p><p>　　3.3 部分程序編寫</p><p>　　實(shí)現(xiàn)該算法的具體編碼如下：</p><p>　　void topusort(Stack *L,ALGraph *G,int i){//拓?fù)渑判?lt;/p><p>　　ListNode *P;</p><p>　　int j,k;Soutput(L);</p

22、><p>　　Sinsert(L,i); //把頂點(diǎn)Vi加入到棧中</p><p>　　P=G->head[i].firstarc;</p><p>　　visited[i]=1; //把排序過(guò)的點(diǎn)標(biāo)記</p><p>　　while(P){</p><p>　　j=P->number;&l

23、t;/p><p>　　rudu[j]--; //把以Vi為頭的終止結(jié)點(diǎn)入度減1</p><p>　　P=P->next;</p><p><b>　　}</b></p><p>　　if(L->top+1==G->vexnum){//判斷棧中一種拓?fù)渑判蛲瓿?lt;/p><p>　　S

24、output(L);</p><p>　　printf("\n");</p><p><b>　　flag++;</b></p><p><b>　　}</b></p><p>　　for(k=0;k<G->vexnum;k++)//調(diào)用部分</p>&

25、lt;p>　　if((visited[k]==0)&&(rudu[k]==0))// 如果Vk在此輪中未被訪問(wèn)過(guò)且入度為0</p><p>　　topusort(L,G,k);</p><p>　　visited[i]=0; //使Vi恢復(fù)為未訪問(wèn)</p><p>　　P=G->head[i].firstarc;</p>

26、<p><b>　　while(P)</b></p><p><b>　　{</b></p><p>　　j=P->number;</p><p>　　rudu[j]++; //使Vj的入度恢復(fù) ，加1</p><p>　　P=P->next;</p><

27、p><b>　　}</b></p><p>　　Sdelete(L);</p><p><b>　　}</b></p><p>　　4 程序的運(yùn)行環(huán)境及運(yùn)行結(jié)果</p><p>　　4.1 程序運(yùn)行的環(huán)境</p><p>　　一個(gè)程序需要一個(gè)良好的環(huán)境才能運(yùn)行，該課

28、程設(shè)計(jì)中的程序運(yùn)行的硬件、軟件環(huán)境如下。</p><p><b>　?。?）硬件環(huán)境</b></p><p><b>　　1）學(xué)生用微機(jī)</b></p><p><b>　　2）局域網(wǎng)</b></p><p><b>　?。?）軟件環(huán)境</b></p

29、><p>　　1）Windows 8 旗艦版系統(tǒng)</p><p><b>　　2）VS2010</b></p><p><b>　　4.2 運(yùn)行結(jié)果</b></p><p>　　程序的運(yùn)行結(jié)果將從三個(gè)方面予以介紹。</p><p><b>　?。?）圖的輸入</

30、b></p><p>　　輸入圖，結(jié)果如圖4-1所示。在這里首先輸入頂點(diǎn)數(shù)和邊數(shù)，然后輸入沒(méi)條邊的起點(diǎn)終點(diǎn)編號(hào)和權(quán)值。</p><p>　　圖 4-1 圖的輸入</p><p>　　（2）圖鄰接表的輸出</p><p>　　輸出圖的鄰接矩陣。輸入圖過(guò)后按回車鍵顯示圖的鄰接表，如圖4-2所示。</p><p>　　

31、圖 4-2 圖鄰接表的輸出</p><p>　?。?）拓?fù)湫蛄械妮敵?lt;/p><p>　　在顯示完拓?fù)湫蛄泻蟀椿剀囕敵鲈搱D的所有拓?fù)渑判蛐蛄校鐖D4-3所示。</p><p>　　圖 4-3 拓?fù)湫蛄械妮敵?lt;/p><p><b>　　5 總結(jié)</b></p><p>　　5.1 課程設(shè)計(jì)總結(jié)&

32、lt;/p><p>　　課程設(shè)計(jì)可以檢驗(yàn)學(xué)生對(duì)知識(shí)的掌握程度。同時(shí)更反映了一個(gè)學(xué)生對(duì)課程設(shè)計(jì)的態(tài)度，對(duì)待任何事都要認(rèn)真，可以不會(huì)，可以做的不是最好的，但是一定要盡自己最大的努力去完成一件哪怕再小的事。在這次課程設(shè)計(jì)中學(xué)到了很多新的知識(shí)，同時(shí)也鞏固了之前學(xué)過(guò)知識(shí)。對(duì)靜態(tài)鏈表有了更深的理解，對(duì)哈夫曼樹(shù)及哈夫曼編碼更是印象深刻。雖然，最后根據(jù)要求完成了任務(wù)，但期間還是出現(xiàn)了種種的問(wèn)題，比如在編寫完函數(shù)時(shí)，運(yùn)行結(jié)果總是不對(duì)，

33、調(diào)試了好多遍，也沒(méi)有發(fā)現(xiàn)錯(cuò)誤，沒(méi)有想到是選擇函數(shù)除了差錯(cuò)，一個(gè)簡(jiǎn)單的函數(shù)，怎么也沒(méi)有想到會(huì)是這里出了錯(cuò)，是因?yàn)槲医os1，s2變量賦初值時(shí)出了錯(cuò)誤。同時(shí)，為了更好的完成任務(wù)還查閱了好多資料，不懂的就到處搜索，去圖書(shū)館借相應(yīng)的書(shū)籍來(lái)看，鍛煉了自己查閱資料的能力。</p><p>　　5.2 心得與體會(huì)</p><p>　　我覺(jué)得本此課程設(shè)計(jì)最大的收獲就是學(xué)會(huì)按部就班的完成任務(wù)。首先想好用什么

34、數(shù)據(jù)結(jié)構(gòu)，主要的思想要明確的認(rèn)定。然后選一個(gè)簡(jiǎn)單的例子，按照你選定的思想，一步一步的走程序，才能更早的發(fā)現(xiàn)程序還存在那些沒(méi)有考慮到的缺陷。特別忌諱的是到寫程序的時(shí)候，對(duì)主要思想和數(shù)據(jù)結(jié)構(gòu)還不是很確定。最后在調(diào)試程序的階段，這次我開(kāi)始用設(shè)置斷點(diǎn)的方法，一步一步看是否達(dá)到你要的理想結(jié)果，從而來(lái)找出程序中出錯(cuò)的地方。還有，一種方法也是用一個(gè)輸出語(yǔ)句，分別放在程序的不同位置，通過(guò)輸出結(jié)果，也可以快速判斷出程序不能運(yùn)行的是那一個(gè)語(yǔ)句了。從而方便你

35、修改，快速得到正確的結(jié)果。還有，這次調(diào)試的過(guò)程中，我表現(xiàn)的比以前要更有耐心，這也是一個(gè)很好的收獲。</p><p>　　還有一個(gè)更重要的體會(huì)就是，遇到不會(huì)的地方，我開(kāi)始習(xí)慣到圖書(shū)館或是網(wǎng)上去找資料。這是一個(gè)很好的學(xué)習(xí)過(guò)程，它不僅僅是可以解決這個(gè)問(wèn)題，關(guān)鍵是你會(huì)從找資料學(xué)習(xí)的過(guò)程中，會(huì)學(xué)好很多很多意想不到的知識(shí)?？赡軙?huì)比你手頭上要學(xué)習(xí)的知識(shí)多得多。</p><p><b>　　參考

36、文獻(xiàn)</b></p><p>　　[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京:清華大學(xué)出版社,2012.5[2]李春葆，尹為民.數(shù)據(jù)結(jié)構(gòu)教程上機(jī)指導(dǎo)[M].北京:清華大學(xué)出版社,2008[3]Andrew Binstock，John Rex.程序員實(shí)用算法(第二版)[M].北京:機(jī)械工業(yè)出版社,2009.06[4]Thomas H.Cormen, Charles E.Leiserso

37、n,Ronald L.Riverst, Clfford Stein.Introduction to Alogrithms Second Edition[M].US:Machine Press,2012</p><p><b>　　附件</b></p><p><b>　　程序清單</b></p><p>　　#includ

38、e"stdio.h"</p><p>　　#include"malloc.h"</p><p>　　#include"stdlib.h"</p><p>　　#define max_vertex_num 100 //頂點(diǎn)的最大個(gè)數(shù)</p><p>　　typedef struct n

39、ode{ //鄰接表中的結(jié)點(diǎn)類型</p><p>　　int number; //結(jié)點(diǎn)編號(hào)</p><p>　　struct node *next; //指向下一個(gè)結(jié)點(diǎn)</p><p>　　int info; //與

40、表頭結(jié)點(diǎn)邊的信息</p><p>　　}ListNode;</p><p>　　typedef struct{ //定義表頭結(jié)點(diǎn)數(shù)組</p><p>　　int number; //頂點(diǎn)信息</p><p>　　ListNode *firstarc; //指向第一個(gè)鄰接點(diǎn)<

41、/p><p>　　}AdjList; //表頭結(jié)點(diǎn)類型</p><p>　　typedef struct{ //鄰接表類型</p><p>　　AdjList head[max_vertex_num]; //鄰接表的組</p><

42、p>　　int vexnum; //頂點(diǎn)個(gè)數(shù)表頭數(shù)</p><p>　　intedgnum; //邊的個(gè)數(shù)</p><p><b>　　}ALGraph;</b></p><p>　　typedef struct{ </p><p>　　

43、int data[max_vertex_num];//堆棧數(shù)組</p><p>　　int top;//棧頂標(biāo)志</p><p>　　}Stack; //順序表類型</p><p>　　int rudu[max_vertex_num];//定義一個(gè)存儲(chǔ)每個(gè)頂點(diǎn)入度的全局?jǐn)?shù)組</p><p>　　int visited[max_vert

44、ex_num];//定義全局?jǐn)?shù)組標(biāo)志拓?fù)渑判蜻^(guò)程中是否訪問(wèn)過(guò)</p><p>　　int flag=0;//接受拓?fù)渑判虻拇螖?shù)，若為0，則該圖不是AOV網(wǎng)</p><p>　　ALGraph *create_AdjListGraph(){</p><p>　　ALGraph *T; ListNode *p; //定義指向結(jié)點(diǎn)的指針</p><p&

45、gt;　　int i,j; //輸入邊是的起點(diǎn)和終點(diǎn)</p><p>　　T=(ALGraph *)malloc(sizeof(ALGraph));//定義圖</p><p>　　printf("1、請(qǐng)輸入頂點(diǎn)數(shù):");</p><p>　　scanf("%d",&T-&g

46、t;vexnum); //輸入頂點(diǎn)個(gè)數(shù)</p><p>　　for(i=0;i<T->vexnum;i++){ //初始化表頭結(jié)點(diǎn)數(shù)組</p><p>　　T->head[i].number=i; //初始化結(jié)點(diǎn)編號(hào)</p><p>　　rudu[i]=0; //將每個(gè)節(jié)點(diǎn)

47、的荼毒初始化為</p><p>　　visited[i]=0;</p><p>　　T->head[i].firstarc=NULL; //將表頭結(jié)點(diǎn)數(shù)組的每個(gè)結(jié)點(diǎn)的指針域置空</p><p><b>　　}</b></p><p>　　printf("2、請(qǐng)輸入邊數(shù):");</p&g

48、t;<p>　　scanf("%d",&T->edgnum); //輸入邊的個(gè)數(shù)</p><p>　　printf("3、按起點(diǎn)終點(diǎn)權(quán)值的順序一次輸入邊的序列:\n");</p><p>　　for(i=0;i<T->edgnum;i++){</p><p>　　prin

49、tf("請(qǐng)輸入第 %d 條邊:",i+1);</p><p>　　p=(ListNode *)malloc(sizeof(ListNode));</p><p>　　scanf("%d",&j); //輸入這條邊起始節(jié)點(diǎn)的編號(hào)</p><p>　　scanf("%d",&a

50、mp;p->number); //輸入這條邊的終點(diǎn)的編號(hào)</p><p>　　scanf("%d",&p->info); //輸入這條邊的權(quán)值</p><p>　　printf("\n");</p><p>　　rudu[p->number]++; //將插入邊

51、中結(jié)點(diǎn)的入度加1</p><p>　　p->next=T->head[j].firstarc;</p><p>　　T->head[j].firstarc=p; //將該結(jié)點(diǎn)插入到單鏈表中創(chuàng)建一條邊</p><p><b>　　}</b></p><p><b>　　return T

52、;</b></p><p><b>　　}</b></p><p>　　void print(ALGraph *T){//輸出圖的鄰接表</p><p>　　ListNode *p;</p><p><b>　　int i;</b></p><p>　　print

53、f("表頭數(shù)組(該結(jié)點(diǎn)的入度) 與之有邊的節(jié)點(diǎn)（該弧的權(quán)值）\n");</p><p>　　for(i=0;i<T->vexnum;i++){</p><p>　　printf("V%d（%d） ",T->head[i].number,rudu[i]);</p><p>　　p=T->

54、;head[i].firstarc;</p><p><b>　　while(p){</b></p><p>　　printf("---------------->V%d(%d)",p->number,p->info);</p><p>　　p=p->next;</p><p>

55、;<b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　Stack *Setnull(){//置?？?lt;/p><p>

56、;<b>　　Stack *L;</b></p><p>　　L=(Stack *)malloc(sizeof(Stack));</p><p>　　L->top=-1;</p><p>　　return(L);</p><p><b>　　}</b></p><p>

57、　　void Sinsert(Stack *L,int x){//入棧</p><p>　　L->top=L->top+1;</p><p>　　L->data[L->top]=x;</p><p><b>　　} </b></p><p>　　void Sdelete(Stack *L){//出

58、棧</p><p>　　L->top=L->top-1;</p><p><b>　　}</b></p><p>　　void Soutput(Stack *L){//輸出棧中元素 </p><p><b>　　int i;</b></p><p>　　for

59、(i=0;i<L->top+1;i++)</p><p>　　printf("V%d ",L->data[i]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void topusort(Stack

60、*L,ALGraph *G,int i){//拓?fù)渑判?lt;/p><p>　　ListNode *P;</p><p>　　int j,k;Soutput(L);</p><p>　　Sinsert(L,i); //把頂點(diǎn)Vi加入到順序表中</p><p>　　P=G->head[i].firstarc;</p>&

61、lt;p>　　visited[i]=1; //把排序過(guò)的點(diǎn)標(biāo)記</p><p>　　while(P){</p><p>　　j=P->number;</p><p>　　rudu[j]--; //把以Vi為頭的終止結(jié)點(diǎn)入度減1</p><p>　　P=P->next;</p><p>&

62、lt;b>　　}</b></p><p>　　if(L->top+1==G->vexnum){//判斷順序表中一種拓?fù)渑判蛲瓿?lt;/p><p>　　Soutput(L);</p><p>　　printf("\n");</p><p><b>　　flag++;</b>&

63、lt;/p><p><b>　　}</b></p><p>　　for(k=0;k<G->vexnum;k++)//調(diào)用部分</p><p>　　if((visited[k]==0)&&(rudu[k]==0))// 如果Vk在此輪中未被訪問(wèn)過(guò)且入度為0</p><p>　　topusort(L,

64、G,k);</p><p>　　visited[i]=0; //使Vi恢復(fù)為未訪問(wèn)</p><p>　　P=G->head[i].firstarc;</p><p><b>　　while(P)</b></p><p><b>　　{</b></p><p>　　j=

65、P->number;</p><p>　　rudu[j]++; //使Vj的入度恢復(fù) ，加1</p><p>　　P=P->next;</p><p><b>　　}</b></p><p>　　Sdelete(L);</p><p><b>　　}</b>&

66、lt;/p><p>　　void caidan(){</p><p>　　printf(" \t_____________________________________________________________\n\n");</p><p>　　printf(" \t◇

67、 ◇\n");</p><p>　　printf(" \t◇ ◇\n");</p><p>　　printf(" \t◇ **********歡迎使用AOV網(wǎng)拓?fù)湫蛄酗@示程序！**

68、******** ◇\n");</p><p>　　printf(" \t◇ ◇\n");</p><p>　　printf(" \t◇

69、 ◇\n");</p><p>　　printf("\t_____________________________________________________________\n");</p><p><b>　　}</b></p><p>　　void caidan1(){</p>

70、<p>　　printf("\n\n\n\n\n");</p><p>　　printf(" \t_____________________________________________________________\n\n");</p><p>　　printf(" \t◇

71、 ◇\n");</p><p>　　printf(" \t◇ ◇\n");</p><p>　　printf(" \t◇ ★★★★ 謝謝使用

72、！ ★★★★ ◇\n");</p><p>　　printf(" \t◇ ◇\n");</p><p>　　printf(" \t◇

73、 ◇\n");</p><p>　　printf(" \t_____________________________________________________________\n");</p><p><b>　　}</b></p><p>　　void main()&l

74、t;/p><p><b>　　{</b></p><p>　　int i;ALGraph *G;Stack *L;int n=1;</p><p>　　L=Setnull();</p><p>　　while(n==1){//循環(huán)顯示拓?fù)渑判?lt;/p><p>　　system("cls&qu

75、ot;);</p><p><b>　　caidan();</b></p><p>　　printf("注意：請(qǐng)按下列步驟輸入您的ＡＯＶ網(wǎng)！\n");</p><p>　　G=create_AdjListGraph();</p><p>　　system("cls");</p

76、><p><b>　　caidan();</b></p><p>　　printf("該圖的鄰接表為：\n");</p><p><b>　　print(G);</b></p><p>　　system("pause");</p><p>

77、　　system("cls");</p><p><b>　　caidan();</b></p><p>　　printf("以下是該圖所有的拓?fù)湫蛄校篭n");</p><p>　　for(i=0;i<G->vexnum;i++)</p><p>　　if(rudu[

78、i]==0&&visited[i]==0) topusort(L,G,i);</p><p>　　if(flag>0){</p><p>　　printf("該AOV圖有%d種拓?fù)渑判?\n",flag);</p><p><b>　　flag=0;</b></p><p>&

79、lt;b>　　}</b></p><p><b>　　else </b></p><p>　　printf("\n\n\t出錯(cuò)!\n\n此圖不是AOV網(wǎng)，無(wú)拓?fù)渑判蛐蛄?\n\n\n");</p><p>　　system("pause");</p><p>

80、　　system("cls");</p><p><b>　　caidan();</b></p><p>　　printf("按1繼續(xù)顯示下一個(gè)圖的拓?fù)湫蛄?，?結(jié)束程序！\n");</p><p>　　scanf("%d",&n);</p><p>