終極數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)模板

1、河南城建學(xué)院課程設(shè)計(jì)報(bào)告書(shū)專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目：校園導(dǎo)航問(wèn)題班 級(jí)：0814122學(xué) 號(hào)：081412211姓 名：諶文娟同 組 人 員：許化宇指 導(dǎo) 老 師：王永皎、趙軍民、陳秋紅、張延紅完 成 時(shí) 間：2014年2月27日摘要校園導(dǎo)航要求每?jī)蓚€(gè)場(chǎng)所間可以有不同的路，且路長(zhǎng)也可能不同，找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑(最短路徑)。要用“鄰接矩陣”來(lái)存儲(chǔ)各點(diǎn)間的距離，然后用 floyd算法求出最短路徑。所以采用工程思想，將系統(tǒng)共分以下五個(gè)模塊：節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)類型、創(chuàng)建導(dǎo)航圖函數(shù)、最短路徑導(dǎo)航函數(shù)、查詢函數(shù)聲明、主菜單。關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；算法設(shè)計(jì)目錄目

2、錄第一章開(kāi)發(fā)環(huán)境和開(kāi)發(fā)工具11.1 C語(yǔ)言簡(jiǎn)介.11.2 開(kāi)發(fā)背景21.3 開(kāi)發(fā)環(huán)境2第二章 算法思想32.1 系統(tǒng)需求分析32.2 系統(tǒng)總體設(shè)計(jì)42.2.1 系統(tǒng)設(shè)計(jì)目標(biāo)42.2.2 開(kāi)發(fā)設(shè)計(jì)思想42.2.3 系統(tǒng)功能模塊設(shè)計(jì)42.3 算法思想描述4第三章算法實(shí)現(xiàn)63.1 數(shù)據(jù)結(jié)構(gòu)63.2 程序模塊83.3 各模塊之間的調(diào)用關(guān)系93.4 源程序代碼10第四章測(cè)試與分析164.1 測(cè)試數(shù)據(jù)選擇164.2 測(cè)試結(jié)果分析20總 結(jié)21心得體會(huì)21參考文獻(xiàn)22第一章 開(kāi)發(fā)環(huán)境和開(kāi)發(fā)工具1.1 C/C+簡(jiǎn)介計(jì)算機(jī)誕生初期,人們要使用計(jì)算機(jī)必須用機(jī)器語(yǔ)言或匯編語(yǔ)言編寫(xiě)程序世界上第一種計(jì)算機(jī)高級(jí)語(yǔ)言誕生于

3、1954年,它是FORTRAN語(yǔ)言先后出現(xiàn)了多種計(jì)算機(jī)高級(jí)語(yǔ)言其中使用最廣泛影響最大的當(dāng)推BASIC語(yǔ)言和C語(yǔ)言它是一種使用非常廣泛的計(jì)算機(jī)編程語(yǔ)言。C+是一種靜態(tài)數(shù)據(jù)類型檢查的、支持多重編程范式的通用程序設(shè)計(jì)語(yǔ)言。它支持過(guò)程化程序設(shè)計(jì)、數(shù)據(jù)抽象、面向?qū)ο蟪绦蛟O(shè)計(jì)、制作圖標(biāo)等等泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格。C+是由AT&T Bell(貝爾)實(shí)驗(yàn)室的Bjarne Stroustrup博士及其同事于20世紀(jì)80年代初在C語(yǔ)言的基礎(chǔ)上開(kāi)發(fā)成功的C+保留了C語(yǔ)言原有的所有優(yōu)點(diǎn),增加了面向?qū)ο蟮臋C(jī)制C+是由C發(fā)展而來(lái)的,與C兼容用C語(yǔ)言寫(xiě)的程序基本上可以不加修改地用于C+從C+的名字可以看出它

