1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、課程設(shè)計(jì)目的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要求能綜合運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些與實(shí)際應(yīng)用結(jié)合緊密的、規(guī) 模較大的問(wèn)題，通過(guò)分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握 數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)技術(shù)，掌握分析、解決實(shí)際問(wèn)題的能力。通過(guò)這次設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法 的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作 等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。二、設(shè)計(jì)要求從課程設(shè)計(jì)的目的出發(fā)，通過(guò)設(shè)計(jì)課題的各個(gè)環(huán)節(jié)，達(dá)到以下教學(xué)要求：從所給題目中任選一個(gè)，每個(gè)學(xué)生必須獨(dú)立完成課程設(shè)計(jì)，不能相互抄襲：設(shè)

2、計(jì)完成后，將所完成的工作交由老師檢查；要求寫(xiě)出一份詳細(xì)的設(shè)計(jì)報(bào)告。三、設(shè)計(jì)題目（以下題目任選一個(gè)）學(xué)生成績(jī)管理系統(tǒng)（線性表）能完成每位學(xué)生某門(mén)課程的成績(jī)錄入、刪除、修改、查找、統(tǒng)計(jì)（即成績(jī)?yōu)椤皟?yōu)”的學(xué) 生信息、成績(jī)?yōu)椤傲肌钡膶W(xué)生信息、成績(jī)?yōu)椤爸小钡膶W(xué)生信息、成績(jī)?yōu)椤凹案瘛钡膶W(xué)生信息、 成績(jī)?yōu)椤安患案瘛钡膶W(xué)生信息）。停車場(chǎng)管理系統(tǒng)（棧和隊(duì)列）設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，旦只有一個(gè)大門(mén)可供汽車進(jìn)出。汽車 在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最北端，最先到達(dá)的第 一輛車停放在車場(chǎng)的最南端），若車場(chǎng)內(nèi)己停滿n輛汽車，則后來(lái)的汽車只能在門(mén)外的便道 上等候，一旦有車

3、開(kāi)走，則排在便道上的第一輛車即可開(kāi)入：當(dāng)停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí), 在它之后開(kāi)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開(kāi)出大門(mén)外，其它車輛再按原次序 進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開(kāi)停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為 停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。迷宮問(wèn)題（棧和隊(duì)列）求迷宮問(wèn)題就是求出從入I I到出I I的所有路徑。在求解時(shí)，通常用的是“窮舉求解”的 方法,即從入I I出發(fā),順某一方向向前試探，若能走通，則繼續(xù)往前走；否則沿原路退回，換一 個(gè)方向再繼續(xù)試探，直至所有可能的通路都試探完為止。家譜管理系統(tǒng)（樹(shù)）本課題的實(shí)質(zhì)是完成對(duì)家譜成員信息的建立、查找、插入、修改、刪除等功

4、能?？梢允?先定義家族成員的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能作為一個(gè)成員函數(shù)來(lái)完成對(duì)數(shù)據(jù)的操作，最后 完成主函數(shù)以驗(yàn)證各個(gè)函數(shù)功能并得出運(yùn)行的結(jié)果。公交路線管理模擬系統(tǒng)（圖）本課題是對(duì)公交路線信息的簡(jiǎn)單模擬，以完成建立公交路線信息、修改公交路線信息和 刪除公交路線信息等功能。課題的實(shí)質(zhì)是完成對(duì)公交路線信息的建立、查找、插入、修改、 刪除等功能?？梢允紫榷x公交路線的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能作為一個(gè)成員函數(shù)來(lái)完成 對(duì)數(shù)據(jù)的操作，最后完成主函數(shù)以驗(yàn)證各個(gè)函數(shù)功能并得出運(yùn)行的結(jié)果。最短路徑導(dǎo)航查詢系統(tǒng)（圖）設(shè)計(jì)一個(gè)交通導(dǎo)航質(zhì)詢系統(tǒng)，能讓旅客質(zhì)詢從任一個(gè)城市頂點(diǎn)到另一個(gè)城市頂點(diǎn)之間的 最短路徑問(wèn)題。設(shè)計(jì)分為三

