投稿
  1. 首页
  2. 随笔

简单交通查询系统（MFC界面）

在线代理网站 • 2022-12-17 • 随笔 • 阅读 97

简单交通查询系统（MFC界面）,第1张

简单交通查询系统（MFC界面）

交通查询系统

[问题描述]

今天铁路交通网络非常发达，人们在出差、旅游时，不仅关注交通费用，还关注里程和时间。请按照下图设计一个交通查询系统，能够满足旅客查询从任一个城市到另一个城市的最短里程、最低花费、最短时间、最少中转次数等问题。

[基本要求]

设计合适的数据结构和算法编写程序完成上述功能，并具有查询界面，能够按照下拉菜单选项进行选择查询。

                

主要思路：

首先分析题干中的要求“任一个城市到另一个城市的最短里程、最低花费，最短时间”，观察给出的无向图可知，每个城市之间的里程，时间，花费是呈线性关系的，因此这三个问题可以归结为同一个最短路径问题，因为要满足任意一个城市到另一个城市的最短路径，因此采用多源最短路径算法即Floyed算法。

Floyed算法的过程：１、用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()
{

}

运行结果：

                           

  选择相同的城市时：

参考资料：《啊哈！算法》--啊哈磊

 

 

 

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5698435.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
在线代理网站 在线代理网站 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存