上傳人：活***

認(rèn)證信息

認(rèn)證類型：機(jī)構(gòu)認(rèn)證

認(rèn)證主體：寧夏凱米世紀(jì)網(wǎng)絡(luò)科技有限公司

IP屬地：寧夏

統(tǒng)一社會(huì)信用代碼/組織機(jī)構(gòu)代碼

91640100MA774ECW4K

IP屬地：寧夏 上傳時(shí)間：2021-12-16 格式：DOC 頁(yè)數(shù)：20 大?。?58.95KB 積分：11 舉報(bào) 版權(quán)申訴

1、 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)報(bào)告題目：題目： 拓?fù)渑判蛩惴ㄍ負(fù)渑判蛩惴?院（系）：理學(xué)院院（系）：理學(xué)院專專 業(yè)：信息與計(jì)算科學(xué)業(yè)：信息與計(jì)算科學(xué) 班班 級(jí)：級(jí)： 94140101學(xué)學(xué) 號(hào)：號(hào)： 姓姓 名：名： 指導(dǎo)教師：指導(dǎo)教師： 2011 年年 12 月月沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 目目 錄錄1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹.11.1 課程設(shè)計(jì)內(nèi)容.11.2 課程設(shè)計(jì)要求.12 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理.22.1 課設(shè)題目粗略分析.22.2 原理圖介紹.32.2.1 功能模塊圖.32.2.2 流程圖分析.33 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析.53.1 存儲(chǔ)結(jié)構(gòu).53.2 算法描

2、述.54 4 調(diào)試與分析調(diào)試與分析.94.1 調(diào)試過(guò)程.94.2 程序執(zhí)行過(guò)程.9參考文獻(xiàn)參考文獻(xiàn).11總結(jié)總結(jié).12附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.13沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 0 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹1.11.1 課程設(shè)計(jì)內(nèi)容課程設(shè)計(jì)內(nèi)容編寫算法，建立有向無(wú)環(huán)圖，系統(tǒng)主要功能如下：1. 能夠求解該有向無(wú)環(huán)圖的拓?fù)渑判虿⑤敵龀鰜?lái)；2. 拓?fù)渑判驊?yīng)能夠處理出現(xiàn)環(huán)的情況。3. 頂點(diǎn)信息要有幾種情況可以選擇。1.21.2 課程設(shè)計(jì)要求課程設(shè)計(jì)要求1.輸出除拓?fù)渑判驍?shù)據(jù)外，還要求輸出鄰接表數(shù)據(jù)；2.參考相應(yīng)資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)；3.交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代

3、碼。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 1 2 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析本課設(shè)題目要求編寫算法能夠建立有向無(wú)環(huán)圖，有向無(wú)環(huán)圖，顧名思義，即一個(gè)無(wú)環(huán)的有向圖，是一類較有向圖更一般的特殊有向圖。其功能要求及個(gè)人在寫程序時(shí)對(duì)該功能的實(shí)現(xiàn)作如下分析：1. 將圖以合適的方式存儲(chǔ)起來(lái)。圖有多種存儲(chǔ)方式，其中最常用的存儲(chǔ)方式有圖的鄰接矩陣和鄰接表。本人在構(gòu)思時(shí)使用鄰接表來(lái)建立有向無(wú)環(huán)圖，將其存儲(chǔ)起來(lái)；2. 求解該有向無(wú)環(huán)圖的拓?fù)渑判?，并將其輸出出?lái)。若通過(guò)構(gòu)造，建立了一個(gè)有向無(wú)環(huán)圖，那么一定可以求出其拓?fù)渑判颍湓肀容^簡(jiǎn)單。即統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度，將入度為 0 的

4、結(jié)點(diǎn)提取出來(lái)，然后再統(tǒng)計(jì)剩下的結(jié)點(diǎn)的入度，再次將入度為零的結(jié)點(diǎn)提取出來(lái)，以此類推，這樣就形成了一個(gè)序列，這樣的序列就是該圖的拓?fù)渑判蛐蛄校?. 拓?fù)渑判蛩惴☉?yīng)能夠處理出現(xiàn)環(huán)的情況。個(gè)人在寫程序時(shí)，考慮到構(gòu)造圖時(shí)，會(huì)有構(gòu)造成有向有環(huán)圖的情況，應(yīng)該在運(yùn)行程序時(shí)，提醒出來(lái)，然后重新輸入有向無(wú)環(huán)圖，知道輸入正確為止。這樣就有多次構(gòu)造鄰接表的問(wèn)題，每一次構(gòu)造鄰接表時(shí)，都應(yīng)該將原來(lái)錯(cuò)誤的（不是無(wú)環(huán)圖的）鄰接表空間釋放掉，否則，會(huì)變得混亂；4. 輸出除拓?fù)渑判蛲?，還要求輸出鄰接表數(shù)據(jù)。由于圖是用鄰接表存儲(chǔ)的，所以很容易將其鄰接表輸出出來(lái)。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 2 2.22.2 原理圖介紹原理圖介紹2

