![数据结构课程设计12440_第1页](http://file2.renrendoc.com/fileroot_temp3/2021-11/2/aa1efbfd-bebc-4673-9c4e-dd220eb27b47/aa1efbfd-bebc-4673-9c4e-dd220eb27b471.gif)
![数据结构课程设计12440_第2页](http://file2.renrendoc.com/fileroot_temp3/2021-11/2/aa1efbfd-bebc-4673-9c4e-dd220eb27b47/aa1efbfd-bebc-4673-9c4e-dd220eb27b472.gif)
![数据结构课程设计12440_第3页](http://file2.renrendoc.com/fileroot_temp3/2021-11/2/aa1efbfd-bebc-4673-9c4e-dd220eb27b47/aa1efbfd-bebc-4673-9c4e-dd220eb27b473.gif)
![数据结构课程设计12440_第4页](http://file2.renrendoc.com/fileroot_temp3/2021-11/2/aa1efbfd-bebc-4673-9c4e-dd220eb27b47/aa1efbfd-bebc-4673-9c4e-dd220eb27b474.gif)
![数据结构课程设计12440_第5页](http://file2.renrendoc.com/fileroot_temp3/2021-11/2/aa1efbfd-bebc-4673-9c4e-dd220eb27b47/aa1efbfd-bebc-4673-9c4e-dd220eb27b475.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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 >,int n);void display(adgeset gt,int n);void insit(adgeset >,int n,adjmatrix ga);/=void insit(adgeset>,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>,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");
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高中二年级下学期生物《生态系统概念和结构模型构建》教学课件
- 施工升降机基础及附着施工方案
- 大学英语四级完形填空高频词
- 承插型键槽式连接钢管高大支模安全专项施工方案
- 卫生洁具安装施工工艺
- 四级作文 三部分作文法
- 2024年石油钻井工(中级工)职业资格考试题库-上(单选题)
- 2024年全国职业院校技能大赛高职组(新型电力系统技术与应用赛项)考试题库-中(多选题)
- 2024年江苏省百万城乡建设职工职业技能竞赛水务行业化学检验员决赛试题库-下(多选、简答题)
- 《Java Web技术》课程期末考试复习题库(含答案)
- 无线广播电视传输中的信号覆盖质量评估考核试卷
- 2024年统编版新教材语文小学一年级上册第一单元测试题及答案
- 煤矿应急叫应、回应、响应机制
- 旋挖钻孔灌注桩施工技术交底记录(干作业)
- 活动三《创意剪纸》教案 小学劳动 三年级
- 小学二年级下册数学《填空题》100道及一套参考答案
- 2024-2030年中国树莓汁行业发展分析及投资前景预测研究报告
- 循证护理实践理论考核试题及答案
- 马工程-公共财政概论-课程教案
- GB/T 226-2015钢的低倍组织及缺陷酸蚀检验法
- 公共政策学-陈振明课件
评论
0/150
提交评论