1、長沙理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 趙思雨學(xué) 院 計算機與通信工程 專 業(yè) 網(wǎng)絡(luò)工程 班 級 網(wǎng)絡(luò)1101班 學(xué) 號 0學(xué)生姓名 趙思雨 指導(dǎo)教師 樂曉波 課程成績 完成日期 2013年7月12日課程設(shè)計任務(wù)書計算機與通信工程 學(xué)院 網(wǎng)絡(luò)工程 專業(yè) 課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計時間2012-2013學(xué)年第2學(xué)期19周-20周學(xué)生姓名趙思雨指導(dǎo)老師樂曉波題 目拓?fù)渑判蛩惴ǖ难芯颗c實現(xiàn)主要內(nèi)容：研究圖的存儲結(jié)構(gòu)，研究AOV網(wǎng)（活動在頂點的網(wǎng)，有向網(wǎng)）的存儲結(jié)構(gòu)與輸入算法，并研究拓?fù)渑判蛩惴ǖ膶崿F(xiàn)方法，在此基礎(chǔ)上對該算法進行分析。要求：（1）研究AOV網(wǎng)（活動在頂點的網(wǎng)，有向網(wǎng)）的存儲結(jié)構(gòu)與輸入算法，并研

2、究拓?fù)渑判蛩惴ǖ膶崿F(xiàn)方法。（2）通過對拓?fù)渑判騿栴}的分析、設(shè)計、編碼、測試等工作，掌握針對實際應(yīng)用問題設(shè)計數(shù)據(jù)結(jié)構(gòu)，結(jié)合C語言解決實際應(yīng)用問題的一般方法和過程，初步掌握利用數(shù)據(jù)結(jié)構(gòu)解決實際應(yīng)用問題的一般方法。（3）對所設(shè)計的算法要求進行認(rèn)真的分析、測試與調(diào)試，所提交的相關(guān)程序要能正確運行。（4）按要求認(rèn)真撰寫課程設(shè)計報告書。應(yīng)當(dāng)提交的文件：（1）課程設(shè)計報告書打印稿一份。（2）課程設(shè)計相關(guān)電子文檔一套（含任務(wù)書、報告書、可正確執(zhí)行的程序等）。課程設(shè)計成績評定學(xué) 院 計算機與通信工程 專 業(yè) 網(wǎng)絡(luò)工程 班 級 網(wǎng)絡(luò)11-01 學(xué) 號 0 學(xué)生姓名 趙思雨 指導(dǎo)教師 樂曉波 完成日期 2013年7

3、月12日 指導(dǎo)教師對學(xué)生在課程設(shè)計中的評價評分項目優(yōu)良中及格不及格課程設(shè)計中的創(chuàng)造性成果學(xué)生掌握課程內(nèi)容的程度課程設(shè)計完成情況課程設(shè)計動手能力文字表達(dá)學(xué)習(xí)態(tài)度規(guī)范要求課程設(shè)計論文的質(zhì)量指導(dǎo)教師對課程設(shè)計的評定意見綜合成績 指導(dǎo)教師簽字 年 月 日拓?fù)渑判蛩惴ǖ难芯颗c實現(xiàn)學(xué)生姓名：趙思雨 指導(dǎo)老師：樂曉波摘 要 該課程設(shè)計研究AOV網(wǎng)。研究圖的存儲結(jié)構(gòu)，研究AOV網(wǎng)（活動在頂點的網(wǎng)，有向網(wǎng)）的存儲結(jié)構(gòu)與輸入算法，并研究拓?fù)渑判蛩惴ǖ膶崿F(xiàn)方法，在此基礎(chǔ)上對該算法進行分析。通過對拓?fù)渑判騿栴}的分析、設(shè)計、編碼、測試等工作，掌握針對實際應(yīng)用問題設(shè)計數(shù)據(jù)結(jié)構(gòu)，結(jié)合C語言解決實際應(yīng)用問題的一般方法和過程，

4、初步掌握利用數(shù)據(jù)結(jié)構(gòu)解決實際應(yīng)用問題的一般方法。關(guān)鍵字 AOV網(wǎng)；拓?fù)渑判?；算法設(shè)計；C語言；數(shù)據(jù)結(jié)構(gòu)目錄 摘要31 引言51.1 課程設(shè)計的目的51.2 課程設(shè)計的內(nèi)容61.3 課程設(shè)計的目標(biāo)62 設(shè)計內(nèi)容72.1 問題描述72.2 思路分析72.3 過程演示83 算法分析及詳細(xì)實現(xiàn)93.1 算法分析93.2 算法中用到的函數(shù)聲明93.3 部分程序編寫94 程序的運行環(huán)境及運行結(jié)果114.1 程序運行的環(huán)境114.2 運行結(jié)果115 總結(jié)145.1 課程設(shè)計總結(jié)145.2 心得與體會14參考文獻(xiàn)15附件161 引言 課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識，發(fā)現(xiàn)，提出，分析和解決實際問題，鍛煉實踐

