数据结构物流信息管理系统课程设计

1、学号13080101192014-2015 学年 第一学期数据结构课程设计报告题目：图形染色问题求解专业：计算机科学与技术班级：13 级计科（ 1）班姓名：刘爽爽学号：1308010119指导教师：王源成绩：计算机与信息工程系二零一四年十月二十五日计算机与信息工程系数据结构课程设计报告目录1设计内容及要求 .11.1设计内容 .11.2设计任务及具体要求 .12概要设计 .12.1该系统的功能简介 .12.2总体程序框图 .22.3各个模块之间的主要关系 .23设计过程或程序代码 .33.1各个模块的程序流程图 .33.2对关键代码加以分析说明 .54程序调试分析 .75小结 .9参考文献 .

2、 .9附：源程序 .10计算机与信息工程系数据结构课程设计报告1 设计内容及要求1.1 设计内容图形染色问题是将图形的各个区域进行染色，且相邻区域所染色彩不同，该程序功能主要包括两个模块：1) 主程序模块void main()初始化；while接受命令；处理命令；2) 图形模块实现图形抽象数据类型模块调用关系如下：主程序模块地图模块1.2设计任务及具体要求主要利用数据结构中的图的存储结构等将图形抽象化开发一个图形染色问题的解决方案程序，应拥有输入图，输出图，并输出解决方案等功能。操作界面要符合用户的一般习惯，图形或文本界面都可以。要求：明确课程设计的目的，能根据课程设计的要求，查阅相关文献，为

3、完成设计准备必要的知识； 提高学生用高级语言进行程序设计的能力，重点提高用数据结构进行文件操作和绘图应用的编程技术水平；进一步了解软件开发的一般方法和步骤；提高撰写技术文档的能力。2 概要设计2.1程序的功能简介1计算机与信息工程系数据结构课程设计报告该程序的主要功能是将图形抽象化，并实现图的输入， 图的输出和输出图形染色问题的解决方案2.2总体程序框图开始主程序创建图输出图调用 trycolor 函数当 s>G.vnum 时，调用 output 函数输出调用LocateVex函当 s<=G.vnum 时，调用colorsame 函数，判断这个颜色能不能满足要求结束2.3各个板块之

4、间的关系该程序的功能是实现图的输入， 图的输出和该图形的染色方案的输出。 各个模块之间是相互联系的。 首先，主函数包含了输入图， 输出图和染色方案的输出三个功能子函数， 而这三个子函数也包含了其他子函数。 主函数是整个函数的核心。子函数之间也有联系， 对图的输出和图的染色方案的输出是在图的输入子函数进行后进行的，因此对图的输出和图的染色方案的输出是非常重要的。2计算机与信息工程系数据结构课程设计报告3 设计过程或程序代码3.1各个模板的程序流程图1) 主函数Graph G;/创建一个图G=CreateGraph(G);/调用 CreateGraph(G)函数，输入抽象化图形PrintGraph

5、(G);/调用 PrintGraph(G)函数，输出该图的邻接矩阵 printf(" 本次的着色方案为 :n");trycolor(1,G);/ 调用 trycolor(1,G) 函数，输出染色方案包含其他子函数并对其调用，主要功能为输入抽象化图形、输出该图的邻接矩阵和输出染色方案。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中的位置，

6、被 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.vexsi);getchar();for(i=0;i<=G .vnum;i+)for(j=0;j<=G .vnum;j+)G.arcsij=MAX;for(k=0;k<G .arcnum;k+)scanf("%c",&

7、amp;v1);getchar();scanf("%c",&v2);getchar();i=Locatevex(G,v1);j=Locatevex(G,v2);G.arcsij=G .arcsji=w;return G;3计算机与信息工程系数据结构课程设计报告此函数的功能是实现图的输入，首先输入顶点和边数， 建立一个初始化全为零的邻接矩阵，在输入一条边的两个顶点，调用Locatevex(Graph G,char u) 返回 v1， v2 在图 G中的位置，在将邻接矩阵中对应位置由零变为1。返回图 G。4) 输出图的邻接矩阵函数int i,j;for(i=1;i<

8、;=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;i<=s-1;i+)G.arcsis=w&&colori=colo

9、rs?真假flag=1;break;return flag;此函数的功能是判断这个颜色能不能满足要求，被 trycolor(ints,Graph G)调用，完成解决方案。6）图形涂色函数int i;if(s>G.vnum)output(G);exit(1);elsefor(i=1;i<=N;i+)colors=i;if(colorsame(s,G)=0)trycolor(s+1,G);本函数是用来实现染色方案功能，在这里应用了函数的递归，并调用colorsame(int s,Graph G)函数来进行判断这个颜色能不能满足要求，当s>G.vnum时，跳出递归，并输出解决方案。

10、4计算机与信息工程系数据结构课程设计报告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.a

11、rcnum);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;k<G.arcnum;k+)scanf("%c",&v1);getchar();5计算机与信息工

