2020年數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)-實驗指導(dǎo)書

數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)-實驗指導(dǎo)書

數(shù)據(jù)結(jié)構(gòu)與算法課程實習(xí)

實驗指導(dǎo)書

資料僅供參考

目錄

實驗一順序表的基本操作錯誤!未定義書簽。

實驗二鏈表的基本操作.…錯誤!未定義書簽。

實驗三二叉樹的基本操作錯誤!未定義書簽。

實驗四綜合應(yīng)用.......錯誤!未定義書簽。

附錄A實驗報告示例....錯誤!未定義書簽。

附錄B實驗報告封面、評語得分表錯誤！未定

義書簽。

資料僅供參考

實驗一順序表的基本操作

【實驗?zāi)康摹?/p>

1、掌握順序存儲的概念,學(xué)會對順序表的基

本操作。

2、加深對順序存儲數(shù)據(jù)結(jié)構(gòu)的理解,逐步培

養(yǎng)解決實際問題的能力。

【實驗性質(zhì)】

設(shè)計型實驗

【實驗內(nèi)容】

1、實現(xiàn)順序表顯示；

2、實現(xiàn)順序表插入；

3、實現(xiàn)順序表查找（顯示比較次數(shù)）；

4、實現(xiàn)順序表刪除（顯示移動次數(shù)）；

5、實現(xiàn)順序表排序（分別實現(xiàn)簡單選擇、

快速，顯示比較次數(shù)、移動次數(shù)）；

6、實現(xiàn)順序表的折半查找（顯示比較次數(shù)）；

7、編程實現(xiàn)一個順序表的就地逆置，即利

用原表的存儲空間將順序表逆置；

資料僅供參考

8、順序表有序插入（顯示比較次數(shù)、移動

次數(shù)），

屏幕提示后，從鍵盤輸入一個元素值,

在經(jīng)過排序的線性表中插入這個元素；

屏幕顯示比較次數(shù)和移動次數(shù)，應(yīng)有

溢出判斷和報告；

9、要求以較高的效率實現(xiàn)刪除順序表中元

素值在x到y(tǒng)（x和y自定）之間的所有元素；

10、編程實現(xiàn)將兩個非遞減的順序表進(jìn)行合

并，要求同樣的數(shù)據(jù)元素只出現(xiàn)一次；

*11、編程實現(xiàn)順序表的shell排序（步長為

5,3,1）；

*12、編程實現(xiàn)堆排序算法；

*13、利用三元組順序表存儲矩陣，實現(xiàn)矩

陣的轉(zhuǎn)置（請獨立寫程序?qū)崿F(xiàn)）。

【實驗環(huán)境】

VC++6.0

【實驗要求】

將如上文件保存在命名為“學(xué)號+姓名”的文件夾中并上傳到指定的服務(wù)器。

資料僅供參考

實驗二鏈表的基本操作

【實驗?zāi)康摹?/p>

1、掌握鏈表的概念，學(xué)會對鏈表進(jìn)行操作。

2、加深對鏈?zhǔn)酱鎯Y(jié)構(gòu)的理解,逐步培養(yǎng)解

決實際問題的編程能力。

【實驗性質(zhì)】

設(shè)計型實驗

【實驗內(nèi)容】

1、實現(xiàn)單鏈表的創(chuàng)立；

2、實現(xiàn)單鏈表的顯示；

3、實現(xiàn)單鏈表的查找（顯示比較次數(shù)）；

4、實現(xiàn)單鏈表的插入；

5、實現(xiàn)單鏈表的刪除（顯示比較次數(shù)）；

6、對已創(chuàng)立的鏈表（數(shù)據(jù)不限）進(jìn)行直接

插入排序；

資料僅供參考

7、將鏈接存儲線性表逆置，即最后一個結(jié)

點變成第1個結(jié)點，原來倒數(shù)第2個結(jié)點變成第

2個結(jié)點，如此等等；

8、生成有序的兩個單鏈表A和B（鏈表的

