?

目錄

零、分工

一、GitHub地址

二、PSP表格

三、控制臺程序解題思路

1. 建模思路和文本信息

2.?Dijkstra算法——/b功能

3. /c功能實現(xiàn)

4. /a功能實現(xiàn)

5. 換乘優(yōu)化

6./z測試功能實現(xiàn)

四、控制臺程序?qū)崿F(xiàn)

1. Dijkstra算法——/b功能代碼

2. /a功能代碼

3./z測試功能代碼

五、控制臺程序性能分析

?

六、控制臺黑盒測試

1./b功能

2./a功能 部分結(jié)果

3./c功能

4./z測試功能

七、界面設(shè)計

1.界面設(shè)計思路

2.將C++封裝為dll

3.圖形界面的實現(xiàn)

4.繪圖功能的實現(xiàn)

5.界面功能基本完成

八、個人感悟

---

零、分工

控制臺：張玉偉

GUI:? ?徐志濤

一、GitHub地址

github地址：https://github.com/ZhangWuren/SE-Team-Project

二、PSP表格

PSP	過程	預(yù)估耗時 （分鐘）	實際耗時 （分鐘）
Planning	計劃	10	?
·Esitimate	·估計耗時	10	15
Development	開發(fā)	1020	?
·Analysis	·需求分析	30	120
·Design Spec	·生成設(shè)計文檔	120?	200
·Design Review	·設(shè)計復(fù)審	30	20
·Coding Standard	·代碼規(guī)范	30	60
·Design	·具體設(shè)計	150	120
·Coding	·編碼	300	2400
·Code Review	·代碼復(fù)審	60	30
·Test	·測試	300	100
Reporting	報告	130	?
·Test Repor	·測試報告	60	30
·Size Measurement	·計算工作量	10	30
·Postmortem &? ?Process Improvement ?Plan	·總結(jié)，改進計劃	60	30
?	總計	1160	3155

?

三、控制臺程序解題思路

1. 建模思路和文本信息

在本項目中，建模的對象是北京地鐵圖，在建模的過程中，建立了兩個類，分別為類Station和類Map。類Map包含了類Station，具體的類圖在項目完成后展示。

在文本數(shù)據(jù)beijing-subway.txt中，記錄了地鐵站及其對應(yīng)的線路，舉例如下

1 蘋果園 1 古城 1 八角游樂園 1 八寶山 1 玉泉路 1 五棵松 1 萬壽路 1 公主墳-10 1 軍事博物館-9 1 木樨地 1 南禮士路 1 復(fù)興門-2 1 西單-4 1 天安門西 1 天安門東

首列為當前線路，接著是對應(yīng)的站名，-表示當前車站為換乘車站，跟著的是換乘線路，多個換乘線路用“，”隔開

經(jīng)統(tǒng)計，北京市地鐵最新的不重復(fù)地鐵站數(shù)量為330。

?

2.?Dijkstra算法——/b功能

在/b功能的實現(xiàn)過程中，將問題抽象出來，就是一個無向圖最短路問題，整個地鐵圖為無向圖，尋找兩點之間站點最少的路線。很容易想到的就是曾經(jīng)學(xué)過的Dijkstra算法。在Dijkstra算法中，重要的是設(shè)置鄰接矩陣。

?

3. /c功能實現(xiàn)

/c功能是輸出整條線路，只需要簡單的輸出同一條線路上的地鐵站即可。

?

4. /a功能實現(xiàn)

/a功能是從選定站點出發(fā)，遍歷全部的站點。在思考全遍歷功能時，想起了之前相似的問題有tsp問題，哈密頓回路，歐拉回路等。其中tsp問題要求每個節(jié)點只能訪問一次，和哈密頓回路類似。歐拉回路則是要求每個邊都訪問一次。這里的全遍歷功能和它們都不太一樣，本題強調(diào)要遍歷所有站點，對于邊并不做要求，只要點遍歷到了，有的邊甚至是可以忽略的，同時每個點的訪問次數(shù)也可以是多次的。

經(jīng)過在網(wǎng)絡(luò)上搜索相關(guān)資料，決定采用貪心策略+dijkstra算法，從給定起點start開始，隨機選取一個沒有路過的節(jié)點作為end，用之前/b功能的dijkstra算法找到這兩個點之間的最短路。接著將end作為新的start，再選取沒有經(jīng)歷的節(jié)點最后end，直到所有點都遍歷結(jié)束，最后再返回給定的初始start。在這個過程中，dijkstra算法的結(jié)果是局部最優(yōu)解，運用貪心的策略，可以判定整個遍歷的過程也可取到最優(yōu)的解。

