第一篇：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)踐實(shí)驗(yàn)報(bào)告
計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)踐
實(shí)驗(yàn)報(bào)告
實(shí)驗(yàn)名稱(chēng) _
姓 名___________________實(shí) 驗(yàn) 日 期： 學(xué) 號(hào)___________________實(shí)驗(yàn)報(bào)告日期：
同組人姓名_________________ 報(bào) 告 退 發(fā)：(訂正、重做)同組人學(xué)號(hào)_ _______________________
一.環(huán)境（詳細(xì)說(shuō)明運(yùn)行的操作系統(tǒng)，網(wǎng)絡(luò)平臺(tái)，機(jī)器的IP地址）
二.實(shí)驗(yàn)?zāi)康?/p>
? ；
? ；
三.實(shí)驗(yàn)內(nèi)容及步驟（包括主要程序流程和函數(shù)說(shuō)明，程序分工說(shuō)明）
四.實(shí)驗(yàn)結(jié)果
五.實(shí)驗(yàn)中的問(wèn)題及心得
六.實(shí)驗(yàn)思考
第二篇：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)踐實(shí)驗(yàn)報(bào)告
計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)踐
實(shí)驗(yàn)報(bào)告
實(shí)驗(yàn)名稱(chēng) 實(shí)驗(yàn)三 RIP和OSPF路由協(xié)議的配置及協(xié)議流程
姓 名____ ______實(shí) 驗(yàn) 日 期： ____________________ 學(xué) 號(hào)___________實(shí)驗(yàn)報(bào)告日期： ____________________ 報(bào) 告 退 發(fā)：(訂正、重做)
一.環(huán)境（詳細(xì)說(shuō)明運(yùn)行的操作系統(tǒng)，網(wǎng)絡(luò)平臺(tái)，機(jī)器的IP地址）? 操作系統(tǒng)：Windows7 ? 網(wǎng)絡(luò)平臺(tái)：虛擬網(wǎng)絡(luò)（軟件Dynamips）? IP地址：127.0.0.1 二.實(shí)驗(yàn)?zāi)康?/p>
? 在上一次實(shí)驗(yàn)的基礎(chǔ)上實(shí)現(xiàn)RIP和OSPF路由協(xié)議
? 自己設(shè)計(jì)網(wǎng)絡(luò)物理拓?fù)浜瓦壿嬀W(wǎng)段，并在其上實(shí)現(xiàn)RIP和OSPF協(xié)議 ? 通過(guò)debug信息詳細(xì)描述RIP和OSPF協(xié)議的工作過(guò)程。
? RIP協(xié)議中觀察沒(méi)有配置水平分割和配置水平分割后協(xié)議的工作流程； ? OSPF中需要思考為什么配置完成后看不到路由信息的交互？如何解決？
三.實(shí)驗(yàn)內(nèi)容及步驟（包括主要配置流程，重要部分需要截圖）
? 設(shè)計(jì)網(wǎng)絡(luò)物理拓?fù)浜瓦壿嬀W(wǎng)段
? 編寫(xiě).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 ? 啟動(dòng)Dynamips服務(wù)端，打開(kāi)管理員控制臺(tái)
-List
分別打開(kāi)路由器和PC設(shè)置IP和PC的靜態(tài)路由
現(xiàn)用R0 舉例說(shuō)明：
分別配置R0端口的ip地址
S1/0
S1/1
S1/2
以上即為R0的IP配置過(guò)程，由于R1、R2、R3和R0的配置過(guò)程類(lèi)似，所以在此不在贅述。
對(duì)于PC的配置，除了IP外還得設(shè)置靜態(tài)路由，如下圖：
直接設(shè)置的默認(rèn)的f0/0口，著實(shí)輕松了不少。
? Rip的設(shè)置
同樣用R0舉例：
根據(jù)拓?fù)鋱D，設(shè)置好network和neighbor,詳細(xì)的可以看拓?fù)鋱D。
設(shè)置好了上述的所有信息，就可以ping啦
PingPC2，成功！
PingPC3, 成功！
? 通過(guò)debug信息詳細(xì)描述RIP協(xié)議的工作過(guò)程。
由圖可知，為了避免在起始路由器和目的路由器之間的路徑中出現(xiàn)回路，路由信息協(xié)議設(shè)定了每條路徑中跳數(shù)的極限值。在路由信息協(xié)議中，每條路經(jīng)中跳數(shù)的最大值設(shè)定為15。當(dāng)跳數(shù)的值達(dá)到16時(shí)，路徑將被認(rèn)定為無(wú)限遠(yuǎn)，同時(shí)目的路由器也將被認(rèn)定為無(wú)法達(dá)到。跳數(shù)極限值的引入避免了路徑中出現(xiàn)
無(wú)限循環(huán)的回路。
如圖所示，數(shù)據(jù)包通過(guò)以太網(wǎng)接口，廣播到整個(gè)路由表，即分別送至10.1.1.1
20.1.1.1
30.1.1.1，然后再選擇合適的端口，直到將數(shù)據(jù)包傳遞。
需要注意的是，RIP不能再兩個(gè)網(wǎng)絡(luò)之間同時(shí)使用多條路由。RIP選擇一條最少路由器的路由器的路由（即最短路由），哪怕還存在另一條高速（低時(shí)延）但路由器較多的路由。同時(shí)，為了規(guī)范路由器的性能，在路由器資訊協(xié)
議中還定義了路由更新計(jì)時(shí)器，路由超時(shí)計(jì)時(shí)器，以及路由更新計(jì)時(shí)器。
無(wú)水平分割的debug信息：
水平分割是在距離矢量路由協(xié)議中最常用的避免環(huán)路發(fā)生的解決方案之一。
產(chǎn)生環(huán)路的一種情況是：路由器A將從路由器B學(xué)習(xí)到的路由信息又告訴給了路由器B。最終，路由器B認(rèn)為通過(guò)路由器A能夠到達(dá)目標(biāo)網(wǎng)絡(luò)，路由器A認(rèn)為通過(guò)路由器B能夠到達(dá)目標(biāo)網(wǎng)絡(luò)。路由數(shù)據(jù)包的時(shí)候，數(shù)據(jù)將在兩個(gè)路由器間不停地循環(huán)，直至TTL的值為0，將此數(shù)據(jù)包丟棄。
水平分割的思想就是：在路由信息傳送過(guò)程中，不再把路由信息發(fā)送到接收到此路由信息的接口上。從而在一定程度上避免了環(huán)路的產(chǎn)生。
觀察無(wú)水平分割的圖，其不能有效的避免出現(xiàn)的環(huán)路。? 實(shí)現(xiàn)OSPF路由協(xié)議
其他類(lèi)比設(shè)置，最后ping同即可
? 通過(guò)debug信息詳細(xì)描述OSPF協(xié)議的工作過(guò)程。
由于cpu占用過(guò)多，電腦出現(xiàn)異常重啟了……結(jié)果未能截下圖……
作為一種鏈路狀態(tài)的路由協(xié)議，OSPF將鏈路狀態(tài)廣播數(shù)據(jù)LSA（Link State Advertisement）傳送給在某一區(qū)域內(nèi)的所有路由器，這一點(diǎn)與距離矢量路由協(xié)議不同。運(yùn)行距離矢量路由協(xié)議的路由器是將部分或全部的路由表傳遞給與其相鄰的路由器。
四.實(shí)驗(yàn)結(jié)果（包括最終實(shí)驗(yàn)結(jié)果，需要截圖）
均在實(shí)驗(yàn)過(guò)程中標(biāo)出。
五.實(shí)驗(yàn)中的問(wèn)題及心得（需要認(rèn)真寫(xiě)，不要寫(xiě)空話、套話）
實(shí)驗(yàn)過(guò)程中的問(wèn)題還是挺多的，從最初的安裝Win_Pcap未果，一度以為是因?yàn)閣in7不支持，兼容模式后安裝不上，于是在網(wǎng)上下載了一個(gè)最新的Win_Pcap才可行。
設(shè)計(jì)拓?fù)鋱D的時(shí)候，一開(kāi)始是想用一個(gè)路由器接多個(gè)PC的，可是后來(lái)選設(shè)備時(shí)C7200-IO-2FE不可用還是怎么，就是不能接上，后來(lái)又換c2600 和c3600時(shí) 發(fā)現(xiàn)都不匹配。說(shuō)不能找到set_npe的信息，估計(jì)還是不適合吧，百度了下說(shuō)仿真環(huán)境要更新……正好也是晚上做的，也沒(méi)人問(wèn)下，也只好作罷。
第一次設(shè)置idlepc的時(shí)候竟然沒(méi)有帶*的……
（這難道是導(dǎo)致后來(lái)ping的延遲都有點(diǎn)偏高的原因？）
寫(xiě).net文件沒(méi)有什么太大的問(wèn)題，由于拓?fù)鋱D和課件中的例子相差無(wú)幾，也不怎么需要大的改動(dòng)，就照貓畫(huà)虎了。
在設(shè)置各個(gè)路由器與PC的ip 和靜態(tài)路由的時(shí)候，操作經(jīng)常有小失誤，不得不重頭再來(lái)，有ping不通的倒也好找，因?yàn)橛泻芏嗟膇p地址，可以用來(lái)發(fā)現(xiàn)是哪塊的錯(cuò)誤，由于設(shè)備有點(diǎn)小多，cpu很吃緊，后來(lái)打字都是一頓一頓的……不過(guò)最后還是ping通了，至于rip的設(shè)置 還是挺好理解的 設(shè)置network和neighbor，不過(guò)對(duì)于OSPF還是有點(diǎn)不怎么理解，到后邊也有點(diǎn)發(fā)懵了。保持清醒很重要……不然一激動(dòng)就很可能功虧一簣。
六.實(shí)驗(yàn)思考（需要認(rèn)真寫(xiě)，不要寫(xiě)空話、套話）
對(duì)于自己ping PC的時(shí)候ping都是有點(diǎn)小高，是機(jī)子性能不
好？還是拓?fù)鋱D本身存在的問(wèn)題？ 但是確實(shí)能ping到 不過(guò)只是很關(guān)心幾個(gè)點(diǎn) 幾個(gè)嘆號(hào)……或許確實(shí)要改進(jìn)下，看他們的環(huán)形圖的延遲都挺好，有時(shí)間再試下其他的拓?fù)浣Y(jié)構(gòu)。
對(duì)于rip的無(wú)水平分割 一直在想有什么用處…… 對(duì)于廣播型網(wǎng)絡(luò)，水平分割解決了很大問(wèn)題 避免了環(huán)路，而對(duì)于非廣播型的網(wǎng)絡(luò)，水平分割的結(jié)果并不理想，描述說(shuō)水平分割像潑出去的水 是不能收回的，意思是和源頭徹底斷開(kāi)了，不能再回去了。
幀中繼Hub-spoke結(jié)構(gòu)的網(wǎng)絡(luò)？ 跳數(shù)的極限值是怎么得到的？
怎樣能提高路由效率，以及數(shù)據(jù)包傳遞的正確率？以后得多做一個(gè) 看看各種拓?fù)浣Y(jié)構(gòu)的優(yōu)劣~ ? OSPF中需要思考為什么配置完成后看不到路由信息的交互？如何解決？
OSPF路由協(xié)議通過(guò)建立交互關(guān)系來(lái)交換路由信息，但是并不是所有相鄰的路由器會(huì)建立OSPF交互關(guān)系。
OSPF協(xié)議是通過(guò)Hello協(xié)議數(shù)據(jù)包來(lái)建立及維護(hù)相鄰關(guān)系的，同時(shí)也用其來(lái)保證相鄰路由器之間的雙向通信。OSPF路由器會(huì)周期性地發(fā)送Hello數(shù)據(jù)包，當(dāng)這個(gè)路由器看到自身被列于其它路由器的Hello數(shù)據(jù)包里時(shí)，這兩個(gè)路由器之間會(huì)建立起雙向通信。在多接入的環(huán)境中，Hello數(shù)據(jù)包還用于發(fā)現(xiàn)指定路由器DR，通過(guò)DR來(lái)控制與哪些路由器建立交互關(guān)系。
兩個(gè)OSPF路由器建立雙向通信這后的第二個(gè)步驟是進(jìn)行數(shù)據(jù)庫(kù)的同步，數(shù)據(jù)庫(kù)同步是所有鏈路狀態(tài)路由協(xié)議的最大的共性。在OSPF路由協(xié)議中，數(shù)據(jù)庫(kù)同步關(guān)系僅僅在建立交互關(guān)系的路由器之間保持。
當(dāng)所有的配置都完成后，路由器之間的交互是穩(wěn)定的，不會(huì)產(chǎn)生新的路由信息。因此在ospf工作是將路由器之間的鏈接斷開(kāi)即可看到其中的信息交互了。
第三篇：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告（范文）
計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
班級(jí)： 120442
學(xué)號(hào)： 11044209
姓名： 鹿弋煒
實(shí)驗(yàn)一 網(wǎng)絡(luò)命令使用
一、實(shí)驗(yàn)內(nèi)容
1、ping命令
2、Netstat命令
2014年12月 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209
3、IPconfig
4、ARP
5、Tracert
6、NBtstat
2014年12月 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209
二、思考題：
1、你的計(jì)算機(jī)平時(shí)能正常上網(wǎng)，某天突然不能上網(wǎng)了，你能否查出是什么原因造成的？
可以通過(guò)ping命令從本地->本地IP->局域網(wǎng)其他IP->網(wǎng)關(guān)->遠(yuǎn)程主機(jī)一步步排查。
2、如何查出計(jì)算機(jī)的MAC地址？有多少種方法？
方法1：ipconfig /all
方法2：nbtstat-A IP Address
3、在同一個(gè)局域網(wǎng)內(nèi)，知道對(duì)方的IP地址，如何查出它的主機(jī)名？
nbtstat-A IP Address-s
三、實(shí)驗(yàn)總結(jié)
2014年12月 3 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209
實(shí)驗(yàn)二 交換機(jī)的基本配置
一、實(shí)驗(yàn)內(nèi)容
二、思考題
1、交換機(jī)有多少種配置模式？
用戶(hù)模式、特權(quán)模式【全局配置模式（線路配置模式、接口配置模式）】
2、為了方便管理，交換機(jī)需開(kāi)能telnet功能，請(qǐng)問(wèn)如何配置交換機(jī)？
將交換機(jī)管理網(wǎng)口配置IP地址并設(shè)置telnet權(quán)限。
3、查看交換所胡配置信息用哪條命令？
switch#show running-config
三、實(shí)驗(yàn)總結(jié)
2014年12月 4
計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209
實(shí)驗(yàn)三 路由器的基本配置
一、實(shí)驗(yàn)內(nèi)容
Router>enable
//進(jìn)入特權(quán)模式
Router#configure terminal
//進(jìn)入全局配置模式。
RA(config)#hostname RA
//配置路由器名稱(chēng)為“RA”。
RA(config)#interface fastethernet 0/0 //進(jìn)入路由器接口配置模式。
RA(config-if)#ip address 192.168.1.1 255.255.255.0 //配置路由器管理接口IP地址。
RA(config-if)#no shutdown //開(kāi)啟路由器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 //要手動(dòng)添加模塊，并確定是數(shù)據(jù)通信設(shè)備（DCE）還是數(shù)據(jù)終端設(shè)備（DTE）。
RA(config-if)#ip address 172.159.1.1 255.255.255.0
RA(config-if)#clock rate 64000 //如果是DCE接口，必須配時(shí)鐘頻率；另外一頭自動(dòng)適應(yīng)為DTE接口，不需要配時(shí)鐘頻率。RA(config-if)#no shutdown
RA#show ip interface brief
//驗(yàn)證各個(gè)接口的IP地址已經(jīng)配置和開(kāi)啟。同樣地，對(duì)另外一臺(tái)路由器端口進(jìn)行配置。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 //也需要手動(dòng)添加模塊，如果RA的serial 1/0口選擇DCE接口，則接口就會(huì)自動(dòng)選擇為DTE接口，無(wú)須配時(shí)鐘頻率。RB(config-if)#ip address 192.168.3.1 255.255.255.0
RB(config-if)#no shutdown
RB#show ip interface brief
//驗(yàn)證各個(gè)接口的IP地址已經(jīng)配置和開(kāi)啟。
2014年12月 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209
二、思考題
1、路由器有多少種配置模式？
有用戶(hù)模式、特權(quán)模式、全局模式三種。
2、為了方便管理，路由器需開(kāi)能telnet功能，請(qǐng)問(wèn)如何配置路由器？
對(duì)管理網(wǎng)口配置IP地址和掩碼，并設(shè)置telnet權(quán)限。
3、查看路由器所有配置信息用哪條命令？
Router #show running-config
4、如果不設(shè)置路由器遠(yuǎn)程登錄密碼與路由器特權(quán)模式密碼，可能通過(guò)telnet訪問(wèn)路由器嗎？
不能。
三、實(shí)驗(yàn)總結(jié)
2014年12月 6 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209 實(shí)驗(yàn)四 Web、FTP服務(wù)器的基本配置
一、實(shí)驗(yàn)內(nèi)容
1、Web服務(wù)器
2、FTP服務(wù)器（Serv-U軟件建立）
二、思考題
1、如果要禁止某個(gè)IP地址訪問(wèn)Web服務(wù)器，應(yīng)該如何設(shè)置呢？（實(shí)驗(yàn)的時(shí)候可以根據(jù)自己的網(wǎng)絡(luò)結(jié)構(gòu)任意定一個(gè)IP地址，或者讓老師定一個(gè)IP地址。）
在IIS設(shè)置中，右鍵單擊網(wǎng)站名，選屬性，選擇目錄安全性選項(xiàng)卡，在IP地址和域名限制中單擊編輯，添加IP地址。
2、如果要禁止某一段IP地址訪問(wèn)Web服務(wù)器，應(yīng)該如何設(shè)置呢？實(shí)驗(yàn)的時(shí)候老師可以根據(jù)實(shí)際的網(wǎng)絡(luò)結(jié)構(gòu)定一段IP地址。（提示：和子網(wǎng)掩碼有關(guān)系）
在IIS設(shè)置中，右鍵單擊網(wǎng)站名，選屬性，選擇目錄安全性選項(xiàng)卡，在IP地址和域名限制中單擊編輯，添加IP地址網(wǎng)段如192.168.1.0，子網(wǎng)掩碼255.255.255.0。
3、如果在同一臺(tái)Web服務(wù)器，要建立多個(gè)站點(diǎn)，有什么方法可以實(shí)現(xiàn)呢？請(qǐng)通過(guò)實(shí)驗(yàn)進(jìn)行調(diào)試。Web服務(wù)器的虛擬目錄有什么作用呢？請(qǐng)建一個(gè)虛擬目錄，通過(guò)實(shí)驗(yàn)掌握它的設(shè)置及使用。
在IIS中添加一個(gè)新的站點(diǎn)，并設(shè)置對(duì)應(yīng)的主機(jī)名。虛擬目錄可以把不同物理目錄集結(jié)在跟目錄下方便文件共享。
2014年12月 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209
4、如果要禁止某個(gè)IP地址訪問(wèn)FTP服務(wù)器，應(yīng)該如何設(shè)置呢？（實(shí)驗(yàn)的時(shí)候可以根據(jù)自己的網(wǎng)絡(luò)結(jié)構(gòu)任意定一個(gè)IP地址，或者讓老師定一個(gè)IP地址。）
在FTP設(shè)置中IP訪問(wèn)規(guī)則加入指定IP地址。
5、如果要禁止某一段IP地址訪問(wèn)FTP服務(wù)器，應(yīng)該如何設(shè)置呢？實(shí)驗(yàn)的時(shí)候老師可以根據(jù)實(shí)際的網(wǎng)絡(luò)結(jié)構(gòu)定一段IP地址。（提示：和子網(wǎng)掩碼有關(guān)系）
在FTP設(shè)置中IP訪問(wèn)規(guī)則加入指定IP地址段如192.168.1.0，子網(wǎng)掩碼設(shè)置為255.255.255.0。
6、FTP服務(wù)器的虛擬目錄有什么作用呢？請(qǐng)新建一個(gè)虛擬目錄，通過(guò)實(shí)驗(yàn)掌握它的設(shè)置及應(yīng)用。
虛擬目錄是將一個(gè)物理路徑不在FTP主路徑下的目錄映射到主路徑下，虛擬成為一個(gè)主目錄下的子目錄。方便文件的管理和訪問(wèn)。
三、實(shí)驗(yàn)總結(jié)
2014年12月 8 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209 實(shí)驗(yàn)五 Wireshark（Ethereal）抓包實(shí)驗(yàn)
一、實(shí)驗(yàn)內(nèi)容
1、Ping抓包
2、FTP密碼抓取
當(dāng)輸入ftp://guest:11044209@192.168.0.9時(shí)成功抓取到用戶(hù)名guest和密碼11044209
3、用FTP軟件FileZilla連接服務(wù)器嘗試抓取密碼
成功獲取用戶(hù)名和密碼
2014年12月 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)驗(yàn)報(bào)告
鹿弋煒11044209
二、思考題
如果我們是用文件傳輸協(xié)議FTP軟件（例如：CuteFTP，LeapFTP等）登錄ftp://192.168.0.1，還能捕獲到FTP的登錄密碼嗎？
當(dāng)使用FTP軟件FileZilla連接，也成功抓取了用戶(hù)名密碼。
三、實(shí)驗(yàn)總結(jié)
2014年12月 10
第四篇：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)實(shí)踐報(bào)告
計(jì)算機(jī)網(wǎng)絡(luò) 課程設(shè)計(jì)報(bào)告
班 級(jí)： 電子商務(wù)1503班 指導(dǎo)教師： 高 星 學(xué) 號(hào)： 0729150318 姓 名： 劉 雅 男
一.校園網(wǎng)建設(shè)的需求分析..........................................................................................3 1.1 校園網(wǎng)的背景...................................................................................................................3
1.2 校園網(wǎng)的內(nèi)容、意義和目的...........................................................................................3
1.2.1校園網(wǎng)的內(nèi)容........................................................................................................3 1.2.2 校園網(wǎng)的意義.......................................................................................................4 1.2.3校園網(wǎng)的目的........................................................................................................4
二.網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)...........................................................................................................................5
2.1 有線網(wǎng)絡(luò)拓?fù)鋱D...............................................................................................................5 2.2 無(wú)線網(wǎng)絡(luò).........................................................................................................................5 三． 校園網(wǎng)的實(shí)施方案.................................................................................................................6
3.1 綜合布線...........................................................................................................................6 3.2 交換機(jī)的選擇...................................................................................................................6 3.3服務(wù)器系統(tǒng)、設(shè)備的故障恢復(fù)及設(shè)置............................................................................6 四．服務(wù)安裝與配置.......................................................................................................................7
4.1 DHCP的安裝與配置..........................................................................................................8
4.1.1 目的及意義...........................................................................................................8 4.2.2 實(shí)現(xiàn)方法...............................................................................................................8 4.2.WEB實(shí)驗(yàn)的設(shè)計(jì)........................................................................................................11 4.3.電腦桌面遠(yuǎn)程控制實(shí)驗(yàn)設(shè)計(jì).......................................................................................23 五．系統(tǒng)安全體系設(shè)計(jì).................................................................................................................29 5.1物理層安全......................................................................................................................29 5.2網(wǎng)絡(luò)層安全......................................................................................................................29 六.結(jié)束語(yǔ).....................................................................................................................................30
遠(yuǎn)大中學(xué)校園網(wǎng)絡(luò)組建實(shí)驗(yàn)報(bào)告
摘要：隨著E時(shí)代的到來(lái)，網(wǎng)絡(luò)越來(lái)越發(fā)揮起它無(wú)可替代的作用。信息資源的共享也為校園網(wǎng)絡(luò)的發(fā)展帶來(lái)無(wú)可比擬的優(yōu)點(diǎn)。因而可根據(jù)校園網(wǎng)的應(yīng)用需求對(duì)校園網(wǎng)進(jìn)行了總體的設(shè)計(jì)，首先根據(jù)學(xué)校的性質(zhì)、規(guī)模以及對(duì)計(jì)算機(jī)的使用，做出適合學(xué)校的網(wǎng)絡(luò)概圖；其次根據(jù)學(xué)校的網(wǎng)絡(luò)建設(shè)目的，明確網(wǎng)絡(luò)的結(jié)構(gòu)和功能；最后根據(jù)學(xué)校的技術(shù)要求，準(zhǔn)確的確定技術(shù)選題、線路分布、設(shè)備和軟件的配置等，進(jìn)而實(shí)施學(xué)校的網(wǎng)絡(luò)組建的具體步驟。關(guān)鍵字：校園網(wǎng) 拓?fù)鋱D 服務(wù)
一.校園網(wǎng)建設(shè)的需求分析
1.1 校園網(wǎng)的背景
隨著人們對(duì)信息資源共享和信息交流的迫切需要，促使了網(wǎng)絡(luò)技術(shù)的產(chǎn)生和快速發(fā)展。校園網(wǎng)絡(luò)的使用也進(jìn)入一個(gè)廣泛使用的時(shí)期。校園網(wǎng)絡(luò)的使用也提高了教研和科研的質(zhì)量，改善了教研和科研的條件，同時(shí)也需要不斷的健全自己的校園網(wǎng)絡(luò)來(lái)滿足日新月異的網(wǎng)絡(luò)環(huán)境。怎樣利用網(wǎng)絡(luò)設(shè)備，對(duì)學(xué)校的網(wǎng)絡(luò)做出一個(gè)新的規(guī)劃，進(jìn)一步發(fā)揮各種設(shè)備的功能，實(shí)現(xiàn)學(xué)校各項(xiàng)系統(tǒng)的集成，提高應(yīng)用水平將是學(xué)校校園網(wǎng)建設(shè)的一個(gè)工作重點(diǎn)。
1.2 校園網(wǎng)的內(nèi)容、意義和目的
1.2.1 校園網(wǎng)的內(nèi)容
基于對(duì)我們學(xué)校的現(xiàn)狀了解，以及世界網(wǎng)絡(luò)的發(fā)展來(lái)看，我覺(jué)得有必要為我們的學(xué)校建設(shè)校園網(wǎng)，將為在校師生提供網(wǎng)絡(luò)服務(wù)。校園網(wǎng)最終必須是一個(gè)集計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)、多項(xiàng)信息管理、辦公自動(dòng)化和信息發(fā)布等功能于一體的綜合信息平臺(tái)，并能夠有效促進(jìn)現(xiàn)有的管理體制和管理方法，提高學(xué)校辦公質(zhì)量和效率，以促進(jìn)學(xué)校整體教學(xué)水平的提高。
根據(jù)校園網(wǎng)絡(luò)項(xiàng)目以及實(shí)際情況，我們應(yīng)該充分考慮學(xué)校的實(shí)際情況，注重設(shè)備選型的性能價(jià)格比，采用成熟可靠的技術(shù)，為學(xué)校設(shè)計(jì)成一個(gè)技術(shù)先進(jìn)、靈活可用、性能優(yōu)秀、可升級(jí)擴(kuò)展的校園網(wǎng)絡(luò)?？紤]到學(xué)校的中長(zhǎng)期發(fā)展規(guī)劃，在網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)應(yīng)用、網(wǎng)絡(luò)管理、系統(tǒng)性能以及遠(yuǎn)程教學(xué)等各個(gè)方面能夠適應(yīng)未來(lái)的發(fā)展，最大程度地保護(hù)學(xué)校的投資。建立合理的校園網(wǎng)絡(luò)建設(shè)方案。1.2.2 校園網(wǎng)的意義
學(xué)校借助校園網(wǎng)的建設(shè)，可充分利用豐富的網(wǎng)上應(yīng)用系統(tǒng)及教學(xué)資源，發(fā)揮網(wǎng)絡(luò)資源共享、信息快捷、無(wú)地理限制等優(yōu)勢(shì)，實(shí)現(xiàn)信息資源的共享。使教育與現(xiàn)代科技相結(jié)合，夠提高教學(xué)質(zhì)量和教學(xué)效率，提高學(xué)?，F(xiàn)代化教學(xué)程度，不僅方便了老師們的辦公，同時(shí)也為同學(xué)們課下咨詢(xún)、查找資料提供了有利條件，為教研工作提供了極大的便利。
1.2.3校園網(wǎng)的目的
主要目標(biāo)是根據(jù)某學(xué)校園區(qū)局域網(wǎng)建設(shè)需求，以滿足目前校園網(wǎng)大多數(shù)應(yīng)用為目標(biāo)，在現(xiàn)有獨(dú)立信息教室的基礎(chǔ)上，將對(duì)學(xué)校辦公樓、教學(xué)樓和平房輔助管理部門(mén)等幾座主要建筑物構(gòu)建校園網(wǎng)絡(luò)。
在教學(xué)教育領(lǐng)域，資源共享、教學(xué)網(wǎng)絡(luò)化、辦公自動(dòng)化無(wú)疑是大勢(shì)所趨，為了讓師生之間、教工之間達(dá)成互聯(lián)互通，更加有利于教研工作的進(jìn)行。二.網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)
2.1 有線網(wǎng)絡(luò)拓?fù)鋱D
DNS服務(wù)器IIS服務(wù)器網(wǎng)管工作DHCP服務(wù)器Internet教學(xué)樓實(shí)驗(yàn)樓圖書(shū)館辦公樓電腦室...............體育館教師樓學(xué)生宿舍食堂............2.2 無(wú)線網(wǎng)絡(luò)
無(wú)線網(wǎng)路指的是任何型式的無(wú)線電電腦網(wǎng)路，普遍和電信網(wǎng)路結(jié)合在一起，不需電纜即可在節(jié)點(diǎn)之間相互連結(jié)[1]。無(wú)線電信網(wǎng)路一般被應(yīng)用在使用電磁波的搖控資訊傳輸系統(tǒng)，像是無(wú)線電波作為載波和實(shí)體層的網(wǎng)路。
正從應(yīng)用需求方面考慮,無(wú)線網(wǎng)絡(luò)很適合學(xué)校的一些不易于網(wǎng)絡(luò)布線的場(chǎng)所應(yīng)用?，F(xiàn)在大部分校園都建有有線局域網(wǎng),如何對(duì)原有網(wǎng)絡(luò)進(jìn)一步擴(kuò)充,使校園的每個(gè)角落都處在網(wǎng)絡(luò)中,形成真正意義上的校園網(wǎng)。三． 校園網(wǎng)的實(shí)施方案
3.1 綜合布線
綜合布線方案設(shè)計(jì)是網(wǎng)絡(luò)布線的重中之重，沒(méi)有好的設(shè)計(jì)，就不可能有好的布線系統(tǒng)。首先要清楚那些建筑物需要布線，建筑物中哪些房間需要布線；其次根據(jù)用戶(hù)對(duì)數(shù)據(jù)輸出量的需求決定網(wǎng)絡(luò)應(yīng)當(dāng)采取何種網(wǎng)絡(luò)連接設(shè)備和布線產(chǎn)品；最后要做到的是此設(shè)計(jì)不僅容納網(wǎng)絡(luò)中當(dāng)前的用戶(hù)，而且還應(yīng)當(dāng)保留網(wǎng)絡(luò)的擴(kuò)展能力，從而使得用戶(hù)增加時(shí)網(wǎng)絡(luò)依然能夠基本滿足增長(zhǎng)的需要。
綜合布線設(shè)計(jì)要做到：
1.資金允許的情況下，網(wǎng)絡(luò)主干和垂直布線系統(tǒng)首選光纖做為通訊介質(zhì) 2.費(fèi)用預(yù)算內(nèi)，對(duì)網(wǎng)絡(luò)線路部分一次性充分鋪?zhàn)?，還要預(yù)留冗余路線
3.架設(shè)通信線路時(shí)必須遵循最長(zhǎng)距離限制的規(guī)范，而且在可能的情況下，線纜要盡可能的短。
3.2 交換機(jī)的選擇
交換機(jī)分為二層交換機(jī)和三層交換機(jī)兩種類(lèi)型，其中二層交換機(jī)的工作原理是：（1）當(dāng)交換機(jī)從某個(gè)端口收到一個(gè)數(shù)據(jù)包，它先讀取包頭中的源MAC地址，這樣它就知道源MAC地址的機(jī)器是連在哪個(gè)端口上的；
（2）再去讀取包頭中目的MAC地址，并在地址表中查找相應(yīng)的端口；（3）如表中有與這目的MAC地址對(duì)應(yīng)的端口，把數(shù)據(jù)包直接復(fù)制到這端口上；（4）如表中找不到相應(yīng)的端口則把數(shù)據(jù)包廣播道所有端口上，當(dāng)目的機(jī)器對(duì)原機(jī)器回應(yīng)時(shí)，交換機(jī)又可以學(xué)習(xí)一目的MAC地址與哪個(gè)端口對(duì)應(yīng)，在下次傳送數(shù)據(jù)時(shí)就不再需要對(duì)所有端口進(jìn)行廣播了。
3.3 服務(wù)器系統(tǒng)、設(shè)備的故障恢復(fù)及設(shè)置
1.服務(wù)器系統(tǒng)應(yīng)能代表當(dāng)今計(jì)算機(jī)的最新技術(shù)，具有最先進(jìn)的CPU技術(shù)，非?？斓挠?jì)算速度，能快速、準(zhǔn)確地處理大量復(fù)雜的數(shù)據(jù)，并具有優(yōu)良的性能價(jià)格比。更為重要的是，它應(yīng)具有長(zhǎng)遠(yuǎn)的生命期和易擴(kuò)展性，能適應(yīng)校園網(wǎng)絡(luò)不斷增長(zhǎng)的需求，以最小的投資，產(chǎn)出最大的效益。校園網(wǎng)工程采取配備多臺(tái)服務(wù)器分擔(dān)負(fù)荷的方案。
2.交換機(jī)等網(wǎng)絡(luò)結(jié)點(diǎn)關(guān)鍵設(shè)備必須具備冷熱備份能力。關(guān)鍵結(jié)點(diǎn)設(shè)備運(yùn)行中出現(xiàn)故障后，能夠有效、及時(shí)地恢復(fù)?；九渲玫慕K端方式操作要簡(jiǎn)單，結(jié)點(diǎn)內(nèi)部的配置內(nèi)容可以通過(guò)筆記本電腦采用TCP/IP協(xié)議下載保存、或是上傳恢復(fù)。四．服務(wù)安裝與配置
首先要進(jìn)行局域網(wǎng)的組建，在我的電腦—屬性—網(wǎng)絡(luò)標(biāo)識(shí)—屬性中修改計(jì)算機(jī)名和工作組，對(duì)局域網(wǎng)中的每臺(tái)機(jī)子進(jìn)行標(biāo)號(hào)。
然后進(jìn)行網(wǎng)絡(luò)設(shè)置，協(xié)議添加，使局域網(wǎng)暢通。只有對(duì)服務(wù)器進(jìn)行安裝配置后，才能對(duì)校園網(wǎng)進(jìn)行服務(wù)。服務(wù)器需要安裝的服務(wù)有DNS，DHCP，IIS服務(wù)，以下以windows2000server系統(tǒng)為例，說(shuō)明一下安裝過(guò)程。
4.1 DHCP的安裝與配置
4.1.1 目的及意義
局域網(wǎng)中每臺(tái)計(jì)算機(jī)都要有自己的IP 地址，但靜態(tài)的去給每臺(tái)機(jī)子輸入，由于校園網(wǎng)的計(jì)算機(jī)很多，會(huì)很麻煩而且容易導(dǎo)致IP沖突，不易管理。所以用DHCP服務(wù)器將IP 地址數(shù)據(jù)庫(kù)中的IP 地址動(dòng)態(tài)的分配給局域網(wǎng)中的客戶(hù)機(jī)，這時(shí)只需在客戶(hù)機(jī)上選擇“自動(dòng)獲取IP地址”即可。
客戶(hù)機(jī)通過(guò)廣播信息包的方式向DHCP服務(wù)器提出申請(qǐng)，服務(wù)器收到信息后會(huì)向客戶(hù)機(jī)提供一個(gè)合適的IP地址，每臺(tái)客戶(hù)機(jī)將選擇一個(gè)IP地址而拒絕其他的，而且DHCP服務(wù)器在提供IP地址時(shí)會(huì)設(shè)置一定的租用期限，當(dāng)客戶(hù)機(jī)的租約到期后會(huì)釋放IP地址而重新獲得服務(wù)器提供的其他IP地址。DHCP服務(wù)器還可以通過(guò)保留設(shè)置，給其它服務(wù)器提供一個(gè)永久不過(guò)期的IP地址，例如給DNS服務(wù)器保留IP192.168.6.2，就相當(dāng)于有了一個(gè)靜態(tài)容易訪問(wèn)的IP地址。
4.2.2 實(shí)現(xiàn)方法
（1）安裝
點(diǎn)擊開(kāi)始—設(shè)置—控制面板—添加/刪除程序—添加/刪除Windows組件—網(wǎng)絡(luò)服務(wù)—詳細(xì)信息—選擇“動(dòng)態(tài)主機(jī)配置協(xié)議（DHCP）”—將系統(tǒng)盤(pán)放入光驅(qū)，按確定進(jìn)行安裝
（2）設(shè)置
我的電腦—管理—服務(wù)和應(yīng)用程序—DHCP—新建作用域—輸入“名稱(chēng)” —下一步輸入“起始IP地址”，“結(jié)束IP地址”（想要分配的IP）—下一步輸入要排除的IP地址（以后可以作為保留的IP）—下一步輸入租約期限—選擇“是，我想現(xiàn)在配置這些選項(xiàng)” —輸入相應(yīng)的“默認(rèn)網(wǎng)關(guān)”“域名稱(chēng)和DNS服務(wù)器”“WINS服務(wù)器” —下一步選擇“是，我現(xiàn)在想要激活此作用域” —下一步—完成
（3）在客戶(hù)機(jī)上選擇自動(dòng)獲取IP地址，在用ipconfig命令查看IP,如果是DHCP服務(wù)器預(yù)留的IP地址，則服務(wù)設(shè)置成功。
（4）設(shè)置保留時(shí)，需在客戶(hù)機(jī)上點(diǎn)開(kāi)始—運(yùn)行—cmd—輸入命令“ipconfig –all”查看MAC地址，在服務(wù)器上輸入客戶(hù)機(jī)相應(yīng)的MAC地址和想要保留的IP地址即可。
4.2.WEB實(shí)驗(yàn)的設(shè)計(jì)
1檢查設(shè)置網(wǎng)絡(luò)環(huán)境，設(shè)置兩臺(tái)虛擬機(jī)的網(wǎng)絡(luò)連接，設(shè)置兩個(gè)虛擬機(jī)的ip地址，并確定網(wǎng)絡(luò)連接成功。
2完成網(wǎng)頁(yè)并存入指定文件夾
3安裝IIS中的WEB服務(wù)
.4、配置WEB服務(wù)，指定主目錄、文檔內(nèi)容
5.在客戶(hù)端打開(kāi)IE瀏覽器，輸入http://服務(wù)器IP訪問(wèn)
6.完成新的網(wǎng)頁(yè)放入指定文件夾，添加虛擬目錄
7.修改WEB服務(wù)端口，在客戶(hù)端打開(kāi)IE瀏覽器
4.3.電腦桌面遠(yuǎn)程控制實(shí)驗(yàn)設(shè)計(jì)
1檢查設(shè)置網(wǎng)絡(luò)環(huán)境，設(shè)置兩臺(tái)虛擬機(jī)的網(wǎng)絡(luò)連接，設(shè)置兩個(gè)虛擬機(jī)的IP地址，并確定網(wǎng)絡(luò)連接成功。
2、完成客
戶(hù)
端
與
虛
擬
機(jī)的遠(yuǎn)
程
控
制
3、成功更改DWORD數(shù)字
4、成功更改第二個(gè)WDORD數(shù)字
5、更改虛擬機(jī)的密碼，并設(shè)置地址，使其重新實(shí)現(xiàn)遠(yuǎn)程控制
五．系統(tǒng)安全體系設(shè)計(jì)
5.1 物理層安全
物理層的安全主要包括環(huán)境、設(shè)備及線路的安全。系統(tǒng)中心或機(jī)房的建設(shè)應(yīng)遵照：GB50173-93《電子計(jì)算機(jī)機(jī)房設(shè)計(jì)規(guī)范》、GB2887-89《計(jì)算機(jī)站場(chǎng)地安全要求》及GB2887-89《計(jì)算機(jī)站場(chǎng)地技術(shù)條件》的要求。在設(shè)備集中的管理間安裝干擾器防止由于設(shè)備輻射造成的信息泄漏。同時(shí)，要注意保護(hù)線路的安全，防止用戶(hù)的搭線竊聽(tīng)行為。
5.2 網(wǎng)絡(luò)層安全
校園網(wǎng)中局域網(wǎng)數(shù)目較多，根據(jù)需要多個(gè)網(wǎng)絡(luò)可能要互相聯(lián)接。正是這種多網(wǎng)的互聯(lián)，使我們對(duì)網(wǎng)絡(luò)層的安全要極度重視。定義一個(gè)網(wǎng)絡(luò)或各網(wǎng)絡(luò)內(nèi)不同安全等級(jí)的部分為不同的安全域。安全域之間的連接處叫網(wǎng)絡(luò)邊界。下面主要討論以下幾方面的網(wǎng)絡(luò)層安全防護(hù)： 1)劃分安全子網(wǎng)。如果同一局域網(wǎng)內(nèi)有不同等級(jí)的安全域，可以通過(guò)劃分子網(wǎng)及VLAN的方法加以訪問(wèn)控制。如在教學(xué)局域網(wǎng)中學(xué)生機(jī)房和多媒體機(jī)房之間可以通過(guò)劃分子網(wǎng)來(lái)控制，不允許學(xué)生機(jī)房的機(jī)器訪問(wèn)多媒體機(jī)房的機(jī)器。2)加強(qiáng)網(wǎng)絡(luò)邊界的訪問(wèn)控制。安全等級(jí)差別較大的邊界需要采用防火墻來(lái)控制。如校園內(nèi)網(wǎng)、校園外網(wǎng)和Internet之間，利用防火墻進(jìn)行訪問(wèn)控制和內(nèi)容過(guò)濾。可有效地解決需求中提到的多種威脅。3)防止內(nèi)外的攻擊威脅。在每個(gè)安全域內(nèi)或多個(gè)安全域之間安裝入侵檢測(cè)系統(tǒng)（IDS）,可有效地防止來(lái)自網(wǎng)絡(luò)內(nèi)外的攻擊。4)定期的網(wǎng)絡(luò)安全性檢測(cè)實(shí)現(xiàn)持續(xù)安全。利用漏洞掃描器（Scanner）,定期對(duì)系統(tǒng)進(jìn)行安全性評(píng)估，及時(shí)發(fā)現(xiàn)安全隱患并實(shí)施修補(bǔ)，可達(dá)到網(wǎng)絡(luò)的相對(duì)持續(xù)安全。5)建立網(wǎng)絡(luò)防病毒系統(tǒng)。在校園網(wǎng)中安裝網(wǎng)絡(luò)版的防毒系統(tǒng)，集中控制、管理查殺網(wǎng)絡(luò)中服務(wù)器、終端的病毒，保護(hù)全網(wǎng)不被病毒侵害。
六.結(jié)束語(yǔ)
組建校園網(wǎng)是一個(gè)復(fù)雜的系統(tǒng)工程，不僅技術(shù)上要求高，其投資也是巨大的。一個(gè)學(xué)校的網(wǎng)絡(luò)通常分有若干個(gè)不同應(yīng)用部門(mén)級(jí)網(wǎng)絡(luò)組成，分布在校園不同樓宇中，地理分布廣泛，范圍大，通過(guò)路由器、交換機(jī)、集線器、FDDI或無(wú)線連接方式連接在一起組成校園網(wǎng)絡(luò)。在具體設(shè)計(jì)中既要根據(jù)實(shí)際情況，資金投入，目前應(yīng)用情況及要求，又要考慮將來(lái)的擴(kuò)充與發(fā)展。因此在建造時(shí)應(yīng)采取一種科學(xué)方法，予以設(shè)與實(shí)現(xiàn)，既先進(jìn)、實(shí)用、安全、可靠，又節(jié)省資金
第五篇：《計(jì)算機(jī)實(shí)踐》 實(shí)驗(yàn)報(bào)告
《計(jì)算機(jī)實(shí)踐》 實(shí)驗(yàn)報(bào)告 I
—數(shù)據(jù)結(jié)構(gòu)
班號(hào)： 0316102 學(xué)號(hào)： 031650106
姓名： 郭硯璞 Email： 2755858446@qq.com
簽名：
南京航空航天大學(xué)
2018年10月21日
目錄
目錄…………………………………………………………2
實(shí)驗(yàn)一：約瑟夫斯問(wèn)題求解………………………………3
實(shí)驗(yàn)二：停車(chē)場(chǎng)管理問(wèn)題…………………………………12
實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案問(wèn)題…………………25
實(shí)驗(yàn)四：內(nèi)部排序算法的實(shí)現(xiàn)與比較……………………35
參考資料……………………………………………………44
源程序清單…………………………………………………44
實(shí)驗(yàn)一、約瑟夫斯問(wèn)題求解
一、問(wèn)題描述
1）問(wèn)題描述
約瑟夫斯（Josephus）問(wèn)題的一種描述是：編號(hào)為 1，2，…，n 的 n 個(gè)人按順時(shí)針?lè)较?/p>
圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值 m，從
第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?1 開(kāi)始報(bào)數(shù)，報(bào)到 m 時(shí)停止報(bào)數(shù)。報(bào) m 的人出列，將他的密碼作為新的 m 值，從他在順時(shí)針?lè)较蛳乱粋€(gè)人開(kāi)始重新從 1 報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)一個(gè)程序，按出列順序印出各人編號(hào)。
2）實(shí)驗(yàn)?zāi)康呐c基本要求
利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序印出各人的編號(hào)。
3）測(cè)試數(shù)據(jù)
n=7，7 個(gè)人的密碼依次為：3，1，7，2，4，8，4。m 初值為 6（正確的出列順序應(yīng)為
6，1，4，7，2，3，5）。
4）提示
程序運(yùn)行后，首先要求用戶(hù)指定初始報(bào)數(shù)上限 m，然后讀取個(gè)人的密碼?？稍O(shè) n≤30。注意鏈表中空表和非空表的界限。
5）輸入輸出
輸入數(shù)據(jù)：建立輸入處理，輸入 n 輸入以及每個(gè)人的密碼；m 的初值。
輸出形式：建立一個(gè)輸出函數(shù)，輸出正確的序列。
6）選作內(nèi)容
添加采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)問(wèn)題求解的模塊。
以上是本實(shí)驗(yàn)的題目要求，下面我將介紹我的實(shí)現(xiàn)算法，程序調(diào)試結(jié)果以及編程過(guò)程中遇到的具體問(wèn)題，并且談?wù)勎业氖斋@和感悟！
二、需求分析
1、本實(shí)驗(yàn)用于求出一組排列數(shù)的約瑟夫斯出列順序。
2、程序運(yùn)行后顯示提示信息，提示用戶(hù)輸入人數(shù)n和初始報(bào)數(shù)上限m，程序需判斷m與n的大小，如果m>n，需提示用戶(hù)重新輸入n值和m值。
3、m和n輸入有效后，程序提示用戶(hù)繼續(xù)輸入n個(gè)數(shù)據(jù)，作為n個(gè)人的密碼。
4、用戶(hù)輸入完畢后，程序需自動(dòng)顯示輸入的數(shù)據(jù)，并且按照出列順序?qū)個(gè)出列者的編號(hào)結(jié)果顯示出來(lái)。
三、概要設(shè)計(jì)
為了實(shí)現(xiàn)上述功能，應(yīng)以循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)n個(gè)人的編號(hào)、密碼信息和順序關(guān)系，因此需要一個(gè)循環(huán)鏈表的數(shù)據(jù)類(lèi)型。
1、循環(huán)鏈表抽象數(shù)據(jù)類(lèi)型定義：
ADT CircularLinkList{
數(shù)據(jù)對(duì)象：一個(gè)循環(huán)鏈表，每個(gè)結(jié)點(diǎn)數(shù)據(jù)域是一個(gè)人的編號(hào)和密碼。
數(shù)據(jù)關(guān)系：一個(gè)結(jié)點(diǎn)的指針域指向按照編號(hào)下一個(gè)結(jié)點(diǎn)。
基本操作：
CREATE_SL(SLNODE*);//構(gòu)建順序鏈表
ShowOutput(SLNODE *h, int m);//遞歸程序，按順序依次輸出出列者的編號(hào)
}ADT CircularLinkList
2、本程序保護(hù)模塊
主函數(shù)模塊
建立鏈表模塊：將輸入數(shù)據(jù)賦給結(jié)點(diǎn)數(shù)據(jù)域，并構(gòu)建循環(huán)鏈表的數(shù)據(jù)關(guān)系
核心算法模塊：按照算法移動(dòng)指針、刪除節(jié)點(diǎn)，依次輸出出列者的編號(hào)。
調(diào)用關(guān)系：
3、算法流程圖
四、詳細(xì)設(shè)計(jì)
1.元素類(lèi)型、結(jié)點(diǎn)類(lèi)型和結(jié)點(diǎn)指針類(lèi)型：
#define ElemType int
#define SLNODE struct sl_node
SLNODE
{
ElemType data[2];
SLNODE *next;
};
2、建立鏈表的偽碼
SLNODE *CREATE_SL(SLNODE *h,int n)//創(chuàng)建一個(gè)h為頭指針的鏈表，h指向的結(jié)點(diǎn)數(shù)據(jù)域用不到
{
ElemType data;
int i = 1;
SLNODE *p, *s;
p = h;
while(i<=n)
{
printf(“請(qǐng)輸入第%d個(gè)元素: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、主函數(shù)偽碼
int main()
{
int m,n,mistake=1;
SLNODE *Head;
PrintInformation1();//輸出程序信息和個(gè)人信息
while(mistake)
{
printf(“輸入人數(shù)n:n”);
scanf_s(“%d”, &n);
printf(“請(qǐng)指定初始報(bào)數(shù)上限m(m應(yīng)必須小于等于n):n”);
scanf_s(“%d”, &m);
if(m>n)
{
printf(“輸入數(shù)據(jù)有誤，請(qǐng)重新輸入n”);
}
else mistake=0;
}
Head =(SLNODE *)malloc(sizeof(SLNODE));
Head->next = NULL;
Head = CREATE_SL(Head,n);
ShowInput(Head,n);
printf(“正確的出列順序?yàn)?rn”);
ShowOutput(Head,m);
PrintInformation2();//程序結(jié)束信息
system(“pause”);
return 0;
}
五、調(diào)試分析與核心算法解釋
程序的調(diào)試主要是針對(duì)循環(huán)鏈表，所以調(diào)試對(duì)象明確，按照算法思路來(lái)調(diào)試，難度不大。
本題在建立好鏈表以后，開(kāi)始執(zhí)行核心程序ShowOutput遞歸函數(shù)，也就是想辦法按照約瑟夫斯問(wèn)題的規(guī)則來(lái)刪除指針指向的結(jié)點(diǎn)、移動(dòng)指針等，從而以一定排列輸出n個(gè)人的密碼。程序剛開(kāi)始，先由用戶(hù)依次輸入人數(shù)n和初始報(bào)數(shù)上限m，并判斷是否m<=n，如果m>n，則顯示重新輸入（程序并不會(huì)結(jié)束）。
然后程序建立頭指針Head并且執(zhí)行CREATE_SL函數(shù)，創(chuàng)建鏈表。
執(zhí)行ShowInput函數(shù)，將n個(gè)人的密碼依次輸出。
下面開(kāi)始執(zhí)行本程序的關(guān)鍵函數(shù)，也是整個(gè)算法的核心函數(shù)ShowOutput，這也是整個(gè)算法的體現(xiàn)：
函數(shù)整體是個(gè)遞歸函數(shù)，運(yùn)用遞歸的思想，效率很高，占用內(nèi)存小，不需要設(shè)置標(biāo)志位來(lái)判斷是否某個(gè)結(jié)點(diǎn)被訪問(wèn)，而是訪問(wèn)到一個(gè)應(yīng)該出列的結(jié)點(diǎn)“出列”，然后以此結(jié)點(diǎn)為下一次遞歸的頭結(jié)點(diǎn)，然后刪除本次遞歸程序充當(dāng)頭結(jié)點(diǎn)的那個(gè)結(jié)點(diǎn)。
圖解：
h，p，s均為指向節(jié)點(diǎn)的指針，第一次執(zhí)行此函數(shù)時(shí)，h指向頭結(jié)點(diǎn)。
p指針尋找到要“出列”的節(jié)點(diǎn)，h指向要出列的結(jié)點(diǎn)作為下一次遞歸的新的頭結(jié)點(diǎn)。
利用p指針和s指針重新改造循環(huán)鏈表,然后s指針用于記錄本次遞歸的頭結(jié)點(diǎn)位置，即將用于刪除、釋放空間。
下面執(zhí)行free(s),刪除所指內(nèi)存空間，開(kāi)始下一次遞歸調(diào)用。
后面執(zhí)行遞歸函數(shù)時(shí)，h剛開(kāi)始指向的是上一次輸出的結(jié)點(diǎn)（還沒(méi)刪除），程序一開(kāi)始先讓s指向h，等這一趟程序快結(jié)束找到下一個(gè)要出列的結(jié)點(diǎn)時(shí)，h指向該結(jié)點(diǎn)作為下一次遞歸函數(shù)的頭結(jié)點(diǎn)，并且讓p找到s指向的充當(dāng)本次頭結(jié)點(diǎn)的結(jié)點(diǎn)，把它刪除，再執(zhí)行此遞歸程序。
終止條件是p->next=h，說(shuō)明沒(méi)有需要輸出的節(jié)點(diǎn)了，于是便實(shí)現(xiàn)了遞歸。如圖所示：
截圖如圖：
六、使用說(shuō)明
按照程序界面指示輸入即可，逐個(gè)整數(shù)數(shù)字輸入，每輸入一個(gè)數(shù)字按一個(gè)回車(chē)。
七、調(diào)試結(jié)果
按照測(cè)試要求進(jìn)行了測(cè)試，結(jié)果如下：
八、遇到的問(wèn)題及解決方法（程序調(diào)試日志）
2018/9/不詳
問(wèn)題：先建立了一個(gè)鏈表實(shí)現(xiàn)插入算法的小功能，再進(jìn)行約瑟夫問(wèn)題求解，結(jié)果程序不停的輸出不完整的數(shù)據(jù)，陷入死循環(huán)。
解決：p指針?biāo)缚臻g邏輯上不該釋放但被不正確釋放，刪去free(p)代碼，一切正常。
2018/9/不詳
問(wèn)題：遞歸程序死循環(huán)。
解決：?jiǎn)尾綀?zhí)行發(fā)現(xiàn)遞歸的終止條件不正確，修改為p->next=h，程序功能實(shí)現(xiàn)！
2018/10/20
最后一天，完善程序，將程序中的注釋寫(xiě)清楚，百度找到了顯示系統(tǒng)時(shí)間的方法，按格式輸出，截屏、書(shū)寫(xiě)報(bào)告。
九、實(shí)驗(yàn)的收獲與感想
個(gè)人感想：循環(huán)鏈表雖然不是很容易理解，但是處理約瑟夫斯這樣的刪除元素的操作真的十分便利，比起數(shù)組要方便的多。但是代價(jià)是編程要仔細(xì)，不要釋放錯(cuò)內(nèi)存空間。
個(gè)人方法優(yōu)點(diǎn)：
1、建立鏈表時(shí)，將頭結(jié)點(diǎn)和頭指針同時(shí)運(yùn)用，使頭指針一開(kāi)始指向頭結(jié)點(diǎn)，這樣操作方便，同時(shí)個(gè)人的算法要利用s刪除上一次h指向的頭結(jié)點(diǎn)，所以一開(kāi)始讓頭指針指向一個(gè)頭結(jié)點(diǎn)對(duì)于個(gè)人的算法是有一定好處的。
2、本人采用遞歸的算法，每次找到要出列的點(diǎn)后，先不馬上刪除結(jié)點(diǎn)，而是將h指針指向此結(jié)點(diǎn)作為下一次遞歸的h結(jié)點(diǎn)，等下一次遞歸找到新的出列結(jié)點(diǎn)并用h指向來(lái)作為頭結(jié)點(diǎn)后，再將廢棄結(jié)點(diǎn)刪除，這樣“改變頭結(jié)點(diǎn)”，操作簡(jiǎn)便，很適合遞歸的條件。
個(gè)人方法缺點(diǎn)：本人認(rèn)為此程序缺點(diǎn)是陌生人剛看到此程序不能馬上理解，因?yàn)檫f歸程序本身不易理解。所以為了更好給別人使用，本人已將程序注釋的很清楚了。
建議：本實(shí)驗(yàn)很好，建議像第四題那樣，增加一項(xiàng)計(jì)算程序空間復(fù)雜度和時(shí)間復(fù)雜度（移動(dòng)次數(shù)）的要求，組織同學(xué)進(jìn)行討論，展示最優(yōu)的算法。
十、源程序
見(jiàn)源程序清單。
實(shí)驗(yàn)二、停車(chē)場(chǎng)管理問(wèn)題
一、問(wèn)題描述
1）問(wèn)題描述
設(shè)停車(chē)場(chǎng)是一個(gè)可停放 n 輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最南端，最先到達(dá)的第一輛車(chē)停放在車(chē)場(chǎng)的最北端）。若停車(chē)場(chǎng)內(nèi)已經(jīng)停滿 n 輛車(chē)，那么后來(lái)的車(chē)只能在門(mén)外的便道上等候。一旦有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)即可開(kāi)入。當(dāng)停車(chē)場(chǎng)內(nèi)某輛車(chē)要離
開(kāi)時(shí)，在它之后進(jìn)入的車(chē)輛必須先退出車(chē)場(chǎng)為它讓路，待該輛車(chē)開(kāi)出大門(mén)外，其他車(chē)輛再
按原次序進(jìn)入車(chē)場(chǎng)。每輛停放在車(chē)場(chǎng)的車(chē)在它離開(kāi)停車(chē)場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短繳納
費(fèi)用。試為停車(chē)場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。
2）基本要求
以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道，按照從終端讀入數(shù)據(jù)的序列進(jìn)行模擬管
理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)的“到達(dá)”（‘A’表示）或“離去”（‘D’表示）信息、汽車(chē)標(biāo)識(shí)（牌照號(hào)）以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車(chē)輛到達(dá)，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或者便道上的停車(chē)位置；若是車(chē)輛離去，則輸出汽車(chē)在停車(chē)場(chǎng)停留的時(shí)間和應(yīng)繳納的費(fèi)用（便道上停留的時(shí)間不收費(fèi)）。棧以順序
結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。
3）測(cè)試數(shù)據(jù)
設(shè) n=2,輸入數(shù)據(jù)為：（‘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）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē) “到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。其中：（‘A’，1，5）表示 1 號(hào)牌照車(chē)在 5 這個(gè)時(shí)刻到達(dá)，而（‘D’，1，15）表示 1 號(hào)牌照車(chē)在 15 這個(gè)時(shí)刻離去。
4）提示
需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車(chē)讓路而從停車(chē)場(chǎng)退出來(lái)的汽車(chē)。輸入數(shù)據(jù)
按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車(chē)，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)的牌照號(hào) 碼和進(jìn)入停車(chē)場(chǎng)的時(shí)刻。
5）輸入輸出:
輸入數(shù)據(jù)：
程序接受 5 個(gè)命令，分別是：到達(dá)（‘A’,車(chē)牌號(hào),時(shí)間)；離去(‘D’,車(chē)牌號(hào),時(shí) 間)；停車(chē)場(chǎng)（‘P’, 0, 0）顯示停車(chē)場(chǎng)的車(chē)數(shù)；候車(chē)場(chǎng)（‘W’, 0, 0）顯示候車(chē)場(chǎng)的車(chē)數(shù)；退出（‘E’, 0, 0）退出程序。
輸出數(shù)據(jù)：
對(duì)于車(chē)輛到達(dá)，要輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或者便道上的停車(chē)位置；對(duì)于車(chē)輛 離去，則輸出汽車(chē)在停車(chē)場(chǎng)停留的時(shí)間和應(yīng)繳納的費(fèi)用（便道上不收費(fèi)）。
二、需求分析
1、本程序用來(lái)模擬停車(chē)場(chǎng)進(jìn)場(chǎng)、進(jìn)便道、場(chǎng)外等候、出場(chǎng)、收費(fèi)等操作。
2、程序運(yùn)行后顯示提示信息，提示用戶(hù)輸入停車(chē)每小時(shí)需繳納的費(fèi)用，用戶(hù)輸入后，提示信息提示用戶(hù)輸入命令：駛?cè)胪＼?chē)場(chǎng)A，離開(kāi)停車(chē)場(chǎng)D，查看停車(chē)場(chǎng)內(nèi)車(chē)數(shù)P 0 0，查看候車(chē)廠內(nèi)車(chē)數(shù)W 0 0，程序結(jié)束E 0 0。
3、程序需判斷用戶(hù)輸入的進(jìn)場(chǎng)出場(chǎng)時(shí)間的有效性，后來(lái)輸入的時(shí)間要大于以前輸入的時(shí)間。
4、用戶(hù)輸入有效命令后，程序顯示汽車(chē)進(jìn)出場(chǎng)信息，若是車(chē)輛到達(dá)，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或者便道上的停車(chē)位置；若是車(chē)輛離去，則輸出汽車(chē)在停車(chē)場(chǎng)停留的時(shí)間和應(yīng)繳納的費(fèi)用。
三、概要設(shè)計(jì)
為了實(shí)現(xiàn)上述功能，需要用棧模擬停車(chē)場(chǎng)，用一個(gè)備用的棧存儲(chǔ)暫時(shí)出場(chǎng)的外部汽車(chē)，用隊(duì)列模擬便道。
1、停車(chē)場(chǎng)“棧”抽象數(shù)據(jù)類(lèi)型定義：
ADT stack{
數(shù)據(jù)對(duì)象：車(chē)牌號(hào)、進(jìn)場(chǎng)時(shí)間、汽車(chē)數(shù)量
數(shù)據(jù)關(guān)系：先入后出
基本操作：
*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、備用存儲(chǔ)“?！背橄髷?shù)據(jù)類(lèi)型定義：
ADT stack1
{
數(shù)據(jù)對(duì)象：車(chē)牌號(hào)、進(jìn)場(chǎng)時(shí)間、汽車(chē)數(shù)量
數(shù)據(jù)關(guān)系：先入后出
基本操作：
*Init_Backup();//置空棧
IsEmpty_Backup(Backup *s);//判空棧
Push_Backup(Backup *s, ElemType license, ElemType timeIn);//入棧
Pop_Backup(Backup *s, ElemType *license,ElemType* timeIn);//出棧
}
3、鏈?zhǔn)疥?duì)列抽象數(shù)據(jù)類(lèi)型定義：
ADT linkqueue
{
數(shù)據(jù)對(duì)象：車(chē)牌號(hào)、汽車(chē)數(shù)量
數(shù)據(jù)關(guān)系：先入先出
基本操作：
*Init_LQueue();//創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)
In_LQueue(LinkQueue *q, ElemType license);//入隊(duì)
IsEmpty_LQueue(LinkQueue *q);//判隊(duì)空
Out_LQueue(LinkQueue *q, ElemType *license);//出隊(duì)
}
4、本程序保護(hù)模塊
主函數(shù)模塊
進(jìn)場(chǎng)模塊：對(duì)于進(jìn)場(chǎng)的命令進(jìn)行完善地操作處理并進(jìn)行狀態(tài)顯示的模塊
出場(chǎng)模塊：對(duì)于出場(chǎng)的命令進(jìn)行完善地操作處理并進(jìn)行狀態(tài)顯示的模塊
置空棧、置空隊(duì)、進(jìn)出棧、進(jìn)出隊(duì)、判棧空棧滿、判隊(duì)空隊(duì)滿模塊：對(duì)棧、備用棧、隊(duì)列進(jìn)行的基本操作
調(diào)用關(guān)系：
5、算法流程圖
四、詳細(xì)設(shè)計(jì)
1、元素類(lèi)型、結(jié)點(diǎn)類(lèi)型和結(jié)點(diǎn)指針類(lèi)型：
#define Maxsize 2 //停車(chē)場(chǎng)最多能停的車(chē)數(shù)
#define ElemType int
int Prize;//每停一個(gè)時(shí)刻收費(fèi)多少元
static int num = 0;//num用于記錄入隊(duì)的車(chē)所在的位置
typedef struct stack //模擬停車(chē)場(chǎng)的棧
{
ElemType license[Maxsize];//用于存放車(chē)牌號(hào)
ElemType timeIn[Maxsize];//用于存放入停車(chē)場(chǎng)時(shí)間
int top;
}Parking;
typedef struct stack1 //退車(chē)時(shí)暫時(shí)存放
{
ElemType license[Maxsize-1];
ElemType timeIn[Maxsize-1];
int top;
}Backup;
typedef struct road
{
ElemType license;
struct road *next;
}Road;
typedef struct linkqueue//隊(duì)列模擬便道
{
Road *front,*rear;
}LinkQueue;
2、部分基本操作的偽碼類(lèi)型
//給停車(chē)場(chǎng)用的配置函數(shù)
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;
}
}
//給備用棧配置的函數(shù)
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;
}
}
//給候車(chē)便道鏈?zhǔn)疥?duì)列配置的函數(shù)
LinkQueue *Init_LQueue()//創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)
{
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)//入隊(duì)
{
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)//判隊(duì)空
{
if(q->front == q->rear)
return 1;
else
return 0;
}
int Out_LQueue(LinkQueue *q, ElemType *license)//出隊(duì)
{
Road *p;
if(IsEmpty_LQueue(q))
{
printf(”隊(duì)空“);
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、主函數(shù)的偽碼
void main()
{
ElemType license, time,timelast=0;//timeInlast是最近一次有車(chē)進(jìn)停車(chē)場(chǎng)的時(shí)間，提示以后輸入的進(jìn)場(chǎng)時(shí)間要大于此數(shù)值
char command;//進(jìn)入A還是離開(kāi)D
Parking *s;
Backup *s1;
LinkQueue *q;
PrintInformation1();//輸出程序信息和個(gè)人信息
s = Init_Parking();//停車(chē)場(chǎng)
q = Init_LQueue();//便道隊(duì)列
s1 = Init_Backup();//退車(chē)時(shí)的備用棧
printf(”請(qǐng)輸入停車(chē)每小時(shí)需交納的費(fèi)用（元）rn“);
setbuf(stdin, NULL);//使stdin輸入流由默認(rèn)緩沖區(qū)轉(zhuǎn)為無(wú)緩沖區(qū),必不可少
scanf(”%d“,&Prize);
setbuf(stdin, NULL);//使stdin輸入流由默認(rèn)緩沖區(qū)轉(zhuǎn)為無(wú)緩沖區(qū),必不可少
while(1)
{
setbuf(stdin, NULL);//使stdin輸入流由默認(rèn)緩沖區(qū)轉(zhuǎn)為無(wú)緩沖區(qū),必不可少
Loop:printf(”請(qǐng)輸入操作的命令，駛?cè)胪＼?chē)場(chǎng)A，離開(kāi)停車(chē)場(chǎng)D，查看停車(chē)場(chǎng)內(nèi)車(chē)數(shù)P 0 0，查看候車(chē)廠內(nèi)車(chē)數(shù)W 0 0，程序結(jié)束E 0 0:n“);
scanf(”%c%d%d“,&command, &license,&time);
setbuf(stdin, NULL);//使stdin輸入流由默認(rèn)緩沖區(qū)轉(zhuǎn)為無(wú)緩沖區(qū),必不可少
if(command == A)
{
if(time <= timelast)
{
printf(”輸入的時(shí)間必須大于上一次輸入的時(shí)間:t“);
printf(”%dt“, timelast);
printf(”請(qǐng)重新輸入n“);
goto Loop;
}
else
{
timelast = time;
GetIn(s,q,license,time);
}
}
if(command == D)
{
if(time <= timelast)
{
printf(”輸入的時(shí)間必須大于上一次輸入的時(shí)間:t“);
printf(”%dt“, timelast);
printf(”請(qǐng)重新輸入n“);
goto Loop;
}
else
{
timelast = time;
GetOut(s, s1, q, license, time);//車(chē)開(kāi)走的函數(shù)
}
}
if(command == P)
{
if(license == 0 && time == 0)
printf(”停車(chē)場(chǎng)內(nèi)停了%d輛車(chē)n“,s->top+1);//顯示停車(chē)場(chǎng)車(chē)數(shù)
}
if(command == W)
{
if(license == 0 && time == 0)
printf(”侯車(chē)場(chǎng)內(nèi)停了%d輛車(chē)n“,num);//顯示候車(chē)場(chǎng)車(chē)數(shù)
}
if(command == E)
{
if(license == 0 && time == 0)
{
PrintInformation2();//程序結(jié)束信息
system(”pause“);
return;
}
}
}
}
五、調(diào)試分析與核心算法解釋
程序本身是利用棧、隊(duì)列的進(jìn)出完成停車(chē)場(chǎng)汽車(chē)進(jìn)出場(chǎng)的模擬的，只要按照模塊化的函數(shù)，按照基本的邏輯編寫(xiě)，調(diào)試是比較容易的。
程序一開(kāi)始會(huì)要求用戶(hù)輸入每小時(shí)繳納多少元費(fèi)用，顯示“請(qǐng)輸入停車(chē)每小時(shí)需交納的費(fèi)用（元）”。
以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道，在while循環(huán)開(kāi)始讓用戶(hù)輸入命令、車(chē)牌號(hào)、時(shí)間三個(gè)變量，對(duì)三個(gè)變量進(jìn)行判斷，并執(zhí)行相應(yīng)函數(shù)。
程序顯示“請(qǐng)輸入操作的命令，駛?cè)胪＼?chē)場(chǎng)A，離開(kāi)停車(chē)場(chǎng)D，查看停車(chē)場(chǎng)內(nèi)車(chē)數(shù)P 0 0，查看候車(chē)廠內(nèi)車(chē)數(shù)W 0 0，程序結(jié)束E 0 0:”
如果后來(lái)輸入的時(shí)間比之前輸入的時(shí)間小，程序會(huì)提示“輸入的時(shí)間必須大于上一次輸入的時(shí)間: xx 請(qǐng)重新輸入”。
其中駛?cè)牒瘮?shù)先判斷是否棧滿，如果棧滿則執(zhí)行入隊(duì)操作，否則入棧，并將車(chē)牌號(hào)、駛?cè)霑r(shí)間存入棧元素?cái)?shù)組，top值加一，用于記錄車(chē)的數(shù)量，用于判斷是否棧滿。
如果棧不滿，程序顯示“車(chē)牌號(hào)為xx的汽車(chē)在xx時(shí)刻停在xx車(chē)位”。
如果棧滿，程序顯示“xx號(hào)車(chē)停在候車(chē)便道的第xx個(gè)位置”。
離開(kāi)函數(shù)先判斷是否棧空，如果?？談t輸出沒(méi)有車(chē)輛提示，否則進(jìn)一步比較是否有棧內(nèi)車(chē)牌號(hào)元素與命令的離開(kāi)的車(chē)牌號(hào)一致，有則出棧，計(jì)算停車(chē)時(shí)間和計(jì)價(jià)，無(wú)則輸出沒(méi)有此車(chē)牌號(hào)的車(chē)的提示。
如果沒(méi)有命令的車(chē)牌號(hào)的汽車(chē)，則顯示“對(duì)不起！停車(chē)場(chǎng)內(nèi)沒(méi)有車(chē)牌號(hào)為xx的車(chē)”。
如果停車(chē)場(chǎng)已空，會(huì)顯示“對(duì)不起！停車(chē)場(chǎng)已空！”。
如果原先棧滿，離開(kāi)一輛車(chē)以后，最早到便道上的一輛車(chē)進(jìn)棧，并顯示“xx號(hào)汽車(chē)此時(shí)退出便道，進(jìn)入停車(chē)場(chǎng)最后一個(gè)位置”。
隊(duì)列和棧的top記錄了車(chē)的數(shù)量，可用于輸出內(nèi)部車(chē)數(shù)，也可用于判斷是否棧滿。
如果三個(gè)變量分別為P,0,0，則輸出停車(chē)場(chǎng)內(nèi)車(chē)的個(gè)數(shù)。
如果三個(gè)變量分別為E,0,0，則輸出便道上車(chē)的個(gè)數(shù)。
如果三個(gè)變量分別為E ,0, 0,則結(jié)束程序。
六、使用說(shuō)明
程序接受 5 個(gè)命令，分別是：到達(dá)（‘A’,車(chē)牌號(hào),時(shí)間)；離去(‘D’,車(chē)牌號(hào),時(shí) 間)；停車(chē)場(chǎng)（‘P’, 0, 0）顯示停車(chē)場(chǎng)的車(chē)數(shù)；候車(chē)場(chǎng)（‘W’, 0, 0）顯示候車(chē)場(chǎng)的車(chē)數(shù)；退出（‘E’, 0, 0）退出程序。
注意：命令字符（A D P W E）用大寫(xiě)，輸入的三個(gè)數(shù)據(jù)之間用空格隔開(kāi)。如A 1 5。代表1號(hào)1號(hào)汽車(chē)在5時(shí)刻進(jìn)場(chǎng)。
七、調(diào)試結(jié)果
按照測(cè)試要求給的數(shù)據(jù)進(jìn)行了測(cè)試：
八、遇到的問(wèn)題和解決方法（程序調(diào)試日志）
2018/9/不詳
問(wèn)題：程序全部結(jié)束，執(zhí)行時(shí)能基本完成功能，但是總是會(huì)間隔有一次命令無(wú)效，重復(fù)輸出“請(qǐng)輸入命令.......”。
解決方法：后來(lái)百度發(fā)現(xiàn)，這是因?yàn)閿?shù)據(jù)緩存區(qū)沒(méi)有清除的緣故，每次回車(chē)都會(huì)在數(shù)據(jù)緩存區(qū)遺留下來(lái)一個(gè)Enter字符，可被char型變量讀取，因此在每次輸入數(shù)據(jù)前后加入一個(gè)清除數(shù)據(jù)緩存區(qū)的函數(shù)setbuf(stdin, NULL)即可解決問(wèn)題。
2018/10/20
最后一天，完善程序，將程序中的注釋寫(xiě)清楚，百度找到了顯示系統(tǒng)時(shí)間的方法，按格式輸出，截屏、書(shū)寫(xiě)報(bào)告。
九、實(shí)驗(yàn)的收獲與感想
個(gè)人感想：
這道題目和后面的第四道題目都是屬于比較透徹的題目，先做了第二題，還是對(duì)第二題印象最深，首先這道題很講究編程的條理性，里面的初始化棧、判?？铡M、入棧、出棧以及初始化隊(duì)列、判隊(duì)空、隊(duì)滿、入隊(duì)、出隊(duì)等函數(shù)在書(shū)上都有，主要的工作是利用模塊化的思想，由整體到局部逐漸求精地去寫(xiě)整個(gè)程序，從而把整個(gè)停車(chē)場(chǎng)的5個(gè)命令功能給實(shí)現(xiàn)，感覺(jué)收獲很多，模塊化的思想很厲害！
方法的優(yōu)點(diǎn)：
整體程序思路比較簡(jiǎn)單，因此個(gè)人沒(méi)有什么更優(yōu)算法，只是在這里面有一個(gè)邏輯，就是后面輸入的時(shí)間不能比之前輸入的時(shí)間小，因?yàn)檫@不符合日常邏輯，同時(shí)也影響了入棧出棧次序，因此我程序里使用了不常用的goto函數(shù)，一般這個(gè)函數(shù)是不建議用的，它會(huì)跳轉(zhuǎn)程序，但是在這里判斷后面輸入的時(shí)間大于之前輸入的時(shí)間后，goto函數(shù)可以讓程序跳轉(zhuǎn)到while循環(huán)開(kāi)始的地方，讓用戶(hù)重新輸入命令，這里感覺(jué)很方便！
建議：
希望多多布置這樣的習(xí)題，有助于教會(huì)學(xué)生利用模塊化思想，不過(guò)希望布置的題目可以是多方向的比如有關(guān)界面制作的題目，把模塊化的函數(shù)給大家，大家進(jìn)行使用，根據(jù)自己愛(ài)好設(shè)計(jì)出相應(yīng)的模塊化功能的程序。
十、源程序
見(jiàn)源程序清單。
實(shí)驗(yàn)三、管道鋪設(shè)施工的最佳方案問(wèn)題
一、問(wèn)題描述
1）問(wèn)題描述
需要在某個(gè)城市 n 個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這 n 個(gè)居民小區(qū)之間只需要鋪設(shè) n-1 條管道即可。假設(shè)任意兩個(gè)小區(qū)之間都可以鋪設(shè)管道，但由于地理環(huán)境不同，所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，這個(gè)問(wèn)題即為求無(wú)向網(wǎng)的最小生成樹(shù)。
2）基本要求
在可能假設(shè)的 m 條管道中，選取 n-1 條管道，使得既能連通 n 個(gè)小區(qū)，又能使總投資最小。每條管道的費(fèi)用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲(chǔ)采用鄰接表的結(jié)構(gòu)。
3）測(cè)試數(shù)據(jù)
使用下圖給出的無(wú)線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。右側(cè)是給出的參考解。
以上是本實(shí)驗(yàn)的題目要求，下面我將介紹我的實(shí)現(xiàn)算法，程序調(diào)試結(jié)果以及編程過(guò)程中遇到的具體問(wèn)題，并且談?wù)勎业氖斋@和感悟！
二、需求分析
1、此程序用來(lái)求無(wú)向帶權(quán)網(wǎng)的最小生成樹(shù)。
2、程序的輸入數(shù)據(jù)放在一個(gè)dat格式的文件中，想要修改輸入數(shù)據(jù)，用記事本打開(kāi)文件直接修改即可。任何時(shí)刻想看到結(jié)果，點(diǎn)擊一下exe文件即可一鍵解決。
3、輸入數(shù)據(jù)的形式是一個(gè)矩陣形式，行和列的元素依次代表A、B、C....，兩點(diǎn)之間有邊，則數(shù)據(jù)是一個(gè)不為0的數(shù)，否則為0。
4、程序運(yùn)行結(jié)果不僅會(huì)在控制臺(tái)顯示出來(lái)，同時(shí)還要在一個(gè)新的文件中顯示出來(lái)，點(diǎn)擊一下exe文件即可一鍵解決，滿足用戶(hù)“即點(diǎn)即看”，輸出文件令用戶(hù)能“隨時(shí)且長(zhǎng)久”看到結(jié)果，不必每一次都要運(yùn)行程序。
三、概要設(shè)計(jì)
為實(shí)現(xiàn)上述功能，應(yīng)以圖的鄰接表數(shù)據(jù)結(jié)構(gòu)，即鏈表與數(shù)組相結(jié)合的數(shù)據(jù)結(jié)構(gòu)。
1、鄰接表抽象數(shù)據(jù)類(lèi)型定義：
ADT ALGraph{
數(shù)據(jù)對(duì)象：結(jié)點(diǎn)A、B、C....數(shù)據(jù)關(guān)系：存儲(chǔ)結(jié)構(gòu)上鏈表式指針相連，物理結(jié)構(gòu)上點(diǎn)之間相連成邊
基本操作：CreateALGraph(ALGraph *G);//建立無(wú)向圖的鄰接表存儲(chǔ)
}ADT ALGraph
2、文件操作模塊
基本操作：
read_data(void);//只讀方式打開(kāi)文件
read_array(double *array,int n1,int n2,FILE *fp);//讀取文件中的邊值信息
cout_data(void);//只寫(xiě)方式打開(kāi)或建立文件
cout_array(double *array,int n1,int n2,FILE *fp);//向文件中寫(xiě)入邊值信息
3、本程序保護(hù)模塊
主程序模塊
建立無(wú)向圖模塊：根據(jù)讀入文件的邊值信息創(chuàng)建無(wú)向圖鄰接表存儲(chǔ)
最小生成樹(shù)模塊：由無(wú)向圖生成最小生成樹(shù)
讀入數(shù)據(jù)模塊：只讀方式讀取文件數(shù)據(jù)
輸出結(jié)果模塊：將結(jié)果輸出到控制臺(tái)
輸出到文件模塊：將結(jié)果輸出到文件
調(diào)用關(guān)系：
四、詳細(xì)設(shè)計(jì)
需要建立一個(gè)無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)，進(jìn)行最小生成樹(shù)的提取。
1、元素類(lèi)型、結(jié)點(diǎn)類(lèi)型和結(jié)點(diǎn)指針類(lèi)型：
#define MaxVertexNum 100 //設(shè)置小區(qū)數(shù)最多為100
#define VertexNum 9
double LeastNum;//用于記錄最短邊長(zhǎng)度
double LongestNum;//用于記錄最長(zhǎng)邊長(zhǎng)度，程序過(guò)程中不改變
double adjacent[VertexNum][VertexNum];
//鄰接矩陣，不用于處理數(shù)據(jù)，而是用于暫時(shí)存儲(chǔ)從文件讀來(lái)的數(shù)據(jù)
//進(jìn)而在鄰接表存儲(chǔ)數(shù)據(jù)時(shí)讀取此數(shù)組數(shù)據(jù)即可
//二維數(shù)組數(shù)據(jù)為0的元素說(shuō)明之間沒(méi)有通道
//在處理完數(shù)據(jù)后，此數(shù)組會(huì)用來(lái)暫時(shí)存儲(chǔ)處理后的數(shù)據(jù)，并寫(xiě)入到另一個(gè)文件中
typedef struct vnode
{//頂點(diǎn)表結(jié)點(diǎn)
char vertex;
EdgeNode *firstedge;
}VertexNode;
typedef struct
{
VertexNode adjlist[MaxVertexNum];
int n,e;
}ALGraph;
2、有序表類(lèi)型：
typedef struct node
{//邊表結(jié)點(diǎn)
char adjvex;
double weight;//權(quán)值
struct node *next;
}EdgeNode;
3、主函數(shù)的偽碼：
void main()
{
ALGraph *G;
PrintInformation1();
G =(ALGraph*)malloc(sizeof(ALGraph));
G->n = VertexNum;//為G指向的圖分配空間，設(shè)置點(diǎn)數(shù)（小區(qū)數(shù)）
read_data();
CreateALGraph(G);
MinimumSpanningTree(G);
cout_data();//輸出到文件
ResultOutput((double *)adjacent,VertexNum,VertexNum);//輸出到控制臺(tái)
PrintInformation2();
system(”pause“);
}
4、算法流程圖
五、調(diào)試分析與核心算法解釋
此題按照Prim算法，設(shè)置一個(gè)用于存儲(chǔ)點(diǎn)的點(diǎn)集，找短邊從一個(gè)點(diǎn)向兩點(diǎn)、三個(gè)....更多逐漸擴(kuò)張，即可得到最小生成樹(shù)。
1).輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為V，邊集合為E；
2).初始化：Vnew = {x}，其中x為集合V中的任一節(jié)點(diǎn)（起始點(diǎn)），Enew = {},為空；
3).重復(fù)下列操作，直到Vnew = V：
a.在集合E中選取權(quán)值最小的邊
b.將v加入集合Vnew中，將
4).輸出：使用集合Vnew和Enew來(lái)描述所得到的最小生成樹(shù)。
具體可以參考資料：https://baike.baidu.com/redirect/cb1fkztQc2TOscNlcMemKsGZ1fsgTprJsdBq_APeZx74W4q4TzbKXHsvSYW_6aM1DqhF56eTgD8EZLzBCQHKBGa6ExWmgXbju_gm13Qbbu0KxbHuiIS_DxEp2fgT3BU
六、使用說(shuō)明
輸入數(shù)據(jù)已經(jīng)在”gyp_program3_Input.dat“中寫(xiě)好，如果想做修改可以在該文件中修改即可，輸出的數(shù)據(jù)既在控制臺(tái)顯示，也會(huì)輸出到”gyp_program3_Output.dat“。
七、調(diào)試結(jié)果
輸入數(shù)據(jù)文件：
這是一個(gè)矩陣，例如：第2行，第3列代表B，C兩點(diǎn)間的邊，0代表無(wú)邊，不為0代表有邊。
控制臺(tái)程序顯示：
輸出數(shù)據(jù)到輸出文件
八、遇到的問(wèn)題和解決方法（程序調(diào)試日志）
2018/9/不詳
問(wèn)題：一進(jìn)入建立無(wú)向圖的函數(shù)程序就中止出錯(cuò)。
解決方法：給建立無(wú)向圖函數(shù)傳遞的形參是指針，而在主函數(shù)中G指針沒(méi)有賦給內(nèi)存空間，所以函數(shù)無(wú)法對(duì)G所指的空間進(jìn)行初始化，在主程序中加入這樣一句代碼就好了：
G =(ALGraph*)malloc(sizeof(ALGraph));
2018/10/17
問(wèn)題：輸出的二維數(shù)組只有一位正常，其余全是0。如下圖所示：
解決方法：后來(lái)發(fā)現(xiàn)是里面flag2這個(gè)標(biāo)志位剛開(kāi)始是1，程序執(zhí)行過(guò)程中被置0用于判斷，但是判斷以后沒(méi)有再次重置為1，導(dǎo)致要用很多次的標(biāo)志位只發(fā)揮了一次作用，后面就誤判了，在循環(huán)結(jié)束加入重置1的語(yǔ)句即可。
問(wèn)題：輸出的二維數(shù)組輸出數(shù)據(jù)不完整，里面總有最小的邊（問(wèn)題切入點(diǎn)）。
解決方法：?jiǎn)尾綀?zhí)行后發(fā)現(xiàn)，某一次循環(huán)中Leastnum這個(gè)變量得到的最小值恰好是所有邊中最小的一個(gè)，它在發(fā)揮完比較作用后，沒(méi)有被置為一個(gè)很大的數(shù)（不小于這些邊中最大值即可），結(jié)果在下一次循環(huán)的時(shí)候，導(dǎo)致后面的邊都比它大，以至于后面的邊都被舍去了，解決方法就是每次循環(huán)第一句先把原圖的最大邊賦給leastnum。
問(wèn)題：直接運(yùn)行debug文件夾里的exe程序，且debug程序終止，懷疑是文件數(shù)據(jù)讀取失敗，無(wú)法打開(kāi)文件，即文件不存在。
解決方法：如果不詳細(xì)說(shuō)明文件路徑，程序本身會(huì)在當(dāng)前文件夾內(nèi)找文件，存數(shù)據(jù)的文件gyp_program3_Input.dat要保存在當(dāng)前文件中。也就是和源代碼在同一個(gè)文件夾中，但是這樣子的話，只有用編程軟件打開(kāi)代碼運(yùn)行，dat文件才有效，若想在debug里直接運(yùn)行exe程序，則把存數(shù)據(jù)的輸入文件同名復(fù)制到debug文件夾里即可。
九、實(shí)驗(yàn)的收獲和感想
個(gè)人感想：這個(gè)程序可以說(shuō)是算法感十足了，也是我遇到問(wèn)題最大的一個(gè)程序，但是也證明了自己的能力，學(xué)到了很多，收獲最大的就是：對(duì)于用的不止一次的標(biāo)志位，一定不可能只單方向置位，一定是雙向置位，一次循環(huán)結(jié)束一定要記得置位，否則用了這一次以后，后面的循環(huán)就會(huì)誤判！
Prim算法真的很好用，不僅適合求帶球圖的最小生成樹(shù)，還適合尋找一個(gè)點(diǎn)到另一點(diǎn)的最短路徑。
個(gè)人方法優(yōu)點(diǎn)：輸入方便，輸出簡(jiǎn)潔。讀取文件中的數(shù)據(jù)，不用手動(dòng)輸入，想修改數(shù)據(jù)在文件中修改就可以，另外輸出有兩種形式，一種是控制臺(tái)輸出，一種是輸出到文件，輸出的是一個(gè)二維數(shù)組，行和列都有表頭，看起來(lái)很清晰，兩個(gè)點(diǎn)之間若有邊，相應(yīng)二維坐標(biāo)的元素就是邊值，無(wú)邊則相應(yīng)的位置為0。
建議：可以要求用順序表的方法，因?yàn)閺睦斫夂途幊屉y度角度考慮，圖的鄰接表找邊會(huì)很慢每次都要順著其中一個(gè)鏈表頭結(jié)點(diǎn)去尋找，不過(guò)這也很鍛煉人的能力！
十、源程序
見(jiàn)源程序清單。
實(shí)驗(yàn)四、內(nèi)部排序算法的實(shí)現(xiàn)與比較
一、問(wèn)題描述
1）問(wèn)題描述
在教科書(shū)中，各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過(guò)隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。
2）基本要求
(1)對(duì)常用的內(nèi)部排序算法進(jìn)行比較：直接插入排序、簡(jiǎn)單選擇排序、冒泡排序、快速排序、希爾排序。
(2)利用隨機(jī)函數(shù)產(chǎn)生N（如30000）個(gè)隨機(jī)整數(shù)，作為輸入數(shù)據(jù)作比較；比較的指標(biāo)為關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為3次移動(dòng)）。
(3)對(duì)結(jié)果作出簡(jiǎn)要分析。
3）測(cè)試數(shù)據(jù)
隨機(jī)函數(shù)產(chǎn)生。
4）提示
主要工作是設(shè)法在已知算法中適當(dāng)位置插入對(duì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)數(shù)操 作。注意采用分塊調(diào)試的方法。
5）輸入輸出:
輸入數(shù)據(jù)：參加排序的整數(shù)個(gè)數(shù) n（如 n=30000）；
輸出數(shù)據(jù)：各種排序方法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)（從小到大排列）。
二、需求分析
1、本程序用來(lái)比較5種排序的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)。
2、本程序用srand()和rand()函數(shù)產(chǎn)生N個(gè)隨機(jī)數(shù)用于排序方法的比較，用戶(hù)無(wú)需輸入。
3、運(yùn)行程序后，程序需按從小到大的順序分別輸出5種排序的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)。
三、概要設(shè)計(jì)
為實(shí)現(xiàn)上述功能，程序需要產(chǎn)生N個(gè)隨機(jī)數(shù)，并且需要寫(xiě)出這5種排序的排序函數(shù)。
1、產(chǎn)生N個(gè)隨機(jī)數(shù)的方法
srand((unsigned)(time(NULL)));
for(int j = 0;j < N;j++)
{
num0[j] = rand();
}
2、保證每次排序的數(shù)據(jù)都相同的方法
num0數(shù)組用于得到隨機(jī)數(shù)，num數(shù)組每次排序前先用num0數(shù)組賦值即可。
for(int j=0;j { num[j] = num0[j]; } InsertSort(num,N);3、5種排序函數(shù) 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、本程序保護(hù)模塊 主程序模塊 排序模塊 比較輸出模塊 調(diào)用關(guān)系： 4、算法流程圖 四、詳細(xì)設(shè)計(jì) 1、排序函數(shù)基本操作的偽碼實(shí)現(xiàn) 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、主函數(shù)偽碼實(shí)現(xiàn) int main() { //數(shù)組設(shè)為N+1個(gè)是因?yàn)橛行┧惴ㄊ菑臄?shù)組1到N存儲(chǔ)的，0位有的不用，有的用作了哨兵 int num0[N+1];//記錄最原先隨機(jī)產(chǎn)生的N個(gè)數(shù)字，因?yàn)閚um[N]每排序一次都會(huì)改變 int num[N+1];//每次排序前先讀入num0[N]數(shù)據(jù) //srand函數(shù)只增加一次就夠了，用系統(tǒng)當(dāng)前時(shí)間設(shè)置rand()隨機(jī)序列種子，保證每次運(yùn)行隨機(jī)序列不一樣 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(”關(guān)鍵字比較次數(shù)按從小到大排列分別是：rn“); KeyCompareNum_pailie(); printf(”rn“); printf(”移動(dòng)次數(shù)按從小到大排列分別是：rn“); MoveNum_pailie(); PrintInformation2(); system(”pause“); return 0; } 五、調(diào)試分析與核心算法解釋 程序的5種排序函數(shù)可以自己寫(xiě)，也可以百度找源碼，總之五種排序函數(shù)寫(xiě)完以后，調(diào)試的關(guān)鍵是設(shè)置計(jì)數(shù)變量，并在這些函數(shù)的合適位置進(jìn)行加1計(jì)數(shù)或加3計(jì)數(shù)，因此注意分塊調(diào)試，分函數(shù)調(diào)試，做到這幾點(diǎn)調(diào)試難度總體不大。 六、使用說(shuō)明 隨機(jī)數(shù)產(chǎn)生，5種排序用的都是同一組N個(gè)隨機(jī)數(shù)，用戶(hù)無(wú)需輸入，直接運(yùn)行程序即可輸出運(yùn)算結(jié)果。 七、調(diào)試結(jié)果 八、遇到的問(wèn)題和解決方法（程序調(diào)試日志） 2018/10/19 問(wèn)題：第一種排序輸出很大，后面輸出很小，幾乎沒(méi)作用。 解決方法：每經(jīng)過(guò)一個(gè)排序函數(shù)，數(shù)組已經(jīng)排好序了，不能直接調(diào)用其余的排序函數(shù)，而是要在程序一開(kāi)始就用另一個(gè)數(shù)組num0[N]記錄了隨機(jī)數(shù)產(chǎn)生的數(shù)組num[N]，因此只需要在每次排序前，把num0數(shù)組中數(shù)據(jù)重新賦給num數(shù)據(jù)即可參與排序了。 問(wèn)題：數(shù)據(jù)輸出個(gè)數(shù)少于5個(gè)，單步執(zhí)行發(fā)現(xiàn)循環(huán)不到5次。 解決方案：分析后發(fā)現(xiàn)，程序的幾個(gè)for循環(huán)，內(nèi)層的循環(huán)里面的計(jì)數(shù)加1變量如i，j，和外層循環(huán)設(shè)置的加1變量用的是一個(gè)變量，導(dǎo)致內(nèi)層循環(huán)計(jì)數(shù)變量的改變會(huì)影響外層循環(huán)，導(dǎo)致輸出個(gè)數(shù)小于5。將這些變量設(shè)置成不同變量就不影響了（相互獨(dú)立的循環(huán)可能不會(huì)影響，但內(nèi)外層關(guān)系的兩個(gè)循環(huán)絕對(duì)不能用同一個(gè)計(jì)數(shù)變量）。 問(wèn)題：程序末尾會(huì)跳出一個(gè)程序中止警告框，說(shuō)是棧釋放的問(wèn)題。 解決方案：百度發(fā)現(xiàn)，這實(shí)際上是數(shù)組越界的問(wèn)題，把數(shù)組個(gè)數(shù)設(shè)置為N+1大小的，就好了。 九、實(shí)驗(yàn)的收獲和感想 個(gè)人感想：這個(gè)程序難度不大，關(guān)鍵在于在合適的位置插入用于記錄的變量+1或者+3,真正有技術(shù)含量的在于按照從小到大的順序輸出相應(yīng)數(shù)據(jù)。收獲比較大的一個(gè)技巧：相互獨(dú)立的循環(huán)計(jì)數(shù)變量可能不會(huì)影響，但內(nèi)外層關(guān)系的兩個(gè)循環(huán)絕對(duì)不能用同一個(gè)計(jì)數(shù)變量，否則程序循環(huán)次數(shù)就會(huì)亂！ 從關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)來(lái)看，選擇和快速排序都是非常高效的，希爾排序也不錯(cuò)，不要用或少用冒泡排序和直接插入排序。 個(gè)人方法的優(yōu)點(diǎn)：只產(chǎn)生了1次隨機(jī)數(shù)，5次排序的用的都是同一組數(shù)據(jù)，可以更好地更嚴(yán)謹(jǐn)?shù)乇容^出這5種算法的優(yōu)劣。 個(gè)人方法的缺點(diǎn)：因?yàn)橐伴L(zhǎng)久”保留產(chǎn)生的隨機(jī)數(shù)，因此需多設(shè)置一個(gè)數(shù)組，占用內(nèi)存空間比較大。 十、源程序 源程序見(jiàn)源程序清單。 參考資料 https://blog.csdn.net/guanyasu/article/details/53153705 https://jingyan.baidu.com/article/49711c616b8a1ffa441b7cdc.html https://zhidao.baidu.com/question/***684.html 源程序清單 實(shí)驗(yàn)一、約瑟夫斯問(wèn)題求解 #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);//每個(gè)人的密碼輸入 void ShowOutput(SLNODE*,int);//排列輸出 void PrintInformation1();//輸出程序信息和個(gè)人信息 void PrintInformation2();//程序結(jié)束信息 void PrintTime();//輸出時(shí)間 int main() { int m,n,mistake=1; SLNODE *Head; PrintInformation1();//輸出程序信息和個(gè)人信息 while(mistake) { printf(”輸入人數(shù)n:n“); scanf_s(”%d“, &n); printf(”請(qǐng)指定初始報(bào)數(shù)上限m(m應(yīng)必須小于等于n):n“); scanf_s(”%d“, &m); if(m>n) { printf(”輸入數(shù)據(jù)有誤，請(qǐng)重新輸入n“); } else mistake=0; } Head =(SLNODE *)malloc(sizeof(SLNODE)); Head->next = NULL; Head = CREATE_SL(Head,n); ShowInput(Head,n); printf(”正確的出列順序?yàn)?rn“); ShowOutput(Head,m); PrintInformation2();//程序結(jié)束信息 system(”pause“); return 0; } void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”實(shí)驗(yàn)名稱(chēng):實(shí)驗(yàn)一.約瑟夫斯問(wèn)題求解rn“); printf(”學(xué)號(hào):031650106rn“); printf(”姓名:郭硯璞rn“); printf(”====================rn“); printf(”程序運(yùn)行開(kāi)始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序運(yùn)行結(jié)束,Current local time and date:“); PrintTime(); } SLNODE *CREATE_SL(SLNODE *h,int n) //創(chuàng)建一個(gè)h為頭指針的鏈表，h指向的結(jié)點(diǎn)數(shù)據(jù)域用不到 { ElemType data; int i = 1; SLNODE *p, *s; p = h; while(i<=n) { printf(”請(qǐng)輸入第%d個(gè)元素: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(”個(gè)人的密碼依次為:“); while((p->next)!= h) { p = p->next; printf(”%dt“, p->data[1]); } printf(”n“); } void ShowOutput(SLNODE *h, int m) { SLNODE *p, *s;//s用于記錄上一個(gè)節(jié)點(diǎn)，從而使p結(jié)點(diǎn)找到它將其刪除 int j = 0; s = h;//第一次執(zhí)行此函數(shù)時(shí)，h指向頭結(jié)點(diǎn)；后面遞歸執(zhí)行時(shí)，h剛開(kāi)始指向的是上一//次輸出的結(jié)點(diǎn)（還沒(méi)刪除） //都用s來(lái)記錄，等那一趟程序快結(jié)束找到下一個(gè)要出列的的點(diǎn)時(shí)，h指向那個(gè)結(jié)點(diǎn)作為頭結(jié)點(diǎn)，并且讓p找到s指向的 //上一個(gè)結(jié)點(diǎn)，把它刪除。 p = h; while(j < m-1) { p = p->next; if(p->next==h)//不能讓h所指向的結(jié)點(diǎn)（上一次輸出的結(jié)點(diǎn)，暫時(shí)用作頭結(jié)點(diǎn)所以//還未刪除）影響小循環(huán)次數(shù) { p=p->next;//所以此處讓p多移動(dòng)一下，等下一次小循環(huán)讓p順利移動(dòng)到下一//個(gè)節(jié)點(diǎn)（從而忽略掉h指向的結(jié)點(diǎn)） } //等找到下一個(gè)該出列的結(jié)點(diǎn)時(shí)，h指向那個(gè)結(jié)點(diǎn)（充當(dāng)下一次的頭節(jié)點(diǎn)），充當(dāng)上一次頭//結(jié)點(diǎn)的結(jié)點(diǎn)利用s刪除 j++; }//此時(shí)p指向第m-1個(gè)結(jié)點(diǎn) if(p->next == h)//整個(gè)程序的終止條件，依次回到上個(gè)函數(shù)結(jié)尾，相當(dāng)于全部結(jié)束了 { return; } h= p->next; p = h;//此時(shí)h和p均指向要出列的結(jié)點(diǎn) printf(”%dt“, h->data[0]); j = 0;//j用于while循環(huán)，使h指針指向要出列的點(diǎn)的前一個(gè)結(jié)點(diǎn)，所以及時(shí)清零 while(p->next!=s)//找s廢棄節(jié)點(diǎn) { p = p->next; } s = p->next; p->next = s->next;//連接新結(jié)點(diǎn) free(s);//釋放s所指空間 ShowOutput(h,h->data[1]); } 實(shí)驗(yàn)二、停車(chē)場(chǎng)管理問(wèn)題 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ #define Maxsize 2 //停車(chē)場(chǎng)最多能停的車(chē)數(shù) #define ElemType int int Prize;//每停一個(gè)時(shí)刻收費(fèi)多少元 static int num = 0;//num用于記錄入隊(duì)的車(chē)所在的位置 typedef struct stack //模擬停車(chē)場(chǎng)的棧 { ElemType license[Maxsize];//用于存放車(chē)牌號(hào) ElemType timeIn[Maxsize];//用于存放入停車(chē)場(chǎng)時(shí)間 int top; }Parking; typedef struct stack1 //退車(chē)時(shí)暫時(shí)存放 { ElemType license[Maxsize-1]; ElemType timeIn[Maxsize-1]; int top; }Backup; typedef struct road { ElemType license; struct road *next; }Road; typedef struct linkqueue//隊(duì)列模擬便道 { Road *front,*rear; }LinkQueue; void GetIn(Parking *s, LinkQueue *q, ElemType license, ElemType timeIn);//有車(chē)進(jìn)來(lái) void GetOut(Parking *s, Backup *s1, LinkQueue *q, ElemType license, ElemType timeOut);//有車(chē)//出去 void PrintInformation1();//輸出程序信息和個(gè)人信息 void PrintInformation2();//程序結(jié)束信息 void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”實(shí)驗(yàn)名稱(chēng):實(shí)驗(yàn)二.停車(chē)場(chǎng)管理問(wèn)題rn“); printf(”學(xué)號(hào):031650106rn“); printf(”姓名:郭硯璞rn“); printf(”====================rn“); printf(”程序運(yùn)行開(kāi)始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序運(yùn)行結(jié)束,Current local time and date:“); PrintTime(); } //給停車(chē)場(chǎng)用的配置函數(shù) 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; } } //給備用棧配置的函數(shù) 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; } } //給候車(chē)便道鏈?zhǔn)疥?duì)列配置的函數(shù) LinkQueue *Init_LQueue()//創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空隊(duì) { 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)//入隊(duì) { 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)//判隊(duì)空 { if(q->front == q->rear) return 1; else return 0; } int Out_LQueue(LinkQueue *q, ElemType *license)//出隊(duì) { Road *p; if(IsEmpty_LQueue(q)) { printf(”隊(duì)空“); 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是最近一次有車(chē)進(jìn)停車(chē)場(chǎng)的時(shí)間，提示以后輸入的進(jìn)場(chǎng)時(shí)間要大于此數(shù)值 char command;//進(jìn)入A還是離開(kāi)D Parking *s; Backup *s1; LinkQueue *q; PrintInformation1();//輸出程序信息和個(gè)人信息 s = Init_Parking();//停車(chē)場(chǎng) q = Init_LQueue();//便道隊(duì)列 s1 = Init_Backup();//退車(chē)時(shí)的備用棧 printf(”請(qǐng)輸入停車(chē)每小時(shí)需交納的費(fèi)用（元）rn“); setbuf(stdin, NULL);//使stdin輸入流由默認(rèn)緩沖區(qū)轉(zhuǎn)為無(wú)緩沖區(qū),必不可少 scanf(”%d“,&Prize); setbuf(stdin, NULL);//使stdin輸入流由默認(rèn)緩沖區(qū)轉(zhuǎn)為無(wú)緩沖區(qū),必不可少 while(1) { setbuf(stdin, NULL);//使stdin輸入流由默認(rèn)緩沖區(qū)轉(zhuǎn)為無(wú)緩沖區(qū),必不可少 Loop:printf(”請(qǐng)輸入操作的命令，駛?cè)胪＼?chē)場(chǎng)A，離開(kāi)停車(chē)場(chǎng)D，查看停車(chē)場(chǎng)內(nèi)車(chē)數(shù)P 0 0，查看候車(chē)廠內(nèi)車(chē)數(shù)W 0 0，程序結(jié)束E 0 0:n“); scanf(”%c%d%d“,&command, &license,&time); setbuf(stdin, NULL);//使stdin輸入流由默認(rèn)緩沖區(qū)轉(zhuǎn)為無(wú)緩沖區(qū),必不可少 if(command == A) { if(time <= timelast) { printf(”輸入的時(shí)間必須大于上一次輸入的時(shí)間:t“); printf(”%dt“, timelast); printf(”請(qǐng)重新輸入n“); goto Loop; } else { timelast = time; GetIn(s,q,license,time); } } if(command == D) { if(time <= timelast) { printf(”輸入的時(shí)間必須大于上一次輸入的時(shí)間:t“); printf(”%dt“, timelast); printf(”請(qǐng)重新輸入n“); goto Loop; } else { timelast = time; GetOut(s, s1, q, license, time);//車(chē)開(kāi)走的函數(shù) } } if(command == P) { if(license == 0 && time == 0) printf(”停車(chē)場(chǎng)內(nèi)停了%d輛車(chē)n“,s->top+1);//顯示停車(chē)場(chǎng)車(chē)數(shù) } if(command == W) { if(license == 0 && time == 0) printf(”侯車(chē)場(chǎng)內(nèi)停了%d輛車(chē)n“,num);//顯示候車(chē)場(chǎng)車(chē)數(shù) } if(command == E) { if(license == 0 && time == 0) { PrintInformation2();//程序結(jié)束信息 system(”pause“); return; } } } } //停車(chē)函數(shù) void GetIn(Parking *s, LinkQueue *q,ElemType license, ElemType timeIn) { if(Push_Parking(s, license, timeIn)== 1)//說(shuō)明成功進(jìn)入停車(chē)場(chǎng) { printf(”%d號(hào)車(chē)在%d時(shí)刻停在停車(chē)場(chǎng)第%d個(gè)位置nn“,license,timeIn,s->top+1); } else //棧滿，汽車(chē)要進(jìn)入便道，即入隊(duì) { num++; In_LQueue(q,license); printf(”%d號(hào)車(chē)停在候車(chē)便道的第%d個(gè)位置nn“,license,num); } } void GetOut(Parking *s, Backup *s1,LinkQueue *q, ElemType license, ElemType timeOut) { ElemType *licen, *tim;//兩個(gè)指針賦給出棧函數(shù)，用于讀取車(chē)牌號(hào)和進(jìn)停車(chē)場(chǎng)時(shí)間 ElemType ParkTime;//汽車(chē)在停車(chē)場(chǎng)停留的時(shí)間 ElemType Money;//汽車(chē)應(yīng)繳金額 licen =(ElemType*)malloc(sizeof(ElemType)); tim=(ElemType*)malloc(sizeof(ElemType)); if(IsEmpty_Parking(s))//先判斷停車(chē)場(chǎng)內(nèi)是否有車(chē) { printf(”對(duì)不起！停車(chē)場(chǎng)已空！nn“); return; } while(s->license[s->top]!= license) { Pop_Parking(s,licen,tim); Push_Backup(s1, *licen, *tim); if(IsEmpty_Parking(s)==1) { printf(”對(duì)不起！停車(chē)場(chǎng)內(nèi)沒(méi)有車(chē)牌號(hào)為%d的車(chē)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(”汽車(chē)在停車(chē)場(chǎng)內(nèi)停留的時(shí)間為%d小時(shí),應(yīng)繳費(fèi)%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號(hào)汽車(chē)此時(shí)退出便道，進(jìn)入停車(chē)場(chǎng)最后一個(gè)位置nn“,*licen); num--; } } } 實(shí)驗(yàn)三、管道鋪設(shè)施工的最佳方案問(wèn)題 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ #define MaxVertexNum 100 //設(shè)置小區(qū)數(shù)最多為100 #define VertexNum 9 double LeastNum;//用于記錄最短邊長(zhǎng)度 double LongestNum;//用于記錄最長(zhǎng)邊長(zhǎng)度，程序過(guò)程中不改變 double adjacent[VertexNum][VertexNum]; //鄰接矩陣，不用于處理數(shù)據(jù)，而是用于暫時(shí)存儲(chǔ)從文件讀來(lái)的數(shù)據(jù) //進(jìn)而在鄰接表存儲(chǔ)數(shù)據(jù)時(shí)讀取此數(shù)組數(shù)據(jù)即可 //二維數(shù)組數(shù)據(jù)為0的元素說(shuō)明之間沒(méi)有通道 //在處理完數(shù)據(jù)后，此數(shù)組會(huì)用來(lái)暫時(shí)存儲(chǔ)處理后的數(shù)據(jù)，并寫(xiě)入到另一個(gè)文件中 typedef struct node {//邊表結(jié)點(diǎn) char adjvex; double weight;//權(quán)值 struct node *next; }EdgeNode; typedef struct vnode {//頂點(diǎn)表結(jié)點(diǎn) char vertex; EdgeNode *firstedge; }VertexNode; typedef struct { VertexNode adjlist[MaxVertexNum]; int n,e; }ALGraph; void PrintInformation1();//輸出程序信息和個(gè)人信息 void PrintInformation2();//程序結(jié)束信息 void CreateALGraph(ALGraph *);//將文件中數(shù)據(jù)導(dǎo)入進(jìn)來(lái)構(gòu)建無(wú)向圖鄰接表 void MinimumSpanningTree(ALGraph *);//將無(wú)向圖轉(zhuǎn)化為最小生成樹(shù) void ResultOutput(double *array,int n1,int n2);//將數(shù)據(jù)在控制臺(tái)顯示出來(lái) void read_data(void);//從輸入文件讀取數(shù)據(jù)到鄰接矩陣 void cout_data(void);//將鄰接矩陣中的數(shù)據(jù)輸出到輸出文件 void read_array(double *array,int n1,int n2,FILE *fp);//內(nèi)部函數(shù)，用戶(hù)無(wú)需調(diào)用 void cout_array(double *array,int n1,int n2,FILE *fp);//內(nèi)部函數(shù)，用戶(hù)無(wú)需調(diào)用 void main() { ALGraph *G; PrintInformation1(); G =(ALGraph*)malloc(sizeof(ALGraph)); G->n = VertexNum;//為G指向的圖分配空間，設(shè)置點(diǎn)數(shù)（小區(qū)數(shù)） read_data(); CreateALGraph(G); MinimumSpanningTree(G); cout_data();//輸出到文件 ResultOutput((double *)adjacent,VertexNum,VertexNum);//輸出到控制臺(tái) PrintInformation2(); system(”pause“); } void PrintTime() { time_t t; time(&t); printf(”%s“, ctime(&t)); printf(”rn“); } void PrintInformation1() { printf(”實(shí)驗(yàn)名稱(chēng):實(shí)驗(yàn)三.管道鋪設(shè)施工的最佳方案問(wèn)題rn“); printf(”學(xué)號(hào):031650106rn“); printf(”姓名:郭硯璞rn“); printf(”====================rn“); printf(”程序運(yùn)行開(kāi)始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序運(yùn)行結(jié)束,Current local time and date:“); PrintTime(); } void CreateALGraph(ALGraph *G) { //建立無(wú)向圖的鄰接表存儲(chǔ) 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));//控制臺(tái)輸出列表頭 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“);// 輸入數(shù)據(jù)文件 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設(shè)置的初值為最大邊邊值 } } } } 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“);//輸出數(shù)據(jù)文件 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);//控制臺(tái)輸出行表頭 for(j=0;j { printf(”%.1ft“,*array); array++; } printf(”n“); } } void MinimumSpanningTree(ALGraph *G) {//將無(wú)向圖轉(zhuǎn)化為最小生成樹(shù) 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;//初始點(diǎn)放入點(diǎn)集 for(i=0;i //剛開(kāi)始只有一個(gè)起始點(diǎn)，之后加入剩余的VertexNum個(gè)點(diǎn)，即VertexNum-1次循環(huán) { LeastNum = LongestNum;//這一步很重要，每加入一個(gè)點(diǎn)，應(yīng)把LeastNum初始化為//最大值，避免受之前數(shù)值的影響 for(j = 0;j < i + 1;j++)//第i次點(diǎn)集里有i+1個(gè)點(diǎn)，即比較這i+1個(gè)點(diǎn)與生于點(diǎn)邊的大//小，找最小邊的另一個(gè)點(diǎn) { point = NowAdjacent[j]-A;//用于指示已經(jīng)存進(jìn)點(diǎn)集中的點(diǎn)是圖的第幾個(gè)點(diǎn) s = G->adjlist[point].firstedge; while(s!= NULL) { for(k = 0;k < i + 1;k++) { if(s->adjvex == NowAdjacent[k]) { flag2 = 0;//flag2=0用于指示此時(shí)s所指的點(diǎn)已經(jīng)在點(diǎn)集內(nèi) break; } } if(flag2 == 1)//確保僅當(dāng)s指向的點(diǎn)是不在點(diǎn)集里的點(diǎn)時(shí)，才被比較處理 { if((LeastNum > s->weight)&&(s->weight!=0)) { end = s->adjvex-A;//flag用于指示最短邊是第幾個(gè)點(diǎn) start = point; LeastNum = s->weight; } } s = s->next; flag2 = 1;//標(biāo)志位有可能已經(jīng)被清0，必須重設(shè)為1，確保不影響下一次 } //啟發(fā)：對(duì)于用的不止一次的標(biāo)志位，一定不可能只單方向置位，一定是雙向置位，//否則用了一次，后面就會(huì)誤判 } adjacent[start][end] = LeastNum; adjacent[end][start] = LeastNum; NowAdjacent[i + 1] = G->adjlist[end].vertex;//向點(diǎn)集加入新點(diǎn) } } 實(shí)驗(yàn)四、內(nèi)部排序算法的實(shí)現(xiàn)與比較 #include ”stdio.h“ #include ”stdlib.h“ #include ”time.h“ const int N=3000;//隨機(jī)產(chǎn)生N個(gè)隨機(jī)整數(shù) void PrintInformation1();//輸出程序信息和個(gè)人信息 void PrintInformation2();//程序結(jié)束信息 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};//分別存儲(chǔ)這5種排序的關(guān)鍵字比較次數(shù) int MoveNum[5]={0};//分別存儲(chǔ)這5種排序的移動(dòng)次數(shù) int main() { //數(shù)組設(shè)為N+1個(gè)是因?yàn)橛行┧惴ㄊ菑臄?shù)組1到N存儲(chǔ)的，0位有的不用，有的用作了哨兵 int num0[N+1];//記錄最原先隨機(jī)產(chǎn)生的N個(gè)數(shù)字，因?yàn)閚um[N]每排序一次都會(huì)改變 int num[N+1];//每次排序前先讀入num0[N]數(shù)據(jù) //srand函數(shù)只增加一次就夠了，用系統(tǒng)當(dāng)前時(shí)間設(shè)置rand()隨機(jī)序列種子，保證每次運(yùn)行隨機(jī)序列不一樣 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(”關(guān)鍵字比較次數(shù)按從小到大排列分別是：rn“); KeyCompareNum_pailie(); printf(”rn“); printf(”移動(dòng)次數(shù)按從小到大排列分別是：rn“); MoveNum_pailie(); PrintInformation2(); system(”pause“); return 0; } void KeyCompareNum_pailie()//關(guān)鍵字比較次數(shù)排列 { int i,j,k,m; int printnum=0;//用于記錄上一次輸出的是數(shù)組KeyCompareNum的第幾個(gè)數(shù) int minimum;//用于輸出最小的數(shù)字 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在每次輸出是都是全新的，不能受之前數(shù)值的影響，因此每次輸出第一步先//把minimum設(shè)為最大值 for(j = 0;j < 5;j++) { if((minimum >=KeyCompareNum[j])&&(KeyCompareNum[j]!= 0)) { minimum = KeyCompareNum[j]; } } for(k = 0;k < 5;k++)//編程時(shí)k原先用的還是i,結(jié)果i=4這個(gè)情況,break以后到緊接//著的外層循環(huán)時(shí)，i的數(shù)值影響到了外層循環(huán)，跳了出來(lá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()//移動(dòng)次數(shù)排列 { int i, j, k, m; int printnum = 0;//用于記錄上一次輸出的是數(shù)組KeyCompareNum的第幾個(gè)數(shù) int minimum;//用于輸出最小的數(shù)字 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每次輸出是都是全新的，不能受之前數(shù)值的影響，//因此每次輸出第一步先把minimum設(shè)為最大值 for(j = 0;j < 5;j++) { if((minimum >= MoveNum[j])&&(MoveNum[j]!= 0)) { minimum = MoveNum[j]; } } for(k = 0;k < 5;k++)//編程時(shí)k原先用的還是i,結(jié)果i=4這個(gè)情況,break以后到緊接//著的外層循環(huán)時(shí)，i的數(shù)值影響到了外層循環(huán)，跳了出來(lá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(”實(shí)驗(yàn)名稱(chēng):實(shí)驗(yàn)四.內(nèi)部排序算法的實(shí)現(xiàn)與比較rn“); printf(”學(xué)號(hào):031650106rn“); printf(”姓名:郭硯璞rn“); printf(”====================rn“); printf(”程序運(yùn)行開(kāi)始,Current local time and date:“); PrintTime(); } void PrintInformation2() { printf(”rn====================rn“); printf(”程序運(yùn)行結(jié)束,Current local time and date:"); PrintTime(); }
點(diǎn)擊咨詢(xún) 