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

数据结构课程设计报告组员人数：2题目数：2姓名：学号：200925503230班级： 计093-2总分：姓名：学号：200925503204班级： 计093-2总分：题目1：熊猫烧香算法程序设计：分数：测试与报告：分数：题目2：室内布线算法程序设计：分数：测试与报告：分数：日期：2010年12月31日第一部分 数据结构课程设计题目一：搜索算法效率比较一、 课程设计内容现在某实验室感染了熊猫烧香病毒。实验室的机器排列为一个M行N列的矩阵，每台机器只和它相邻的奇迹直接相连（横向和纵向）。开始时有T台机器被感染，每台遭遇的熊猫变种类型都不同，分别及为K1，K2,KT。每台机器都具有一等级别的防御能力，将防御级别记为L （0L1000）。熊猫烧香按照下列规则传播：l 病毒只能从一台被感染的机器传到另一台没有被感染的机器。l 如果一台机器已经被某个变种的病毒感染过，就不能被其他变种感染。l 病毒的传播能力每天都在增强。第1天，病毒只能感染它可以到达的，防御级别不超过1的机器，而防御级别大于1的机器可以阻止它从自己出继续传播。第D天，病毒只能感染它可以到达的，防御级别不超过D的机器，而防御级别大于D的机器可以阻止它从自己出继续传播。l 在同一天之内，K1变种的病毒先开始传播，感染所有它可能感染的机器，然后是K2变种，K3变种依次进行传播。本题目的任务是：当整个网络被感染后，计算有多少台机器被某个特定变种所感染。二、 数据结构与算法设计1、 数据结构定义图结构 存放二维数组图节点的定义如下：typedef struct VertexType /节点信息int day;/第几天感染的int dl;/防御级别int r,c;/行列号int vt;/ 病毒类型图定义如下：typedef struct MGraph VertexType mMAXNODEMAXNODE;int row,colum ,num;/行列数，感染的数目MGraph;2、 主要算法（1）最终矩阵的生成函数：四重循环函数 通过两个WHILE实现病毒全部感染前天数的循环和病毒种类的循环。通过两个FOR函数实现图节点中和病毒种类相同的节点，运行图广度查找并感染四周节点函数。（2）感染函数（运用图的广度优先遍历查找）：建立队列，定义头尾指针。队列初始为空，从输入的节点开始，将节点入队。在队列不空的前提下，反复将对头出队，将该节点的四个方向相邻节点入队并判断能否感染，并实施感染。三、 程序实现介绍实现算法所编制的程序，包括头文件和源文件。简要说明个文件的功能MGraph.h 记录了矩阵图和图节点的数据结构 MGraph。 Suanfa.h 记录了最终矩阵生产函数和感染函数。main.cpp 实现算法的主程序。四、 测试结果l 测试输入：1 -3 -2 -3l -2 -1 -2 2l -3 -2 -1 -1l 1；l 测试目的：输入3*4矩阵 和病毒类型 验证能否输出正确感染相应病毒机器个数和原输入矩阵。l 正确输出：你的输入为l 1 -3 -2 -3l -2 -1 -2 2l -3 -2 -1 -1l 病毒类型为1的病毒个数为9l 实际输出：你的输入为l 1 -3 -2 -3l -2 -1 -2 2l -3 -2 -1 -1l 病毒类型为1的病毒个数为9ll 当前状态：通过五、 分析与探讨1. 测试结果分析。解释测试策略，对得到的结果进行分析，总结出算法的时间和空间复杂度，对算法的性能进行评价：测试结果正确实现算法功能。实现病毒感染天数和病毒感染天数的预测和输出结果。病毒感染函数的时间复杂度是O（n2）。2. 探索算法改进的可能性，提出自己的建议：(1病毒感染算法空间复杂度有缩小空间。可尝试放弃图的广度优先遍历使用其他算法。(2图的定义复杂 可以适当简化。 第二部分：数据结构课程设计题目二：室内布线一：课程设计题目：最小生成树：室内布线1. 题目要求编写程序帮助房主世界室内电线的布局。首先，墙上的插座是固定的。插座间需要有电线相连，而且要布置的整齐美观，即要求每条线都至少与一条墙边平行，且嵌入四壁或者地板（不能走屋顶）。另外，每个房间都有们，电线不可以穿门而过。要求将所有的插座连通，且告诉房主需要买的电线的最短长度。输入要求： 输入有若干组测试数据组成。每组数据的第1行包含房间的长宽高和插座的个数N=20。接下去的N行中，第i行给出第i个插座的位置坐标（xi， yi， zi），最后一行包含4个3元组，分别是长方形门框的4个交的三位坐标。4个整数全部为0表示全部测试结束。注：房间是长方体，位于三维指教坐标系的第一象限内，并且有一个角落在原点上。地板位于xy平面，插座位于墙上，门上没有插座。要求每段线段的两端仅与插座相连，电线之间不能互相连接。输出要求：对每一组测试，在一行里输出将所有插座连通需要买的电线的最短整数长度。输入例子：10 10 10 40 1 3.32.5 0 25 0 0.85 10 10 0 0 0 0 3 1.5 0 0 1.5 0 30 0 0 0输出例子：212. 简要提示可以将每个插座看成图中的一个结点，计算出任意两插座之间的最短距离，作为两结点间边的权重。要求的布线结果是一个保证连通的子图，其中包括边的权重和最小，这实际上是一个最小生成树，可以用求最小生成树的算法解决。构建图的过程比较复杂，因为图中任意两点间都有边，所以采用邻接矩阵表示图较好。构建图的过程比较复杂，为了方便计算两插座间的最短距离，每个插座除了要在数据结构中记录坐标外，还需要判断它属于哪一面墙，为此建议增加墙的编号。两插座的分布情况：在同一面墙，相邻的两面墙，在对面的墙。还要考虑是否有门。输出时要输出的整数长度要上取。二：数据结构与算法设计结构体：typedef struct CZ (CZ即插座的意思)/定义插座结构体int m; /m为插座所在墙(xz面为1；yz面为2；对xz面为3；对yz面为4)float x,y,z; /x,y,z分别为插座的三个坐标CZ;全局数组：float MIN2020; /定义全局矩阵存放每两个插座之间的最短连线主函数：void main()CZ CZ20;int L,W,H,N;T: coutLWHN; /L，W，H即X，Y，Z方向坐标 coutendl; for(int i=0;iN;i+) cout请输入第i+1CZi.mCZi.xCZi.yCZi.z; if(CZi.m4|CZi.xL|CZi.yW|CZi.zH) cout输入数据错误!重新输入: ; goto T2; coutendl;Count(N,L,W,CZ); /计算每两个插座间最短连线cout最短连线为：Calculate(N,MIN)endlendl; goto T;思路与算法实现 ：首先根据提示输入房间的长宽高和插座总数N，然后输入各个插座坐标及所在面（事先给每面墙编上号），输入数据错误则重新输入，坐标全部输入后调用Count函数计算每两个插座间连线的最短连线，并把连线的长度存入全局变量数组中，（计算两插座间最短连线分同面墙、临面墙和对面墙三种，同面墙和临面墙计算相似，对面墙有三种连线方式，调用Compare函数通过比较求得最短连线，其中以防距离有负数，在有可能出现负数的地方调用Contrary函数，正数不变负数取反），计算完之后调用Calculate函数（该函数实际是贪心算法即Dijkstra算法），计算所得对称矩阵即邻接矩阵的最小连通图权值之和，由于是对称的，计算了两遍，返回结果除以二即所有插座间连线的最短值。实用性即：新建一房子，长宽高知道，量出所有插座坐标，输入程序即可得出电线的最少值，买电线时就可以花最少的钱。三：程序实现其中求每两个插座最短连线为：for(int i=0;iN;i+)for(int j=0;jN;j+) if(CZi.m=CZj.m) /同面或临面墙 |(CZi.m=1&CZj.m=2)|(CZi.m=2&CZj.m=1) |(CZi.m=1&CZj.m=4)|(CZi.m=4&CZj.m=1) |(CZi.m=2&CZj.m=3)|(CZi.m=3&CZj.m=2) |(CZi.m=3&CZj.m=4)|(CZi.m=4&CZj.m=3) p1=CZi.x-CZj.x;p2=CZi.y-CZj.y;p3=CZi.z-CZj.z; p1=Contrary(p1);p2=Contrary(p2);p3=Contrary(p3); MINij=p1+p2+p3; else /对面墙 if(CZi.m=1&CZj.m=3)|(CZi.m=3&CZj.m=1) p1=CZi.x;p2=CZj.x;p3=W; a=p1+p2+p3; p1=CZi.z;p2=CZj.z;p3=W; b=p1+p2+p3; p1=L-CZi.x;p2=L-CZj.x;p3=CZi.z-CZj.z;p3= Contrary(p3); c=p1+p2+p3; MINij=Compare(a, b,c); /找出最短连线 else if(CZi.m=2&CZj.m=4)|(CZi.m=4&CZj.m=2) p1=CZj.y;p2=CZi.y;p3=L; a=p1+p2+p3; p1=CZi.z;p2=CZj.z;p3=L; b=p1+p2+p3; p1=W-CZj.y;p2=W-CZi.y;p3=L; c=p1+p2+p3; MINij=Compare(a, b,c); Calculate函数为：float Calculate(int N,float MIN2020)/计算最短路径float M=0,min=MIN00,k; /min为每一遍查找的最短连接长度，k为循环次数for(k=0;kN;k+) for(int i=0;iN;i+)for(int j=0;j0,MINij0;j+)if(minMINij) min=MINij; MINij=0;M+=min; /总连线最短长度return M/2; /所得矩阵为对称矩阵，数据加了两边四：测试结果测试过程是在草稿纸上画一个三维坐标，在第一卦限画一个房子，并任意墙上找出几个点作为插座，编上坐标计算最短连线，有简单到复杂，计算结果同程序运行结果对照，结果一样。具体数据：墙长宽高各为5，3个插座A（1 2 0 2）B（2 2 0 4）C（3 2 5 1）计算得AB间为6，结果正确；AC间