數(shù)據(jù)結(jié)構(gòu)-數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)指導(dǎo)書

遍草栗喟工大劈

得！於EASTCHINAUNIVERSITYOFSCIENCEANDTECHNOLOGY

《算法與數(shù)據(jù)結(jié)構(gòu)》

實(shí)驗(yàn)指導(dǎo)書

2

第一部分算法與數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)概述

實(shí)驗(yàn)?zāi)康?/p>

《算法與數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)專業(yè)的主干課程和必修課程之一，其目的

是讓大家學(xué)習(xí)、分析和研究數(shù)據(jù)對象特征，掌握數(shù)據(jù)組織方法和計(jì)算機(jī)的表

示方法，以便選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)相應(yīng)的運(yùn)算操作，

把現(xiàn)實(shí)世界中的問題轉(zhuǎn)化為計(jì)算機(jī)內(nèi)部的表示與處理的方法,要求掌握算法

的時(shí)間、空間復(fù)雜度分析基本技術(shù)，培養(yǎng)良好的程序設(shè)計(jì)風(fēng)格，掌握進(jìn)行復(fù)

雜程序設(shè)計(jì)的技能。在計(jì)算機(jī)科學(xué)領(lǐng)域，尤其是在系統(tǒng)軟件和應(yīng)用軟件的設(shè)

計(jì)和應(yīng)用中要用到各種數(shù)據(jù)結(jié)構(gòu)，因此，掌握數(shù)據(jù)結(jié)構(gòu)對提高軟件設(shè)計(jì)和程

序編制水平有很大的幫助。

二.實(shí)驗(yàn)要求

2.1實(shí)驗(yàn)步驟

設(shè)計(jì)步驟的規(guī)范不但可以培養(yǎng)學(xué)生科學(xué)的工作方法和作風(fēng)，而且還能有

效地減少錯(cuò)誤，提高工作效率。因此必須嚴(yán)格執(zhí)行良好的實(shí)驗(yàn)步驟規(guī)范（包

括上機(jī)操作規(guī)范）。本課程實(shí)驗(yàn)的基本步驟是：

2.1.1問題分析

充分地分析和理解問題本身，明確問題要求做什么。對問題的描述應(yīng)避

開算法和所涉及的數(shù)據(jù)類型，而是對所需完成的任務(wù)作出明確的回答。例如；

輸入、輸出數(shù)據(jù)的類型、值的范圍以及形式等。同時(shí)為調(diào)試程序準(zhǔn)備好測試

數(shù)據(jù)，包含合法的輸入數(shù)據(jù)和非法形式輸入的數(shù)據(jù)。

2.1.2設(shè)計(jì)和編碼

3

設(shè)計(jì)即是對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，定義主程

序模塊和各抽象數(shù)據(jù)類型；定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各過程和函數(shù)的偽碼

算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡

單和易于調(diào)試。

編碼即把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序，寫出源程

序。對程序中的疑問應(yīng)作出記號(hào)，以便上機(jī)時(shí)注意解決。每個(gè)明確的功能模

塊程序一般不超過60行，程序的每一行不得超過60個(gè)字符，否則要進(jìn)一步

劃分。

2.1.3上機(jī)前程序靜態(tài)檢查

上機(jī)前程序靜態(tài)檢查可有效提高調(diào)試效率，減少上機(jī)調(diào)試程序時(shí)的無謂

錯(cuò)誤。

靜態(tài)檢查主要有兩種途徑：用一組測試數(shù)據(jù)手工執(zhí)行程序；通過閱讀或

給別人講解自己的程序而深入全面地理解程序邏輯。把程序中的明顯錯(cuò)誤事

先排除。

2.1.4上機(jī)調(diào)試程序

上機(jī)實(shí)驗(yàn)時(shí)要帶上《C語言》教材、《數(shù)據(jù)結(jié)構(gòu)》教材、《數(shù)據(jù)結(jié)構(gòu)上機(jī)

實(shí)驗(yàn)指導(dǎo)書》，調(diào)試最好分模塊進(jìn)行，自底向下，即先調(diào)試低層過程或函數(shù)。

調(diào)試過程中應(yīng)多動(dòng)手確定疑點(diǎn)，通過修改程序來證明。

調(diào)試正確后，認(rèn)真整理源程序及其注釋，寫出或打印出帶有完整注釋的

且格式良好的源程序清單和結(jié)果。

2.1.5完成上機(jī)實(shí)驗(yàn)報(bào)告

2.2實(shí)驗(yàn)報(bào)告格式

4

得;睜EASTCHINAUNIVERSITYOFSCIENCEANDTECHNOLOGY

《算法與數(shù)據(jù)結(jié)構(gòu)》

實(shí)驗(yàn)報(bào)告本

班級(jí):___________________

學(xué)號(hào)：___________________

姓名:___________________

指導(dǎo)教師：___________________

5

2.3實(shí)驗(yàn)過程

需求分析

以無歧義的陳述說明程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)程序要做什么。明確規(guī)定：

(1).輸入的形式和輸入值的范圍；

(2)輸出的形式

(3)程序所能達(dá)到的功能

