数据结构课程设计12440

1、成 绩 评 定 表学生姓名冯有礼班级学号1009010118专 业信息与计算科学课程设计题目1.最小生成树解决城市联络网建设问题2.线性表的插入,删除,添加。评语组长签字：成绩日期 20 年 月 日课程设计任务书学 院理学院专 业信息与计算科学学生姓名冯有礼班级学号1009010118课程设计题目1.最小生成树解决城市联络网建设问题2.线性表的插入,删除,添加。实践教学要求与任务:1、巩固和加深对数据结构基本知识的理解。2、初步掌握简单软件的分析方法和设计方法。3、了解与课程有关的工程技术规范，能正确解释和分析设计结果。4、具体任务（1）最小生成树解决城市联络网建设问题（2）线性表的插入,删除

2、,添加。工作计划与进度安排:第一天 查阅资相关料； 第二、三天 程序设计； 第四程序调试； 第五天天 答辩指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘 要“数据结构”是有关计算技术及信息管理技术专业的一门必修的核心课程。数据结构课程的任务实在讨论在应用问题求解时数据的逻辑组织、在计算机中的存储实现以及相关操作的算法设计。数据结构课程目的是使学生掌握在实际问题解决过程中组织数据、存储数据和处理数据的基本方法，为以后从事软件开发和应用，为进一步学习后续课程打下坚实的基础。本文第一个问题是针对随着现代网络的高速发展，从成本角度出发，要求所假设的光缆

3、长度最短，故而采用最小生成树来建模此问题。本文给出了一个城市间光缆假设的场景，采用prim算法、kruskal算法两种算法解决该城市间光缆假设问题，并通过实验仿真分别实现这两种算法，得到了城市联络网建设的最佳解决方案。本文第二个问题是根据本学期对数据结构中线性表的学习，编写了一个程序，完成线性表的插入，删除，和查找功能。关键词：最小生成树；prim算法；kruskal算法；线性表目 录1.最小生成树解决城市联络网建设问题11.1问题描述11.2问题分析11.3算法分析21.4算法实现及结果分析52.线性表的插入删除查找程序72.1问题描述72.2问题分析72.3算法分析82.4运行结果9总 结

4、10参考文献11附录源程序代码12171.最小生成树解决城市联络网建设问题1.1问题描述假设要在个城市之间建立通信联络网，其中顶点表示城市，边表示城市之间是否有通路，边上的权值表示在两者间建立通信链路的花费，要求使得任意两市之间都有通信链路，并且使得总的建设费用最少。显然，我们会想到连通个城市只需要条线路，在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。个城市之间，最多可以设置条线路，那么，如何在这些可能的线路中选择条，使得总的耗费最少呢？根据所学的知识，我们知道可以通过寻找最小生成树来解决这个问题。下面我们以图1为例，运用普利姆算法以及克鲁斯卡尔算法来解决城市间通信网建立问

5、题。 图11.2问题分析在一个具有几个顶点的连通图中，如果存在子图包含中所有顶点和一部分边，且不形成回路，则称为图的生成树，代价最小生成树则称为最小生成树。最小生成树有个重要的性质mst性质（最小生成树性质）：设是一个连通网络，是顶点集的一个真子集。若是中一条“一个端点在中(例如：)，另一个端点不在中的边，且具有最小权值，则一定存在的一棵最小生成树包括此边。多数算法利用这个性质来求解最小生成树，本文用到的普里姆算法和克鲁斯卡尔算法均利用了这个性质，同时它们也属于贪心算法。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅

6、是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。本文中的城市通信网建设问题要求使得任意两市之间都有通信链路，并且使得总的建设费用最少，故而适合用贪心算法求解。1.3算法分析1）prim 算法 假设是图中顶点的集合,为最小生成树中的边的集合,则算法通过以下步骤可以得到最小生成树:1:初始化:,。此步骤设立一个只有结点的结点集和一个空的边集作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。2:在所有边中,找一条权最小的边，将此边加进集合中，并将此边的非中顶点加入

7、中。此步骤的功能是在边集中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合和中,其次边的权要最小。找到这条边以后,把这条边放到边集中,并把这条边上不在中的那个顶点加入到中。这一步骤在算法中应执行多次,每执行一次,集合和都将发生变化,分别增加一条边和一个顶点,因此,和是两个动态的集合,这一点在理解算法时要密切注意。3:如果,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当时,步骤2共执行了次(设n为图中顶点的数目),中也增加了条边,这条边就是需要求出的最小生成树的边。prim算法伪代码如下：void minispantree_prim(mgraph g,

8、vertextype u) /用普利姆算法从第u个顶点出发构造网g的最小生成树t，输出t的各条边。/记录从顶点集u到v-u的代价最小的边得辅助数组定义/ struct/ vertextype adjvex;/ vrtype lowcost;/ closedgemax_vertex_num; k=locatevex(g,u); for(j=0;j<g.vexnum;+j) /辅助数组初始化 if(j!=k) closedgej=u,g.arcskj.adj; /adjvex,lowcost closedgek.loecost=0; /初始，u=u for(i-0;i<g.vexnum

9、;+i) /选择其余g.vexnum-1个顶点 k=minimum(closedge); /求出t的下一个结点：第k顶点 / closedgek.loecost= / minclosedgevi.lowcost|closedgevi.lowcost>0, printf(closedgek.adjvex,g.vexsk); /输出生成树的边 closedgek.lowcost=0; /第k顶点并入u集 for(j=0;j<g.vexnum;+j) if(g.arcskj.adj<closedgej.lowcost) /新顶点并入u后重新选择最小边 closedgej=g.vex

