课程设计地图着色课程设计名称：课程设计专业班级：学生姓名：学号：指导教师：课程设计时间：计算机专业课程设计任务书目录1 需求分析 (4)2 概要设计 (4)3详细设计 (5)4 运行环境 (6)5开发环境 (6)6 程序设计.............................................................................................6~97 调试分析........................................................................................9~108 测试结果 (10)9参考文献 (11)10心得体会 (11)11成绩评价表 (12)a) 1需求分析A 已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；B 将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系；C 演示程序以用户和计算机的对话方式进行；D 最后对结果做出简单分析。
b ) 2概要设计：i 画程序整体结构图ii 分配函数功能功能模块的划分及模块间调用关系typedef struct //定义图{vextype vexs[MAXedg]; //存放边的矩阵adjtype arcs[MAXedg][MAXedg]; //图的邻接矩阵int vnum,arcnum; //图的顶点数和边数}Graph;C) 3详细设计i ) 主要功能模块的算法思想及其步骤着色模块：int colorsame(int s,Graph G)//判断这个颜色能不能满足要求{int i,flag=0;for(i=1;i<=s-1;i++)//分别与前面已经着色的几块比较if(G.arcs[i][s]==1&&color[i]==color[s]){flag=1;break;}return flag;void output(Graph G)//输出函数{int i;for(i=1;i<=G.vnum;i++)printf("%d ",color[i]);printf("\n");}void trycolor(int s,Graph G)//s为开始图色的顶点{int i;if(s>G.vnum)//递归出口{output(G);exit(1);}else{for(i=1;i<=N;i++)//对每一种色彩逐个测试{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//进行下一块的着色}}}d) 4 运行环境i 软件环境操作系统：Windows8ii 硬件环境处理器：Intel Pentium 166MX内存：32MB硬盘空间：1GB显卡：SVGAE) 5 开发环境I 编程环境：Dev-C++ 5.0 beta 9.2 (4.9.9.2)Ii 编程语言：C语言，ANSI C89。
f) 6 程序设计#include <stdio.h>#include <stdlib.h>#define MAXedg 100#define MAX 0#define N 4 //着色的颜色数int color[30]={0};//来存储对应块的对应颜色typedef char vextype;typedef int adjtype;typedef struct //定义图{vextype vexs[MAXedg]; //存放边的矩阵adjtype arcs[MAXedg][MAXedg]; //图的邻接矩阵int vnum,arcnum; //图的顶点数和边数}Graph;//*********************************************************** int LocateVex(Graph G,char u){int i;for(i=1;i<=G.vnum;i++){if(u==G.vexs[i])return i;}if(i==G.vnum){printf("Error u!\n");exit(1);}return 0;}//**********************************************************void CreateGraph(Graph &G) //输入图{int i,j,k, w;vextype v1,v2;printf("输入图的顶点数和边数:\n");scanf("%d%d",&G.vnum,&G.arcnum);getchar();printf("输入图的各顶点：\n");for(i=1;i<=G.vnum;i++){scanf("%c",&G.vexs[i]);getchar();}for(i=0;i<=G.vnum;i++)for(j=0;j<=G.vnum;j++)G.arcs[i][j]=MAX;printf("输入边的两个顶点和权值(均用1表示):\n");for(k=0;k<G.arcnum;k++){scanf("%c", &v1);getchar();scanf("%c", &v2);getchar();scanf("%d", &w); getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=w;}}//**************************************************************** void PrintGraph(Graph G) //输出图的信息{int i,j;printf("图的各顶点：\n");for(i=1;i<=G.vnum;i++)printf("%c ",G.vexs[i]);printf("\n");printf("图的邻接矩阵：\n");for(i=1;i<=G.vnum;i++){for(j=1;j<=G.vnum;j++)printf("%d ",G.arcs[i][j]);printf("\n");}}//****************************************************************** int colorsame(int s,Graph G)//判断这个颜色能不能满足要求{int i,flag=0;for(i=1;i<=s-1;i++)//分别与前面已经着色的几块比较if(G.arcs[i][s]==1&&color[i]==color[s]){flag=1;break;}return flag;}//****************************************************************** void output(Graph G)//输出函数{int i;for(i=1;i<=G.vnum;i++)printf("%d ",color[i]);printf("\n");}//****************************************************************** void trycolor(int s,Graph G)//s为开始图色的顶点，本算法从1开始{int i;if(s>G.vnum)//递归出口{output(G);exit(1);}else{for(i=1;i<=N;i++)//对每一种色彩逐个测试{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//进行下一块的着色}}}//*****************************************************************int main(){Graph G;CreateGraph(G);PrintGraph(G);printf("着色方案:\n");trycolor(1,G);return 0;}G) 7 调试分析1．测试中的问题举例：在测试删除联系人函数时发现无论通讯录中现存多少条记录只要删除一条之后，通讯录就会被清空，经过检查发现是删除函数中的条件控制设置有错，导致只要一删除一个联系人就会事头结点与尾结点指向同一个，导致再显示联系人时显示无联系人。
经过调整已处理好。
2．算法改进设想举例：程序中还有很多地方不能很好的模拟通讯录的功能，比如在增肌联系人时，不管原来新联系人姓名是否已存在，都会被加入通讯录，这样一来就有可能重复记录。
此外在查找联系人时只要查找到一个合法记录就会中断查找操作，如此有可能导致记录的漏查。
结合以上两点应优化增加查找联系人算法，在存入之间进行防重判断。
H) 8 测试结果由于地图上各省连接关系太多，所以这里只给出简单的测试数据，来测试该程序的功能，如下：给出如下示意图，省份抽象为点，接壤抽象为有边相连。
顶点为：a b c d e f相邻边：a-b b-c b-e b-f c-d c-e c-f e-fI ）参考文献[1]严蔚敏,《数据结构（C语言版）》清华大学出版社[2]谭浩强.《C语言程序设计》（第三版）清华大学出版社J ）心得体会通过这次数据结构的课程设计，我更进一步的了解到了C语言对编程的基础性，与数据结构思想对于一个程序编码顺利进行的重要性。
c语言是程序的骨架，而数据结构和算法便是程序的思想，要成功的编写程序必须选择好合适的数据结构。
除此之外，我觉得比较重要的一点是在编复杂程序时要有宏观思想，要从整体把握设计好各个板块的调用关系，最好先做出一个流程图，再按照这个总体设想进一步具体、细化！这样才不会在需要调用其它函数时手忙脚乱！信息科学与工程学院课程设计成绩评价表课程名称：数据结构课程设计设计题目：地图着色专业：班级：姓名：学号：。