數(shù)據(jù)和個數(shù)自定），其首結(jié)點指針分別為a和b,

要求將兩個單鏈表合并為一個有序的單鏈表C,

其首結(jié)點指針為c,而且合并后的單鏈表的數(shù)據(jù)

不重復(fù)；

9、將一個首結(jié)點指針為a的單鏈表A分解

成兩個單鏈表A和B,其首結(jié)點指針分別為a

和b,使得鏈表A中含有原鏈表A中序號為奇

數(shù)的元素，而鏈表B中含有原鏈表A中序號為

偶數(shù)的元素，且保持原來的相對順序；

10、請編程實現(xiàn)鏈棧的基本操作函數(shù)，并經(jīng)

過調(diào)用這些基本函數(shù)，實現(xiàn)十進(jìn)制和八進(jìn)制轉(zhuǎn)換

的功能。

【實驗環(huán)境】

VC++6.0

【實驗要求】

資料僅供參考

將如上文件保存在命名為“學(xué)號+姓名”的文件夾中并上傳到指定的服務(wù)器。

資料僅供參考

實驗三二叉樹的基本操作

【實驗?zāi)康摹?/p>

【實驗性質(zhì)】

設(shè)計型實驗

【實驗內(nèi)容】

1、實現(xiàn)二叉樹的創(chuàng)立；

2、用遞歸方法分別先序、中序、后序遍歷以

Tree為根指針的二叉樹；

3、編寫遞歸算法，計算二叉樹中葉子結(jié)點的

數(shù)目；

4、編寫遞歸算法，計算二叉樹的深度；

5、編寫遞歸算法,將二叉樹中所有結(jié)點的左、

右子樹相互交換；

6、使用數(shù)組elem中的隨機(jī)數(shù)序列（以0表

示結(jié)束，不包括0）,生成以Tree為根指針的二

叉排序樹；

7、在以Tree為根指針的二叉排序樹中查找

資料僅供參考

結(jié)點；

8、從以Tree為根指針的二叉排序樹中刪除

結(jié)點(適用各種位置的結(jié)點)；

9、用非遞歸算法，先序遍歷以Tree為根指

針的二叉樹；

提示：用數(shù)組BiTNode*stack[max]

構(gòu)成堆棧，利用這個堆棧實現(xiàn)功能。

10、用凹入表示法的表示以Tree為根指針的

二叉樹，例如：

//324

//123

//746

//690

//567

11、用廣義表表示以Tree為根指針的二叉樹,

例如

//(324(123(746,690),567))

12、對以Tree為根指針的二叉樹，從根結(jié)點

開始，逐層從左到右輸出各結(jié)點的數(shù)據(jù)。

提示：用數(shù)組BiTNode*queue[max]

構(gòu)成隊列，利用這個隊列實現(xiàn)功能

13、根據(jù)Huffman編碼原理，使用數(shù)組elem

資料僅供參考

中的隨機(jī)數(shù)序列（以0表示結(jié)束，不包括0）作

為結(jié)點的權(quán)重,生成赫夫曼樹，以及赫夫曼編碼,

計算平均帶權(quán)徑長度。

14、（1）隨機(jī)生成二叉樹。（2）生成并保

存先（后）序、中序輸出序列。（3）按照保存

的一對輸出序列恢復(fù)出二叉樹。（4）生成先（后）

序輸出序列。

【實驗環(huán)境】

VC++6.0

【實驗要求】

將如上文件保存在命名為“學(xué)號+姓名”的文件夾中并上傳到指定的服務(wù)器。

實驗四綜合應(yīng)用

一、運動會分?jǐn)?shù)統(tǒng)計

問題描述

參加運動會的n個學(xué)校編號為1~聯(lián)比賽分

成m個男子項目和w個女子項目，項目編號分

資料僅供參考

別為l~m和m+1-m+Wo由于各項目參加人數(shù)差

別較大，有些項目取前五名，得分順序為7,5,

3,2,1；還有些項目只取前三名，得分順序為

5,3,2O寫一個統(tǒng)計程序產(chǎn)生各種成績單和得