4、是C的超越和集中C+既可用于面向過(guò)程的結(jié)構(gòu)化程序設(shè)計(jì),又可用于面向?qū)ο蟮某绦蛟O(shè)計(jì),是一種功能強(qiáng)大的混合型的程序設(shè)計(jì)語(yǔ)言C+支持面向過(guò)程的程序設(shè)計(jì)，也支持基于對(duì)象的程序設(shè)計(jì)，又支持面向?qū)ο蟮某绦蛟O(shè)計(jì)。以后我們將介紹基于對(duì)象的程序設(shè)計(jì)。包括類和對(duì)象的概念、類的機(jī)制和聲明、類對(duì)象的定義與使用等。這是面向?qū)ο蟮某绦蛟O(shè)計(jì)的基礎(chǔ)?；趯?duì)象就是基于類。與面向過(guò)程的程序不同，基于對(duì)象的程序是以類和對(duì)象為基礎(chǔ)的，程序的操作是圍繞對(duì)象進(jìn)行的。在此基礎(chǔ)上利用了繼承機(jī)制和多態(tài)性，就成為面向?qū)ο蟮某绦蛟O(shè)計(jì)(有時(shí)不細(xì)分基于對(duì)象程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)，而把二者合稱為面向?qū)ο蟮某绦蛟O(shè)計(jì))。1.2 開(kāi)發(fā)背景 隨著科學(xué)技術(shù)的

5、不斷發(fā)展，計(jì)算機(jī)科學(xué)日漸成熟，其強(qiáng)大的功能已為人們所深刻認(rèn)識(shí)，它己進(jìn)入人類社會(huì)的各個(gè)領(lǐng)域并發(fā)揮著越來(lái)越重要的作用。采用計(jì)算機(jī)進(jìn)行信息化管理已成為人們出行重要的工具，而信息管理的全面自動(dòng)化、信息化則是其中重要的組成部分。信息管理的好壞對(duì)于出行者來(lái)說(shuō)至關(guān)重要。因此，本文所研究的信息系統(tǒng)具有一定的使用價(jià)值和現(xiàn)實(shí)意義。1.3 開(kāi)發(fā)環(huán)境本文所采用的開(kāi)發(fā)環(huán)境：Windows2000以上操作系統(tǒng) Visual C+6.0以上編譯環(huán)境第二章 算法思想2.1 系統(tǒng)需求分析此次課程設(shè)計(jì)的主要內(nèi)容是校園導(dǎo)航系統(tǒng)，所謂系統(tǒng)其實(shí)也不盡然，只不過(guò)是個(gè)小小的提示，為來(lái)訪的客人提供各種信息查詢服務(wù)。主要包括：查看學(xué)校的全景圖

6、各個(gè)景點(diǎn)的簡(jiǎn)介查看某一景點(diǎn)到其它所有景點(diǎn)的最短路徑查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短路徑。 一些約定： 對(duì)于功能的輸入形式是沒(méi)什么要求的，主要就是根據(jù)菜單的提示輸入相應(yīng)的數(shù)字選擇相應(yīng)的功能；對(duì)于功能的輸入形式的要求也比較簡(jiǎn)單，要查詢某一景點(diǎn)的簡(jiǎn)介直接輸入其對(duì)應(yīng)的編號(hào)即可；對(duì)于功能的輸入形式的要求同功能；對(duì)于功能只需要輸入想要查看的起始景點(diǎn)的編號(hào)即可；對(duì)于功能只需要輸入起始景點(diǎn)和目的景點(diǎn)的編號(hào)即可。此程序在輸入形式上都沒(méi)什么特殊的要求只是一些簡(jiǎn)單的數(shù)字就可以搞定一切。 功能就是輸出由字符構(gòu)成的一幅簡(jiǎn)易圖，形式比較單一；景點(diǎn)的簡(jiǎn)介方面輸出景點(diǎn)的簡(jiǎn)單信息就可以了；要查詢最短路徑的話輸出的自然是從起始景點(diǎn)到目

7、的地的最短路徑中所途經(jīng)的各個(gè)景點(diǎn)及距離。 本程序所能達(dá)到的功能就是前面所提到的中的功能。2.2 系統(tǒng)總體設(shè)計(jì) 系統(tǒng)設(shè)計(jì)目標(biāo) 景點(diǎn)顯示（顯示景點(diǎn)的編號(hào)、名稱以及簡(jiǎn)介） 最短路徑求解（求一點(diǎn)到所有點(diǎn)之間的路徑及長(zhǎng)短，求始終兩點(diǎn)之間的路徑及長(zhǎng)短） 景點(diǎn)查找（有選擇的查找你所想了解的景點(diǎn)） 開(kāi)發(fā)設(shè)計(jì)思想 基于以上系統(tǒng)設(shè)計(jì)目標(biāo)，本文在開(kāi)發(fā)校園導(dǎo)航系統(tǒng)時(shí)遵循了以下開(kāi)發(fā)設(shè)計(jì)思想: 采用現(xiàn)有的軟硬件環(huán)境及先進(jìn)的管理系統(tǒng)開(kāi)發(fā)方案，從而達(dá)到充分利用現(xiàn)有資源，提高系統(tǒng)開(kāi)發(fā)水平和應(yīng)用效果的目的。盡量達(dá)到操作過(guò)程中的直觀、方便、實(shí)用、安全等要求。系統(tǒng)采用模塊化程序設(shè)計(jì)方法，既便于系統(tǒng)功能的各種組合和修改，又便于未參與開(kāi)