5、能力的重要環(huán)節(jié)，是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程。 數(shù)據(jù)結(jié)構(gòu)是學(xué)習(xí)計算機相關(guān)專業(yè)的非常重要的知識，所謂結(jié)構(gòu)就是組織形式，數(shù)據(jù)的結(jié)構(gòu)就是數(shù)據(jù)怎么組織，即怎么描述，怎么在電腦中存儲。不同類型的數(shù)據(jù)，它們的組織形式（數(shù)據(jù)結(jié)構(gòu)）是不同的，在程序設(shè)計中，除了應(yīng)精心設(shè)計算法外，還應(yīng)精心組織數(shù)據(jù)（包括原始數(shù)據(jù)、中間結(jié)果 、最終結(jié)果），使之形成一定的組織形式（數(shù)據(jù)結(jié)構(gòu)），以便讓計算機盡可能高效率地處理。數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與工程的基礎(chǔ)研究之一，掌握該領(lǐng)域的知識對于我們進一步進行高效率的計算機程序開發(fā)非常重要。無論在中國還是在美國，數(shù)據(jù)結(jié)構(gòu)一直是大學(xué)的計算機專業(yè)重要的專業(yè)基礎(chǔ)課。 數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計要求

6、學(xué)生熟練掌握數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示，具有分析問題的能力，可以根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，運用該數(shù)據(jù)結(jié)構(gòu)結(jié)合相應(yīng)的算法解決實際問題。1.1 課程設(shè)計的目的為了更好的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，深刻理解數(shù)據(jù)結(jié)構(gòu)在解決實際問題中的應(yīng)用，體會其重要性，熟練掌握線性表、棧和隊列、串、數(shù)組、樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)，熟悉各自的特點和應(yīng)用場合。同時鍛煉自己獨立分析理解問題的能力，學(xué)會根據(jù)不同的問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，然后結(jié)合適當(dāng)?shù)乃惴ń鉀Q問題。鍛煉自己的設(shè)計和編寫程序的技巧，進一步調(diào)試和測試自己所寫的程序，使其功能更加完善，養(yǎng)成較好的編寫程序習(xí)慣。提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力1，訓(xùn)練用系統(tǒng)

7、的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。本課程設(shè)計的目的就是要達(dá)到理論與實際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計技能2。1.2 課程設(shè)計的內(nèi)容 本次課程設(shè)計要求對于給定的AOV網(wǎng)求出它所有拓?fù)湫蛄小OV網(wǎng)（是一個有向無環(huán)圖（Directed Acycline Graph，DAG圖）3。AOV網(wǎng)中，如果頂點Vi表示的活動在和頂點Vj表示的活動之前進行，則稱Vi是Vj的前驅(qū)頂點，Vj是Vi后繼頂點。拓?fù)渑判蚓褪菍⒂邢驘o環(huán)圖中的各個頂點排成一個序列，使得

8、所有的前去后繼關(guān)系都得到滿足。對于相互之間沒有次序關(guān)系的頂點，在拓?fù)渑判虻男蛄兄锌梢蕴幵谌我獾奈恢?。因此，拓?fù)渑判虻慕Y(jié)果往往是不唯一的。本次課程設(shè)計的主要任務(wù)就是將給定的一個AOV網(wǎng)輸出所有的該種序列4。1.3 課程設(shè)計的目標(biāo) 通過對拓?fù)渑判騿栴}的分析、設(shè)計、編碼、測試等工作，掌握針對實際應(yīng)用問題設(shè)計數(shù)據(jù)結(jié)構(gòu)，結(jié)合C語言解決實際應(yīng)用問題的一般方法和過程，初步掌握利用數(shù)據(jù)結(jié)構(gòu)解決實際應(yīng)用問題的一般方法。 2 設(shè)計內(nèi)容2.1 問題描述 在AOV網(wǎng)中為了更好地完成工程，必須滿足活動之間先后關(guān)系，需要將各活動排一個先后次序即為拓?fù)渑判?。拓?fù)渑判蚩梢詰?yīng)用于教學(xué)計劃的安排，根據(jù)課程之間的依賴關(guān)系，制定課程

