《程序设计报告-城市管理.doc》由会员分享,可在线阅读,更多相关《程序设计报告-城市管理.doc(20页珍藏版)》请在课桌文档上搜索。
1、课程设计报告设计题目:城市管理(1) 需求和规格说明问题描述:问题描述:用无序表实现一个城市数据库。每条数据库记录包括城市名任意长的字符串和城市的坐标用整数*和y表示。实现数据的插入、删除、查询功能,并实现指定距离的所有城市。设计算法实现指定一定数目的具体城市,寻找遍历这些城市并回到出发点的最正确路径,观察随着城市数目的增加,算法执行效率的变化。编程任务:1用列表对城市进展记录和管理,实现城市的增加、删除和查询功能,并实现文件保存和读取2计算城市之间距离,统计输出距离*城市一定围的所有城市。3实现一定规模城市的遍历最正确路径选择。4分析随着城市数目增加时,算法执行效果的改变,深刻理解旅行商问题
2、。2 设计建立一个CityNode,包含城市的名称,横纵坐标和指针。再建立一CityManage类属性和法定义类名成员类别类型成员名描述CityNode属性Stringcityname城市名称int*城市的横坐标inty城市的纵坐标CityNode*ne*t其连接作用Class中的法bool Insert_CityNode(stringcityname, int*, inty); 添加城市bool Insert_CityNode_2(stringcityname, int*, inty);添加城市-文件读入bool Insert_CityNode_3(string cityname, floa
3、t *, float y);遍历指定城市中使用bool Search_CityNode(stringcityname);通过城市名字查找bool Search_CityNode(int*, inty);用过城市坐标查找bool Delete_CityNode(stringcityname);用过城市名字删除bool Delete_CityNode(int*, inty);通过城市坐标删除float Distance(stringcityname1, stringcityname2);两城市间的距离void SaveFile(stringcityname, int*, inty);保存文件voi
4、d ReadFile();读取文件void Operation();switc语句,便于操作void SaveAgain();删除节点时重新保存文件void Clear();遍历指定城市后清空链表void IsE*ist(int*, inty, stringcityname, int &temp);判断是否已经存在bool Distance_In_Range(intnum, int*, inty);一定围的城市bool Travel_Edge();将城市和坐标分别存在数组中,便于求最短路径void Travel_Path();贪心算法 求最短路径bool Travel_Edge_ALL();遍
5、历所有城市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*includ
6、e*include*include*includeusing namespace std;int number = 0, number2 = 0;float Weight100100;string citys100;struct CityNodestring cityname;float *, y;CityNode * ne*t;struct minedgeint ve*;int low;minedge Edge100;void Travel();class CityManagepublic:CityManage();/CityManage();bool Insert_CityNode(str
7、ing cityname, float *, float y);bool Insert_CityNode_2(string cityname, float *, float y);bool Insert_CityNode_3(string cityname, float *, float y);bool Search_CityNode(string cityname);bool Search_CityNode(float *, float y);bool Delete_CityNode(string cityname);bool Delete_CityNode(float *, float y
8、);float Distance(string cityname1, string cityname2);void SaveFile(string cityname, float *, float y);void ReadFile();void Operation();void SaveAgain();void Clear();void IsE*ist(float *, float y, string cityname, int &temp);bool Distance_In_Range(int num, float *, float y);bool Travel_Edge();bool Tr
9、avel_Edge_ALL();bool ZDCZ(string cityname);private:CityNode * head;CityNode * head2;CityManage:CityManage()head = new CityNode;head-ne*t = NULL;head2 = new CityNode;head2-ne*t = NULL;bool CityManage:Insert_CityNode(string cityname, float *, float y)/添加城市CityNode*p = new CityNode;p-cityname = citynam
10、e;p-* = *;p-y = y;int temp1 = 0;IsE*ist(*, y, cityname, temp1);if (temp1 = 0)SaveFile(cityname, *, y);cout 添加成功 ne*t = NULL)head-ne*t = p;p-ne*t = NULL;number = 1;return true;p-ne*t = head-ne*t;head-ne*t = p;number+;return true;return true;bool CityManage:Insert_CityNode_2(string cityname, float *,
11、float y)/添加城市-文件读入CityNode*p = new CityNode;p-cityname = cityname;p-* = *;p-y = y;if (head-ne*t = NULL)head-ne*t = p;p-ne*t = NULL;number = 1;return true;p-ne*t = head-ne*t;head-ne*t = p;number+;return true;bool CityManage:Insert_CityNode_3(string cityname, float *, float y)/添加城市-文件读入CityNode*p = ne
12、w CityNode;p-cityname = cityname;p-* = *;p-y = y;if (head2-ne*t = NULL)head2-ne*t = p;p-ne*t = NULL;number2 = 1;return true;p-ne*t = head2-ne*t;head2-ne*t = p;number2+;return true;bool CityManage:ZDCZ(string cityname)CityNode*p;p = new CityNode;p = head-ne*t;while (p != NULL)if (p-cityname = citynam
13、e)Insert_CityNode_3(p-cityname, p-*, p-y);return true;p = p-ne*t;return true;bool CityManage:Search_CityNode(string cityname)/通过城市名字查找CityNode*p;p = new CityNode;p = head-ne*t;while (p != NULL)if (p-cityname = cityname)cout * endl;cout cityname * , y endl;cout * ne*t;cout 未发现此城市 ne*t;while (p != NUL
14、L)if (p-* = * & p-y = y)cout endl;cout * endl;cout cityname * , y endl;cout * endl;cout ne*t;cout 所在坐标下没有城市 ne*t;while (k != NULL)if (k-* = * & k-y = y | k-cityname = cityname)cout 该城市已存在 ne*t;bool CityManage:Delete_CityNode(string cityname)/用过城市名字删除CityNode *p, *s;p = new CityNode;s = new CityNode;
15、s = head;p = head-ne*t;while (p != NULL)if (p-cityname = cityname)s-ne*t = p-ne*t;delete p;cout 该城市已删除 ne*t;s = s-ne*t;return false;bool CityManage:Delete_CityNode(float *, float y)/通过城市坐标删除CityNode *p, *s;p = new CityNode;s = new CityNode;s = head;p = head-ne*t;while (p != NULL)if (p-* = * & p-y =
16、y)s-ne*t = p-ne*t;delete p;number-;cout 该城市已删除 ne*t;s = s-ne*t;return false;void CityManage:SaveAgain()ofstream fout(City.t*t, ios:out);CityNode *p;p = new CityNode;p = head-ne*t;while (p != NULL)SaveFile(p-cityname, p-*, p-y);p = p-ne*t;float CityManage:Distance(string cityname1, string cityname2)/
17、两城市间的距离CityNode *p, *s;float c1*, c1y, c2*, c2y, dis;p = new CityNode;s = new CityNode;p = head-ne*t;s = head-ne*t;while (p != NULL)if (p-cityname = cityname1)c1* = p-*;c1y = p-y;break;p = p-ne*t;/if (p-cityname != cityname1)if (p = NULL)cout 未找到您所输入的第一个城市 cityname = cityname2)c2* = s-*;c2y = s-y;br
18、eak;s = s-ne*t;/if (s-cityname != cityname2)if (s = NULL)cout 未找到您所输入的第二个城市 endl;return 1;dis = sqrt(c1* - c2*)*(c1* - c2*) + (c1y - c2y)*(c1y - c2y);cout cityname * , y 到;cout cityname * , y 的距离为: dis ne*t;while (p != NULL)if (sqrt(pow(p-* - *, 2) + pow(p-y - y, 2) = num)cout cityname * , y ne*t;if
19、 (n = 0)cout ne*t)p = head2-ne*t;head2-ne*t = p-ne*t;free(p);number2-;bool CityManage:Travel_Edge()/将城市和坐标分别存在数组中,便于求最短路径CityNode *p, *s;p = new CityNode;s = new CityNode;p = head2-ne*t;int a = 0, b = 0, c = 0;for (a = 0; a100; a+)for (b = 0; b100; b+)Weightab = 100;for (a = 0; ane*t;for (b = a + 1;
20、 b* - s-*), 2) + pow(abs(p-y - s-y), 2);s = s-ne*t;p = p-ne*t;p = head2-ne*t;for (c = 0; ccityname;p = p-ne*t;return true;bool CityManage:Travel_Edge_ALL()/将城市和坐标分别存在数组中,便于求最短路径CityNode *p, *s;p = new CityNode;s = new CityNode;p = head-ne*t;int a = 0, b = 0, c = 0;for (a = 0; a100; a+)for (b = 0; b1
21、00; b+)Weightab = 100;for (a = 0; ane*t;for (b = a + 1; b* - s-*), 2) + pow(abs(p-y - s-y), 2);s = s-ne*t;p = p-ne*t;p = head-ne*t;for (c = 0; ccityname;p = p-ne*t;return true;void Travel(int Number)/求最短路径int i, j, k, l;int S100;/用于存储已访问过的城市 /用于存储两个城市之间的距离float sum = 0;/用于记算已访问过的城市的最小路径长度float Dtemp
22、;/保证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表示当前未被访问的
23、城市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 =
24、0; j Number; j+) /输出经过的城市的路径cout citysSj ;cout citys0;cout endl;cout 最短距离为: sum endl;cout * endl endl;void CityManage:Operation()cout ttt* endl;cout ttt* 于博 *:2021212064 * 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
25、;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 *, y;switch (num)case 1: cout 请输入城市名称:
26、 cityname;cout 请输入坐标 endl;cout *;cout y;Insert_CityNode(cityname, *, 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: co
27、ut 请输入坐标 endl;cout *;cout y;Search_CityNode(*, 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);Sa
28、veAgain();system(pause);system(cls);break;case 2: cout 请输入要删除城市的坐标:;cout endl;cout *;cout y;Delete_CityNode(*, 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, cit
29、yname2);system(pause);system(cls);break;case 5: cout n;cout 请输入要查找点的坐标: endl;cout *;cout y;Distance_In_Range(n, *, y);system(pause);system(cls);break;case 6:cout * endl;cout 1,遍历指定城市 endl;cout 2,遍历所有城市 endl;cout * endl;char Num3;cout Num3;switch (Num3)case1:int citycount, ct;cout citycount;cout 请输入城市,最后一个输入出发城市: endl;for (ct = 0; ct cityname;ZDCZ(cityname);Travel_Edge();Travel(number2);Clear();system(pause);system(cls);break;case2:Travel_Edge_ALL();Travel(number);Clear();system(pause);system(cls);break;default:cout Error ne*t;while (p != NULL)