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

课程设计报告 设计题目 城市管理 学生姓名 魏于博 专 业 电子信息工程 班 级 电信工 17 1 班 学 号 指导教师 方帅 完成日期 2018 年 6 月 29 日 合肥工业大学计算机与信息学院 1 1 需求和规格说明需求和规格说明 问题描述 问题描述 问题描述 问题描述 用无序表实现一个城市数据库 每条数据库记录包括城市名 任意长的字符串 和城市的坐标 用整数 x 和 y 表示 实现数据的插入 删除 查询功能 并实现指定距离内的所有城市 设计算法实现指定一定数目 的具体城市 寻找遍历这些城市并回到出发点的最佳路径 观察随着城市数目 的增加 算法执行效率的变化 编程任务 编程任务 1 用列表对城市进行记录和管理 实现城市的增加 删除和查询功能 并 实现文件保存和读取 2 计算城市之间距离 统计输出距离某城市一定范围内的所有城市 3 实现一定规模城市的遍历最佳路径选择 4 分析随着城市数目增加时 算法执行效果的改变 深刻理解旅行商问题 2 2 设计设计 建立一个 CityNode 包含城市的名称 横纵坐标和指针 再建立一 CityManage 类 属性和方法定义 类名类名成员类成员类 别别 类型类型成员名成员名描述描述 Stringcityname 城市名称 intx 城市的横坐标 inty 城市的纵坐标 CityNode 属性 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 判断是否已经存在 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 3 用户手册用户手册 4 4 调试及测试调试及测试 1 1 添加城市添加城市 若城市已存在 则提示存在 不能添加若城市已存在 则提示存在 不能添加 2 2 查找城市查找城市 通过名称查找通过名称查找 通过坐标查找 3 删除城市 通过名称删除 通过坐标删除 4 查看两城市间的距离 5 查找距离定点一定距离的城市 6 查找最优路径 1 制定城市查询最短路径 2 全部城市最短路径 测试数据 环形数据能更好的检测 中国 9 1 合肥 9 6 广州 5 6 深圳 5 1 安徽 1 6 北京 1 1 7 7 查看所有城市查看所有城市 5 5 附录程序代码附录程序代码 include include include include include using namespace std int number 0 number2 0 float Weight 100 100 string citys 100 struct CityNode string cityname float x y CityNode next struct minedge int vex int low minedge Edge 100 void Travel class CityManage public 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 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 cout endl cout cityname x y endl cout endl cout next cout 所在坐标下没有城市 next while k NULL if k x x 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 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 a 100 a for b 0 b 100 b Weight a b 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 a 100 a for b 0 b 100 b Weight a b 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 S 100 用于存储已访问过的城市 用于存储两个城市之间的距离 float sum 0 用于记算已访问过的城市的最小路径长度 float Dtemp 保证 Dtemp 比任意两个城市之间的距离都大 其实在算法描述中更准确的应为无穷大 int flag 最为访问的标志 若被访问过则为 1 从未被访问过则为 0 初始化 i 1 i 是至今已访问过的城市 S 0 0 do k 1 Dtemp 100 do l 0 flag 0 do if S l k 判断该城市是否已被访问过 若被访问过 flag 1 则 flag 为 1 break 跳出循环 不参与距离的比较 else l while l i if flag 0 j 用于存储已访问过的城市 k Dtemp Weight k S i 1 Dtemp 用于暂时存储当前最小路径的值 k while k Number S i j 将已访问过的城市 j 存入到 S i 中 i sum Dtemp 求出各城市之间的最短距离 注意 在结束循环时 该旅行商尚未回到原出发的 城市 while i Number sum Weight 0 j D 0 j 为旅行商所在的最后一个城市与原出发的城市之间的距离 cout endl cout 路线如下 endl cout endl cout for j 0 j Number j 输出经过的城市的路径 cout citys S j cout citys 0 cout endl cout 最短距离为 sum endl cout endl endl void CityManage Operation cout t t t endl cout t t t 作者 魏于博 学号 endl cout t t t 城市管理 endl cout t t t endl cout t t t t t 1 添加城市 t t t t endl cout t t t t t 2 查找城市 t t t t endl cout t t t t t 3 删除城市 t t t t endl cout t t t t t 4 两个城市间的距离 t t t endl cout t t t t t 5 查找距离某地为 n 的城市 t t endl cout t t t t t 6 最短距离遍历指定城市 t t endl cout t t t t t 7 查看所有城市 t t t endl cout t t t t t 8 退出城市管理系统 t t t endl cout t t t endl cout t t t 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 遍历所有城