数据结构课程设计报告

组员人数：2

题目数：2

姓名：学号：200925503230 姓名：

学号：200925503204

题目1：熊猫烧香

算法程序设计：测试与报告：

题目2：室内布线

算法程序设计：测试与报告：

班级：计093-2 总分：

分数：

分数：分数：

日期：20xx年12月31日

第一部分数据结构课程设计题目一：搜索算法效率比较

一、课程设计内容

现在某实验室感染了熊猫烧香病毒。实验室的机器排列为一个M行N列的矩阵，每台机器只和它相邻的奇迹直接相连（横向和纵向）。开始时有T台机器被感染，每台遭遇的熊猫变种类型都不同，分别及为K1，K2,…KT。每台机器都具有一等级别的防御能力，将防御级别记为L （0<L<1000）。熊猫烧香按照下列规则传播：

? 病毒只能从一台被感染的机器传到另一台没有被感染的机器。

? 如果一台机器已经被某个变种的病毒感染过，就不能被其他变种感染。

? 病毒的传播能力每天都在增强。第1天，病毒只能感染它可以到达的，防御级别不超过1的机器，而防

御级别大于1的机器可以阻止它从自己出继续传播。第D天，病毒只能感染它可以到达的，防御级别不超过D的机器，而防御级别大于D的机器可以阻止它从自己出继续传播。

? 在同一天之内，K1变种的病毒先开始传播，感染所有它可能感染的机器，然后是K2变种，K3变种……

依次进行传播。

本题目的任务是：当整个网络被感染后，计算有多少台机器被某个特定变种所感染。

二、数据结构与算法设计

1、数据结构

定义图结构存放二维数组

图节点的定义如下：

typedef struct VertexType //节点信息

