数据结构——校园导游系统
校園導(dǎo)游系統(tǒng)
1. 要求
大二下學(xué)期修了數(shù)據(jù)結(jié)構(gòu)這門課,課設(shè)的要求是做一個校園導(dǎo)航系統(tǒng)。詳細(xì)的要求如下
問題描述:
當(dāng)我們參觀校園時,會遇到如下問題:從當(dāng)前所處位置去校園另外一個位置,要走什么樣的路線距離最短?本課程設(shè)計任務(wù)要求,在給出校園各主要建筑的名稱信息及有路線連通的建筑之間的距離的基礎(chǔ)上,利用校園導(dǎo)游系統(tǒng)計算出給定起點到終點之間距離最近的行進(jìn)路線。
任務(wù)要求:
(1)從地圖文件中讀取校園主要建筑信息及建筑之間的距離信息。
(2)計算出給定的起點到終點之間距離最近的行進(jìn)路線。
(3)輸出該路線及其總距離。
2. 分析
2.1 數(shù)據(jù)提取
第一個問題,如何看地圖把信息提取出來,根據(jù)目前所掌握的知識來看并沒有很智能、自動化的方法,只有人手工地把地圖重要信息進(jìn)行提取并錄入。這些信息包括各個地點與各地點之間的距離。接下來就以我的學(xué)校地圖為例。
為了演示的方便,便于后期算法正確與否的驗證,提取中其中15個重要的點
同樣為了演示、檢驗的方便,目測(編造)點與點之間的距離以及關(guān)系,來抽象成一張圖:
而數(shù)據(jù)結(jié)構(gòu)與算法這門課可以幫助解決的問題是怎么來存儲這些數(shù)據(jù)。這個問題比較好回答,地圖抽象出來就是圖結(jié)構(gòu),而圖的信息的常常用鄰接矩陣來存儲。
2.2 路徑搜索
第二個問題,如何得到最優(yōu)路徑,以我的水平,或者說我接觸過、學(xué)過的方法來說,可以選擇的有兩種算法,Dijkstra算法和Floyd算法。
3 設(shè)計
3.1 功能設(shè)計
首先,要先確定這個系統(tǒng)能實現(xiàn)什么樣的功能。
3.1.1 菜單
第一肯定是要有一個菜單,當(dāng)然,這是一個課設(shè)就不搞什么UI了,就是最基礎(chǔ)的輸入選項選擇式菜單就可以了。
3.1.2 點位選擇
第二,要找出兩點最短路徑,那肯定需要能夠進(jìn)行起點,終點的選擇
3.1.3 地圖數(shù)據(jù)來源選擇
第三,我希望我做出來的東西不只是一個只是用來演示的東西,所以地圖的數(shù)據(jù)肯定不能寫死,希望能夠?qū)崿F(xiàn)只要能把地圖數(shù)據(jù)抽取出來抽象成圖,無論多大多小,都可以用我這個工具來找最短路徑。因此,這就需要這個系統(tǒng)可以進(jìn)行地圖數(shù)據(jù)來源的選擇。可以是默認(rèn)的,也可以是自己手動輸入的圖數(shù)據(jù)。并且地圖起點、中斷選擇界面的內(nèi)容可以根據(jù)我們的數(shù)據(jù)來源進(jìn)行對應(yīng)的改變。
如果想要自定義輸入地圖數(shù)據(jù),那么肯定需要有一個固定的輸入格式,這樣才能通過程序來把輸入的數(shù)據(jù)提取出來,所以我們要規(guī)定一個格式。我的規(guī)定是,需要把每個點之間的關(guān)系都告訴程序,因此就需要很多組的兩個端點與端點距離。因此我規(guī)定
每組三個數(shù)據(jù),組內(nèi)數(shù)據(jù)以空格分開,組間以分號分開。例如節(jié)點1序號 節(jié)點2序號 權(quán)值;節(jié)點3序號 節(jié)點4序號 權(quán)值;...這個自定義的問題解決的,但是隨后又想到,如果這個圖是一個很大的圖,我們自己手動輸入會很麻煩,但是這是必須的。可是最要救命的是,如果下一次還想接著用,那么就要再輸入一大堆,非常的麻煩,這是可以避免的。因此可以設(shè)計一個配置文件的方法方式,通過直接讀取配置文件的內(nèi)容來直接配置好地圖數(shù)據(jù)。這樣的話我們也需要再對配置文件的內(nèi)容格式進(jìn)行一個規(guī)范,我很簡單地使用了這樣的標(biāo)準(zhǔn)
地圖數(shù)據(jù)在前 地圖節(jié)點名稱在后,寫在同一行,之間用星號(*)隔開,最終以感嘆號(!)結(jié)尾 地圖數(shù)據(jù):每組三個數(shù)據(jù),組內(nèi)數(shù)據(jù)以空格分開,組間以分號分開 例如:節(jié)點1序號 節(jié)點2序號 權(quán)值;節(jié)點3序號 節(jié)點4序號 權(quán)值;... 節(jié)點名稱:順序填寫逗號分割. 例如:北門,東門,南門 例如:1 2 30; 2 3 50;*北門,東門,西門! 注意:為了避免中文亂碼的問題,配置文件的編碼格式需要是ANSI3.1.4 算法選擇
第四,能夠使用不同的算法來處理。現(xiàn)在我還是個小菜雞,只會兩種算法Dijkstra算法和Floyd算法,而且這兩個算法最后的結(jié)果看不出來差別。
3.2 代碼結(jié)構(gòu)設(shè)計
我對于程序的代碼結(jié)構(gòu)沒什么研究,并且沒有寫出過結(jié)構(gòu)優(yōu)美的代碼,那是我很渴望的。我希望自己寫出來的程序是很清晰明了的,代碼之間的關(guān)系、結(jié)構(gòu)都很清晰,我也在慢慢地摸索。而我所知道或者所秉承的觀念是很樸素的:1.不同功能的代碼塊要盡量解耦 2. 變量盡可能地用面向?qū)ο蟮乃季S來進(jìn)行管理,在C語言里具體的體現(xiàn)就是盡可能用結(jié)構(gòu)體將變量進(jìn)行整合。
因為在RM戰(zhàn)隊寫過屎山代碼,所以我腦子里有一個很淺顯或者說是粗俗的觀點:各個部分要有一個Controller結(jié)構(gòu)體來進(jìn)行管理。因此懷著這樣的想法,我把代碼在結(jié)構(gòu)上整體分成了三部分:
- 算法模塊
- 系統(tǒng)管理模塊
- 界面展示模塊
然后整個系統(tǒng)圍繞著三個控制器(結(jié)構(gòu)體)展開:
- 系統(tǒng)控制器 SystemController
- 算法控制器 DijkstraController、FloydController
- 圖信息控制器 MGraph
在控制器中SystemController掌控著整個系統(tǒng)的所有信息,如:地圖數(shù)據(jù)、配置文件數(shù)據(jù)、算法控制器、選項結(jié)果等等。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-GWOBNuq8-1671969502895)(https://www.houenup.com/wp-content/uploads/2022/12/數(shù)據(jù)結(jié)構(gòu)課設(shè)程序控制器.png)]
4 具體實現(xiàn)
4.1 程序流程
整個程序的入口是main函數(shù),在main函數(shù)中調(diào)用System_Start()進(jìn)入系統(tǒng),System_Start的作用就是將系統(tǒng)中核心的控制器(控制結(jié)構(gòu)體)之間建立聯(lián)系并初始化相關(guān)數(shù)據(jù),然后進(jìn)入界面的控制。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-UARpp9Z8-1671969502895)(https://www.houenup.com/wp-content/uploads/2022/12/數(shù)據(jù)結(jié)構(gòu)課設(shè)程序流程圖1.png)]
4.2 算法實現(xiàn)
4.2.1 Dijkstra算法:
? Dijkstra算法的核心是對于三個列表的更新迭代,三個列表分別為,前驅(qū)節(jié)點列表、頂點最短路徑列表、頂點是否確認(rèn)列表。
具體的算法實現(xiàn)步驟為:
算法控制器
/** Dijkstra算法控制器 **/ typedef struct {int forerunner_list[MAX_VERTICES]; /** 前驅(qū)頂點列表 **/int confirmed_flag_list[MAX_VERTICES]; /** 該頂點是否確定了最短路徑 **/int distance_list[MAX_VERTICES]; /** 最短路徑距離 **/int start_point; /** 起點 **/int end_point; /** 終點 **/int latest_confirmed_node; /** 最新被確認(rèn)的節(jié)點 **/int route[MAX_VERTICES]; /** 最終算出來的最優(yōu)路徑 **/int sum_distance; /** 路徑總距離 **/MGraph * mgraph; /** 存儲了圖數(shù)據(jù)的指針 **/ }DijkstraControler;初始化函數(shù)
/*** @brief 算法初始化* @param controler:算法控制器* @param system_data: 系統(tǒng)控制器* */ void Dijkstra_Init(DijkstraControler* controler,SystemControler* system_data) {/*** 初始化:1.出發(fā)點是第一的已經(jīng)確定最短路徑的頂點* 2.更新與出發(fā)點有路徑的頂點的最短路徑和前驅(qū)頂點* */int distance_temp = 0;/* 獲取需要使用的信息 */controler->mgraph = system_data->graph_data;controler->start_point = system_data->start_point;controler->end_point = system_data->end_point;for (int i = 0; i < MAX_VERTICES; ++i) {controler->distance_list[i] = 0;controler->confirmed_flag_list[i] = 0;controler->forerunner_list[i] = 0;}int node_num = controler->mgraph->numNodes;/*頂點最短路徑初始化為無窮*/for (int i = 0; i < node_num; ++i) {controler->distance_list[i+1] = GIGANTIC; //0棄除不用 從1開始}/* 出發(fā)點是第一的已經(jīng)確定最短路徑的頂點,自己到自己的距離是0 */controler->latest_confirmed_node = controler->start_point;controler->distance_list[controler->start_point] = 0;controler->confirmed_flag_list[controler->start_point] = 1; //起始點已經(jīng)確定controler->forerunner_list[controler->start_point] = controler->start_point;/* 更新與出發(fā)點有路徑的頂點的最短路徑和前驅(qū)頂點 */Update_Distance_Predecessor(controler,controler->start_point);}更新確認(rèn)節(jié)點函數(shù)
/*** @brief 更新確認(rèn)節(jié)點節(jié)點* */ void Update_Confirmed_Node(DijkstraControler* controler) {int min_distance_index;for (int i = 0; i < controler->mgraph->numNodes; ++i) //找最短路徑最小的頂點{if (controler->confirmed_flag_list[i+1] != 1){min_distance_index = Find_Min(controler->distance_list[i+1],i+1);controler->latest_confirmed_node = min_distance_index; //更新最新被確認(rèn)的頂點}}min_distance = GIGANTIC;controler->confirmed_flag_list[controler->latest_confirmed_node] = 1; }更新最短路徑與前驅(qū)節(jié)點函數(shù)
/*** @brief 更新與確認(rèn)頂點有路徑的頂點的最短路徑* @param controler:控制器* @param comfirmed_point: 需要更新的與其之間有路徑的點* */void Update_Distance_Predecessor(DijkstraControler* controler,int comfirmed_point) {int node_num = controler->mgraph->numNodes;int distance_temp = 0;for (int i = 0; i < node_num; ++i){distance_temp = controler->mgraph->arc[comfirmed_point][i+1];if ( distance_temp != 0) //找到有路徑的頂點的路徑長度{//如果與confirmed_point有關(guān)的路徑的最短距離比它原來的最短距離更小 就更新它if (distance_temp + controler->distance_list[comfirmed_point] < controler->distance_list[i+1] || controler->distance_list[i+1]==GIGANTIC){controler->distance_list[i+1] = distance_temp + controler->distance_list[comfirmed_point]; //更新最短距離Update_predecessor_node(controler,comfirmed_point,i+1);//更新前驅(qū)頂點}}} }算法循環(huán)函數(shù)
/*** @brief 算法循環(huán)* @param controler:算法控制器* */void Dijkstra_Loop(DijkstraControler* controler) {/*** 循環(huán):1.從未確定最短路徑的頂點中選取最短路徑最小的頂點為新確定最短路徑的頂點;* 2.更新與新確認(rèn)頂點有路徑的頂點的最短路徑和前驅(qū)頂點。(如果新路徑更短就更新,更長則不更新)** 結(jié)束條件:所有的點都被確定過最短路徑了即尋找完畢* */int min_distance = 0;int new_point = 0;while (!controler->confirmed_flag_list[controler->end_point]){/*從未確定最短路徑的頂點中選取最短路徑最小的頂點為新確定最短路徑的頂點*/Update_Confirmed_Node(controler);/* 更新與新確認(rèn)頂點有路徑的頂點的最短路徑和前驅(qū)頂點 */Update_Distance_Predecessor(controler,controler->latest_confirmed_node);}}4.2.2 Floyd算法
Floyd算法的核心在于對兩張表的更新迭代,分別為兩點距離表和兩點間中繼節(jié)點表。
具體的算法實現(xiàn)步驟為:
Floyd算法控制器
/** Floyd算法控制器 **/ typedef struct {int shortest_distance_table[MAX_VERTICES][MAX_VERTICES]; /** 兩點之間最短距離表 (0,0)棄用 **/int relay_node_table[MAX_VERTICES][MAX_VERTICES]; /** 兩點之間中繼節(jié)點表 (0,0)棄用 **/int start_point; /** 起點 **/int end_point; /** 終點 **/int route[MAX_VERTICES]; /** 最終算出來的最優(yōu)路徑 **/int route_num; /** 路線途徑點個數(shù) **/int sum_distance; /** 路徑總距離 **/MGraph * mgraph; /** 存儲了圖數(shù)據(jù)的指針 **/ }FloydControler;初始化函數(shù)
/*** @brief 算法初始化函數(shù)* */ void Floyd_Init(FloydControler* controler, SystemControler* system_data) {controler->mgraph = system_data->graph_data;controler->start_point = system_data->start_point;controler->end_point = system_data->end_point;controler->route[0] = controler->start_point;controler->route_num = 1;/* 初始化兩張表 */for (int i = 0; i < MAX_VERTICES-1; ++i) {for (int j = 0; j < MAX_VERTICES-1; ++j) {controler->relay_node_table[i+1][j+1] = GIGANTIC;if (controler->mgraph->arc[i+1][j+1] == 0){if (i == j){controler->shortest_distance_table[i+1][j+1] = 0;} else{controler->shortest_distance_table[i+1][j+1] = GIGANTIC;}}else{controler->shortest_distance_table[i+1][j+1] = controler->mgraph->arc[i+1][j+1];}}} }更新循環(huán)函數(shù)
/*** @brief 更新循環(huán)* */void Floyd_Upgrade_Loop(FloydControler* controler) {int node_num = controler->mgraph->numNodes;//最短距離表更新for (int v = 1; v < node_num; ++v) {for (int i = 1; i < node_num+1; ++i) {for (int j = 1; j < node_num+1; ++j) {//中繼節(jié)點到某一點不通就不更新if (controler->shortest_distance_table[i][v]==GIGANTIC || controler->shortest_distance_table[v][j] == GIGANTIC){;}else{ //中繼到兩邊都通,總長更小就更新if ((controler->shortest_distance_table[i][j] == GIGANTIC) || (controler->shortest_distance_table[i][j]>controler->shortest_distance_table[i][v]+controler->shortest_distance_table[v][j])){controler->shortest_distance_table[i][j] = controler->shortest_distance_table[i][v]+controler->shortest_distance_table[v][j];controler->relay_node_table[i][j] = v; //更新中繼節(jié)點表}}}}}}路徑尋找函數(shù)
/*** @brief 尋找最短路徑* */void Floyd_Find_Path(FloydControler* controler,int start,int end) {if (controler->relay_node_table[start][end] == GIGANTIC){controler->route[controler->route_num++] = end;controler->sum_distance+=controler->shortest_distance_table[start][end];} else{int mid = controler->relay_node_table[start][end];Floyd_Find_Path(controler,start,mid);Floyd_Find_Path(controler,mid,end);} }4.3 管理實現(xiàn)
總體來說整個系統(tǒng)管理起來的邏輯是比較簡單的,就是通過用戶在對應(yīng)界面選擇的選項來調(diào)用不同的函數(shù)實現(xiàn)界面的跳轉(zhuǎn)、數(shù)據(jù)的選擇與輸出等。
其中相對花了一些時間的地方在輸入數(shù)據(jù)的提取、配置文件的數(shù)據(jù)提取上。
主菜單管理
/*** @brief 主菜單管理* */void MainMenu_Control(SystemControler* system_controler) {uint8_t temp = 0;static int time_flag = 0; //用來表示是首次進(jìn)入該界面還是成功設(shè)置完成后再次進(jìn)入的 0 首次 1 成功設(shè)置 2 設(shè)置錯誤system("cls"); //刷新界面MainMenu_Show();switch (time_flag) {case 0:printf("請輸入選項:");scanf("%s",&temp);break;case 2:printf("請選擇正確選項!\r\n");printf("請輸入選項:");scanf("%s",&temp);break;}if ((temp-48 <1 || temp-48>6) && temp != '*'){time_flag = 2;MainMenu_Control(system_controler);}switch (temp-48) {case 1:MapDataSelectionMenu_Control(system_controler);break;case 2:Origin_LocationSelectionMenu_Control(system_controler);break;case 3:Destination_LocationSelectionMenu_Control(system_controler);break;case 4:AlgorithmSelectionMenu_Control(system_controler);break;case 5:RouteOutputMenu_Control(system_controler);break;case 6:Configuration_Import_Control(system_controler);break;case -6:Thanks_Show();break;} }可以看到這個switch就是選項的邏輯,選擇不同的選項會調(diào)用不同的菜單管理控制函數(shù),每一個菜單管理控制函數(shù)都包括菜單的展示、邏輯的實現(xiàn)… 基本上方法是一樣的。
導(dǎo)游系統(tǒng)執(zhí)行函數(shù)
系統(tǒng),或者說是算法,的執(zhí)行是在最后用戶選擇輸出地址的時候才開始執(zhí)行的。如果使用的是默認(rèn)的地圖數(shù)據(jù),那么地圖數(shù)據(jù)的提取也是在這個時候開始的。
/*** @brief 導(dǎo)游系統(tǒng)執(zhí)行函數(shù)* */ void Work_Start(SystemControler* system_controler) {Information_Entry(system_controler);/*使用Dijkstra算法*/if (system_controler->algorithm_options == 0){Dijkstra_Init(system_controler->pdijkstra_controler,system_controler);Dijkstra_Loop(system_controler->pdijkstra_controler);Dijkstra_Find_Path(system_controler->pdijkstra_controler);}/*使用Floyd算法*/else{Floyd_Init(system_controler->pfloyd_controler,system_controler);Floyd_Upgrade_Loop(system_controler->pfloyd_controler);Floyd_Find_Path(system_controler->pfloyd_controler,system_controler->pfloyd_controler->start_point,system_controler->pfloyd_controler->end_point);} }地圖數(shù)據(jù)錄入函數(shù)
該函數(shù)的所有精髓都在數(shù)據(jù)數(shù)據(jù)提取函數(shù)中。
/*** @brief 系統(tǒng)景點信息錄入函數(shù)* @param data:存放景點數(shù)據(jù)的鄰接矩陣指針* */ void Information_Entry(SystemControler* system_controler) {if (system_controler->map_data_options) //使用自定義地圖數(shù)據(jù){Data_Extracte(data_buffer,system_controler->data); //將原始數(shù)據(jù)提取出來并轉(zhuǎn)換成整數(shù)類型存儲在extracted_data中/*鄰接矩陣初始化*/Adjacency_Matrix_Init(system_controler->graph_data,system_controler->data);}else{Adjacency_Matrix_Init(system_controler->graph_data,system_controler->data);}}數(shù)據(jù)數(shù)據(jù)提取函數(shù)
對于有固定格式的數(shù)據(jù)的提取,我一般都是用狀態(tài)機(jī)編程的思想來實現(xiàn)。而這個實現(xiàn)的方式是從一個開源的RM裁判系統(tǒng)解析程序中學(xué)習(xí)到的。當(dāng)然這樣的方法可能不是最好的,但是易懂、易實現(xiàn)。這個方法的總體思路是,把解析的過程分成若干步,然后用枚舉來定義這個連續(xù)的步驟,通過枚舉變量的數(shù)值來得知到了哪一步,下一步該到哪個狀態(tài)。
/*** @brief 輸入數(shù)據(jù)提取操作* @param data_input:需要提取數(shù)據(jù)的存儲地址* @param data_output:提取數(shù)據(jù)輸出地址* */ void Data_Extracte(char* data_input,int* data_output) {int run_flag = 1;int index_buffer = 0; //提取暫存buffer索引int index_raw_data = 0; //原始數(shù)據(jù)掃描索引int index_data = 0; //提取完成數(shù)據(jù)索引char buffer[20]; //用來暫存提取的時候讀到的數(shù)據(jù)while (run_flag){switch (step){case NODE_1:{if(data_input[index_raw_data] == ' '){step++;}else{buffer[index_buffer] = data_input[index_raw_data];index_raw_data++;index_buffer++;}}break;case BLANK_1: /*遇見空格就把上一次的字符數(shù)據(jù)給轉(zhuǎn)換成數(shù)字?jǐn)?shù)據(jù)存在存放提取數(shù)據(jù)的數(shù)組中*/{buffer[index_buffer] = '\0'; /*將數(shù)組構(gòu)造成字符串形式*/data_output[index_data] = atoi(buffer); //將提取出來的數(shù)據(jù)轉(zhuǎn)換成int型存放在處理好的數(shù)組中memset(buffer,0,sizeof(buffer)/sizeof(char));step++;index_raw_data++;index_buffer++;index_buffer = 0; //重置buffer索引index_data++;}break;case NODE_2:{if(data_input[index_raw_data] == ' '){step++;}else{buffer[index_buffer] = data_input[index_raw_data];index_raw_data++;index_buffer++;}}break;case BLANK_2:{buffer[index_buffer] = '\0'; /*將數(shù)組構(gòu)造成字符串形式*/data_output[index_data] = atoi(buffer); //將提取出來的數(shù)據(jù)轉(zhuǎn)換成int型存放在處理好的數(shù)組中memset(buffer,0,sizeof(buffer)/sizeof(char));step++;index_raw_data++;index_buffer++;index_buffer = 0; //重置buffer索引index_data++;}break;case EDGE:{if(data_input[index_raw_data] == ';'){step++;}else{buffer[index_buffer] = data_input[index_raw_data];index_raw_data++;index_buffer++;}}break;case BRANCH:{buffer[index_buffer] = '\0'; /*將數(shù)組構(gòu)造成字符串形式*/data_output[index_data] = atoi(buffer); //將提取出來的數(shù)據(jù)轉(zhuǎn)換成int型存放在處理好的數(shù)組中memset(buffer,0,sizeof(buffer)/sizeof(char));step++;index_raw_data++;index_buffer++;index_buffer = 0; //重置buffer索引index_data++;}break;case END:{if(data_input[index_raw_data] == 0){run_flag = 0;}else{step = 0;}}}}}5 鏈接
5.1 演示視頻
https://www.bilibili.com/video/BV1e14y1P7Aa/?spm_id_from=333.999.0.0&vd_source=e240c7dafa7cf5d1b5ebfa7d64e9b941
5.2 源碼鏈接
https://gitee.com/HouEna/campus-tour-guide-system
總結(jié)
以上是生活随笔為你收集整理的数据结构——校园导游系统的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 软件众包 业余主义的复兴
- 下一篇: HTML:给自己设计一个简单的专属网页音