程序课程设计--城市管理.doc

1、（1） 需求和规格说明问题描述：问题描述：用无序表实现一个城市数据库。每条数据库记录包括城市名（任意长的字符串）和城市的坐标（用整数x和y表示）。实现数据的插入、删除、查询功能，并实现指定距离内的所有城市。设计算法实现指定一定数目的具体城市，寻找遍历这些城市并回到出发点的最佳路径，观察随着城市数目的增加，算法执行效率的变化。编程任务：1）用列表对城市进行记录和管理，实现城市的增加、删除和查询功能，并实现文件保存和读取2）计算城市之间距离，统计输出距离某城市一定范围内的所有城市。3）实现一定规模城市的遍历最佳路径选择。4）分析随着城市数目增加时，算法执行效果的改变，深刻理解旅行商问题。（2） 设

2、计首先建立一个CityNode, 包含城市的名称，横纵坐标和指针。再建立一CityManage类属性和方法定义类名成员类别类型成员名描述CityNode属性Stringcityname城市名称intx城市的横坐标inty城市的纵坐标CityNode*next其连接作用类名成员类别类型成员名描述CityManage属性Stringcityname城市名称intx城市横坐标inty城市纵坐标CityNode*next指针，起连接作用Class中的方法bool Insert_CityNode(string cityname, int x, int y); （添加城市）bool Insert_City

3、Node_2(string cityname, int x, int 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

4、SaveFile(string cityname, int x, int y);（保存文件）void ReadFile();（读取文件）void Operation();（switc语句，便于操作）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();（贪心算法 求最短路径）（3） 用户手

5、册（4） 调试及测试1. 添加城市若城市已存在，则提示存在，不能添加2. 查找城市通过名称查找 通过坐标查找3. 删除城市通过名称删除通过坐标删除4.查看两城市间的距离5.查找距离定点一定距离的城市6.查找最优路径测试数据（环形数据能更好的检测）中国 9 1 合肥 9 6 广州 5 6 深圳 5 1 安徽 1 6 北京 1 1（5） 附录程序代码#include#include#include#includeusing namespace std;int number = 0;/城市数目int Weight100100;/边距string citys100;/城市名称struct CityNo

6、destring cityname;int x, y;CityNode * next;struct minedgeint vex;int low;minedge Edge100;void Travel_Path(int v0);class CityManagepublic:CityManage();/CityManage();bool Insert_CityNode(string cityname, int x, int y);bool Insert_CityNode_2(string cityname, int x, int y);bool Search_CityNode(string ci

7、tyname);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();void SaveAgain();void IsExist(int x, int y, string city

8、name, int &temp);bool Distance_In_Range(int num, int x, int y);bool Travel_Edge();bool Test();private:CityNode * head;CityManage:CityManage()head = new CityNode;head-next = NULL;bool CityManage:Insert_CityNode(string cityname, int x, int y)/（添加城市）CityNode*p = new CityNode;p-cityname = cityname;p-x =

9、 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;bool CityManage:Insert_CityNode_2(string cityname, int x, int y)/（添加城市-文件读入）Cit

10、yNode*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:Search_CityNode(string cityname)/（通过城市名字查找）CityNode*p;p = new CityNode;p = head-next;while (p != N

11、ULL)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 该城市已存在 n

12、ext;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(int x, int y)/（通过城市坐标删除

13、）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 !

14、= 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

15、= p-next;if (p-cityname != cityname1)cout 未找到您所输入的第一个城市 cityname = cityname2)c2x = s-x;c2y = s-y;break;s = s-next;if (s-cityname != cityname2)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

16、 != NULL)if (sqrt(pow(p-x - x, 2) + pow(p-y - y, 2) = num)cout cityname x , y next;if (n = 0)cout 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

17、= 0; ccityname;p = p-next;return true;void Travel()/（求最短路径）int i, j, k, l;int S100;/用于存储已访问过的城市 /用于存储两个城市之间的距离int sum = 0;/用于记算已访问过的城市的最小路径长度int Dtemp;/保证Dtemp比任意两个城市之间的距离都大（其实在算法描述中更准确的应为无穷大）int flag;/最为访问的标志，若被访问过则为1，从未被访问过则为0 /*初始化*/i = 1; /i是至今已访问过的城市S0 = 0;do k = 1; Dtemp = 100;do l = 0; flag =

18、 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 100);Si = j;/将已访问过的城市j存入到Si中i+;sum += Dtemp;/求出各城市之

19、间的最短距离，注意：在结束循环时，该旅行商尚未回到原出发的城市 while (i 100);sum += Weight0j;/D0j为旅行商所在的最后一个城市与原出发的城市之间的距离cout endl;cout 路线如下: endl;cout * endl;cout ;for (j = 0; j number; j+) /输出经过的城市的路径cout citysSj ;cout citys0;cout endl;cout * endl endl;void CityManage:Operation()cout ttt* endl;cout ttt* 作者：魏于博 学号：2017212064 *

20、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，最短距离遍历城市ttt* endl;cout ttt* * endl;cout ttt* endl;int n;char num;cout num;string cityname,

21、cityname1, cityname2;int 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;Searc

22、h_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;

23、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 请输入两

24、个城市： 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:Travel_Edge();Travel();system(pause);system(cls);break;case 7:Test();system(paus

25、e);system(cls);break;default:cout Error cityname x y)Insert_CityNode_2(cityname, x, y);ifile.close();void CityManage:SaveFile(string cityname, int x, int y)ofstream outfile(City.txt, ios:out | ios:app);if (!outfile)cout opre City.dat error! endl;exit(1);string a100;int b100;int c100;for (int n = 0; n100; n+)an = cityname;bn = x;cn = y;int i = 0;i = i + 1;outfile ai ;outfile bi ;outfile ci;outfile next;for (int h = 0; h15; h+)cout cityname;p = p-next;return true;void main()CityManage City;string start;City.ReadFile();while (1)City.Operation();