數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-拓撲排序備課講稿

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——拓撲排序精品文檔課程設(shè)計任務(wù)書學(xué)生姓名： 專業(yè)班級：指導(dǎo)教師： 工作單位： 計算機科學(xué)系題 目: 拓撲排序初始條件：1）采用鄰接表作為有向圖的存儲結(jié)構(gòu)；2）給出所有可能的拓撲序列。（3）測試用例見嚴蔚敏《數(shù)據(jù)結(jié)構(gòu)習(xí)題集 (C語言版)》p48題7.9圖要求完成的主要任務(wù) :（包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）課程設(shè)計報告按學(xué)校規(guī)定格式用 A4紙打?。〞鴮懀?，并應(yīng)包含如下內(nèi)容：問題描述簡述題目要解決的問題是什么。設(shè)計存儲結(jié)構(gòu)設(shè)計、主要算法設(shè)計（用類 C/C++語言或用框圖描述）、測試用例設(shè)計；調(diào)試報告調(diào)試過程中遇到的問題是如何解決的；對設(shè)計和編碼的討論和分析。經(jīng)驗和體會（包括對算法改進的設(shè)想）附源程序清單和運行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運行結(jié)果要包含這些測試數(shù)據(jù)和運行輸出。說明：設(shè)計報告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。2. 凡拷貝往年任務(wù)書或課程設(shè)計充數(shù)者，成績一律無效，以 0分記。時間安排：1．第17周完成，驗收時間由指導(dǎo)教師指定2．驗收地點：實驗中心3．驗收內(nèi)容：可執(zhí)行程序與源代碼、課程設(shè)計報告書。指導(dǎo)教師簽名：2013年6月14日收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔系主任（或責(zé)任教師）簽名： 年 月 日拓撲排序目錄問題描述具體設(shè)計2.1存儲結(jié)構(gòu)設(shè)計2.2主要算法設(shè)計拓撲排序的算法總體設(shè)計將有向圖表示為鄰接表拓撲排序函數(shù)的設(shè)計順序表的運算設(shè)計2.3測試用例設(shè)計調(diào)試報告3.1設(shè)計和編碼的分析3.2調(diào)試過程問題及解決經(jīng)驗與體會用戶使用說明參考文獻收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔附錄源代碼與運行結(jié)果問題描述題目：拓撲排序如果用有向圖表示一個工程，在這種有向圖中，用頂點表示活動，用有向邊<vi,vj>表示活動vi必須先于活動 vj進行，這種有向圖叫做頂點表示活動的網(wǎng)絡(luò)，記作AOV網(wǎng)絡(luò)。對一個有向無環(huán)圖 G進行拓撲排序，是將 G中所有頂點排成一個線性序列，使得AOV網(wǎng)絡(luò)中的所有應(yīng)存在前驅(qū)和后繼的關(guān)系都能得到滿足，這種構(gòu)造 AOV網(wǎng)絡(luò)全部頂點的拓撲有序序列的運算叫做拓撲排序。在AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，用拓撲排序就可以判斷網(wǎng)中是否有環(huán)，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該 AOV-網(wǎng)必定不存在環(huán)。進行拓撲排序步驟如下：1、輸入AOV網(wǎng)絡(luò)即有向圖。令 n為頂點個數(shù)。2、從有向圖上選擇一個沒有入度的節(jié)點并輸出。3、從網(wǎng)中刪去該點，同時刪去從該頂點發(fā)出的全部有向邊。4、重復(fù)上述2，3，直到1）、全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成。2）、圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了，這時AOV網(wǎng)絡(luò)中必定存在有向環(huán)。要求：1）、采用鄰接表作為有向圖的存儲結(jié)構(gòu)；2）、給出所有可能的拓撲序列。具體設(shè)計2.1存儲結(jié)構(gòu)設(shè)計本問題中，我將采用三種數(shù)據(jù)結(jié)構(gòu)：鄰接表，順序表和數(shù)組。<1>鄰接表：鄰接表是圖的鏈式存儲結(jié)構(gòu)，在鄰接表的存儲結(jié)構(gòu)中，圖中的每個收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除//鄰接表類型精品文檔頂點對應(yīng)一個單鏈表。從拓撲排序的步驟個方法來看，在整個排序過程中需要頻繁地檢查頂點的前驅(qū)以及作刪除頂點和邊的操作、恢復(fù)頂點和頂點前驅(qū)入度的操作。所以，可以采用鄰接表作為有向無環(huán)圖的存儲結(jié)構(gòu)。為了快速的判斷頂點是否有前驅(qū)，可以在表頭結(jié)點中增加一個“入度域into）”用來指示頂點當前的入度。當into域的值為0時，表明該頂點沒有前驅(qū)，可以加入到結(jié)果序列中。而刪除頂點及以它為起點的邊操作時，可以通過把該頂點的所有鄰接點的入度域減一來完成，恢復(fù)則入度域加一。鄰接表的定義如下：typedefstructARCNODE{ //表結(jié)點intadjvex; //鄰接點的位置ARCNODE*nextarc;//指向下一個結(jié)點}ARCNODE; //鄰接表中的結(jié)點類型typedefstructVEXNODE{ //頭結(jié)點intvexdata; //頂點信息intinto; //每個頂點的入度ARCNODE*firstarc;//指向第一個鄰接結(jié)點}VEXNODE,AdjList[MAX];//鄰接表的表頭結(jié)點類型typedefstruct{AdjListvexs; //表頭結(jié)點數(shù)組intvexnum,arcnum;//頂點數(shù)、邊數(shù)}ALGraph;<2>順序表：在整個拓撲排序的過程中，把滿足條件（在此輪中未訪問過visited[i]=0以及入度為0）的頂點加入到順序表的末尾，使 last加1。當一輪排序結(jié)束后，輸出順序表中的排序。接著，是恢復(fù)部分，每恢復(fù)一步，都要把 visit[i]置0并且相應(yīng)的入度加 1，把這個頂點從順序表中刪除，重新加入到圖中，進行下一輪的拓撲排序。鄰接表的順序表定義如下：typedefstruct{收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔VEXNODEdata[MAX];intlast;}Sequenlist; //順序表類型<2>數(shù)組：產(chǎn)生所有的拓撲排序是一個遞歸（回溯）過程。其中，定義的visited[MAX]數(shù)組是一個輔助變量，數(shù)組元素的初值為0，當?shù)趇個頂點被訪問后，便置visited[i]為1.記錄該頂點是否被訪問過。Visited[MAX]；2.2主要算法設(shè)計拓撲排序的算法總體設(shè)計因為這個課程設(shè)計題目是讓AOV網(wǎng)絡(luò)產(chǎn)生所有的拓撲排序，所以我想必然要用到遞歸或者回溯的思想?？紤]到要不斷的對數(shù)據(jù)進行刪除，恢復(fù)，所以考慮了順序表，單鏈表，堆棧，發(fā)現(xiàn)用順序表刪除和插入都很簡單，好實施，只要在表尾插入或是刪除即可。在整個過程中主要用到三部分：一、從圖中刪除，添加到順序表中；二、遞歸；三、把刪除的頂點和邊恢復(fù)到圖中并從順序表中刪除。首先，在整個圖中搜索即沒有被訪問過而且入度為 0的頂點Vi，進行拓撲排序。在拓撲排序的函數(shù)里，首先將這個頂點加入到順序表中，然后將這個頂點標志為被訪問過，即Visited[i]=1。把以這個頂點為起點的鄰接點的入度均減1.然后，判斷順序表的表長是否等于圖的頂點數(shù)。如果不相等的話，則繼續(xù)判斷圖中是否還存在滿足拓撲排序條件的頂點，若存在就再次調(diào)用拓撲排序函數(shù)。接下來，就是使剛排序過的頂點Vi的標志恢復(fù)到原始狀態(tài)0，每個以Vi為起點的鄰接點的入度加1，恢復(fù)到原來的狀態(tài)。把頂點Vi從順序表中刪除。如果，順序表的表長等于圖的頂點數(shù)，那么就輸出這一種拓撲排序序列。計數(shù)器count加1之后，就是采用遞歸，不斷的調(diào)用拓撲排序函數(shù)，不斷的恢復(fù)、刪除，直到排出所有的拓撲序列。最后，如果 count大于0的話，那么就輸出有 count種拓撲排序。否則，輸出此圖不是AOV網(wǎng)，無拓撲排序序列產(chǎn)生。收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔開始置空順序表A，表長賦初值用鄰接表建立圖 G，調(diào)用i賦初值0初始化標志數(shù)組，visited[i]置0i的值遞增1Yi<G.頂點NJ賦初值0NVisited[j]=0 且Vj入度為0？Y調(diào)用函數(shù)Topusort(G,L,i);j的值遞增1Yj<G.頂點數(shù)？NYCount>0？N此圖不是AOV網(wǎng)，無拓撲排序該圖有count種排序結(jié)束收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔將有向圖表示為鄰接表在產(chǎn)生拓撲排序的算法設(shè)計中，首先要將有向圖用鄰接表表示，主要流程如下：開始定義表頭結(jié)點數(shù)組 al輸入頂點數(shù)n和邊數(shù)e初始化al的各項值：al[i].vexdata=i;al[i].into=0;al[i].firstarc=NULL;（i=0to圖的頂點數(shù)）輸入e條邊的起點值j和終點值將Vk的入度加一，并將結(jié)點Vk加入到鏈表中；邊數(shù)從0到e定義圖algn=alg.vexnum頂點數(shù)；e=alg.arcnum邊數(shù)i賦初值0將al[]中的值、入度、指針分別賦給圖alg中數(shù)組vexs[]的.各的值遞增1Yi<結(jié)點數(shù)N結(jié)束收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔拓撲排序函數(shù)的設(shè)計開始插入SqLinsert(L,vexs[i])標志數(shù)visited[i]賦初值Vi指向第一個結(jié)點指針 PP!=NULL？YNP指向頂點Vj順序表長=頂點Vj的入度減1數(shù)？P指向鏈表下一結(jié)點輸出Output(L)計數(shù)器Count加K賦初值0Visited[k]==0且Vk入度為0？調(diào)用函數(shù)Topusort(L,G,k);K的值遞增1Yk<頂點數(shù)？N收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔Vi指向的第一個結(jié)點的指針 PYP！=NULL？N P指向頂點VjVj的入度加1P指向鏈表下一結(jié)點調(diào)用刪除函數(shù)SqLdelete(L,vexs[i])結(jié)束順序表的運算設(shè)計收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔開始定義順序表A順序表置空：setnull()表長L->last+1賦初值0插入：SqLinsert(L,vexs[i])

