课程设计报告-- 小区网络光纤的铺设

课程设计报告--小区网络光纤的铺设本文简介：广东海洋大学信息学院课程设计报告设计题目小区网络光纤的铺设课程名称数据结构姓名（学号）庞东兴（201211621165）刘凯（201211621121）梁杰生（201211621118）联系电话13726907179（67）专业名称计算机科学与技术所在班级计算机科学与技术1班指导教师谢仕义教师职称教

课程设计报告--小区网络光纤的铺设本文内容：

广东海洋大学信息学院

课程设计报告

设计题目

小区网络光纤的铺设

课程名称

数据结构

姓名（学号）

庞东兴（201211621165）

刘凯（201211621121）

梁杰生（201211621118）

联系电话

13726907179（67）

专业名称

计算机科学与技术

所在班级

计算机科学与技术

1

班

指导教师

谢仕义

教师职称

教授

起止时间

2013

年10月29日至

2013年12月6日

评定成绩

一、

课程设计的主要内容

设计数据结构和算法，实现居民小区之间网络光纤铺设的最佳方案选择，主要内容如下：需要在某个城市n个居民小区之间铺设网络光纤，假设任意两个居民小区之间均需要铺设光纤，则在这n个居民小区之间只需要铺设n-1条光纤即可形成一个网络，但由于地理环境不同，所需要的代价也不尽相同。本课程设计要求事先随机生成任意居民小区之间铺设网络光纤的代价，并将代价存入文件，然后设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间的网络，又能使网络光纤铺设的代价最小，最终以图形形式输出所设计的最佳方案。

二、

功能和结构设计

1、克鲁斯卡尔算法：

1

克鲁斯卡尔算法的思想：

设无向连通网为G=（V，E），令G的最小生成树为T=（U，TE）,其初态为U=V，TE={}，这样T中个顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，依次考察边集E中的各条边。若被考察边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下来，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。

2

算法过程描述：

1.

初始化：U=V;

TE={};

2.

重复下述操作直到T中的连通分量个数为1；

2、1

在E中寻找最短边（U,V）；

2、2

如果顶点u、v位于T的两个不同连通分量，则

2

.

2

.

1、

将边（u、v）并入TE；

2

.

2

.

2、

将这两个连通分量合为一个；

2、3

在E中标记边（u，v），使得（u，v）不参加后续最短边的选取；

2、

模块分析

根据对模型的功能分析，该管道铺设设计可以具有以下功能：

①．

网络光纤铺设信息的输入；

②．

最小生成树信息的输出；

3、

抽象数据类型分析

Vertex[]

居民区

Edge[][]

邻接矩阵储存居民区的关系

R[]

居民区之间的距离

vertexNum

表示居民区数量

edgeNum

表示居民区的路线数目

4、

功能分析

信息输入：

程序输出：

最短路径：

三、

流程图和算法设计

//居民区数据输入

cout>vertexNum;

cout>vertex[i];

cout>edgeNum;

//二维数组存储居民区信息

cout>n>>m>>k;

Edge[n][m]=k;

Edge[m][n]=k;

R[i]=k;

}

cout::InsertSort()