5、.2.12.2.1 功能模塊圖功能模塊圖圖 2.1 功能模塊圖2.2.22.2.2 流程圖分析流程圖分析根據(jù)程序的總的步驟，擬將整個(gè)流程分為三個(gè)模塊。三個(gè)模塊既相互獨(dú)立又相互聯(lián)系。具體分析如下：1. 圖像輸入，根據(jù)題目要求，要能夠建立一個(gè)有向無(wú)環(huán)圖，這就要我們?cè)诔绦蛑腥ソⅰ？紤]到輸入方式要盡量方便全面，采用輸入弧的方式，輸入每條弧的鏈接的兩個(gè)結(jié)點(diǎn)，當(dāng)輸入-1 時(shí)結(jié)束輸入。這樣再輸入的時(shí)候，與相鄰的兩個(gè)結(jié)點(diǎn)的鄰接矩陣對(duì)應(yīng)的位置也做相應(yīng)改變。2. 判斷圖是不是有向無(wú)環(huán)圖。當(dāng)圖為有向無(wú)環(huán)圖時(shí)，則挑選完畢后，隊(duì)列應(yīng)該是滿的，進(jìn)行后續(xù)步驟。對(duì)于結(jié)點(diǎn)入隊(duì)列的順序，需要借助于數(shù)組。選取入visited度為

6、零的結(jié)點(diǎn)，入隊(duì)列，調(diào)整數(shù)組，循環(huán)進(jìn)行。若隊(duì)列不滿，則輸入的圖visited不符合要求，應(yīng)該重新輸入。在程序中應(yīng)做適當(dāng)提醒，然后自動(dòng)轉(zhuǎn)模塊 1.，進(jìn)行圖的重新編輯。 拓?fù)渑判蛴协h(huán)圖遍歷全部圖的遍歷 圖的存儲(chǔ) 鄰接表 輸出隊(duì)列入度為零入隊(duì)列拓?fù)渑判蛩惴o(wú)環(huán)圖無(wú)法遍歷 鄰接矩陣沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 3 3. 拓?fù)渑判?。此時(shí)，所輸入的弧應(yīng)該是有向無(wú)環(huán)圖了，下面進(jìn)行拓?fù)渑判?。在判斷它是否為無(wú)環(huán)圖的過(guò)程中已經(jīng)形成了一個(gè)滿隊(duì)列。接下來(lái)所要做的事情就是循環(huán)出隊(duì)列，按照隊(duì)列固有的順序進(jìn)行輸出即可，排序完成。圖 2.2 程序流程圖 開(kāi)始開(kāi)始 圖形輸入圖形輸入構(gòu)造鄰接表，并將其輸構(gòu)造鄰接表，并將其輸出出無(wú)環(huán)

7、圖無(wú)環(huán)圖 否否是是 入度為零入隊(duì)列入度為零入隊(duì)列滿隊(duì)列滿隊(duì)列是是 循環(huán)出隊(duì)列循環(huán)出隊(duì)列 調(diào)整調(diào)整 visited否否 結(jié)束結(jié)束沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 4 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析3.13.1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)一個(gè)無(wú)環(huán)的有向圖叫做有向無(wú)環(huán)圖，簡(jiǎn)稱 dag 圖。本算法首先要建立一個(gè)有向五環(huán)圖，即通過(guò)輸入各邊的數(shù)據(jù)，搭建圖的結(jié)構(gòu)。對(duì)于圖的存儲(chǔ)，用到鄰接表，是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。typedef struct nodeint data;struct node *next;graphnode;graphnode vexsmaximum;對(duì)于用來(lái)排序的隊(duì)列，則用到了順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列，用數(shù)組表示。q