12、程系数据结构课程设计报告scanf("%c",&v2);getchar();i=Locatevex(G,v1); /输出 v1 在图中的位置j=Locatevex(G,v2); /输出 v2 在图中的位置G.arcsij=G.arcsji=w; /一条边的两点在矩阵中表示为1return G;此函数的功能是实现图的输入，首先输入顶点和边数，建立一个初始化全为零的邻接矩阵，在输入一条边的两个顶点，调用Locatevex(Graph G,char u) 返回 v1， v2 在图 G中的位置，在将邻接矩阵中对应位置由零变为1。返回图 G。3）输出图的邻接矩阵函数void

13、PrintGraph(Graph G)int i,j;printf("此图的顶点为 :n");for(i=1;i<=G.vnum;i+)printf("%c",G.vexsi); /输出顶点printf("n");printf("此图的邻接矩阵为 :n");for(i=1;i<=G.vnum;i+)for(j=1;j<=G.vnum;j+)printf("%d ",G.arcsij); / 输出邻接矩阵 printf("n");此函数的功能是将由Create

14、Graph(Graph G)返回的邻接矩阵G输出，从而实现对图的输出功能。用户可以对应抽象化图形判断是否出错。6计算机与信息工程系数据结构课程设计报告4）图形涂色函数void trycolor(int s,Graph G) /s为开始图色的顶点，本算法从1 开始int i;if(s>G.vnum)/递归出口output(G);exit(1);elsefor(i=1;i<=N;i+) /对每一种色彩逐个测试colors=i;if(colorsame(s,G)=0)trycolor(s+1,G); /进行下一块的着色本函数是用来实现染色方案功能，在这里应用了函数的递归，并调用color

15、same(int s,Graph G)函数来进行判断这个颜色能不能满足要求，当s>G.vnum时，跳出递归，并输出解决方案。4 设计结果与分析如下图，为一图形的抽象化连接图，顶点为ABCDEFG，相邻边为： AB AF BCBE BF CD CE CF DE EF EG FG，现有四种颜色，四种颜色分别对应1，2，3，4，在图形的各个区域进行染色， 且相邻的区域所染的颜色不能相同。由该问题来实验程序功能。ABDFCEG7计算机与信息工程系数据结构课程设计报告实验结果如下：ABDFCEG由解决方案对其染色， 可以得到上图， 显然程序的功能可以实现解决图形染色问题。8计算机与信息工程系数据结

16、构课程设计报告5 小结本次课程设计所选题目是“图形染色问题求解” ，在本次数据结构课程设计的过程，我先是将数据结构的一些内容有再次复习了一遍， 然后就是对着电脑不停的分析问题解决问题写代码实验， 不然就是去图书馆或者网上翻阅资料、 问老师同学。因为对图的基础知识不太牢固， 出现了很多问题。 也让我体会到只有专业知识过硬基础扎牢，在设计的时候做到够细心和够耐心才能设计好程序。此次数据结构设计实验的目的不仅仅加强了我们的动手能力， 思考能力和解决问题的能力， 也让我认识到理论和实际的差别， 学会了怎样查阅资料， 怎样把理论与实际相结合， 在此次课程设计充分的认识到了自己的不足， 构思也借鉴了许多网

17、上资料，调试也遇到了很多的低级错误，像定义错误，丢符号等等，最终还是完成了自己所选的设计题目， 也积累了很多的实战经验， 为以后的学习打下了良好的基础，也真正的认识了自己的知识水平。参考文献【 1】数据结构（C语言版），严蔚敏，清华大学出版社， 2003.【 2】数据结构题集（C语言版），严蔚敏，清华大学出版社， 2005.【 3】数据结构（C语言版），刘大有，高等教育出版社， 2004.【 4】Data Structure with C+ , William Ford.William Topp,清华大学出版社， 2003.9计算机与信息工程系数据结构课程设计报告附：源程序#include&l

18、t;stdio.h>#include<stdlib.h>#define MAX 0#define MAXedg 100#define N 4/着色的颜色数#define w 1/两点之间的权值int color30=0; /来存储对应块的对应颜色typedef char vextype;typedef int adjtype;typedef struct定义图vextype vexsMAXedg;/存放边的矩阵adjtype arcsMAXedgMAXedg;/图的邻接矩阵int vnum,arcnum;/图的顶点数和边数Graph;int Locatevex(Graph G

19、,char u)/返回 u 在图 G中的位置int i;for(i=1;i<=G.vnum;i+)if(u=G.vexsi)return i;if(i=G.vnum)10计算机与信息工程系数据结构课程设计报告printf("Error u!n");exit(1);return 0;Graph CreateGraph(Graph G)/输入图int i,j,k;vextype v1,v2;printf("依次输入顶点数和边数:n");scanf("%d%d",&G.vnum,&G.arcnum);getchar()

20、;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;k<G.arcnum;k+)scanf("%c",&v1);getchar();scanf("%c",&

21、v2);getchar();i=Locatevex(G,v1);/输出 v1在图中的位置j=Locatevex(G,v2);/输出 v2在图中的位置G.arcsij=G.arcsji=w;/一条边的两点在矩阵中表示为 111计算机与信息工程系数据结构课程设计报告return G;void PrintGraph(Graph G)/输出图的信息int i,j;printf("此图的顶点为 :n");for(i=1;i<=G.vnum;i+)printf("%c",G.vexsi); /输出顶点printf("n");printf("此图的邻接矩阵为:n");for(i=1;i<=G.vnum;i+)for(j=1;j<=G.vnum;j+)pr