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

1、軟 件 學(xué) 院課程設(shè)計(jì)報(bào)告書課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目 地鐵建設(shè)問(wèn)題 專業(yè)班級(jí) 學(xué) 號(hào) 姓 名 指導(dǎo)教師 2015 年 1 月目錄1 設(shè)計(jì)時(shí)間32 設(shè)計(jì)目的33設(shè)計(jì)任務(wù)34 設(shè)計(jì)內(nèi)容34.1需求分析34.2總體設(shè)計(jì)44.3詳細(xì)設(shè)計(jì)44.4測(cè)試與分析5測(cè)試5分析64.5 附錄75 總結(jié)與展望11參考文獻(xiàn)12成績(jī)?cè)u(píng)定121 設(shè)計(jì)時(shí)間 2015年1月19日2012年1月23日2 設(shè)計(jì)目的通過(guò)課程設(shè)計(jì)，加深對(duì)數(shù)據(jù)結(jié)構(gòu)這一課程所學(xué)內(nèi)容的進(jìn)一步理解與鞏固，加深對(duì)結(jié)構(gòu)化設(shè)計(jì)思想的理解，能對(duì)系統(tǒng)功能進(jìn)行分析，并設(shè)計(jì)合理的模塊化結(jié)構(gòu)。提高程序開發(fā)功能，能運(yùn)用合理的控制流程編寫清晰高效的程序。訓(xùn)練C程序

2、調(diào)試能力，能將一個(gè)中小型各級(jí)組織系統(tǒng)聯(lián)調(diào)通過(guò)。開發(fā)一個(gè)中小型系統(tǒng)，掌握系統(tǒng)研發(fā)全過(guò)程。培養(yǎng)分析問(wèn)題、解決實(shí)際問(wèn)題的能力。3設(shè)計(jì)任務(wù)某城市要在各個(gè)轄區(qū)之間修建地鐵，由于地鐵建設(shè)費(fèi)用昂貴，因此需要合理安排地鐵建設(shè)線路，使市民可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總費(fèi)用最小。4 設(shè)計(jì)內(nèi)容 設(shè)計(jì)思路：(1)輸入各個(gè)轄區(qū)名稱和各轄區(qū)間直接距離（地鐵鋪設(shè)費(fèi)用與距離成正比）。如:北京到大連的直接距離是100公里.(2)根據(jù)轄區(qū)距離信息，計(jì)算出應(yīng)該在哪些轄區(qū)建立地鐵線路。(3)輸出應(yīng)該建設(shè)的地鐵線路及所需建設(shè)總里程。本程序中用到的所有抽象數(shù)據(jù)類型的定義；typedef char InfoTypetypedef char

3、 VertexTypeMAX_NAMEtypedef struct VRType adj; InfoType *info; 、 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; MGraph;typedef struct VertexType adjvex; VRType lowcost;minsideMAX_VERTEX_NUM;4.1需求分析 輸出應(yīng)該建設(shè)的地鐵線路及所需建設(shè)總里程。要求

4、輸出建設(shè)地鐵的最短路線，再利用其最短路線上的權(quán)值把總的里程計(jì)算出來(lái)，已達(dá)到最省的費(fèi)用，實(shí)現(xiàn)該地鐵的建設(shè)。4.2總體設(shè)計(jì)1.首先要了解本題中的要求，要用已經(jīng)學(xué)的鄰接矩陣，根據(jù)輸入的轄區(qū)信息，建立圖模型，使用的數(shù)據(jù)結(jié)構(gòu)是無(wú)向圖，采用鄰接矩陣存儲(chǔ)。2. 根據(jù)普利姆算法計(jì)算最小生成樹。假設(shè)WN=(V,E) 是一個(gè)含有 n 個(gè)頂點(diǎn)的連通網(wǎng)，TV 是 WN 上最小生成樹中頂點(diǎn)的集合，TE 是最小生成樹中邊的集合。顯然，在算法執(zhí)行結(jié)束時(shí)，TV=V，而 TE 是 E 的一個(gè)子集。在算法開始執(zhí)行時(shí)，TE 為空集，TV 中只有一個(gè)頂點(diǎn)，因此，按普里姆算法構(gòu)造最小生成樹的過(guò)程為：在所有“其一個(gè)頂點(diǎn)已經(jīng)落在生成樹上，

