数据结构课程设计报告-煤气管道铺设程序设计报告.doc

数据结构程序设计报告数据结构课程设计报告 班 级: 姓 名： 指导教师： 成 绩： 2011年6月24日以下文档为第15题 煤气管道铺设 程序设计报告！摘要N(N10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。问题的实质就是编写相应程序求解最小生成树问题。程序要求：事先任意两个居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。目 录一、引言3二、需求分析3三、概要设计31普利姆算法思想32、模块分析4系统功能模块图：43.抽象数据类型分析6四、详细设计61.算法分析62建立最小生成树并输出结果7五.测试结果81.程序开始82.信息输入93.输出结果9六、调试分析9七.设计体会9八、结束语10九、参考文献10附录：10一、引言C语言作为一门最通用的语言，从语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子。学习掌握C语言是每一个计算机技术人员的基本功之一。实际生活中最小生成树的问题具有很大的意义。例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干地区铺设光缆等等。最小生成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解决方法。二、需求分析 在多个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的边数无关， 适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，适宜求解边稀疏的最小生成树。 由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线，即这样的图应该是边较为稠密的。因此，我们选择了普利姆算法对问题进行求解最小生成树。三、概要设计1普利姆算法思想普利姆算法的思想是：在图中人去一个定点k0作为开始点，令U=k0，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在w中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删除这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集。2 算法过程描述在图G=（V，E）（V是顶点，E是边）中，从集合V中任取一个顶点，如k0放入集合U中，这时，U=k0，集合T（E）为空。从k0出发寻找与U中顶点相邻权值最小的边的另一顶点k1 ，并使k1加入U。即U=k0，k1，同时将该边加入集合T（E）中。重复（2），直到U=V为止。这时T（E）中有n-1条边，T=（U，T（E）就是一颗最小生成树。 2、模块分析 系统功能模块图： 输入存储构造无向网输出结果输出最小生成树系统普利姆算法流程图 开始 j=0jG.vexnumstrcpy(closedgej.adjvex,G.vexk)+jYNiG.vexnumYk=minimum(closedge,G)closedgej.lowest=G.arcskj.adjk=locatevex(G,u)closedgek.lowest=0 j=1closedgek.lowest=0c printf(closedgek.adjvex.G.vexsk) j=0jG.vexnum +jYG.arcskj.adjclosedgej.lowest Closedgej=G.vexsk,G.arcskjY j=0 结束NN3.抽象数据类型分析areanum 居民区总数（顶点总数）；edgenum 边的总数；date2020 邻接矩阵存储图结构；s 边的权值；short-wayi 居民区i到目前生成树中所有点集U中某个居民区的路程最小值near-areai U中能使其最小的居民区四、详细设计1.算法分析1信息输入模块/读入图的信息，并将邻接矩阵输出void read()int areanum, edgenum,data2020;printf(请依次输入顶点数和边数:n); scanf(%d,%d,&areanum,&edgenum);/初始化邻接矩阵各元素值int i, j;for(i=0;iareanum;i+)for(j=0;jareanum;j+)dataij=0;/读入边int from, to, s;printf(输入边,格式为i j k,表示i到j的权值是k.n);for(i=0;iedgenum;i+)scanf(%d%d%d,&from,&to,&s);datafromto=s;/输出邻接矩阵for(i=0;iareanum;i+)for(j=0;jareanum;j+)printf(%6d,dataij);printf(n);2建立最小生成树并输出结果 / 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边void MiniSpanTree_PRIM(MGraph G,VertexType u) int i,j,k;k=LocateVex(G,u);for(j=0;jG.vexnum;+j) / 辅助数组初始化 if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; / 初始,U=u printf(最小代价生成树的各条边为:n);for(i=1;iG.vexnum;+i) / 选择其余G.vexnum-1个顶点 k=minimum(closedge,G); / 求出T的下一个结点：第K顶点 printf(%s-%s)n,closedgek.adjvex,G.vexsk); / 输出生成树的边 closedgek.lowcost=0; / 第K顶点并入U集 for(j=0;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost)/ 新顶点并入U集后重新选择最小边 strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj;system(pause);五.测试结果1.程序开始2.信息输入 3.输出结果 六、调试分析调试程序时发现自己编写的程序虽然能够运行但是对于错误输入没有反应，居然还能继续运行并且没有任何提示信息显示，后来通过不断的修改代码，增加说明从而减少这一问题的出现。七.设计体会通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了大家的动手能力。同时也发现了自己的很多不足之处，对知识的应用能力很是欠缺，应用软件的能力及编程水平与课程要求更是存在很大的差距。程序的运行结果与理论推导结果完全吻合，即该算法与程序设计满足课程设计要求。该程序的主要优点是简单易懂，不存在理解上的障碍，也很自然地能想到这种解法。主要缺点是程序的变动性比较差初始化邻接矩阵后结果就固定了。如果能加入图行和图的修改、插入、删除等操作，我想应该会好很多。八、结束语转眼，数据结构课程设计的第一阶段即将结束了。在这次课程设计中我的c语言知识和数据结构知识得到了很好学习。编程能力也有了一定的提高。同时也学回了解决问题的方法。总结起来，自己主要有以下几点体会：必须牢固掌握基础知识。由于C语言是大一所学知识，没有好好的去体会掌握，同时也没有掌握好上学期学的数据结构这门课，所以在课程设计初期感到无从下手，但在后来的设计过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所了解和熟悉。这时才逐渐有了思路。所以，在这次课程设计以后，我下了决心：以后一定要好好学习好专业知识。必须培养严谨的科学态度。我在编写程序时经常因为一些类似于少写了分号，大括号不匹配等造成的程序调试失败，不够认真仔细，给自己带来了许多麻烦。这次课程设计也让我充分的认识到数据结构这门课的重要性。它给我们的一个思想和大纲，让我们再编程时更容易找到思路，不至于无章可循。同时它也有更广泛的实际应用价值。总之，在这次课程设计中，我的C语言以及数据结构知识得到了长足的进步，对编程有了更深层次的了解。九、参考文献谭浩强 C语言设计第三版 严蔚敏 数据结构C语言版附录：程序源代码：#include #include #include#include #include#define MAX_VERTEX_NUM 40/ 最大顶点个数#define MAX_NAME 3 / 顶点字符串的最大长度#define MAX_INFO 20 / 相关信息字符串的最大长度typedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_NAME;/ 邻接矩阵的数据结构typedef structVRType adj; / 顶点关系类型。对无权图，用1或0表示相邻否；/ 对带权图，则为权值类型InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 图的数据结构typedef structVertexType vexsMAX_VERTEX_NUM;/ 顶点向量AdjMatrix arcs;/ 邻接矩阵int vexnum;/ 图的当前顶点数intarcnum;/ 图的当前弧数MGraph;/ 记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef structVertexType adjvex;VRType lowcost;edge,minsideMAX_VERTEX_NUM;/ 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。int LocateVex(MGraph G,VertexType u)int i;for(i = 0; i G.vexnum; +i)if( strcmp(u, G.vexsi) = 0)return i;return -1;/代价存入文件void file() system(cls);FILE *fp;char s50,ch;strcpy(s,D:record.txt);if(fp=fopen(s,ab+)=NULL)printf(无法打开此文件n);exit(0);elseprintf(请输入顶点数和边数:(输入键表示结束)n); ch=getchar(); while(ch!=)fputc(ch,fp);ch=getchar();printf(请输入起点,终点,及相应的权值:(输入#键表示结束)n); ch=getchar(); while(ch!=#)fputc(ch,fp);ch=getchar();fclose(fp);system(pause);system(cls);/从文件中得到信息构成图void display ()system(cls); FILE *fp;char s50,ch;strcpy(s,D:record.txt);if(fp=fopen(s,r)=NULL)printf(无法打开此文件n);exit(0);elsewhile(!feof(fp)ch=fgetc(fp);putchar(ch);putchar(10);fclose(fp);system(pause);system(cls);/ 算法7.2 P162/ 采用数组(邻接矩阵)表示法,构造无向网G。void CreateAN(MGraph *G) system(cls);int i,j,k,w;VertexType va,vb;printf(请输入无向网G的顶点数,边数,(空格区分):n );scanf(%d%d,&(*G).vexnum,&(*G).arcnum);printf(请输入%d个顶点的值:n,(*G).vexnum);for(i=0;i(*G).vexnum;+i) / 构造顶点向量scanf(%s,(*G).vexsi);for(i=0;i(*G).vexnum;+i) / 初始化邻接矩阵for(j=0;j(*G).vexnum;+j)(*G).arcsij.adj=0; / 网初始化为0printf(请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): n,(*G).arcnum);for(k=0;k(*G).arcnum;+k)scanf(%s%s%d%*c,va,vb,&w); / %*去除回车符i=LocateVex(*G,va);j=LocateVex(*G,vb);if(i!=-1&j!=-1)(*G).arcsij.adj=(*G).arcsji.adj=w;/无向网邻接矩阵成对称else printf(data error! 有顶点不存在！请重新输入); for(i=0;i(*G).vexnum;+i) / 初始化邻接矩阵for(j=0;j(*G).vexnum;+j)(*G).arcsij.adj=0; / 网初始化为0 k=-1;printf(输出临接矩阵：n);for(i=0;i(*G).vexnum;+i) for(j=0;j(*G).vexnum;+j)printf(%3d , (*G).arcsij.adj); printf(n);system(pause);system(cls);/ 求closedge.lowcost的最小正值int minimum(minside SZ,MGraph G)/用k返回权值最小的顶点的位置int i=0,j,k,min;while(SZi.lowcost=-1&iG.vexnum) +i;/ 查找不在集合U中的顶点min=SZi.lowcost; / 第一个不为-1的值k=i;for(j=i+1;j0&minSZj.lowcost) min=SZj.lowcost; k=j;return k;/ 算法7.9 P175/ 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边void MiniSpanTree_PRIM(MGraph G,VertexType u)int i,j,k;minside closedge;k=LocateVex(G,u);/找到顶点u在顶点集合中的位置kfor(j=0;jG.vexnum;+j) / 辅助数组初始化 if(j!=k)/除去被选取的第一个顶点ustrcpy(closedgej.adjvex,G.vexsk);/顶点名字赋值给辅助数组closedge的adjvexclosedgej.lowcost=G.arcskj.adj;/将顶点的权值赋值给辅助数组closedge的lowcostclosedgek.lowcost=-1; / 初始,U=u用lowecost是否为-1来区分顶点是否在集合U中printf(最小代价生成树的各条边为:n);for(i=1;iG.vexnum;+i) / 选择其余G.vexnum-1个顶点k=minimum(closedge,G); / 求出T的下一个结点printf(%s-%s)n,closedgek.adjvex,G.vexsk); / 输出生成树的边closedgek.lowcost=-1; / 第K顶点并入U集for(j=0;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost)/ 新顶点并入U集后重新选择最小边strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj;system(pause);system(cls);int main()MGraph G; int xz; while(1) printf(ntt*管 道 铺 设 最 佳 方 案 选 择*n); printf(tt* 0 记录保存为文件 *n); printf(tt* 1 从文件中读记录 *n);printf(tt* 2 构造无向网 *n ); printf(tt* 3 求出最小生成树 *n); printf(tt* 4 退出 *n);printf(tt*n); printf( 请输入操作序号(0-4):n); scanf(%d,&xz); switch(xz) case 0: file(); break; case 1: display (); break; case 2: CreateAN(&G); break; case 3: MiniSpanTree_PRIM(G,G.vexs0); break; case 4: exit(0);default:system(cls); printf(输入无效指令! 按任意键继续); 以下文档为第37题工资管理的程序设计报告摘要 首先建立职工相关的数据文件，然后通过一定的操作来实现以下功能：查询职工的平均工资查询某一级别人员的平均工资普调工资将职工姓名按工资额度进行排序。本文通过对数组的一定操作来实现职工信息的变更管理以及工资的管理，1.引言192.需求分析203.概要设计20抽象数据类型：20系统总体功能设计图21程序模块分析214.详细设计21新建职工信息表22删除职工信息22工资排序235.测试结果24三个菜单24职工信息录入25职工信息输出256.调试分析257.设计体会268.结束语26参考文献27附录271.引言C语言作为一门最通用的语言，从语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子。学习掌握C语言是每一个计算机技术人员的基本功之一。实际生活中工资管理的问题具有很大的意义。例如，本文所讨论的对职工表进行增加、删除、插入，工资调整等具有很强的现实意义，职工信息管理在公司管理之中占据一定重要的地位。2.需求分析需求一，录入职工信息并且具有一定的查询功能（包括查询所有在职职工的平均工资，查询某一级别所有职工的平均工资，查找某为职工的信息，同时将查询到的结果显示出来）需求二，还实现对职工信息修改的功能，主要包括对于职工信息的插入和删除，以及对于职工工资普调的修改；需求三,，将职工姓名按照工资额度进行排序并且将结果显现出来。3.概要设计抽象数据类型：xm 姓名数组 people 职工总人数worker 职工信息(包括姓名，工资和等级)系统总体功能设计图系统修改职工文档普调工资工资排序 查询某级 职工的均资 查询职工的平均工资 退 出 新 建 追 加 上 涨 下 调 返 回 删 除 返 回 程序模块分析职工信息录入核心算法：输入职工姓名判断是否为输入结束符后，再继续输入工资和等级，然后判断信息是否符合规定，继而循环执行，最后返回结果职工总人数删除职工信息：输入要删除的职工信息存入数组后，逐个与职工信息表进行核对判断是否存在，然后将这个职工的信息后面的职工信息前移如果存在的话。工资排序：从第一个职工开始进行扫描，然后按照工资等级逐个存入相应的数组内，最后按照等级输出各数组内容显示。工资调整：读取职工信息，逐个按照规则(上涨或下调)进行修改职工信息. 4.详细设计职工信息录入： 增加职工信息查询平均工资开始i=0, sum=0ini+sum+=straffi.pays结束增加职工信息 求取职工平均工资新建职工信息表void newfile(workers staff,people p)/输入职工信息并返回职工人数 system(cls); p.num=abc(staff,0,MAX); printf(成功输入%d位职工信息！,p.num); go_on();删除职工信息void del_worker(workers staff,people p)/通过姓名删除该职工信息 int i,j=0,k,x=0,n=p.num;/x用来记录要删除的职工的人数 xm st,z20; printf(输出要删除职工的姓名(结束); scanf(%s,st); while(strcmp(st,)!=0) strcpy(zj,st); +x; for(j=0; jx; +j) for(i=0; in; +i) if(strcmp(zj,) = 0) for(k=i; kn; +k) strcpy(,staffk+1.name); staffk.pays=staffk+1.pays; staffk.wages_rank=staffk+1.wages_rank; n-=1; else printf(职工不存在，请确认正确); exit(0); p.num=n;go_on();工资排序void drop(workers staff,people p) /将职工姓名按工资额度进行排序 system(cls); printf(职工工资降序排列为:); xm aMAX,bMAX,cMAX,dMAX; int i,j=0,k=0,m=0,n=0; for(i=0; ip.num; i+) if(staffi.wages_rank=1) strcpy(aj+,);/将职工姓名对应存入数组 if(staffi.wages_rank=2) strcpy(bk+,); if(staffi.wages_rank=3) strcpy(cm+,); if(staffi.wages_rank=4) strcpy(dn+,); printf(工资等级为一级的职工姓名为:n);display(a,j); printf(工资等级为二级的职工姓名为:n);display(b,k); printf(工资等级为三级的职工姓名为:n); display(c,m); printf(工资等级为四级的职工姓名为:n); display(d,n); go_on(); 5.测试结果三个菜单职工信息录入职工信息输出6.调试分析问题：1. 不能多次执行和分菜单返回主菜单异常；2.内存不能read等情况。3. 运行发现开关语句的default语句对于字符的输入将循环执行，不像数字那样正常的直接继续执行default语句，而是出现类似于死循环的情形，无休止的按任意键继续；分析解决：1.返回主菜单异常，是因为没有出现假死循环的条件，后来通过将语句块放入while（1）中，解决了继续执行的问题。至于分菜单返回主菜单的问题，仔细思考后发现将分菜单中的开关语句switch后面括号的表达式修改为变量，初始值设定为1，在返回主菜单那一个case 中将变量修改为0.2.仔细检查代码发现在函数命名时出现重名，修改后异常消失7.设计体会通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了大家的动手能力。同时也发现了自己的很多不足之处，对知识的应用能力很是欠缺，应用软件的能力及编程水平与课程要求更是存在很大的差距。程序的运行结果与理论推导结果完全吻合，即该算法与程序设计满足课程设计要求。该程序的主要优点是简单易懂，不存在理解上的障碍，也很自然地能想到这种解法。主要缺点是程序的变动性比较差初始化邻接矩阵后结果就固定了。如果能加入图行和图的修改、插入、删除等操作，我想应该会好很多。8.结束语转眼，数据结构课程设计的第一阶段即将结束了。在这次课程设计中我的c语言知识和数据结构知识得到了很好学习。编程能力也有了一定的提高。同时也学回了解决问题的方法。总结起来，自己主要有以下几点体会：必须牢固掌握基础知识。由于C语言是大一所学知识，没有好好的去体会掌握，同时也没有掌握好上学期学的数据结构这门课，所以在课程设计初期感到无从下手，但在后来的设计过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所了解和熟悉。这时才逐渐有了思路。所以，在这次课程设计以后，我下了决心：以后一定要好好学习好专业知识。必须培养严谨的科学态度。我在编写程序时经常因为一些类似于少写了分号，大括号不匹配等造成的程序调试失败，不够认真仔细，给自己带来了许多麻烦。这次课程设计也让我充分的认识到数据结构这门课的重要性。它给我们的一个思想和大纲，让我们再编程时更容易找到思路，不至于无章可循。同时它也有更广泛的实际应用价值。总之，在这次课程设计中，我的C语言以及数据结构知识得到了长足的进步，对编程有了更深层次的了解。参考文献谭浩强 C语言设计第三版 严蔚敏 数据结构C语言版附录源代：#includestdio.h#includestring.h#include#define MAX 100/职工人数最大值为MAX#define EXTRA 20typedef char xm10;/ 姓名最大字符数为10typedef struct int num; /职工人数people;typedef struct xm name; /职工姓名 int pays; /职工工资 int wages_rank;/职工工资等级 /工资等级分为1 2 3 4 等 /工资等级对应表(单位：元) 1：1000-3000；2：30005000；3：5000-10000：4：10000 worker,workersMAX; /职工总数限制为100人void go_on()/返回前一级菜单system(pause); system(cls);int abc(workers staff,int i,int n)/后面多次运用，单独取出作为函数/i为职工信息数组开始的位置，n为职工人数最大值 printf( t 工资与工资等级对照表nn); printf( * 工资等级 | 工资范围 *n); printf( * 1t | 1000,3000) *n); printf( * 2t | 3000,5000) *n); printf( * 3t | 5000,10000) *n); printf( * 4t | 10000,unknow) *nn); printf(请依次输入职工信息:职工姓名(结束)，工资，工资等级(1-4):n); scanf(%s,);/输入职工姓名 while(strcmp(,)!=0)&i=1000&staffi.pays=3000&staffi.pays=5000&staffi.pays10000)break;else printf(data error!n); exit(0);default: printf(data error!n);exit(0); +i; scanf(%s,);/输入职工姓名 return i;/返回现在职工总人数void newfile(workers staff,people p)/输入职工信息并返回职工人数 system(cls); p.num=abc(staff,0,MAX); printf(成功输入%d位职工信息！,p.num); go_on();void add_worker(workers staff,people p) int add,i,n=p.num; worker staffsMAX+EXTRA; printf(请输入要增加职工的人数：); scanf(%d,&add); if(n+addMAX) for(i=0;in;+i)/结构体数组staff的值赋给结构体数组staffs strcpy(,); staffsi.pays=staffi.pays; staffsi.wages_rank=staffi.wages_rank; printf(请输入要增加职工的信息：); p.num=abc(staffs,n,n+add); 饿lse p.num=abc(staff,n,MAX+EXTRA);printf(成功输入增加的%d位职工的信息！,add); go_on();void del_worker(workers staff,people p)/通过姓名删除该职工信息 int i,j=0,k,x=0,n=p.num;/x用来记录要删除的职工的人数 xm st,z20; printf(输出要删除职工的姓名(结束); scanf(%s,st); while(strcmp(st,)!=0) strcpy(zj,st);+x; for(j=0; jx; +j) for(i=0; in; +i) if(strcmp(zj,) = 0) for(k=i; kn; +k) strcpy(,staffk+1.name); staffk.pays=staffk+1.pays; staffk.wages_rank=staffk+1.wages_rank; n-=1; elseprintf(职工不存在，请确认正确);exit(0); p.num=n;go_on();void display(workers staff,people p)/显示职工信息 system(cls); int n=p.num; printf(职工信息如下：n); printf(*); printf( 姓名t 工资t 工资等级); for(int i=0; in; i+) printf(%st%dt%dn,,staffi.pays,staffi.wages_rank);printf(*);go_on();void all_average(workers staff,people p)/求所有职工的平均工资 int n=p.num,i; long sum=0; for(i=0; in; i+) sum+=staffi.pays; printf(所有职工共计%d人平均工资为:%d元,n,sum/n);go_on();void part_average(workers staff,people p) /查询某一级别人员的平均工资 system(cls); int wages_level,n=p.num; int sum=0,i=0,avg; printf(输入要查询的工资等级(1-4):); scanf(%d,wages_level); if(0wages_level5) while(in) if(staffi.wages_rank=wages_level) sum+=staffi+.pays; else printf(工资等级不存在！请重新输入！);ex