數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)地鐵建設(shè)問題

1、軟件學(xué)院課程設(shè)計(jì)報(bào)告書課程名稱數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目地鐵建設(shè)問題專業(yè)班級學(xué)號姓名指導(dǎo)教師2013年1月目錄1設(shè)計(jì)時(shí)間22設(shè)計(jì)目的23設(shè)計(jì)任務(wù)24設(shè)計(jì)內(nèi)容24.1需求分析24.1.1程序所能達(dá)到的功能24.1.2輸入'輸出的形式和輸入值的范圍24.1.3測試數(shù)據(jù)34.2總體設(shè)計(jì)34.2.1抽象數(shù)據(jù)類型定義34.2.2主程序的流程、模塊之間的調(diào)用關(guān)系44.3詳細(xì)設(shè)計(jì)54.3.1數(shù)據(jù)類型、函數(shù)的偽碼算法54.3.2函數(shù)的調(diào)用關(guān)系圖94.4測試與分析104.4.1測試104.4.2分析114.5附錄115總結(jié)與展望16參考文獻(xiàn)17成績評定171設(shè)計(jì)時(shí)間2012年1月21日2012年1月25日2設(shè)計(jì)目

2、的1通過這次設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對課程基本內(nèi)容的理解2 .訓(xùn)練程序設(shè)計(jì)方法以及上機(jī)操作等基本技能，積累編程經(jīng)驗(yàn)3 .培養(yǎng)用計(jì)算機(jī)解決實(shí)際問題的能力3設(shè)計(jì)任務(wù)某城市要在各個(gè)轄區(qū)之間修建地鐵，山于地鐵建設(shè)費(fèi)用昂貴，因此需要合理安排地鐵建設(shè)線路，使市民可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總費(fèi)用最小。4設(shè)計(jì)內(nèi)容4.1 需求分析4.1.1 程序所能達(dá)到的功能城市要在各個(gè)轄區(qū)之間修建地鐵來加快經(jīng)濟(jì)發(fā)展，但山于建設(shè)地鐵的費(fèi)用昂貴，因此需要編寫程序合理安排地鐵的建設(shè)路線，使乘客可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總的建設(shè)費(fèi)用最小。（1）使用結(jié)構(gòu)體數(shù)組，存儲轄區(qū)

3、名稱（2） 建立轄區(qū)間直接距離的無向圖，用鄰接矩陣存儲轄區(qū)間直接距離信息（3） 根據(jù)讀入的轄區(qū)距離信息，計(jì)算出應(yīng)該建設(shè)哪些轄區(qū)的地鐵路線（4） 輸出應(yīng)該建設(shè)的路線，以及所需建設(shè)的總里程信息4.1.2 輸入、輸出的形式和輸入值的范圍輸出的形式和輸入值的范圉輸入數(shù)字和字母，字母為轄區(qū)名，數(shù)字為轄區(qū)間直接距離，名稱個(gè)數(shù)。，0線路個(gè)數(shù)<o（0-1），直接距離m,0<m<10000輸出的形式1:轄區(qū)名轄區(qū)名路程2：轄區(qū)名轄區(qū)名路程3：轄區(qū)名轄區(qū)名路程總費(fèi)用為：路程的和4.1.3 測試數(shù)據(jù)正確輸入：轄區(qū)個(gè)數(shù)：4名稱abed線路起止轄區(qū)及直接距離：db3>dc5>ad4>

4、bc2>bd3>cd2>000開始轄區(qū)：a輸出為：1：ab32：be23：cd2總費(fèi)用：7錯誤輸入：轄區(qū)個(gè)數(shù)：4名稱abed線路及之間距離：asb3輸出為：沒有as這個(gè)轄區(qū)4.2總體設(shè)計(jì)4.2.1抽象數(shù)據(jù)類型定義1.抽象數(shù)據(jù)類型圖的定義ADTGraph數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R二VRVR=<v,w>v,wWV且P(v,w),<v,w>表示從v至w的弧，謂詞P(V,W)定義了弧v,w>的意義或信息、基本操作P:CreateGraph(&G,V,VR)；初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合

