交通查询系统
[问题描述]
今天铁路交通网络非常发达,人们在出差、旅游时,不仅关注交通费用,还关注里程和时间。请按照下图设计一个交通查询系统,能够满足旅客查询从任一个城市到另一个城市的最短里程、最低花费、最短时间、最少中转次数等问题。
[基本要求]
设计合适的数据结构和算法编写程序完成上述功能,并具有查询界面,能够按照下拉菜单选项进行选择查询。
主要思路:
首先分析题干中的要求“任一个城市到另一个城市的最短里程、最低花费,最短时间”,观察给出的无向图可知,每个城市之间的里程,时间,花费是呈线性关系的,因此这三个问题可以归结为同一个最短路径问题,因为要满足任意一个城市到另一个城市的最短路径,因此采用多源最短路径算法即Floyed算法。
Floyed算法的过程:1、用weight v记录每一对顶点的最短距离,最少花费,最短时间(实际只需判断一个量即可)。2、依次扫描每一个点,并以其作为中转顶点k再遍历每一对顶点weightv的值,看看是否可用过该中转顶点k让这对顶点间的距离更小即判断(weightv>weightv+weightk)。在Floyed进行中定义一个Path数组用于记录每一次可行的中转顶点,最后可通过这个数组来打印路径。
分析题目的另一个需求“最少中转次数”,可转化为源点经过最少的顶点(边)到达目标顶点,为了最后能求出它的路径,这里采用了BFS(广度优先搜索算法),从源点开始进行搜索直到达到目标顶点结束。定义一个结构体队列,包含了步数(即中转次数)、城市编号,pre(有pre顶点扩展得到,即前驱结点)。BFS算法的过程:1、从图中某个顶点V0出发,并访问此顶点;2、从V0出发,访问V0的各个未曾访问(使用一个标记数组book记录是否被访问)的邻接点W1,W2,…,Wk并依次入队列,遍历完邻接点后将V0出队,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点;3、重复步骤2,直到访问到目标顶点。
为了打印最短路径和中转次数最少的路径,可分别利用已经得到的path[]数组,队列中的pre属性。path数组中记录的是出发城市到目标城市的中转顶点,例如i->k->j, k->k1->j, k1->k2->j….通过循环可得到完整的路线;pre表示x是由pre扩展出来的,通过循环也可得到反向路径。
在设计查询界面采用的是MFC技术,通过两个下拉框来选择起始城市和城市,最后设置一个查询按钮,点击后会在对应的查询框显示各个结果和路径。
具体页面设计思路:
出发地和目标地添加了两个Combo BOX(下拉框)控件,查询按钮为Button控件,为了显示求到的数据,添加若干个Edit Control(编辑框)控件。
为了能 *** 作添加的控件,需要为各个控件添加变量。(这里并没有添加具体比如说int,double类型是因为不好 *** 作,尝试过但很难将数据显示到编辑框)
同时在程序中,添加全局变量,用于最后与控件的变量进行关联:
比如start,end可以用于获取两个下拉框的索引(使用GetCurSel()函数可以获取到当前位置的索引):
那么如何添加值进入下拉框呢?很简单,只要使用InsertString()函数即可,第一个参数是位置,类似于数组都是从0开始。值得一提的是,这里的字符串类型,需要转化为文本类型使用_T()强制转化即可。而SetCurSel()函数的作用就是初始显示的位置。
具体效果:
另外还需要注意的一点就是,数值不能直接显示在编辑框里,需要转化为Cstring类型,可利用Cstring类中自带的Format()函数转化:
部分代码(.cpp):
// MFCApplication4Dlg.cpp: 实现文件 #include "pch.h" #include "framework.h" #include "MFCApplication4.h" #include "MFCApplication4Dlg.h" #include "afxdialogex.h" #include#ifdef _DEBUG #define new DEBUG_NEW #endif #define Maxint 32767 int m_distance=0; //最小距离 double m_time=0; //最短时间 int m_price=0; //最低花费 int m_step = 0; //最少中转次数 CString m_path1; CString m_path2; int start;//起点 int end; //终点 //创建一个储存城市编号和中转次数的结构体 struct note { int x; //城市编号0-6 int step; //中转次数 int pre; //前驱点在队列中的编号 }; //创建一个储存价格,时间和距离的结构体 struct info { int price; //价格 double time; //时间 int distance; //距离 }; //初始化站点信息 void InitCity(info& c, int price, double time, int distance) { c.price = price; c.time = time; c.distance = distance; } typedef struct { int edgesNum; //边的个数 int verxs; //节点个数 CString city[7]; //节点数据,记录了城市名字 info weight[7][7]; //由全部信息构成的邻接矩阵 int path[7][7]; //记录floyed算法的路径数组 }MGraph; //插入边 void insertEdge(MGraph& graph, int v1, int v2, info c) { //v1,v2表示第几个顶点 graph.weight[v1][v2] = c; graph.weight[v2][v1] = c; //无向图需要两点都要 graph.edgesNum++;//边数+1 } //初始化图 void InitGraph(MGraph& graph, int verxs) { graph.verxs = verxs; //初始化city数据 graph.city[0] = "北京"; graph.city[1] = "西安"; graph.city[2] = "郑州"; graph.city[3] = "徐州"; graph.city[4] = "成都"; graph.city[5] = "广州"; graph.city[6] = "上海"; //初始化邻接矩阵,初始权值即距离为最大 //初始化路径数组 for (int i = 0; i < verxs; i++) { for (int j = 0; j < verxs; j++) { //对角线为距离0 if (i == j) { graph.weight[i][j].distance = 0; graph.weight[i][j].time = 0; graph.weight[i][j].price = 0; } else { graph.weight[i][j].distance = Maxint; graph.weight[i][j].time = 0; graph.weight[i][j].price = 0; } //记录了对应点的最小路径的前驱点即中转点 graph.path[i][j] = j; } } graph.edgesNum = 0; //边与边之间的信息 info c1, c2, c3, c4, c5, c6, c7, c8, c9, c10; InitCity(c1, 885, 8, 2553); InitCity(c2, 225, 2.5, 704); InitCity(c3, 202, 2.3, 695); InitCity(c4, 148, 1.5, 511); InitCity(c5, 112, 1.2, 349); InitCity(c6, 283, 3, 812); InitCity(c7, 495, 5, 1579); InitCity(c8, 162, 2, 651); InitCity(c9, 684, 7, 2368); InitCity(c10, 386, 4, 1385); //插入边 insertEdge(graph, 0, 1, c1); insertEdge(graph, 0, 2, c3); insertEdge(graph, 0, 3, c2); insertEdge(graph, 1, 2, c4); insertEdge(graph, 2, 3, c5); insertEdge(graph, 1, 4, c6); insertEdge(graph, 2, 5, c7); insertEdge(graph, 3, 6, c8); insertEdge(graph, 4, 5, c9); insertEdge(graph, 5, 6, c10); } //floyed算法求各个城市间的最短路径 void Floyed(MGraph& graph) { //中转顶点k for (int k = 0; k < graph.verxs; k++) { //i为出发顶点 for (int i = 0; i < graph.verxs; i++) { //j为终点顶点 for (int j = 0; j < graph.verxs; j++) { //如果i到k的距离+k到j的距离小于i到j的距离则更新 if ((graph.weight[i][k].distance + graph.weight[k][j].distance) < graph.weight[i][j].distance) { //更新最短路径 graph.weight[i][j].distance = graph.weight[i][k].distance + graph.weight[k][j].distance; //更新最低价格 graph.weight[i][j].price = graph.weight[i][k].price + graph.weight[k][j].price; //更新最少时间 graph.weight[i][j].time = graph.weight[i][k].time + graph.weight[k][j].time; //更新最小路径中转顶点即前驱点 graph.path[i][j] = graph.path[i][k]; } } } } } // 用于应用程序“关于”菜单项的 CaboutDlg 对话框 class CaboutDlg : public CDialogEx { public: CaboutDlg(); // 对话框数据 #ifdef AFX_DESIGN_TIME enum { IDD = IDD_aboutBOX }; #endif protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV 支持 // 实现 protected: DECLARE_MESSAGE_MAP() }; CaboutDlg::CaboutDlg() : CDialogEx(IDD_aboutBOX) { } void CaboutDlg::DoDataExchange(CDataExchange* pDX) { CDialogEx::DoDataExchange(pDX); } BEGIN_MESSAGE_MAP(CaboutDlg, CDialogEx) END_MESSAGE_MAP() // CMFCApplication4Dlg 对话框 CMFCApplication4Dlg::CMFCApplication4Dlg(CWnd* pParent ) : CDialogEx(IDD_MFCAPPLICATION4_DIALOG, pParent) { m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINframe); } void CMFCApplication4Dlg::DoDataExchange(CDataExchange* pDX) { CDialogEx::DoDataExchange(pDX); DDX_Control(pDX, IDC_COMBO1, m1); DDX_Control(pDX, IDC_COMBO2, m2); DDX_Control(pDX, IDC_EDIT1, distance); DDX_Control(pDX, IDC_EDIT5, price); DDX_Control(pDX, IDC_EDIT6, Time); DDX_Control(pDX, IDC_EDIT2, Path1); DDX_Control(pDX, IDC_EDIT4, Path2); DDX_Control(pDX, IDC_EDIT3, Step); } BEGIN_MESSAGE_MAP(CMFCApplication4Dlg, CDialogEx) ON_WM_SYSCOMMAND() ON_WM_PAINT() ON_WM_QUERYDRAGICON() ON_BN_CLICKED(IDC_BUTTON1, &CMFCApplication4Dlg::OnBnClickedButton1) ON_EN_CHANGE(IDC_EDIT1, &CMFCApplication4Dlg::OnEnChangeEdit1) ON_EN_CHANGE(IDC_EDIT3, &CMFCApplication4Dlg::OnEnChangeEdit3) ON_EN_CHANGE(IDC_EDIT5, &CMFCApplication4Dlg::OnEnChangeEdit5) ON_EN_CHANGE(IDC_EDIT2, &CMFCApplication4Dlg::OnEnChangeEdit2) ON_CBN_SELCHANGE(IDC_COMBO1, &CMFCApplication4Dlg::OnCbnSelchangeCombo1) ON_EN_CHANGE(IDC_EDIT6, &CMFCApplication4Dlg::OnEnChangeEdit6) ON_EN_CHANGE(IDC_EDIT4, &CMFCApplication4Dlg::OnEnChangeEdit4) END_MESSAGE_MAP() // CMFCApplication4Dlg 消息处理程序 BOOL CMFCApplication4Dlg::onInitDialog() { CDialogEx::onInitDialog(); // 将“关于...”菜单项添加到系统菜单中。 // IDM_aboutBOX 必须在系统命令范围内。 ASSERT((IDM_aboutBOX & 0xFFF0) == IDM_aboutBOX); ASSERT(IDM_aboutBOX < 0xF000); CMenu* pSysMenu = GetSystemMenu(FALSE); if (pSysMenu != nullptr) { BOOL bNamevalid; CString straboutMenu; bNamevalid = straboutMenu.LoadString(IDS_aboutBOX); ASSERT(bNamevalid); if (!straboutMenu.IsEmpty()) { pSysMenu->AppendMenu(MF_SEPARATOR); pSysMenu->AppendMenu(MF_STRING, IDM_aboutBOX, straboutMenu); } } // 设置此对话框的图标。 当应用程序主窗口不是对话框时,框架将自动 // 执行此 *** 作 SetIcon(m_hIcon, TRUE); // 设置大图标 SetIcon(m_hIcon, FALSE); // 设置小图标 // TODO: 在此添加额外的初始化代码 //添加初始值进入下拉框 m1.InsertString(0,_T("北京")); m1.InsertString(1,_T("西安")); m1.InsertString(2,_T("郑州")); m1.InsertString(3,_T("徐州")); m1.InsertString(4,_T("成都")); m1.InsertString(5,_T("广州")); m1.InsertString(6,_T("上海")); m2.InsertString(0,_T("北京")); m2.InsertString(1,_T("西安")); m2.InsertString(2,_T("郑州")); m2.InsertString(3,_T("徐州")); m2.InsertString(4,_T("成都")); m2.InsertString(5,_T("广州")); m2.InsertString(6,_T("上海")); m1.SetCurSel(0); m2.SetCurSel(0); return TRUE; // 除非将焦点设置到控件,否则返回 TRUE } //求一点到另一点最短路径 void min_Path(MGraph graph, int start, int end) { m_distance = graph.weight[start][end].distance; m_time = graph.weight[start][end].time; m_price = graph.weight[start][end].price; int k = graph.path[start][end]; m_path1 = graph.city[start];//拼接起点 while (k != end) { m_path1 += "-->"; m_path1 += graph.city[k]; //拼接中转顶点 k = graph.path[k][end]; } m_path1 += "-->";m_path1+= graph.city[end]; //拼接终点 } //通过广度优先遍历得到最少中转次数 void min_Cur(MGraph graph, int start, int end) { m_path2 = ""; //路径重新初始化 if (start == end) { m_path2 = "不需中转"; return; } note* que = new note[10]; //简易队列,用于进行广度优先遍历 int book[10] = { 0 }; //标记数组 int head = 0, tail = 0; //队头队尾初始化 int cur = 0; //临时变量 int flag = 0; //是否到达目标城市 //从start号城市出发,将start加入队列 que[tail].x = start; que[tail].step = 0; //步数为0 que[tail].pre = -1; //队列头的前驱顶点为-1 tail++; book[start] = 1; //标记start号城市已存在队列中 //当队列不为空时进行循环 while (head < tail) { cur = que[head].x; //当前队列中队首的城市编号 for (int i = 0; i < graph.verxs; i++) { //从城市cur到城市i是否有班次并且判断i是否已经在队列中 if (graph.weight[cur][i].distance != Maxint && book[i] == 0) { que[tail].x = i;//入队 que[tail].step = que[head].step + 1; //中转次数+1,步数是父亲步数+1 que[tail].pre = head; //由哪个点扩展出来的,谁就是它的父顶点 tail++;//队尾指针后移 book[i] = 1;//标记 } //如果到达目标城市,停止扩展,退出循环 if (que[tail - 1].x == end) { flag = 1; break; } } if (flag) { break; } head++; //队首出队 } //队列中最后一个城市的中转次数就是最少中转次数 m_step = que[tail - 1].step - 1; int rear = tail - 1; while (true) { //如果没有达到队首,即起点城市 if (que[rear].pre != -1) { m_path2 += graph.city[que[rear].x]; m_path2+= "<--"; } else { m_path2 += graph.city[que[rear].x]; break; } rear = que[rear].pre; } delete[]que; } MGraph graph; //全局变量图 void CMFCApplication4Dlg::onSysCommand(UINT nID, LPARAM lParam) { if ((nID & 0xFFF0) == IDM_aboutBOX) { CaboutDlg dlgabout; dlgabout.DoModal(); } else { CDialogEx::onSysCommand(nID, lParam); } } // 如果向对话框添加最小化按钮,则需要下面的代码 // 来绘制该图标。 对于使用文档/视图模型的 MFC 应用程序, // 这将由框架自动完成。 void CMFCApplication4Dlg::onPaint() { if (IsIconic()) { CPaintDC dc(this); // 用于绘制的设备上下文 SendMessage(WM_ICONERASEBKGND, reinterpret_cast (dc.GetSafeHdc()), 0); // 使图标在工作区矩形中居中 int cxIcon = GetSystemMetrics(SM_CXICON); int cyIcon = GetSystemMetrics(SM_CYICON); CRect rect; GetClientRect(&rect); int x = (rect.Width() - cxIcon + 1) / 2; int y = (rect.Height() - cyIcon + 1) / 2; // 绘制图标 dc.DrawIcon(x, y, m_hIcon); } else { CDialogEx::onPaint(); } } //当用户拖动最小化窗口时系统调用此函数取得光标 //显示。 HCURSOR CMFCApplication4Dlg::onQueryDragIcon() { return static_cast (m_hIcon); } void CMFCApplication4Dlg::OnBnClickedButton1() { // TODO: 在此添加控件通知处理程序代码 //点击查询按钮 start = m1.GetCurSel(); end = m2.GetCurSel(); InitGraph(graph,7); //初始化图 //求得最少中转次数 min_Cur(graph,start,end); //Floyed算法求最短路径 Floyed(graph); //路径 min_Path(graph, start, end); //将字符串拼接显示在编辑框里 CString str; str.Format(_T("%d"),m_distance); str += "千米"; distance.SetWindowText(str); str.Format(_T("%d"), m_price); str += "元"; price.SetWindowText(str); str.Format(_T("%.1f"), m_time); //保留一位小数 str += "小时"; Time.SetWindowText(str); Path1.SetWindowText( m_path1); str.Format(_T("%d"), m_step); str += "次"; Step.SetWindowText(str); Path2.SetWindowText(m_path2); } void CMFCApplication4Dlg::OnEnChangeEdit1() { // TODO: 如果该控件是 RICHEDIT 控件,它将不 // 发送此通知,除非重写 CDialogEx::onInitDialog() // 函数并调用 CRichEditCtrl().SetEventMask(), // 同时将 ENM_CHANGE 标志“或”运算到掩码中。 // TODO: 在此添加控件通知处理程序代码 } void CMFCApplication4Dlg::OnEnChangeEdit2() { // TODO: 如果该控件是 RICHEDIT 控件,它将不 // 发送此通知,除非重写 CDialogEx::onInitDialog() // 函数并调用 CRichEditCtrl().SetEventMask(), // 同时将 ENM_CHANGE 标志“或”运算到掩码中。 // TODO: 在此添加控件通知处理程序代码 } void CMFCApplication4Dlg::OnEnChangeEdit3() { // TODO: 如果该控件是 RICHEDIT 控件,它将不 // 发送此通知,除非重写 CDialogEx::onInitDialog() // 函数并调用 CRichEditCtrl().SetEventMask(), // 同时将 ENM_CHANGE 标志“或”运算到掩码中。 // TODO: 在此添加控件通知处理程序代码 } void CMFCApplication4Dlg::OnEnChangeEdit5() { // TODO: 如果该控件是 RICHEDIT 控件,它将不 // 发送此通知,除非重写 CDialogEx::onInitDialog() // 函数并调用 CRichEditCtrl().SetEventMask(), // 同时将 ENM_CHANGE 标志“或”运算到掩码中。 // TODO: 在此添加控件通知处理程序代码 } void CMFCApplication4Dlg::OnEnChangeEdit4() { // TODO: 如果该控件是 RICHEDIT 控件,它将不 // 发送此通知,除非重写 CDialogEx::onInitDialog() // 函数并调用 CRichEditCtrl().SetEventMask(), // 同时将 ENM_CHANGE 标志“或”运算到掩码中。 // TODO: 在此添加控件通知处理程序代码 } void CMFCApplication4Dlg::OnEnChangeEdit6() { // TODO: 如果该控件是 RICHEDIT 控件,它将不 // 发送此通知,除非重写 CDialogEx::onInitDialog() // 函数并调用 CRichEditCtrl().SetEventMask(), // 同时将 ENM_CHANGE 标志“或”运算到掩码中。 // TODO: 在此添加控件通知处理程序代码 } void CMFCApplication4Dlg::OnCbnSelchangeCombo1() { }
运行结果:
选择相同的城市时:
参考资料:《啊哈!算法》--啊哈磊
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)