5、而另一個(gè)頂點(diǎn)尚未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。3.了解了這些就可以實(shí)現(xiàn)它的基本操作，然后構(gòu)建一個(gè)鄰接矩陣，輸入各個(gè)轄區(qū)構(gòu)成一個(gè)無(wú)向連通圖，并把直接距離當(dāng)作權(quán)值來(lái)標(biāo)記，之后，進(jìn)行普里姆的算法，使其生成最小生成樹，并帶有權(quán)值了，把這些轄區(qū)輸出，并把最小路徑和最少的費(fèi)用輸出，這樣就完成了操作。本題出現(xiàn)的調(diào)用函數(shù)是：i=creatgraph(&g);MiniSpanTree_PRIM(g,a);k=locatevex(&g,a);minimun(struct tree *a,Graph g)；開始主程序流程圖：主函數(shù) 建設(shè)

6、界面 普里姆的構(gòu)建及使用鄰接矩陣的建立及存儲(chǔ)MiniSpanTree_PRIMcreatgraphminimunlocatevex主函數(shù)結(jié)束 圖14.3詳細(xì)設(shè)計(jì)typedef struct char VM10; int RMM; int vexnum; Graph; int locatevex(Graph *g,char a10) int i; for(i=0;i<g->vexnum;i+) if(strcmp(a,g->Vi)=0) return i; if(i=g->vexnum) return -1; int creatgraph(Graph *g) int i=

