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

课程设计报告设计题目：城市管理学生姓名：魏于博专业：电子信息工程 班级：电信工 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广州 56深圳 5 1安 徽 1 6北京 117.查看所有城市（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*tt4，两个城市间的距离ttt* endl;cout ttt*tt5，查找距离某地为n 的城市 tt* endl; cout ttt*tt6，最短距离遍历指定城市tt* endl; cout ttt*tt7，查看所有城市 ttt* endl;cout ttt*tt8，退出城市管理系统ttt* endl;cout ttt* endl;cout ttt* endl;intn;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，遍历所有城市 endl; cout * e