8、ueue int queuemaximum;3.23.2 算法描述算法描述1. 鄰接表的構(gòu)造：本算法借用圖的鄰接矩陣構(gòu)造鄰接表，其形式如下：int graphmaximummaximum;對(duì)于相鄰的結(jié)點(diǎn) 和，graphij=1，若不相鄰，則 graphij=0；對(duì)于鄰接表ij的存儲(chǔ)結(jié)構(gòu)，上面已作說(shuō)明，定義一個(gè) graphnode 類型的數(shù)組變量vexsmaximum和一個(gè) graphnode 類型的指針變量*newnode。若兩個(gè)結(jié)點(diǎn) 和相ij鄰（由 指向，graphij=1） ，則在 vexsmaximum第 行添加以為值的ijijnewnode 數(shù)據(jù)，即 vexsi-1-next=*new

9、node。其中 newnode-data=j，newnode-next=null。直到遍歷完整個(gè)鄰接矩陣，鄰接表隨即建立完成。簡(jiǎn)單算法說(shuō)明如下：for(i=0;il;i+)for(j=0;jl;j+)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 5 if(graphij)createadjacenttable(i,j); /當(dāng)鄰接矩陣 graphij有值時(shí)，則構(gòu)造鄰接表2. 隊(duì)列初始化（入隊(duì)操作）及出隊(duì)操作在本算法中隊(duì)列主要用來(lái)，構(gòu)造拓?fù)渑判蛐蛄?。由于?duì)列具有先入先出的特點(diǎn)，所以，將每次選擇入度為零的結(jié)點(diǎn)入隊(duì)，這樣當(dāng)結(jié)點(diǎn)都入隊(duì)的時(shí)候，再依次出隊(duì)，這樣，排序序列顯而易見(jiàn)。它將圖這樣的非線性結(jié)構(gòu)轉(zhuǎn)化為隊(duì)列這樣的線

10、性結(jié)構(gòu)。（1） 隊(duì)列初始化：void addqueue(int *queue,int x)/入隊(duì)操作if(rear=l-1)printf(隊(duì)列已滿n); return;rear+;queuerear=x;return;（2） 出隊(duì)操作：int delqueue(int *queue)/出隊(duì)操作int e;if(rear=front)return -2;沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 6 front+;e=queuefront;queuefront=0;return e;3. 拓?fù)渑判虮境绦虻耐負(fù)渑判颍仨氃趫D的鄰接表已知的情況下。它還有另外一個(gè)功能：判斷一個(gè)圖是不是無(wú)環(huán)圖。確切的說(shuō)，不能單純的叫

11、拓?fù)渑判?，但考慮它主要的作用，在不引起誤解的情況下就叫拓?fù)渑判蛩惴?。判斷一個(gè)圖是否為有向無(wú)環(huán)圖并進(jìn)行拓?fù)渑判?，判定方法有很多種，檢查一個(gè)有向圖是否存在環(huán)要比無(wú)向圖復(fù)雜。對(duì)于無(wú)向圖來(lái)說(shuō)，若深度優(yōu)先遍歷過(guò)程中遇到回邊（即指向已訪問(wèn)過(guò)的頂點(diǎn)的邊） ，則必存在環(huán)；而對(duì)于有向圖來(lái)說(shuō)，這條回邊有可能指向深度優(yōu)先森林中另一棵生成樹上頂點(diǎn)的弧。但是，如果從有向圖上某個(gè)頂點(diǎn) 出發(fā)的遍歷，在結(jié)束之前出現(xiàn)一條從頂點(diǎn)到頂點(diǎn) 的回邊，v)(vdfsuv由于在生成樹上是 的子孫，則有向圖中必定存在包含頂點(diǎn) 和的環(huán)。uvvu另一種判斷是否有環(huán)的方法則顯得簡(jiǎn)單的多，尤其是對(duì)于本題目來(lái)說(shuō)，由于本題要求是對(duì)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判?/p>

12、，其主要方法是將入度為零的結(jié)點(diǎn)依次輸出出來(lái)，知道圖的所有定點(diǎn)全部輸出為止。那么若圖為有環(huán)圖，在環(huán)上的結(jié)點(diǎn)在其他結(jié)點(diǎn)都選擇出來(lái)后，入度都不為零，即無(wú)法被輸出出來(lái)。那么就可以認(rèn)為按照拓?fù)渑判虻姆椒ㄝ敵鼋Y(jié)點(diǎn)后，若不是將節(jié)點(diǎn)全部輸出出來(lái)的，則此圖為有環(huán)圖。判斷好圖是否為有向圖后，考慮到題目要求，要能夠處理出現(xiàn)環(huán)的情況，若構(gòu)造的圖為有環(huán)圖，則折回開(kāi)始重新輸入圖的數(shù)據(jù)，重新構(gòu)造圖，直到該圖為無(wú)環(huán)圖為止。若圖已經(jīng)是無(wú)環(huán)圖，則進(jìn)行拓?fù)渑判?，排序方法前面已?jīng)講過(guò)，在此主要訴說(shuō)用到的輔助存儲(chǔ)。數(shù)組存儲(chǔ)各結(jié)點(diǎn)的入度，對(duì)入度為零的結(jié)點(diǎn)，visited依次入隊(duì)列，調(diào)整數(shù)組，結(jié)點(diǎn)全部入隊(duì)列后，然后依次出隊(duì)列，queuev