{

int

k;

for(int

i=1;i::Kruskal()

{

Sum=0;

int

i,b=0,d=0,num,vex1,vex2;

for(i=0;ivertexNum*(vertexNum-1)/2

N

Y

cin>>c

edgeNum=c

输权值(Edge[n][m]),并赋值给R[i]

对R[i]

直接插入排序

Kruskal算法

输出图形

计算代价

结束

四、

源程序代码

#ifndef

Graph_H

#define

Graph_H

const

int

MaxVertex=10;

const

int

MaxEdge=100;

struct

EdgeType

{

int

from,to;

int

weight;

};

template

class

Graph

{

public:

Graph();

~Graph(){}

void

Kruskal();

void

InsertSort();

void

BubbleSort1();

int

FindRoot(int

a[],int

n);

void

outSum();

void

Price();

void

Print();

private:

Datatype

vertex[MaxVertex];

int

Edge[MaxVertex][MaxVertex];

EdgeType

edge[MaxEdge];

EdgeType

edgeP[MaxEdge];

int

parent[MaxVertex];

int

vertexNum,edgeNum;

int

R[MaxEdge];

int

Sum;

int

price;

};

#endif

#include

using

namespace

std;

#include

“Graph.h“#include

#include

#include

#include

#include

template

Graph::Graph()

{

getch();

int

i,j,k,n,m;

cout>vertexNum;

cout>vertex[i];

cout>edgeNum;

coutvertexNum*(vertexNum-1)/2)

{

int

c;

cout>c;

edgeNum=c;

}

for(i=0;i>n>>m>>k;

Edge[n][m]=k;

Edge[m][n]=k;

R[i]=k;

}

cout

void

Graph::InsertSort()

{

int

k;

for(int

i=1;i

void

Graph::BubbleSort1()

{

int

count=0;

while(count!=edgeNum)

{

for(int

i=0;i

void

Graph::Kruskal()

{

Sum=0;

int

i,b=0,d=0,num,vex1,vex2;

for(i=0;i

int

Graph::FindRoot(int

parent[],int

v)

{

int

t=v;

if(parent[t]>-1)

t=parent[t];

return

t;

}

template

void

Graph::outSum()

{

cout

void

Graph::Price()

{

cout>price;

cout

void

Graph::Print()

{

int

x1,x2,y1,y2;

initgraph(500,500);

if(vertexNum>0){

circle(100,200,25);

outtextxy(100,200,vertex[0]);

if(vertexNum>1){

circle(250,100,25);

outtextxy(250,100,vertex[1]);

if(vertexNum>2){

circle(150,350,25);

outtextxy(150,350,vertex[2]);

if(vertexNum>3){

circle(350,350,25);

outtextxy(350,350,vertex[3]);

if(vertexNum>4){

circle(400,200,25);

outtextxy(400,200,vertex[4]);

if(vertexNum>5)circle(250,250,25);

outtextxy(250,250,vertex[5]);}}}}}

for(int

n=0,k=0;k

using

namespace

std;

#include

“Graph.cpp“#include

#include

int

main()

{

int

a1;

for(a1=0;a1G;

G.InsertSort();

G.BubbleSort1();

G.Kruskal();

G.outSum();

G.Price

();

getch();

G.Print

();

cout<

for(a1=0;a1<15;a1++)

cout<<““;

for(a1=0;a1<25;a1++)

cout<<“*“;

cout<

for(a1=0;a1<15;a1++)

cout<<““;

cout<<“*

谢

谢

您

的

使

用

!“<

for(a1=0;a1<15;a1++)

cout<<““;

for(a1=0;a1<25;a1++)

cout<<“*“;

cout<

return

0;

}

五、

课程设计总结

经过两个多星期的不懈努力，我们小组终于完成本次课程设计一一《网络光纤铺设的最佳方案选择》，我们选用克鲁斯卡尔算法进行程序设计。首先，我们对程序的大概框架进行构想，设计好基本的逻辑框架，然后针对克鲁斯卡尔算法进行程序编写，对于高级程序员来说，虽然bug可以使程序崩溃，但他们依然可以闲庭信步般把问题解决，可是对于我们这些正在成长中的初级程序员来说，那就是一个灾难，需要我们一起扛才能度过难关，于是我们的合作精神就被发挥得淋漓尽致了，不管对外还是对内，我们这些菜鸟程序员都是一家子，处理分析问题就跟快，完成了编写，再经过多次的调试，终于完成本次程序设计。

通过本次程序设计，使我们对本学期学习的数据结构有了进一步的了解，巩固上一学年所学的知识；而且，我们对程序设计的算法有了基本的认识，同时，让我们知道算法对于一个程序来说是非常重要的，好的程序就应该要用好的算法；本次课程设计中涉及到图形的处理，但我们对于图形是一无所知的，经过在多种渠道的查阅，最后通过使用C++图形库EasyX实现图形处理。

本次程序设计使我们学会了很多，巩固课本所学的知识的同时，也掌握一些课外的有关程序设计的知识，希望以后能够编写出更好的程序！

六、

参考资料

1、胡明

《数据结构》（C++版）

清华大学出版社

2、张勇

《C++语言程序设计教程》（第二版）

清华大学出版社

3、C++语言的图形库EasyX