计算机网络生成树实验报告
实验八、九生成树配置—生成树协议STP和快速生成树协议RSTP
一．实验名称
生成树协议STP、快速生成树RSTP
二．实验目的
理解生成树协议STP和快速生成树协议RSTP
三．背景描述
某学校为了开展计算机教学和网络办公，建立了一个计算机教室和一个校办公区，这两处的计算机网络通过两台交换机互联组成内部校园网，为了提高网络的可靠性，网络管理员用2条链路将交换机互联，现要在交换机上做适当配置，使网络避免环路。
本实验以2台S3550-24交换机为例，2台交换机分别命名为SwitchA和SwitchB。PC1和PC2在同一个网段，假设IP地址分别为192.168.0.137，192.168.0.136，网络掩码为255.255.255.0。
四.实验功能
使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。
五.实验步骤
1.生成树协议STP
步骤1.在每台交换机说那个开启生成树协议。
SwitchA>enable 14
Password:
SwitchA#configure terminal
Enter configuration commands, one per line. End with CNTL/Z.
SwitchA(config)#spanning-tree
2009-10-16 19:10:41 @5-CONFIG:Configured from outband
SwitchA(config)#end
2009-10-16 19:10:43 @5-CONFIG:Configured from outband
验证测试：验证生成树协议已经开启
SwitchA#show spanning-tree
StpVersion : MSTP
SysStpStatus : Enabled
BaseNumPorts : 24
MaxAge : 20
HelloTime : 2
ForwardDelay : 15
BridgeMaxAge : 20
BridgeHelloTime : 2
BridgeForwardDelay : 15
MaxHops : 20
TxHoldCount : 3
PathCostMethod : Long
BPDUGuard : Disabled
BPDUFilter : Disabled
###### MST 0 vlans mapped : All
BridgeAddr : 00d0.f8ff.837c
Priority : 32768
TimeSinceTopologyChange : 0d:0h:6m:47s TopologyChanges : 0
DesignatedRoot : 800000D0F8FF837C
RootCost : 0
RootPort : 0
CistRegionRoot : 800000D0F8FF837C
CistPathCost : 0
SwitchA#show spanning-tree interface fastethernet 0/1
PortAdminPortfast : Disabled
PortOperPortfast : Disabled
PortAdminLinkType : auto
PortOperLinkType : point-to-point
PortBPDUGuard: Disabled
PortBPDUFilter: Disabled
###### MST 0 vlans mapped : All
PortState : discarding
PortPriority : 128
PortDesignatedRoot : 800000D0F8FF837C PortDesignatedCost : 0
PortDesignatedBridge : 800000D0F8FF837C PortDesignatedPort : 0000
PortForwardTransitions : 0
PortAdminPathCost : 0
PortOperPathCost : 0
PortRole : disabledPort
步骤2：设置生成树模式
SwitchA#configure terminal
Enter configuration commands, one per line. End with CNTL/Z. SwitchA(config)#spanning-tree mode stp
2009-10-16 19:12:31 @5-CONFIG:Configured from outband SwitchA(config)#end
2009-10-16 19:12:33 @5-CONFIG:Configured from outband 验证测试：验证生成树协议模式为802.ID
SwitchA#show spanning-tree
StpVersion : STP
SysStpStatus : Enabled
BaseNumPorts : 24
MaxAge : 20
HelloTime : 2
ForwardDelay : 15
BridgeMaxAge : 20
BridgeHelloTime : 2
BridgeForwardDelay : 15
MaxHops : 20
TxHoldCount : 3
PathCostMethod : Long
BPDUGuard : Disabled
BPDUFilter : Disabled
BridgeAddr : 00d0.f8ff.837c
Priority : 32768
TimeSinceTopologyChange : 0d:0h:8m:30s TopologyChanges : 0
DesignatedRoot : 800000D0F8FF837C
RootCost : 0
RootPort : 0
SwitchA#configure terminal
Enter configuration commands, one per line. End with CNTL/Z. SwitchA(config)#spanning-tree priority 4096
2009-10-16 19:13:14 @5-CONFIG:Configured from outband SwitchA(config)#end
2009-10-16 19:13:17 @5-CONFIG:Configured from outband SwitchA#show spanning-tree
StpVersion : STP
SysStpStatus : Enabled
BaseNumPorts : 24
MaxAge : 20
HelloTime : 2
ForwardDelay : 15
BridgeMaxAge : 20
BridgeHelloTime : 2
BridgeForwardDelay : 15
MaxHops : 20
TxHoldCount : 3
PathCostMethod : Long
BPDUGuard : Disabled
BPDUFilter : Disabled
BridgeAddr : 00d0.f8ff.837c
Priority : 4096
TimeSinceTopologyChange : 0d:0h:9m:13s
TopologyChanges : 0
DesignatedRoot : 100000D0F8FF837C
RootCost : 0
RootPort : 0
在SwitchB上做完验证后，将两个交换机的接口1和接口2分别连起来，然后再将其网线换到右端，将其另一端接到交换机上，然后进行ping连接，运行cmd，ping 192.168.0.53,可以看到先是连接着的，若把1接口拔掉，就会出现30个丢包信息。
2.快速生成树协议RSTP
步骤1：开启生成树协议
SwitchA>enable 14
Password:
SwitchA#configure terminal
Enter configuration commands, one per line. End with CNTL/Z.
SwitchA(config)#spanning-tree
2009-10-16 19:31:08 @5-CONFIG:Configured from outband
SwitchA(config)#end
2009-10-16 19:31:10 @5-CONFIG:Configured from outband
SwitchA#show spanning-tree
StpVersion : STP
SysStpStatus : Enabled
BaseNumPorts : 24
MaxAge : 20
HelloTime : 2
ForwardDelay : 15
BridgeMaxAge : 20
BridgeHelloTime : 2
BridgeForwardDelay : 15
MaxHops : 20
TxHoldCount : 3
PathCostMethod : Long
BPDUGuard : Disabled
BPDUFilter : Disabled
BridgeAddr : 00d0.f8ff.837c
Priority : 4096
TimeSinceTopologyChange : 0d:0h:1m:36s
TopologyChanges : 0
DesignatedRoot : 100000D0F8FF837C
RootCost : 0
RootPort : 0
显示交换机接口fastethernet0/1的状态
SwitchA#show spanning-tree interface fastethernet0/1
PortAdminPortfast : Disabled
PortOperPortfast : Disabled
PortAdminLinkType : auto
PortOperLinkType : shared
PortBPDUGuard: Disabled
PortBPDUFilter: Disabled
PortState : discarding
PortPriority : 128
PortDesignatedRoot : 100000D0F8FF837C PortDesignatedCost : 0
PortDesignatedBridge : 100000D0F8FF837C PortDesignatedPort : 8001
PortForwardTransitions : 2
PortAdminPathCost : 0
PortOperPathCost : 2000000
PortRole : disabledPort
显示交换机接口fastethernet0/2的状态
SwitchA#show spanning-tree interface fastethernet 0/2
PortAdminPortfast : Disabled
PortOperPortfast : Disabled
PortAdminLinkType : auto
PortOperLinkType : point-to-point
PortBPDUGuard: Disabled
PortBPDUFilter: Disabled
PortState : forwarding
PortPriority : 128
PortDesignatedRoot : 100000D0F8FF837C PortDesignatedCost : 0
PortDesignatedBridge : 100000D0F8FF837C PortDesignatedPort : 8002
PortForwardTransitions : 2
PortAdminPathCost : 0
PortOperPathCost : 200000
PortRole : designatedPort
设置生成树模式
SwitchA#configure terminal
Enter configuration commands, one per line. End with CNTL/Z. SwitchA(config)#spanning-tree mode rstp
2009-10-16 19:32:48 @5-CONFIG:Configured from outband SwitchA(config)#end
2009-10-16 19:32:51 @5-CONFIG:Configured from outband
SwitchA#show spanning-tree
StpVersion : RSTP
SysStpStatus : Enabled
BaseNumPorts : 24
MaxAge : 20
HelloTime : 2
ForwardDelay : 15
BridgeMaxAge : 20
BridgeHelloTime : 2
BridgeForwardDelay : 15
MaxHops : 20
TxHoldCount : 3
PathCostMethod : Long
BPDUGuard : Disabled
BPDUFilter : Disabled
BridgeAddr : 00d0.f8ff.837c
Priority : 4096
TimeSinceTopologyChange : 0d:0h:3m:16s TopologyChanges : 0
DesignatedRoot : 100000D0F8FF837C
RootCost : 0
RootPort : 0
设置交换机优先级
SwitchA#configure terminal
Enter configuration commands, one per line. End with CNTL/Z. SwitchA(config)#spanning-tree priority 8192
2009-10-16 19:33:18 @5-CONFIG:Configured from outband SwitchA(config)#end
2009-10-16 19:33:20 @5-CONFIG:Configured from outband SwitchA#show spanning-tree
StpVersion : RSTP
SysStpStatus : Enabled
BaseNumPorts : 24
MaxAge : 20
HelloTime : 2
ForwardDelay : 15
BridgeMaxAge : 20
BridgeHelloTime : 2
BridgeForwardDelay : 15
MaxHops : 20
TxHoldCount : 3
PathCostMethod : Long
BPDUGuard : Disabled
BPDUFilter : Disabled
BridgeAddr : 00d0.f8ff.837c
Priority : 8192
TimeSinceTopologyChange : 0d:0h:3m:45s TopologyChanges : 0
DesignatedRoot : 200000D0F8FF837C
RootCost : 0
RootPort : 0
步骤4.综合验证测试
验证接口1和2 的状态
SwitchA>enable 14
Password:
SwitchA#
2009-10-16 19:18:56 @4-TOPOCHANGE:Topology is changed SwitchA#show spanning-tree interface fastEthernet0/1
PortAdminPortfast : Disabled
PortOperPortfast : Disabled
PortAdminLinkType : auto
PortOperLinkType : point-to-point
PortBPDUGuard: Disabled
PortBPDUFilter: Disabled
PortState : forwarding
PortPriority : 128
PortDesignatedRoot : 200000D0F8FF837C PortDesignatedCost : 0
PortDesignatedBridge : 200000D0F8FF837C PortDesignatedPort : 8001
PortForwardTransitions : 3
PortAdminPathCost : 0
PortOperPathCost : 200000
PortRole : rootPort
SwitchA#show spanning-tree interface fastEthernet0/2
PortAdminPortfast : Disabled
PortOperPortfast : Disabled
PortAdminLinkType : auto
PortOperLinkType : point-to-point
PortBPDUGuard: Disabled
PortBPDUFilter: Disabled
PortState :discarding
PortPriority : 128
PortDesignatedRoot : 200000D0F8FF837C
PortDesignatedCost : 0
PortDesignatedBridge : 200000D0F8FF837C
PortDesignatedPort : 8002
PortForwardTransitions : 3
PortAdminPathCost : 0
PortOperPathCost : 200000
PortRole : alternatePort
SwitchA#
2009-10-16 19:20:36 @5-LINKUPDOWN:Fa0/1 changed state to down s
2009-10-16 19:20:36 @4-TOPOCHANGE:Topology is changed
% Incomplete command.
SwitchA#show spanning-tree interface fastEthernet0/2
PortAdminPortfast : Disabled
PortOperPortfast : Disabled
PortAdminLinkType : auto
PortOperLinkType : point-to-point
PortBPDUGuard: Disabled
PortBPDUFilter: Disabled
PortState : learning
PortPriority : 128
PortDesignatedRoot : 200000D0F8FF837C
PortDesignatedCost : 0
PortDesignatedBridge : 200000D0F8FF837C
PortDesignatedPort : 8002
PortForwardTransitions : 3
PortAdminPathCost : 0
PortOperPathCost : 200000
PortRole : rootPort
SwitchA#
2009-10-16 19:21:06 @4-TOPOCHANGE:Topology is changedshow spanning-tree interfa ce fastEthernet0/2
PortAdminPortfast : Disabled
PortOperPortfast : Disabled
PortAdminLinkType : auto
PortOperLinkType : point-to-point
PortBPDUGuard: Disabled
PortBPDUFilter: Disabled
PortState : forwarding
PortPriority : 128
PortDesignatedRoot : 200000D0F8FF837C
PortDesignatedCost : 0
PortDesignatedBridge : 200000D0F8FF837C
PortDesignatedPort : 8002
PortForwardTransitions : 4
PortAdminPathCost : 0
PortOperPathCost : 200000
PortRole : rootPort
将接口1down后，接口2由discarding—learning—forwarding
六.实验感想
这次实习的主要内容是生成树配置-生成树协议STP和快速生成树协议RSTP。按照书上的要求完成操作后，连好相应的线，第一个实验后出现了丢包现象；第二个实验虽然不知道与第一个实验有什么具体区别，丢包数不同，也顺利完成了任务。
最小生成树问题课程设计报告
数据结构课程设计 目录 一. 设计目的.................................................................................................. 错误！未定义书签。 二. 设计内容 (1) 三．概要设计 (1) 1、功能模块图 (1) 2、各个模块详细的功能描述 (2) 四．详细设计 (3) 1．主函数和其他函数的伪码算法 (3) 2、主要函数的程序流程图 (7) 3、函数之间的调用关系图 (15) 五．测试数据及运行结果 (15) 1．正常测试数据及运行结果 (16) 2、非正常测试数据及运行结果 (17) 六．调试情况，设计技巧及体会 (18) 七．参考文献 (19) 八．附录：源代码 (19)
一. 设计目的 课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼： 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 二. 设计内容 最小生成树问题: 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 三．概要设计 1、功能模块图
武汉大学计算机网络实验报告 (2)
武汉大学教学实验报告 动力与机械学院能源动力系统及自动化专业2013 年11 月10 日
一、实验操作过程 1.在仿真软件packet tracer上按照实验的要求选择无线路由器，一般路由器和PC机构建一个无线局域网，局域网的网络拓扑图如下： 2.按照实验指导书上的表9.1（参数配置表）对路由器，ＤＮＳ服务器，ＷＷＷ服务器和ＰＣ机进行相关参数的配置： 服务器配置信息（子网掩码均为255.255.255.0） 主机名IP地址默认网关 DNS 202.2.2.1 202.2.2.2 WWW 202.3.3.1 202.3.3.3 路由器配置信息（子网掩码均为255.255.255.0） 主机名型号IP地址默认网关时钟频率ISP 2620XM e1/0:202.2.2.2 e1/1:202.3.3.3 s0/0:202.1.1.2 64000 Router2(Server) 2620XM f0/0:192.168.1.1 s0/0:202.1.1.1 Wireless Router Linksys WRT300N 192.168.1.2 192.168.1.1 202.2.2.1 备注：PC机的IP地址将通过无线路由器的设置自动分配 2.1 对router0（sever）断的配置： 将下列程序代码输到router0中的IOS命令行中并执行，对router0路由器进行设置。Router>en Router#conf t
2.3 WWW服务器的相关配置 对www服务器进行与DNS服务器相似的配置，包括它的IP地址，子网掩码，网关等，具体的相关配置图见下图： WWW服务器的相关配置图
最小生成树实验报告
数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析
1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={
数据结构课程设计最小生成树问题
数据结构与算法 课程设计报告 课程设计题目：最小生成树问题 专业班级：信息与计算科学1001班 姓名：谢炜学号：100701114 设计室号：理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师：杜洪波成绩： 一、摘要： 随着社会经济的发展，人们的生活已经越来越离不开网络，网络成为人们社 会生活的重要组成部分。我们希望拥有一个宽松的上网环境，以便更好的进行信 息的交流，在此我们有必要提升我们的网络传播速度。从某种程度上来说网络传
播速度代表着一个国家网络化程度的高低。 为了解决网络传输速度的问题我们希望在各个城市之间多架设一些通信网络线路，以缓解网络不够流畅不够便捷的问题。而在城市之间架设网络线路受到资金因素等的限制，我们希望找到一条捷径这样我们即达到了连接了各个城市网络的目的又节省了建设成本。 通过以上的分析我们得出解决此问题的关键在于找到一个短的路径完成网络的假设。在此我们想将各个城市抽象成为一个个节点，连接各个城市之间的网络作为连接各个节点的边。于是我们就将城市的空间分布抽象成为一个网络图，再将各条边的距离抽象成为各节点之间的权值。在原来的基础上建立一个带有权值的网络图。于是原有的问题就转化为找图的最小生成树问题。 我们利用普利姆算法和卡鲁斯卡尔算法找到我们所需要的最小的生成树。 二、问题分析 在n个城市间建立通信网络，需架设n-1条路线。求解如何以最低的经济代价建设此通信网，这是一个最小生成树问题。我们可以利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。将城市之间的距离当做网中各点之间的权值。 三、实现本程序需要解决的问题 （1）如何选择存储结构去建立一个带权的网络； （2）如何在所选存储结构下输出这个带权网络； （3）如何实现普利姆算法的功能； （4）如何从每个顶点开始找到所有的最小生成树的顶点； （5）如何输出最小生成树的边及其权值 此问题的关键就是利用普利姆算法，找到一个最小上的生成树，在一个就是输出我们所需要的信息，在此我们将各个城市看做是网中的各个顶点城市之间的距离看做是个顶点之间的权值。现在我们问题做如下的分析： 这个问题主要在于普利姆算法的实现。我们将各个城市的空间分布抽象成一个带有权值的网络，这个权值就是任意两个城市之间，各个城市就看做是网络的各个顶点。 我们建立的输入的数据格式为：首先提示输入带权的顶点数目，我定义为整形的数据型，然后输入每条边的信息，即边的两个顶点之间的权值，以十进制整数类型数据，这样我们就建立了一个带权的网络。 问题的输出我是将我们所得到的最小生成树的路线输出出来。 题目的要求就是我们在n个城市之间架设网络得到的最为经济的架设方法，我们进行以上的工作就是在找我们所需要的最小生成树，已解决我们的问题。 四、算法思想 普利姆算法求最小生成树的主要思想 假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V),TE={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{E}）为N的最小生成树。
最小生成树的Prim算法提高型实验报告
黄冈师范学院 提高型实验报告 实验课题最小生成树的Prim算法 （实验类型：□综合性■设计性□应用性） 实验课程算法程序设计 实验时间 2010年12月24日 学生姓名周媛鑫 专业班级计科 0801 学号 200826140110
一．实验目的和要求 （1）根据算法设计需要, 掌握连通网的灵活表示方法; （2）掌握最小生成树的Prim算法; （3）熟练掌握贪心算法的设计方法; 二．实验条件 （1）硬件环境：实验室电脑一台 （2）软件环境：winTC 三．实验原理分析 （1）最小生成树的定义： 假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。 （2）构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u.v)的最小生成树。 （3）普里姆（Prim）算法即是利用MST性质构造最小生成树的算法。算法思想如下： 假设N=(V,{E})和是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u, v) ∈E 中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。 四．实验步骤 （1）数据结构的设计： 采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作： 邻接矩阵的抽象数据结构定义： #define INFINITY INT_MAX //最大值 #define MAX_ERTEX_NUM 20 //最大顶点数 typedef enum {DG,DN,UDG,UDN}GraphKind;//{有向图,有向网，无向网，无向图} typedef struct Arc Cell{ VRType adj ; // VRType 是顶点关系的类型。对无权图用1和0表示相邻否；InfoType * info; //该弧相关信息的指针 }ArcCell ，AdjMatrix [ MAX_VERTEX_NUM][MAX_VERTEX_NUM]； Typedef struct { VertexType vexs [ MAX_VERTEX_NUM] ; //顶点向量
最小生成树-实验报告
实验五最小生成树 一、需求分析 1、本程序の目の是要建设一个最经济の网，，输出相应の最小生成树。在这里都用整型数来代替。 2、测试数据 见下程序。 二、概要设计 主程序： int main() { 初始化； while (条件) { 接受命令; 处理命令; } return 0; } 三、详细设计 #include
{ char adjvex; int lowcost; }Close,close[MAX_VERTEX_NUM]; typedef struct ArcNode { int adjvex; ArcNode *nextarc; int info; }ArcNode; typedef struct VNode { char data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList verties; int vexnum,arcnum; }ALGraph; ALGraph G;//对象G int LocateVek(ALGraph ,char );//返回结点位置 int minimum(close);//返回最小数 void MinSpanTree_PRIM(ALGraph,char);//最小生成树 void Create(ALGraph &);//创建邻接表 int main() { char a;int i=1; Create(G); /*for(int i=1;i<=G.vexnum;i++) { for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc) cout<
数据结构课程设计报告java最小生成树
上海电力学院 数据结构（JAVA）课程设计 题目:____最小生成树_______ 学生姓名：_****___________ 学号：_____*******_______ 院系：计算机科学与技术学院 专业年级： ______*****___级 20**年 *月**日
目录 1.设计题目 (1) 2.需求分析 (1) 1）运行环境 (1) 2）输入的形式和输入值的范围 (1) 3）输出的形式描述 (1) 4）功能描述 (1) 5）测试数据 (1) 3.概要设计 (1) 1）抽象数据类型定义描述 (1) .2）功能模块设计 (1) 3）模块层次调用关系图 (2) 4.详细设计。实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。 (2) 5.调试分析。包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。 (6) 6.用户使用说明。详细列出每一步的操作说明。 (7) 7. 测试结果 (7) 8.附录：程序设计源代码 (9)
一、设计题目 1).问题描述 若要在 n 个城市之间建设通信网络，只需要架设n-1 条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 2). 基本要求 以邻接多重表存储无向带权图，利用克鲁斯卡尔算法或普瑞姆算法求网的最小生成树。 二、需求分析 1）运行环境 软件在JDK运行，硬件支持windows系统 2）输入的形式和输入值的范围 自动生成顶点数据在10~20之间；各个顶点之间权值在25~50之间；通过程序改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为edge edge[]={new edge(0,1,16),new（0,2,18）......}； 将已知顶点、权值通过其函数输入再生成其所对应最小生成树。 3）输出的形式描述 输出随机生成顶点个数以及各个顶点之间权值；然后输出本次生成顶点之间构成的最小生成树。
计算机网络实验报告-答案.
计算机网络实验报告 专业计算机科学与技术 班级计102 学号 109074057 姓名王徽军 组号一组D 指导教师毛绪纹 安徽工业大学计算机学院 二○一二年十二月
目录 实验总体说明 (3) 实验一以太网帧的构成 (3) 实验三路由信息协议RIP (9) 实验四传输控制协议TCP (11) 实验五邮件协议SMTP、POP3、IMAP (12) 实验六超文本传输协议HTTP (14)
实验总体说明 1．实验总体目标 配合计算机网络课程的教学，加强学生对计算机网络知识（TCP/IP协议）的深刻理解，培养学生的实际操作能力。 2．实验环境 计算机网络协议仿真实验室： 实验环境：网络协议仿真教学系统（通用版）一套 硬件设备：服务器，中心控制设备，组控设备，PC机若干台 操作系统：Windows 2003服务器版 3．实验总体要求 ●按照各项实验内容做实验，记录各种数据包信息，包括操作、观察、记录、分析， 通过操作和观察获得直观印象，从获得的数据中分析网络协议的工作原理； ●每项实验均提交实验报告，实验报告的内容可参照实验的具体要求，但总体上应包 括以下内容：实验准备情况，实验记录，实验结果分析，算法描述，程序段，实验过程中遇到的问题以及对思考问题的解答等，实验目的、实验原理、实验步骤不需要写入实验报告中。 实验一以太网帧的构成 实验时间：_____________ 成绩：________________ 实验角色：_____________ 同组者姓名：______________________________
练习一：领略真实的MAC帧 00000000: FF FF FF FF FF FF 8C 89 A5 75 71 10 06 05 14 55 ..q....U 00000010: 85 48 D2 78 62 13 47 24 58 25 00 00 00 00 00 00 .H襵b.G$X%...... 00000020: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 00000030: 00 00 00 00 00 00 00 00 00 00 00 00 ............ 练习二：理解MAC地址的作用 ●记录实验结果 表1-3实验结果 本机MAC地址源MAC地址目的MAC地址是否收到，为什么 主机B 8C89A5-7570BB 8C89A5-757113 8C89A5-7570C1 是，主机A与主机B接在同一共享模块 主机D 8C89A5-771A47 8C89A5-757113 8C89A5-7570C1 是，主机C与主机D接在同一共享模块 主机E 8C89A5-757110 无无否，与主机A、C都不在同一共享模块 主机 F 8C89A5-7715F8 无无否，与主机A、C都不在同一共享模块 练习三：编辑并发送MAC广播帧 ●结合练习三的实验结果，简述FFFFFF-FFFFFF作为目的MAC地址的作用。 答：该地址为广播地址，作用是完成一对多的通信方式，即一个数据帧可发送给同一网段内的所有节点。 练习四：编辑并发送LLC帧 ●实验结果 帧类型发送序号N（S）接受序号N（R） LLC 001F 0 ●简述“类型和长度”字段的两种含义 答：一是如果字段的值小于1518，它就是长度字段，用于定义下面数据字段的长度；二是如果字段的值大于1536，用于定义一个封装在帧中的PDU分组的类型。 思考问题： 1.为什么IEEE802标准将数据链路层分割为MAC子层和LLC子层？ 答：出于厂商们在商业上的激烈竞争，IEEE的802委员会未能形成一个统一的、最佳的局域网标准，而是被迫制定了几个不同标准，如802.4令牌总线网、802.5令牌环网等。为了使数据链路层能更好地适应多种局域网标准，802委员会就将局域网的数据链路层拆成两个子层，即逻辑链路控制
Prim最小生成树算法实验报告材料
算法分析与设计之Prim 学院：软件学院学号：201421031059 ：吕吕 一、问题描述 1.Prim的定义 Prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。 2.实验目的 选择一门编程语言，根据Prim算法实现最小生成树，并打印最小生成树权值。 二、算法分析与设计 1.Prim算法的实现过程 基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U ＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作： 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。 Prim算法的核心:始终保持TE中的边集构成一棵生成树。 2.时间复杂度 Prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，N 为顶点数，而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。 三、数据结构的设计 图采用类存储，定义如下： class Graph { private: int *VerticesList; int **Edge; int numVertices; int numEdges; int maxVertices; public: Graph(); ~Graph(); bool insertVertex(const int vertex); bool insertEdge(int v1,int v2,int cost); int getVertexPos(int vertex); int getValue(int i); int getWeight(int v1,int v2); int NumberOfVertices();
最小生成树数据结构课程设计报告
河北科技大学 课程设计报告 学生姓名：白云学号：Z110702301 专业班级：计算机113班 课程名称：数据结构课程设计 学年学期： 2 01 3—2 014学年第2学期指导教师：郑广 2014年6月
课程设计成绩评定表
目录 一、需求分析说明 (1) 1.1最小生成树总体功能要求 (1) 1.2基本功能 (1) 1.3 模块分析 (1) 二、概要设计说明 (1) 2.1设计思路 (1) 2.2模块调用图 (2) 2.3数据结构设计 (2) 2.3.1.抽象数据类型 (2) 2.3.2方法描述 (2) 三、详细设计说明 (3) 3.1主函数模块 (3) 3.2邻接表输出子模块 (3) 3.3邻接矩阵输出子模块 (3) 3.4创建邻接矩阵子模块 (3) 3.5创建邻接表子模块 (3) 3.6 Prim子模块 (3) 3.7 Kruscal子模块 (4) 四、调试分析 (4) 4.1实际完成情况说明 (4) 4.2 出现的问题及解决方案 (4) 4.3程序中可以改进的地方 (4) 六、课程设计总结 (7) 七、测试数据 (7) 八、参考书目 (7)
一、需求分析说明 1.1最小生成树总体功能要求 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 1.2基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析 主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。 邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。 二、概要设计说明 2.1设计思路 问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。 1) 普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。 2) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。
福建农林大学计算机网络实验报告二
福建农林大学计算机与信息学院 实验报告 2015年10 月27 日
实验项目列表
实验报告 系：计算机科学专业：计算机科学与技术年级： 姓名：学号：实验室号：计算机号： 实验日期：2015 年10 月27 日指导教师签字：成绩： 报告退发(订正、重做) 实验二网络监听实验 一、实验目的 1、理解网络监听原理 2、熟悉网络监听方法 3、理解网络流量 4、掌握TCP/IP的主要协议和协议的层次结构 二、实验环境与设备 本实验在实际因特网环境下进行操作，需要的设备有：一台PC机，WireShark监听软件。WireShark监听软件可从网址：https://www.sodocs.net/doc/5b7502052.html,/下载。实验配置如图所示。 因特网 三、实验原理 1、网络协议分析器 如果使用Web浏览器或OICQ聊天这样的网络软件，必须有网络连接才能工作，然而，你知道它们在因特网上传送的是什么类型的信息吗？ 例如，计算机要对远程Web服务器发送什么数据来获取它需要的网页呢？计算机如何将邮件发给指定的人呢？ 可以通过网络协议分析器（如WireShark）来协助观察网络会话的细节。网络协议分析器是一个能记录所有网络分组，并以人们可读的形式显示的软件。在监听重流量网络时，允许用户过滤掉不想要的分组或查看感兴趣的特定分组，而且还能为用户提供所有分组的统计概要。 2、网络监听原理 在共享式局域网中，位于同一网段的每台主机都可以截获在网络中传输的所有数据，正常情况下，一个网卡只响应目的地址为单播地址和广播地址的MAC帧而忽略其它MAC帧，网卡接收这两种帧时，通过CPU产生一个硬件中断，然后由操作系统负责处理该中断，对数据
实验报告
算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房
目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示：
07_生成树实验
0分计。 4. 实验报告文件以PDF 格式提交。 【实验题目】生成树协议 【实验目的】理解快速生成树协议的配置及原理。使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 【实验内容】 (1)完成实验教程实例3-8的实验，回答实验提出的问题及实验思考。（P117） (2)抓取生成树协议数据包，分析桥协议数据单元（BPDU ）。 (3)在实验设备上查看VLAN 生成树，并学会查看其它相关重要信息。 【实验要求】 一些重要信息需给出截图。 注意实验步骤的前后对比！ 【实验记录】(如有实验拓扑请自行画出, 要求自行画出拓扑图) (1) 实例3-8 实验拓扑图如下：
步骤0： 将PC1和PC2配置好IP地址和掩码后按照拓扑图连接实验设备。 在PC1上启动Wireshark 软件观察包的数量变化如下： 此时已经产生了广播风暴。 两台交换机此时的生成树配置信息如下： 无生成树配置信息。 用PC1pingPC2时包增长情况如下：
可见此时包增长的更快，已经产生广播风暴，但是PC并未发生死锁。步骤1： 配置交换机A： 步骤2： 配置交换机B： 步骤3: 配置两交换机的快速生成树协议：
再按照拓扑图连接实验设备，此时包增长情况如下： 此时两PC间可以相互ping通，且无广播风暴。由此可见生成树协议的作用为避免网络中存在交换环路的时候产生广播风暴，确保在网络中有环路时自动切断环路。
步骤4：验证测试 SwitchA的生成树信息： SwitchB的生成树信息：
步骤5：设置交换机的优先级 将SwitchA的优先级设置为4096 步骤6: 验证SwitchA的优先级 当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入
最小生成树问题中北大学数据结构课程设计资料
中北大学 数据结构与算法课程设计 说明书 学院、系：软件学院 专业：软件工程 班级： 学生姓名：学号： 设计题目：最小生成树问题 起迄日期: 2015年1月12日- 2015年1月29日指导教师:王秀娟 2015 年1月 29 日
1需求分析 1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。 1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。 1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。 1.4程序通过人机交互实现数据的输入和输出。 2选题要求 设计内容： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性。 3程序设计方法及主要函数介绍 ADT Graph{ 数据对象V;V是具有相同特性的数据元素的集合，成为顶点集。 数据关系R： R = {VR} VR = {（v,w）|v,w为V集合中的元素，（v,w）表示v和w之间存在的路径} 基本操作P; CreateMGraph(MGraph *G) 初始条件：V是图的顶点集，VR是图的边的集合。 操作结果：按V和VR的定义构造图G，用邻接矩阵存储。 CreateALGraph(ALGraph *G)
离散数学 最小生成树
实验五 实验名称： 得到最小生成树 实验目的： 1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 2.掌握图论中的最小生成树及Prim 和 Kruskal 算法等，进一步能用它们来解决实际问题。 实验内容： 输入一个图的权矩阵，得到该图的生成树，用Kruskal算法的最小生成树，用Prim算法的最小生成树。
Kruskal算法 假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。 1）将所有顶点涂成红色； 2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红； 3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。 Prim算法 假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树: 1)初始化:U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。 2)在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U 中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。 3)如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。
n个城市最小生成树实验报告材料
数据结构 课程设计报告 起评分理论成绩实践成绩总成绩 院系： 专业： 班级： 学号： ： 教师： 时间：
目录 一、设计要求 (3) 1、问题描述 (3) 2、功能 (3) 3、数据 (3) 二、概述与分析 (3) 1、图 (3) 2、邻接矩阵 (3) 3、生成树 (4) 4、最小生成树 (5) 5、最小生成树的操作 (5) 三、程序设计及分析 (6) 四、流程图 (7) 1、模块结构流程图 (7) 2、Prim算法流程设计 (8) 五、测试分析 (8) 六、总结 (10) 七、源程序代码 (10)
一、设计要求： 1、问题描述 构造可以使n个城市连接的最小生成树。 2、功能 给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。本人采用的是Prim算法。 3、数据 城市间的距离网采用邻接矩阵表示（要求至少6个城市，10条边），邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 表示城市间距离网的邻接矩阵（要求至少6个城市，10条边） 二、概述与分析 1、图 图的定义：图G是有两个集合V和E组成，记做G=（V,E），其中V是定点的有限集合，记做V(G)，E是连接V的两个不同的顶点的边的有限集合，记做E(G)。 2、邻接矩阵 邻接矩阵是图的一种存储方法，它是表示顶点之间相邻关系的矩阵。设 G=(V,E)是具有n(n>0)个顶点的图，顶点的顺序依次为（v 0,v 1,… ,v n-1 ）,则G的 邻接矩阵A是n阶方阵，其定义如下。 1)如果G是无向图，则 1 (v i,v j ) ∈E(G) A[i][j]= 0 其他 2)如果G是有向图，则 1
最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日
题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。
计算机网络实验报告
农林大学计算机与信息学院 信息工程类 实验报告 课程名称：计算机网络 姓名： 系：计算机科学与技术系 专业：计算机科学与技术 年级：2011级 学号： 指导教师：周术成老师 职称： 2014年 5 月 4 日
农林大学计算机与信息学院实验报告 系：计算机与信息系专业：计算机科学与技术年级：2011 ：学号：实验课程：_ 计算机网络 实验室号____田C-305__ 计算机号：实验时间： 指导教师签字：成绩： 实验一以太网组网实验 1．实验目的和要求 1．熟悉局域网所使用的基本设备 2. 掌握以太网组建方法 3. 掌握网络连通性测试方法 2．实验原理 以太网事实上是一簇局域网技术，不同的以太网在链路层帧头的格式、电缆的类型和传输速度上有很大的差异以太网可以利用同轴电缆、双绞线、光缆等不同的传输介质进行组网，也可以运行10Mb/s、100Mb/s、1000Mb/s 的网络速度。不管采用何种传输介质，以及网络速度各不相同，只要是以太网，采用的都是CSMA/CD介质访问控制方法。即任何结点没有可预约的发送时间，所有结点平等地争用发送时间，并随机地发送数据。 组建局域网常用的传输介质为双绞线，作为10BASE-T 和100BASE-TX 以太网的传输介质，非屏蔽双绞线在组网中起着重要的作用。非屏蔽双绞线UTP 中的8 芯导线采用了不同的颜色，分成4 对，其中橙和橙白一对，绿和绿白一对，蓝和蓝白一对，棕和棕白一对。以太网使用的UTP 分为直通UTP 和交叉UTP。 UTP 双绞线有两种接法：T568A 标准和T568B 标准。 直通UTP：线的两头都按T568B 线序标准连接。 交叉UTP：线的一头按T568A 线序连接，另一头按T568B 线序连接。 组装不同类型的局域网需要不同的设备，10Base-T 和100Base-TX 组网所需要的设备有：UTP 电缆、以太网卡、10M/100M 集线器、以太网交换机等。现在的以太网在逻辑上采用星型拓扑结构，用这种拓扑结 构，每台计算机用电缆线连接到共享网络设备上，如集线器和交换机等。 集线器和交换机都是用以太网接口连接多台设备，然而，它们在实现上有很大不同。集线器是第1 层设备，是以太网的集中连接点，具有信号放大功能，扩大以太网的地理围。通常采用RJ-45 接口，计算 机或其他终端设备通过双绞线电缆与集线器相连。当数据到达集线器的一个端口后，集线器不进行过滤处 理，直接将收到的数据包复制并广播到所有其他的端口，而不管这些端口连接的设备是否需要这些数据。 因此，网络中集线器数量越多，整个网络的性能就越差。 一般以太网的拓扑既用到集线器也用到交换机，集线器连接到交换机端口上，计算机连接到集线器上。在这种配置里，连接在同一集线器的计算机能看到彼此传输的数据，并且一次只能有一个传输；但在
大数据结构课程设计-最小生成树
《数据结构》期末课程设计 题目第8题：最小生成树问题学院计算机学院 专业 班别 学号 姓名陈聪 2015年7月6日
一、需求分析 1、问题描述 若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。 2、基本要求 （1）利用克鲁斯卡尔算法求网的最小生成树。 （2）实现并查集。以此表示构造生成树过程中的连通分量。 （3）以文本形式输出生成树中各条边以及他们的权值。 3、实现提示 通讯线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机数函数产生。 图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组即边集数组表示图。 二、详细设计 根据课设题目要求，拟将整体程序分为三大模块，分别是：图的存储结构，并查集的实现，克鲁斯卡尔算法的实现。 1、边集数组的类型定义： typedef struct { int x, y; int w; }edge; x表示起点，y表示终点，w为权值。 2、并查集功能的实现由以下函数实现： Make_Set(int x)初始化集合； Find_Set(int x) 查找x元素所在的集合,回溯时压缩路径； Union(int x, int y, int w)合并x,y所在的集合。
3、克鲁斯卡尔算法的实现 该算法的实现位于主函数中： qsort(e, n, sizeof(edge), cmp); //将边排序 printf("最小生成树的各条边及权值为：\n"); for (i = 0; i < n; i++) { x = Find_Set(e[i].x); y = Find_Set(e[i].y); if (x != y ) { printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w); Union(x, y, e[i].w); } } 4、设计中还包含以下函数： （1）/* 比较函数，按权值(相同则按x坐标)非降序排序*/ int cmp(const void *a, const void *b) { if ((*(edge *)a).w == (*(edge *)b).w) { return (*(edge *)a).x - (*(edge *)b).x; } return (*(edge *)a).w - (*(edge *)b).w; } （2）快排函数qsort,包含在stdlib.h头文件里 qsort(e, n, sizeof(edge), cmp); （3）C语言提供的随机数函数srand( unsigned int seed ); 使用随机数函数如下： srand( (unsigned)time( NULL ) ); for( i = 0; i < n;i++ )