(4)測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果，含有錯(cuò)誤的輸入及其

輸出結(jié)果。

1.系統(tǒng)設(shè)計(jì)

1.說明本程序中用到的所有抽象數(shù)據(jù)類型的定義；

2.主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系，畫出函數(shù)的調(diào)用關(guān)

系圖。

3.列出各個(gè)功能模塊的主要功能及輸入輸出參數(shù)。

3.調(diào)試分析

內(nèi)容包括：

(1).調(diào)試過程中遇到的問題是如何解決的及對設(shè)計(jì)與實(shí)現(xiàn)的回顧討論與分

析。

(2)算法的時(shí)間復(fù)雜度分析(包括基本操作和其他算法)和改進(jìn)設(shè)想；

(3)經(jīng)驗(yàn)與體會(huì)等。

4.測試結(jié)果

列出你的測試結(jié)果，包括輸入與輸出，這里的測試數(shù)據(jù)應(yīng)完整和嚴(yán)格，可用

需求分析中的測試數(shù)據(jù)。

5、用戶手冊

說明如何使用你編寫的程序，詳細(xì)列出每一步操作步驟。

6、附錄

6

即帶注釋的源程序清單和結(jié)果。除原有注釋外再加一些必要的注釋和斷

言（關(guān)鍵語句或函數(shù)功能的注釋）。對填空和改錯(cuò)題還要寫出正確答案，如

果題目規(guī)定了測試數(shù)據(jù)，則結(jié)果要包含這些測試數(shù)據(jù)和運(yùn)行輸出，當(dāng)然還可

以含其它測試數(shù)據(jù)及其運(yùn)行輸出。

2.4考核及評分辦法

上機(jī)實(shí)驗(yàn)成績根據(jù)上機(jī)考勤、調(diào)試情況、實(shí)驗(yàn)報(bào)告評分，分為五級(jí)制：

優(yōu)、良、中、及格、不及格。

7

第二部分上機(jī)實(shí)驗(yàn)內(nèi)容

序

實(shí)驗(yàn)實(shí)驗(yàn)每組課程

號(hào)

實(shí)驗(yàn)名稱主要內(nèi)容目標(biāo)

類型時(shí)數(shù)人數(shù)

C/C++語言的循環(huán)、條件

數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)基礎(chǔ)實(shí)

1控制語句，數(shù)組、鏈表A211

驗(yàn)

等數(shù)據(jù)存儲(chǔ)

熟練掌握順序和鏈?zhǔn)骄€性

2線性表實(shí)驗(yàn)B21

表的基本操作1,2

熟練掌握堆棧和隊(duì)列的

基本操作，棧在表達(dá)式

3棧和隊(duì)列實(shí)驗(yàn)B211,2

求解中的應(yīng)用，雙端隊(duì)

列的應(yīng)用

熟練掌握二叉樹的存儲(chǔ)

結(jié)構(gòu)，二叉樹的先序、

4樹的應(yīng)用實(shí)驗(yàn)B411,2

中序遍歷，二叉搜索樹、

哈夫曼編碼

熟練掌握圖的存儲(chǔ)結(jié)構(gòu)、連

通性、廣度優(yōu)先和深度優(yōu)先

5圖的應(yīng)用實(shí)驗(yàn)搜索、Dijkstra單原點(diǎn)最短B411,2

路徑、拓?fù)渑判?、Floyd算

法

熟練掌握選擇、插入、

6排序算法B211,2

交換、歸并算法的應(yīng)用

8

實(shí)驗(yàn)一數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)基礎(chǔ)

一、實(shí)驗(yàn)?zāi)康?/p>

1.了解數(shù)據(jù)結(jié)構(gòu)的語法基礎(chǔ)。

二、實(shí)驗(yàn)內(nèi)容

1.數(shù)組元素循環(huán)左移問題2-2；

2.整數(shù)分解問題2-3；

3.數(shù)列求和問題2-6.

9

實(shí)驗(yàn)二線性表

一、實(shí)驗(yàn)?zāi)康?/p>

1.了解線性表的特性，以便靈活應(yīng)用。

2.熟練掌握線性表的各種操作和應(yīng)用

二、實(shí)驗(yàn)內(nèi)容

10

實(shí)驗(yàn)三棧和隊(duì)列

一、實(shí)驗(yàn)?zāi)康?/p>

1.掌握棧和隊(duì)列的概念及存儲(chǔ)方法。

2.掌握順序棧、鏈?zhǔn)綏！⒀h(huán)隊(duì)列的算法。

3.熟練掌握編寫實(shí)現(xiàn)棧和隊(duì)列的各種運(yùn)算的算法。

二、實(shí)驗(yàn)內(nèi)容

11

實(shí)驗(yàn)四樹和二叉樹

一、實(shí)驗(yàn)?zāi)康?/p>

1.掌握二叉樹，二叉樹排序數(shù)的概念及存儲(chǔ)方法。

2.掌握二叉樹的遍歷算法。

3.熟練掌握編寫實(shí)現(xiàn)樹的各種運(yùn)算的算法。

二、實(shí)驗(yàn)內(nèi)容

12

實(shí)驗(yàn)五圖

