数据结构课程设计报告

PAGEPAGE13淮阴工学院数据结构课程设计报告选题名称:无向图应用问题系（院）:计算机工程学院专业: 计算机科学与技术 班级:网络1111姓名:1111311105指导教师:周海岩单劲松 学年学期: 2012~2013学年第1学期 2012 年12 月20 日

设计任务书课题名称无向图应用问题设计目的1．掌握关键数据结构，如线性表、树、图建立过程及操作算法；2．掌握常用算法的实现方法及作用；3．理解利用数据结构及算法解决实际问题的思想；4．学会资料收集与整理方法，学会撰写实习报告；5．学会对所学知识进行总结，加深对课堂知识的理解与掌握。实验环境1．Windows2000以上操作系统；2．C++，C#或Java编程工具。任务要求1．利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理；2．在第15周末之前完成预设计，请指导教师审查通过后进行下一步工作；3．按所设计方案进行软设计；4．完成系统设计，写出报告初稿方可申请参加答辩；5．结束后，及时提交实习报告（含纸质稿、电子稿）。工作进度计划序号起止日期工作内容12012.11.12~2012.11.25查阅资料，提出设计方案。22012.11.26~2012.12.8根据提出设计方案逐项完成。32012.12.24~2012.12.30在机房实现软件系统、系统调试。42013.1.3~2013.1.6根据教师反馈意见，修改、完善、上交实习报告。指导教师：2012年11月10日摘要：本课程设计是设计的关于无向图应用问题的课程。通过此课程，我们可以解决n个城市间设计通信网络，使其造价最低。以及当其造价最低的时候我们应该怎样设计。本课程实际是通过应用Prim算法来求最小生成树。将n个城市和各边的权值建立成邻接矩阵，再应用Prim算法就能完成。关键词：Prim算法；邻接矩阵；最小生成树；无向图

目录TOC\o"1-2"\h\z1需求分析 131需求分析 131.1课程设计题目 131.2课程设计任务 131.3课程设计思想 132概要设计 132.1本课程设计的总体结构 133详细设计和实现 133.1源代码 133.2算法流程图 133.3模块的功能描述 133.4算法原理 133.5程序运行截图 13总 结 13致 谢 13参考文献 13