分報表。

基本要求

產(chǎn)生各學(xué)校的成績單，內(nèi)容包括各校所取得

的每項成績的項目號、名次（成績）、姓名和得

分；產(chǎn)生團(tuán)體總分報表，內(nèi)容包括校號、男子團(tuán)

體總分、女子團(tuán)體總分和團(tuán)體總分。

測試數(shù)據(jù)

對于n=4,m=3,w=2,編號為奇數(shù)的項目取前

五名，編號為偶數(shù)的項目取前三名，設(shè)計一組實

例數(shù)據(jù)。

實現(xiàn)提示

能夠假設(shè)n<=20,m<=30,w<=20,姓名長度

不超過20個字符。每個項目結(jié)束時，將其編號、

類型符（區(qū)分取前五名還是前三名）輸入，并按

名次順序輸入運動員姓名、校名（和成績）。

選作內(nèi)容

允許用戶指定某項目采取其它名次取法。

資料僅供參考

二、一元稀疏多項式簡單計算器

問題描述

設(shè)計一個一元稀疏多項式簡單計算器

基本要求

一元稀疏多項式簡單計算器的基本功能是：

(1)輸入并建立多項式；

(2)輸出多項式，輸出形式為整數(shù)序列：

n,Ci,ebC2,e2,.......,cn,en,其中n是多項式的項數(shù)，

G和齒分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)

降序排列；

(3)多項式a和b相加，建立多項式a+b；

(4)多項式a和b相減，建立多項式a.b。

測試數(shù)據(jù)

(1)(2x+5x3-3.1xn)

+(7-5X8+11X9)=(-3.1XU+11X9+2X+7)

(2)

(6X-3-X+4.4X2-1.2X9)-(-6X-3+5.4X2-X2+7.8X15)=(-

7.8X15-1.2X9+12X-3-X)

(3)

(l+X+X2+X3+X4+X5)+(-X3-X4)=(l+X+X2+X5)

(4)(X+X3)+(-X-X3)=0

資料僅供參考

實現(xiàn)提示

用帶表頭結(jié)點的單鏈表存儲多項式。

選作內(nèi)容

(1)計算多項式在X處的值。

(2)計算多項式a的導(dǎo)函數(shù)a，。

(3)多項式a和b相乘，建立乘積多項式

abo

(4)多項式的輸出形式為類數(shù)學(xué)表示式。例

如，多項式-3x8+6x3-18的輸出形式為

-3xA8+6xA3-18o注意，系數(shù)為1的非零

次項的輸出形式中略去系數(shù)1,如1x8的

輸出形式為“8。

(5)計算器的仿真界面。

三、停車場管理

問題描述

設(shè)停車場是一個可停放n輛汽車的狹長通

道，且只有一個大門可供汽車進(jìn)出。汽車在停車

場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南

排列(大門在最南端，最先到達(dá)的第一輛停放在

車場的最北端)，若車廠內(nèi)已停滿n輛汽車，則

資料僅供參考

后來的汽車只能在門外的便道上等候，一旦有車

開走，則排在便道上的第一輛車即可開入；當(dāng)停

車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必

須先退出車場為它讓路，待該輛車開出大門外，

其它車輛再按原次序進(jìn)入車場，每輛停放在車場

的車在它離開停車場時必須按它停留的時間長

短繳納費用。試為停車場編制按上述要求進(jìn)行管

理的模擬程序。

基本要求

以棧模擬停車場，以隊列模擬車場外的便

道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管

理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到

達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或

離去的時刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸

出信息為：若是車輛到達(dá)，則輸出汽車在停車場

內(nèi)或便道上的停車位置；若是車輛離去，則輸出

汽車在停車場內(nèi)停留的時間和應(yīng)繳納的費用(在

便道上停留的時間不收費)?！Ｒ皂樞蚪Y(jié)構(gòu)實

現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。

測試數(shù)據(jù)

設(shè)n=2,輸入數(shù)據(jù)為(A,l,5),(A,2,10),