13、isited拓?fù)渑判蛲瓿?。沈?yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 7 void toposort(int *visited,int *queue)int i; rear=-1; front=-1; int topnum=0,mlmaximum,n=0; graphnode *p;for(i=0;inext; while(p!=null)visited(p-data)-1+; p=p-next;while(topnum!=l)for(i=0;inext;while(p!=null)visited(p-data)-1-; p=p-next;visitedi=-1;topnum+;for(i=0;il;i+)

14、mli=delqueue(queue);for(i=0;il;i+)if(mli=-2)printf(您輸入的圖為有環(huán)圖,請(qǐng)重新輸入!n);break;elsen=n+1;if(n=l) printf(拓?fù)渑判驗(yàn)椋簄);for(i=0;i);jj=1;printf(n);沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 8 4 4 調(diào)試與分析調(diào)試與分析4.14.1 調(diào)試過(guò)程調(diào)試過(guò)程在調(diào)試程序是主要遇到以下幾類問(wèn)題：1. 數(shù)組的數(shù)據(jù)容易出現(xiàn)混亂，比如結(jié)點(diǎn)用數(shù)字標(biāo)識(shí)，數(shù)組結(jié)點(diǎn)的位置是從 0 開(kāi)始，而標(biāo)識(shí)符往往從 1 開(kāi)始，這在程序的開(kāi)始就應(yīng)該注意到；2. 各函數(shù)的形參，實(shí)參的區(qū)別，全局變量，局部變量的區(qū)別，特別是在做

15、大型程序的時(shí)候，如果多個(gè)函數(shù)都要用到一個(gè)變量，那么就應(yīng)把該變量定義為全局變量，若錯(cuò)誤的定義為局部變量，很容易出現(xiàn)錯(cuò)誤；3. 對(duì)于一個(gè)程序，對(duì)于出現(xiàn)不同情況應(yīng)能夠正確處理，比如對(duì)本題而言，是對(duì)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判?。若?jīng)過(guò)錯(cuò)誤的構(gòu)造，該圖是有環(huán)圖，則應(yīng)該提示該圖是有環(huán)圖，并自動(dòng)重新輸入該圖，開(kāi)始的時(shí)候由于缺乏考慮，會(huì)導(dǎo)致有環(huán)圖也像無(wú)環(huán)圖一樣進(jìn)行“拓?fù)渑判颉?。4. 程序應(yīng)該條例清晰，結(jié)構(gòu)明朗，各個(gè)函數(shù)代表各個(gè)模塊，起到不同的作用，并協(xié)調(diào)運(yùn)作，形成含有不同功能的程序。開(kāi)始時(shí)因?yàn)槌绦虻慕Y(jié)構(gòu)混亂而導(dǎo)致很難調(diào)試，無(wú)法找到錯(cuò)誤的根源。4.24.2 程序執(zhí)行過(guò)程程序執(zhí)行過(guò)程1. 對(duì)于有向無(wú)環(huán)圖，以圖 4.2

16、.1 為例進(jìn)行拓?fù)渑判颍?1 24356沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 9 圖 4.1 有向無(wú)環(huán)圖程序運(yùn)行結(jié)果如圖 4.2.2 所示：圖 4.2 有向無(wú)環(huán)圖拓?fù)渑判?. 對(duì)于有向有環(huán)圖，以圖 4.2.3 為例：圖 4.3 有向有環(huán)圖程序運(yùn)行結(jié)果如圖 4.2.4 所示： 1 24356沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 10 圖 4.4 有向有環(huán)圖程序運(yùn)行結(jié)果沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 11 參考文獻(xiàn)參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民. .數(shù)據(jù)結(jié)構(gòu)m.北京：清華大學(xué)出版社，2007.2 張長(zhǎng)海，陳娟. .c 程序設(shè)計(jì)m.北京：高等教育出版社，2004. 3 譚浩強(qiáng). .c 程序設(shè)計(jì)m.北京：清華大學(xué)出版社，2

