數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-拓撲問題

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目:拓撲排序 學院：班級：學生姓名：學生學號：指導(dǎo)教師：課程設(shè)計任務(wù)書姓名班級學號設(shè)計題目拓撲排序理論要點拓撲排序是指由某個集合上的一個偏序得到該集合上的一個全序。更直觀地講，一個偏序是自反的、反對稱的，用圖表示時每個點都有環(huán)且只有單向邊。設(shè)計目標拓撲排序的任務(wù)是在這個偏序上得到一個全序，即得到一個完成整個項目的各步驟的序列。研究方法步驟在有向圖中選一個沒有前驅(qū)的頂點且輸出之。從圖中刪除該頂點和所有以它為尾的弧。預(yù)期結(jié)果直至全部頂點均已輸出，或者當前圖中不存在無前驅(qū)的頂點。計劃與進步的安排按時并分部完成任務(wù)。PAGEII摘要拓撲排序是有向無環(huán)圖的一種重要應(yīng)用,實現(xiàn)算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切,本文以鄰接表作為圖的存儲結(jié)構(gòu),詳細討論了拓撲排序算法在計算機上的實現(xiàn)方法,并對該算法作了必要的分析。關(guān)鍵詞拓撲排序，有向無環(huán)圖，鄰接表目錄摘要 I課程設(shè)計題目 11需求分析 12概要設(shè)計 13詳細設(shè)計 14調(diào)試分析 35用戶使用說明 36測試結(jié)果 87結(jié)論 10參考文獻 11數(shù)據(jù)結(jié)構(gòu)課程設(shè)計13-拓撲排序1.需求分析拓撲排序是指由某個集合上的一個偏序得到該集合上的一個全序。更直觀地講，一個偏序是自反的、反對稱的，用圖表示時每個點都有環(huán)且只有單向邊。拓撲排序的任務(wù)是在這個偏序上得到一個全序，即得到一個完成整個項目的各步驟的序列。2．概要設(shè)計：說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。概要設(shè)計（1）在有向圖中選一個沒有前驅(qū)的頂點且輸出之。（2）從圖中刪除該頂點和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點均已輸出，或者當前圖中不存在無前驅(qū)的頂點為止。后一種情況則說明有向圖中存在環(huán)。具體的算法實現(xiàn)參照源程序。3.詳細設(shè)計構(gòu)造鄰接表圖：typedefstruct{ AdjListvertices; intvexnum,arcnum;}Graph;//鄰接表圖為了避免重復(fù)檢測入度為零的頂點，源程序中設(shè)了一個棧，暫存所有入度為零的頂點：typedefstructstack{int*base; int*top; intstacksize;}sqstack;//棧的結(jié)構(gòu)，存儲圖的頂點序號算法的流程圖開始設(shè)輔助數(shù)組indegree記錄圖的各頂點的入度值，并將indegree數(shù)組各變量賦初值。輸入圖的頂點數(shù)、邊數(shù)建立一個棧，存儲圖的頂點的序號用鄰接表法建圖，并計算出indegree數(shù)組中各變量值開始設(shè)輔助數(shù)組indegree記錄圖的各頂點的入度值，并將indegree數(shù)組各變量賦初值。輸入圖的頂點數(shù)、邊數(shù)建立一個棧，存儲圖的頂點的序號用鄰接表法建圖，并計算出indegree數(shù)組中各變量值根據(jù)indegree數(shù)組將入度為0的頂點入棧count對輸出頂點計數(shù)0=>count棧不空刪除棧頂元素,賦給icount++將與第i個頂點鏈接的各頂點入度減1輸出第i個頂點值頂點入度為0頂點序號入棧count<G.vexnum輸出“拓撲排序成功”輸出“拓撲排序不成功”結(jié)束4．調(diào)試分析（1）它的時間復(fù)雜度是O(G.vexnum+G.arcnum)。（2）整個程序的關(guān)鍵就是采用尾插法創(chuàng)的鄰接表圖，運用棧來實現(xiàn)各個數(shù)值的輸入輸出及存儲。（3）注意*的使用，并不是什么情況下都用*，它有時候會造成數(shù)據(jù)破壞，利用破壞的值進行運算，結(jié)果可想而知，所以，如果沒返回值時，一般不要用。（4） 為了避免重復(fù)檢測入度為零的頂點，源程序中設(shè)了一個棧，暫存所有入度為零的頂點，此程序段書寫如下： InitStack(S); for(i=0;i<G.vexnum;++i)//建零入度頂點棧S if(!indegree[i])Push(S,i);//入度為0者進棧 count=0;//對輸出頂點計數(shù) while(!StackEmpty(S)){ Pop(S,i);printf(i,G.vertices[i].data);++count;//輸出i號頂點并計數(shù) for(p=G.vertices[i].firstarc;p;p=p->next){ k=p->adj;//對i號頂點的每個鄰接點的入度減1 if(!(--indegree[k]))Push(S,k);//一旦入度為0，則入棧 }//for }//while5．用戶使用說明//采用尾插法創(chuàng)的鄰接圖#include<iostream>usingnamespacestd;constintMAX=20;constintSTACK_INIT_SIZE=100;constintERROR=0;typedefstructstack{int*base;int*top;intstacksize;}sqstack;//棧的結(jié)構(gòu)，存儲圖的頂點序號typedefstructlnode{intadjvex;structlnode*next;}ArcNode;//弧結(jié)點typedefstructnode2{chardata;ArcNode*fristarc;}VNode,AdjList[MAX];//頂點數(shù)組,fristarc指向與頂點鄰接的第一條弧typedefstruct{ AdjListvertices; intvexnum,arcnum;}Graph;//鄰接表圖voidInitstack(sqstack&s){ s.base=newint; if(!s.base) exit(0); s.top=s.base; s.stacksize=STACK_INIT_SIZE;}voidPush(sqstack&s,int&e){ *s.top++=e;}intEmptystack(sqstack&s){ if(s.base==s.top) return1; else return0;}intPop(sqstack&s,int&e){ if(s.base==s.top) returnERROR; e=*--s.top;}voidCreatGraph(Graph&G,int*indegree){inti;cout<<"請輸入圖的頂點數(shù)和弧數(shù)(且頂點數(shù)不能超過"<<MAX<<")"<<endl;cin>>G.vexnum>>G.arcnum; cout<<"請輸入頂點值:"<<endl; for(inti=0;i<G.vexnum;i++)//輸入圖的頂點 { cin>>G.vertices[i].data; G.vertices[i].fristarc=NULL; indegree[i]=0; } for(i=0;i<G.arcnum;i++)//輸入圖的弧 { intm,n; ArcNode*p; cout<<"請輸入第"<<i+1<<"條弧的弧尾和弧頭:"<<endl; cin>>m>>n; p=newArcNode; if(!p) exit(0); indegree[n-1]++;//求每個頂點的入度值 p->adjvex=n-1; p->next=G.vertices[m-1].fristarc; G.vertices[m-1].fristarc=p; }}intToposort(Graph&G,int*indegree){inti; sqstackS; Initstack(S); for(inti=0;i<G.vexnum;i++)//0入度頂點入棧 { if(!indegree[i]) Push(S,i); } intcount=0; while(!Emptystack(S)) { Pop(S,i); cout<<G.vertices[i].data<<""; count++;//記錄輸出的頂點數(shù) for(ArcNode*p=G.vertices[i].fristarc;p;p=p->next)//把與頂點 { //相鄰接的頂點的入度 intk=p->adjvex; if(!(--indegree[k])) Push(S,k); } } if(count<G.vexnum) return0; else return1;} intmain(){GraphG; int*indegree; indegree=newint;CreatGraph(G,indegree); if(!Toposort(G,indegree)) { cout<<endl; cout<<"拓撲排序不成功!"<<endl; } else { cout<<endl; cout<<"拓撲排序成功!"<<endl; } system("pause"); return0;}測試結(jié)果第一組結(jié)果（有向無環(huán)圖）：對應(yīng)的圖如下：115432第二組結(jié)果（有向有環(huán)圖）：對應(yīng)的圖如下：115432結(jié)論做一個課程設(shè)計要注意很多方面，無論是格式，還是書寫的內(nèi)容和要表達的思想都得嚴格要求自己，所以做起來真的不算容易。本次課程設(shè)計涉及了很多知識，由于往日沒有學得很扎實，對某些問題仍然比較疑惑，所以要進行充足的補習。數(shù)據(jù)結(jié)構(gòu)及其算法在解決現(xiàn)實生活中的常見問題和書寫軟件設(shè)計方面上都有著重要的意義，我們應(yīng)該好好掌握它的相關(guān)知識，在以后的學習過程中，更多的去學會如何運用知識。8.參考文獻傅清祥,王曉東.算法與數(shù)據(jù)結(jié)構(gòu),電子工業(yè)出版社,1993嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu),清華大學出版社,1997許卓群,張乃孝,楊冬青.唐世渭?數(shù)據(jù)結(jié)構(gòu)?,高等教育出版社,1988張友生,遠程控制編程技術(shù).電子工業(yè)出版社.2002陸麗娜,伍衛(wèi)國等譯.分布式操作系統(tǒng).電子工業(yè)出版社.2002王達,計算機網(wǎng)絡(luò)遠程訪問與遠程啟動.清華大學出版社.2003課程設(shè)計評閱書課程設(shè)計報告評語：（評閱意見主要對設(shè)計任務(wù)的合理性、規(guī)范性和正確性以及設(shè)計報告書的完整性、規(guī)