5、個(gè)部分，一是建立交通網(wǎng)結(jié)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源最短路 徑問(wèn)題；最后再實(shí)現(xiàn)兩個(gè)城市頂點(diǎn)之間的最短路徑問(wèn)題。鏈表綜合算法設(shè)計(jì)設(shè)有一個(gè)職工文件，其結(jié)構(gòu)為：職工號(hào)（no）、姓名（name）部門(mén)號(hào)（depno）、工資數(shù)（salary）、 職工號(hào)指針（pno）和工資數(shù)指針（psalary）o設(shè)計(jì)一個(gè)程序，從該文件中讀取記錄到一個(gè)單 鏈表中。復(fù)雜表達(dá)式的值設(shè)計(jì)一個(gè)程序計(jì)算含有如下標(biāo)識(shí)符的表達(dá)式的值o （1）數(shù)值包括整數(shù)和實(shí)數(shù)，數(shù)值可帶正 負(fù)號(hào)。（2） 一般運(yùn)算符：正號(hào)負(fù)號(hào)、加減乘除和求模乘方，其中可以包含括號(hào)。（3）單詞（即 運(yùn)算函數(shù)）四、課程設(shè)計(jì)需提交內(nèi)容提交“課程設(shè)計(jì)報(bào)告”打印版，其內(nèi)容詳見(jiàn)“課程設(shè)

6、計(jì)報(bào)告書(shū)”。提交己調(diào)試通過(guò)的完整的相關(guān)源程序和“課程設(shè)計(jì)報(bào)告”電子版，將兩者壓縮為一個(gè)文 件包，文件名為：“11位學(xué)號(hào)+姓名”（如2009*小強(qiáng)）。提交時(shí)間:6月24日（18周五）12:00前。設(shè)計(jì)題目：最短路徑導(dǎo)航查詢系統(tǒng)（圖）實(shí)習(xí)目的通過(guò)學(xué)習(xí)，了解并初步掌握設(shè)計(jì)、實(shí)現(xiàn)較大系統(tǒng)的完整過(guò)程，包括系統(tǒng)分析、編碼設(shè)計(jì)、 編碼集成以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計(jì)、實(shí)現(xiàn)、以及操作方法，為進(jìn)一步 的開(kāi)發(fā)應(yīng)用打好基礎(chǔ)。問(wèn)題描述設(shè)計(jì)分為三個(gè)部分，一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源最短路徑問(wèn)題： 最后再實(shí)現(xiàn)兩個(gè)城市頂點(diǎn)之間的最短路徑問(wèn)題的輸出。需求分析該程序所做的工作是給司機(jī)們提供最佳路線，

7、來(lái)提高能源和時(shí)間的合理利用。此程序規(guī)定：把城市交通線路轉(zhuǎn)化為圖，從而對(duì)圖進(jìn)行相應(yīng)的結(jié)構(gòu)存儲(chǔ);程序的輸出信息主要為：起始城市到目的城市的最短路徑;程序的功能主要包括：城市之間路徑的存儲(chǔ)，最短路徑的計(jì)算，以及最短路徑和鄰接矩陣的輸出：概要設(shè)計(jì)對(duì)于這樣的問(wèn)題，先假設(shè)有四個(gè)城市甲乙丙丁，甲乙相距2千米，且只有從乙到甲的單 程線路。甲丙相距7千米，且只有從甲到丙的單程線路。甲丁相距4千米，且只有從甲到丁的 單程線路。乙丙相距5千米，且只有從丙到乙的單程線路。乙丁相距3千米，且只有從丁到乙 的單程線路。丙丁相距3千米，且只有從丁到丙的單程線路。戊甲相距6千米，且只有從戊到 甲的單程線路。戊丁相距2千米，旦

8、只有從丁到戊的單程線路。乙己相距8千米，且只有從乙 到己的單程線路。丙己相距6千米，旦只有從己到丙的單程線路。編程出能求出個(gè)一點(diǎn)到任一點(diǎn)的最短路經(jīng)。則圖G的鄰接矩陣為:甲乙丙T戊己甲r ooOO74oo00 、乙2ooooOOoo8丙OO5ooOOoo8丁OO33oo28戊6ooooOOOO8己1OO6OOOOoo )8表示無(wú)窮大系統(tǒng)用到的數(shù)據(jù)有： int which; int v ; int endv;用到的主要函數(shù)：輸出鄰接矩陣gvoid DispMat(MGraph g)void ppath(mt pathMAXV,mt v,mt endv) 輸出相應(yīng)選擇的起點(diǎn)和終點(diǎn)的最短路void D