5. 換乘優(yōu)化

題目中要求，換乘時因為各種原因，相當于坐了三個站。一開始我陷入了難題，因為每個站點都是獨立的，譬如“公主墳”這個換乘站，公主墳既在1號線，又在10號線，在不考慮換乘為3站的情況下，它和“萬壽路”軍事博物館“”蓮花臺“西釣魚臺”這四個站點的鄰接矩陣權(quán)值都是1，但是考慮換乘優(yōu)化時，權(quán)值要根據(jù)上一站點變化，陷入了僵局。

（所說權(quán)值均表示鄰接矩陣權(quán)值）后來經(jīng)過很長時間的思考，就是設(shè)置多個同名的換乘站表示不同地鐵線上的同一個換成站，同名換乘站之間權(quán)值為0，同線路前后站權(quán)值為1，不同線路前后站權(quán)值為3。用“公主墳”舉例，即創(chuàng)建一個1號線上的公主墳，一個10號線上的公主墳，1號線上的公主墳和“萬壽路”軍事博物館“權(quán)值為1，和”蓮花臺“西釣魚臺”權(quán)值為3表示換乘，和10號線上的公主墳權(quán)值為0，因為同個站點本質(zhì)上是在一起的，能夠成功的解決換乘優(yōu)化問題。

6./z測試功能實現(xiàn)

/z功能也比較簡單，首先根據(jù)設(shè)定好的鄰接矩陣來判斷遍歷順序是否合理。然后再判斷節(jié)點數(shù)以及是否全部遍歷，再給出遺漏的站點，比較簡單。

四、控制臺程序?qū)崿F(xiàn)

1. Dijkstra算法——/b功能代碼

void Map::search(string start, string end) //dijkstra算法 {..m_dis[startnumber] = 0;for (int i = 0; i < _TOTAL; i++){//找到和起點距離最短的點int minx = INF;int minmark;for (int j = 0; j < _TOTAL; j++){if (m_vis[j] == false && m_dis[j] <= minx){minx = m_dis[j];minmark = j;}}//并標記m_vis[minmark] = true;//更新所有和它連接的點的距離for (int j = 0; j < _TOTAL; j++){if (m_vis[j] == false && m_dis[j] > m_dis[minmark] + m_maze[minmark][j]){m_dis[j] = m_dis[minmark] + m_maze[minmark][j];m_path[j] = minmark;}}}this->printPath(endnumber, lastline); }

Dijkstra算法的另一塊重點部分為鄰接矩陣權(quán)值的設(shè)定，代碼如下