10、sk,g.arcskj.adj; /minispantree 由上述伪代码可知，prim算法的时间复杂度为。 算法构造最小生成树如下图所示： 图2 图3 图4 图5 图6 图72）kruskal算法假设 是一个含有个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有棵树的一个森林。之后，从网的边集中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小

11、的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有条边为止。kruskal算法的伪代码如下：void dfsarticul(algraph g,int v0)/从第v0个顶点出发深度优先遍历图g，查找并输出关节点。 visitedv0=min=+count; /v0是第count个访问的顶点 for(p=g.verticesv0.firstarc;p;p=p->nextarc)/对v0的每个邻接顶点检查w=p->adjvex; /w为v0的邻接顶点if(visitedw=0) /w未曾访问，是v0的孩子 dfsarticul(g,w); /返回前求得loww if(loww

12、<min) min=loww; if(loww>=visitedv0) printf(v0,g.verticesv0.data); /关节点else if(visitedw<min) min=visitedw; /w已访问，w是v0在生成树上的祖先/forlowv0=min/dfsarticul。kruskal算法的时间复杂度为（其中e为网中边得数目）。kruskal算法构造最小生成树如下图所示： 图8 图9 图10 图11 图12 图131.4算法实现及结果分析输入（表1）：城市或城镇点 a(0)点 b(1)点 c(2)点 d(3)点 e(4)点 a(0)点 b(1)1点