8、發(fā)的技術(shù)維護(hù)人員補(bǔ)充、維護(hù)。系統(tǒng)應(yīng)具備數(shù)據(jù)庫(kù)維護(hù)功能，及時(shí)根據(jù)用戶需求進(jìn)行數(shù)據(jù)的添加、刪除、修改、備份等操作。 系統(tǒng)功能模塊設(shè)計(jì) 采用工程思想，將系統(tǒng)共分以下五個(gè)模塊：節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)類型、創(chuàng)建導(dǎo)航圖函數(shù)、最短路徑導(dǎo)航函數(shù)、查詢函數(shù)聲明、主菜單。2.3 算法思想描述本課程設(shè)計(jì)的內(nèi)容為設(shè)計(jì)學(xué)校的平面圖,至少包括10個(gè)以上的場(chǎng)所,每?jī)蓚€(gè)場(chǎng)所間可以有不同的路,且路長(zhǎng)也可能不同,找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑(最短路徑)。如圖1,圖中已標(biāo)出主要路線，各路線的長(zhǎng)度如圖1中所示。顯然要解決這一問(wèn)題要用“鄰接矩陣”來(lái)存儲(chǔ)各點(diǎn)間的距離，然后用Dijkstra求出最短路徑。 3塑膠操場(chǎng)北門(mén)行政樓體育館 1 2

9、 4教學(xué)區(qū)教學(xué)區(qū)操場(chǎng) 5 6 7教學(xué)區(qū) 南門(mén)10噴泉廣場(chǎng) 9 8服務(wù)區(qū)15 山頂操場(chǎng)圖書(shū)館 11 12 宿舍樓 13 西門(mén) 14 圖一第三章 算法實(shí)現(xiàn)3.1 數(shù)據(jù)結(jié)構(gòu)1.節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)類型#define Num 15/*景點(diǎn)個(gè)數(shù)*/#define Maxedge 5000/*定義路徑的無(wú)窮大*/typedef struct char name14 ; /*定義景點(diǎn)名稱*/ int number;/*景點(diǎn)編號(hào)*/ char introduce100;/*景點(diǎn)描述*/vertex;/*定義頂點(diǎn)類型*/vertex verNum; /* 存放頂點(diǎn)的一維數(shù)組，數(shù)組地領(lǐng)個(gè)單元沒(méi)有用 */int edgeN

10、umNum; /* 存放路徑的長(zhǎng)度 */int shortestNumNum; /*定義全局變量存儲(chǔ)最小路徑*/int pathNumNum; /*定義存儲(chǔ)路徑*/2.創(chuàng)建導(dǎo)航圖函數(shù)void init()int i,j;函數(shù)描述：主要將每個(gè)節(jié)點(diǎn)進(jìn)行命名、每個(gè)頂點(diǎn)到其他所有定點(diǎn)的路徑值用鄰接矩陣進(jìn)行存儲(chǔ)。例如：ver1.number =1;strcpy(,"北門(mén)");strcpy(roduce,"河南城建北門(mén)，面朝北");作用：使1號(hào)定點(diǎn)命名為“北門(mén)”；描述為“河南城建北門(mén)，面朝北”；3.最短路徑導(dǎo)航函數(shù)void floy

11、d()int i=1,j=1,k=1,l=1;for(i=1;i<=Num;i+)for(j=1;j<=Num;j+)shortestij=edgeij;pathij=0;for(k=1;k<=Num;k+)for(i=1;i<=Num;i+)for(j=1;j<=Num;j+)if(shortestij>(shortestik+shortestkj)shortestij=(shortestik+shortestkj);pathij=pathji=k;函數(shù)描述，用floyd算法通過(guò)圖的權(quán)值矩陣求出圖中的每?jī)牲c(diǎn)間的最短路徑矩陣。還引入一個(gè)后繼節(jié)點(diǎn)矩陣path來(lái)

