上傳人：灰***

認(rèn)證信息

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

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

IP屬地：寧夏

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

91640100MA774ECW4K

IP屬地：寧夏 上傳時間：2021-10-13 格式：DOC 頁數(shù)：20 大小：223.50KB 積分：10.8 舉報 版權(quán)申訴

1、 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計報告課程設(shè)計報告 題目：題目： 拓?fù)渑判蛩惴ㄍ負(fù)渑判蛩惴?院（系）：理學(xué)院院（系）：理學(xué)院 專專 業(yè)：信息與計算科學(xué)業(yè)：信息與計算科學(xué) 班班 級：級： 94140101 學(xué)學(xué) 號：號： 姓姓 名：名： 指導(dǎo)教師：指導(dǎo)教師： 2011 年年 12 月月 目目 錄錄 1 1 課程設(shè)計介紹課程設(shè)計介紹.1 1.1 課程設(shè)計內(nèi)容.1 1.2 課程設(shè)計要求.1 2 2 課程設(shè)計原理課程設(shè)計原理.2 2.1 課設(shè)題目粗略分析.2 2.2 原理圖介紹.3 2.2.1 功能模塊圖.3 2.2.2 流程圖分析.3 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析.5 3.1 存儲結(jié)構(gòu).5 3.2 算法描

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

3、。 2 2 課程設(shè)計原理課程設(shè)計原理 2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析 本課設(shè)題目要求編寫算法能夠建立有向無環(huán)圖，有向無環(huán)圖，顧名思義，即一個 無環(huán)的有向圖，是一類較有向圖更一般的特殊有向圖。 其功能要求及個人在寫程序時對該功能的實現(xiàn)作如下分析： 1. 將圖以合適的方式存儲起來。圖有多種存儲方式，其中最常用的存儲方式有 圖的鄰接矩陣和鄰接表。本人在構(gòu)思時使用鄰接表來建立有向無環(huán)圖，將其存儲 起來； 2. 求解該有向無環(huán)圖的拓?fù)渑判?，并將其輸出出來。若通過構(gòu)造，建立了一個 有向無環(huán)圖，那么一定可以求出其拓?fù)渑判?，其原理比較簡單。即統(tǒng)計每個節(jié)點 的入度，將入度為 0 的結(jié)點提取出來，

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

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

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

7、否否 是是 入度為零入隊列入度為零入隊列 滿隊列滿隊列 是是 循環(huán)出隊列循環(huán)出隊列 調(diào)整調(diào)整 visited 否否 結(jié)束結(jié)束 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析 3.13.1 存儲結(jié)構(gòu)存儲結(jié)構(gòu) 一個無環(huán)的有向圖叫做有向無環(huán)圖，簡稱 dag 圖。本算法首先要建立一個 有向五環(huán)圖，即通過輸入各邊的數(shù)據(jù)，搭建圖的結(jié)構(gòu)。 對于圖的存儲，用到鄰接表，是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。 typedef struct node int data; struct node *next; graphnode; graphnode vexsmaximum; 對于用來排序的隊列，則用到了順序存儲結(jié)構(gòu)的隊列，用數(shù)組表示。queue in

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

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

10、。 （1） 隊列初始化： void addqueue(int *queue,int x)/入隊操作 if(rear=l-1) printf(隊列已滿n); return; rear+; queuerear=x; return; （2） 出隊操作： int delqueue(int *queue)/出隊操作 int e; if(rear=front) return -2; front+; e=queuefront; queuefront=0; return e; 3. 拓?fù)渑判?本程序的拓?fù)渑判?，必須在圖的鄰接表已知的情況下。它還有另外一個功能： 判斷一個圖是不是無環(huán)圖。確切的說，不能單純的叫拓

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

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

13、后，然后依次出隊列，queuevisited 拓?fù)渑判蛲瓿伞?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

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

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

16、執(zhí)行過程 1. 對于有向無環(huán)圖，以圖 4.2.1 為例進行拓?fù)渑判颍?1 2 4 3 5 6 圖 4.1 有向無環(huán)圖 程序運行結(jié)果如圖 4.2.2 所示： 圖 4.2 有向無環(huán)圖拓?fù)渑判?2. 對于有向有環(huán)圖，以圖 4.2.3 為例： 圖 4.3 有向有環(huán)圖 程序運行結(jié)果如圖 4.2.4 所示： 1 2 4 3 5 6 圖 4.4 有向有環(huán)圖程序運行結(jié)果 參考文獻參考文獻 1 嚴(yán)蔚敏，吳偉民. .數(shù)據(jù)結(jié)構(gòu)m.北京：清華大學(xué)出版社，2007. 2 張長海，陳娟. .c 程序設(shè)計m.北京：高等教育出版社，2004. 3 譚浩強. .c 程序設(shè)計m.北京：清華大學(xué)出版社，2005. 總結(jié) 課程設(shè)計總

17、結(jié)：課程設(shè)計總結(jié)： 每一次課設(shè)都是對自己綜合能力的提高，這次也不例外。數(shù)據(jù)結(jié)構(gòu)是 一門應(yīng)用性很高的基礎(chǔ)課程。通過課設(shè)，我收到到了一下幾個方面 1. 通過此次課設(shè)，我恢復(fù)了基礎(chǔ)的 c 語言編程能力，并在此基礎(chǔ)上， 利用數(shù)據(jù)結(jié)構(gòu)，能夠變出更具有實用性，也具有更復(fù)雜功能的程序。很多 以前想象不到的功能，通過數(shù)據(jù)結(jié)構(gòu)巧妙的安排，也可以輕松實現(xiàn)。 2. 通過此次課設(shè)，我鍛煉了自己獨立思考的能力。以前總是不相信自 己，能夠把一個問題思考的有多深?，F(xiàn)在，通過獨立的思考，哪怕是一段 漫長的時間得到的是對知識更為深刻的理解。 3. 通過此次課設(shè)，我能夠借閱資料。通過更為廣泛的尋找來為自己獲 得啟發(fā)。通過請教他人

18、，運用合作意識，讓自己的做事效率更高。為自己 增添信心。 4. 它讓我學(xué)到很多。雖然課設(shè)時間很短，但收獲卻是別的方式無法擁 有的，因為它讓我把只是運用于實踐，把思考當(dāng)做一種享受，其樂趣是無 窮的，它對我的影響很深遠。 指導(dǎo)教師評語： 指導(dǎo)教師(簽字)： 年 月 日 課程設(shè)計成績 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單） 程序代碼程序代碼 #include stdafx.h #include stdio.h #include stdlib.h #define maximum 20 int graphmaximummaximum; int distmaximum; / 表示當(dāng)前點到源點的

19、最短路徑長度 int visitedmaximum; int queuemaximum; int l; int jj=0; typedef struct node int data; struct node *next; graphnode; graphnode vexsmaximum; /頂點數(shù)組 int rear=-1; int front=-1; int queuemaximum; void addqueue(int *queue,int x)/入隊操作 if(rear=l-1) printf(隊列已滿n); return; rear+; queuerear=x; return; int

20、 delqueue(int *queue)/出隊操作 int e; if(rear=front) 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= while(p-next!=null) p=p-next; p-n

21、ext=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)圖,請重新輸入!n); break; else n=n+1;