9、安排計劃。按照用戶輸入的課程數(shù)，課程間的先后關(guān)系數(shù)目以及課程間兩兩間的先后關(guān)系，程序執(zhí)行后會給出符合拓?fù)渑判虻恼n程安排計劃。2.2 思路分析一種拓?fù)湫蛄械纳梢话阌幸幌虏襟E：（1）、從有向無環(huán)圖中選擇一個沒有前驅(qū)結(jié)點的頂點并加入到結(jié)點的序列中；（2）、從有向無環(huán)圖中刪除該頂點以及該頂點為尾的所有的?。唬?）、重復(fù)（1）（2）的步驟。在整個拓?fù)渑判虻倪^程中需要頻繁的檢查頂點的前驅(qū)以及作刪除頂點和弧的操作，在這里我們用兩個全局變量rudumax_vertex_num和visitedmax_vertex_num來分別實現(xiàn)這兩個操作，如果rudui為零則表示無前驅(qū)結(jié)點，如果visitedi為零則表示沒

10、有被訪問過。如果每刪除一個結(jié)點就檢查，那樣的話時間復(fù)雜度將很大（等于遍歷所有的頂點一遍），因此設(shè)計一個堆棧，把檢測到的入度為零的結(jié)點入棧。每次刪除頂點只要從棧中取出一個結(jié)點即可。但是如果需要實現(xiàn)一個AOV網(wǎng)所有拓?fù)湫蛄械纳蓜t不止如此。在每找到一個符合要求的結(jié)點后入棧，從而實現(xiàn)一種拓?fù)渑判颉Ｔ谝惶送負(fù)渑判蚪Y(jié)束后，應(yīng)該進行恢復(fù)刪除的結(jié)點和刪除的弧，并標(biāo)記已經(jīng)有過的序列，在恢復(fù)某幾個個結(jié)點后進行下一次的拓?fù)渑判颉?.3 過程演示 該部分給出了算法執(zhí)行的流程，如圖2-1所示。 圖 2-1 算法流程圖3 算法分析及詳細(xì)實現(xiàn)3.1 算法分析 首先建立空棧，并從第一個頂點開始進行拓?fù)渑判?。將該結(jié)點初始化為

11、被訪問過，并將圖類的結(jié)點指針指向該編號的結(jié)點的表頭數(shù)組firstarc域，把該頂點入棧后，將所有的以它為起點的弧都刪掉，即將弧的終點的入度都減一。接著判斷棧里面的數(shù)據(jù)個數(shù)是否和圖頂點的個數(shù)一樣，如果一樣，則說明已經(jīng)有一次拓?fù)渑判蛲瓿?，若不一樣，則往下進行遞歸，再將符合條件的頂點入棧，直到一次拓?fù)渑判蛲瓿傻臈l件成立。最后將頂點出棧，恢復(fù)所有結(jié)點的入度，并準(zhǔn)備下一趟拓?fù)渑判颉?.2 算法中用到的函數(shù)聲明 在該程序中用到了很多函數(shù)，具體聲明如表3-1所示。print(ALGraph *T)輸出圖的鄰接表Sinsert(Stack *L,int x)入棧Sdelete(Stack *L)出棧Soutp

12、ut(Stack *L)輸出棧中元素topusort(Stack *L,ALGraph *G,int 拓?fù)渑判虮?-1 算法中用到的函數(shù)聲明3.3 部分程序編寫實現(xiàn)該算法的具體編碼如下：void topusort(Stack *L,ALGraph *G,int i)/拓?fù)渑判?ListNode *P; int j,k;Soutput(L); Sinsert(L,i); /把頂點Vi加入到棧中 P=G-headi.firstarc; visitedi=1; /把排序過的點標(biāo)記 while(P) j=P-number; ruduj-; /把以Vi為頭的終止結(jié)點入度減1 P=P-next;if(L-

13、top+1=G-vexnum)/判斷棧中一種拓?fù)渑判蛲瓿蒘output(L);printf(n);flag+;for(k=0;kvexnum;k+)/調(diào)用部分 if(visitedk=0)&(ruduk=0)/ 如果Vk在此輪中未被訪問過且入度為0topusort(L,G,k);visitedi=0; /使Vi恢復(fù)為未訪問P=G-headi.firstarc; while(P) j=P-number; ruduj+; /使Vj的入度恢復(fù) ，加1 P=P-next; Sdelete(L);4 程序的運行環(huán)境及運行結(jié)果4.1 程序運行的環(huán)境 一個程序需要一個良好的環(huán)境才能運行，該課程設(shè)計中的程序運

