数据结构课设之地图着色.doc

课程设计(论文)任务书 软 件 学 院 学院 软 件+电气 专业 2011 3 班一、课程设计(论文)题目 地图着色问题 二、课程设计(论文)工作自 2012 年 12 月 29 日起至 2013 年 1 月 6 日止 三、课程设计(论文) 地点: 科 技 楼 机 房 四、课程设计(论文)内容要求：1本课程设计的目的训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。2课程设计的任务及要求1）基本要求：要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率；程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释；每位同学需提交可独立运行的程序和规范的课程设计报告。2）课程设计论文编写要求理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等；设计部分应包含系统功能模块图，调试分析应包括运行截图等。3）课程设计评分标准： 学习态度：10分；系统设计：20分；编程调试：20分；回答问题：20分；论文撰写：30分。4）参考文献：严蔚敏,吴伟民. 数据结构(C语言版)M. 清华大学出版社. 2010.3 严蔚敏,吴伟民. 数据结构题集(C语言版)M. 清华大学出版社. 1999.2何钦铭,冯燕等. 数据结构课程设计M. 浙江大学出版社. 2007.85）课程设计进度安排准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；程序模块设计分析阶段（4学时）：程序概要设计、详细设计；代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。学生签名： 2012 年 12 月 29 日6）课程设计题目具体要求：已知江西地图，请设计地图着色软件，对11个地级市进行着色，要求相邻地级市所使用的颜色不同，并保证使用的颜色最少。基本要求：地图采用图型数据结构，每个地级市为一个节点，边表示对应的两个地级市相邻。设计着色算法，保证邻接点不是同一种颜色。演示程序以用户和计算机的对话方式进行。课程设计(论文)评审意见（1）学习态度（10分）：优（）、良（）、中（）、一般（）、差（）； （2）系统设计（20分）：优（ ）、良（）、中（）、一般（）、差（）； （3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（30分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 王英华 职称： 讲师 2013 年 1 月 7 日23目录一、设计任务4二、需求分析4三、系统设计53.1 系统总体框架，系统流程53.2 详细设计64.1 测试当前点所连接的点是否全部被标记颜色74.2 测试当前着色方案是否可行74.3从current开始标记，sum的地图上的11市，colorN为标记颜色74.4 菜单设计84.5 实现加载的动态界面8五、调试分析与结果10六、课设总结12七、参考文献13八、附源代码14一、设计任务问题描述：已知江西地图，请设计地图着色软件，对11个地级市进行着色，要求相邻地级市所使用的颜色不同，并保证使用的颜色最少。基本要求：地图采用图型数据结构，每个地级市为一个节点，边表示对应的两个地级市相邻。设计着色算法，保证邻接点不是同一种颜色。演示程序以用户和计算机的对话方式进行。二、需求分析 该程序包含八个模块：第一个加载程序模块，主要是体现界面的美观；第二个模块为着色模块，包含初始化地图和开始着色，其中开始着色还包括了判断着色方案是否可行的模块，判断着色方案可行性的模块又包括对当前点的邻接点所有的点是否已经着色分析的模块；第四个模块为菜单模块；其他两个模块分别为关于江西和关于作者的模块；三、系统设计加载的演示。3.1 系统总体框架，系统流程当前点所连接的市是否全部染色当前方案尝试染色江西地图染色退出系统关于软件江西地图关于江西进入程序 3.2 详细设计void load(); /加载UI调用system()函数改变 窗体颜色，调用time，实现加载效果void menu(); /菜单主要使用输出语句，以及调用system()函数实现改变窗体颜色以及暂停和清屏void aboutjx(); /关于江西使用输出语句输出关于江西的简介void aboutme(); /关于作者输出语句输出关于作者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_color()函数为接口进行着色，包括初始化，还有调用sta( )函数着色；关于着色的算法为本程序重点，下面用进行详细分析： yes( )函数sta( )函数set_color( )函数初始化 调用 递归For i = 1 - 4着色：color = i城市for 1-11 调 用all_color( )函数调用四、编码实现4.1 测试当前点所连接的点是否全部被标记颜色int all_color(int jx_mapNN, int colorN, int current)int p = 1;for(int j = 1; j current; j+)if(jx_mapcurrentj = 1) p = 0;if(p)return 1;return 0;4.2 测试当前着色方案是否可行int yes(int jx_mapNN, int colorN, int current) if(all_color(jx_map, color, current) return 1;int j; for(j = 1; j current; j+) if ( (jx_mapcurrentj = 1) & (colorj = colorcurrent) ) return 0;/*城市相邻且颜色相同*/ return 1; 4.3从current开始标记，sum的地图上的11市，colorN为标记颜色void sta(int jx_mapNN,int colorN,int sum,int current) int i; if (current =sum) for(i=1;i =4;i+)/*测试每种颜色*/ colorcurrent=i;/*尝试着色*/ if( yes(jx_map, color,current) )/*若尝试成功*/ sta(jx_map, color,sum,current+1);/*检查下一个城市*/ return; 4.4 菜单设计void menu()system(color 2F);printf(欢迎使用地图着色系统软件！n);printf(3 3 -1.关于江西- n);printf( 3 -2.江西地图- 3 3n);printf( 3 -3.江西地图着色- 3 n);printf( -4.关于本软件- 3 n);printf(5.退出系统|n); printf( 3请选择服务：n);4.5 实现加载的动态界面void load() /加载中的动态界面 int n = 5;time_t start,end;while(n-) /*五次循环*/start=time(NULL); /读取机器时间 end=time(NULL);string ch5;ch4 = n;ch3 = n;ch2 = n;ch1 = n;ch0 = n;while(end-start1) /*每次循环1s*/system(color 3D);cout请稍等nnnttn;couttt 程序加载中。n;couttchn;system(cls);end=time(NULL); system(cls);system(color 2F);couttt 加载成功！;printf(n);五、调试分析与结果起初着色算法只写了两个函数yes( )函数和sta( )函数，另外写了个初始化的函数让用户来输入江西地图，那时候运行正常，可是后来想想 江西地图固定的，也就是说用户不能让原本不相邻的南昌和赣州 输成相邻，所以，另外写了个初始化，直接在代码中写好了，并注明了111编号分别代表那个省；但是问题出现了，当测试到第二个城市的时候就不染色了，程序异常退出；苦苦查了好久，发现由于我标号的时候，景德镇市标为2号，只和1号上饶市相连，而1号之前已经染色了，导致找不到下一个染色对象了。于是改进yes函数，添加all_color( )函数进行判断是否当前点相连的其他城市已全部染色，如果是，依然满足条件，返回1；染下一个城市； 六、课设总结通过这次课程设计我感受了编程的乐趣从中也学到了不少知识。大一我们学习了C语言程序设计 和c+程序设计但学的不是很好前几章还行,但越往后就有点跟不上了因此C语言编程中的问题很大。尤其是指针还有形参和实参的传等 问题都没搞的很清楚而且同大多数人一样眼高手低编程量太少了容易 出问题所以做起来很困难。 我感受最深的一点是以前上实验课时只是注重如何编写函数能够完成所需要的功能似乎没有明确的战术只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗有勇无谋只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前自己能够综合考虑各种因素首先选取自己需要的数据结构是树还是图或是别的什么然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前可以仔细斟酌比对挑选出最适合当前状况的算法。这样即使在完整的程序还没有写出来之前自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。经历了这次课程设计不仅对我的学习提供了帮助而且在意志力方面也得到了锻炼。没有足够的耐力和信心就很难坚持对课程设计每一步的顺利进行。 总之我会继续我的兴趣编写程序的相信在越来越多的尝试之后自己会不断进步不断提高的七、参考文献严蔚敏,吴伟民. 数据结构(C语言版)M. 清华大学出版社. 2010.3严蔚敏,吴伟民. 数据结构题集(C语言版)M. 清华大学出版社. 1999.2何钦铭,冯燕等. 数据结构课程设计M. 浙江大学出版社. 2007.8Thomas H.Cormen. Charles E.Leserson 算法导论 机械工业出版社 2006.9百度百科 - 四色猜想 /view/6807.htm八、附源代码江西地图着色.cpp#include #include #include 江西地图着色.h using namespace 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(); coutbye!n ;exit(1);default : coutInput Error!;system(pause);system(cls);menu(); return 0; 江西地图着色.h/*-定理：注明的四色定理表明：任何平面地图可以使用4种颜色给每个不同的城 市或区域着色，而保证相邻的城市着不同的颜色。 思路：把地图上的每个城市抽象为一个点，并给每个城市 编号，相邻的城市之间用直线连接。据此做出邻接 矩阵，若第i个城市与第j个城市相邻，则 mapij=1,否则mapij=0。 算法：按照编号从小到大的顺序检查每个城市，对每个城市从1到4使用4种颜色着色，若当前颜色可用（即不与相邻城市颜色相同），则着色；否则测试下一种颜色。*/#include #include #include #include #include#define N 12using namespace std;void menu(); /菜单void load(); /加载UI void aboutjx();void aboutme();/void InitMap();void aboutjx()system(color 8E);cout江西省，简称赣(gn)，位于中国东南部，长江中下游南岸。属江南地带，endl;cout东临浙江、福建，南嵌广东，西靠湖南，北毗湖北、安徽而共接长江，endl;cout是中国毗邻省市最多的省份，为长江三角洲、珠江三角洲和海西经济区等发达地区的共同腹地。endl;cout自古以来素有“物华天宝、人杰地灵”之誉，文物古迹、风景名胜众多，endl;cout庐山、滕王阁、三清山、婺源、龙虎山、井冈山等闻名海内外。endl;cout江西总面积16.69万平方公里，人口4456.75万（2010年），由11个地级市组成，省会南昌市。endl; void aboutme()system(color 1C);coutECJTU_软件+电气3班 付强 编写；endl;cout大二第一学年数据结构课程设计；endl;cout感谢您的使用；endl;/*void InitMap(int jx_mapNN) /江西地图是固定的，所以此功能隐去 memset(jx_map,0,sizeof(jx_map);coutscanf a,b, stand for a,b is near.endl;coutscanf 0 0 exit scanfendl;int a,b;while(scanf(%d%d,&a,&b),a&b)jx_mapab = jx_mapba = 1;*/int all_color(int jx_mapNN, int colorN, int current)int p = 1;for(int j = 1; j current; j+)if(jx_mapcurrentj = 1) p = 0;if(p)return 1;return 0;/*测试当前着色方案是否可行*/ int yes(int jx_mapNN, int colorN, int current) if(all_color(jx_map, color, current) return 1;int j; for(j = 1; j current; j+) if ( (jx_mapcurrentj = 1) & (colorj = colorcurrent) ) return 0;/*城市相邻且颜色相同*/ return 1; /*从current开始标记，sum为总的地图上的11市，colorN为标记颜色*/void sta(int jx_mapNN,int colorN,int sum,int current) int i; if (current =sum) for(i=1;i =4;i+)/*测试每种颜色*/ colorcurrent=i;/*尝试着色*/ if( yes(jx_map, color,current) )/*若尝试成功*/ sta(jx_map, color,sum,current+1);/*检查下一个城市*/ return; void load() /加载中的动态界面 int n = 5;time_t start,end;while(n-)start=time(NULL); /延迟两秒操作end=time(NULL);string ch5;ch4 = n;ch3 = n;ch2 = n;ch1 = n;ch0 = n;while(end-start1)system(color 3D);cout请稍等nnnttn;couttt 程序加载中。n;couttchn;system(cls);end=time(NULL); system(cls);system(color 2F);couttt 加载成功！;printf(n);void menu()system(color 2F);printf(欢迎使用地图着色系统软件！n);printf(3 3 -1.关于江西- n);printf( 3 -2.江西地图- 3 3n);printf( 3 -3.江西地图着色- 3 n);printf( -4.关于本软件- 3 n);printf(5.退出系统|n); printf( 3请选择服务：n);void JXmap()system(color 5E);cout各市代号：1上饶 2 景德镇 3 九江 4南昌 endl;cout5鹰潭 6抚州 7宜春 8 新余 9吉安 10萍乡 11赣州endl; cout_ 1_2_3_4_5_6_7_8_9_10_11endl;cout1| 0,1,1,1,1,1,0,0,0,0,0endl;cout2| 1,0,0,0,0,0,0,0,0,0,0endl;cout3| 1,0,0,1,0,0,1,0,0,0,0endl;cout4| 1,0,1,0