{

int day;//第几天感染的

int dl;//防御级别

int r,c;//行列号

int vt;// 病毒类型

图定义如下：

typedef struct MGraph

{

VertexType m[MAXNODE][MAXNODE];

int row,colum ,num;//行列数，感染的数目

}MGraph;

2、主要算法

（1）最终矩阵的生成函数：四重循环函数通过两个WHILE实现病毒全部感染前天数的循环和病毒种类的循环。通过两个FOR函数实现图节点中和病毒种类相同的节点，运行图广度查找并感染四周节点函数。

（2）感染函数（运用图的广度优先遍历查找）：

建立队列，定义头尾指针。队列初始为空，从输入的节点开始，将节点入队。在队列不空的前提下，反复将对头出队，将该节点的四个方向相邻节点入队并判断能否感染，并实施感染。

三、程序实现

介绍实现算法所编制的程序，包括头文件和源文件。简要说明个文件的功能

MGraph.h 记录了矩阵图和图节点的数据结构 MGraph。

Suanfa.h 记录了最终矩阵生产函数和感染函数。

main.cpp 实现算法的主程序。

四、测试结果

测试输入：1 -3 -2 -3 -2 -1 -2 2 -3 -2 -1 -1 1；测试目的：输入3*4矩阵和病毒类型验证能否输出正确感染相应病毒机器个数和原输入矩阵。正确输出：你的输入为 1 -3 -2 -3 -2 -1 -2 2 -3 -2 -1 -1 病毒类型为1的病毒个数为9 实际输出：你的输入为 1 -3 -2 -3 -2 -1 -2 2 -3 -2 -1 -1 病毒类型为1的病毒个数为9 当前状态：通过

五、分析与探讨

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 4

0 1 3.3

2.5 0 2

5 0 0.8

5 10 1

0 0 0 0 0 3 1.5 0 0 1.5 0 3

0 0 0 0

输出例子：

2. 简要提示

可以将每个插座看成图中的一个结点，计算出任意两插座之间的最短距离，作为两结点间边的权重。要求的布线结果是一个保证连通的子图，其中包括边的权重和最小，这实际上是一个最小生成树，可以用求最小生成树的算法解决。

构建图的过程比较复杂，因为图中任意两点间都有边，所以采用邻接矩阵表示图较好。

构建图的过程比较复杂，为了方便计算两插座间的最短距离，每个插座除了要在数据结构中记录坐标外，还需要判断它属于哪一面墙，为此建议增加墙的编号。两插座的分布情况：在同一面墙，相邻的两面墙，在对面的墙。还要考虑是否有门。

输出时要输出的整数长度要上取。

二：数据结构与算法设计

结构体：typedef struct CZ (CZ即插座的意思)

{//定义插座结构体

int m; //m为插座所在墙(xz面为1；yz面为2；对xz面为3；对yz面为4) float x,y,z; //x,y,z分别为插座的三个坐标

}CZ;

全局数组：float MIN[20][20]; //定义全局矩阵存放每两个插座之间的最短连线

主函数：void main()

{

CZ CZ[20];

int L,W,H,N;

T: cout<<"请输入房间长宽高及插座数：";

cin>>L>>W>>H>>N; //L，W，H即X，Y，Z方向坐标

cout<<endl;

for(int i=0;i<N;i++)

{

cout<<"请输入第"<<i+1<<"个插座所在墙面及坐标: ";

T2: cin>>CZ[i].m>>CZ[i].x>>CZ[i].y>>CZ[i].z;

if(CZ[i].m>4||CZ[i].x>L||CZ[i].y>W||CZ[i].z>H)

{

cout<<"输入数据错误!重新输入: ";

goto T2;

}

cout<<endl;

Count(N,L,W,CZ); //计算每两个插座间最短连线

cout<<"最短连线为："<<Calculate(N,MIN)<<endl<<endl;

goto T;

}

思路与算法实现：首先根据提示输入房间的长宽高和插座总数N，然后输入各个插座坐标及所在面（事先给每面墙编上号），输入数据错误则重新输入，坐标全部输入后调用Count函数计算每两个插座间连线的最短连线，并把连线的长度存入全局变量数组中，（计算两插座间最短连线分同面墙、临面墙和对面墙三种，同面墙和临面墙计算相似，对面墙有三种连线方式，调用Compare函数通过比较求得最短连线，其中以防距离有负数，在有可能出现负数的地方调用Contrary函数，正数不变负数取反），计算完之后调用Calculate函数（该函数实际是贪心算法即Dijkstra算法），计算所得对称矩阵即邻接矩阵的最小连通图权值之和，由于是对称的，计算了两遍，返回结果除以二即所有插座间连线的最短值。

实用性即：新建一房子，长宽高知道，量出所有插座坐标，输入程序即可得出电线的最少值，买电线时就可以花最少的钱。

三：程序实现

其中求每两个插座最短连线为：

for(int i=0;i<N;i++)

{

for(int j=0;j<N;j++)

{

if((CZ[i].m==CZ[j].m) //同面或临面墙

||(CZ[i].m==1&&CZ[j].m==2)||(CZ[i].m==2&&CZ[j].m==1)

||(CZ[i].m==1&&CZ[j].m==4)||(CZ[i].m==4&&CZ[j].m==1)

||(CZ[i].m==2&&CZ[j].m==3)||(CZ[i].m==3&&CZ[j].m==2)

||(CZ[i].m==3&&CZ[j].m==4)||(CZ[i].m==4&&CZ[j].m==3))

{

p1=CZ[i].x-CZ[j].x;p2=CZ[i].y-CZ[j].y;p3=CZ[i].z-CZ[j].z;

p1=Contrary(p1);p2=Contrary(p2);p3=Contrary(p3);

MIN[i][j]=p1+p2+p3;

}

else //对面墙

{

if((CZ[i].m==1&&CZ[j].m==3)||(CZ[i].m==3&&CZ[j].m==1))

{

p1=CZ[i].x;p2=CZ[j].x;p3=W;

a=p1+p2+p3;

p1=CZ[i].z;p2=CZ[j].z;p3=W;

b=p1+p2+p3;

p1=L-CZ[i].x;p2=L-CZ[j].x;p3=CZ[i].z-CZ[j].z;p3= Contrary(p3); c=p1+p2+p3;

MIN[i][j]=Compare(a, b,c); //找出最短连线

}

else

if((CZ[i].m==2&&CZ[j].m==4)||(CZ[i].m==4&&CZ[j].m==2))

{

p1=CZ[j].y;p2=CZ[i].y;p3=L;

a=p1+p2+p3;

p1=CZ[i].z;p2=CZ[j].z;p3=L;

b=p1+p2+p3;

p1=W-CZ[j].y;p2=W-CZ[i].y;p3=L;

c=p1+p2+p3;

MIN[i][j]=Compare(a, b,c);

}

Calculate函数为：

float Calculate(int N,float MIN[20][20])

{//计算最短路径

float M=0,min=MIN[0][0],k; //min为每一遍查找的最短连接长度，k为循环次数 for(k=0;k<N;k++)

{

for(int i=0;i<N;i++)

{

for(int j=0;j<N,min>0,MIN[i][j]>0;j++)

{

if(min<MIN[i][j])

min=MIN[i][j];

MIN[i][j]=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间为8，结果正确；ABC间为14，结果正确；五：分析与探讨

经测试，结果正确，并让同队成员来测试，测试结果也正确。

待改进地方（1）没有考虑地板上有插座（2）没有考虑门的影响

解决方案：（1）定义插座参数m为5时表示插座在地板上，地板和每面墙为临面，则插座在地板上时的计算方法归结到第一种if条件中即可

（2）考虑门时可将门固定在一面墙上，比如1号墙（xz面），则所有连线中经过1号墙的

连线多一条判断语句，即判断连线在门上面过连线短还是在门下面过连线短，即可解决。

第二篇：数据结构课程设计报告敢死队问题

华北科技学院

课程设计说明书

（数据结构课程设计）

班级: 信管B08-1 姓名: 陈秋苗

学号： 200807034118

设计题目：敢死队问题

设计时间:__20##-9-6_____至___20##-9-17____

指导教师:______兰芸__________________

评语:________________________________

_________________________________________

评阅成绩:＿＿＿＿评阅教师:＿＿＿＿＿

《数据结构》课程设计实验报告

开课实验室：基础实验室一 20## 年9 月16 日

相关推荐

数据结构课程设计报告

第二篇：数据结构课程设计报告敢死队问题

专栏推荐