7、0,j,m,k,p; char a10,b10; printf("所有的轄區(qū)，以0為結(jié)束n"); scanf("%s",g->Vi); while(strcmp("0",g->Vi)!=0) i+; scanf("%s",g->Vi); g->vexnum=i; for(i=0;i<g->vexnum;i+) for(j=0;j<g->vexnum;j+) g->Rij=INFINITY; printf("轄區(qū)之間的路程，以0 0 0為結(jié)束標(biāo)志n&qu

8、ot;); scanf("%s%s%d",a,b,&m); while(strcmp("0",a)!=0 | strcmp("0",b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);if(k=-1) printf("沒(méi)有%s這個(gè)轄區(qū)n",a); return 0; if(p=-1) printf("沒(méi)有%s這個(gè)轄區(qū)n",b); return 0;g->Rkp=g->Rpk=m;scanf("%s%s%d",a

9、,b,&m); return 1;struct tree int weizhi; int lowcost; ;int minimun(struct tree *a,Graph g) int i,k,m=0; for(i=0;i<g.vexnum;i+) if(m=0 && ai.lowcost!=0) m=1; k=i;if(m=1 && ai.lowcost!=0) if(ai.lowcost<ak.lowcost) k=i; return k;void MiniSpanTree_PRIM(Graph g,char a10) struct

10、tree closedgeM; int i,j,k,money=0; k=locatevex(&g,a); for(i=0;i<g.vexnum;i+) if(i!=k) closedgei.lowcost=g.Rki; closedgei.weizhi=k; closedgek.lowcost=0; for(i=1;i<g.vexnum;i+) k=minimun(closedge,g); money+=closedgek.lowcost; printf("%d:%s %s %dn",i,g.Vclosedgek.weizhi,g.Vk,closedg

11、ek.lowcost); closedgek.lowcost=0; for(j=0;j<g.vexnum;j+) if(g.Rkj<closedgej.lowcost) closedgej.weizhi=k; closedgej.lowcost=g.Rkj; printf("總費(fèi)用為：%dn",money);4.4測(cè)試與分析4.4.1測(cè)試鄰接矩陣的建立及存儲(chǔ)：圖2普里姆算法： 圖34.4.2分析1.調(diào)試過(guò)程中遇到的問(wèn)題及其解決方法（1）問(wèn)題:在 for 循環(huán)語(yǔ)句中,循環(huán)變量使用控制錯(cuò)誤 解決方法: 在 for 循環(huán)語(yǔ)句中,應(yīng)該意識(shí)到:循環(huán)變量的執(zhí)行次數(shù)總是比循環(huán)

12、體的執(zhí)行次數(shù)多一次;即最后一次的循環(huán)體執(zhí)行完畢之后,循環(huán)變量又執(zhí)行了一次,但是循環(huán)體卻沒(méi)有再執(zhí)行了。（2）問(wèn)題：二位數(shù)組在使用的時(shí)候數(shù)組未初始化：導(dǎo)致最后輸出的時(shí)候的鄰接矩陣出現(xiàn)錯(cuò)誤；解決方法：根據(jù)輸出的窗口從代碼中分析發(fā)現(xiàn)錯(cuò)誤，二維數(shù)組初始化之后，所得到的鄰接矩陣正確輸出。2.復(fù)雜度分析分析普里姆算法，假設(shè)網(wǎng)中有n個(gè)定點(diǎn)，則第一個(gè)進(jìn)行初始化的循環(huán)語(yǔ)句的頻率為n，第二個(gè)循環(huán)語(yǔ)句的頻率為n-1。其中有兩個(gè)內(nèi)循環(huán)：其一是在closedgev.lowcost中求最小值，其頻率為n-1;其二是重新選擇具有最小代價(jià)的變量，其頻度為n。由此，普里姆算法的時(shí)間復(fù)雜度為O(n*n),與網(wǎng)中的遍數(shù)無(wú)關(guān)。利用PR

13、IM算法生成最小生成樹時(shí)，求第k次的最短邊共需比較2(n-k)-1次，即時(shí)間復(fù)雜度為O(n-k)。3.思路探索開始分析問(wèn)題時(shí)，我把問(wèn)題想得過(guò)于簡(jiǎn)單，結(jié)合老師講過(guò)得算法和書上得算法設(shè)計(jì)得，但本題不是這樣的，這個(gè)實(shí)際問(wèn)題中有權(quán)值，而且這還是本題的關(guān)鍵，開始的時(shí)候造成了不少的麻煩，然后經(jīng)過(guò)同學(xué)間得討論，才看出來(lái)我的錯(cuò)誤來(lái)，及時(shí)改了過(guò)來(lái)。還有在普里姆的操作上，可謂是麻煩重重，書上的算法根本行不通，（因?yàn)樯厦娴氖荂+）后來(lái)我反復(fù)的來(lái)看書也整的一知半解的，通過(guò)老師的幫助，我又開始重做，在最后才做出來(lái)。由于開始時(shí)對(duì)于問(wèn)題的錯(cuò)誤分析，浪費(fèi)了不少時(shí)間。 其實(shí)，由于自己的馬虎也浪費(fèi)了不少的時(shí)間在不必要的地方，如：

14、字母的大小寫，自負(fù)的定義上，但還好最后這些都克服了，對(duì)我來(lái)說(shuō)對(duì)數(shù)據(jù)結(jié)構(gòu)又有了進(jìn)一步的了解，繼續(xù)學(xué)習(xí)，豐富自己！4.5 附錄#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h>#define INFINITY 10000#define M 20 typedef struct char VM10; int RMM; int vexnum; Graph; int locatevex(Graph *g,char a10) int i; for(i=0;

15、i<g->vexnum;i+) if(strcmp(a,g->Vi)=0) return i; if(i=g->vexnum) return -1; int creatgraph(Graph *g) int i=0,j,m,k,p; char a10,b10; printf("所有的轄區(qū)，以0為結(jié)束n"); scanf("%s",g->Vi); while(strcmp("0",g->Vi)!=0) i+; scanf("%s",g->Vi); g->vexnum=i