(D,l,15),(A,3,20),(A,4,25),(A,5,30),

資料僅供參考

(D,2,35),(D,4,40),(E,0,0)。其中A表示到

達(dá)；D表示離去；E表示結(jié)束。

實現(xiàn)提示

需另設(shè)一個棧，臨時停放為給要離去的汽車

讓路而從停車場退出來的汽車，也用順序存儲結(jié)

構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。棧

中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽

車牌照號碼和進(jìn)入停車場的時刻。

選作內(nèi)容

(1)兩個棧共享空間,思考應(yīng)開辟數(shù)組的空

間是多少。

(2)汽車可有不同種類,則她們的占地面積

不同，收費標(biāo)準(zhǔn)也不同，如1輛客車和1.5

輛小汽車的占地面積相同，1輛十輪卡車

占地面積相當(dāng)于3輛小汽車的占地面積。

(3)汽車能夠直接從便道上開走,此時排在

它前面的汽車要先開走讓路，然后再依次

排到隊尾。

(4)停放在便道上的汽車也收費，收費標(biāo)準(zhǔn)

比停放在停車場的車低，請思考如何修改

結(jié)構(gòu)以滿足這種要求。

資料僅供參考

四、航空客運訂票系統(tǒng)

問題描述

航空客運訂票的業(yè)務(wù)活動包括：查詢航線、

客票預(yù)訂和辦理退票等。試設(shè)計一個航空客運訂

票系統(tǒng)，以使上述業(yè)務(wù)能夠借助計算機(jī)來完成。

基本要求

（1）每條航線所涉及的信息有：終點站名、

航班號、飛機(jī)型號、飛行周日（星期幾）、

乘員定額?、余票量、已定票的客戶名單

（包括姓名、訂票量、艙位等級1,2或

3）以及等候替補(bǔ)的客戶名單（包括姓名、

所需票量）；

（2）作為示意系統(tǒng)，全部數(shù)據(jù)能夠只放在內(nèi)

存中；

（3）系統(tǒng)能實現(xiàn)的操作和功能如下：

查詢航線：根據(jù)旅客提出的終點站名輸出下

列信息：航班號、飛機(jī)號、星期幾飛行，最

近一天航班的日期和余票額；

承辦定票業(yè)務(wù)：根據(jù)客戶提出的要求（航班

號、訂票數(shù)額）查詢該航班票額情況，若尚

資料僅供參考

有余票，則為客戶辦理訂票手續(xù)，輸出座位

號；若以滿員或余票額少于定票額，則需重

新詢問客戶要求。若需要,可登記排隊候補(bǔ);

承辦退票業(yè)務(wù):根據(jù)客戶提供的情況（日期、

航班），為客戶辦理退票手續(xù)，然后查詢該

航班是否有人排隊候補(bǔ)，首先詢問排在第一

的客戶，若所退票額能滿足她的要求，則為

她辦理訂票手續(xù)，否則依次詢問其它排隊候

補(bǔ)的客戶。

測試數(shù)據(jù)

自行指定。

實現(xiàn)提示

兩個客戶名單可分別由線性表和隊列實現(xiàn)。

為查找方便，已訂票客戶的線性表應(yīng)按客戶姓名

有序，而且，為插入和刪除方便，應(yīng)以鏈表作為

存儲結(jié)構(gòu)，由于預(yù)約人數(shù)無法預(yù)計，隊列也應(yīng)以

鏈表作為存儲結(jié)構(gòu)。整個系統(tǒng)需匯總各條航線的

情況登錄在一張線性表上，由于航線基本不變，

可采用順序存儲結(jié)構(gòu)，并按航班有序或按終點站

名有序。每條航線是這張表上的一個記錄，包含

上述8個域，其中乘員名單域為指向乘員名單鏈

表的頭指針，等候替補(bǔ)的客戶名單域為分別指向

資料僅供參考

隊頭和隊尾的指針。

選作內(nèi)容

當(dāng)客戶訂票要求不能滿足時，系統(tǒng)可向客戶

