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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目:拓撲排序 學院：班級：學生姓名：學生學號：指導(dǎo)教師：2021年12月05日課程設(shè)計任務(wù)書姓名班級學號設(shè)計題目拓撲排序理論要點拓撲排序是指由某個集合上的一個偏序得到該集合上的一個全序。更直觀地講，一個偏序是自反的、反對稱的，用圖表示時每個點都有環(huán)且只有單向邊。設(shè)計目標拓撲排序的任務(wù)是在這個偏序上得到一個全序，即得到一個完成整個項目的各步驟的序列。研究方法步驟在有向圖中選一個沒有前驅(qū)的頂點且輸出之。從圖中刪除該頂點和所有以它為尾的弧。預(yù)期結(jié)果直至全部頂點均已輸出，或者當前圖中不存在無前驅(qū)的頂點。計劃與進步的安排按時并分部完成任務(wù)。PAGEI摘要拓撲排序是有向無環(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è)計2-拓撲排序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),清華大學出版社,2021許卓群,張乃孝,楊冬青.唐世渭?數(shù)據(jù)結(jié)構(gòu)?,高等教育出版社,1988張友生,遠程控制編程技術(shù).電子工業(yè)出版社.2021陸麗娜,伍衛(wèi)國等譯.分布式操作系統(tǒng).電子工業(yè)出版社.2021王達,計算機網(wǎng)絡(luò)遠程訪問與遠程啟動.清華大學出版社.2021課程設(shè)計評閱書課程設(shè)計報告評語：（評閱意見主要對設(shè)計任務(wù)的合理性、規(guī)范性和正確性以及設(shè)計報告書的完整性、規(guī)范性和通順性等方面作出評價）報告成績：答辯記錄與評語：答辯成績：課程設(shè)計總成績：教師簽名：年月日

