程序设计报告---城市管理.doc

.课程设计报告设计题目：城市管理学生姓名： 魏于博专 业：电子信息工程班 级：电信工17-1班学 号：2017212064指导教师： 方帅完成日期：2018年6月29日合肥工业大学计算机与信息学院（1） 需求和规格说明问题描述：问题描述：用无序表实现一个城市数据库。每条数据库记录包括城市名（任意长的字符串）和城市的坐标（用整数x和y表示）。实现数据的插入、删除、查询功能，并实现指定距离内的所有城市。设计算法实现指定一定数目的具体城市，寻找遍历这些城市并回到出发点的最佳路径，观察随着城市数目的增加，算法执行效率的变化。编程任务：1）用列表对城市进行记录和管理，实现城市的增加、删除和查询功能，并实现文件保存和读取2）计算城市之间距离，统计输出距离某城市一定范围内的所有城市。3）实现一定规模城市的遍历最佳路径选择。4）分析随着城市数目增加时，算法执行效果的改变，深刻理解旅行商问题。（2） 设计建立一个CityNode, 包含城市的名称，横纵坐标和指针。再建立一CityManage类属性和方法定义类名成员类别类型成员名描述CityNode属性Stringcityname城市名称intx城市的横坐标inty城市的纵坐标CityNode*next其连接作用Class中的方法bool Insert_CityNode(string cityname, int x, int y); （添加城市）bool Insert_CityNode_2(string cityname, int x, int y);（添加城市-文件读入）bool Insert_CityNode_3(string cityname, float x, float y);（遍历指定城市中使用）bool Search_CityNode(string cityname);（通过城市名字查找）bool Search_CityNode(int x, int y);（用过城市坐标查找）bool Delete_CityNode(string cityname);（用过城市名字删除）bool Delete_CityNode(int x, int y);（通过城市坐标删除）float Distance(string cityname1, string cityname2);（两城市间的距离）void SaveFile(string cityname, int x, int y);（保存文件）void ReadFile();（读取文件）void Operation();（switc语句，便于操作）void SaveAgain();（删除节点时重新保存文件）void Clear();（遍历指定城市后清空链表）void IsExist(int x, int y, string cityname, int &temp);（判断是否已经存在）bool Distance_In_Range(int num, int x, int y);（一定范围内的城市）bool Travel_Edge();（将城市和坐标分别存在数组中，便于求最短路径）void Travel_Path();（贪心算法 求最短路径）bool Travel_Edge_ALL();（遍历所有城市）bool ZDCZ(string cityname);（添加需要便利的指定城市）CityNode * head;（保存所有城市数据）CityNode * head2;（保存指定城市的信息）（3） 用户手册（4） 调试及测试1. 添加城市若城市已存在，则提示存在，不能添加2. 查找城市通过名称查找 通过坐标查找3. 删除城市通过名称删除通过坐标删除4.查看两城市间的距离5.查找距离定点一定距离的城市6.查找最优路径1制定城市查询最短路径2全部城市最短路径测试数据（环形数据能更好的检测）中国 9 1 合肥 9 6 广州 5 6 深圳 5 1 安徽 1 6 北京 1 17.查看所有城市（5） 附录程序代码#include#include#include#include#includeusing namespace std;int number = 0, number2 = 0;float Weight100100;string citys100;struct CityNodestring cityname;float x, y;CityNode * next;struct minedgeint vex;int low;minedge Edge100;void Travel();class CityManagepublic:CityManage();/CityManage();bool Insert_CityNode(string cityname, float x, float y);bool Insert_CityNode_2(string cityname, float x, float y);bool Insert_CityNode_3(string cityname, float x, float y);bool Search_CityNode(string cityname);bool Search_CityNode(float x, float y);bool Delete_CityNode(string cityname);bool Delete_CityNode(float x, float y);float Distance(string cityname1, string cityname2);void SaveFile(string cityname, float x, float y);void ReadFile();void Operation();void SaveAgain();void Clear();void IsExist(float x, float y, string cityname, int &temp);bool Distance_In_Range(int num, float x, float y);bool Travel_Edge();bool Travel_Edge_ALL();bool ZDCZ(string cityname);private:CityNode * head;CityNode * head2;CityManage:CityManage()head = new CityNode;head-next = NULL;head2 = new CityNode;head2-next = NULL;bool CityManage:Insert_CityNode(string cityname, float x, float y)/（添加城市）CityNode*p = new CityNode;p-cityname = cityname;p-x = x;p-y = y;int temp1 = 0;IsExist(x, y, cityname, temp1);if (temp1 = 0)SaveFile(cityname, x, y);cout 添加成功 next = NULL)head-next = p;p-next = NULL;number = 1;return true;p-next = head-next;head-next = p;number+;return true;return true;bool CityManage:Insert_CityNode_2(string cityname, float x, float y)/（添加城市-文件读入）CityNode*p = new CityNode;p-cityname = cityname;p-x = x;p-y = y;if (head-next = NULL)head-next = p;p-next = NULL;number = 1;return true;p-next = head-next;head-next = p;number+;return true;bool CityManage:Insert_CityNode_3(string cityname, float x, float y)/（添加城市-文件读入）CityNode*p = new CityNode;p-cityname = cityname;p-x = x;p-y = y;if (head2-next = NULL)head2-next = p;p-next = NULL;number2 = 1;return true;p-next = head2-next;head2-next = p;number2+;return true;bool CityManage:ZDCZ(string cityname)CityNode*p;p = new CityNode;p = head-next;while (p != NULL)if (p-cityname = cityname)Insert_CityNode_3(p-cityname, p-x, p-y);return true;p = p-next;return true;bool CityManage:Search_CityNode(string cityname)/（通过城市名字查找）CityNode*p;p = new CityNode;p = head-next;while (p != NULL)if (p-cityname = cityname)cout * endl;cout cityname x , y endl;cout * next;cout 未发现此城市 next;while (p != NULL)if (p-x = x & p-y = y)cout endl;cout * endl;cout cityname x , y endl;cout * endl;cout next;cout 所在坐标下没有城市 next;while (k != NULL)if (k-x = x & k-y = y | k-cityname = cityname)cout 该城市已存在 next;bool CityManage:Delete_CityNode(string cityname)/（用过城市名字删除）CityNode *p, *s;p = new CityNode;s = new CityNode;s = head;p = head-next;while (p != NULL)if (p-cityname = cityname)s-next = p-next;delete p;cout 该城市已删除 next;s = s-next;return false;bool CityManage:Delete_CityNode(float x, float y)/（通过城市坐标删除）CityNode *p, *s;p = new CityNode;s = new CityNode;s = head;p = head-next;while (p != NULL)if (p-x = x & p-y = y)s-next = p-next;delete p;number-;cout 该城市已删除 next;s = s-next;return false;void CityManage:SaveAgain()ofstream fout(City.txt, ios:out);CityNode *p;p = new CityNode;p = head-next;while (p != NULL)SaveFile(p-cityname, p-x, p-y);p = p-next;float CityManage:Distance(string cityname1, string cityname2)/（两城市间的距离）CityNode *p, *s;float c1x, c1y, c2x, c2y, dis;p = new CityNode;s = new CityNode;p = head-next;s = head-next;while (p != NULL)if (p-cityname = cityname1)c1x = p-x;c1y = p-y;break;p = p-next;/if (p-cityname != cityname1)if (p = NULL)cout 未找到您所输入的第一个城市 cityname = cityname2)c2x = s-x;c2y = s-y;break;s = s-next;/if (s-cityname != cityname2)if (s = NULL)cout 未找到您所输入的第二个城市 endl;return 1;dis = sqrt(c1x - c2x)*(c1x - c2x) + (c1y - c2y)*(c1y - c2y);cout cityname x , y 到;cout cityname x , y 的距离为： dis next;while (p != NULL)if (sqrt(pow(p-x - x, 2) + pow(p-y - y, 2) = num)cout cityname x , y next;if (n = 0)cout next)p = head2-next;head2-next = p-next;free(p);number2-;bool CityManage:Travel_Edge()/（将城市和坐标分别存在数组中，便于求最短路径）CityNode *p, *s;p = new CityNode;s = new CityNode;p = head2-next;int a = 0, b = 0, c = 0;for (a = 0; a100; a+)for (b = 0; b100; b+)Weightab = 100;for (a = 0; anext;for (b = a + 1; bx - s-x), 2) + pow(abs(p-y - s-y), 2);s = s-next;p = p-next;p = head2-next;for (c = 0; ccityname;p = p-next;return true;bool CityManage:Travel_Edge_ALL()/（将城市和坐标分别存在数组中，便于求最短路径）CityNode *p, *s;p = new CityNode;s = new CityNode;p = head-next;int a = 0, b = 0, c = 0;for (a = 0; a100; a+)for (b = 0; b100; b+)Weightab = 100;for (a = 0; anext;for (b = a + 1; bx - s-x), 2) + pow(abs(p-y - s-y), 2);s = s-next;p = p-next;p = head-next;for (c = 0; ccityname;p = p-next;return true;void Travel(int Number)/（求最短路径）int i, j, k, l;int S100;/用于存储已访问过的城市 /用于存储两个城市之间的距离float sum = 0;/用于记算已访问过的城市的最小路径长度float Dtemp;/保证Dtemp比任意两个城市之间的距离都大（其实在算法描述中更准确的应为无穷大）int flag;/最为访问的标志，若被访问过则为1，从未被访问过则为0 /*初始化*/i = 1; /i是至今已访问过的城市S0 = 0;do k = 1; Dtemp = 100;do l = 0; flag = 0;do if (Sl = k) /判断该城市是否已被访问过，若被访问过，flag = 1;/则flag为1break;/跳出循环，不参与距离的比较elsel+; while (l i);if (flag = 0 & WeightkSi - 1 Dtemp) /*DkSi - 1表示当前未被访问的城市k与上一个已访问过的城市i-1之间的距离*/j = k;/j用于存储已访问过的城市kDtemp = WeightkSi - 1;/Dtemp用于暂时存储当前最小路径的值k+; while (k Number);Si = j;/将已访问过的城市j存入到Si中i+;sum += Dtemp;/求出各城市之间的最短距离，注意：在结束循环时，该旅行商尚未回到原出发的城市 while (i Number);sum += Weight0j;/D0j为旅行商所在的最后一个城市与原出发的城市之间的距离cout endl;cout 路线如下: endl;cout * endl;cout ;for (j = 0; j Number; j+) /输出经过的城市的路径cout citysSj ;cout citys0;cout endl;cout 最短距离为： sum endl;cout * endl endl;void CityManage:Operation()cout ttt* endl;cout ttt* 作者：魏于博 学号：2017212064 * endl;cout ttt*城市管理* endl;cout ttt* * endl;cout ttt*tt 1，添加城市tttt* endl;cout ttt*tt 2，查找城市tttt* endl;cout ttt*tt 3，删除城市tttt* endl;cout ttt*tt 4，两个城市间的距离ttt* endl;cout ttt*tt 5，查找距离某地为n的城市tt* endl;cout ttt*tt 6，最短距离遍历指定城市tt* endl;cout ttt*tt 7，查看所有城市ttt* endl;cout ttt*tt 8，退出城市管理系统ttt* endl;cout ttt* * endl;cout ttt* endl;int n;char num;cout num;string cityname, cityname1, cityname2;float x, y;switch (num)case 1: cout 请输入城市名称： cityname;cout 请输入坐标 endl;cout x;cout y;Insert_CityNode(cityname, x, y);system(pause);system(cls);break;case 2:cout * endl;cout 1，通过城市查找坐标 endl;cout 2，通过坐标查找城市 endl;cout * endl;char Num1;cout Num1;switch (Num1)case 1: cout cityname;Search_CityNode(cityname);system(pause);system(cls);break;case 2: cout 请输入坐标 endl;cout x;cout y;Search_CityNode(x, y);system(pause);system(cls);break;default:cout Error endl;system(pause);system(cls);break;break;case 3:cout * endl;cout 1，通过城市名称删除 endl;cout 2，通过城市坐标删除 endl;cout * endl;char Num2;cout Num2;switch (Num2)case 1: cout cityname;Delete_CityNode(cityname);SaveAgain();system(pause);system(cls);break;case 2: cout 请输入要删除城市的坐标：;cout endl;cout x;cout y;Delete_CityNode(x, y);SaveAgain();system(pause);system(cls);break;default:cout Error endl;system(pause);system(cls);break;break;case 4: cout 请输入两个城市： endl;cout cityname1;cout cityname2;Distance(cityname1, cityname2);system(pause);system(cls);break;case 5: cout n;cout 请输入要查找点的坐标： endl;cout x;cout y;Distance_In_Range(n, x, y);system(pause);system(cls);break;case 6:cout * endl;cout 1，遍历指定城市 endl;cout 2，遍历所有城