提供到達(dá)同一目的地的其它航線情況。還能夠充

分發(fā)揮自己的想象力，增加系統(tǒng)的功能和其它服

務(wù)項目。

五、簡單行編輯程序

問題描述

文本編輯程序是利用計算機(jī)進(jìn)行文字加工

的基本軟件工具，實現(xiàn)對文本文件的插入、刪除

等修改操作。限制這些操作以行為單位進(jìn)行的編

輯程序稱為行編輯程序。

被編輯的文本文件可能很大，全部讀入編輯

程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟(jì)，也不

總能實現(xiàn)。一種解決方法是逐段編輯。任何時刻

只能把待編輯的文件的一段放在內(nèi)存中，稱為活

區(qū)。試按照這種方法實現(xiàn)一個簡單的行編輯程

序。設(shè)文件每行不超過320個字符，很少超過

80個字符。

基本要求

資料僅供參考

實現(xiàn)以下4條基本編輯命令：

（1）行插入o格式:iv行號＞v回車＞v文本》.v

回車〉

將文本插入活區(qū)中第V行號〉行之后。

（2）行刪除。格式：dv行號1＞[＜空格＞v行

號2＞]v回車＞

刪除活區(qū)中第〈行號行（到第〈行號

2＞行）。例如“diO”和“diO14”

（3）活區(qū)切換。格式：nv回車〉

將活區(qū)寫入輸出文件，并從輸入文件中

讀入下一段，作為新的活區(qū)。

（4）活區(qū)顯示。格式：pv回車》

逐頁的（每頁20行）顯示活區(qū)內(nèi)容，

每顯示一頁之后請用戶決定是否繼續(xù)顯示

以后各頁（如果存在）。印出的每一行要前

置行號和一個空格符，行號固定占4位，增

量為1。

各條命令中的行號均須在活區(qū)中各行行

號范圍之內(nèi)，只有插入命令的行號能夠等于活

區(qū)第一行行號減一，表示插入當(dāng)前屏幕中第一

行之前，否則命令參數(shù)非法。

測試數(shù)據(jù)

資料僅供參考

自行設(shè)定，注意測試將活區(qū)刪空等特殊情

況。

實現(xiàn)提示

（1）設(shè)活區(qū)的大小用行數(shù)ActiveMaxLen

（可設(shè)為100）來描述?？紤]到文本文件

行長一般為正態(tài)分布,且峰值在60到70

之間，用320*ActiveMaxLen大小的字

符數(shù)組實現(xiàn)存儲將造成大量浪費，能夠

以標(biāo)準(zhǔn)行塊為單位為各行分配存儲，每

個標(biāo)準(zhǔn)行塊可含81個字符。這些行塊能

夠組成一個數(shù)組，也能夠利用動態(tài)鏈表

連接起來。一行文字可能占多個行塊。

行尾可用一個特殊的ASCII字符（如

（012）8）標(biāo)識。另外，還應(yīng)記住活區(qū)起始

行號。行插入將引起隨后各行行號的順

序下推。

（2）初始化函數(shù)包括:請用戶提供輸入文件

名（空串表示無輸入文件）和輸出文件

名，兩者不能相同。然后盡可能多地從

輸入文件中讀入各行，但不超過

ActiveMaxLen-xox的值能夠自定，例

如20o

資料僅供參考

（3）在執(zhí)行行插入命令的過程中，每接收到

一行時都要檢查活區(qū)大小是否已達(dá)

ActiveMaxLeno如果是，則為了在插入

這一行之后仍保持活區(qū)大小不超過

ActiveMaxLen,應(yīng)將插入點之前的活區(qū)

部分中第一行輸出到輸出文件中；若插

入點為第一行之前，則只得將新插入的

這一行輸出。

（4）若輸入文件尚未讀完，活區(qū)切換命令可

將原活區(qū)中最后幾行留在活區(qū)頂部，以

保持閱讀連續(xù)性；否則，它意味著結(jié)束

編輯或開始編輯另一個文件。

