数据结构课程设计设计说明书TSP 问题起止日期：2016 年 6 月27 日至2016 年7 月 1 日学生姓名班级学号成绩指导教师( 签字)2016 年7 月 1 日目录第1 章需求分析.................................................................................1...1.1 简介 (1)1.2 系统的开发背景 (1)1.3 研究现状 (1)第2 章概要设计.................................................................................2...2.1 系统开发环境和技术介绍 (2)2.2 系统需求分析 (2)2.2.1 总体功能分析 (2)2.2.2 核心功能分析 (3)第3 章详细设计...................................................................................4...3.1 系统开发流程 (4)3.2 系统模块设计 (4)3.3 系统结构 (6)3.2 系统流程图 (6)第4 章调试分析...................................................................................7...4.1 程序逻辑调试 (7)4.2 系统界面调试 (8)第5 章测试结果...................................................................................9...5.1 测试环境 (9)5.2 输入输出测试项目 (9)5.3 测试结果 (10)结论.....................................................................................................1..1.. 参考文献................................................................................................1..1. 附录.......................................................................................................1..2..第1章需求分析1.4简介旅行商问题，即TSP问题（Travelling Salesman Problem ）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。
假设有一个旅行商人要拜访n 个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。
路径的选择目标是要求得的路径路程为所有路径之中的最小值。
1.5系统的开发背景TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64 个方格，走访64 个方格一次且仅一次，并且最终返回到起始点。
TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。
1.6研究现状T SP问题是一个组合优化问题。
该问题可以被证明具有NP计算复杂性。
因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
旅行推销员问题是图论中最著名的问题之一，即“已给一个n 个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。
Edmonds，Cook和Karp 等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。
迄今为止，这类问题中没有一个找到有效算法。
倾向于接受NP完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。
第2 章概要设计1.7系统开发环境和技术介绍Microsoft Visual C++ 6.0 不仅是一个C++ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境（IDE）。
Visual C++6.0 由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard 等开发工具。
这些组件通过一个名为Developer Studio 的组件集成为和谐的开发环境。
1.8系统需求分析2.3总体功能分析TSP问题最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。
但是用穷举法求解TSP问题的时间复杂度为Ο(n!) ，当n 大到一定程度后是不可解的。
于TSP问题，一个旅行家要穿过多个城市，已知城市个数，以及城市间距，每个城市经历且只经历一次，求出最短路径解和最短路径长度。
本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。
输入城市数目N为正整数，城市间距离按邻接矩阵方式排列输入，最小值为0，共有N*N个数值；输出最优解和最优值。
2.4核心功能分析以下是核心功能代码分析：贪心算法排序：为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。
起初，算法选出的候选对象的集合为空。
接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。
如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。
每一次都扩充集合，并检查该集合是否构成解。
如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
代码如下图所示：WORD格式第3章详细设计1.9系统开发流程1、上网查找与题目相关的资料，并重点阅读课本上的相关知识。
2、对问题进行抽象，得到描述问题的算法，编写出程序。
3、设计完整的程序进行演示。
4、对设计进行总结分析。
1.10系统模块设计功能模块：主函数：int main()主要由以下函数构成：int DistanceMin(int *p) ：搜索得到与当前距离最近的城市，返回当前距离最短节点对应下标void CreatArry() ：动态创建标记数组void CreateMatrix() ：动态创建矩阵void TSP() ：贪心算法排序1.11系统流程图第4章调试分析1.12程序逻辑调试由于以下程序中定义CreateMatrix 时忘记加括号导致程序错误。
1.13系统界面调试请输入城市数：输入城市间距离的邻接矩阵：输入一个邻接矩阵0 20 30 30 80 5020 0 40 55 70 3030 40 0 60 65 4530 55 60 0 75 3580 70 65 75 0 9050 30 45 35 90 0第5章测试结果1.14测试环境安全无误，测试运行其上的软件和硬件环境的描述。
准备一些数据用于测试。
设计测试用例时，相应的输出结果正确，而且测试用例应包括合理的输入数据和不合理的输入数据。
1.15输入输出测试项目（1）输入：a. 城市数：6（如下图）：b. 城市间距离的邻接矩阵（如下图）（2）输出：a. 最短路径：1->2,2->6,6->4,4->3,3->5,5->1.b. 最短距离：2901.16测试结果结论本次数据结构的课程设计，从第一天的选题到最后一天的设计成果，虽然时间只有短短一周，但我收获良多。
开始对于TSP这个问题，只是对旅行者的问题比较感兴趣，经过百度详细的TSP问题实例与计算，我选择了TSP问题。
我认为在程序设计中细心很重要，常常一个符号的错误就需要很长时间的修改。
在设计过程中要善于查找资料，认真查看课本，又不懂的问题及时问老师或者同学。
数据结构这是一门知识，纯属于设计的科目，它需用把理论变为上机调试。
纯属于设计的科目，它需用把理论变为上机调试。
我选的上机题目是TSP问题。
刚开始都没什么思路，后面问了老师和同学加上自己百度逐渐有了思路，刚开始调试代码的时候有时就是一个很小的错误，导致整个程序不能运行。
在看程序的过程中，不断的上网查资料以及翻阅相关书籍，通过不断的模索，测试，发现问题，解决问题和在老师的帮助下一步一步慢慢的正确运行程序，终于完成了这次课程设计。
过程中每当程序错误时我都非常焦躁，甚至想到了放弃，但我最终找到了状态，一步一步慢慢来，经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然具备的条件！通过本次课程设计巩固了课本的基本知识，熟练运用课程知识。
提高我们组织数据及编写程序的能力，使我们能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的问题在计算机内部表示出来并用软件解决问题，本次实验大大提高了我们对编程的爱好。
同时，通过此次课程设计使我了解到，硬件语言必不可缺少，要想成为一个有能力的人，必须懂得硬件语言。
自已懂得的知识很是不足，学无止境，以后还会更加的努力深入的学习。
参考文献[1] 严蔚敏，吴伟民. 数据结构[M] ，清华大学出版社。
[2] 谭浩强. 《C语言程序设计》（第三版）. 清华大学出版社。
[3] 刘振鹏，罗文劼，石强. 《数据结构》（第三版）. 中国铁道出版社。
[4] 李长云，廖立君，王平，童启，王志兵.《C语言程序设计》国防工业出版社。
附录源代码如下：#include<stdio.h>#include<stdlib.h>int *choiced; // 定义于全局，所有函数都能访问int **matrix; // 定义二级指针，操作矩阵int n; // 节点数int DistanceMin(int *p); // 返回当前距离最短节点对应下标void CreatArry(); // 动态创建标记数组void CreateMatrix(); // 动态创建矩阵void TSP(); // 贪心算法排序int main(){printf(" 输入城市数:\n");scanf("%d",&n);CreateMatrix();CreatArry();TSP();return 0;}void CreateMatrix(){int i=0,j=0;matrix=(int **)malloc ((sizeof(int *))*n); // 动态创建n 行n 列矩阵for(i=0;i<n;++i){matrix[i]=(int *)malloc ((sizeof(int *))*n);}printf(" 输入城市间距离的邻接矩阵:\n",n);for(i=0;i<n;i++) // 输入数据到矩阵{for(j=0;j<n;j++){scanf("%d",&matrix[i][j]);}}}void CreatArry(){int i=0;choiced=(int *)malloc ((sizeof(int *))*n); choiced[0]=0;for(i=1;i<n;i++){choiced[i]=1;}}int DistanceMin(int *p){int start=0,min=p[0],k=0;while(choiced[start]==0){start++;min=p[start];}for(;start<n;start++){if((choiced[start]==1)&&(min>=p[start])){k=start;min=p[k];}}return k;}void TSP(){int i=0,j=0,s=0;int log=0;printf(" 最短路径为:\n");for(;log<n;log++){j=DistanceMin(matrix[i]);choiced[j]=0;printf("%d->%d,",i+1,j+1);s=s+matrix[i][j];i=j;}printf("\n");printf(" 最短距离为:%d\n",s);char wait;scanf("%c",&wait);scanf("%c",&wait);}。