數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-拓?fù)鋯栴}

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