東北大學數(shù)據(jù)結(jié)構(gòu)實踐實驗報告

1、課程編號：B080109010數(shù)據(jù)結(jié)構(gòu)課程設(shè)計總結(jié)報告姓名燕江弟學號20144671班級軟件1404班指導教師劉益先實驗名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計開設(shè)學期2016-2017第一學期開設(shè)時間第10周第12周報告日期2016-11-25評定成績評定人評定日期2016-11-28東北大學軟件學院第一章需求分析1.1 建立主程序應(yīng)用菜單選項主程序應(yīng)用菜單選項包含所實現(xiàn)的所有功能，并且對選項采用數(shù)字標識進行選擇，對其他錯誤輸入可以進行判別，提示輸入錯誤。1.2 導游線路圖的創(chuàng)建級景區(qū)分布圖的輸出用鄰接鏈表存儲景點分布圖的信息，（帶權(quán)無向）圖的鄰接鏈表。輸出景區(qū)景點分布圖（鄰接矩陣）。圖中邊的權(quán)值用32767表

2、示。1.3 輸出導游線路圖景區(qū)旅游信息管理系統(tǒng)中制訂旅游景點導游線路策略，首先通過遍歷景點，給出一個入口景點，建立一個導游線路圖，導游線路圖用有向圖表示。1.4 輸出導游線路圖中是否有回路景區(qū)旅游信息管理系統(tǒng)中，創(chuàng)建好導游路線圖后，判斷該圖中是否存在回路。1.5 查找及排序l 查找功能： 可以根據(jù)用戶輸入的關(guān)鍵字進行景點的查找，關(guān)鍵字可以在景點名稱也可以在景點介紹中。查找成功則返回景點的相關(guān)簡介，如果查找不成功請給予正確提示。l 排序功能：按景點歡迎度，景點的岔路數(shù)對景點進行排序并打印出來排序順序。1.6 輸出兩個景點之間最短路徑和最短距離求出兩個景點間的最短路徑和最短距離，并且輸出道路修建規(guī)

3、劃圖。 算法采用迪杰斯特拉算法。1.7 輸出道路修建規(guī)劃圖道路建設(shè)首先要保證能連通所有景點，但又要花最小的代價。1.8 輸出車輛的進出信息1.8.1 具體需求：停車場是一個可以停放n輛汽車，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次排列，若車場內(nèi)已停滿n輛車，后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。輸出每輛車到達后的停車位置（停車場或便道上），以及

4、某輛車離開停車場時應(yīng)繳納的費用和它在停車場內(nèi)停留的時間。1.8.2 停車場的管理流程如下：A.當車輛要進入停車場時，檢查停車場是否已滿，如果未滿則車輛進入停車場；如果停車場已滿，則車輛進入便道等候。B.當車輛要求出棧時，先讓在它之后進入停車場的車輛退出停車場為它讓路，再讓該車退出停車場，讓路的所有車輛再按其原來進入停車場的次序進入停車場。之后，再檢查在便道上是否有車等候，有車則讓最先等待的那輛車進入停車場。1.8.3 車輛出入清單：每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場

5、內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。1.9退出整個程序。第二章系統(tǒng)設(shè)計2.1總體設(shè)計：2.1.1：具體數(shù)據(jù)結(jié)構(gòu)定義首先需要創(chuàng)建節(jié)點類，鄰接邊類，無向圖類以及停車類。節(jié)點類包括了存儲的景點名稱，景點介紹，景點的歡迎度，景點有誤休息區(qū)，景點有無廁所以及指向下一條鄰接邊的指針。鄰接邊類包括了鄰接點的序號，邊的權(quán)值（即是距離）以及指向下一條邊的節(jié)點指針。無向圖類包括了該圖中所需要的節(jié)點個數(shù)，所需要的鄰接邊數(shù)以及存儲具體節(jié)點和邊的指針。具體如下：class ArcNode public:int adjvex;ArcNode *ne

6、xtarc;double weight;class VNode public:string data1;string data2;int wel;bool wc;bool rest; ArcNode *firstarc;class ALGraph public:VNode *vertices;int vexnum, arcnum;ArcNode *arcNode;class zanlindpublic:int number;string time;2.1.2 ：具體功能實現(xiàn)方法： a. 景區(qū)景點分布圖的創(chuàng)建：int LocateVex(ALGraph G, string v)void Crea