（5）可令前三條命令執(zhí)行后自動調(diào)用活區(qū)

顯示。

選作內(nèi)容

（1）對于命令格式非法等一切錯誤作嚴(yán)格

檢查和適當(dāng)處理。

（2）加入更復(fù)雜的編輯操作,如對某行進(jìn)行

串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式

能夠為Sv行號>@v串l>@v串2>v回車>

和mv串〉v回車

資料僅供參考

【實驗環(huán)境】

VC++6.0

【實驗要求】

將如上文件保存在命名為“學(xué)號+姓名”的文件夾中并上傳到指定的服務(wù)器。

資料僅供參考

附錄A實驗報告示例

“學(xué)生通訊錄管理系統(tǒng)”的設(shè)計與實現(xiàn)

一、設(shè)計要求

1、問題描述

紙質(zhì)的通訊錄已經(jīng)不能滿足大家的要

求，容易丟失，查找困難等問題是紙質(zhì)通訊

錄所不能克服的缺點?！皩W(xué)生通訊錄管理系

統(tǒng)”是為了幫助老師、同學(xué)，或者其它一些

需要使用通訊錄的人員進(jìn)行管理和分析的

一種應(yīng)用程序。

2、需求分析

(1)輸入數(shù)據(jù)建立通訊錄

(2)查詢通訊錄中滿足要求的信息

(3)插入新的通訊錄信息

(4)刪除不需要的通訊錄信息

(5)查看所有的通訊錄信息

二、概要設(shè)計

為了實現(xiàn)需求分析中的功能，能夠從3個方面

著手設(shè)計

1、主界面設(shè)計

為了實現(xiàn)學(xué)生通訊錄管理系統(tǒng)各功能的管

資料僅供參考

理，設(shè)計一個含有多個菜單項的主控菜單子

程序以鏈接系統(tǒng)的各項子功能，方便用戶使

用本系統(tǒng)。

2、存儲結(jié)構(gòu)設(shè)計

本系統(tǒng)主要采用鏈表結(jié)構(gòu)類型來表示存儲

在“學(xué)生通訊錄管理系統(tǒng)”中的信息。其中,

鏈表結(jié)點有4個分量構(gòu)成：通訊錄成員學(xué)

號、姓名、電話號碼、指向該結(jié)構(gòu)體的指針。

另外，本系統(tǒng)還設(shè)置一個全局變量seat,表

示成員序號。

3、系統(tǒng)功能設(shè)計

本系統(tǒng)設(shè)置5個子功能：

(1)建立通訊錄系統(tǒng)：能夠一次輸入多

個成員的信息，建立通訊錄。

(2)插入通訊錄記錄：每次能夠插入一

個成員的信息。

(3)查詢通訊錄記錄：能夠按兩種方式

查詢所要的記錄，一是按學(xué)號查詢，二

是按姓名查詢。

(4)刪除通訊錄記錄：能夠按三種方式

刪除信息，按序號刪除，按學(xué)號刪除，

按姓名刪除。

資料僅供參考

(5)顯示通訊錄記錄：能夠查看通訊錄

中所有成員信息。

三、模塊設(shè)計

1、模塊設(shè)計

本程序包含兩個模塊：主程序模塊和鏈表操

作程

毋xn----------＞必+啟

2、系統(tǒng)子程序及功能設(shè)計

本系統(tǒng)共設(shè)置10個子程序，各程序的函數(shù)

名及功能說明如下：

(1)LinkListCreateIncreLink()

〃鏈表的創(chuàng)立

(2)deleteElem(LinkListL,inti)//

從通訊錄中按序號刪除第i各元素

(3)delName(LinkListL,charn[])//

按姓名刪除通訊者紀(jì)錄

(4)delNum(LinkListL,intn)//

按學(xué)號刪除通訊者紀(jì)錄

(5)voidinsertYouXu(LinkListL,

LinkListElem)〃插入一條通訊錄

資料僅供參考

(6)printList(LinkListL)//

打印通訊錄

(7)prior(LinkListL,LinkLis