景点旅游信息系统——C/C++程序设计、Qt图形化界面
🔋 一個(gè) Qt、C/C++ 程序設(shè)計(jì)項(xiàng)目
文章目錄
- 一、簡(jiǎn)單的效果演示
- 二、系統(tǒng)要求
- 三、系統(tǒng)設(shè)計(jì)
- 四、框架搭建
- 五、算法設(shè)計(jì)
- 5.1 創(chuàng)建景區(qū)景點(diǎn)分布圖的算法：
- 5.2 判斷創(chuàng)建的導(dǎo)游線路圖有無(wú)回路的算法——拓?fù)鋱D：
- 5.3 輸出給定入口景點(diǎn)的導(dǎo)游線路圖的算法——DFS
- 5.4 求兩個(gè)景點(diǎn)間的最短路徑的算法——Floyd
- 5.5 給出道路建設(shè)(最小生成樹(shù))的算法——Kruskal
- 六、測(cè)試數(shù)據(jù)及其結(jié)果分析
- 七、完整代碼
- 八、參考附錄
一、簡(jiǎn)單的效果演示
??● 說(shuō)明：簡(jiǎn)單演示了一下新增/刪除結(jié)點(diǎn)和邊，以及一些功能按鈕。
二、系統(tǒng)要求
??● 景區(qū)旅游信息系統(tǒng)，需要實(shí)現(xiàn)的功能有如下 4 項(xiàng)：
????(1) 能自行建立一個(gè)導(dǎo)游線路地圖。能通過(guò)拓樸排序判斷圖中有無(wú)回路，若有回路，則打印輸出回路中的景點(diǎn)。
????(2) 若給出一個(gè)入口景點(diǎn)，能自行采用深度優(yōu)先策略建立一個(gè)導(dǎo)游線路圖。
????(3) 在導(dǎo)游線路圖中，能實(shí)現(xiàn)查看從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑。
????(4) 景區(qū)道路能保證連通所有景點(diǎn)，且能通過(guò)最小代價(jià)生成樹(shù)的策略來(lái)修建道路（代價(jià)只與它的里程有關(guān)）。
三、系統(tǒng)設(shè)計(jì)
四、框架搭建
??● 項(xiàng)目管理如下：
??● 說(shuō)明：
????① main.cpp 是主函數(shù)入口。
????② main_window.cpp 是 “開(kāi)始” 界面的源代碼。
????③ tour_system.cpp 是景區(qū)旅游信息系統(tǒng)的源代碼 。
??● 頭文件tour_system.h 如下：
??● 說(shuō)明【這段話很關(guān)鍵】：其中主要反復(fù)調(diào)用的函數(shù)是mousePressEvent()，即 “鼠標(biāo)相應(yīng)函數(shù)”。因?yàn)槲覀冊(cè)谶M(jìn)行相關(guān)圖形操作時(shí)，都是以 “點(diǎn)” 為基本操作對(duì)象（若是要確定一條邊，也是點(diǎn)擊某兩個(gè)點(diǎn)。若要進(jìn)行某項(xiàng)功能，也是點(diǎn)擊相應(yīng)的功能按鈕一下）。所以我們主要在mousePressEvent()寫(xiě) “景區(qū)系統(tǒng)的主核心艙”，配合switch()語(yǔ)句來(lái)實(shí)現(xiàn)對(duì)各個(gè)功能的反復(fù)調(diào)用。
??● mousePressEvent()的 框架版代碼 如下：
void Tour_System::mousePressEvent(QMouseEvent* e) // 鼠標(biāo)點(diǎn)擊事件 {if (e->button() == Qt::LeftButton) // 按左鍵{switch(function_num){case 1: // 添加點(diǎn)function_num = 0; // 執(zhí)行完后歸零...break;case 2: // 新增邊(選擇邊的起點(diǎn))function_num = 3;...break;case 3: // 新增邊(選擇邊的終點(diǎn))function_num = 0; ... break;case 4: // 刪除結(jié)點(diǎn)function_num = 0; ...break;case 5: // 刪除邊(選擇邊的起點(diǎn))function_num = 6; ...break;case 6: // 刪除邊(選擇邊的終點(diǎn))function_num = 0; ...break;case 7: // 編輯結(jié)點(diǎn)的標(biāo)簽function_num = 0; ...break;case 8: // 修改邊(選擇邊的起點(diǎn))function_num = 9; ...break;case 9: // 修改邊(選擇邊的終點(diǎn))function_num = 0; ...break;case 10: // 建立導(dǎo)游路線圖(DFS)function_num = 0; ...break;case 11: // 求兩點(diǎn)之間的最短路徑(Floyd)——選擇起點(diǎn)function_num = 12; ...break;case 12: // 求兩點(diǎn)之間的最短路徑(Floyd)——選擇終點(diǎn)...break;}} }void Tour_System::on_Btn_1_1_clicked() // 新增結(jié)點(diǎn) { function_num = 1... }void Tour_System::on_Btn_1_2_clicked() // 新增邊 { function_num = 2... }void Tour_System::on_Btn_1_3_clicked() // 刪除結(jié)點(diǎn) { function_num = 4... }void Tour_System::on_Btn_1_4_clicked() // 刪除邊 { function_num = 5... }void Tour_System::on_Btn_1_5_clicked() // 編輯結(jié)點(diǎn) { function_num = 7... }void Tour_System::on_Btn_1_6_clicked() // 修改邊 { function_num = 8... }void Tour_System::on_Btn_2_1_clicked() // 判斷是否有回路 { ... }void Tour_System::on_Btn_2_2_clicked() // 建立一張導(dǎo)游線路圖(DFS) { function_num = 10... }void Tour_System::on_Btn_2_3_clicked() // 求兩點(diǎn)之間的最短路徑(Floyd) { function_num = 11... }void Tour_System::on_Btn_2_4_clicked() // 最小生成樹(shù)(Kruskal) { ... }void Tour_System::on_Btn_3_1_clicked() // 顯示所有邊長(zhǎng) { ... }void Tour_System::on_Btn_3_2_clicked() // 加載地圖 { ... }void Tour_System::on_Btn_3_3_clicked() // 保存地圖 { ... }void Tour_System::on_Btn_3_4_clicked() // 加載背景 { ... }void Tour_System::on_Btn_3_5_clicked() // 清除屏幕 { ... }五、算法設(shè)計(jì)
??● 在寫(xiě)算法之前，先把所有要用到的全局變量展示出來(lái)，如下圖所示：
5.1 創(chuàng)建景區(qū)景點(diǎn)分布圖的算法：
??● 運(yùn)用繪圖函數(shù)paintEvent()和鼠標(biāo)點(diǎn)擊響應(yīng)函數(shù)mousePressEvent()來(lái)處理景區(qū)景點(diǎn)以及道路的繪制與連接。
??● 景點(diǎn)的繪制機(jī)制：鼠標(biāo)點(diǎn)擊處所在的小圓域(半徑自行設(shè)置)，如果沒(méi)有其他已創(chuàng)建的景點(diǎn)(結(jié)點(diǎn))，那么將新生成并繪制該景點(diǎn)(結(jié)點(diǎn))。
??● 道路的繪制機(jī)制：用鼠標(biāo)選取兩個(gè)景點(diǎn)(結(jié)點(diǎn))，即可新生成一條景區(qū)道理，并會(huì)賦予該道路相應(yīng)的結(jié)構(gòu)體成員信息。
??● 流程圖如下：
??● 代碼如下：
void Tour_System::mousePressEvent(QMouseEvent* e) // 鼠標(biāo)點(diǎn)擊事件 {if (e->button() == Qt::LeftButton) // 按左鍵{QPoint cur_click_pos = e->pos(); // e->pos(): 獲取當(dāng)前點(diǎn)擊位置switch(function_num){case 1: // 添加點(diǎn)if(node_num < Node_MAX_NUM && cur_click_pos.x() >= show_window_x &&cur_click_pos.x() <= show_window_x+show_window_width &&cur_click_pos.y() >= show_window_y && cur_click_pos.y() <= show_window_y+show_window_height) // 判斷所加的點(diǎn)是否在窗口范圍內(nèi){int save_node_num = node_num;node_num++;for(int i = 1; i < node_num; i++){if(is_Click_Suc(cur_click_pos, point[i], RADIUS+10)) // 判斷鼠標(biāo)所點(diǎn)擊位置和圖上所有已添加的結(jié)點(diǎn)位置,是否靠的太近{node_num--;QMessageBox::warning(this, "警告", "兩個(gè)點(diǎn)靠太近！");}}if(save_node_num == node_num)break;point[node_num] = e->pos(); // 當(dāng)前位置賦給最新的結(jié)點(diǎn)point_info[node_num] = QString::number(++info_ind); // 創(chuàng)建默認(rèn)標(biāo)簽update();}else if(node_num >= Node_MAX_NUM){QMessageBox::warning(this, "警告", "目前結(jié)點(diǎn)數(shù)已達(dá)上限，無(wú)法再繼續(xù)添加！");}else{QMessageBox::warning(this, "警告", "新加結(jié)點(diǎn)已超出邊界！");}ui->Message_1->clear();ui->Message_1->addItem("目前有結(jié)點(diǎn)個(gè)數(shù)：" + QString::number(node_num));ui->Message_1->addItem("目前有邊的條數(shù)：" + QString::number(side_num));ui->Message_1->addItem("如果還要繼續(xù)添加, 請(qǐng)選擇下一個(gè)點(diǎn)的位置。");function_num = 1; // 功能號(hào) 1 保持不變(便于重復(fù)添加點(diǎn))break;case 2: // 新增邊(選擇邊的起點(diǎn))if(side_num >= Side_MAX_NUM){QMessageBox::warning(this, "警告", "路徑數(shù)已達(dá)上限！");}else{for( int i = 1; i <= node_num; i++ ){if( is_Click_Suc(cur_click_pos, point[i], RADIUS) ) // 判斷是否選中{function_num = 3; // 找到了新增邊的起點(diǎn)后, 還需找到其終點(diǎn). 故把控制權(quán)交給功能號(hào)3temp_Point_1 = point[i];line[side_num + 1].node_1 = i;ui->Message_1->clear();ui->Message_1->addItem("請(qǐng)選擇邊的終點(diǎn)位置");break;}}}update();break;case 3: // 新增邊(選擇邊的終點(diǎn))for( int i = 1; i <= node_num; i++ ){if(point[i] != temp_Point_1 && is_Click_Suc(cur_click_pos, point[i], RADIUS)) // 若選中了與第一個(gè)點(diǎn)不同的點(diǎn){function_num = 2; // 重新把控制權(quán)交給功能號(hào)2(便于重復(fù)添加“邊”)int save_side_num = side_num++; // 線數(shù)量 + 1temp_Point_2 = point[i];line[side_num].node_2 = i;if(line[side_num].node_1 > line[side_num].node_2) // 確保邊的起點(diǎn)下標(biāo)比終點(diǎn)的小, 不然做交換{int temp = line[side_num].node_1;line[side_num].node_1 = line[side_num].node_2;line[side_num].node_2 = temp;}for( int j = 1; j < side_num; j++ ) // 判斷是否路線已經(jīng)存在{if(line[side_num].node_1 == line[j].node_1 && line[side_num].node_2 == line[j].node_2){line[side_num] = line[0];side_num--;QMessageBox::warning(this, "警告", "該路徑已添加！");break;}}if(save_side_num != side_num) // 如果路該線之前在圖中不存在, 則該表達(dá)式成立{int ind_1 = line[side_num].node_1;int ind_2 = line[side_num].node_2;dis_matrix[ind_1][ind_2] = dis_matrix[ind_2][ind_1] = Count_distanse(point[ind_1], point[ind_2]); // 距離矩陣賦值line[side_num].ind = side_num; // 邊的“編號(hào)”line[side_num].dis = Count_distanse(point[ind_1], point[ind_2]); // 邊的長(zhǎng)度}ui->Message_1->clear();ui->Message_1->addItem("目前有結(jié)點(diǎn)個(gè)數(shù)：" + QString::number(node_num));ui->Message_1->addItem("目前有邊的條數(shù)：" + QString::number(side_num));ui->Message_1->addItem("如果還要繼續(xù)添加邊, 請(qǐng)選擇下一條邊的起點(diǎn)");break;}}update();break;case 4: // 刪除結(jié)點(diǎn)......}} }void Tour_System::on_Btn_1_1_clicked() // 新增結(jié)點(diǎn) {All_flag_Clear(); // 標(biāo)簽清空操作Recover(); // 按鈕信息重置if(function_num != 1){function_num = 1;ui->Btn_1_1->setStyleSheet("border-image: url(:/new/prefix1/btn_2.png);");ui->Btn_1_1->setText("停止該操作");ui->Message_1->clear();ui->Message_1->addItem("請(qǐng)選擇一個(gè)位置添加新結(jié)點(diǎn)");}else{function_num = 0;ui->Btn_1_1->setText("新增結(jié)點(diǎn)");ui->Message_1->clear();}}void Tour_System::on_Btn_1_2_clicked() // 新增邊 {All_flag_Clear(); // 標(biāo)簽清空操作Recover(); // 按鈕信息重置if(function_num != 2){function_num = 2;ui->Btn_1_2->setStyleSheet("border-image: url(:/new/prefix1/btn_2.png);");ui->Btn_1_2->setText("停止該操作");ui->Message_1->clear();ui->Message_1->addItem("請(qǐng)選擇新增邊的起點(diǎn)");}else{function_num = 0;ui->Btn_1_2->setText("新增邊");ui->Message_1->clear();} }5.2 判斷創(chuàng)建的導(dǎo)游線路圖有無(wú)回路的算法——拓?fù)鋱D：
??● 算法思路：
????[1]采用拓?fù)渑判?#xff0c;先用一維數(shù)組存儲(chǔ)所有結(jié)點(diǎn)的度(數(shù)組下標(biāo)設(shè)為結(jié)點(diǎn)對(duì)應(yīng)的序號(hào))
????[2]每有一條邊，與之相連的結(jié)點(diǎn)的度數(shù)就加 1
????[3]然后我們進(jìn)行遍歷，將度數(shù)為 1 的結(jié)點(diǎn)刪去(與之相連的邊也要?jiǎng)h去)
????[4]數(shù)組也要隨之更新，刪去的那條邊所相連的結(jié)點(diǎn)的度數(shù) - 1
????[5]如果已沒(méi)有符合條件的結(jié)點(diǎn)被刪去，則跳到[5]，否則轉(zhuǎn)向[2]
????[6]如果還有數(shù)組中還有數(shù)，那么打印出它們即是存在回路的幾個(gè)結(jié)點(diǎn)。
????時(shí)間復(fù)雜度：O(n^2)
??● 流程圖如下：
??● 代碼如下：
5.3 輸出給定入口景點(diǎn)的導(dǎo)游線路圖的算法——DFS
??● 算法思路如下：
????[1]首先設(shè)定每個(gè)結(jié)點(diǎn)最多只能被訪問(wèn)一次(有些結(jié)點(diǎn)所處的位置可能是“死胡同”)
????[2]用一維的vector來(lái)儲(chǔ)存結(jié)果, 單元依次存儲(chǔ)路徑結(jié)點(diǎn)的info（標(biāo)簽）.
????[3]采用DFS方式進(jìn)行搜索, 每搜索到一個(gè)結(jié)點(diǎn)就放入當(dāng)前的vector里面
????[4]發(fā)生遞歸(兩種情況：<1>搜完了所有結(jié)點(diǎn);<2>搜索失敗), 注意對(duì)vector的調(diào)整
????[5]每次調(diào)用該函數(shù)時(shí)，都會(huì)進(jìn)行“性能”比較，會(huì)將“好路線”更新到ans里面
????[6]最后輸出對(duì)應(yīng)ans最后一組結(jié)點(diǎn)信息即可。
??● 流程圖如下：
??● 代碼如下：
5.4 求兩個(gè)景點(diǎn)間的最短路徑的算法——Floyd
??● 算法思路如下：
????[1]初始化距離矩陣和路徑矩陣
????[2]依次加入每一個(gè)結(jié)點(diǎn), 加入后更新距離矩陣和路徑矩陣
????[3]更新機(jī)制：
????[4]最后再進(jìn)行 “回溯” 輸出最短路徑即可(詳見(jiàn)Find_Shortest_Path()函數(shù))
??● 流程圖如下：
??● 代碼如下：
5.5 給出道路建設(shè)(最小生成樹(shù))的算法——Kruskal
??● 算法思路如下：
????[1]將所有的邊提取出來(lái), 然后按邊長(zhǎng)進(jìn)行排序(快排+升序)
????[2]再將每一個(gè)結(jié)點(diǎn)都劃分為一個(gè)單獨(dú)的集合(初始化)
????[3]然后依次加邊(按邊長(zhǎng)從小到大的順序), 被連接在一起的結(jié)點(diǎn)歸屬到一個(gè)集合
????[4]在加邊過(guò)程中，加了這條邊若會(huì)形成回路就跳過(guò)這條邊(采用查并集算法)
????[5]當(dāng)所有的結(jié)點(diǎn)(n個(gè))都被加入且在一個(gè)連通集合里面的時(shí)候, 把所有加入的邊(n-1條)都輸出出來(lái), 圖形界面展示即可
????[6]最后給出景區(qū)建設(shè)中的能花最小的代價(jià)的道路建設(shè)。
??● 流程圖如下：
??● 代碼如下：
六、測(cè)試數(shù)據(jù)及其結(jié)果分析
??● 登錄界面如下：
??● 創(chuàng)建景區(qū)結(jié)點(diǎn)和道路：
??● 刪除景區(qū)結(jié)點(diǎn)和邊：
??● 刪除景區(qū)結(jié)點(diǎn)和邊：
??● 編輯景區(qū)結(jié)點(diǎn)和邊：
??● 加載圖片背景(無(wú)結(jié)點(diǎn)、邊的數(shù)據(jù))：
??● 注：加載地圖功能和加載背景功能類似，只是多加了一個(gè)讀文本文件的操作，而加載背景只讀取限定后綴名的圖片。保存地圖功能是加載地圖的反操作。清除屏幕功能即是把顯示框里面的所有內(nèi)容清除。這三個(gè)功能不方便用截圖方式體現(xiàn)，詳見(jiàn)源代碼。
??● 判斷有無(wú)回路(拓?fù)渑判?的演示圖：
??● 建立導(dǎo)游線路(DFS)的演示圖：
??● 求兩點(diǎn)之間的最短路徑(Floyd)的演示圖：
??● 最小代價(jià)修建道路(Kruskal)的演示圖：
七、完整代碼
??● 可執(zhí)行文件下載鏈接(百度云網(wǎng)盤(pán)，提取碼: mlxg)：https://pan.baidu.com/s/1eStv1uIHXjaMns_0JZY3eg.
??● 項(xiàng)目文件源代碼：https://download.csdn.net/download/Wang_Dou_Dou_/47693292.
八、參考附錄
[1]《Qt5 開(kāi)發(fā)及實(shí)例 第3版》 作者：陸文周
[2] Qt 5.14.2 下載、安裝、使用教程，Qt+vs2019開(kāi)發(fā)環(huán)境搭建
鏈接: https://www.bilibili.com/video/BV1r54y1G7m4.
[3] “地圖”編輯器 之 程序演示【感謝南開(kāi)大學(xué)的鍆鋅UP主，框架搭建主要參考了他的】
鏈接: https://www.bilibili.com/video/BV1k64y1W73o?spm_id_from=333.999.0.0.
?? ??
總結(jié)
以上是生活随笔為你收集整理的景点旅游信息系统——C/C++程序设计、Qt图形化界面的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： mysql codesmith_Code
- 下一篇： insert 和 insertSelec