7、teUDN(ALGraph &G);b 輸出景區(qū)景點分布圖：void PrintAdjList(ALGraph &G)，void OutputGraph(ALGraph G)。c. 輸出導游線路圖：void DFSTraverse(ALGraph G)d. 輸出導游線路圖中是否有回路：void FindInDegree( ALGraph &g)，void JudgeCir(ALGraph G)。e.查找及排序：int LocateW(ALGraph G, int wel)，void LocateVex2(ALGraph G, string v)，void Search(

8、ALGraph G,string s)，void FindInDegree(G)，void SortWel(ALGraph G)，bool isInN(ALGraph G,int aMAX,int n)void SortN(ALGraph G)，f. 輸出兩個景點之間最短路徑和最短距離：void ShortestPath_DIJ(ALGraph G,int v0, int pMAX, int D)，bool isInVe(ALGraph G,string va)void printShortestPath(ALGraph G)。g.輸出道路修建規(guī)劃圖：void build(ALGraph &a

9、mp;G)void prim(ALGraph G,int v,double arrMAXMAX)。h.輸出車輛的進出信息：bool isInZan(int zaMAX,int number)，int indexZ(int z,int n)void goIn()，void goOut()。2.2程序設(shè)計a. 景區(qū)景點分布圖的創(chuàng)建: void CreateUDN(ALGraph &G) G.arcNode=new ArcNodeMAX;G.vertices=new VNodeMAX;fstream file("C:Users22291_000Desktop數(shù)據(jù)結(jié)構(gòu)info.txt

10、");if(file.fail()cout << "error open!" << endl; int j;ArcNode *s, *t;cout<<"請輸入頂點數(shù)和邊數(shù)："cin>>G.vexnum>>G.arcnum;int i=0;cout<<endl;while(!file.eof()file >>G.verticesi.data1>>G.verticesi.data2 >> G.verticesi.wel>> G.v

11、erticesi.rest>>G.verticesi.wc;G.verticesi.firstarc = NULL;i+;cout<<endl;fstream file1("C:Users22291_000Desktop數(shù)據(jù)結(jié)構(gòu)edge.txt");if(file.fail()cout << "error open!" << endl; while(!file1.eof()int weight;string v1, v2;file1>>v1>>v2>>weight;int

12、 i = LocateVex(G, v1);int j = LocateVex(G, v2);s = new ArcNode();t = new ArcNode();s->adjvex = j;s->nextarc = G.verticesi.firstarc;s->weight=weight;G.verticesi.firstarc =s;t->adjvex = i;t->nextarc = G.verticesj.firstarc;t->weight=weight;G.verticesj.firstarc =t; b.深度優(yōu)先遍歷算法：具體如下：void

13、 DFSTraverse(ALGraph G)bool sta20;int v;for (v = 0; v<G.vexnum; v+)stav =true; stack<int>status; int n=0; int num = -1; int pk; ArcNode *e; cout << G.vertices0.data1 << "->" sta0 =false; status.push(0); int aa, bb; aa = 0; while (n < G.vexnum-1) e = NULL; num = s

14、tatus.top(); e = G.verticesnum.firstarc; while (e) if (stae->adjvex = false) e = e->nextarc; else status.push(e->adjvex); cout << G.verticese->adjvex.data1<<"->" aa = e->adjvex; stae->adjvex = false; n+; break; if (e = NULL) pk = status.top(); bb = pk; if (

15、aa != bb) cout << G.verticespk.data1<<"->" status.pop(); if (status.top() = 0) cout << G.vertices0.data1 << "->" cout << endl; c. 輸出車輛進出信息： void goIn()zanlind zan;cout<<"車牌號為："cin>>zan.number;cout<<endl;time_t t = ti

16、me(0);char tmp64; strftime(tmp,sizeof(tmp),"%X ",localtime(&t);zan.time=tmp;cout<<"進場時間為："cout<<tmp<<endl;if(parking.size()<MAX2)parking.push(zan);zk+=zan.number;cout<<"該車已進入停車場在： 1號車道"elsecout<<"停車場已滿，請等待其他車輛離開：" waits.pus

17、h(zan); void goOut()if(parking.size()<=0)cout<<"停車場為空，沒有車要離開！"elsecout<<"請輸入您的車牌號："int number;cin>>number;if(isInZan(z,number) while(parking.top().number!=number) cars.push(parking.top();parking.pop();time_t t = time(0); char tmp64; strftime(tmp,sizeof(tmp),&

18、quot;%X ",localtime(&t); cout<<"車牌號為："<<parking.top().number<<"的車要離開了,離開時間為"<<tmp; parking.pop(); while(!cars.empty() && parking.size()<MAX2) parking.push(cars.top();cars.pop();while(parking.size()<MAX2) parking.push(waits.front();wa

19、its.pop();elsecout<<"沒有該輛車！請輸入正確的車牌號："<<endl; 。第三章系統(tǒng)實現(xiàn)與調(diào)試3.1 景區(qū)景點分布圖的創(chuàng)建實現(xiàn)過程：是通過定義的數(shù)據(jù)結(jié)構(gòu)將節(jié)點數(shù)據(jù)和鄰接邊數(shù)據(jù)信息讀取后存儲在其數(shù)據(jù)結(jié)構(gòu)上，節(jié)點通過頭插法進行插入鄰接邊。難點：如何定義合理的數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)。解決方案：定義了三種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，包括節(jié)點類，鄰邊類和無向圖類。3.2輸出導游路線圖及其圖中的回路部分實現(xiàn)過程：導游路線路采取了深度優(yōu)先遍歷算法來進行所有節(jié)點的遍歷，然后將遍歷順序值壓入聲明好的棧中，在訪問下一個節(jié)點之前輸出棧中的元素。輸出回路時，在創(chuàng)建時記錄

20、下所有節(jié)點的度，然后在判斷回路時，將其度為0或者是1 的節(jié)點壓入隊列，記錄下具體數(shù)目，然后將所有與度為1節(jié)點相連的節(jié)點的度減少1 ，記錄下數(shù)目。如果前面數(shù)目與該數(shù)目相加小于總結(jié)點數(shù)目，則存在回路，反之沒有回路。難點：在輸出導游路線圖時如何遍歷回去，再進行下一個節(jié)點的遍歷。解決方案：采用了庫函數(shù)里的數(shù)據(jù)結(jié)構(gòu)棧，將前面深度優(yōu)先遍歷順序記錄下來，然后再下一個節(jié)點遍歷之前將其彈棧輸出即可解決。3.3輸出兩個景點之間最短路徑和最短距離實現(xiàn)過程：采用了迪杰斯特拉算法，進行距離比較，選出最短路徑與距離。難點：如何進行比較與下一個節(jié)點連接時，距離的大小。解決方案：用一個數(shù)組來存儲下當前所有遍歷路徑上的距離之和

21、，每次連接之時進行比較。3.4輸出道路修建規(guī)劃圖實現(xiàn)過程：采用了無向圖最小生成樹的思想，用prim算法實現(xiàn)建立已存無向圖的最小生成樹。即是在圖中中選取權(quán)值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，并且vV（如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一），然后將v加入集合Vnew中，將<u, v>邊加入集合Enew中，最后使用集合Vnew和Enew來描述所得到的最小生成樹。難點：在創(chuàng)建中需要反復判斷是否回路。解決方案：每次加入新的節(jié)點后判斷有無回路。3.5查找及排序?qū)崿F(xiàn)過程：查找時讓游客輸入含有景點信息的關(guān)鍵字，然

22、后逐一從圖的節(jié)點遍歷，若節(jié)點的名稱或者是簡介中包含此關(guān)鍵字，則輸出該景點所有信息，若是多個，則將多個按遍歷順序輸出所有節(jié)點所有信息。排序時將歡迎度或者是岔路數(shù)（即是節(jié)點度數(shù)）按照冒泡排序進行排序。然后輸出節(jié)點名稱的排序順序。難點：如何在節(jié)點名稱和簡介中判斷是否含有關(guān)鍵字。解決方案：采用了C+庫函數(shù)<cstring>中的find()函數(shù)來實現(xiàn)。3.6輸出車輛的進出信息實現(xiàn)過程：采用棧與隊列的思想，當一個汽車來時，都以棧的形式進入停車場（即是誰先來誰在最里面，先進后出），如果停車場滿了，那么就在路邊等候空位出現(xiàn)，在等待時采用隊列思想，誰先來誰先走（即是誰先進入空位）。如果某輛車要離開，

23、則位于前面的車都以出棧的形式出來，先停在空閑處為其讓位，在讓位時采用進棧思想，誰在前面，誰先進去。然后的離開后，依次出棧的思想進入停車場，這樣就不會弄亂次序。難點：當停車場滿了后，有車離開時，如何讓等待的車按順序進入直到又滿為止。 解決方案：采用隊列的思想，讓等待的車存儲在隊列中，當滿后有車離開時，隊列中的車依次出隊列進入停車場，在此過程中順便判斷停車場是否已滿。第四章系統(tǒng)測試4.1. 測試方法：輸入不同特征的幾組數(shù)據(jù)，驗證輸出結(jié)果是否符合需要。4.2. 測試用例（應(yīng)該給出幾組具有不同特征的數(shù)據(jù)進行測試）：(1)節(jié)點信息：a qwer 3 1 1 b asdfg 1 0 1 c rtyuio 4 1 0鄰接邊信息：a b 1 a c 2 b c 5.(2)節(jié)點信息：a asdfg 3 1 1 b sdfgh 4 1 0 c asdfg 1 0 1 d werty 2 1 0 eqwert 5 0 0鄰接邊信息：a b 1 a c 2 b d 2 b e 34.3. 測試結(jié)果：4.4. 出現(xiàn)的問題及解決辦法：（1）在輸出導游路線圖時，棧的存儲順序有問題導致輸出順序存在偏差解決辦法：深度遍歷時，棧存儲之前判斷有沒有訪問過該節(jié)點，若沒有則壓棧存儲進去。（2）查找兩