《数据结构课程设计报告模板--计科.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告模板--计科.doc（136页珍藏版）》请在金锄头文库上搜索。
1、数数 据据 结结 构构 课课程程设设计计报报告告 设计题目 各种排序 专 业 计算机科学与技术 班 级 2013 5 学生姓名 张 钧 辉 指导教师 孙 鹏 飞 2014 年 12 月 25 日 指导教师评语 该生能够按照课程设计课程的要求 认 真完成程序编写 获得正确实验结果 验报告清晰整洁 格式符规范 能够正 确运用数据结构知识解决实际问题 加 深了对数据结构知识的理解 指导教师 孙鹏飞 2014年 12 月 26 日 成绩评定 学 号姓 名任务分工成绩 2013026687张钧辉编写代码 制作 ppt 等 目目 录录 1 设计内容设计内容 1 1 1 问题描述 1 1 2 设计要求 1
2、1 3 开发环境 1 1 4 研究思路 1 2 设计步骤设计步骤 5 2 1 需求分析 5 2 2 概要设计 5 2 3 详细设计 9 2 4 调试分析 12 2 5 测试结果 14 3 设计成果展示设计成果展示 17 3 1 用户手册 17 3 2 程序运行部分截图 18 4 总结与心得体总结与心得体会会 19 附附 录录 21 各种排序计算问题 1 1 设计内容设计内容 1 1 问题描述问题描述 给出你所选择的题目的要求描述 给出你所选择的题目的要求描述 课程题目是排序算法的实现 课程设计一共设计 6 种排序算法 这六种算 法包括插入排序 希尔排序 起泡排序 快速排序 选择排序 堆排序和
3、归并排序 1 2 设计要求设计要求 1 输入数据放到文件里 输入要测试的文件名 能输出最短路程 及其路线 2 能用图形演示旅行商的最佳推销路线 1 3 开发环境开发环境 本程序开发环境为 Visual Studio 2003 1 4 研究思路研究思路 对于 旅行商路线选择 这一问题 我们的思路如下 运行程序 调用用户所给标准地图 程序自带中国交通地图与山东 省主要城市及周边省会地图 选择要去的城市 通过坐标算出两城 市之间的距离存入内存 将城市连成一条回路 通过算法将回路优化 优化一定程度后停止 界面显示最优路线与旅行顺序 我们程序的主要算法是遗传算法 其基本描述如下 遗传算法是模拟自然选择和
4、生物进化的过程 以优胜劣汰的方式求解 问题 算法需要选择一种合适的编码方式表示解 并选择一种评价函数来 计算每个解的适应值 适应值高的解可以更容易地被选中并进行交配 从 各种排序计算问题 2 而产生新的子代 选择和交配的过程一直循环 同时以一定的概率进行变 异 直到求得满意解或其它终止条件 算法运行的过程具有很强的指向性 适合众多复杂问题的求解 遗传算法的过程可以抽象为 4 大部分 初始化 选择算子 交配算子 和变异算子 初始化确定具体问题在遗传算法中的编码 群体大小 各种 概率大小等参数 选择算子确定如何在群体中选择新的种群 交配算子使 选出来的种群进行交配以模拟进化 变异算子使新的个体能够
5、保持多样性 旅行商问题规定了每个城市只能出现一次 因此编码有其特殊性 一 般采用整数的编码方式 通过数字序列来表示城市的遍历次序 采用整数 编码方式的简单遗传算法 SGA 的交配策略通常是以单个整数为单位进 行 可称为基于点的交配 为 TSP 设计的交配策略通常都会以边为单位进 行 可称为基于边的交配 1 简单遗传算法的流程如图 各种排序计算问题 3 随机生成初始种群 计算适应值并保存最优解 交配 变异 优化 可省略 计算适应值并 保存最优解 选择新子代 是否满足终止条件 结束 否 是 2 适应度函数 适应度函数必须能够配合选择方式有效区分子代的优劣 我们采 用的方式是 f 1 s 其中 s
6、是路径的总长度 3 选择操作 实验采用了轮盘赌 的选择方式 它是一种经典的 GA 选 各种排序计算问题 4 择方式 概率大个体在轮盘中占有更大的面积 更容易被选中 4 变异操作 变异操作是让遗传算法跳出局部最优的重要手段 一般采用的变 异操作是随机产生两个变异位 把这两个位的城市调换位置 在一次变异 中 选中的个体进行进行 n 20 n 为城市数目 次交换 例 对序列 1 2 3 4 5 6 7 8 执行 2 次交换 变异位分别 2 与 5 3 与 6 那么 一次交换后 1 5 3 4 2 6 7 8 两次交换后 1 5 6 4 2 3 7 8 5 优化搜索 遗传算法一般采用的是 2 opt
7、二段优化 这是一种简单的优化方 案 一次 2 opt 表述如下 选择位置 a b 尝试倒置 ab 间的所有路径 如果路径比原来短 则接受倒置 否则路径保持不变 例如 1 2 3 4 5 6 7 8 倒置 2 5 间路径 则变成 1 5 4 3 2 6 7 8 在我们采用遗传算法的优化中 倒置操作一共进行 n 10 次尝试 同 时因为倒置较长的序列通常不会得到路径提升 所以控制倒置位置 a b 之间的差小于等于 n 5 由于我们的问题实际属于动态旅行商问题 我们提前做了两个假定 1 旅行期间 城市间的交通都很发达 不存在因交通而耽误时间现 象 2 在信息采样周期内 城市的规模与城市之间的距离等参
8、数固定 各种排序计算问题 5 2 设计步骤设计步骤 2 1 需求分析需求分析 市场营销需要商家派遣人员到各个城市去调查市场状况和推销公司产 品 为了节省开销和节约路途花费时间 就产生了旅行商到各个城市的顺 序和最短路线选择问题 基于以上问题 旅行商们需要的是一款能够直观反映所需到达城市的 顺序以及最短路线的可视化应用程序 以供自己参考决策 选择最佳行程 因此 我们的程序为了解决以上问题 采用了 C 语言编程 其主要 功能是 用可视化界面给用户提够所需到达城市的最短路线 用户只需用 鼠标和热键点击选择所需到达城市 然后通过程序运算 就可看到行程路 线 2 2 概要设计概要设计 针对主要功能 我们
9、首先要设计可视化界面 然后在控件上添加事件 过程 再编写代码 1 程序中使用的主要变量 x 点的横坐标 y 点的纵坐标 CitySites Point 城市序列 RoomSize 空间大小 Comput 是否正在计算 KillMsg 是否关闭计算 DistanceM 距离矩阵 各种排序计算问题 6 DMSize 矩阵大小 BestIndex 最有序列 CurrBestIndex 当前最有序列 BestMark 最高分 AVGMark 平均分 GenNum 代数 BestGen 最优代 JumpCountDown 突变剩余次数 JumpCount 突变次数 TimeUsed 使用时间 ProPa
10、th 当前路径 2 使用的主要函数 GetCityNum 获取城市数量 GetCitySite int index 获取城市地图中的某点 Variant 变异函数 ThreadPro pParam LPVOID 辅助线程 ComputeDistanceMatrix 计算距离矩阵 DestroyDistanceMatrix 销毁举例矩阵 Mark gene GENE 实现界面的初始化 OnLButtonDown 对鼠标做出的反应 实现选中点 OnLButtonUp UINT nFlags CPoint point 释放鼠标捕捉 OnMouseMove UINT nFlags CPoint poi
11、nt 对鼠标移动的反应 OnKeyDown 实现对键盘的反应 这里只处理用 Shift D 删除 点 下面的函数实现下拉菜单地图里面的子菜单的反应 各种排序计算问题 8 OnOpen 实现对菜单栏 打开地图 的反应 OnSave 实现对菜单栏 保存地图 的反应 OnRandom 实现对菜单栏 随机生成 的反应 OnDelete 实现对菜单栏 删除城市 的反应 OnClear 实现对菜单栏 清空地图 的反应 OnExit 实现对菜单栏 退出 的反应 下面函数实现计算功能 OnStartcomput 实现对菜单栏 开始计算 的反应 OnStopcomput 实现对菜单栏 停止运算 的反应 各种排序
12、计算问题 9 下面的函数实现背景菜单的功能 OnSetbk 实现对菜单栏 设置背景 的反应 OnShowback 实现对菜单栏 显示背景 的反应 OnHelp 实现对菜单栏 帮助的反应 OnTimer UINT nIDEvent 计时器 每隔一段时间做出的反应 除了这三个类以外 还有像一些产生对话框需要的类 例如 RandCreateDlg 等 2 主程序运行界面 3 程序结束界面 各种排序计算问题 10 2 3 详细设计详细设计 1 通过我们初步的分析 研究过旅行商的算法 包括蚁群算法 变异 算法 神经网络算法等 决定使用变异算法 并进入详细设计阶段 详 细设计阶段分为界面设计和代码设计 开
13、始我们打算利用 VB 实现程序的 但是由于程序中大量的使用到了指针 使用 VB 不能满足程序的需要 我 们选择了 C 虽然我们几个并不是很懂 但是由于我们中有几个已经接 触过 所以我们也就拿了几本书 边学边做 2 首先 我们的程序中的类有 1 CityMap 类 因为这个类这是我们程序中最重要的一个类 里面包 含了我们程序使用的绝大多数函数 2 Point 类 因为距离在平面图上的表示并不容易 我们选择了利用 点坐标定义点 然后通过点坐标计算距离矩阵 这就设计到了我们程序中 各种排序计算问题 11 最基本的一个类 Point 类 其中属性有 x y 坐标 行为有求距离 以便 于距离矩阵的求出
14、3 TravellerDlg类 这个类是程序主界面的主要控制程序 对主界面的 程序做出相应的反应 包括鼠标 包括 键盘 包括菜单的单击属性 主 要是用MFC实现 通过MFC来实现界面的布局 主要方法有 3 主要函数解释 1 变异函数 Variant 这是变异函数得来的原因 实现了有父代到子 代的变异 顺次变异按块变异 随机数 2 56565 65656565556 发达的花费较 大 地方就是 老大的房间乐 山大佛份开始 对焦方式地方 都是分开计算 得分手段废旧 塑料地方就是 打开见风使舵 发送到飞水电 开发家里看书 的肌肤上的风 建设力度封建 时代快捷方式 简单方 2 1 0 顺次交换 将 i
15、 到 j 之间的点依次与 m 到 n 之间的点进行交换 交换函数 如下 tmp gdest index m gdest index m gdest index n gdest index n tmp ijmn 按块交换 将第 i 块和第 m 块交换 将第 j 块和第 m 块交换 每一块中含 有的元素不定 每次都是随机生成 用下面函数实现函数如下 各种排序计算问题 12 memcpy ptemp gdest index n sizeof int 其中 ptemp 为暂存区为目标区 gdest index 表示原目标 n 表示要复制的长度 详细代码见附录 ijmn 2 距离矩阵的计算函数 Comp
16、uteDistanceMatrix 根据点坐标 求得距离矩阵 便于计算使用 由于距离问题的特殊性 其距离矩阵为一 个对称矩阵 且对角线上的都为 0 所以生成的矩阵格式如下 1 0 2 0 3 0 4 0 2 1 3 1 3 2 4 1 5 0 5 1 5 2 5 3 5 4 4 2 4 3 3 四边形优化 此函数主要实现了图的每次优化 为一个调整函 数 各种排序计算问题 13 d 0 d d d 1 2 3 通过移动线 构造平行四边形 然后通过钝角的证明 利用原理两边之和 等于第三边上的中线的两倍 则该三角形为直角三角形 如果 d0 d2 d1 d3 则形成的角比为锐角 如果是对钝角 则说明该四边形不用优 化 如果不是则将该四边形进行优化 因为要构成一个闭合的最短回路则 要是所有的这些构成整个环路的的这些四边形都是钝角 2 4 调试分析调试分析 1 此程序由于设计到的问题比较繁琐 开始是我们打算使用中国邮路的 算法进行求解 但是由于那个算法对于数量较大时效率太低 我们选择了 变异算法 当然程序的复杂度也大大的增加 又由于我们的程序使用 MFC 来实现 而且我们以前也都没有接触过 MFC