14、行的硬件、軟件環(huán)境如下。（1）硬件環(huán)境1）學(xué)生用微機2）局域網(wǎng)（2）軟件環(huán)境1）Windows 8 旗艦版系統(tǒng)2）VS20104.2 運行結(jié)果 程序的運行結(jié)果將從三個方面予以介紹。（1）圖的輸入輸入圖，結(jié)果如圖4-1所示。在這里首先輸入頂點數(shù)和邊數(shù)，然后輸入沒條邊的起點終點編號和權(quán)值。 圖 4-1 圖的輸入（2）圖鄰接表的輸出 輸出圖的鄰接矩陣。輸入圖過后按回車鍵顯示圖的鄰接表，如圖4-2所示。 圖 4-2 圖鄰接表的輸出（3）拓?fù)湫蛄械妮敵?在顯示完拓?fù)湫蛄泻蟀椿剀囕敵鲈搱D的所有拓?fù)渑判蛐蛄?，如圖4-3所示。 圖 4-3 拓?fù)湫蛄械妮敵?5 總結(jié)5.1 課程設(shè)計總結(jié) 課程設(shè)計可以檢驗學(xué)生對知

15、識的掌握程度。同時更反映了一個學(xué)生對課程設(shè)計的態(tài)度，對待任何事都要認(rèn)真，可以不會，可以做的不是最好的，但是一定要盡自己最大的努力去完成一件哪怕再小的事。在這次課程設(shè)計中學(xué)到了很多新的知識，同時也鞏固了之前學(xué)過知識。對靜態(tài)鏈表有了更深的理解，對哈夫曼樹及哈夫曼編碼更是印象深刻。雖然，最后根據(jù)要求完成了任務(wù)，但期間還是出現(xiàn)了種種的問題，比如在編寫完函數(shù)時，運行結(jié)果總是不對，調(diào)試了好多遍，也沒有發(fā)現(xiàn)錯誤，沒有想到是選擇函數(shù)除了差錯，一個簡單的函數(shù)，怎么也沒有想到會是這里出了錯，是因為我給s1，s2變量賦初值時出了錯誤。同時，為了更好的完成任務(wù)還查閱了好多資料，不懂的就到處搜索，去圖書館借相應(yīng)的書籍來

16、看，鍛煉了自己查閱資料的能力。5.2 心得與體會 我覺得本此課程設(shè)計最大的收獲就是學(xué)會按部就班的完成任務(wù)。首先想好用什么數(shù)據(jù)結(jié)構(gòu)，主要的思想要明確的認(rèn)定。然后選一個簡單的例子，按照你選定的思想，一步一步的走程序，才能更早的發(fā)現(xiàn)程序還存在那些沒有考慮到的缺陷。特別忌諱的是到寫程序的時候，對主要思想和數(shù)據(jù)結(jié)構(gòu)還不是很確定。最后在調(diào)試程序的階段，這次我開始用設(shè)置斷點的方法，一步一步看是否達(dá)到你要的理想結(jié)果，從而來找出程序中出錯的地方。還有，一種方法也是用一個輸出語句，分別放在程序的不同位置，通過輸出結(jié)果，也可以快速判斷出程序不能運行的是那一個語句了。從而方便你修改，快速得到正確的結(jié)果。還有，這次調(diào)試

17、的過程中，我表現(xiàn)的比以前要更有耐心，這也是一個很好的收獲。 還有一個更重要的體會就是，遇到不會的地方，我開始習(xí)慣到圖書館或是網(wǎng)上去找資料。這是一個很好的學(xué)習(xí)過程，它不僅僅是可以解決這個問題，關(guān)鍵是你會從找資料學(xué)習(xí)的過程中，會學(xué)好很多很多意想不到的知識?？赡軙饶闶诸^上要學(xué)習(xí)的知識多得多。參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)M.北京:清華大學(xué)出版社,2012.52李春葆，尹為民.數(shù)據(jù)結(jié)構(gòu)教程上機指導(dǎo)M.北京:清華大學(xué)出版社,20083Andrew Binstock，John Rex.程序員實用算法(第二版)M.北京:機械工業(yè)出版社,2009.064Thomas H.Cormen, Ch