咖啡店創(chuàng)業(yè)計劃書第一部分：背景在中國，人們越來越愛喝咖啡。隨之而來的咖啡文化充滿生活的每個時刻。無論在家里、還是在辦公室或各種社交場合，人們都在品著咖啡?？Х戎饾u與時尚、現(xiàn)代生活聯(lián)系在一齊。遍布各地的咖啡屋成為人們交談、聽音樂、休息的好地方，咖啡豐富著我們的生活，也縮短了你我之間的距離，咖啡逐漸發(fā)展為一種文化。隨著咖啡這一有著悠久歷史飲品的廣為人知，咖啡正在被越來越多的中國人所理解。第二部分：項目介紹第三部分：創(chuàng)業(yè)優(yōu)勢目前大學校園的這片市場還是空白，競爭壓力小。而且前期投資也不是很高，此刻國家鼓勵大學生畢業(yè)后自主創(chuàng)業(yè)，有一系列的優(yōu)惠政策以及貸款支持。再者大學生往往對未來充滿期望，他們有著年輕的血液、蓬勃的朝氣，以及初生牛犢不怕虎的精神，而這些都是一個創(chuàng)業(yè)者就應(yīng)具備的素質(zhì)。大學生在學校里學到了很多理論性的東西，有著較高層次的技術(shù)優(yōu)勢，現(xiàn)代大學生有創(chuàng)新精神，有對傳統(tǒng)觀念和傳統(tǒng)行業(yè)挑戰(zhàn)的信心和欲望，而這種創(chuàng)新精神也往往造就了大學生創(chuàng)業(yè)的動力源泉，成為成功創(chuàng)業(yè)的精神基礎(chǔ)。大學生創(chuàng)業(yè)的最大好處在于能提高自己的潛力、增長經(jīng)驗，以及學以致用;最大的誘人之處是透過成功創(chuàng)業(yè)，能夠?qū)崿F(xiàn)自己的理想，證明自己的價值。第四部分：預(yù)算1、咖啡店店面費用咖啡店店面是租賃建筑物。與建筑物業(yè)主經(jīng)過協(xié)商，以合同形式達成房屋租賃協(xié)議。協(xié)議資料包括房屋地址、面積、結(jié)構(gòu)、使用年限、租賃費用、支付費用方法等。租賃的優(yōu)點是投資少、回收期限短。預(yù)算10-15平米店面，啟動費用大約在9-12萬元。2、裝修設(shè)計費用咖啡店的滿座率、桌面的周轉(zhuǎn)率以及氣候、節(jié)日等因素對收益影響較大?？Х瑞^的消費卻相對較高，主要針對的也是學生人群，咖啡店布局、格調(diào)及采用何種材料和咖啡店效果圖、平面圖、施工圖的設(shè)計費用，大約6000元左右3、裝修、裝飾費用具體費用包括以下幾種。(1)外墻裝飾費用。包括招牌、墻面、裝飾費用。(2)店內(nèi)裝修費用。包括天花板、油漆、裝飾費用，木工、等費用。(3)其他裝修材料的費用。玻璃、地板、燈具、人工費用也應(yīng)計算在內(nèi)。整體預(yù)算按標準裝修費用為360元/平米，裝修費用共360*15=5400元。4、設(shè)備設(shè)施購買費用具體設(shè)備主要有以下種類。(1)沙發(fā)、桌、椅、貨架。共計2250元(2)音響系統(tǒng)。共計450(3)吧臺所用的烹飪設(shè)備、儲存設(shè)備、洗滌設(shè)備、加工保溫設(shè)備。共計600(4)產(chǎn)品制造使用所需的吧臺、咖啡杯、沖茶器、各種小碟等。共計300凈水機，采用美的品牌，這種凈水器每一天能生產(chǎn)12l純凈水，每一天銷售咖啡及其他飲料100至200杯，價格大約在人民幣1200元上下。咖啡機，咖啡機選取的是電控半自動咖啡機，咖啡機的報價此刻就應(yīng)在人民幣350元左右，加上另外的附件也不會超過1200元。磨豆機，價格在330―480元之間。冰砂機，價格大約是400元一臺，有點要說明的是，最好是買兩臺，不然夏天也許會不夠用。制冰機，從制冰量上來說，一般是要留有富余?？钪票鶛C每一天的制冰量是12kg。價格稍高550元，質(zhì)量較好，所以能夠用很多年，這么算來也是比較合算的。5、首次備貨費用包括購買常用物品及低值易耗品，吧臺用各種咖啡豆、奶、茶、水果、冰淇淋等的費用。大約1000元6、開業(yè)費用開業(yè)費用主要包括以下幾種。(1)營業(yè)執(zhí)照辦理費、登記費、保險費;預(yù)計3000元(2)營銷廣告費用;預(yù)計450元7、周轉(zhuǎn)金開業(yè)初期，咖啡店要準備必須量的流動資金，主要用于咖啡店開業(yè)初期的正常運營。預(yù)計2000元共計： 120000+6000+5400+2250+450+600+300+1200+1200+480+400+550+1000+3000+450+2000=145280元第五部分：發(fā)展計劃1、營業(yè)額計劃那里的營業(yè)額是指咖啡店日常營業(yè)收入的多少。在擬定營業(yè)額目標時，必須要依據(jù)目前市場的狀況，再思考到咖啡店的經(jīng)營方向以及當前的物價情形，予以綜合衡量。按照目前流動人口以及人們對咖啡的喜好預(yù)計每一天的營業(yè)額為400-800，根據(jù)淡旺季的不同可能上下浮動2、采購計劃依據(jù)擬訂的商品計劃，實際展開采購作業(yè)時，為使采購資金得到有效運用以及商品構(gòu)成達成平衡，務(wù)必針對設(shè)定的商品資料排定采購計劃。透過營業(yè)額計劃、商品計劃與采購計劃的確立，我們不難了解，一家咖啡店為了營業(yè)目標的達成，同時有效地完成商品構(gòu)成與靈活地運用采購資金，各項基本的計劃是不可或缺的。當一家咖啡店設(shè)定了營業(yè)計劃、商品計劃及采購計劃之后，即可依照設(shè)定的采購金額進行商品的采購。經(jīng)過進貨手續(xù)檢驗、標價之后，即可寫在菜單上。之后務(wù)必思考的事情，就是如何有效地將這些商品銷售出去。3、人員計劃為了到達設(shè)定的經(jīng)營目標，經(jīng)營者務(wù)必對人員的任用與工作的分派有一個明確的計劃。有效利用人力資源，開展人員培訓，都是我們務(wù)必思考的。4、經(jīng)費計劃經(jīng)營經(jīng)費的分派是管理的重點工作。通常能夠?qū)⒖Х鹊杲?jīng)營經(jīng)費分為人事類費用(薪資、伙食費、獎金等)、設(shè)備類費用(修繕費、折舊、租金等)、維持類費用(水電費、消耗品費、事務(wù)費、雜費等)和營業(yè)類費用(廣告宣傳費、包裝費、營業(yè)稅等)。還能夠依其性質(zhì)劃分成固定費用與變動費用。我們要針對過去的實際業(yè)績設(shè)定可能增加的經(jīng)費幅度。5、財務(wù)計劃財務(wù)計劃中的損益計劃最能反映全店的經(jīng)營成果。咖啡店經(jīng)營者在營運資金的收支上要進行控制，以便做到經(jīng)營資金合理的調(diào)派與運用?？傊?，以上所列的六項基本計劃(營業(yè)額、商品采購、銷售促進、人員、經(jīng)費、財務(wù))是咖啡店管理不可或缺的。當然，有一些咖啡店為求管理上更深入，也能夠配合工作實際需要制訂一些其他輔助性計劃。第六部分：市場分析2019-2021年中國咖啡市場經(jīng)歷了高速增長的階段，在此期間咖啡市場總體銷售的復(fù)合增長率到達了17%;高速增長的市場為咖啡生產(chǎn)企業(yè)帶給了廣闊的市場空間，國外咖啡生產(chǎn)企業(yè)如雀巢、卡夫、ucc等企業(yè)紛紛加大了在中國的投資力度，為爭取未來中國咖啡市場的領(lǐng)先地位打下了良好的基礎(chǔ)?？Х蕊嬃现饕侵杆偃芸Х群凸嘌b即飲咖啡兩大類咖啡飲品;在速溶咖啡方面，2018-2021年間中國速溶咖啡市場規(guī)模年均增長率到達16%，顯示出還處于成長階段的中國速溶咖啡市場的高增長性和投資空間;在灌裝即飲咖啡方面，2008-2010年間中國灌裝即飲咖啡市場年均增長率也同樣到達15%;未來幾年，中國咖啡飲料的前景仍將被看好。現(xiàn)今咖啡店主要是以連鎖式經(jīng)營，市場主要被幾個集團壟斷。但由于幾個集團的咖啡店并沒有個性主題，很難配合講求特式的年青人。我們亦有思考到其他飲品