void Map::setMartix() {memset(m_maze, INF, sizeof(m_maze));//2、10為環(huán)線m_maze[23][38] = 1;m_maze[38][23] = 1;m_maze[173][207] = 1;m_maze[207][173] = 1;for (int i = 0; i < _TOTALS; i++){if (i != 0 && i != _TOTALS - 1)//排除第一個和最后一個{if (stations[i].compareLine(stations[i + 1])) {//判斷是否為同一條線路m_maze[stations[i].getNumber()][stations[i + 1].getNumber()] = 1;}if (stations[i].compareLine(stations[i - 1])) {m_maze[stations[i].getNumber()][stations[i - 1].getNumber()] = 1;}}else{if (i == 0){m_maze[stations[i].getNumber()][stations[i + 1].getNumber()] = 1;}else{m_maze[stations[i].getNumber()][stations[i - 1].getNumber()] = 1;}}} }

2. /a功能代碼

void Map::traversal(string start) {this->setTransMartix();..m_tvis[startsta.getNumber()] = true;while (visnumber > 0){for (int i = 0; i < _TOTAL; i++){if (this->m_tvis[i] != true){Station endsta = this->getStationbynumber(i);this->greedSearch(startsta, endsta);startsta = endsta;visnumber = this->getRemainStationNumber();break;}}}this->greedSearch(startsta, this->getStationbyname(start));.. }

其中函數(shù)setTransMartix()為換乘優(yōu)化時的矩陣，具體如下

void Map::setTransMartix() {memset(m_maze, INF, sizeof(m_maze));//2、10為環(huán)線m_maze[23][38] = 1;m_maze[38][23] = 1;m_maze[173][207] = 1;m_maze[207][173] = 1;for (int i = 0; i < _TOTALS; i++){if (i != 0 && i != _TOTALS - 1)//如果不是第一個和最后一個{if (stations[i].getType()){//如果是換乘車站，則需要考慮換乘的代價{//本條線路上權(quán)值仍未1if (stations[i].compareLine(stations[i + 1])) {m_maze[i][i + 1] = 1;}if (stations[i].compareLine(stations[i - 1])) {m_maze[i][i - 1] = 1;}}{//別的線路上可以換乘的站點for (int j = 0; j < _TOTALS; j++){if (stations[i].getNumber() == stations[j].getNumber() && i != j){//找到除了本身以外的同名站點m_maze[i][j] = 0;//同名站點可以直接到達，賦權(quán)值為0//和同名站點的相鄰站點，即為換乘，賦權(quán)值為3if (j != 392){//需考慮巴溝站沒有j+1站if (stations[j].compareLine(stations[j + 1])) {m_maze[i][j + 1] = 3;}if (stations[j].compareLine(stations[j - 1])) {m_maze[i][j - 1] = 3;}}else{m_maze[i][j - 1] = 3;}}}}}else{//如果不是換乘車站，直接將權(quán)值賦為1if (stations[i].compareLine(stations[i + 1])) {m_maze[i][i + 1] = 1;}if (stations[i].compareLine(stations[i - 1])) {m_maze[i][i - 1] = 1;}}}else{if (i == 0){m_maze[i][i + 1] = 1;}else{m_maze[i][i - 1] = 1;m_maze[i][195] = 3;}}} }

3./z測試功能代碼

void Map::test(string filename) {this->setMartix();memset(this->m_tvis, false, sizeof(m_tvis));fstream fin(filename);string readline;string stas[_TOTALS * 10];for (int i = 0; i < _TOTALS * 10; i++){stas[i].clear();}getline(fin, readline);int count = stoi(readline);int count1 = 0;int i = 0;while (getline(fin, readline)){stas[i] = readline;i++;}for (int i = 1; !stas[i].empty(); i++){Station s1 = this->getStationbyname(stas[i]);Station s2 = this->getStationbyname(stas[i - 1]);m_tvis[s1.getNumber()] = true;m_tvis[s2.getNumber()] = true;if (!this->m_maze[s1.getNumber()][s2.getNumber()]){cout << "error" << endl;return;}}int novissta[_TOTAL];memset(novissta, -1, sizeof(novissta));for (int i = 0, j = 0; i < _TOTAL; i++){if (this->m_tvis[i] == false){novissta[j] = i;j++;}}if (novissta[0] == -1){cout << "true" << endl;}else{cout << "false" << endl;cout << "遺漏的站點有:" << endl;for (int i = 0; novissta[i] != -1; i++){cout << this->getStationbynumber(novissta[i]).getName() << endl;}} }

五、控制臺程序性能分析

對全遍歷功能進行性能分析，發(fā)現(xiàn)耗時較長的函數(shù)是全遍歷函數(shù)traversal以及其調(diào)用的貪心迪杰斯特拉搜索greedSearch,均控制在較短時間，不再做進一步優(yōu)化。

還有讀取地圖的setMap函數(shù)，本項目采用txt方式，逐行讀取北京地鐵圖，因為數(shù)據(jù)量較小，故不做進一步改進。

六、控制臺黑盒測試

1./b功能

和百度地圖比較

基本類似

2./a功能 部分結(jié)果

3./c功能

房山線

4./z測試功能

將/a的結(jié)果用作測試時，應(yīng)該為true

刪除部分/a的結(jié)果

造成錯誤站點

七、界面設(shè)計

1.界面設(shè)計思路

以C++代碼為功能，將函數(shù)封裝為dll供圖形界面調(diào)用，因為在小學(xué)期的時候用過C#寫過圖形界面，所以決定采用C#構(gòu)建圖形界面，在C++函數(shù)中將要走過的站點依次輸出到文本文件中，然后再根據(jù)之前存儲的坐標信息將各個站點的位置和路線畫在以北京地鐵線路圖為背景的畫布上。

2.將C++封裝為dll

C++函數(shù)封裝成動態(tài)鏈接庫時才能提供接口供C#進行調(diào)用，首先創(chuàng)建一個dll項目，然后將之前編寫好的C++頭文件復(fù)制到這個項目中，再將要用到的函數(shù)聲明在dll項目的頭文件中，如下圖所示

之后在C#中就可以直接聲明調(diào)用函數(shù)了

項目目錄大致是這樣的，然后再將項目進行編譯 ，項目目錄下會生成一個名字為Subway_dll.dll的動態(tài)鏈接庫文件，我們這時就的到想要的dll文件，然后將這個dll文件復(fù)制到C#圖形界面項目的可執(zhí)行文件目錄下，就能在圖形界面進行C++函數(shù)的調(diào)用了

3.圖形界面的實現(xiàn)

在窗體中導(dǎo)入北京地鐵線路圖，想要正確的繪圖首先要得到各個站點的坐標，然后為了得到各個點的坐標，我寫了一個Onclick事件，每點一次就獲得當前位置的坐標，將各個站點的坐標依次記錄在Beijing_Subway_Location.txt文件中。然后就可以根據(jù)經(jīng)過的站點信息畫圖了。

為了能夠在C#項目中調(diào)用遍歷功能的C++函數(shù)，需要再主函數(shù)這里引入聲明要調(diào)用的函數(shù)

這個函數(shù)會將經(jīng)過的站點信息依次輸出存入txt文件中，然后C#讀這個文件，進行繪圖。

4.繪圖功能的實現(xiàn)

因為在繪制路線圖的過程中會反復(fù)進行繪圖，所以編寫了一個DrawTool類來實現(xiàn)繪圖功能，這個類中會有兩個功能，一個是畫圖，一個是畫帶箭頭的線來表明路線，代碼如下

public static class DrawTool{/// <summary>/// 線畫筆顏色，在構(gòu)造函數(shù)中初始化何種顏色/// </summary>public static Color line_brush_color = new Color();/// <summary>/// 圈畫筆顏色，在構(gòu)造函數(shù)中初始化何種顏色/// </summary>public static Color circle_brush_color = new Color();static DrawTool(){DrawTool.line_brush_color = Color.FromArgb(0, 0, 0);DrawTool.circle_brush_color = Color.FromArgb(0, 0, 255);}/// <summary>/// 繪制指定顏色粗細帶箭頭的線/// </summary>public static void DrawArrowLine(Graphics g, float x1, float y1, float x2, float y2, float width){Pen p = new Pen(DrawTool.line_brush_color, width);p.EndCap = LineCap.ArrowAnchor; // 定義線尾的樣式為箭頭g.DrawLine(p, x1, y1, x2, y2);}/// <summary>/// 繪制圓心(x,y),半徑r,寬度為width的空心圓/// </summary>public static void DrawCircle(Graphics g, float x, float y, float r, float width){Pen p = new Pen(DrawTool.circle_brush_color, width);g.DrawEllipse(p, (int)(x - r), (int)(y - r), (int)(2 * r), (int)(2 * r));}}

5.界面功能基本完成

設(shè)置了一個Button_Click事件，點擊Search按鈕即可實現(xiàn)繪制線路圖，點擊Search先會調(diào)用ResetMap函數(shù)來刷新界面，防止上一次的繪圖對本次繪圖發(fā)生影響，具體調(diào)用繪圖功能的代碼如下

public void ResetMap(){Bitmap bitmap = new Bitmap("subway_map.bmp");Rectangle r = new Rectangle(0, 0,this.pictureBox1.Size.Width, this.pictureBox1.Size.Height);Form1.graphics.DrawImage(bitmap, r); // 使用原地圖覆蓋} StreamReader sr = new StreamReader("subway_station.txt", Encoding.Default);String readline;float x1 = 0, x2 = 0, y1 = 0, y2 = 0;int flag_first = 0;int index = 0;while ((readline = sr.ReadLine()) != null){x2 = 0;y2 = 0;index = 0;while (readline[index] != ' '){x2 = x2 * 10 + readline[index] - '0';index++;}index++;while (index < readline.Length){y2 = y2 * 10 + readline[index] - '0';index++;}DrawTool.DrawCircle(graphics, x2, y2, 8,2);if (flag_first == 0) flag_first = 1;else{//畫從x1，y1到x2，y2的線DrawTool.DrawArrowLine(graphics, x1, y1, x2, y2, 2);}x1 = x2;y1 = y2;}

執(zhí)行如下命令

界面如圖所示，手動輸入坐標會有誤差，站點繪制的并不是非常準確，在可以接受的誤差范圍內(nèi)

八、個人感悟

張玉偉：在本次結(jié)對項目中，我負責控制臺程序的編寫，運用了曾經(jīng)學(xué)過的迪杰斯特拉算法，對地鐵圖的建模思想也有所收獲，同時對多人共同使用github進行團隊合作，收獲頗多。

總結(jié)

以上是生活随笔為你收集整理的软件工程团队项目——subway的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。