18、arles E.Leiserson,Ronald L.Riverst, Clfford Stein.Introduction to Alogrithms Second EditionM.US:Machine Press,2012附件程序清單#includestdio.h#includemalloc.h#includestdlib.h#define max_vertex_num 100 /頂點的最大個數(shù)typedef struct node /鄰接表中的結(jié)點類型int number; /結(jié)點編號struct node *next; /指向下一個結(jié)點int info; /與表頭結(jié)點邊的信息List

19、Node;typedef struct /定義表頭結(jié)點數(shù)組int number; /頂點信息ListNode *firstarc; /指向第一個鄰接點AdjList; /表頭結(jié)點類型typedef struct /鄰接表類型AdjList headmax_vertex_num; /鄰接表的組int vexnum; /頂點個數(shù)表頭數(shù)intedgnum; /邊的個數(shù)ALGraph;typedef struct int datamax_vertex_num;/堆棧數(shù)組int top;/棧頂標(biāo)志Stack; /順序表類型int rudumax_vertex_num;/定義一個存儲每個頂點入度的全局?jǐn)?shù)組

20、int visitedmax_vertex_num;/定義全局?jǐn)?shù)組標(biāo)志拓?fù)渑判蜻^程中是否訪問過int flag=0;/接受拓?fù)渑判虻拇螖?shù)，若為0，則該圖不是AOV網(wǎng)ALGraph *create_AdjListGraph()ALGraph *T; ListNode *p; /定義指向結(jié)點的指針int i,j; /輸入邊是的起點和終點T=(ALGraph *)malloc(sizeof(ALGraph);/定義圖 printf(1、請輸入頂點數(shù):); scanf(%d,&T-vexnum); /輸入頂點個數(shù)for(i=0;ivexnum;i+) /初始化表頭結(jié)點數(shù)組 T-headi.number

21、=i; /初始化結(jié)點編號rudui=0; /將每個節(jié)點的荼毒初始化為visitedi=0;T-headi.firstarc=NULL; /將表頭結(jié)點數(shù)組的每個結(jié)點的指針域置空 printf(2、請輸入邊數(shù):); scanf(%d,&T-edgnum); /輸入邊的個數(shù)printf(3、按起點終點權(quán)值的順序一次輸入邊的序列:n); for(i=0;iedgnum;i+)printf(請輸入第 %d 條邊:,i+1);p=(ListNode *)malloc(sizeof(ListNode);scanf(%d,&j); /輸入這條邊起始節(jié)點的編號 scanf(%d,&p-number); /輸入這

22、條邊的終點的編號scanf(%d,&p-info); /輸入這條邊的權(quán)值printf(n); rudup-number+; /將插入邊中結(jié)點的入度加1p-next=T-headj.firstarc;T-headj.firstarc=p; /將該結(jié)點插入到單鏈表中創(chuàng)建一條邊return T;void print(ALGraph *T)/輸出圖的鄰接表ListNode *p;int i;printf(表頭數(shù)組(該結(jié)點的入度) 與之有邊的節(jié)點（該弧的權(quán)值）n);for(i=0;ivexnum;i+)printf(V%d（%d） ,T-headi.number,rudui);p=T-headi.fir

23、starc;while(p)printf(-V%d(%d),p-number,p-info);p=p-next;printf(n);Stack *Setnull()/置?？誗tack *L;L=(Stack *)malloc(sizeof(Stack);L-top=-1;return(L);void Sinsert(Stack *L,int x)/入棧 L-top=L-top+1;L-dataL-top=x; void Sdelete(Stack *L)/出棧L-top=L-top-1;void Soutput(Stack *L)/輸出棧中元素 int i;for(i=0;itop+1;i+)

24、printf(V%d ,L-datai);printf(n);void topusort(Stack *L,ALGraph *G,int i)/拓?fù)渑判?ListNode *P; int j,k;Soutput(L); Sinsert(L,i); /把頂點Vi加入到順序表中 P=G-headi.firstarc; visitedi=1; /把排序過的點標(biāo)記 while(P) j=P-number; ruduj-; /把以Vi為頭的終止結(jié)點入度減1 P=P-next;if(L-top+1=G-vexnum)/判斷順序表中一種拓?fù)渑判蛲瓿蒘output(L);printf(n);flag+;for(k=0;kvexnum;k+)/調(diào)用部分 if(visitedk=0)&(ruduk=0)/ 如果Vk在此輪中未被訪問過且入度為0topusort(L,G,k);visitedi=0; /使Vi恢復(fù)為未訪問P=G-headi.firstarc; while(P) j=P-nu