輸出：output(L);

刪 除：SqLdelete(L,vexs[i表長加1

I賦初值0即L->last+1輸出Vi把結(jié)點X賦給順序表I的值遞增1最后一位L->r[L-Yi<表長?N結(jié)束

表長減1；L->last-1收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔2.3測試用例設(shè)計21 43圖121 43圖231 46725圖3收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除1

精品文檔32 456圖4調(diào)試報告3.1設(shè)計和編碼的分析1、鄰接表實現(xiàn)拓撲序列 shixian()在本函數(shù)里，首先定義一個順序表，然后把它置空。接著，以鄰接表創(chuàng)建一個圖，并且把它賦給圖 G。接著，把全局變量數(shù)組 visited[]初始化。對于整個圖中，沒被訪問過的而且入度為0的頂點進行拓撲排序。如果常量 count等于0的話，說明圖有回路，不能拓撲排序。否則，在拓撲排序函數(shù)中會輸出所有的拓撲排序序列。voidshixian(){SequenlistA,*L=&A;L=(Sequenlist*)malloc(sizeof(Sequenlist));Setnull(L);ALGraphG;G=creatGraph();for(intn=1;n<=G.vexnum;n++){visited[n]=0;}inti;cout<<"該圖的所有拓撲排序為： "<<endl;for(i=1;i<=G.vexnum;i++)if((G.vexs[i].into==0)&&(visited[i]==0))收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔topusort(L,G,i);if(count<=0)cout<<"您輸入的圖不是有向無環(huán)圖，故無拓撲排序序列產(chǎn)生 ."<<endl;else{cout<<"此圖有"<<count<<"種拓撲排序\n\n";count=0;}}2、鄰接表的主要算法拓撲排序 topusort()voidtopusort(Sequenlist*L,ALGraphG,inti){intj,k;SqLinsert(L,G.vexs[i]); //把頂點Vi加入到順序表中P=G.vexs[i].firstarc;visited[i]=1; //把排序過的點標記while(P!=NULL){j=P->adjvex;G.vexs[j].into--;//把以Vi為頭的終止結(jié)點入度減 1P=P->nextarc;}for(k=1;k<=G.vexnum;k++)if((visited[k]==0)&&(G.vexs[k].into==0))// 如果Vk在此輪中未被訪問過且入度為 0topusort(L,G,k);if(L->last==G.vexnum) //判斷順序表中一種拓撲排序完成{output(L);cout<<endl;count++;}visited[i]=0;//使Vi恢復(fù)為未訪問while(P!=NULL)收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔{j=P->adjvex;G.vexs[j].into++;//使Vj的入度恢復(fù)P=P->nextarc;}SqLdelete(L,G.vexs[i]);}3、順序表函數(shù)在這個設(shè)計中，只有順序表的簡單應(yīng)用，置空，插入，刪除和輸出。插入和刪除都只是在表尾插入和刪除。即只要把表長加1或是減1.Sequenlist*Setnull(Sequenlist*L)//順序表置空{(diào)L->last=0;return(L);}voidSqLinsert(Sequenlist*L,VEXNODEx)//在順序表尾插入新接點{L->last=L->last+1;L->data[L->last]=x;}voidSqLdelete(Sequenlist*L,VEXNODEx)//刪除順序表中的最后一個節(jié)點{L->last=L->last-1;}intcount=0;voidoutput(Sequenlist*L) //輸出順序表中的元素{inti;for(i=1;i<=L->last;i++){if(i<L->last)收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔cout<<"V"<<L->data[i].vexdata<<"----->";elsecout<<"V"<<L->data[i].vexdata;}cout<<endl<<endl;}3.2調(diào)試過程問題及解決在調(diào)試的過程中出現(xiàn)了很多語法錯誤，如：開始沒有申明 iostream頭文件，導(dǎo)致所有的<<，>>輸入輸出流都是錯誤的，還有errorC2562:'main':'void'functionreturningavalue，發(fā)現(xiàn)main函數(shù)被我定義為了void返回類型，可是我在函數(shù)語句里又使用了return0；把main函數(shù)的返回值改成int即可，還有其他的語法錯誤都根據(jù)提示一一改進了。接著，我發(fā)現(xiàn)無論如何輸出的結(jié)果都是零種排序，于是找到了 ALGraphcreatGraph()函數(shù)的一組賦值語句，開始我是這樣寫的“G.vexs=al;”后來改成for(i=0;i<alg.vexnum;i++){alg.vexs[i].vexdata=al[i].vexdata;alg.vexs[i].indegree=al[i].indegree;alg.vexs[i].firstarc=al[i].firstarc;}再次運行時，輸出結(jié)果還是不對。最后發(fā)現(xiàn)在 for語句前少了alg.vexnum=n;alg.arcnum=e;賦值語句。在topusort函數(shù)中下列語句使得運行結(jié)果一直為您輸入的圖不是有向無環(huán)圖，故無拓撲排序序列產(chǎn)生.for(k=1;k<=G.vexnum;k++)if((visited[k]==0)&&(G.vexs[k].into==0))//如果Vk在此輪中未被訪問過且入度為0{if(L->last==G.vexnum) //判斷順序表中一種拓撲排序完成{output(L);cout<<endl;count++;}收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔topusort(L,G,k);}改成如下代碼即可：for(k=1;k<=G.vexnum;k++)if((visited[k]==0)&&(G.vexs[k].into==0))// 如果Vk在此輪中未被訪問過且入度為 0topusort(L,G,k);if(L->last==G.vexnum) //判斷順序表中一種拓撲排序完成{output(L);cout<<endl;count++;}經(jīng)驗與體會此次課程設(shè)計為拓撲排序，利用c++語言實現(xiàn)的，此算法還有多發(fā)面可以改進，比如圖的表示利用的是鄰接表，還可以在代碼中增加鄰接矩陣的表示方法，使得對于兩種形式表示的圖都可以進行拓撲排序，還有在代碼中并沒有把鄰接表很直觀的輸出給用戶，如果可以編寫代碼把鄰接表很直觀的輸出，會更有可讀性。在執(zhí)行的過程中發(fā)現(xiàn)對于大量的數(shù)據(jù)，比如邊比較復(fù)雜的情況，程序執(zhí)行就有可能會崩潰，說明程序的健壯性還有待提高。通過五天的課程設(shè)計，我鞏固了以前學(xué)過的知識，懂得了理論與實際相結(jié)合的重要性，只有理論知識是遠遠不夠的，理論知識是為將來的實踐服務(wù)的，理論知識很重要，實踐活動更重要。通過課程設(shè)計我看到自己實際操作能力的嚴重不足，知識理解不夠深刻，掌握不夠牢固，編程基礎(chǔ)薄弱，沒有耐心。在同學(xué)和相關(guān)資料的幫助下，最終完成了代碼。通過這次設(shè)計，我看到自身學(xué)習(xí)方法存在很多錯誤，我決心在以后的學(xué)習(xí)過程中，要多鍛煉自己處理實際問題的能力，要提高獨立分析問題和解決問題的能力，多動手多上機操作。并且利用假期時間進一步鞏固數(shù)據(jù)結(jié)構(gòu)課程與C++語言基礎(chǔ)，為今后的學(xué)習(xí)打下比較堅實的基礎(chǔ)。收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔用戶使用說明運行后，根據(jù)提示，“請輸入結(jié)點數(shù)”,即輸入圖的頂點數(shù)目，“請入邊總數(shù)數(shù)”，即輸入圖的邊數(shù)；接著依次輸入每條邊的起始點序號和終止點序號即可，輸出結(jié)果就可以一目了然。例如：請輸入頂點數(shù)：4請輸入弧數(shù)：4請輸入邊的信息：請輸入第一條邊：12請輸入第二條邊：13請輸入第三條邊：23請輸入第四條邊：346參考文獻：嚴蔚敏，吳偉民。數(shù)據(jù)結(jié)構(gòu)題集(c語言)。清華大學(xué)出版社，2011年11月。殷人昆。數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++語言描述)(第2版)。清華大學(xué)出版社，2007年6月附錄源代碼與運行結(jié)果源程序代碼（c++語言）#include<stdio.h>#include<string.h>#include<malloc.h>#include<iostream.h>#defineNULL0收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔#definemaxlen100typedefstructARCNODE//表結(jié)點{intadjvex;//接鄰點的位置ARCNODE*nextarc;//指向下一個結(jié)點}ARCNODE; //鄰接表中的結(jié)點類型typedefstructVEXNODE//頭結(jié)點{intvexdata;//頂點的位置intinto;//頂點的入度ARCNODE*firstarc;//指向第一個鄰接結(jié)點}VEXNODE,AdjList[maxlen];// 表頭結(jié)點類型typedefstruct{AdjListvexs;//表頭結(jié)點數(shù)組intvexnum,arcnum;//頂點數(shù)、邊數(shù)}ALGraph;//鄰接表類型typedefstruct{VEXNODEdata[maxlen];intlast;}Sequenlist; //順序表類型typedefstruct{intdata[maxlen];intlast;}Seqlist;//順序表收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔ALGraphcreatGraph(){intn,e,i,j,k;ARCNODE*p;AdjListal;cout<<endl;cout<<"------------------------拓撲排序----------------------"<<endl<<endl;cout<<"請輸入結(jié)點數(shù):";cin>>n;for(i=1;i<=n;i++) //初始化表頭結(jié)點數(shù)組{al[i].vexdata=i;al[i].into=0;al[i].firstarc=NULL;}cout<<"請輸入邊總數(shù):";cin>>e;cout<<"請依次輸入邊的信息:"<<endl;for(i=1;i<=e;i++){cout<<"請輸入第"<<i<<"條邊:";cin>>j>>k; //依次讀入邊的信息p=(ARCNODE*)malloc(sizeof(ARCNODE));p->adjvex=k;al[k].into++; //把終止結(jié)點的入度加 1p->nextarc=al[j].firstarc; //用頭插法把p插入到鏈表中al[j].firstarc=p;}cout<<endl;ALGraphalg;alg.vexnum=n;收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔alg.arcnum=e;for(i=1;i<=alg.vexnum;i++)//把頭結(jié)點表頭數(shù)組的值賦給鄰接表表頭數(shù)組{alg.vexs[i].vexdata=al[i].vexdata;alg.vexs[i].into=al[i].into;alg.vexs[i].firstarc=al[i].firstarc;}returnalg;}Sequenlist*Setnull(Sequenlist*L)//順序表置空{(diào)L->last=0;return(L);}voidSqLinsert(Sequenlist*L,VEXNODEx)//在順序表尾插入新接點{L->last=L->last+1;L->data[L->last]=x;}voidSqLdelete(Sequenlist*L,VEXNODEx)//刪除順序表中的最后一個節(jié)點{L->last=L->last-1;}intcount=0;voidoutput(Sequenlist*L) //輸出順序表中的元素{inti;for(i=1;i<=L->last;i++){if(i<L->last)cout<<"V"<<L->data[i].vexdata<<"----->";elsecout<<"V"<<L->data[i].vexdata;收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔}cout<<endl<<endl;}ARCNODE*P;intn;intvisited[maxlen];voidtopusort(Sequenlist*L,ALGraphG,inti){intj,k;SqLinsert(L,G.vexs[i]); //把頂點Vi加入到順序表中P=G.vexs[i].firstarc;visited[i]=1; //把排序過的點標記while(P!=NULL){j=P->adjv