12、記錄兩點(diǎn)間的最短路徑。5.主菜單char show1()描述;顯示導(dǎo)航圖中的所有導(dǎo)航節(jié)點(diǎn)，能夠快速方便的對(duì)各個(gè)地點(diǎn)進(jìn)行導(dǎo)航。先執(zhí)行main函數(shù)。3.2 程序模塊 開(kāi)始 輸入始末景點(diǎn)顯示路徑信息輸入景點(diǎn)序號(hào)顯示景點(diǎn)介紹顯示各個(gè)景點(diǎn)之間的距離顯示學(xué)校介紹返回退出查詢景點(diǎn)路徑查詢景點(diǎn)信息查詢各景點(diǎn)間距結(jié)束學(xué)校簡(jiǎn)介3.3 各模塊之間的調(diào)用關(guān)系造圖函數(shù)（）Main（）主菜單Show1（）最短路徑函數(shù)Shortestpath（）輸出函數(shù) 圖二3.4 源程序代碼 #include <stdio.h>#include<string.h>#define Num 15/*景點(diǎn)個(gè)數(shù)*/#de

13、fine Maxedge 5000/*typedef struct char name14 ; /*景點(diǎn)名稱*/ int number; /*景點(diǎn)編號(hào)*/ char introduce100; /*景點(diǎn)描述*/vertex; /*定義頂點(diǎn)的類型*/vertex verNum; /*圖中的頂點(diǎn)，即為景點(diǎn) */int edgeNumNum; /*圖中的邊*/ int shortestNumNum; /*景點(diǎn)間最短距離*/ int pathNumNum; void show1()/*主菜單*/printf("ttt*河南城建學(xué)院平面圖*nn"); printf("t 塑

14、膠操場(chǎng)n"); printf("t 北門(mén) 行政樓 體育館n"); printf("t n"); printf("t 教 教 操場(chǎng)n"); printf("t 學(xué) 學(xué) 教 n"); printf("t 區(qū) 區(qū) 學(xué)南門(mén)n"); printf("t 區(qū) n"); printf("t 噴泉廣場(chǎng) n"); printf("t服 n"); printf("t務(wù) 山 頂 圖書(shū)館n"); printf("t區(qū) 操

15、 場(chǎng)n"); printf("t宿舍樓n"); printf("t n"); printf("t 西門(mén)nn"); void show2()/*景點(diǎn)編號(hào)*/int i=1;for(i=1;i<=Num;i+)printf("%d,%st",i,);printf("nn");void init()int i,j;ver1.number =1;strcpy(,"北門(mén)");strcpy(roduce,"河南

16、城建北門(mén)，面朝北");ver2.number =2;strcpy(,"行政樓");strcpy(roduce,"總辦公樓");ver3.number =3;strcpy(,"塑膠操場(chǎng)");strcpy(roduce,"四百米跑道，足球場(chǎng)，辦運(yùn)動(dòng)會(huì)的主要場(chǎng)地");ver4.number =4;strcpy(,"體育館");strcpy(roduce,"有羽毛球場(chǎng)，籃球場(chǎng)，為校方

17、一些籃球賽提供場(chǎng)所，還有乒乓球室");ver5.number =5;strcpy(,"教學(xué)區(qū)");strcpy(roduce,"包括二號(hào)樓，三號(hào)樓，四號(hào)樓");ver6.number =6;strcpy(,"教學(xué)區(qū)");strcpy(roduce,"五號(hào)教學(xué)樓，六號(hào)教學(xué)樓，七號(hào)教學(xué)樓");ver7.number =7;strcpy(,"操場(chǎng)");strcpy(roduce,"

18、網(wǎng)球場(chǎng)，籃球場(chǎng)，學(xué)生上課的主要場(chǎng)所，軍訓(xùn)會(huì)操演練");ver8.number =8;strcpy(,"教學(xué)區(qū)");strcpy(roduce,"八號(hào)樓，九號(hào)樓，十號(hào)樓");ver9.number =9;strcpy(,"噴泉廣場(chǎng)");strcpy(roduce,"迎新的時(shí)候開(kāi)啟噴泉，小型匯演場(chǎng)所");ver10.number =10;strcpy(,"南門(mén)");strcpy(rod

19、uce,"河南城建南門(mén)，面朝南");ver11.number =11;strcpy(,"山頂操場(chǎng)");strcpy(roduce,"學(xué)生晨練、晨讀經(jīng)常去的地方"); ver12.number =12;strcpy(,"圖書(shū)館");strcpy(roduce,"同學(xué)借還書(shū)，還有自習(xí)"); ver13.number =13;strcpy(,"宿舍樓");strcpy(

20、roduce,"供學(xué)生住宿");ver14.number =14;strcpy(,"西門(mén)");strcpy(roduce,"河南城建西門(mén)，面朝西"); ver15.number =15;strcpy(,"服務(wù)區(qū)");strcpy(roduce,"老師和學(xué)生購(gòu)物的地方");for(i=1;i<=Num;i+) for(j=1;j<=Num;j+) edgeij=Maxedge; for(i=1;i<=Nu

21、m;i+)edgeii=0;edge12=edge21=50;edge15=edge51=80; edge19=edge91=300; edge111=edge111=370;edge115=edge151=500;edge23=edge32=100;edge24=edge42=150;edge26=edge62=10;edge47=edge74=10;edge78=edge87=40;edge710=edge107=50;edge89=edge98=100;edge812=edge128=100;edge912=edge129=10;edge1112=edge1211=50; edge111