16、; for(i=0;i<g->vexnum;i+) for(j=0;j<g->vexnum;j+) g->Rij=INFINITY; printf("轄區(qū)之間的路程，以0 0 0為結(jié)束標(biāo)志n"); scanf("%s%s%d",a,b,&m); while(strcmp("0",a)!=0 | strcmp("0",b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);if(k=-1) printf("沒(méi)有%s這個(gè)轄區(qū)n&q

17、uot;,a); return 0; if(p=-1) printf("沒(méi)有%s這個(gè)轄區(qū)n",b); return 0;g->Rkp=g->Rpk=m;scanf("%s%s%d",a,b,&m); return 1;struct tree int weizhi; int lowcost; ;int minimun(struct tree *a,Graph g) int i,k,m=0; for(i=0;i<g.vexnum;i+) if(m=0 && ai.lowcost!=0) m=1; k=i;if(m=1

18、 && ai.lowcost!=0) if(ai.lowcost<ak.lowcost) k=i; return k;void MiniSpanTree_PRIM(Graph g,char a10) struct tree closedgeM; int i,j,k,money=0; k=locatevex(&g,a); for(i=0;i<g.vexnum;i+) if(i!=k) closedgei.lowcost=g.Rki; closedgei.weizhi=k; closedgek.lowcost=0; for(i=1;i<g.vexnum;i

19、+) k=minimun(closedge,g); money+=closedgek.lowcost; printf("%d:%s %s %dn",i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost); closedgek.lowcost=0; for(j=0;j<g.vexnum;j+) if(g.Rkj<closedgej.lowcost) closedgej.weizhi=k; closedgej.lowcost=g.Rkj; printf("總費(fèi)用為：%dn",money);void main()

20、 int i; Graph g; char a10; i=creatgraph(&g); if(i) printf("從哪里開始："); scanf("%s",a); MiniSpanTree_PRIM(g,a); 5 總結(jié)與展望通過(guò)這一周的課程設(shè)計(jì)，加深了我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程所學(xué)內(nèi)容的進(jìn)一步的理解與掌握；同時(shí)，通過(guò)對(duì)地鐵建設(shè)問(wèn)題的開發(fā)，使得我將計(jì)算機(jī)課程所學(xué)知識(shí)與實(shí)際問(wèn)題很好地相聯(lián)接在了一起。初步的了解了我們所學(xué)的課本知識(shí)在實(shí)際中的應(yīng)用。同時(shí)業(yè)培養(yǎng)了我開發(fā)一個(gè)中小型程序的能力。在這次對(duì)地鐵建設(shè)問(wèn)題的開發(fā)過(guò)程中使我更加體會(huì)到細(xì)心耐心在程序設(shè)計(jì)中的

21、重要性，和同學(xué)的合作交流業(yè)讓自己學(xué)到了更多，發(fā)現(xiàn)自己在實(shí)際問(wèn)題分析中的不足。通過(guò)本次課程設(shè)計(jì)，對(duì)圖的概念有了一個(gè)新的認(rèn)識(shí)，在學(xué)習(xí)離散數(shù)學(xué)的時(shí)候，總覺(jué)得圖是很抽象的東西，但是在學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)與算法這門課程之后，我慢慢地體會(huì)到了其中的奧妙，圖能夠在計(jì)算機(jī)中存在，首先要捕捉他有哪些具體化、數(shù)字化的信息，比如說(shuō)權(quán)值、頂點(diǎn)個(gè)數(shù)等，這也就說(shuō)明了想要把生活中的信息轉(zhuǎn)化到計(jì)算機(jī)中必須用數(shù)字來(lái)完整的構(gòu)成一個(gè)信息庫(kù)，而圖的存在，又涉及到了頂點(diǎn)之間的聯(lián)系。圖分為有向圖和無(wú)向圖，而無(wú)向圖又是有向圖在權(quán)值雙向相等下的一種特例，如何能在計(jì)算機(jī)中表示一個(gè)雙向權(quán)值不同的圖，這就是一件很巧妙的事情，經(jīng)過(guò)了思考和老師同學(xué)的幫助，我用edgesij=up和edgesji=up就能實(shí)現(xiàn)了一個(gè)雙向圖信息的存儲(chǔ)。     對(duì)整個(gè)程序而言，Dijkstra算法始終都是核心內(nèi)容，其實(shí)這個(gè)算法在實(shí)際思考中并不難，也許我們誰(shuí)都知道找一個(gè)路徑最短的方法，及