《数据结构物流信息管理系统课程设计.doc》由会员分享，可在线阅读，更多相关《数据结构物流信息管理系统课程设计.doc（15页珍藏版）》请在金锄头文库上搜索。
1、学号2014-2015学年 第一学期1308010119数据结构课程设计报告题目：图形染色问题求解专业：计算机科学与技术班级：13级计科（1）班姓名：刘爽爽学号：1308010119指导教师：王源成绩：计算机与信息工程系二零一四年十月二十五日 / 目 录1 设计内容及要求.11.1 设计内容.11.2 设计任务及具体要求.12 概要设计.12.1 该系统的功能简介.12.2 总体程序框图.22.3 各个模块之间的主要关系.23 设计过程或程序代码.33.1 各个模块的程序流程图.33.2 对关键代码加以分析说明.54 程序调试分析.75 小结.9参考文献.9附： 源程序.10 1 设计内容及要
2、求1.1设计内容 图形染色问题是将图形的各个区域进行染色，且相邻区域所染色彩不同，该程序功能主要包括两个模块：1) 主程序模块 void main()初始化；while接受命令；处理命令； 2) 图形模块实现图形抽象数据类型模块调用关系如下： 主程序模块 地图模块1.2 设计任务及具体要求 主要利用数据结构中的图的存储结构等将图形抽象化开发一个图形染色问题的解决方案程序，应拥有输入图，输出图，并输出解决方案等功能。操作界面要符合用户的一般习惯，图形或文本界面都可以。 要求：明确课程设计的目的，能根据课程设计的要求，查阅相关文献，为完成设计准备必要的知识；提高学生用高级语言进行程序设计的能力，重
3、点提高用数据结构进行文件操作和绘图应用的编程技术水平；进一步了解软件开发的一般方法和步骤；提高撰写技术文档的能力。 2 概要设计2.1 程序的功能简介 该程序的主要功能是将图形抽象化，并实现图的输入，图的输出和输出图形染色问题的解决方案2.2 总体程序框图主程序调用LocateVex函数创建图输出图调用trycolor函数当sG.vnum时，调用output函数输出当s=G.vnum时，调用colorsame函数，判断这个颜色能不能满足要求结束开始2.3 各个板块之间的关系 该程序的功能是实现图的输入，图的输出和该图形的染色方案的输出。各个模块之间是相互联系的。首先，主函数包含了输入图，输出图
4、和染色方案的输出三个功能子函数，而这三个子函数也包含了其他子函数。主函数是整个函数的核心。子函数之间也有联系，对图的输出和图的染色方案的输出是在图的输入子函数进行后进行的，因此对图的输出和图的染色方案的输出是非常重要的。 3 设计过程或程序代码3.1 各个模板的程序流程图1)主函数Graph G;/创建一个图G=CreateGraph(G);/调用CreateGraph(G)函数，输入抽象化图形PrintGraph(G);/调用PrintGraph(G)函数，输出该图的邻接矩阵printf(本次的着色方案为:n);trycolor(1,G);/调用trycolor(1,G)函数，输出染色方案
5、包含其他子函数并对其调用，主要功能为输入抽象化图形、输出该图的邻接矩阵和输出染色方案。2) 返回u在图G中的位置函数int i;for(i=1;i=G.vnum;i+)u=G.vexsi?真假return ii=G.vnum?真假printf(Error u!n);exit(1);return 0; 此函数主要功能是返回u在图G中的位置，被CreateGraph(Graph G)调用。3) 输入图函数int i,j,k; vextype v1,v2;scanf(%d%d,&G.vnum,&G.arcnum);getchar();for(i=1;i=G.vnum;i+)scanf(%c,&G.v
6、exsi);getchar();for(i=0;i=G.vnum;i+)for(j=0;j=G.vnum;j+)G.arcsij=MAX;for(k=0;kG.arcnum;k+)scanf(%c,&v1);getchar();scanf(%c,&v2);getchar();i=Locatevex(G,v1);j=Locatevex(G,v2);G.arcsij=G.arcsji=w;return G;此函数的功能是实现图的输入，首先输入顶点和边数，建立一个初始化全为零的邻接矩阵，在输入一条边的两个顶点，调用Locatevex(Graph G,char u) 返回v1，v2在图G中的位置，在将
7、邻接矩阵中对应位置由零变为1。返回图G。4) 输出图的邻接矩阵函数int i,j;for(i=1;i=G.vnum;i+)printf(%c,G.vexsi);printf(n);for(i=1;i=G.vnum;i+)for(j=1;j=G.vnum;j+)printf(%d ,G.arcsij);printf(n);此函数的功能是将由CreateGraph(Graph G)返回的邻接矩阵G输出，从而实现对图的输出功能。5)颜色判断函数int i,flag=0;for(i=1;iG.vnum)output(G);exit(1);elsefor(i=1;iG.vnum时，跳出递归，并输出解决方
8、案。3.2 对关键代码加以分析说明 1）创建一个图typedef struct 定义图vextype vexsMAXedg;/存放边的矩阵adjtype arcsMAXedgMAXedg;/图的邻接矩阵int vnum,arcnum;/图的顶点数和边数Graph; 声明一个类型图，同时定义变量2）输入图函数Graph CreateGraph(Graph G)/输入图int i,j,k;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.vexsi); getchar();for(i=0;i=G.vnum;i+) for(j=0;j=G.vnum;j+) G.arcsij=MAX; / 将矩阵所有元素初始化为0printf(输入每条边的两个点:n);for(k=0;kG.arcnum;k+)scanf(%c,&v1);getchar();scanf(%c,&v2);getchar();i=Locatevex(G,v1); /输出v1在图中的位置j=Locatevex(G,v2); /输出v2在图中的位置G.arcsij=G.arcsji=w; /一条边的两点在矩阵中表