一、實(shí)驗(yàn)?zāi)康?/p>

1.熟悉圖的各種存儲(chǔ)方法。

2.掌握遍歷圖的遞歸和非遞歸的算法。

3.理解圖的有關(guān)算法。

二、實(shí)驗(yàn)內(nèi)容

1、任務(wù)調(diào)度的合理性

假定一個(gè)工程項(xiàng)目由一組子任務(wù)構(gòu)成，子任務(wù)之間有的可以并行執(zhí)行，

有的必須在完成了其它一些子任務(wù)后才能執(zhí)行?！叭蝿?wù)調(diào)度”包括一組子任

務(wù)、以及每個(gè)子任務(wù)可以執(zhí)行所依賴的子任務(wù)集。例如完成一個(gè)專業(yè)的所

有課程學(xué)習(xí)和畢業(yè)設(shè)計(jì)可以看成一個(gè)本科生要完成的一項(xiàng)工程，各門課程可

以看成是子任務(wù)。有些課程可以同時(shí)開設(shè)，比如英語和C程序設(shè)計(jì)，它們

沒有必須先修哪門的約束；有些課程則不可以同時(shí)開設(shè)，因?yàn)樗鼈冇邢群蟮?/p>

依賴關(guān)系，比如C程序設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)兩門課，必須先學(xué)習(xí)前者。

但是需要注意的是，對一組子任務(wù)，并不是任意的任務(wù)調(diào)度都是一個(gè)可

行的方案。比如方案中存在“子任務(wù)A依賴于子任務(wù)B,子任務(wù)B依賴于子

任務(wù)C,子任務(wù)C又依賴于子任務(wù)A"，那么這三個(gè)任務(wù)哪個(gè)都不能先執(zhí)行,

這就是一個(gè)不可行的方案。你現(xiàn)在的工作是寫程序判定任何一個(gè)給定的任務(wù)

調(diào)度是否可行。

輸入說明：輸入第一行給出子任務(wù)數(shù)N（S100）,子任務(wù)按1~N編號(hào)。隨后

N行，每行給出一個(gè)子任務(wù)的依賴集合：首先給出依賴集合中的子任務(wù)數(shù)K,

隨后給出K個(gè)子任務(wù)編號(hào)，整數(shù)之間都用空格分隔。

輸出說明：如果方案可行，則輸出1,否則輸出0。

測試樣例：輸入

11

11

223

輸出：1

13

2、社交網(wǎng)絡(luò)圖中結(jié)點(diǎn)的“重要性”計(jì)算

在社交網(wǎng)絡(luò)中，個(gè)人或單位(結(jié)點(diǎn))之間通過某些關(guān)系(邊)聯(lián)系起來。

他們受到這些關(guān)系的影響，這種影響可以理解為網(wǎng)絡(luò)中相互連接的結(jié)點(diǎn)之間

戛延的一種相互作用，可以增強(qiáng)也可以減弱。而結(jié)點(diǎn)根據(jù)其所處的位置不同，

其在網(wǎng)絡(luò)中體現(xiàn)的重要性也不盡相同。

“緊密度中心性”是用來衡量一個(gè)結(jié)點(diǎn)到達(dá)其它結(jié)點(diǎn)的“快慢”的指標(biāo)，即

一個(gè)有較高中心性的結(jié)點(diǎn)比有較低中心性的結(jié)點(diǎn)能夠更快地(平均意義下)

到達(dá)網(wǎng)絡(luò)中的其它結(jié)點(diǎn)，因而在該網(wǎng)絡(luò)的傳播過程中有更重要的價(jià)值。在有

N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中，結(jié)點(diǎn)vi的“緊密度中心性”Cc(vi)數(shù)學(xué)上定義為vi到其余

所有結(jié)點(diǎn)vj。為)的最短距離d(vi,vj)的平均值的倒數(shù)：

N

N-l

Cc（v,）=T—rErf（v.>vP

~~N

IV—1

"J

對于非連通圖，所有結(jié)點(diǎn)的緊密度中心性都是0。

給定一個(gè)無權(quán)的無向圖以及其中的一組結(jié)點(diǎn)，計(jì)算這組結(jié)點(diǎn)中每個(gè)結(jié)點(diǎn)

的緊密度中心性。

輸入格式：輸入第一行給出兩個(gè)正整數(shù)N和M,其中N(<104)是圖

中結(jié)點(diǎn)個(gè)數(shù)，順便假設(shè)結(jié)點(diǎn)從1到N編號(hào)；M(<105)是邊的條數(shù)。隨后

的M行中，每行給出一條邊的信息，即該邊連接的兩個(gè)結(jié)點(diǎn)編號(hào)，中間用

空格分隔。最后一行給出需要計(jì)算緊密度中心性的這組結(jié)點(diǎn)的個(gè)數(shù)K(ROO)

以及K個(gè)結(jié)點(diǎn)編號(hào)，用空格分隔。

輸出格式：按照Cc(i)=x.xx的格式輸出K個(gè)給定結(jié)點(diǎn)的緊密度中心性,

每個(gè)輸出占一行，結(jié)果保留到小數(shù)