数据结构课程设计报告3.doc

课程设计报告题目:在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。一、需求分析1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。1.4程序通过人机交互实现数据的输入和输出。1.5测试数据 （a,b）:2 ; (a,c):3; (a,d):4; (c,d):4; (b,d):5二、概要设计程序分为两大部分存储部分和算法部分；存储部分分为邻接矩阵和邻接表，而且包含了两者直接的互相转换；算法部分分为普里母算法和克鲁斯卡尔算法。1.抽象数据类型图的定义如下adt graph数据对象v;v是具有相同特性的数据元素的集合，成为顶点集。数据关系r： r = vrvr = （v,w）|v,w为v集合中的元素，（v,w）表示v和w之间存在的路径基本操作p;createmgraph(mgraph *g)初始条件：v是图的顶点集，vr是图的边的集合。操作结果：按v和vr的定义构造图g，用邻接矩阵存储。createalgraph(algraph *g)初始条件：v是图的顶点集，vr是图的边的集合。操作结果：按v和vr的定义构造图g，用邻接表存储。locatevex（g，u）初始条件：图g存在，u和g中顶点有相同的特征。操作结果：若g中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。minispantree_prim（g, u)初始条件：图g存在，u是图g中的一个顶点。操作结果：用普利姆算法从第u个顶点出发构造网g的最小生成树t，输出t的各条边。kriuskal(g)初始条件：图g存在操作结果：用克鲁斯卡尔算法构造图g的最小生成树t，输出t的各条边。listtomat(mgraph *g1,algraph *g2)初始条件：图g2存在操作结果：把图的邻接表存储结构转换为邻接矩阵存储结构，用图g1表示。mattolist(mgraph *g1,algraph *g2)初始条件：图g1存在操作结果：把图的邻接矩阵存储结构转换为邻接表存储结构，用图g2表示。locatevex(mgraph *g,vertextype u)初始条件：图g存在，u和g中顶点有相同特征操作结果：若g中存在顶点u，则返回该顶点在图中位置；否则返回-1adt graph2.主程序 void main()创建图g，并按不同的存储结构输出。对图的存储结构进行转换使用算法构造最小生成树并输出各边3.模块间的调用关系主模块子模块 三、详细设计1.图和顶点的定义#define ok 1#define error 0#define ture 1#define false 0#define overflow -1#define infeasible -2typedef int status;#define infinity 32767 /两地之间没有架设线路的权值为最大数。#define max_vertex_num 20 /城市的数目最大为20#define max_name 5/城市名称的最大长度为5typedef char vertextypemax_name;/城市的名称用字符数组存储typedef int vrtype; /两城市间的关系类型1.1邻接矩阵存储表示的图的结构体类型的定义typedef struct arccell vrtype adj; /*顶点关系类型。对无权图，用1（是）或0(否）表示相邻否*/ /*对带权全图，则为权值类型*/ arccell,adjmatrixmax_vertex_nummax_vertex_num;typedef struct vertextype vexsmax_vertex_num; /*顶点向量*/ adjmatrix arcs; /*邻接矩阵*/ int vexnum,arcnum; /*图的当前顶点数和弧数*/ mgraph; 1.2邻接表类型存储表示的图的结构体类型的定义 typedef struct anode /* 弧的结点结构类型 */ int end; /弧尾在邻接表头结点中的位置 int begin; /弧头在邻接表头结点中的位置 int weight; /* 该弧的相关信息,这里用于存放权值 */ struct anode *nextarc; /* 指向下一条弧的指针 */ anode;typedef struct vnode /* 邻接表头结点的类型 */ vertextype vertex; /* 顶点信息，城市名称 */ int bianhao; /城市在邻接表头结点数组中的相应编号 anode *firstarc; /* 指向第一条弧 */ vnode,adjlistmax_vertex_num; /* adjlist是邻接表类型 */typedef struct adjlist adjlist; /* 邻接表 */ int vexnum,arcnum; /* 图中顶点数n和边数e */ algraph; 2.prim算法的思想假设v是图中顶点的集合,e是图中边的集合,te为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树: （1）初始化:u=u 0,te=f。此步骤设立一个只有结点u 0的结点集u和一个空的边集te作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。 （2）在所有uu,vvu的边(u,v)e中,找一条权最小的边(u 0,v 0)，将此边加进集合te中，并将此边的非u中顶点加入u中。此步骤的功能是在边集e中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合u和vu中,其次边的权要最小。找到这条边以后,把这条边放到边集te中,并把这条边上不在u中的那个顶点加入到u中。这一步骤在算法中应执行多次,每执行一次,集合te和u都将发生变化,分别增加一条边和一个顶点,因此,te和u是两个动态的集合,这一点在理解算法时要密切注意。 （3）如果u=v,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当u=v时,步骤2共执行了n1次(设n为图中顶点的数目),te中也增加了n1条边,这n1条边就是需要求出的最小生成树的边。prim算法假设网中有n个顶点，则第一个进行初始化的循环语句频度为n，第二个循环语句的频度为n-1。其中有两个内循环；由此普里母算法的时间复杂度为o(n2),与网中的边数无关！3.克鲁斯卡尔算法的思想为假设 wn=(v,e) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：（1）先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。（2）从网的边集 e 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。（3）依次类推，重复上述操作，直至森林中只有一棵树，也即子图中含有 n-1条边为止。克鲁斯卡尔算法至多对e条边各扫描一次时间复杂度为o（eloge）。4.编写程序使用到的函数为 (a)程序中用来实现邻接矩阵和邻接表存储、输出以及互相转化的函数status initalgraph(algraph *g)/初始化邻接表void createalgraph(algraph *g)/创建邻接表status initmgraph(mgraph *g)/初始化邻接表status createmgraph(mgraph *g)/创建邻接表status mattolist(mgraph *g1,algraph *g2)/将邻接矩阵g1转换成邻接表g2status listtomat(mgraph *g1,algraph *g2)/将邻接表g1转换成邻接矩阵g2status printmgraph(mgraph *g)/输出邻接矩阵gstatus printalgraph(algraph *g)/输出邻接表g(b)程序中用来完成prim和kriuskal算法的函数int mininum(minside closedge,mgraph *g)/ 求closedege数组中lowcost的最小正值void minispantree_prim(mgraph *g,vertextype u)/ 用普利姆算法从第u个顶点出发构造网g的最小生成树t，输出t的各条边void insertsort(edgetype e,int n)/对e0.n-1按权值递增有序的进行直接插入排序void kriuskal(algraph *g)/克鲁斯卡尔算法(c) 查找顶点u在图中的位置int locatevex(mgraph *g,vertextype u)/查找顶点u在图中的位置5.主函数模块为：void main()定义邻接矩阵存储结构的图；定义邻接表存储结构的图；选择一种存储结构画出图，并输出；邻接矩阵和邻接表相互转化，得到两种类型的存储图，并输出转换后的图；选择一种算法得到最小生成树并输出生成树的各边。6.模块间的调用层次main()void createalgraph(algraph *g)status createmgraph(mgraph *g)status mattolist(mgraph *g1,algraph *g2)status listtomat(mgraph *g1,algraph *g2)void minispantree_prim(mgraph *g,vertextype u)void kriuskal(algraph *g)status initalgraph(algraph *g)status initmgraph(mgraph *g)status printmgraph(mgraph *g)status printalgraph(algraph *g)int mininum(minside closedge,mgraph *g)void insertsort(edgetype e,int n)int locatevex(mgraph *g,vertextype u) 四、编码与测试这个阶段主要是对代码的编写及代码正确性的检验。通过前面的详细设计的分析，这个阶段是完成各个函数的功能，在编程的过程中出现了许多的错误，导致功能的无法实现，出现的错误主要有及心的：1.对于结构体的成员的调用 心得：结构体变量名调用函数时使用符号.,对于结构体指针使用符号-或者是先使用*取得变量名在使用.调用成员。2.函数调用时指针的传递 心得：这个主要是c+与c语言的区别，在c+中函数的参数中有&，表示该变量为返回值数据，而在c语言中，据我所学确没有这样的用法。3.非法字符的使用 心的：非法字符的使用往往让人很难找到错误，而且win-tc环境给出的提示往往是错误的。产生这种错误的原因是汉语的标识符的出现，往后要注意了。4.字符串的输入及输出心的：对于字符串的输入输出都应使用取地址符号。5数据的输入心的：数据的输入可以使用空格符或取地址符号，但是空格符的输入常常容易发生错误，最好使用换行符。6.程序的输出出现错误的数据心的：程序总是会莫名奇妙的输出错误的信息，有时候输出是错误的，有时候是正确的，很奇怪，建议以后出现这类型情况时先看代码，若没有错误，那就等会再运行一边。7.命令行的消失心的：有时候在输入数据的过程中，命令行就会突然消失，在同学的建议下加了getchar（）；语句就不出现这类情况了，不明白是为什么。8.命令行重复输出相同的数据心的：这种情况很有可能是出现了死循环，这不仅发生在循环语句的情况下，对于结点指针的指向也会导致是循环。五、综合测试综合测试其实是对程序的总体测试，但在编码阶段已经对语句的进行了测试，在总体测试阶段多采用几组数据，在编码阶段的数据可以简单一些，但在综合测试阶段要用使用比较复杂的数据，可以检测到在编码阶段不宜发现的错误。在综合测试阶段发现的错误：对于邻接表的指针的取向。测试数据：（a,b）:2 ; (a,c):3; (a,d):4; (c,d):4; (b,d):5采用邻接表存储的输入及邻接表转换为邻接矩阵并显示通过prim算法显示最小生成树的各边采用邻接矩阵存储的输入邻接矩阵转换为邻接表并显示及通过prim算法显示最小生成树的各边通过kruskal算法显示最小生成数的各边六、课程总结认识： 对于编程，假期一个月的学习里，我已经有了很深刻的体会，搭建框架是十分必要的，只有有了框架才能在具体实现上一步一步的完成。通过这次的课程设计，不仅让我提高了编写程序的能力，同时也让我对大学所学课本的知识有了更好的这学期，我学习了软件工程导论，这门课程主要是对编写软件过程的顺序的介绍，不同的阶段应该完成什么样的任务。按着书上的步骤一步步完成，确实很节省时间。数据结构对于建立n地最小生成树问题是将数据结构的知识运用于实现现实问题，在程序设计过程中对于我来说十分繁杂，在具体实现算法是出现了问题：例如prim算法实现的时候没有办法记录起始点，再输出边的过程中出现错误，经过上网查阅资料才建立了数组将其解决。再调试程序过程中也是相当繁琐，代码写完了但是运行过程中出现了很多错误。编写程序是一件幸苦但又愉快的过程，在学完c语言是并没有什么太多的算法思想，但数据结构给了我很多灵感，有了数据结构的思想很多实际问题就能解决了，主要由于代码接触太少，所以在有了思想的情况下很难实现代码，以后要经常去用代码实现自己的想法，算法对于程序设计十分重要，数据结构可以说是编程者的大脑，没有数据结构代码就失去了运用于实际问题的能力。心得：在课程设计的过程中收获很多，独立思考是我首先觉悟到的，因为起初在看到繁杂的代码满脑子只有愤怒，自己根本没有办法实现，可后来在经过上网查阅思想和数据结构书我才慢慢的有了自己的想法。最后渐渐的喜欢上了代码，课程设计的确让我有一种成为编程人员的感觉了，经过努力我终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的做小生成树问题，深刻的体会到它的实用性。通过本次课程设计我们发现我们对于c语言和数据结构还有很多地方不知道，今后需要努力学习。-参考文献：1 李云清，杨庆红.数据结构（c语言版）.北京：人民邮电出版社，2004.2 严蔚敏,吴伟民.数据结构（c语言版）.北京：清华大学出版.1997.3 苏光奎,李春葆.数据结构导学.北京:清华大学出版.2002. 4 周海英，马巧梅，靳雁霞.数据结构与算法设计.北京：国防工业出版社，2007.5 张海藩. 软件工程导论. 北京：清华大学出版社.2003.6互联网附录：程序清单#include #include #define ok 1#define error 0#define ture 1#define false 0#define overflow -1#define infeasible -2typedef int status;#define infinity 32767#define max_vertex_num 20#define max_name 5typedef char vertextypemax_name;typedef int vrtype;typedef struct arccell vrtype adj; /*顶点关系类型。对无权图，用1（是）或0(否）表示相邻否*/ /*对带权全图，则为权值类型*/ arccell,adjmatrixmax_vertex_nummax_vertex_num;typedef struct vertextype vexsmax_vertex_num; /*顶点向量*/ adjmatrix arcs; /*邻接矩阵*/ int vexnum,arcnum; /*图的当前顶点数和弧数*/ mgraph; /* 以下定义邻接表类型 */typedef struct anode /* 弧的结点结构类型 */ int end; int begin; /* 该弧的终点位置 */ int weight; /* 该弧的相关信息,这里用于存放权值 */ struct anode *nextarc; /* 指向下一条弧的指针 */ anode;typedef struct vnode /* 邻接表头结点的类型 */ vertextype vertex; /* 顶点信息 */ int bianhao; anode *firstarc; /* 指向第一条弧 */ vnode,adjlistmax_vertex_num; /* adjlist是邻接表类型 */typedef struct adjlist adjlist; /* 邻接表 */ int vexnum,arcnum; /* 图中顶点数n和边数e */ algraph; /* 图的邻接表类型 */int locatevex(mgraph *g,vertextype u) /*初始条件：图g存在，u和g中顶点有相同特征*/ /*操作结果：若g中存在顶点u，则返回该顶点在图中位置；否则返回-1*/ int i; for(i=0;ivexnum;+i) if(strcmp(u,g-vexsi)=0) return i; return -1;/* 建立无向图的邻接表算法 */status initalgraph(algraph *g) int i ; printf(请输入城市的数量及城市间的路径数目n); scanf(%d%d,&g-vexnum,&g-arcnum); for(i=0;i vexnum;i+) /* 建立顶点表 */ printf(请输入第%d个城市的名称n,i); scanf(%s,&g-adjlisti.vertex); /* 读入顶点信息 */ g-adjlisti.firstarc=null;/* 边表置为空表 */ g-adjlisti.bianhao = i; printf(每个城市所对应的序号为n); for(i = 0;ivexnum;i+) printf(%d-%s ,i,&g-adjlisti.vertex); return ok;status printalgraph(algraph *g) int i,end,begin,weight; anode *s; for(i=0;ivexnum;i+)/* 建立顶点表 */ printf(%s -,&g-adjlisti.vertex); s = g-adjlisti.firstarc; while(s!=null) printf( %s,%s ):%d ,&g-adjlists-end.vertex,&g-adjlists-begin.vertex,s-weight); s = s-nextarc; printf(n); return ok;void createalgraph(algraph *g) int i,j,k,weight; anode *s; initalgraph (g); for(k=0;k arcnum;k+) /* 建立边表 */ printf(请输入第%d条边的两个城市的编号及路径的架设费用n,k); scanf(%d,&i); scanf(%d,&j); scanf( %d,&weight);/* 读入边(vi，vj)的顶点对序号 */ s=( anode *)malloc(sizeof(anode); /* 生成边表结点 */ if(!s) printf(申请空间失败!n); exit(overflow); s- begin=j; /* 邻接点序号为j */ s-end = i; s-weight = weight; s-nextarc= g-adjlisti.firstarc; g-adjlisti.firstarc=s; /* 将新结点*s插入顶点vi的边表头部 */ s=(anode*)malloc(sizeof(anode); if(!s) printf(申请空间失败!n); exit(overflow); s- begin=i; /* 邻接点序号为i */ s-end = j; s-weight = weight; s-nextarc=g-adjlistj.firstarc; g-adjlistj.firstarc=s; /* 将新结点*s插入顶点vj的边表头部 */ printalgraph(g);/* createalgraph */status printmgraph(mgraph *g) int a; int i,j; printf( ); for(i=0;ivexnum;+i) printf( %s ,&g-vexsi); printf(n); for ( i=0; ivexnum; i+) printf( %s ,&g-vexsi); for ( j=0; jvexnum; j+) printf( %5d ,g-arcsij.adj); printf(n); return ok;status initmgraph(mgraph *g) int i,j; printf(请输入城市的数量及城市间的路径数目n); scanf(%d%d,&g-vexnum,&g-arcnum); printf(n请依次输入城市的名称，字符串类型n); for(i=0;ivexnum;+i) /*构造顶点向量*/ scanf(%s,&g-vexsi); for(i=0;ivexnum;+i) /*初始化邻接矩阵*/ for(j=0;jvexnum;+j) g-arcsij.adj=infinity; return ok;status createmgraph(mgraph *g)/*采用数组（邻接矩阵）表示法，构造无向网g*/ int i,j,k,weight,incinfo; vertextype va,vb; initmgraph(g); for(k=0;karcnum;+k) printf(请输入第%d条路径的起点城市和终点城市的名称及路径的架设费用n,k); scanf(%s %s %d,&va,&vb,&weight); i=locatevex(g,va); j=locatevex(g,vb); g-arcsij.adj=weight; g-arcsji.adj=weight; printmgraph(g); return ok;typedef struct/*记录从顶点集u到v-u的代价最小的边的辅助数组定义*/ vertextype adjvex; vrtype lowcost;minsidemax_vertex_num;int mininum(minside closedge,mgraph *g)/*求closedege,lowcost的最小正值*/ int i=0,j,k,min; while(!closedgei.lowcost) i+; min=closedgei.lowcost; k=i; for(j=i+1;jvexnum;j+) if(closedgej.lowcost0) if(minclosedgej.lowcost) min=closedgej.lowcost; k=j; return k;void minispantree_prim(mgraph *g,vertextype u)/*用普利姆算法从第u个顶点出发构造网g的最小生成树t，输出t的各条边*/ int i,j,k; int qidian,zhongdian,weight; vertextype va,vb; minside closedge; k=locatevex(g,u); for(j=0;jvexnum;+j) /*辅助数组初始化*/ if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=g-arcskj.adj; closedgek.lowcost=0; /*初始u=u*/ printf(最小代价生成树的各条边为:n); for(i=1;ivexnum;+i) /*选择其余g.vexnum-1个顶点*/ k=mininum(closedge,g); /*求出t的下一个结点：第k顶点*/ strcpy( va,closedgek.adjvex); strcpy(vb ,g-vexsk); qidian=locatevex(g,va); zhongdian=locatevex(g,vb); weight = g-arcsqidianzhongdian.adj; printf(weight(%s,%s)=%dn,va,vb,weight); /*输出生成树的边*/ closedgek.lowcost=0; /*第k顶点并入u集*/ for(j=0;jvexnum;+j) if(g-arcskj.adjvexsk); closedgej.lowcost=g-arcskj.adj; void insertsort(anode *e,int n)/* 对e0.n-1按权值递增有序的进行直接插入排序 */ int i,j; anode temp; for(i=1;i=0&temp.weightvexnum; e=(struct anode*)malloc(n*sizeof(struct anode); k=0; for(i=0;ivexnum;i+) /* 将各边存到e0.n数组中 */ for(j=0;jvexnum;j+) s = g-adjlisti.firstarc; while(s!=null) (e+k)-end = s-end; (e+k)-begin = s-begin; (e+k)-weight = s-weight ; s = s-nextarc; k+; insertsort(e,k); /* 对e数组按w递增排序 */ for(i=0;ivexnum;i+) vseti=i; /* 初始化辅助数组 */ k=1; j=0; while(kvexnum) /* 生成的边数小于n时循环 */ end=(e+j)-end; begin=(e+j)-begin; /* 取一条边的头尾顶点 */ sn1=vsetend; sn2=vsetbegin;/* 分别得到两个顶点所属的集合编号 */ if(sn1!=sn2) /* 两顶点属不同集合，则该边是最小生成树的一条边 */ printf( weight(%s %s) : %dn,&(g-adjlistend.vertex),&(g-adjlistbegin.vertex),(e+j)-weight); k+; /* 生成边数增1 */ for(i=0;in;i+)/* 两个集合统一编号 */ if(vseti=sn2) vseti=sn1; j+; /* 扫描下一条边 */ status selectsavestructure() int c; printf(请选择一种算法存储无向图n); printf(*n); printf( #邻接矩阵: 1 #邻接表: 2n); printf(*n); printf(请按键选择: ); while(1) scanf(%d,&c); if(c=1|c=2) break; else printf(输入的数字不符合要求，请从新输入n); getchar(); return c;status selectsuanfa() int c; printf(请选择一种算法构建最小生成树n); printf(*n); printf( #普里姆算法（prim）: 1 #和克鲁斯卡尔算法（kruskal）: 2n); printf(*n); printf(请按键选择: ); while(1) scanf(%d,&c); if(c=1|c=2) break; else printf(输入的数字不符合要求，请从新输入n); getchar(); return c;status listtomat(mgraph *g1,algraph