《数据结构课设之地图着色》由会员分享，可在线阅读，更多相关《数据结构课设之地图着色（20页珍藏版）》请在金锄头文库上搜索。
1、1课程设计(论文)任务书软 件 学 院 学 院 软 件+电气 专 业 2011 3 班一、课程设计(论文)题目 地图着色问题 二、课程设计(论文)工作自 2012 年 12 月 29 日起至 2013 年 1 月 6 日止 三、课程设计(论文) 地点: 科 技 楼 机 房 四、课程设计(论文)内容要求：1本课程设计的目的训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。2课程设计
2、的任务及要求1）基本要求：要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率；程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释；每位同学需提交可独立运行的程序和规范的课程设计报告。2）课程设计论文编写要求理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等；设计部分应包含系
3、统功能模块图，调试分析应包括运行截图等。3）课程设计评分标准： 2学习态度：10分；系统设计：20分；编程调试：20分；回答问题：20分；论文撰写：30分。4）参考文献：严蔚敏,吴伟民. 数据结构(C语言版)M. 清华大学出版社. 2010.3 严蔚敏,吴伟民. 数据结构题集(C语言版)M. 清华大学出版社. 1999.2何钦铭,冯燕等. 数据结构课程设计M. 浙江大学出版社 . 2007.85）课程设计进度安排准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；程序模块设计分析阶段（4学时）：程序概要设计、详细设计；代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；撰写
4、论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。学生签名： 2012 年 12 月 29 日6）课程设计题目具体要求：已知江西地图，请设计地图着色软件，对11个地级市进行着色，要求相邻地级市所使用的颜色不同，并保证使用的颜色最少。基本要求：地图采用图型数据结构，每个地级市为一个节点，边表示对应的两个地级市相邻。设计着色算法，保证邻接点不是同一种颜色。演示程序以用户和计算机的对话方式进行。课程设计(论文)评审意见（1）学习态度（10分）：优（）、良（）、中（）、一般（）、差（）； （2）系统设计（20分）：优（ ）、良（）、中（）、一般（）、差（）； （3）编程调试（20分）：
5、优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（30分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）3评阅人： 王英华 职称： 讲师 2013 年 1 月 7 日4目录一、设计任务 .4二、需求分析 .4三、系统设计 .53.1 系统总体框架，系统流程 .53.2 详细设计 .64.1 测试当前点所连接的点是否全部被标记颜色 .74.2 测试当前着色方案是否可行 .74.3从current开始标记，sum的地图上的11市， colorN为标记颜色 .74.4 菜单设计
6、.84.5 实现加载的动态界面 .8五、调试分析与结果 .10六、课设总结 .12七、参考文献 .13八、附源代码 .145一、设计任务问题描述：已知江西地图，请设计地图着色软件，对11个地级市进行着色，要求相邻地级市所使用的颜色不同，并保证使用的颜色最少。基本要求：地图采用图型数据结构，每个地级市为一个节点，边表示对应的两个地级市相邻。设计着色算法，保证邻接点不是同一种颜色。演示程序以用户和计算机的对话方式进行。二、需求分析该程序包含八个模块：第一个加载程序模块，主要是体现界面的美观；第二个模块为着色模块，包含初始化地图和开始着色，其中开始着色还包括了判断着色方案是否可行的模块，判断着色方案
7、可行性的模块又包括对当前点的邻接点所有的点是否已经着色分析的模块；第四个模块为菜单模块；其他两个模块分别为关于6江西和关于作者的模块；7三、系统设计3.1 系统总体框架，系统流程加载的演示。进入程序关于江西江西地图江西地图染色关于软件退出系统尝试染色当前方案当前点所连接的市是否全部染色83.2 详细设计void load(); /加载UI调用system()函数改变 窗体颜色，调用time，实现加载效果void menu(); /菜单主要使用输出语句，以及调用system()函数实现改变窗体颜色以及暂停和清屏void aboutjx(); /关于江西使用输出语句输出关于江西的简介void ab
8、outme(); /关于作者输出语句输出关于作者int all_color(int jx_mapNN, int colorN, int current);使用for语句测试当前点所连接的点是否全部被标记颜色int yes(int jx_mapNN, int colorN, int current);使用for语句和if语句判断测试当前着色方案是否可用void sta(int jx_mapNN,int colorN,int sum,int current);综合使用if-else和for语句对地图进行递归着色，着色过程中用yes函数进行判断是否可行；void set_color();set_co
9、lor()函数为接口进行着色，包括初始化，还有调用sta( )函数着色；关于着色的算法为本程序重点，下面用进行详细分析：调用 递归调 用调用set_color( )函数初始化sta( )函数For i = 1 - 4着色：color = i城市for 1-11yes( )函数all_color( )函数9四、编码实现4.1 测试当前点所连接的点是否全部被标记颜色int all_color(int jx_mapNN, int colorN, int current)int p = 1;for(int j = 1; j #include #include 江西地图着色.h using namesp
10、ace std;int main() load();menu(); int n;while(cinn)switch(n)case 1: aboutjx();break;case 2: JXmap(); break;case 3: set_color();break;case 4: aboutme();break;case 5: aboutme(); cout #include #include #include #include#define N 12using namespace std;void menu(); /菜单void load(); /加载UI void aboutjx();vo
11、id aboutme();/void InitMap();void aboutjx()system(color 8E);cout表示i市与j市有领土相邻endl; void set_color()int colorN=0; /*每个市所染的颜色*/ int i; int jx_mapNN=0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0, 0,1,0,0,1,0,0,1,0,0,0,0, 0,1,0,1,0,0,1,1,0,0,0,0, 0,1,0,0,0,0,1,0,0,0,0,0, 0,1,0,0,1,1,0,1,0,1,0,1, 0,0,0,1,1,0,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,1,0,0, 0,0,0,0,0,0,1,1,0,0,1,1, 0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0;sta(jx_map,color,11,1); printf(n); cout*endl;23cout各市代号：1上饶 2 景德镇 3 九江 4南昌 endl;cout5鹰潭 6抚州 7宜春 8 新余 9吉安 10萍乡 11赣