17、005.沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 12 總結(jié)課程設(shè)計(jì)總結(jié)：課程設(shè)計(jì)總結(jié)：每一次課設(shè)都是對(duì)自己綜合能力的提高，這次也不例外。數(shù)據(jù)結(jié)構(gòu)是一門應(yīng)用性很高的基礎(chǔ)課程。通過(guò)課設(shè)，我收到到了一下幾個(gè)方面1. 通過(guò)此次課設(shè)，我恢復(fù)了基礎(chǔ)的 c 語(yǔ)言編程能力，并在此基礎(chǔ)上，利用數(shù)據(jù)結(jié)構(gòu)，能夠變出更具有實(shí)用性，也具有更復(fù)雜功能的程序。很多以前想象不到的功能，通過(guò)數(shù)據(jù)結(jié)構(gòu)巧妙的安排，也可以輕松實(shí)現(xiàn)。2. 通過(guò)此次課設(shè)，我鍛煉了自己獨(dú)立思考的能力。以前總是不相信自己，能夠把一個(gè)問(wèn)題思考的有多深?，F(xiàn)在，通過(guò)獨(dú)立的思考，哪怕是一段漫長(zhǎng)的時(shí)間得到的是對(duì)知識(shí)更為深刻的理解。3. 通過(guò)此次課設(shè)，我能夠借閱資料。通過(guò)更為廣

18、泛的尋找來(lái)為自己獲得啟發(fā)。通過(guò)請(qǐng)教他人，運(yùn)用合作意識(shí)，讓自己的做事效率更高。為自己增添信心。4. 它讓我學(xué)到很多。雖然課設(shè)時(shí)間很短，但收獲卻是別的方式無(wú)法擁有的，因?yàn)樗屛野阎皇沁\(yùn)用于實(shí)踐，把思考當(dāng)做一種享受，其樂(lè)趣是無(wú)窮的，它對(duì)我的影響很深遠(yuǎn)。指導(dǎo)教師評(píng)語(yǔ)：指導(dǎo)教師(簽字)： 年 月 日課程設(shè)計(jì)成績(jī)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 13 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）程序代碼程序代碼#include stdafx.h#include stdio.h#include stdlib.h#define maximum 20int graphmaximummaximum;int di

19、stmaximum; / 表示當(dāng)前點(diǎn)到源點(diǎn)的最短路徑長(zhǎng)度int visitedmaximum;int queuemaximum;int l;int jj=0;typedef struct nodeint data;struct node *next;graphnode;graphnode vexsmaximum; /頂點(diǎn)數(shù)組int rear=-1;int front=-1;int queuemaximum;void addqueue(int *queue,int x)/入隊(duì)操作if(rear=l-1)printf(隊(duì)列已滿n);return;rear+;queuerear=x;return;i

20、nt delqueue(int *queue)/出隊(duì)操作int e;if(rear=front)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 14 return -2; front+;e=queuefront;queuefront=0;return e;void createadjacenttable(int v1,int v2)graphnode *newnode;newnode=(graphnode *)malloc(sizeof(graphnode);newnode-data=v2+1;newnode-next=null;graphnode *p;p=&vexsv1;while(p-next!=

21、null)p=p-next;p-next=newnode;void toposort(int *visited,int *queue)int i;rear=-1;front=-1;int topnum=0;int mlmaximum;int n=0;graphnode *p;for(i=0;inext;while(p!=null)visited(p-data)-1+;p=p-next;while(topnum!=l)for(i=0;inext;while(p!=null)visited(p-data)-1-;p=p-next;visitedi=-1;topnum+;for(i=0;il;i+)mli=delqueue(queue);for(i=0;il;i+)if(mli=-2)printf(您輸入的圖為有環(huán)圖,請(qǐng)重新輸入!n);break;elsen=n+1;if(n=l) printf(拓?fù)渑判驗(yàn)椋簄);for(i=0;i);jj=1;printf(n);void main()int graphmaximumma