9、isPath(uit AMAXV,int pathMAXV,int n.mt endv)/|l| path 計(jì)算最短 路徑 void Floyd(MGraph g,mt v,int endv)/采用弗洛伊德算法求沒(méi)對(duì)頂點(diǎn)之間的最 路徑/主函數(shù)int main ()各程序模塊之間的調(diào)用關(guān)系： 函數(shù)3)可以調(diào)用函數(shù)2)。 函數(shù)4)可以調(diào)用函數(shù)3)。函數(shù)5)可以調(diào)用函數(shù)1)和函數(shù)4)。詳細(xì)設(shè)計(jì)頂點(diǎn)編號(hào)頂點(diǎn)其他信息，這里用于存放邊的權(quán)值頂點(diǎn)類型圖的定義鄰接矩陣/頂點(diǎn)數(shù)，弧數(shù)存放頂點(diǎn)信息圖的鄰接矩陣類型typedef stmct (int no;InfbType uifo;VertexTyp

10、e;typedef stiuct(int edgesMAXVMAXq； mt n.e;VertexType vexsMAXV;MGiaph;以下定義鄰接表類型孤的結(jié)點(diǎn)結(jié)構(gòu)類型該弧的終點(diǎn)位置指向下一個(gè)弧的指針該孤的相關(guān)信息，這里用于存放權(quán)值typedef strnct ANode(int adj vex;stmct ANode *nextarc;InfbType info;ArcNode;typedef int Vertex;typedef stmct Vnode(Vertex data;AicNode * fir stare MAXV;VNode;typedef VNode AdjListMA

11、XV;/AdjList 是鄰接表類型 typedef stmct (AdjList adjlist;mt n,e; AL Graph;鄰接表頭結(jié)點(diǎn)的類型頂點(diǎn)信息指向第一條孤鄰接表/圖中頂點(diǎn)數(shù)n和邊數(shù)e圖的鄰接表類型輸出鄰接矩陣gvoid DispMat(MGraph g) intij;fbr(i=O;ig.n;i+) (for(j=0;jg.nj+)if(g.edgesij=INF) COUt，00，tM else coutg.edgesijn coutnn,r;void ppath(int pathMAXVant vjnt endv) 輸出相應(yīng)選擇的起點(diǎn)和終點(diǎn)的最短路線 int k;k=pa

12、thvendv;if(k=-l)retinn;ppath(path,v,k);coutk;ppath(path,k,endv);void DisPatli(uit AMAXV.int pathMAXV,int n,int v,int endv)/由 path 計(jì)算最短路 徑cout”從” vwvv” 到” vvendvvv” 路線為：”；coutv;ppath(path,v,endv);coutendv;coutendl;coutvv”路線長(zhǎng)度為：”vvAvendvvv”千米”vv”；void Floyd(MGiaph g,mt v,mt endv)采用弗洛伊德算法求沒(méi)對(duì)頂點(diǎn)之間的最短路徑(i

13、nt AMAXV MAXV ,pathMAXV MAXV;mt ij,k,n=g.n;for(i=0;ivn;i+)給數(shù)組A置初值for(j=0;jn;j-H-)Aij=g.edgesiU；pathij=-l;foi (k=0 ;kn;k+)/計(jì)算 Akfor(i=0;in;i-H-)for(j=0;j(Aik+AkD)Aij=(Aik+Ak|j)；pathij=k;coutvv”n”vv”輸出最短路線：”vv偵,；DisPath(A,path,n.v,endv);輸出最短路線測(cè)試分析歡迎使員L上-交通導(dǎo)航索統(tǒng)地點(diǎn)名禰： 。.地點(diǎn)甲1.弛點(diǎn)乙2.地點(diǎn)丙3.地點(diǎn)丁4.弛點(diǎn)戊S.地點(diǎn)己*以八播選擇

14、所需要的服務(wù)：霏要求最短路線請(qǐng)技b.輸出直向圖G的鄰接矩陣：2請(qǐng)輸入整羲1到3：短圖請(qǐng)咨虧 青賽代 求套手整點(diǎn)誤 要出出入起 C.請(qǐng)蕾 : 路G&按的:4:1 短圖請(qǐng) 曰伺霸代代 求復(fù)至整點(diǎn)點(diǎn) 要出出入起終 SSA.A直米03千4 3 -:1 線為:路線為 短路度 秀2F牛 W巨的地地要需3 1丙fe:稱甲丁名點(diǎn)點(diǎn)點(diǎn)地弛歡通交所擇軋先J 1陣 乙戊#1=鋌 點(diǎn)點(diǎn)堆??； 地地 -1 4路源技祁:3:5 最向饕代代 求尊亦整點(diǎn)點(diǎn) 要出出入起終 圭黯退E八米.15千3 1 -:1 線為：路線為短路度3 2陣 出出入圖8 8 蕾退曹a-玖6薯8 28 8 68 3co使用說(shuō)明首先運(yùn)行程序，包括三個(gè)選項(xiàng)

15、，a.需要求最短路徑請(qǐng)按：1.輸出有向圖G的鄰接矩陣：2.退出系統(tǒng)請(qǐng)按：3.然后可以根據(jù)不同的需要選擇不同的選項(xiàng)進(jìn)行操作最后按3退出程序。附錄：測(cè)試數(shù)據(jù)起點(diǎn)為：地點(diǎn)?。?）終點(diǎn)為：地點(diǎn)己（5）通 交丙己曄地地要乙戊選:1昨稱甲丁名點(diǎn)點(diǎn)點(diǎn)地弛 也 . 103路源技祁:3:5 最向饕代代 求尊亦整點(diǎn)點(diǎn) 要出出入起終 圭黯退軸IA1A la,lb,lc請(qǐng)米.15千3 1 :1 線為： 路線為 短路度 曰柔長(zhǎng) 出螯C+實(shí)現(xiàn)include #iiiclude using namespace std;#define MAXV 6/最大頂點(diǎn)個(gè)數(shù)#define INF 32767用32767表示8typede

16、f int InfbType; typedef stmct最大頂點(diǎn)個(gè)數(shù)(int no;/頂點(diǎn)編號(hào)InfoType infb;頂點(diǎn)其他信息，這里用于存放邊的權(quán)值JVertexType;頂點(diǎn)類型typedef stmct/圖的定義(int edgesMAXVMAXV;鄰接矩陣hit n,e;頂點(diǎn)數(shù)，弧數(shù)VertexType vexsMAXV;/存放頂點(diǎn)信息)MGraph;/以下定義鄰接表類型圖的鄰接矩陣類型typedef stmct ANode弧的結(jié)點(diǎn)結(jié)構(gòu)類型(int adjvex;該弧的終點(diǎn)位置stmct ANode *nextarc;指向下一個(gè)孤的指針I(yè)nfoType infb;該弧的相關(guān)信息

17、，這里用于存放權(quán)值A(chǔ)icNode;typedef int Vertex;typedef struct Vnode/鄰接表頭結(jié)點(diǎn)的類型(Vertex data;頂點(diǎn)信息AicNode *firstaic MAXV:指向第一條孤VNode;typedefVNode AdjListNIAXV;/AdjList 是鄰接表類型typedef stmctAdjList adjlist;鄰接表int n,e;圖中頂點(diǎn)數(shù)n和邊數(shù)e)ALGraph;圖的鄰接表類型void DispMat(MGraph g)輸出鄰接矩陣 smt i,j;fbi(i=O;ig.n;i+)(for(j=Ojg.nj+)if(g.ed

18、gesi(j=INF)coutHMelsecoutvvg.edgesijvv” ”；coutHnH;void ppatli(mt path MAXV ,int v,int endv)輸出相應(yīng)選擇的起點(diǎn)和終點(diǎn)的最短路徑(int k;k=pathvendv;if(k=-l)renrn;ppath(path,v,k);coutk;ppath(path,k.eudv);void DisPath(mt AMAXV,int pathMAXV,int n,int v.mt endv)/由 path 計(jì)算最短路徑 coutH 從” vvvvv” 到路線為二coutv;ppath(path,v,endv);coutendv;coutendl;coutH路線長(zhǎng)度為：”vAvendvvv”千米”vv”n”；void Floyd(MGrapli g,int v,iiit endv)采用弗洛伊德算法求沒(méi)對(duì)頂點(diǎn)之間的最短路徑int A MAXV MAXV ,pathMAXVMAXV;mt i,j,k,n=g.n;foi(i=0;in;i+)給數(shù)組A置初值fbr(j=Ojnj+)(Aij=g.edgesij;pa