13、c(2)213点 d(3)384点 e(4)111456点 f(5)12101597 表1prim算法输出（表2）：从(）城市到（）城市权值a（0）b（1）1a（0）c（2）2a（0）d（3）3c（2）e（4）5e（4）f（5）7 表2运行结果如图14： 图14kruskal算法输出（表3）：从（）城市到（）城市权值a(0)b(1) 1a(0)c(2) 2a(0)d(3) 3c(2)e(4) 5e(4)f(5) 7合计18 表3运行情况如图15： 图152.线性表的插入删除查找程序2.1问题描述线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第

14、一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。 本文针对首先建立顺序表，然后利用顺序表的查找、删除、输出等运算反复实现顺序表的这些操作（插入、删除、查找、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。2.2问题分析 本文开始建立一个顺序表，根据要求，然后利用顺序表的查找、删除、输出等运算反复实现顺序表的这些操作（插入、删除、查找、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。2.3算法分析status listinsert_sq(sqlist *l, int i

15、 ,elemtype e) /顺序表的插入          elemtype *p,*q;          if (i<1 | i>l->length+1) return error;           if (l->length >=l->listsize)  &#

16、160;       l->elem = (elemtype * )realloc(l->elem,(l->listsize + listincrement) * sizeof (elemtype);          if (!l->elem )exit(overflow);           l->listsize +=

17、listincrement;                      q = & (l->elemi-1);          for (p = & (l->eleml->length - 1);p>=q;-p)*(p+1) = *p;     &

18、#160;    *q = e ;          +l->length ;          return ok ;status locateelem_sq(sqlist l, elemtype e) /顺序表的查找       int i=1;       elemtype *

19、p;       p =l.elem;        while (i<=l.length && !(*p+=e) +i;       if (i<=l.length)     return i;       else return 0; status listdelete_sq(sqlis

20、t *l,int i) /顺序表的删除elemtype e,*p,*q;if(i<1)|(i>l->length) return error;p=&(l->elemi-1);e=*p;q=l->elem+l->length-1;for(+p;p<=q;+p)   *(p-1)=*p;-l->length;printf("%3dn",e);return ok;2.4运行结果总 结通过本次课程设计，使我对数据结构程序的设计方法、步骤、思路、有一定的了解与认识。在课程设计过程中按照规定的程序进行，先针对题

21、目收集、调查有关资料，然后进入程序调试阶段，其间与指导教师进行讨论、修改，再讨论、再修改，最后定案，进行写论文阶段。整个过程周密有序，按时高质完成全部课程设计。此次课程设计按照设计任务书、指导书、技术条件的要求进行顺利完成任务，加深了对数据结构这么课程的了解，在程序调试以及实现过程中，进一步了解数据结构中的原理，理论，对知识的理解进一步深化参考文献1吴伟民.数据结构（c语言版）.北京：清华大学出版社，20092姚诗斌.数据结构基础.北京：北京大学出版社，19933严蔚敏.并行算法引论.天津：石油工业出版社，19924胡蕴超.算法与数据结构.北京：电子工业出版社，1993附录源程序代码1最小生成

22、树解决城市联络网建设问题源程序代码#include<iostream>using namespace std;#include <time.h>const int maxvertexnum=20;const int maxedgenum=40;typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;/=void insitadj(adjmatrix &ga)

23、;void setadj(adjmatrix &ga,int n);void fun(adjmatrix ga,adgeset &gt,int n);void display(adgeset gt,int n);void insit(adgeset &gt,int n,adjmatrix ga);/=void insit(adgeset&gt,int n,adjmatrix ga)for(int i=0;i<n-1;i+)gti.frontvex=0;gti.rearvex=i+1;gti.weight=ga0i+1;void insitadj(adjma

24、trix &ga)for(int i=0;i<maxvertexnum;i+)for(int j=0;j<maxvertexnum;j+)gaij=20000;void setadj(adjmatrix &ga,int n)int i;for(i=0;i<=n;i+)for(int j=i+1;j<n;j+)cout<<"请输入第"<<i<<"个城市到第"<<j<<"个城市的距离"cin>>gaij;for(i=0;i<

25、;=n;i+)for(int j=i+1;j<n;j+)gaji=gaij;void fun(adjmatrix ga,adgeset&gt,int n) int i,j;for( i=0;i<n-1;i+)int min=10000,m=i;for(j=i;j<n-1;j+)if(gtj.weight<min)min=gtj.weight;m=j;edgenode temp=gti;gti=gtm;gtm=temp;int k=gtm.rearvex;for( j=i;j<n-1;j+)int t=gtj.rearvex;int w=gakt;if(w&

26、lt;gtj.weight)gtj.weight=w;gtj.frontvex=k;void display(adgeset gt,int n)for(int i=0;i<n-1;i+)cout<<"第"<<gti.frontvex<<"个城市到第"<<gti.rearvex<<"城市修建一条电缆！"<<gti.weight<<endl;cout<<"这样修建可以使距离最短！"int main()cout<&

27、lt;"你要在几个城市间建设网络？请输入："<<endl;int n;cin>>n;adgeset gt;adjmatrix ga;insitadj(ga);setadj(ga,n);insit(gt,n,ga);fun(ga,gt,n);display(gt,n); int x; cin>>x;return 0;2.线性表的插入，删除，添加的源程序：#include <stdio.h>#include <stdlib.h>#define     ok  

28、    1#define     error     0 #define     overflow     -1typedef     int     elemtype;    typedef     int status;#define  

29、;   list_init_size 100#define     listincrement     10typedef     struct        elemtype *elem;     int length;      int listsize;    sqlist

30、;status initlist_sq(sqlist *l)          int i,n;          l->elem = (elemtype * )malloc(list_init_size*sizeof(elemtype);          if (! l->elem) exit (overflow

31、);    printf("您希望您的线性表有几个元素:   ");    scanf("%d",&n);    printf("n");    printf("输入您的%d个元素，以构建顺序表: n",n);              fo

32、r(i=1;i<=n;i+)              scanf("%d",&l->elemi-1);          l->length = n;          l->listsize = list_init_size;

33、60;         return ok;/initlist_sqstatus printlist_sq(sqlist l)          int i;          printf("顺序表中的元素为： ");        &#

34、160; for (i=1;i<=l.length;i+)               printf("%d      ",l.elemi-1);          printf("n");       

35、   return ok;/printlist_sq status listinsert_sq(sqlist *l, int i ,elemtype e)          elemtype *p,*q;          if (i<1 | i>l->length+1) return error;       

36、0;   if (l->length >=l->listsize)          l->elem = (elemtype * )realloc(l->elem,(l->listsize + listincrement) * sizeof (elemtype);          if (!l->elem )exit(overflow);  &

37、#160;        l->listsize += listincrement;                      q = & (l->elemi-1);          for (p = & (l->eleml

38、->length - 1);p>=q;-p)*(p+1) = *p;          *q = e ;          +l->length ;          return ok ;/listinsert_sqstatus locateelem_sq(sqlist l, elemtype e)   &#

39、160;   int i=1;       elemtype *p;       p =l.elem;        while (i<=l.length && !(*p+=e) +i;       if (i<=l.length)     return i; 

40、      else return 0; status listdelete_sq(sqlist *l,int i)elemtype e,*p,*q;if(i<1)|(i>l->length) return error;p=&(l->elemi-1);e=*p;q=l->elem+l->length-1;for(+p;p<=q;+p)   *(p-1)=*p;-l->length;printf("%3dn",e);return ok;void mai

41、n()       sqlist l;       elemtype k,e;       int i,j,m;            if (initlist_sq(&l)=overflow)          printf("分配失败，退出程序！");    printf("输出程序中的元素n");  &#