5、。操作結(jié)果：按V和VR的定義構(gòu)造圖G。ADTGraph422主程序的流程、模塊之間的調(diào)用關(guān)系主程序的流程模塊之間的調(diào)用關(guān)系(1)主函數(shù)main。調(diào)用intcreatgraph(Graph*g)建立無向圖，用鄰接矩陣存儲；(2)voidMiniSpanTree_PRIM(Graphg,chara10)調(diào)用intminimun(structtree*a,Graphg)和intlocatevex(Graph*g,chara10)生成樹，判斷轄區(qū)名稱輸入是否正確；(3)主函數(shù)main()調(diào)用voidMiniSpanTree_PRIM(Graphg,chara10)計(jì)算最小生成樹，輸出最優(yōu)線路和總里程。

6、4.3詳細(xì)設(shè)計(jì)4.3.1數(shù)據(jù)類型、函數(shù)的偽碼算法1 .結(jié)構(gòu)體類型typedefstruct)charVM10;intvexnum;(Graph;2 .函數(shù)算法創(chuàng)建無向圖intlocatevex(Graph*g,chara10)(inti;for(i=0;i<g->vexnum;i+)(if(strcnip(a,g->Vi)=O)returni;if(i=g,>vexnum)return-1;)intcreatgraph(Graph*g)(inti=0J,mkpoe;chara10,b10;printfC*設(shè)置轄區(qū)的個(gè)數(shù)：“)；城市中轄區(qū)的個(gè)數(shù)scanfd&o);

7、for(i=0;i<o;i+)建立城市轄區(qū)名數(shù)組(printf(f%d個(gè)城市轄區(qū)名稱為：“，i+1);scanf(H%su,g->Vi);g->vexnum=o;for(i=0;i<g->vexnum;i+)for(j=0;j<g->vexnum;j+)g->Rij=INFINITY;printf(“轄區(qū)之間的路程，以000為結(jié)束標(biāo)志n“)；scanf("s%s%d”,a,b,&m);while(strcmp(nOM,a)!=OIIstrcmp(nOu,b)!=OIIm!=0)k=locatevex(g,a);p=locatev

8、ex(g,b);if(k=-l)printf("沒有$這個(gè)轄區(qū)n”,a);return0;printf(沒有$這個(gè)轄區(qū)nb);return0;g->Rkp=g->Rpk=m;scanf("s%s%cT,a,b,&m);return1;structtreeintweizhi;intlowcost;intmininiun(structtreeGraphg)inti,k,m=O;for(i=0;i<g.vexnum;i+)(if(m=O&&ai.lowcost!=0)(m=1;k=i;)if(m=l&&ai.lowcost

9、!=0)(if(ai.Iowcost<ak.lowcost)k=i;1returnk;)普利姆算法求最小生成樹，輸出最優(yōu)線路及費(fèi)用voidMiniSpanTree_PRIM(Graphg.chara10J)(structtreeclosedgeM;intij5kjnoney=0;k=locatevex(&g,a)；for(i=0;i<g.vexnum;i+)closedgei.lowcost=g.Rki;closedgei.weizhi=k;closedgek.lowcost=0;for(i=l;i<g.vexnum;i+)k=minimun(closedge,g);

10、money+=closedgek.lowcost;printf(H%d:%s%s%dni,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost);ciosedgek.lowcost=0;for(j=0;j<g.vexnum;j+)if(g.Rkj<closedgej.Iowcost)(ck)sedgej.weizhi二k;closedgejlowcost二gRkj;>)printfC*總費(fèi)用為:%dnH,money);432函數(shù)的調(diào)用關(guān)系圖4. 4測試與分析4. 4. 1測試1.正確的輸入城城城城不個(gè)個(gè)個(gè)-12 3 4年名名名名葭區(qū)區(qū)區(qū)區(qū)于 &

11、amp;一cd 0。為結(jié)品標(biāo)志ah beB:3:總Pressanykeytocontinue2.錯誤的輸入為為為為>0>»# 譴 1 2 3巨品C:WIKDO¥Ssysto»L32c«L<i.ex©cd00為結(jié)束標(biāo)志Pi»eeant;keytocontxnue4.4.2分析調(diào)試過程中遇到的問題及其解決方法（1）問題：用for循環(huán)語句控制輸入轄區(qū)名稱及輸出轄區(qū)名稱時(shí)候的個(gè)數(shù)名不對應(yīng)解決方法：數(shù)組下標(biāo)時(shí)從零開始的，并且在for循環(huán)語句中，循環(huán)變量的執(zhí)行次數(shù)總是比循環(huán)體的執(zhí)行次數(shù)多一次，所以應(yīng)該注意修改使其相對應(yīng)（2）問題

12、：用循環(huán)控制各轄區(qū)及其之間的距離沒有考慮清楚解決方法：用輸入。00判定轄區(qū)及其直接距離數(shù)據(jù)輸入完畢（3）問題：普利姆算法理解不透徹，用其計(jì)算最小生成樹輸出結(jié)果的時(shí)候出現(xiàn)問題解決方法：上網(wǎng)查閱資料及閱讀課本詢問同學(xué)，并在以前程序上加以修改，最終得以運(yùn)行。4.5附錄#indu(le<stclio.h>#defineINF32767typedefintInfoType;#defineMAXV100typedefstruct(intadj;InfoType*lnfo;ArcCell,AdjMatrixMAXVMAXVJ;typedefstruct(intedgesMAXVMAXV;intn

13、,e;intvexsMAXV;JMGraph;typedefstructANodeintadjvex;structANode*nextarc;InfoTypeinfo;JArcNode;typedefintVertex;typedefstructVnode(Vertexdata;ArcNode*flrstarqJVNode;typedefVNodeAdJListMAXV;typedefstruct(AdjListadjlist;intn,e;JALGraph;intsum=O;intLocatevex(MGraphg,intA)(inti;for(l=0;i<g,n;i+)(if(A=g

14、.vexsi)returni;)if(i=g.n)return1;intCreateMgraph(MGraph&g)int ij,k,w,vl,v2;printf("3s"畀oo”);elsepantfu%3d/gedges-11111deUsh-A)oljjprim(MGraph必34W)inI1omcos=MAXVhmm3二g-HinfclosesI1MAXVJfcKM-u.+4lowcossllgedges=sclosessnw;)M-O，=一+<mmHINF;fora=o;J：Il;j+一n-eoMuoss=o<<1。mmHoxvcostE

15、;中.)prms國M司ms區(qū)(堂dd)灘區(qū)=恭窿$:%dn.2.oses=khrmm)"-Slnn+HmimkHVCOS=kjHO;J。|WUII+in6P68SUJUJ=O會會6P68S【3MuOsm4alowcostJ=g.edgeskJ;closestJ=k;print”建設(shè)鐵路線的最低費(fèi)用為:%dii-sum);)voidmain()(intij;MGraphg;CreateMgraph(g);pHntf("轄區(qū)圖的鄰接矩陣:n")；DispMat(g);prlntfC*普里姆算法結(jié)果:nH)；Prim(g,O);printf(-ir);5總結(jié)與展望這次課

16、程設(shè)計(jì)任務(wù)是我在大學(xué)以來的遇到的第一次課程設(shè)計(jì)，剛開始看到題U的時(shí)候看起來不是很難，但是在實(shí)際編程操作中遇到了很多的問題，不過，在不斷地遇到和解決問題的過程中，學(xué)到了很多的知識。通過這一周的課程設(shè)訃，加深了我對數(shù)據(jù)結(jié)構(gòu)這門課程所學(xué)內(nèi)容的進(jìn)一步的理解與掌握。同時(shí)'通過設(shè)計(jì)程序解決地鐵建設(shè)問題，讓我明口學(xué)習(xí)知識不僅僅是要學(xué)習(xí)課本上的內(nèi)容,還要從實(shí)際生活中學(xué)習(xí)課外的知識，把書本上的知識與現(xiàn)實(shí)生活好好的結(jié)合在一起。并且在查閱資料和完成設(shè)計(jì)的同時(shí)丁我初步的了解了我們所學(xué)的課本知識在實(shí)際中的應(yīng)用。同時(shí).，這次課程設(shè)計(jì)進(jìn)一步鍛煉了我的編寫程序的能力，和同學(xué)的合作交流也讓自己學(xué)到了更多，發(fā)現(xiàn)自己在實(shí)際問題分析中的不足。在編寫程序的過程中，我更深切的認(rèn)識到了認(rèn)真、仔細(xì)、耐心的重要性，比如，就不能忽略循環(huán)時(shí)的控制變量。在本次課程設(shè)計(jì)中，主要運(yùn)用了圖的知識解決實(shí)際問題。同過這次的應(yīng)用實(shí)踐，讓我體會到了圖之所以能夠在計(jì)算機(jī)中存在，首先要捕捉他有哪些具體化、數(shù)字化的信息，比如說權(quán)值、頂點(diǎn)個(gè)數(shù)等，也就是想要把生活中的信息用計(jì)算機(jī)表達(dá)出來，首先就得把他們數(shù)字化，具體化成