22、3=edge1311=20;edge1115=edge1511=50; edge1315=edge1513=30; edge1314=edge1413=30;char show3()/*查詢菜單*/char i;printf("信息查詢請(qǐng)輸入a.n");printf("最短路徑查詢請(qǐng)輸入b.n");printf("退出系統(tǒng)請(qǐng)輸入c.n");printf("你的選擇：");scanf("%s",&i);return i;void information()int i;while(1)sys

23、tem("cls");show1();show2();printf("請(qǐng)輸入查詢地點(diǎn)的編號(hào)：");scanf("%d",&i);if(i<=Num&&i>=1)printf("名稱：%sn簡(jiǎn)介：%sn",,roduce);return;elseprintf("輸入有誤！");void floyd()/*造圖函數(shù)*/int i=1,j=1,k=1,l=1;for(i=1;i<=Num;i+)for(j=1;j<=Nu

24、m;j+)shortestij=edgeij;pathij=0;for(k=1;k<=Num;k+)for(i=1;i<=Num;i+)for(j=1;j<=Num;j+)if(shortestij>(shortestik+shortestkj)shortestij=(shortestik+shortestkj);pathij=pathji=k; /*記錄經(jīng)過(guò)的路徑*/void show4(int i,int j)/*輸出函數(shù)*/int k=0,a=i,b=j;if(shortestij!=Maxedge)printf("從%s到%s的最短路徑為:n"

25、;,,);printf("%s",);while(pathij!=0)k=pathij;while(pathik!=0)k=pathik;printf("-%s",);i=k;printf("-%s;n", );printf("最短距離為：%d米。n",shortestab);elseprintf("從%s不能到達(dá)%s。", , );void shortestpath()

26、/*最短路徑函數(shù)*/int i=0,j=0;while(1)system("cls");show1();show2();printf("請(qǐng)輸入要查詢的兩點(diǎn)的編號(hào)：（以空格間隔）");scanf("%d%d",&i,&j);if(i<=Num&&i>0&&j<=Num&&j>0)floyd();show4(i,j);return;int main()/*主函數(shù)*/char i;printf("nnnnnnttWELCOME TO HENAN

27、 CHENGJIAN UNIVERSITY!nnn");printf("ttt n");printf("ttt n");printf("ttt 祝你健康快樂(lè)！ n");printf("ttt 每天都是 n");printf("ttt 星期天 ！ n");printf("ttt n");printf("ttt n");printf("ttt n");printf("ttt n");printf("n

28、n");init();system("pause");while (1)system("cls");show1();show2();i=show3();switch(i)case 'a':information();break;case 'b':shortestpath();break;case 'c':system("cls");/*清屏操作*/printf("nnnnnnnnnttttGOODBYE!nnnttO(_)OttO(_)Onnnnnnnnn"); system("pause");exit(0);default :printf("輸入錯(cuò)誤！n");break;system("pause");第四章 測(cè)試與分析4.1 測(cè)試數(shù)據(jù)選擇導(dǎo)航系統(tǒng)開(kāi)啟任意鍵進(jìn)入主菜單輸入a進(jìn)入信息查詢，并選擇景點(diǎn)5選擇b進(jìn)入最短路徑查詢，并選擇1到10選擇c退出校