1需求分析1.1课程设计题目无向图应用问题1.2课程设计任务如果以无向网表示n个城市之间通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通讯网的总造价最低。1.3课程设计思想本课程设计主要应用如何生成最小生成树，以及Prim算法。2概要设计2.1本课程设计的总体结构本课程设计的总体结构分为4个部分。2.1.1第1部分设定了城市数目为5，并且设定了每条边的权值。2.1.2第2部分设计了一个Prim函数。并且通过Prim算法来求最小生成树。而Prim算法的具体实现步骤：1：初始化：U={u0},TE={f}。此步骤设立一个只有结点u0的结点集U和一个空的边集TE作为最小生成树的初始形态，在随后的算法执行中，这个形态会不断的发生变化，直到得到最小生成树为止。2：在所有u∈U,v∈V－U的边（u,v）∈E中，找一条权最小的边（u0,v0），将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边，要求这条边满足以下条件：首先边的两个顶点要分别在顶点集合U和V－U中，其次边的权要最小。找到这条边以后，把这条边放到边集TE中，并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次，每执行一次，集合TE和U都将发生变化，分别增加一条边和一个顶点，因此，TE和U是两个动态的集合，这一点在理解算法时要密切注意。3：如果U=V，则算法结束；否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时，步骤2共执行了n－1次（设n为图中顶点的数目），TE中也增加了n－1条边，这n－1条边就是需要求出的最小生成树的边。2.1.3第3部分设计了一个creatlist函数。该函数可以用来得出当是最小生成树的时候的排列顺序。2.1.4第4部分设计了一个main()函数。该函数用来对整个课程设计进行运行。它调用了Prim算法和creatlist函数。对5个城市的通信网络建立邻接矩阵然后对运用Prim算法，再调用creatlist()函数，将最小生成树时的排列进行输出。3详细设计和实现3.1源代码#include<stdio.h>#include<iostream>#definen5#definemax1000.0typedefstructnode{ intno; floatwgt; structnode*next;}edgenode;typedefstruct{ charvtx; edgenode*link;}vexnode;floatgali[n][n]={{0,2,12,10,max},{2,0,8,max,9},{12,8,0,6,3},{10,max,6,0,7},{max,9,3,7,0}};typedefvexnodeGraph[n];GraphG;voidprim(vexnodeG[],intk){ intv2link[n],vset[n],parent[n],w[n]; edgenode*ptr; intx,s,ecount,i,y,z,f; s=-1; x=k; vset[k]=-1; v2link[n]=-1; ecount=0; for(i=0;i<n;i++) if(i!=k) vset[i]=3; while(ecount<n-1) { ptr=G[x].link; while(ptr!=NULL) { y=ptr->no; if((vset[y]==2)&&(ptr->wgt<w[y])) { parent[y]=x; w[y]=ptr->wgt; } if(vset[y]==3) { vset[y]=2; v2link[y]=s; s=y; parent[y]=x; w[y]=ptr->wgt; } ptr=ptr->next; } if(s==-1) break; z=x=s; y=v2link[x]; f=-1; while(y!=-1) { if(w[y]<w[x]) { x=y; f=z; } z=y; y=v2link[y]; } if(f==-1) s=v2link[x]; else v2link[f]=v2link[x]; vset[x]=1; ecount++; } printf("\nroot%c:\t",G[k].vtx); for(i=0;i<n;i++) { if(i!=k) { printf("%c",G[i].vtx); f=parent[i]; printf("%c\t",G[f].vtx); } }}voidcreatlist(vexnodega[]){ inti,j; edgenode*se; for(i=0;i<n;i++) { ga[i].vtx='a'+i; for(j=0;j<n;j++) { if((gali[i][j]<max)&&(gali[i][j]!=0)) { se=(edgenode*)malloc(sizeof(*se)); se->no=j; se->next=ga[i].link; se->wgt=gali[i][j]; ga[i].link=se; } } }}main(){ inti; edgenode*ve; creatlist(G); for(i=0;i<n;i++) { printf("\nv%c=link:",G[i].vtx); ve=G[i].link; while(ve!=NULL) { printf("%dw=%.2f\t",ve->no,ve->wgt);ve=ve->next; } } prim(G,4); return0;开始Prim算法开始Prim算法Creatlist函数Main()函数调用Prim()调用creatlist()输出结果及安排结束3.2算法流程图3.3模块的功能描述Prim算法的功能描述：Prim算法是用来求出最小生成树。Creatlist()函数的功能描述：creatlist()函数可以将Prim算法求出来的最小生成树进行输出。Main()函数的功能描述：main()函数是该程序的主函数，它先对Prim算法进行调用，将5个城市及其边的权值进行最小生成树的生成，然后再调用了creatliast()函数，运用creatlist()函数，将Prim算法求出的最小生成树输出。3.4算法原理Prim算法的基本思想：假设G=（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取V0），将它并入U中，此时U={V0}，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（i,j），其中Vi∈U,Vj∈(V-U),并把该边（i,j）和顶点j分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组closedge[]，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每个最小生成树。而在Prim算法中需要解决2个问题①在无向网中，当出现从一个顶点到其它顶点时，若其边上的权值相等，则可能从某一起点出发时会得出不同的最小生成树，但最小生成树的权必定都相等，此时我们应该怎样将所有的最小生成树求解出来；②每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次（1≤k≤n-1）前，生成树T中已有k个顶点和k-1条边，此时T中到T外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相联，其权值被看做常量INFINIT的边在内，从如此多的边中查找最短边，其时间复杂度为O(k(n-k))，显然是很费时的，是否有一种好的方法能够降低查找最短边的时间复杂度。而针对这2个问题其解决方法如下：针对①中出现的问题可以通过在算法中实现，详情请看PRIM算法的基本思想；针对②中出现的问题，通过对PRIM算法的分析，可以使查找最短边的时间复杂度降低到O(n-k)。具体方法是假定在进行第k次前已经保留着从T中到T外的每一顶点（共n-k个顶点）的各一条最短边，进行第k次时，首先从这n-k条最短边中，找出一条最最短的边，它就是从T中到T外的所有边中的最短边，假设为（i,j），此步需进行n-k次比较；然后把边（i,j）和顶点j分别并入T中的边集TE和顶点集U中，此时T外只有n-(k+1)个顶点，对于其中的每个顶点t，若（j,t）边上的权值小于已保留的从原T中到顶点t的最短边的权值，则用（j,t）修改之，使从T中到T外顶点t的最短边为（j,t），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点t的各一条最短边都保留下来了，为进行第k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。3.5程序运行截图

总 结在这次课程设计中，感觉自己学到了不少知识，以往在上机实验过程中，书上总有相关的代码可以让我们参考，但是在这次课程设计中，是要独立的设计出一个真正的程序，在开始的时候我们使用了上学期C++所学到的关于文本输入输出的程序，但是在和同伴的讨论过程中，发现仅仅只是输入输出流的应用，并没有数据结构中的知识，所以我们就否定了原来的程序，重新做了这个程序，在这个程序中使用了链表存储相关信息，在编写程序中，动手能力得到了很大的提高，同时对链表的知识得到了很大的巩固。在编写过程中，遇到了很多的问题，比如开始的时候算法不正确，后来的编写程序中对程序函数不能正确认识，但是在后来查阅资料和与同伴讨论中，很多的问题都得到了良好的解决。总之，这次的课程设计对我来说是受益匪浅。对于此次数据结构课程设计来说，我觉的我最大的收获就是学会了如何使用最小生成树以及Prim算法的基本原理及其应用。让我理解了Prim算法是不断迭代进行的。此算法的精妙之处在于对求权值最小的边这一问题的分解（也正是由于这种分解，而导致了算法理解上的困难）。按照常规的思路，这一问题应该这样解决：分别从集合V－U和U中取一顶点，从邻接矩阵中找到这两个顶点行成的边的权值，设V－U中有m个顶点，U中有n个顶点，则需要找到m*n个权值，在这m*n个权值中，再查找权最小的边。循环每执行一次，这一过程都应重复一次，相对来说计算量比较大。而本算法则利用了变量tree中第k+1到第n－1号元素来存放到上一循环为止的一些比较结果，如以第k+1号元素为例，其存放的是集合U中某一顶点到顶点tree.en的边，这条边是到该点的所有边中权值最小的边，所以，求权最小的边这一问题，通过比较第k+1号到第n－1号元素的权的大小就可