第一篇：计算机网络技术实践实验报告
计算机网络技术实践
实验报告
实验名称 _
姓 名___________________实 验 日 期： 学 号___________________实验报告日期：
同组人姓名_________________ 报 告 退 发：(订正、重做)同组人学号_ _______________________
一.环境（详细说明运行的操作系统，网络平台，机器的IP地址）
二.实验目的
；
；
三.实验内容及步骤（包括主要程序流程和函数说明，程序分工说明）
四.实验结果
五.实验中的问题及心得
六.实验思考
第二篇：计算机网络技术实践实验报告
计算机网络技术实践
实验报告
实验名称 实验三 RIP和OSPF路由协议的配置及协议流程
姓 名____ ______实 验 日 期： ____________________ 学 号___________实验报告日期： ____________________ 报 告 退 发：(订正、重做)
一.环境（详细说明运行的操作系统，网络平台，机器的IP地址） 操作系统：Windows7 网络平台：虚拟网络（软件Dynamips） IP地址：127.0.0.1 二.实验目的
在上一次实验的基础上实现RIP和OSPF路由协议
自己设计网络物理拓扑和逻辑网段，并在其上实现RIP和OSPF协议 通过debug信息详细描述RIP和OSPF协议的工作过程。
RIP协议中观察没有配置水平分割和配置水平分割后协议的工作流程； OSPF中需要思考为什么配置完成后看不到路由信息的交互？如何解决？
三.实验内容及步骤（包括主要配置流程，重要部分需要截图）
设计网络物理拓扑和逻辑网段
编写.net文件
autostart = false
[localhost] port = 7200 udp = 10000 workingdir =..tmp
[[router R0]]
image =..iosunzip-c7200-is-mz.122-37.bin
model = 7200
console = 3001
npe = npe-400
ram = 64
confreg = 0x2102
exec_area = 64
mmap = false
slot0 = PA-C7200-IO-FE
slot1 = PA-4T
s1/0 = R1 s1/1
s1/1 = R2 s1/2
s1/2 = R3 s1/3
[[router R1]]
image =..iosunzip-c7200-is-mz.122-37.bin
model = 7200
console = 3002
npe = npe-400
ram = 64
confreg = 0x2102
exec_area = 64
mmap = false
slot0 = PA-C7200-IO-FE
slot1 = PA-4T
f0/0 = PC1 f0/0
[[router R2]]
image =..iosunzip-c7200-is-mz.122-37.bin
model = 7200
console = 3003
npe = npe-400
ram = 64
confreg = 0x2102
exec_area = 64
mmap = false
slot0 = PA-C7200-IO-FE
slot1 = PA-4T
f0/0 = PC2 f0/0
[[router R3]]
image =..iosunzip-c7200-is-mz.122-37.bin
model = 7200
console = 3004
npe = npe-400
ram = 64
confreg = 0x2102
exec_area = 64
mmap = false
slot0 = PA-C7200-IO-FE
slot1 = PA-4T
f0/0 = PC3 f0/0
[[router PC1]]
model = 2621 ram = 20 image =..iosunzip-c2600-i-mz.121-3.T.bin mmap = False confreg = 0x2102 console = 3005
[[router PC2]]
model = 2621 ram = 20 image =..iosunzip-c2600-i-mz.121-3.T.bin mmap = False confreg = 0x2102 console = 3006
[[router PC3]]
model = 2621 ram = 20 image =..iosunzip-c2600-i-mz.121-3.T.bin mmap = False
confreg = 0x2102 console = 3007 启动Dynamips服务端，打开管理员控制台
-List
分别打开路由器和PC设置IP和PC的静态路由
现用R0 举例说明：
分别配置R0端口的ip地址
S1/0
S1/1
S1/2
以上即为R0的IP配置过程，由于R1、R2、R3和R0的配置过程类似，所以在此不在赘述。
对于PC的配置，除了IP外还得设置静态路由，如下图：
直接设置的默认的f0/0口，着实轻松了不少。
Rip的设置
同样用R0举例：
根据拓扑图，设置好network和neighbor,详细的可以看拓扑图。
设置好了上述的所有信息，就可以ping啦
PingPC2，成功！
PingPC3, 成功！
通过debug信息详细描述RIP协议的工作过程。
由图可知，为了避免在起始路由器和目的路由器之间的路径中出现回路，路由信息协议设定了每条路径中跳数的极限值。在路由信息协议中，每条路经中跳数的最大值设定为15。当跳数的值达到16时，路径将被认定为无限远，同时目的路由器也将被认定为无法达到。跳数极限值的引入避免了路径中出现
无限循环的回路。
如图所示，数据包通过以太网接口，广播到整个路由表，即分别送至10.1.1.1
20.1.1.1
30.1.1.1，然后再选择合适的端口，直到将数据包传递。
需要注意的是，RIP不能再两个网络之间同时使用多条路由。RIP选择一条最少路由器的路由器的路由（即最短路由），哪怕还存在另一条高速（低时延）但路由器较多的路由。同时，为了规范路由器的性能，在路由器资讯协
议中还定义了路由更新计时器，路由超时计时器，以及路由更新计时器。
无水平分割的debug信息：
水平分割是在距离矢量路由协议中最常用的避免环路发生的解决方案之一。
产生环路的一种情况是：路由器A将从路由器B学习到的路由信息又告诉给了路由器B。最终，路由器B认为通过路由器A能够到达目标网络，路由器A认为通过路由器B能够到达目标网络。路由数据包的时候，数据将在两个路由器间不停地循环，直至TTL的值为0，将此数据包丢弃。
水平分割的思想就是：在路由信息传送过程中，不再把路由信息发送到接收到此路由信息的接口上。从而在一定程度上避免了环路的产生。
观察无水平分割的图，其不能有效的避免出现的环路。 实现OSPF路由协议
其他类比设置，最后ping同即可
通过debug信息详细描述OSPF协议的工作过程。
由于cpu占用过多，电脑出现异常重启了……结果未能截下图……
作为一种链路状态的路由协议，OSPF将链路状态广播数据LSA（Link State Advertisement）传送给在某一区域内的所有路由器，这一点与距离矢量路由协议不同。运行距离矢量路由协议的路由器是将部分或全部的路由表传递给与其相邻的路由器。
四.实验结果（包括最终实验结果，需要截图）
均在实验过程中标出。
五.实验中的问题及心得（需要认真写，不要写空话、套话）
实验过程中的问题还是挺多的，从最初的安装Win_Pcap未果，一度以为是因为win7不支持，兼容模式后安装不上，于是在网上下载了一个最新的Win_Pcap才可行。
设计拓扑图的时候，一开始是想用一个路由器接多个PC的，可是后来选设备时C7200-IO-2FE不可用还是怎么，就是不能接上，后来又换c2600 和c3600时 发现都不匹配。说不能找到set_npe的信息，估计还是不适合吧，百度了下说仿真环境要更新……正好也是晚上做的，也没人问下，也只好作罢。
第一次设置idlepc的时候竟然没有带*的……
（这难道是导致后来ping的延迟都有点偏高的原因？）
写.net文件没有什么太大的问题，由于拓扑图和课件中的例子相差无几，也不怎么需要大的改动，就照猫画虎了。
在设置各个路由器与PC的ip 和静态路由的时候，操作经常有小失误，不得不重头再来，有ping不通的倒也好找，因为有很多的ip地址，可以用来发现是哪块的错误，由于设备有点小多，cpu很吃紧，后来打字都是一顿一顿的……不过最后还是ping通了，至于rip的设置 还是挺好理解的 设置network和neighbor，不过对于OSPF还是有点不怎么理解，到后边也有点发懵了。保持清醒很重要……不然一激动就很可能功亏一篑。
六.实验思考（需要认真写，不要写空话、套话）
对于自己ping PC的时候ping都是有点小高，是机子性能不
好？还是拓扑图本身存在的问题？ 但是确实能ping到 不过只是很关心几个点 几个叹号……或许确实要改进下，看他们的环形图的延迟都挺好，有时间再试下其他的拓扑结构。
对于rip的无水平分割 一直在想有什么用处…… 对于广播型网络，水平分割解决了很大问题 避免了环路，而对于非广播型的网络，水平分割的结果并不理想，描述说水平分割像泼出去的水 是不能收回的，意思是和源头彻底断开了，不能再回去了。
帧中继Hub-spoke结构的网络？ 跳数的极限值是怎么得到的？
怎样能提高路由效率，以及数据包传递的正确率？以后得多做一个 看看各种拓扑结构的优劣~ OSPF中需要思考为什么配置完成后看不到路由信息的交互？如何解决？
OSPF路由协议通过建立交互关系来交换路由信息，但是并不是所有相邻的路由器会建立OSPF交互关系。
OSPF协议是通过Hello协议数据包来建立及维护相邻关系的，同时也用其来保证相邻路由器之间的双向通信。OSPF路由器会周期性地发送Hello数据包，当这个路由器看到自身被列于其它路由器的Hello数据包里时，这两个路由器之间会建立起双向通信。在多接入的环境中，Hello数据包还用于发现指定路由器DR，通过DR来控制与哪些路由器建立交互关系。
两个OSPF路由器建立双向通信这后的第二个步骤是进行数据库的同步，数据库同步是所有链路状态路由协议的最大的共性。在OSPF路由协议中，数据库同步关系仅仅在建立交互关系的路由器之间保持。
当所有的配置都完成后，路由器之间的交互是稳定的，不会产生新的路由信息。因此在ospf工作是将路由器之间的链接断开即可看到其中的信息交互了。
第三篇：计算机网络技术实验报告（范文）
计算机网络技术实验报告
鹿弋炜11044209 计算机网络技术实验报告
班级： 120442
学号： 11044209
姓名： 鹿弋炜
实验一 网络命令使用
一、实验内容
1、ping命令
2、Netstat命令
2014年12月 计算机网络技术实验报告
鹿弋炜11044209
3、IPconfig
4、ARP
5、Tracert
6、NBtstat
2014年12月 计算机网络技术实验报告
鹿弋炜11044209
二、思考题：
1、你的计算机平时能正常上网，某天突然不能上网了，你能否查出是什么原因造成的？
可以通过ping命令从本地->本地IP->局域网其他IP->网关->远程主机一步步排查。
2、如何查出计算机的MAC地址？有多少种方法？
方法1：ipconfig /all
方法2：nbtstat-A IP Address
3、在同一个局域网内，知道对方的IP地址，如何查出它的主机名？
nbtstat-A IP Address-s
三、实验总结
2014年12月 3 计算机网络技术实验报告
鹿弋炜11044209
实验二 交换机的基本配置
一、实验内容
二、思考题
1、交换机有多少种配置模式？
用户模式、特权模式【全局配置模式（线路配置模式、接口配置模式）】
2、为了方便管理，交换机需开能telnet功能，请问如何配置交换机？
将交换机管理网口配置IP地址并设置telnet权限。
3、查看交换所胡配置信息用哪条命令？
switch#show running-config
三、实验总结
2014年12月 4
计算机网络技术实验报告
鹿弋炜11044209
实验三 路由器的基本配置
一、实验内容
Router>enable
//进入特权模式
Router#configure terminal
//进入全局配置模式。
RA(config)#hostname RA
//配置路由器名称为“RA”。
RA(config)#interface fastethernet 0/0 //进入路由器接口配置模式。
RA(config-if)#ip address 192.168.1.1 255.255.255.0 //配置路由器管理接口IP地址。
RA(config-if)#no shutdown //开启路由器fastethernet 0/1接口。RA(config)#interface serial 0/1
RA(config-if)#ip address 10.10.1.1 255.255.255.0
//配置路由器管理接口IP地址。
RA(config-if)#no shutdown
RA(config)#interface serial 1/0 //要手动添加模块，并确定是数据通信设备（DCE）还是数据终端设备（DTE）。
RA(config-if)#ip address 172.159.1.1 255.255.255.0
RA(config-if)#clock rate 64000 //如果是DCE接口，必须配时钟频率；另外一头自动适应为DTE接口，不需要配时钟频率。RA(config-if)#no shutdown
RA#show ip interface brief
//验证各个接口的IP地址已经配置和开启。同样地，对另外一台路由器端口进行配置。Router>enable
Router#configure terminal RB(config)#hostname RB
RB(config)#interface fastethernet 0/0 RB(config-if)#ip address 192.168.1.2 255.255.255.0 RB(config-if)#no shutdown
RB(config)#interface serial 1/0 //也需要手动添加模块，如果RA的serial 1/0口选择DCE接口，则接口就会自动选择为DTE接口，无须配时钟频率。RB(config-if)#ip address 192.168.3.1 255.255.255.0
RB(config-if)#no shutdown
RB#show ip interface brief
//验证各个接口的IP地址已经配置和开启。
2014年12月 计算机网络技术实验报告
鹿弋炜11044209
二、思考题
1、路由器有多少种配置模式？
有用户模式、特权模式、全局模式三种。
2、为了方便管理，路由器需开能telnet功能，请问如何配置路由器？
对管理网口配置IP地址和掩码，并设置telnet权限。
3、查看路由器所有配置信息用哪条命令？
Router #show running-config
4、如果不设置路由器远程登录密码与路由器特权模式密码，可能通过telnet访问路由器吗？
不能。
三、实验总结
2014年12月 6 计算机网络技术实验报告
鹿弋炜11044209 实验四 Web、FTP服务器的基本配置
一、实验内容
1、Web服务器
2、FTP服务器（Serv-U软件建立）
二、思考题
1、如果要禁止某个IP地址访问Web服务器，应该如何设置呢？（实验的时候可以根据自己的网络结构任意定一个IP地址，或者让老师定一个IP地址。）
在IIS设置中，右键单击网站名，选属性，选择目录安全性选项卡，在IP地址和域名限制中单击编辑，添加IP地址。
2、如果要禁止某一段IP地址访问Web服务器，应该如何设置呢？实验的时候老师可以根据实际的网络结构定一段IP地址。（提示：和子网掩码有关系）
在IIS设置中，右键单击网站名，选属性，选择目录安全性选项卡，在IP地址和域名限制中单击编辑，添加IP地址网段如192.168.1.0，子网掩码255.255.255.0。
3、如果在同一台Web服务器，要建立多个站点，有什么方法可以实现呢？请通过实验进行调试。Web服务器的虚拟目录有什么作用呢？请建一个虚拟目录，通过实验掌握它的设置及使用。
在IIS中添加一个新的站点，并设置对应的主机名。虚拟目录可以把不同物理目录集结在跟目录下方便文件共享。
2014年12月 计算机网络技术实验报告
鹿弋炜11044209
4、如果要禁止某个IP地址访问FTP服务器，应该如何设置呢？（实验的时候可以根据自己的网络结构任意定一个IP地址，或者让老师定一个IP地址。）
在FTP设置中IP访问规则加入指定IP地址。
5、如果要禁止某一段IP地址访问FTP服务器，应该如何设置呢？实验的时候老师可以根据实际的网络结构定一段IP地址。（提示：和子网掩码有关系）
在FTP设置中IP访问规则加入指定IP地址段如192.168.1.0，子网掩码设置为255.255.255.0。
6、FTP服务器的虚拟目录有什么作用呢？请新建一个虚拟目录，通过实验掌握它的设置及应用。
虚拟目录是将一个物理路径不在FTP主路径下的目录映射到主路径下，虚拟成为一个主目录下的子目录。方便文件的管理和访问。
三、实验总结
2014年12月 8 计算机网络技术实验报告
鹿弋炜11044209 实验五 Wireshark（Ethereal）抓包实验
一、实验内容
1、Ping抓包
2、FTP密码抓取
当输入ftp://guest:11044209@192.168.0.9时成功抓取到用户名guest和密码11044209
3、用FTP软件FileZilla连接服务器尝试抓取密码
成功获取用户名和密码
2014年12月 计算机网络技术实验报告
鹿弋炜11044209
二、思考题
如果我们是用文件传输协议FTP软件（例如：CuteFTP，LeapFTP等）登录ftp://192.168.0.1，还能捕获到FTP的登录密码吗？
当使用FTP软件FileZilla连接，也成功抓取了用户名密码。
三、实验总结
2014年12月 10
第四篇：计算机网络技术实践报告
计算机网络 课程设计报告
班 级： 电子商务1503班 指导教师： 高 星 学 号： 0729150318 姓 名： 刘 雅 男
一.校园网建设的需求分析..........................................................................................3 1.1 校园网的背景...................................................................................................................3
1.2 校园网的内容、意义和目的...........................................................................................3
1.2.1校园网的内容........................................................................................................3 1.2.2 校园网的意义.......................................................................................................4 1.2.3校园网的目的........................................................................................................4
二.网络拓扑结构...........................................................................................................................5
2.1 有线网络拓扑图...............................................................................................................5 2.2 无线网络.........................................................................................................................5 三． 校园网的实施方案.................................................................................................................6
3.1 综合布线...........................................................................................................................6 3.2 交换机的选择...................................................................................................................6 3.3服务器系统、设备的故障恢复及设置............................................................................6 四．服务安装与配置.......................................................................................................................7
4.1 DHCP的安装与配置..........................................................................................................8
4.1.1 目的及意义...........................................................................................................8 4.2.2 实现方法...............................................................................................................8 4.2.WEB实验的设计........................................................................................................11 4.3.电脑桌面远程控制实验设计.......................................................................................23 五．系统安全体系设计.................................................................................................................29 5.1物理层安全......................................................................................................................29 5.2网络层安全......................................................................................................................29 六.结束语.....................................................................................................................................30
远大中学校园网络组建实验报告
摘要：随着E时代的到来，网络越来越发挥起它无可替代的作用。信息资源的共享也为校园网络的发展带来无可比拟的优点。因而可根据校园网的应用需求对校园网进行了总体的设计，首先根据学校的性质、规模以及对计算机的使用，做出适合学校的网络概图；其次根据学校的网络建设目的，明确网络的结构和功能；最后根据学校的技术要求，准确的确定技术选题、线路分布、设备和软件的配置等，进而实施学校的网络组建的具体步骤。关键字：校园网 拓扑图 服务
一.校园网建设的需求分析
1.1 校园网的背景
随着人们对信息资源共享和信息交流的迫切需要，促使了网络技术的产生和快速发展。校园网络的使用也进入一个广泛使用的时期。校园网络的使用也提高了教研和科研的质量，改善了教研和科研的条件，同时也需要不断的健全自己的校园网络来满足日新月异的网络环境。怎样利用网络设备，对学校的网络做出一个新的规划，进一步发挥各种设备的功能，实现学校各项系统的集成，提高应用水平将是学校校园网建设的一个工作重点。
1.2 校园网的内容、意义和目的
1.2.1 校园网的内容
基于对我们学校的现状了解，以及世界网络的发展来看，我觉得有必要为我们的学校建设校园网，将为在校师生提供网络服务。校园网最终必须是一个集计算机网络技术、多项信息管理、办公自动化和信息发布等功能于一体的综合信息平台，并能够有效促进现有的管理体制和管理方法，提高学校办公质量和效率，以促进学校整体教学水平的提高。
根据校园网络项目以及实际情况，我们应该充分考虑学校的实际情况，注重设备选型的性能价格比，采用成熟可靠的技术，为学校设计成一个技术先进、灵活可用、性能优秀、可升级扩展的校园网络。考虑到学校的中长期发展规划，在网络结构、网络应用、网络管理、系统性能以及远程教学等各个方面能够适应未来的发展，最大程度地保护学校的投资。建立合理的校园网络建设方案。1.2.2 校园网的意义
学校借助校园网的建设，可充分利用丰富的网上应用系统及教学资源，发挥网络资源共享、信息快捷、无地理限制等优势，实现信息资源的共享。使教育与现代科技相结合，够提高教学质量和教学效率，提高学校现代化教学程度，不仅方便了老师们的办公，同时也为同学们课下咨询、查找资料提供了有利条件，为教研工作提供了极大的便利。
1.2.3校园网的目的
主要目标是根据某学校园区局域网建设需求，以满足目前校园网大多数应用为目标，在现有独立信息教室的基础上，将对学校办公楼、教学楼和平房辅助管理部门等几座主要建筑物构建校园网络。
在教学教育领域，资源共享、教学网络化、办公自动化无疑是大势所趋，为了让师生之间、教工之间达成互联互通，更加有利于教研工作的进行。二.网络拓扑结构
2.1 有线网络拓扑图
DNS服务器IIS服务器网管工作DHCP服务器Internet教学楼实验楼图书馆办公楼电脑室...............体育馆教师楼学生宿舍食堂............2.2 无线网络
无线网路指的是任何型式的无线电电脑网路，普遍和电信网路结合在一起，不需电缆即可在节点之间相互连结[1]。无线电信网路一般被应用在使用电磁波的摇控资讯传输系统，像是无线电波作为载波和实体层的网路。
正从应用需求方面考虑,无线网络很适合学校的一些不易于网络布线的场所应用。现在大部分校园都建有有线局域网,如何对原有网络进一步扩充,使校园的每个角落都处在网络中,形成真正意义上的校园网。三． 校园网的实施方案
3.1 综合布线
综合布线方案设计是网络布线的重中之重，没有好的设计，就不可能有好的布线系统。首先要清楚那些建筑物需要布线，建筑物中哪些房间需要布线；其次根据用户对数据输出量的需求决定网络应当采取何种网络连接设备和布线产品；最后要做到的是此设计不仅容纳网络中当前的用户，而且还应当保留网络的扩展能力，从而使得用户增加时网络依然能够基本满足增长的需要。
综合布线设计要做到：
1.资金允许的情况下，网络主干和垂直布线系统首选光纤做为通讯介质 2.费用预算内，对网络线路部分一次性充分铺足，还要预留冗余路线
3.架设通信线路时必须遵循最长距离限制的规范，而且在可能的情况下，线缆要尽可能的短。
3.2 交换机的选择
交换机分为二层交换机和三层交换机两种类型，其中二层交换机的工作原理是：（1）当交换机从某个端口收到一个数据包，它先读取包头中的源MAC地址，这样它就知道源MAC地址的机器是连在哪个端口上的；
（2）再去读取包头中目的MAC地址，并在地址表中查找相应的端口；（3）如表中有与这目的MAC地址对应的端口，把数据包直接复制到这端口上；（4）如表中找不到相应的端口则把数据包广播道所有端口上，当目的机器对原机器回应时，交换机又可以学习一目的MAC地址与哪个端口对应，在下次传送数据时就不再需要对所有端口进行广播了。
3.3 服务器系统、设备的故障恢复及设置
1.服务器系统应能代表当今计算机的最新技术，具有最先进的CPU技术，非常快的计算速度，能快速、准确地处理大量复杂的数据，并具有优良的性能价格比。更为重要的是，它应具有长远的生命期和易扩展性，能适应校园网络不断增长的需求，以最小的投资，产出最大的效益。校园网工程采取配备多台服务器分担负荷的方案。
2.交换机等网络结点关键设备必须具备冷热备份能力。关键结点设备运行中出现故障后，能够有效、及时地恢复。基本配置的终端方式操作要简单，结点内部的配置内容可以通过笔记本电脑采用TCP/IP协议下载保存、或是上传恢复。四．服务安装与配置
首先要进行局域网的组建，在我的电脑—属性—网络标识—属性中修改计算机名和工作组，对局域网中的每台机子进行标号。
然后进行网络设置，协议添加，使局域网畅通。只有对服务器进行安装配置后，才能对校园网进行服务。服务器需要安装的服务有DNS，DHCP，IIS服务，以下以windows2000server系统为例，说明一下安装过程。
4.1 DHCP的安装与配置
4.1.1 目的及意义
局域网中每台计算机都要有自己的IP 地址，但静态的去给每台机子输入，由于校园网的计算机很多，会很麻烦而且容易导致IP冲突，不易管理。所以用DHCP服务器将IP 地址数据库中的IP 地址动态的分配给局域网中的客户机，这时只需在客户机上选择“自动获取IP地址”即可。
客户机通过广播信息包的方式向DHCP服务器提出申请，服务器收到信息后会向客户机提供一个合适的IP地址，每台客户机将选择一个IP地址而拒绝其他的，而且DHCP服务器在提供IP地址时会设置一定的租用期限，当客户机的租约到期后会释放IP地址而重新获得服务器提供的其他IP地址。DHCP服务器还可以通过保留设置，给其它服务器提供一个永久不过期的IP地址，例如给DNS服务器保留IP192.168.6.2，就相当于有了一个静态容易访问的IP地址。
4.2.2 实现方法
（1）安装
点击开始—设置—控制面板—添加/删除程序—添加/删除Windows组件—网络服务—详细信息—选择“动态主机配置协议（DHCP）”—将系统盘放入光驱，按确定进行安装
（2）设置
我的电脑—管理—服务和应用程序—DHCP—新建作用域—输入“名称” —下一步输入“起始IP地址”，“结束IP地址”（想要分配的IP）—下一步输入要排除的IP地址（以后可以作为保留的IP）—下一步输入租约期限—选择“是，我想现在配置这些选项” —输入相应的“默认网关”“域名称和DNS服务器”“WINS服务器” —下一步选择“是，我现在想要激活此作用域” —下一步—完成
（3）在客户机上选择自动获取IP地址，在用ipconfig命令查看IP,如果是DHCP服务器预留的IP地址，则服务设置成功。
（4）设置保留时，需在客户机上点开始—运行—cmd—输入命令“ipconfig –all”查看MAC地址，在服务器上输入客户机相应的MAC地址和想要保留的IP地址即可。
4.2.WEB实验的设计
1检查设置网络环境，设置两台虚拟机的网络连接，设置两个虚拟机的ip地址，并确定网络连接成功。
2完成网页并存入指定文件夹
3安装IIS中的WEB服务
.4、配置WEB服务，指定主目录、文档内容
5.在客户端打开IE浏览器，输入http://服务器IP访问
6.完成新的网页放入指定文件夹，添加虚拟目录
7.修改WEB服务端口，在客户端打开IE浏览器
4.3.电脑桌面远程控制实验设计
1检查设置网络环境，设置两台虚拟机的网络连接，设置两个虚拟机的IP地址，并确定网络连接成功。
2、完成客
户
端
与
虚
拟
机的远
程
控
制
3、成功更改DWORD数字
4、成功更改第二个WDORD数字
5、更改虚拟机的密码，并设置地址，使其重新实现远程控制
五．系统安全体系设计
5.1 物理层安全
物理层的安全主要包括环境、设备及线路的安全。系统中心或机房的建设应遵照：GB50173-93《电子计算机机房设计规范》、GB2887-89《计算机站场地安全要求》及GB2887-89《计算机站场地技术条件》的要求。在设备集中的管理间安装干扰器防止由于设备辐射造成的信息泄漏。同时，要注意保护线路的安全，防止用户的搭线窃听行为。
5.2 网络层安全
校园网中局域网数目较多，根据需要多个网络可能要互相联接。正是这种多网的互联，使我们对网络层的安全要极度重视。定义一个网络或各网络内不同安全等级的部分为不同的安全域。安全域之间的连接处叫网络边界。下面主要讨论以下几方面的网络层安全防护： 1)划分安全子网。如果同一局域网内有不同等级的安全域，可以通过划分子网及VLAN的方法加以访问控制。如在教学局域网中学生机房和多媒体机房之间可以通过划分子网来控制，不允许学生机房的机器访问多媒体机房的机器。2)加强网络边界的访问控制。安全等级差别较大的边界需要采用防火墙来控制。如校园内网、校园外网和Internet之间，利用防火墙进行访问控制和内容过滤。可有效地解决需求中提到的多种威胁。3)防止内外的攻击威胁。在每个安全域内或多个安全域之间安装入侵检测系统（IDS）,可有效地防止来自网络内外的攻击。4)定期的网络安全性检测实现持续安全。利用漏洞扫描器（Scanner）,定期对系统进行安全性评估，及时发现安全隐患并实施修补，可达到网络的相对持续安全。5)建立网络防病毒系统。在校园网中安装网络版的防毒系统，集中控制、管理查杀网络中服务器、终端的病毒，保护全网不被病毒侵害。
六.结束语
组建校园网是一个复杂的系统工程，不仅技术上要求高，其投资也是巨大的。一个学校的网络通常分有若干个不同应用部门级网络组成，分布在校园不同楼宇中，地理分布广泛，范围大，通过路由器、交换机、集线器、FDDI或无线连接方式连接在一起组成校园网络。在具体设计中既要根据实际情况，资金投入，目前应用情况及要求，又要考虑将来的扩充与发展。因此在建造时应采取一种科学方法，予以设与实现，既先进、实用、安全、可靠，又节省资金
第五篇：《计算机实践》 实验报告
《计算机实践》 实验报告 I
—数据结构
班号： 0316102 学号： 031650106
姓名： 郭砚璞 Email： 2755858446@qq.com
签名：
南京航空航天大学
2018年10月21日
目录
目录…………………………………………………………2
实验一：约瑟夫斯问题求解………………………………3
实验二：停车场管理问题…………………………………12
实验三：管道铺设施工的最佳方案问题…………………25
实验四：内部排序算法的实现与比较……………………35
参考资料……………………………………………………44
源程序清单…………………………………………………44
实验一、约瑟夫斯问题求解
一、问题描述
1）问题描述
约瑟夫斯（Josephus）问题的一种描述是：编号为 1，2，…，n 的 n 个人按顺时针方向
围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从
第一个人开始按顺时针方向自 1 开始报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向下一个人开始重新从 1 报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。
2）实验目的与基本要求
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
3）测试数据
n=7，7 个人的密码依次为：3，1，7，2，4，8，4。m 初值为 6（正确的出列顺序应为
6，1，4，7，2，3，5）。
4）提示
程序运行后，首先要求用户指定初始报数上限 m，然后读取个人的密码。可设 n≤30。注意链表中空表和非空表的界限。
5）输入输出
输入数据：建立输入处理，输入 n 输入以及每个人的密码；m 的初值。
输出形式：建立一个输出函数，输出正确的序列。
6）选作内容
添加采用顺序存储结构实现问题求解的模块。
以上是本实验的题目要求，下面我将介绍我的实现算法，程序调试结果以及编程过程中遇到的具体问题，并且谈谈我的收获和感悟！
二、需求分析
1、本实验用于求出一组排列数的约瑟夫斯出列顺序。
2、程序运行后显示提示信息，提示用户输入人数n和初始报数上限m，程序需判断m与n的大小，如果m>n，需提示用户重新输入n值和m值。
3、m和n输入有效后，程序提示用户继续输入n个数据，作为n个人的密码。
4、用户输入完毕后，程序需自动显示输入的数据，并且按照出列顺序将n个出列者的编号结果显示出来。
三、概要设计
为了实现上述功能，应以循环链表的数据结构存储n个人的编号、密码信息和顺序关系，因此需要一个循环链表的数据类型。
1、循环链表抽象数据类型定义：
ADT CircularLinkList{
数据对象：一个循环链表，每个结点数据域是一个人的编号和密码。
数据关系：一个结点的指针域指向按照编号下一个结点。
基本操作：
CREATE_SL(SLNODE*);//构建顺序链表
ShowOutput(SLNODE *h, int m);//递归程序，按顺序依次输出出列者的编号
}ADT CircularLinkList
2、本程序保护模块
主函数模块
建立链表模块：将输入数据赋给结点数据域，并构建循环链表的数据关系
核心算法模块：按照算法移动指针、删除节点，依次输出出列者的编号。
调用关系：
3、算法流程图
四、详细设计
1.元素类型、结点类型和结点指针类型：
#define ElemType int
#define SLNODE struct sl_node
SLNODE
{
ElemType data[2];
SLNODE *next;
};
2、建立链表的伪码
SLNODE *CREATE_SL(SLNODE *h,int n)//创建一个h为头指针的链表，h指向的结点数据域用不到
{
ElemType data;
int i = 1;
SLNODE *p, *s;
p = h;
while(i<=n)
{
printf(“请输入第%d个元素:t”,i);
scanf_s(“%d”, &data);
s =(SLNODE *)malloc(sizeof(SLNODE));
s->data[0]=i;
s->data[1] = data;
if(h->next == NULL)
{
h->next = s;
}
else
{
p->next = s;
}
p = s;
i++;
}
p->next = h;
return h;
}
3、主函数伪码
int main()
{
int m,n,mistake=1;
SLNODE *Head;
PrintInformation1();//输出程序信息和个人信息
while(mistake)
{
printf(“输入人数n:n”);
scanf_s(“%d”, &n);
printf(“请指定初始报数上限m(m应必须小于等于n):n”);
scanf_s(“%d”, &m);
if(m>n)
{
printf(“输入数据有误，请重新输入n”);
}
else mistake=0;
}
Head =(SLNODE *)malloc(sizeof(SLNODE));
Head->next = NULL;
Head = CREATE_SL(Head,n);
ShowInput(Head,n);
printf(“正确的出列顺序为:rn”);
ShowOutput(Head,m);
PrintInformation2();//程序结束信息
system(“pause”);
return 0;
}
五、调试分析与核心算法解释
程序的调试主要是针对循环链表，所以调试对象明确，按照算法思路来调试，难度不大。
本题在建立好链表以后，开始执行核心程序ShowOutput递归函数，也就是想办法按照约瑟夫斯问题的规则来删除指针指向的结点、移动指针等，从而以一定排列输出n个人的密码。程序刚开始，先由用户依次输入人数n和初始报数上限m，并判断是否m<=n，如果m>n，则显示重新输入（程序并不会结束）。
然后程序建立头指针Head并且执行CREATE_SL函数，创建链表。
执行ShowInput函数，将n个人的密码依次输出。
下面开始执行本程序的关键函数，也是整个算法的核心函数ShowOutput，这也是整个算法的体现：
函数整体是个递归函数，运用递归的思想，效率很高，占用内存小，不需要设置标志位来判断是否某个结点被访问，而是访问到一个应该出列的结点“出列”，然后以此结点为下一次递归的头结点，然后删除本次递归程序充当头结点的那个结点。
图解：
h，p，s均为指向节点的指针，第一次执行此函数时，h指向头结点。
p指针寻找到要“出列”的节点，h指向要出列的结点作为下一次递归的新的头结点。
利用p指针和s指针重新改造循环链表,然后s指针用于记录本次递归的头结点位置，即将用于删除、释放空间。
下面执行free(s),删除所指内存空间，开始下一次递归调用。
后面执行递归函数时，h刚开始指向的是上一次输出的结点（还没删除），程序一开始先让s指向h，等这一趟程序快结束找到下一个要出列的结点时，h指向该结点作为下一次递归函数的头结点，并且让p找到s指向的充当本次头结点的结点，把它删除，再执行此递归程序。
终止条件是p->next=h，说明没有需要输出的节点了，于是便实现了递归。如图所示：
截图如图：
六、使用说明
按照程序界面指示输入即可，逐个整数数字输入，每输入一个数字按一个回车。
七、调试结果
按照测试要求进行了测试，结果如下：
八、遇到的问题及解决方法（程序调试日志）
2018/9/不详
问题：先建立了一个链表实现插入算法的小功能，再进行约瑟夫问题求解，结果程序不停的输出不完整的数据，陷入死循环。
解决：p指针所指空间逻辑上不该释放但被不正确释放，删去free(p)代码，一切正常。
2018/9/不详
问题：递归程序死循环。
解决：单步执行发现递归的终止条件不正确，修改为p->next=h，程序功能实现！
2018/10/20
最后一天，完善程序，将程序中的注释写清楚，百度找到了显示系统时间的方法，按格式输出，截屏、书写报告。
九、实验的收获与感想
个人感想：循环链表虽然不是很容易理解，但是处理约瑟夫斯这样的删除元素的操作真的十分便利，比起数组要方便的多。但是代价是编程要仔细，不要释放错内存空间。
个人方法优点：
1、建立链表时，将头结点和头指针同时运用，使头指针一开始指向头结点，这样操作方便，同时个人的算法要利用s删除上一次h指向的头结点，所以一开始让头指针指向一个头结点对于个人的算法是有一定好处的。
2、本人采用递归的算法，每次找到要出列的点后，先不马上删除结点，而是将h指针指向此结点作为下一次递归的h结点，等下一次递归找到新的出列结点并用h指向来作为头结点后，再将废弃结点删除，这样“改变头结点”，操作简便，很适合递归的条件。
个人方法缺点：本人认为此程序缺点是陌生人刚看到此程序不能马上理解，因为递归程序本身不易理解。所以为了更好给别人使用，本人已将程序注释的很清楚了。
建议：本实验很好，建议像第四题那样，增加一项计算程序空间复杂度和时间复杂度（移动次数）的要求，组织同学进行讨论，展示最优的算法。
十、源程序
见源程序清单。
实验二、停车场管理问题
一、问题描述
1）问题描述
设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满 n 辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离
开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再
按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳
费用。试为停车场编制按上述要求进行管理的模拟程序。
2）基本要求
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管
理。每一组输入数据包括三个数据项：汽车的“到达”（‘A’表示）或“离去”（‘D’表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序
结构实现，队列以链表结构实现。
3）测试数据
设 n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车 “到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。其中：（‘A’，1，5）表示 1 号牌照车在 5 这个时刻到达，而（‘D’，1，15）表示 1 号牌照车在 15 这个时刻离去。
4）提示
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据
按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号 码和进入停车场的时刻。
5）输入输出:
输入数据：
程序接受 5 个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时 间)；停车场（‘P’, 0, 0）显示停车场的车数；候车场（‘W’, 0, 0）显示候车场的车数；退出（‘E’, 0, 0）退出程序。
输出数据：
对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆 离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。
二、需求分析
1、本程序用来模拟停车场进场、进便道、场外等候、出场、收费等操作。
2、程序运行后显示提示信息，提示用户输入停车每小时需缴纳的费用，用户输入后，提示信息提示用户输入命令：驶入停车场A，离开停车场D，查看停车场内车数P 0 0，查看候车厂内车数W 0 0，程序结束E 0 0。
3、程序需判断用户输入的进场出场时间的有效性，后来输入的时间要大于以前输入的时间。
4、用户输入有效命令后，程序显示汽车进出场信息，若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用。
三、概要设计
为了实现上述功能，需要用栈模拟停车场，用一个备用的栈存储暂时出场的外部汽车，用队列模拟便道。
1、停车场“栈”抽象数据类型定义：
ADT stack{
数据对象：车牌号、进场时间、汽车数量
数据关系：先入后出
基本操作：
*Init_Parking();//置空栈
IsEmpty_Parking(Parking *s);//判空栈
Push_Parking(Parking *s,ElemType license,ElemType timeIn);//入栈
Pop_Parking(Parking *s,ElemType *license,ElemType *timeIn);//出栈
}ADT stack
2、备用存储“栈”抽象数据类型定义：
ADT stack1
{
数据对象：车牌号、进场时间、汽车数量
数据关系：先入后出
基本操作：
*Init_Backup();//置空栈
IsEmpty_Backup(Backup *s);//判空栈
Push_Backup(Backup *s, ElemType license, ElemType timeIn);//入栈
Pop_Backup(Backup *s, ElemType *license,ElemType* timeIn);//出栈
}
3、链式队列抽象数据类型定义：
ADT linkqueue
{
数据对象：车牌号、汽车数量
数据关系：先入先出
基本操作：
*Init_LQueue();//创建一个带头结点的空队
In_LQueue(LinkQueue *q, ElemType license);//入队
IsEmpty_LQueue(LinkQueue *q);//判队空
Out_LQueue(LinkQueue *q, ElemType *license);//出队
}
4、本程序保护模块
主函数模块
进场模块：对于进场的命令进行完善地操作处理并进行状态显示的模块
出场模块：对于出场的命令进行完善地操作处理并进行状态显示的模块
置空栈、置空队、进出栈、进出队、判栈空栈满、判队空队满模块：对栈、备用栈、队列进行的基本操作
调用关系：
5、算法流程图
四、详细设计
1、元素类型、结点类型和结点指针类型：
#define Maxsize 2 //停车场最多能停的车数
#define ElemType int
int Prize;//每停一个时刻收费多少元
static int num = 0;//num用于记录入队的车所在的位置
typedef struct stack //模拟停车场的栈
{
ElemType license[Maxsize];//用于存放车牌号
ElemType timeIn[Maxsize];//用于存放入停车场时间
int top;
}Parking;
typedef struct stack1 //退车时暂时存放
{
ElemType license[Maxsize-1];
ElemType timeIn[Maxsize-1];
int top;
}Backup;
typedef struct road
{
ElemType license;
struct road *next;
}Road;
typedef struct linkqueue//队列模拟便道
{
Road *front,*rear;
}LinkQueue;
2、部分基本操作的伪码类型
//给停车场用的配置函数
Parking *Init_Parking()//置空栈
{
Parking *s;
s=(Parking*)malloc(sizeof(Parking));
s->top=-1;
return s;
}
int IsEmpty_Parking(Parking *s)//判空栈
{
if(s->top==-1)
return 1;
else return 0;
}
int Push_Parking(Parking *s,ElemType license,ElemType timeIn)//入栈
{
if(s->top==Maxsize-1)
return 0;
else
{
s->top++;
s->license[s->top]=license;
s->timeIn[s->top]=timeIn;
return 1;
}
}
int Pop_Parking(Parking *s,ElemType *license,ElemType *timeIn)//出栈
{
if(IsEmpty_Parking(s))
return 0;
else
{
*license = s->license[s->top];
*timeIn = s->timeIn[s->top];
s->top--;
return 1;
}
}
//给备用栈配置的函数
Backup *Init_Backup()//置空栈
{
Backup *s;
s =(Backup*)malloc(sizeof(Backup));
s->top =-1;
return s;
}
int IsEmpty_Backup(Backup *s)//判空栈
{
if(s->top ==-1)
return 1;
else return 0;
}
int Push_Backup(Backup *s, ElemType license, ElemType timeIn)//入栈
{
if(s->top == Maxsize-1)
return 0;
else
{
s->top++;
s->license[s->top] = license;
s->timeIn[s->top] = timeIn;
return 1;
}
}
int Pop_Backup(Backup *s, ElemType *license,ElemType* timeIn)//出栈
{
if(IsEmpty_Backup(s))
return 0;
else
{
*license = s->license[s->top];
*timeIn = s->timeIn[s->top];
s->top--;
return 1;
}
}
//给候车便道链式队列配置的函数
LinkQueue *Init_LQueue()//创建一个带头结点的空队
{
LinkQueue *q;
Road *p;
q =(LinkQueue*)malloc(sizeof(LinkQueue));
p =(Road*)malloc(sizeof(Road));
p->next = NULL;
q->front = q->rear = p;
return q;
}
void In_LQueue(LinkQueue *q, ElemType license)//入队
{
Road *p;
p =(Road*)malloc(sizeof(Road));
p->license = license;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
int IsEmpty_LQueue(LinkQueue *q)//判队空
{
if(q->front == q->rear)
return 1;
else
return 0;
}
int Out_LQueue(LinkQueue *q, ElemType *license)//出队
{
Road *p;
if(IsEmpty_LQueue(q))
{
printf(”队空“);
return 0;
}
else
{
p = q->front->next;
q->front->next = p->next;
*license = p->license;
free(p);
if(q->front->next == NULL)
q->rear = q->front;
return 1;
}
}
3、主函数的伪码
void main()
{
ElemType license, time,timelast=0;//timeInlast是最近一次有车进停车场的时间，提示以后输入的进场时间要大于此数值
char command;//进入A还是离开D
Parking *s;
Backup *s1;
LinkQueue *q;
PrintInformation1();//输出程序信息和个人信息
s = Init_Parking();//停车场
q = Init_LQueue();//便道队列
s1 = Init_Backup();//退车时的备用栈
printf(”请输入停车每小时需交纳的费用（元）rn“);
setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少
scanf(”%d“,&Prize);
setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少
while(1)
{
setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少
Loop:printf(”请输入操作的命令，驶入停车场A，离开停车场D，查看停车场内车数P 0 0，查看候车厂内车数W 0 0，程序结束E 0 0:n“);
scanf(”%c%d%d“,&command, &license,&time);
setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少
if(command == A)
{
if(time <= timelast)
{
printf(”输入的时间必须大于上一次输入的时间:t“);
printf(”%dt“, timelast);
printf(”请重新输入n“);
goto Loop;
}
else
{
timelast = time;
GetIn(s,q,license,time);
}
}
if(command == D)
{
if(time <= timelast)
{
printf(”输入的时间必须大于上一次输入的时间:t“);
printf(”%dt“, timelast);
printf(”请重新输入n“);
goto Loop;
}
else
{
timelast = time;
GetOut(s, s1, q, license, time);//车开走的函数
}
}
if(command == P)
{
if(license == 0 && time == 0)
printf(”停车场内停了%d辆车n“,s->top+1);//显示停车场车数
}
if(command == W)
{
if(license == 0 && time == 0)
printf(”侯车场内停了%d辆车n“,num);//显示候车场车数
}
if(command == E)
{
if(license == 0 && time == 0)
{
PrintInformation2();//程序结束信息
system(”pause“);
return;
}
}
}
}
五、调试分析与核心算法解释
程序本身是利用栈、队列的进出完成停车场汽车进出场的模拟的，只要按照模块化的函数，按照基本的逻辑编写，调试是比较容易的。
程序一开始会要求用户输入每小时缴纳多少元费用，显示“请输入停车每小时需交纳的费用（元）”。
以栈模拟停车场，以队列模拟车场外的便道，在while循环开始让用户输入命令、车牌号、时间三个变量，对三个变量进行判断，并执行相应函数。
程序显示“请输入操作的命令，驶入停车场A，离开停车场D，查看停车场内车数P 0 0，查看候车厂内车数W 0 0，程序结束E 0 0:”
如果后来输入的时间比之前输入的时间小，程序会提示“输入的时间必须大于上一次输入的时间: xx 请重新输入”。
其中驶入函数先判断是否栈满，如果栈满则执行入队操作，否则入栈，并将车牌号、驶入时间存入栈元素数组，top值加一，用于记录车的数量，用于判断是否栈满。
如果栈不满，程序显示“车牌号为xx的汽车在xx时刻停在xx车位”。
如果栈满，程序显示“xx号车停在候车便道的第xx个位置”。
离开函数先判断是否栈空，如果栈空则输出没有车辆提示，否则进一步比较是否有栈内车牌号元素与命令的离开的车牌号一致，有则出栈，计算停车时间和计价，无则输出没有此车牌号的车的提示。
如果没有命令的车牌号的汽车，则显示“对不起！停车场内没有车牌号为xx的车”。
如果停车场已空，会显示“对不起！停车场已空！”。
如果原先栈满，离开一辆车以后，最早到便道上的一辆车进栈，并显示“xx号汽车此时退出便道，进入停车场最后一个位置”。
队列和栈的top记录了车的数量，可用于输出内部车数，也可用于判断是否栈满。
如果三个变量分别为P,0,0，则输出停车场内车的个数。
如果三个变量分别为E,0,0，则输出便道上车的个数。
如果三个变量分别为E ,0, 0,则结束程序。
六、使用说明
程序接受 5 个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时 间)；停车场（‘P’, 0, 0）显示停车场的车数；候车场（‘W’, 0, 0）显示候车场的车数；退出（‘E’, 0, 0）退出程序。
注意：命令字符（A D P W E）用大写，输入的三个数据之间用空格隔开。如A 1 5。代表1号1号汽车在5时刻进场。
七、调试结果
按照测试要求给的数据进行了测试：
八、遇到的问题和解决方法（程序调试日志）
2018/9/不详
问题：程序全部结束，执行时能基本完成功能，但是总是会间隔有一次命令无效，重复输出“请输入命令.......”。
解决方法：后来百度发现，这是因为数据缓存区没有清除的缘故，每次回车都会在数据缓存区遗留下来一个Enter字符，可被char型变量读取，因此在每次输入数据前后加入一个清除数据缓存区的函数setbuf(stdin, NULL)即可解决问题。
2018/10/20
最后一天，完善程序，将程序中的注释写清楚，百度找到了显示系统时间的方法，按格式输出，截屏、书写报告。
九、实验的收获与感想
个人感想：
这道题目和后面的第四道题目都是属于比较透彻的题目，先做了第二题，还是对第二题印象最深，首先这道题很讲究编程的条理性，里面的初始化栈、判栈空、栈满、入栈、出栈以及初始化队列、判队空、队满、入队、出队等函数在书上都有，主要的工作是利用模块化的思想，由整体到局部逐渐求精地去写整个程序，从而把整个停车场的5个命令功能给实现，感觉收获很多，模块化的思想很厉害！
方法的优点：
整体程序思路比较简单，因此个人没有什么更优算法，只是在这里面有一个逻辑，就是后面输入的时间不能比之前输入的时间小，因为这不符合日常逻辑，同时也影响了入栈出栈次序，因此我程序里使用了不常用的goto函数，一般这个函数是不建议用的，它会跳转程序，但是在这里判断后面输入的时间大于之前输入的时间后，goto函数可以让程序跳转到while循环开始的地方，让用户重新输入命令，这里感觉很方便！
建议：
希望多多布置这样的习题，有助于教会学生利用模块化思想，不过希望布置的题目可以是多方向的比如有关界面制作的题目，把模块化的函数给大家，大家进行使用，根据自己爱好设计出相应的模块化功能的程序。
十、源程序
见源程序清单。
实验三、管道铺设施工的最佳方案问题
一、问题描述
1）问题描述
需要在某个城市 n 个居民小区之间铺设煤气管道，则在这 n 个居民小区之间只需要铺设 n-1 条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。
2）基本要求
在可能假设的 m 条管道中，选取 n-1 条管道，使得既能连通 n 个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。
3）测试数据
使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。
以上是本实验的题目要求，下面我将介绍我的实现算法，程序调试结果以及编程过程中遇到的具体问题，并且谈谈我的收获和感悟！
二、需求分析
1、此程序用来求无向带权网的最小生成树。
2、程序的输入数据放在一个dat格式的文件中，想要修改输入数据，用记事本打开文件直接修改即可。任何时刻想看到结果，点击一下exe文件即可一键解决。
3、输入数据的形式是一个矩阵形式，行和列的元素依次代表A、B、C....，两点之间有边，则数据是一个不为0的数，否则为0。
4、程序运行结果不仅会在控制台显示出来，同时还要在一个新的文件中显示出来，点击一下exe文件即可一键解决，满足用户“即点即看”，输出文件令用户能“随时且长久”看到结果，不必每一次都要运行程序。
三、概要设计
为实现上述功能，应以图的邻接表数据结构，即链表与数组相结合的数据结构。
1、邻接表抽象数据类型定义：
ADT ALGraph{
数据对象：结点A、B、C....数据关系：存储结构上链表式指针相连，物理结构上点之间相连成边
基本操作：CreateALGraph(ALGraph *G);//建立无向图的邻接表存储
}ADT ALGraph
2、文件操作模块
基本操作：
read_data(void);//只读方式打开文件
read_array(double *array,int n1,int n2,FILE *fp);//读取文件中的边值信息
cout_data(void);//只写方式打开或建立文件
cout_array(double *array,int n1,int n2,FILE *fp);//向文件中写入边值信息
3、本程序保护模块
主程序模块
建立无向图模块：根据读入文件的边值信息创建无向图邻接表存储
最小生成树模块：由无向图生成最小生成树
读入数据模块：只读方式读取文件数据
输出结果模块：将结果输出到控制台
输出到文件模块：将结果输出到文件
调用关系：
四、详细设计
需要建立一个无向图的邻接表存储结构，进行最小生成树的提取。
1、元素类型、结点类型和结点指针类型：
#define MaxVertexNum 100 //设置小区数最多为100
#define VertexNum 9
double LeastNum;//用于记录最短边长度
double LongestNum;//用于记录最长边长度，程序过程中不改变
double adjacent[VertexNum][VertexNum];
//邻接矩阵，不用于处理数据，而是用于暂时存储从文件读来的数据
//进而在邻接表存储数据时读取此数组数据即可
//二维数组数据为0的元素说明之间没有通道
//在处理完数据后，此数组会用来暂时存储处理后的数据，并写入到另一个文件中
typedef struct vnode
{//顶点表结点
char vertex;
EdgeNode *firstedge;
}VertexNode;
typedef struct
{
VertexNode adjlist[MaxVertexNum];
int n,e;
}ALGraph;
2、有序表类型：
typedef struct node
{//边表结点
char adjvex;
double weight;//权值
struct node *next;
}EdgeNode;
3、主函数的伪码：
void main()
{
ALGraph *G;
PrintInformation1();
G =(ALGraph*)malloc(sizeof(ALGraph));
G->n = VertexNum;//为G指向的图分配空间，设置点数（小区数）
read_data();
CreateALGraph(G);
MinimumSpanningTree(G);
cout_data();//输出到文件
ResultOutput((double *)adjacent,VertexNum,VertexNum);//输出到控制台
PrintInformation2();
system(”pause“);
}
4、算法流程图
五、调试分析与核心算法解释
此题按照Prim算法，设置一个用于存储点的点集，找短边从一个点向两点、三个....更多逐渐扩张，即可得到最小生成树。
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边
b.将v加入集合Vnew中，将
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
具体可以参考资料：https://baike.baidu.com/redirect/cb1fkztQc2TOscNlcMemKsGZ1fsgTprJsdBq_APeZx74W4q4TzbKXHsvSYW_6aM1DqhF56eTgD8EZLzBCQHKBGa6ExWmgXbju_gm13Qbbu0KxbHuiIS_DxEp2fgT3BU
六、使用说明
输入数据已经在”gyp_program3_Input.dat“中写好，如果想做修改可以在该文件中修改即可，输出的数据既在控制台显示，也会输出到”gyp_program3_Output.dat“。
七、调试结果
输入数据文件：
这是一个矩阵，例如：第2行，第3列代表B，C两点间的边，0代表无边，不为0代表有边。
控制台程序显示：
输出数据到输出文件
八、遇到的问题和解决方法（程序调试日志）
2018/9/不详
问题：一进入建立无向图的函数程序就中止出错。
解决方法：给建立无向图函数传递的形参是指针，而在主函数中G指针没有赋给内存空间，所以函数无法对G所指的空间进行初始化，在主程序中加入这样一句代码就好了：
G =(ALGraph*)malloc(sizeof(ALGraph));
2018/10/17
问题：输出的二维数组只有一位正常，其余全是0。如下图所示：
解决方法：后来发现是里面flag2这个标志位刚开始是1，程序执行过程中被置0用于判断，但是判断以后没有再次重置为1，导致要用很多次的标志位只发挥了一次作用，后面就误判了，在循环结束加入重置1的语句即可。
问题：输出的二维数组输出数据不完整，里面总有最小的边（问题切入点）。
解决方法：单步执行后发现，某一次循环中Leastnum这个变量得到的最小值恰好是所有边中最小的一个，它在发挥完比较作用后，没有被置为一个很大的数（不小于这些边中最大值即可），结果在下一次循环的时候，导致后面的边都比它大，以至于后面的边都被舍去了，解决方法就是每次循环第一句先把原图的最大边赋给leastnum。
问题：直接运行debug文件夹里的exe程序，且debug程序终止，怀疑是文件数据读取失败，无法打开文件，即文件不存在。
解决方法：如果不详细说明文件路径，程序本身会在当前文件夹内找文件，存数据的文件gyp_program3_Input.dat要保存在当前文件中。也就是和源代码在同一个文件夹中，但是这样子的话，只有用编程软件打开代码运行，dat文件才有效，若想在debug里直接运行exe程序，则把存数据的输入文件同名复制到debug文件夹里即可。
九、实验的收获和感想
个人感想：这个程序可以说是算法感十足了，也是我遇到问题最大的一个程序，但是也证明了自己的能力，学到了很多，收获最大的就是：对于用的不止一次的标志位，一定不可能只单方向置位，一定是双向置位，一次循环结束一定要记得置位，否则用了这一次以后，后面的循环就会误判！
Prim算法真的很好用，不仅适合求带球图的最小生成树，还适合寻找一个点到另一点的最短路径。
个人方法优点：输入方便，输出简洁。读取文件中的数据，不用手动输入，想修改数据在文件中修改就可以，另外输出有两种形式，一种是控制台输出，一种是输出到文件，输出的是一个二维数组，行和列都有表头，看起来很清晰，两个点之间若有边，相应二维坐标的元素就是边值，无边则相应的位置为0。
建议：可以要求用顺序表的方法，因为从理解和编程难度角度考虑，图的邻接表找边会很慢每次都要顺着其中一个链表头结点去寻找，不过这也很锻炼人的能力！
十、源程序
见源程序清单。
实验四、内部排序算法的实现与比较
一、问题描述
1）问题描述
在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
2）基本要求
(1)对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序。
(2)利用随机函数产生N（如30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
(3)对结果作出简要分析。
3）测试数据
随机函数产生。
4）提示
主要工作是设法在已知算法中适当位置插入对关键字的比较次数和移动次数的计数操 作。注意采用分块调试的方法。
5）输入输出:
输入数据：参加排序的整数个数 n（如 n=30000）；
输出数据：各种排序方法的关键字比较次数和移动次数（从小到大排列）。
二、需求分析
1、本程序用来比较5种排序的关键字比较次数和关键字移动次数。
2、本程序用srand()和rand()函数产生N个随机数用于排序方法的比较，用户无需输入。
3、运行程序后，程序需按从小到大的顺序分别输出5种排序的关键字比较次数和移动次数。
三、概要设计
为实现上述功能，程序需要产生N个随机数，并且需要写出这5种排序的排序函数。
1、产生N个随机数的方法
srand((unsigned)(time(NULL)));
for(int j = 0;j < N;j++)
{
num0[j] = rand();
}
2、保证每次排序的数据都相同的方法
num0数组用于得到随机数，num数组每次排序前先用num0数组赋值即可。
for(int j=0;j { num[j] = num0[j]; } InsertSort(num,N);3、5种排序函数 void InsertSort(int R[], int n);//插入排序 void SelectSort(int R[], int n);//选择排序 void BubbleSort(int R[], int n);//冒泡排序 void QuickSort(int R[],int low,int high);//快速排序 void ShellInsert(int R[],int m,int n);//快速排序 void Shellsort(int R[],int n);//希尔排序 4、本程序保护模块 主程序模块 排序模块 比较输出模块 调用关系： 4、算法流程图 四、详细设计 1、排序函数基本操作的伪码实现 void InsertSort(int R[], int n)//插入排序 { int i, j; for(i = 2;i <= n;i++) { R[0] = R[i]; MoveNum[0]++; j = i-1; while(R[0] < R[j]) { KeyCompareNum[0]++; R[j + 1] = R[j]; MoveNum[0]++; j--; } R[j + 1] = R[0]; MoveNum[0]++; } } void SelectSort(int R[], int n)//选择排序 { int i, j, k; for(i = 1;i < n;i++) { k = i; for(j = i + 1;j <= n;j++) if(R[j] < R[k]) { k = j; KeyCompareNum[1]++; } if(k!= i) { R[0] = R[k]; R[k] = R[i]; R[i] = R[0]; MoveNum[1]+=3; } } } void BubbleSort(int R[], int n)//冒泡排序 { int i, j, flag = 0; for(i = 1;(i < n && flag == 0);i++) { flag = 1; for(j=1;j if(R[j + 1] < R[j]) { KeyCompareNum[2]++; flag = 0; R[0] = R[j]; R[j] = R[j+1]; R[j + 1] = R[0]; MoveNum[2]+=3; } } } void QuickSort(int R[],int low,int high)//快速排序 { int i,j; i=low; j=high; R[0]=R[i]; MoveNum[3]++; while(i { while((R[j]>=R[0])&&(j>i)) { j--; KeyCompareNum[3]++; } if(j>i) { R[i]=R[j]; MoveNum[3]++; i++; } while((R[i]<=r[0])&&(j>i)) { i++; KeyCompareNum[3]++; } if(j>i) { R[j]=R[i]; MoveNum[3]++; j--; } } R[i]=R[0]; MoveNum[3]++; if(low QuickSort(R,low,i-1); if(i QuickSort(R,j+1,high); } void ShellInsert(int R[],int m,int n) {//一趟希尔排序，按间隔m划分子序列 int temp,j; for(int i=m;i { temp=R[i]; MoveNum[4]++; j=i; while(j>=m && temp { KeyCompareNum[4]++; R[j]=R[j-m]; MoveNum[4]++; j-=m; } R[j]=temp; MoveNum[4]++; } } void Shellsort(int R[],int n)//希尔排序 { int m; m=n/2; while(m>=1) { ShellInsert(R,m,n); m=(m==2?1:(m/2)); } } 2、主函数伪码实现 int main() { //数组设为N+1个是因为有些算法是从数组1到N存储的，0位有的不用，有的用作了哨兵 int num0[N+1];//记录最原先随机产生的N个数字，因为num[N]每排序一次都会改变 int num[N+1];//每次排序前先读入num0[N]数据 //srand函数只增加一次就够了，用系统当前时间设置rand()随机序列种子，保证每次运行随机序列不一样 srand((unsigned)(time(NULL))); for(int j = 0;j < N;j++) { num0[j] = rand(); } PrintInformation1(); for(int j=0;j { num[j] = num0[j]; } InsertSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } SelectSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } BubbleSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } Shellsort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } QuickSort(num,0,N-1); printf(”关键字比较次数按从小到大排列分别是：rn“); KeyCompareNum_pailie(); printf(”rn“); printf(”移动次数按从小到大排列分别是：rn“); MoveNum_pailie(); PrintInformation2(); system(”pause“); return 0; } 五、调试分析与核心算法解释 程序的5种排序函数可以自己写，也可以百度找源码，总之五种排序函数写完以后，调试的关键是设置计数变量，并在这些函数的合适位置进行加1计数或加3计数，因此注意分块调试，分函数调试，做到这几点调试难度总体不大。 六、使用说明 随机数产生，5种排序用的都是同一组N个随机数，用户无需输入，直接运行程序即可输出运算结果。 七、调试结果 八、遇到的问题和解决方法（程序调试日志） 2018/10/19 问题：第一种排序输出很大，后面输出很小，几乎没作用。 解决方法：每经过一个排序函数，数组已经排好序了，不能直接调用其余的排序函数，而是要在程序一开始就用另一个数组num0[N]记录了随机数产生的数组num[N]，因此只需要在每次排序前，把num0数组中数据重新赋给num数据即可参与排序了。 问题：数据输出个数少于5个，单步执行发现循环不到5次。 解决方案：分析后发现，程序的几个for循环，内层的循环里面的计数加1变量如i，j，和外层循环设置的加1变量用的是一个变量，导致内层循环计数变量的改变会影响外层循环，导致输出个数小于5。将这些变量设置成不同变量就不影响了（相互独立的循环可能不会影响，但内外层关系的两个循环绝对不能用同一个计数变量）。 问题：程序末尾会跳出一个程序中止警告框，说是栈释放的问题。 解决方案：百度发现，这实际上是数组越界的问题，把数组个数设置为N+1大小的，就好了。 九、实验的收获和感想 个人感想：这个程序难度不大，关键在于在合适的位置插入用于记录的变量+1或者+3,真正有技术含量的在于按照从小到大的顺序输出相应数据。收获比较大的一个技巧：相互独立的循环计数变量可能不会影响，但内外层关系的两个循环绝对不能用同一个计数变量，否则程序循环次数就会乱！ 从关键字比较次数和移动次数来看，选择和快速排序都是非常高效的，希尔排序也不错，不要用或少用冒泡排序和直接插入排序。 个人方法的优点：只产生了1次随机数，5次排序的用的都是同一组数据，可以更好地更严谨地比较出这5种算法的优劣。 个人方法的缺点：因为要“长久”保留产生的随机数，因此需多设置一个数组，占用内存空间比较大。 十、源程序 源程序见源程序清单。 参考资料 https://blog.csdn.net/guanyasu/article/details/53153705 https://jingyan.baidu.com/article/49711c616b8a1ffa441b7cdc.html https://zhidao.baidu.com/question/***684.html 源程序清单 实验一、约瑟夫斯问题求解 #include #include #include #define ElemType int #define SLNODE struct sl_node SLNODE { ElemType data[2]; SLNODE *next; }; SLNODE *CREATE_SL(SLNODE*,int); void ShowInput(SLNODE*h,int n);//每个人的密码输入 void ShowOutput(SLNODE*,int);//排列输出 void PrintInformation1();//输出程序信息和个人信息 void PrintInformation2();//程序结束信息 void PrintTime();//输出时间 int main() { int m,n,mistake=1; SLNODE *Head; PrintInformation1();//输出程序信息和个人信息 while(mistake) { printf(”输入人数n:n“); scanf_s(”%d“, &n); printf(”请指定初始报数上限m(m应必须小于等于n):n“); scanf_s(”%d“, &m); if(m>n) { printf(”输入数据有误，请重新输入n“); } else mistake=0; } Head =(SLNODE *)malloc(sizeof(SLNODE)); Head->next = NULL; Head = CREATE_SL(Head,n); ShowInput(Head,n); printf(”正确的出列顺序为:rn“); ShowOutput(Head,m); PrintInformation2();//程序结束信息 system(”pause“); return 0; } void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”实验名称:实验一.约瑟夫斯问题求解rn“); printf(”学号:031650106rn“); printf(”姓名:郭砚璞rn“); printf(”====================rn“); printf(”程序运行开始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序运行结束,Current local time and date:“); PrintTime(); } SLNODE *CREATE_SL(SLNODE *h,int n) //创建一个h为头指针的链表，h指向的结点数据域用不到 { ElemType data; int i = 1; SLNODE *p, *s; p = h; while(i<=n) { printf(”请输入第%d个元素:t“,i); scanf_s(”%d“, &data); s =(SLNODE *)malloc(sizeof(SLNODE)); s->data[0]=i; s->data[1] = data; if(h->next == NULL) { h->next = s; } else { p->next = s; } p = s; i++; } p->next = h; return h; } void ShowInput(SLNODE *h,int n) { SLNODE *p; p = h; printf(”%d“,n); printf(”个人的密码依次为:“); while((p->next)!= h) { p = p->next; printf(”%dt“, p->data[1]); } printf(”n“); } void ShowOutput(SLNODE *h, int m) { SLNODE *p, *s;//s用于记录上一个节点，从而使p结点找到它将其删除 int j = 0; s = h;//第一次执行此函数时，h指向头结点；后面递归执行时，h刚开始指向的是上一//次输出的结点（还没删除） //都用s来记录，等那一趟程序快结束找到下一个要出列的的点时，h指向那个结点作为头结点，并且让p找到s指向的 //上一个结点，把它删除。 p = h; while(j < m-1) { p = p->next; if(p->next==h)//不能让h所指向的结点（上一次输出的结点，暂时用作头结点所以//还未删除）影响小循环次数 { p=p->next;//所以此处让p多移动一下，等下一次小循环让p顺利移动到下一//个节点（从而忽略掉h指向的结点） } //等找到下一个该出列的结点时，h指向那个结点（充当下一次的头节点），充当上一次头//结点的结点利用s删除 j++; }//此时p指向第m-1个结点 if(p->next == h)//整个程序的终止条件，依次回到上个函数结尾，相当于全部结束了 { return; } h= p->next; p = h;//此时h和p均指向要出列的结点 printf(”%dt“, h->data[0]); j = 0;//j用于while循环，使h指针指向要出列的点的前一个结点，所以及时清零 while(p->next!=s)//找s废弃节点 { p = p->next; } s = p->next; p->next = s->next;//连接新结点 free(s);//释放s所指空间 ShowOutput(h,h->data[1]); } 实验二、停车场管理问题 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ #define Maxsize 2 //停车场最多能停的车数 #define ElemType int int Prize;//每停一个时刻收费多少元 static int num = 0;//num用于记录入队的车所在的位置 typedef struct stack //模拟停车场的栈 { ElemType license[Maxsize];//用于存放车牌号 ElemType timeIn[Maxsize];//用于存放入停车场时间 int top; }Parking; typedef struct stack1 //退车时暂时存放 { ElemType license[Maxsize-1]; ElemType timeIn[Maxsize-1]; int top; }Backup; typedef struct road { ElemType license; struct road *next; }Road; typedef struct linkqueue//队列模拟便道 { Road *front,*rear; }LinkQueue; void GetIn(Parking *s, LinkQueue *q, ElemType license, ElemType timeIn);//有车进来 void GetOut(Parking *s, Backup *s1, LinkQueue *q, ElemType license, ElemType timeOut);//有车//出去 void PrintInformation1();//输出程序信息和个人信息 void PrintInformation2();//程序结束信息 void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”实验名称:实验二.停车场管理问题rn“); printf(”学号:031650106rn“); printf(”姓名:郭砚璞rn“); printf(”====================rn“); printf(”程序运行开始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序运行结束,Current local time and date:“); PrintTime(); } //给停车场用的配置函数 Parking *Init_Parking()//置空栈 { Parking *s; s=(Parking*)malloc(sizeof(Parking)); s->top=-1; return s; } int IsEmpty_Parking(Parking *s)//判空栈 { if(s->top==-1) return 1; else return 0; } int Push_Parking(Parking *s,ElemType license,ElemType timeIn)//入栈 { if(s->top==Maxsize-1) return 0; else { s->top++; s->license[s->top]=license; s->timeIn[s->top]=timeIn; return 1; } } int Pop_Parking(Parking *s,ElemType *license,ElemType *timeIn)//出栈 { if(IsEmpty_Parking(s)) return 0; else { *license = s->license[s->top]; *timeIn = s->timeIn[s->top]; s->top--; return 1; } } //给备用栈配置的函数 Backup *Init_Backup()//置空栈 { Backup *s; s =(Backup*)malloc(sizeof(Backup)); s->top =-1; return s; } int IsEmpty_Backup(Backup *s)//判空栈 { if(s->top ==-1) return 1; else return 0; } int Push_Backup(Backup *s, ElemType license, ElemType timeIn)//入栈 { if(s->top == Maxsize-1) return 0; else { s->top++; s->license[s->top] = license; s->timeIn[s->top] = timeIn; return 1; } } int Pop_Backup(Backup *s, ElemType *license,ElemType* timeIn)//出栈 { if(IsEmpty_Backup(s)) return 0; else { *license = s->license[s->top]; *timeIn = s->timeIn[s->top]; s->top--; return 1; } } //给候车便道链式队列配置的函数 LinkQueue *Init_LQueue()//创建一个带头结点的空队 { LinkQueue *q; Road *p; q =(LinkQueue*)malloc(sizeof(LinkQueue)); p =(Road*)malloc(sizeof(Road)); p->next = NULL; q->front = q->rear = p; return q; } void In_LQueue(LinkQueue *q, ElemType license)//入队 { Road *p; p =(Road*)malloc(sizeof(Road)); p->license = license; p->next = NULL; q->rear->next = p; q->rear = p; } int IsEmpty_LQueue(LinkQueue *q)//判队空 { if(q->front == q->rear) return 1; else return 0; } int Out_LQueue(LinkQueue *q, ElemType *license)//出队 { Road *p; if(IsEmpty_LQueue(q)) { printf(”队空“); return 0; } else { p = q->front->next; q->front->next = p->next; *license = p->license; free(p); if(q->front->next == NULL) q->rear = q->front; return 1; } } void main() { ElemType license, time,timelast=0; //timeInlast是最近一次有车进停车场的时间，提示以后输入的进场时间要大于此数值 char command;//进入A还是离开D Parking *s; Backup *s1; LinkQueue *q; PrintInformation1();//输出程序信息和个人信息 s = Init_Parking();//停车场 q = Init_LQueue();//便道队列 s1 = Init_Backup();//退车时的备用栈 printf(”请输入停车每小时需交纳的费用（元）rn“); setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少 scanf(”%d“,&Prize); setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少 while(1) { setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少 Loop:printf(”请输入操作的命令，驶入停车场A，离开停车场D，查看停车场内车数P 0 0，查看候车厂内车数W 0 0，程序结束E 0 0:n“); scanf(”%c%d%d“,&command, &license,&time); setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区,必不可少 if(command == A) { if(time <= timelast) { printf(”输入的时间必须大于上一次输入的时间:t“); printf(”%dt“, timelast); printf(”请重新输入n“); goto Loop; } else { timelast = time; GetIn(s,q,license,time); } } if(command == D) { if(time <= timelast) { printf(”输入的时间必须大于上一次输入的时间:t“); printf(”%dt“, timelast); printf(”请重新输入n“); goto Loop; } else { timelast = time; GetOut(s, s1, q, license, time);//车开走的函数 } } if(command == P) { if(license == 0 && time == 0) printf(”停车场内停了%d辆车n“,s->top+1);//显示停车场车数 } if(command == W) { if(license == 0 && time == 0) printf(”侯车场内停了%d辆车n“,num);//显示候车场车数 } if(command == E) { if(license == 0 && time == 0) { PrintInformation2();//程序结束信息 system(”pause“); return; } } } } //停车函数 void GetIn(Parking *s, LinkQueue *q,ElemType license, ElemType timeIn) { if(Push_Parking(s, license, timeIn)== 1)//说明成功进入停车场 { printf(”%d号车在%d时刻停在停车场第%d个位置nn“,license,timeIn,s->top+1); } else //栈满，汽车要进入便道，即入队 { num++; In_LQueue(q,license); printf(”%d号车停在候车便道的第%d个位置nn“,license,num); } } void GetOut(Parking *s, Backup *s1,LinkQueue *q, ElemType license, ElemType timeOut) { ElemType *licen, *tim;//两个指针赋给出栈函数，用于读取车牌号和进停车场时间 ElemType ParkTime;//汽车在停车场停留的时间 ElemType Money;//汽车应缴金额 licen =(ElemType*)malloc(sizeof(ElemType)); tim=(ElemType*)malloc(sizeof(ElemType)); if(IsEmpty_Parking(s))//先判断停车场内是否有车 { printf(”对不起！停车场已空！nn“); return; } while(s->license[s->top]!= license) { Pop_Parking(s,licen,tim); Push_Backup(s1, *licen, *tim); if(IsEmpty_Parking(s)==1) { printf(”对不起！停车场内没有车牌号为%d的车nn“,license); while(IsEmpty_Backup(s1)!= 1) { Pop_Backup(s1, licen, tim); Push_Parking(s, *licen, *tim); } return; } } if(s->license[s->top] == license) { ParkTime = timeOut-s->timeIn[s->top]; Money = ParkTime * Prize; printf(”汽车在停车场内停留的时间为%d小时,应缴费%d元nn“,ParkTime,Money); Pop_Parking(s, licen, tim); while(IsEmpty_Backup(s1)!= 1) { Pop_Backup(s1,licen,tim); Push_Parking(s,*licen,*tim); } if(IsEmpty_LQueue(q)!= 1) { Out_LQueue(q,licen); Push_Parking(s,*licen,timeOut); printf(”%d号汽车此时退出便道，进入停车场最后一个位置nn“,*licen); num--; } } } 实验三、管道铺设施工的最佳方案问题 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ #define MaxVertexNum 100 //设置小区数最多为100 #define VertexNum 9 double LeastNum;//用于记录最短边长度 double LongestNum;//用于记录最长边长度，程序过程中不改变 double adjacent[VertexNum][VertexNum]; //邻接矩阵，不用于处理数据，而是用于暂时存储从文件读来的数据 //进而在邻接表存储数据时读取此数组数据即可 //二维数组数据为0的元素说明之间没有通道 //在处理完数据后，此数组会用来暂时存储处理后的数据，并写入到另一个文件中 typedef struct node {//边表结点 char adjvex; double weight;//权值 struct node *next; }EdgeNode; typedef struct vnode {//顶点表结点 char vertex; EdgeNode *firstedge; }VertexNode; typedef struct { VertexNode adjlist[MaxVertexNum]; int n,e; }ALGraph; void PrintInformation1();//输出程序信息和个人信息 void PrintInformation2();//程序结束信息 void CreateALGraph(ALGraph *);//将文件中数据导入进来构建无向图邻接表 void MinimumSpanningTree(ALGraph *);//将无向图转化为最小生成树 void ResultOutput(double *array,int n1,int n2);//将数据在控制台显示出来 void read_data(void);//从输入文件读取数据到邻接矩阵 void cout_data(void);//将邻接矩阵中的数据输出到输出文件 void read_array(double *array,int n1,int n2,FILE *fp);//内部函数，用户无需调用 void cout_array(double *array,int n1,int n2,FILE *fp);//内部函数，用户无需调用 void main() { ALGraph *G; PrintInformation1(); G =(ALGraph*)malloc(sizeof(ALGraph)); G->n = VertexNum;//为G指向的图分配空间，设置点数（小区数） read_data(); CreateALGraph(G); MinimumSpanningTree(G); cout_data();//输出到文件 ResultOutput((double *)adjacent,VertexNum,VertexNum);//输出到控制台 PrintInformation2(); system(”pause“); } void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”实验名称:实验三.管道铺设施工的最佳方案问题rn“); printf(”学号:031650106rn“); printf(”姓名:郭砚璞rn“); printf(”====================rn“); printf(”程序运行开始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序运行结束,Current local time and date:“); PrintTime(); } void CreateALGraph(ALGraph *G) { //建立无向图的邻接表存储 int i=0,j=0,k=0; EdgeNode *s; for(i = 0;i < G->n;i++) { G->adjlist[i].vertex = 65 + i; printf(”t%c“,(G->adjlist[i].vertex));//控制台输出列表头 G->adjlist[i].firstedge=NULL; } printf(”n“); for(k=0;k { for(j=0;j { if(adjacent[k][j]!=0) { s =(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex = 65+j; s->weight=adjacent[k][j]; s->next = G->adjlist[k].firstedge; G->adjlist[k].firstedge = s; } } } } void read_data(void) { int i,j; FILE *fp; fp=fopen(”gyp_program3_Input.dat“,”r“);// 输入数据文件 read_array((double *)adjacent,VertexNum,VertexNum,fp); fclose(fp); for(i = 0;i < VertexNum;i++) { for(j = 0;j < VertexNum;j++) { if(adjacent[i][j] > LongestNum) { LongestNum = adjacent[i][j];//即给LongestNum设置的初值为最大边边值 } } } } void read_array(double *array,int n1,int n2,FILE *fp) { int i,j; float q; for(i=0;i for(j=0;j { fscanf(fp,”%f“,&q); *array++ =(double)q; } } void cout_data(void) { FILE *fp; fp=fopen(”gyp_program3_Output.dat“,”w“);//输出数据文件 cout_array((double *)adjacent,VertexNum,VertexNum,fp); fclose(fp); } void cout_array(double *array,int n1,int n2,FILE *fp) { int i,j; for(i = 0;i < n2;i++) { fprintf(fp, ”t%c“, 65 + i);//输出文件里打印列表头 } fprintf(fp,”n“); for(i=0;i { fprintf(fp,”%ct“,65+i);//输出文件里打印行表头 for(j=0;j { fprintf(fp,”%.1ft“,*array); array++; } fprintf(fp,”n“); } } void ResultOutput(double *array,int n1,int n2) { int i,j; for(i=0;i { printf(”%ct“,65+i);//控制台输出行表头 for(j=0;j { printf(”%.1ft“,*array); array++; } printf(”n“); } } void MinimumSpanningTree(ALGraph *G) {//将无向图转化为最小生成树 int i, j, k; int flag2=1,point; int start, end; EdgeNode *s; char NowAdjacent[VertexNum]; for(i=0;i { for(j = 0;j < VertexNum;j++) { adjacent[i][j] = 0;//先将邻接矩阵所有值清零 } } NowAdjacent[0]=G->adjlist[0].vertex;//初始点放入点集 for(i=0;i //刚开始只有一个起始点，之后加入剩余的VertexNum个点，即VertexNum-1次循环 { LeastNum = LongestNum;//这一步很重要，每加入一个点，应把LeastNum初始化为//最大值，避免受之前数值的影响 for(j = 0;j < i + 1;j++)//第i次点集里有i+1个点，即比较这i+1个点与生于点边的大//小，找最小边的另一个点 { point = NowAdjacent[j]-A;//用于指示已经存进点集中的点是图的第几个点 s = G->adjlist[point].firstedge; while(s!= NULL) { for(k = 0;k < i + 1;k++) { if(s->adjvex == NowAdjacent[k]) { flag2 = 0;//flag2=0用于指示此时s所指的点已经在点集内 break; } } if(flag2 == 1)//确保仅当s指向的点是不在点集里的点时，才被比较处理 { if((LeastNum > s->weight)&&(s->weight!=0)) { end = s->adjvex-A;//flag用于指示最短边是第几个点 start = point; LeastNum = s->weight; } } s = s->next; flag2 = 1;//标志位有可能已经被清0，必须重设为1，确保不影响下一次 } //启发：对于用的不止一次的标志位，一定不可能只单方向置位，一定是双向置位，//否则用了一次，后面就会误判 } adjacent[start][end] = LeastNum; adjacent[end][start] = LeastNum; NowAdjacent[i + 1] = G->adjlist[end].vertex;//向点集加入新点 } } 实验四、内部排序算法的实现与比较 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ const int N=3000;//随机产生N个随机整数 void PrintInformation1();//输出程序信息和个人信息 void PrintInformation2();//程序结束信息 void PrintTime(); void InsertSort(int R[], int n);//插入排序 void SelectSort(int R[], int n);//选择排序 void BubbleSort(int R[], int n);//冒泡排序 void QuickSort(int R[],int low,int high);//快速排序 void ShellInsert(int R[],int m,int n);//快速排序 void Shellsort(int R[],int n);//希尔排序 void KeyCompareNum_pailie(); void MoveNum_pailie(); int KeyCompareNum[5]={0};//分别存储这5种排序的关键字比较次数 int MoveNum[5]={0};//分别存储这5种排序的移动次数 int main() { //数组设为N+1个是因为有些算法是从数组1到N存储的，0位有的不用，有的用作了哨兵 int num0[N+1];//记录最原先随机产生的N个数字，因为num[N]每排序一次都会改变 int num[N+1];//每次排序前先读入num0[N]数据 //srand函数只增加一次就够了，用系统当前时间设置rand()随机序列种子，保证每次运行随机序列不一样 srand((unsigned)(time(NULL))); for(int j = 0;j < N;j++) { num0[j] = rand(); } PrintInformation1(); for(int j=0;j { num[j] = num0[j]; } InsertSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } SelectSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } BubbleSort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } Shellsort(num,N); for(int j = 0;j < N;j++) { num[j] = num0[j]; } QuickSort(num,0,N-1); printf(”关键字比较次数按从小到大排列分别是：rn“); KeyCompareNum_pailie(); printf(”rn“); printf(”移动次数按从小到大排列分别是：rn“); MoveNum_pailie(); PrintInformation2(); system(”pause“); return 0; } void KeyCompareNum_pailie()//关键字比较次数排列 { int i,j,k,m; int printnum=0;//用于记录上一次输出的是数组KeyCompareNum的第几个数 int minimum;//用于输出最小的数字 int maximum=0; for(i = 0;i < 5;i++) { if(maximum < KeyCompareNum[i]) maximum = KeyCompareNum[i]; } for(m = 0;m< 5;m++) { minimum = maximum; //minimum在每次输出是都是全新的，不能受之前数值的影响，因此每次输出第一步先//把minimum设为最大值 for(j = 0;j < 5;j++) { if((minimum >=KeyCompareNum[j])&&(KeyCompareNum[j]!= 0)) { minimum = KeyCompareNum[j]; } } for(k = 0;k < 5;k++)//编程时k原先用的还是i,结果i=4这个情况,break以后到紧接//着的外层循环时，i的数值影响到了外层循环，跳了出来，因此换成了k { if(minimum == KeyCompareNum[k]) { KeyCompareNum[k] = 0; printnum = k; break; } } if(printnum == 0) printf(”直接插入排序:%dt“, minimum); if(printnum == 1) printf(”选择排序:%dt“,minimum); if(printnum == 2) printf(”冒泡排序:%dt“, minimum); if(printnum == 3) printf(”快速排序:%dt“, minimum); if(printnum == 4) printf(”希尔排序:%dt“, minimum); } printf(”rn“); } void MoveNum_pailie()//移动次数排列 { int i, j, k, m; int printnum = 0;//用于记录上一次输出的是数组KeyCompareNum的第几个数 int minimum;//用于输出最小的数字 int maximum = 0; for(i = 0;i < 5;i++) { if(maximum < MoveNum[i]) maximum = MoveNum[i]; } for(m = 0;m < 5;m++) { minimum = maximum;//minimum每次输出是都是全新的，不能受之前数值的影响，//因此每次输出第一步先把minimum设为最大值 for(j = 0;j < 5;j++) { if((minimum >= MoveNum[j])&&(MoveNum[j]!= 0)) { minimum = MoveNum[j]; } } for(k = 0;k < 5;k++)//编程时k原先用的还是i,结果i=4这个情况,break以后到紧接//着的外层循环时，i的数值影响到了外层循环，跳了出来 {//因此换成了k if(minimum == MoveNum[k]) { MoveNum[k] = 0; printnum = k; break; } } if(printnum == 0) printf(”直接插入排序：%dt“, minimum); if(printnum == 1) printf(”选择排序：%dt“, minimum); if(printnum == 2) printf(”冒泡排序：%dt“, minimum); if(printnum == 3) printf(”快速排序：%dt“, minimum); if(printnum == 4) printf(”希尔排序：%dt“, minimum); } printf(”rn“); } void InsertSort(int R[], int n)//插入排序 { int i, j; for(i = 2;i <= n;i++) { R[0] = R[i]; MoveNum[0]++; j = i-1; while(R[0] < R[j]) { KeyCompareNum[0]++; R[j + 1] = R[j]; MoveNum[0]++; j--; } R[j + 1] = R[0]; MoveNum[0]++; } } void SelectSort(int R[], int n)//选择排序 { int i, j, k; for(i = 1;i < n;i++) { k = i; for(j = i + 1;j <= n;j++) if(R[j] < R[k]) { k = j; KeyCompareNum[1]++; } if(k!= i) { R[0] = R[k]; R[k] = R[i]; R[i] = R[0]; MoveNum[1]+=3; } } } void BubbleSort(int R[], int n)//冒泡排序 { int i, j, flag = 0; for(i = 1;(i < n && flag == 0);i++) { flag = 1; for(j=1;j if(R[j + 1] < R[j]) { KeyCompareNum[2]++; flag = 0; R[0] = R[j]; R[j] = R[j+1]; R[j + 1] = R[0]; MoveNum[2]+=3; } } } void QuickSort(int R[],int low,int high)//快速排序 { int i,j; i=low; j=high; R[0]=R[i]; MoveNum[3]++; while(i { while((R[j]>=R[0])&&(j>i)) { j--; KeyCompareNum[3]++; } if(j>i) { R[i]=R[j]; MoveNum[3]++; i++; } while((R[i]<=r[0])&&(j>i)) { i++; KeyCompareNum[3]++; } if(j>i) { R[j]=R[i]; MoveNum[3]++; j--; } } R[i]=R[0]; MoveNum[3]++; if(low QuickSort(R,low,i-1); if(i QuickSort(R,j+1,high); } void ShellInsert(int R[],int m,int n) {//一趟希尔排序，按间隔m划分子序列 int temp,j; for(int i=m;i { temp=R[i]; MoveNum[4]++; j=i; while(j>=m && temp { KeyCompareNum[4]++; R[j]=R[j-m]; MoveNum[4]++; j-=m; } R[j]=temp; MoveNum[4]++; } } void Shellsort(int R[],int n)//希尔排序 { int m; m=n/2; while(m>=1) { ShellInsert(R,m,n); m=(m==2?1:(m/2)); } } void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”实验名称:实验四.内部排序算法的实现与比较rn“); printf(”学号:031650106rn“); printf(”姓名:郭砚璞rn“); printf(”====================rn“); printf(”程序运行开始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序运行结束,Current local time and date:"); PrintTime(); }
点击咨询 