2016年數(shù)據(jù)結(jié)構(gòu)實驗報告格式

《數(shù)據(jù)結(jié)構(gòu)課程實驗》大綱

一、《數(shù)據(jù)結(jié)構(gòu)課程實驗》的地位與作用

“數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，是計算機(jī)專業(yè)的一門核心的關(guān)鍵性課程。本

課程較系統(tǒng)地介紹了軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)和實現(xiàn)算法，介紹了常用的多種查找和

排序技術(shù)，并做了性能分析和比較，內(nèi)容非常豐富。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計水平的

提高打下良好的基礎(chǔ)。

由于以下原因，使得掌握這門課程具有較大的難度：

(1)內(nèi)容豐富，學(xué)習(xí)量大，給學(xué)習(xí)帶來困難；

(2)貫穿全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點也是難點；

(3)所用到的技術(shù)多，而在此之前的各門課程中所介紹的專業(yè)性知識又不多，因而加大了學(xué)習(xí)難度：

(4)隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點和難點。

根據(jù)《數(shù)據(jù)結(jié)構(gòu)課程》課程本身的技術(shù)特性，設(shè)置《數(shù)據(jù)結(jié)構(gòu)課程實驗》實踐環(huán)節(jié)卜分重要。逋過實

驗實踐內(nèi)容的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征，目的是提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力。實驗學(xué)

時為18。

二、《數(shù)據(jù)結(jié)構(gòu)課程實驗》的目的和要求

不少學(xué)生在解答習(xí)題尤其是算法設(shè)計題時，覺得無從下手，做起來特別費勁。實驗中的內(nèi)容和教科書的

內(nèi)容是密切相關(guān)的，解決題目要求所需的各種技術(shù)大多可從教科書中找到，只不過其出現(xiàn)的形式呈多樣化，

因此需要仔細(xì)體會，在反復(fù)實踐的過程中才能掌握。

為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計所需的技術(shù)，為整個專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運

用所學(xué)知識，上機(jī)解決一些典型問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢

固掌握所用到的一些技術(shù)。數(shù)據(jù)結(jié)構(gòu)中梢微復(fù)雜一些的算法設(shè)計中可能同時要用到多種技術(shù)和方法，如算法

設(shè)計的構(gòu)思方法，動態(tài)鏈表，算法的編碼，遞歸技術(shù)，與特定問題相關(guān)的技術(shù)等，要求重點掌握線性鏈表、

二叉樹和樹、圖結(jié)構(gòu)、數(shù)組結(jié)構(gòu)相關(guān)算法的設(shè)計。在掌握基本算法的基礎(chǔ)上，掌握分析、解決實際問題的能

力。

三、《數(shù)據(jù)結(jié)構(gòu)課程實驗》內(nèi)容

課程實驗共18學(xué)時，要求完成以下六個題目：

實習(xí)一約瑟夫環(huán)問題(2學(xué)時)

用循環(huán)鏈表實現(xiàn)約瑟夫環(huán)問題，熟悉鏈表結(jié)構(gòu)的使用。

實習(xí)二停車場管理（4學(xué)時）

利用棧和隊列模擬停車場管理，學(xué)習(xí)利用棧和隊列解決實際問題。

實習(xí)三二叉樹基本操作（3學(xué)時）

創(chuàng)建、遍歷、插入、刪除、顯示二叉樹，通過二叉樹的基本操作，

掌握樹結(jié)構(gòu)的處理方法。

實習(xí)四圖的基本操作（3學(xué)時）

分別用鄰接矩陣和鄰接表實現(xiàn)以卜.操作：

圖的創(chuàng)建、遍歷、插入、刪除、最短路徑。

熟悉圖的常用存儲結(jié)構(gòu)和基本操作。

實習(xí)五哈希表設(shè)計（3學(xué)時）

給定30個人的姓名，用除留余數(shù)法構(gòu)造哈希函數(shù)，用線性探測再散列法處理

沖突，構(gòu)造哈希表，掌握哈希表的設(shè)計與使用。

實習(xí)六常用排序算法的對比分析（3學(xué)時）

分別實現(xiàn)直接插入排序、冒泡排序、簡單選擇排序、希爾排序、快速排序、

堆排序，并隨機(jī)生成30個數(shù)，比較各算法的時、空性能和穩(wěn)定性。

掌握常用排序算法的特點，以便根據(jù)實際情況選擇使用。

四、《數(shù)據(jù)結(jié)構(gòu)課程實驗》考核方式

采用上機(jī)情況、程序質(zhì)量、實習(xí)報告相結(jié)合的形式，滿分為100分。

1.上機(jī)情況（30%）

包括出勤情況、調(diào)試表現(xiàn)、是否上網(wǎng)、玩游戲。

2.程序質(zhì)量（50%）

3.實習(xí)報告（20%）

實習(xí)一線性表

本次實習(xí)的主要目的在于熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)卜一的實現(xiàn)，其中以熟悉各種鏈表的操作

為側(cè)重點。通過本次實習(xí)還可幫助讀者復(fù)習(xí)高級語言的使用方法。

約瑟夫環(huán)

［問題描述］

約瑟夫（Joeph）問題的?種描述是：編號為1,2,…,n的n個人按順時針方向圍坐一圈，每人持有個

密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始按順時針方向自1開始順序報

數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下個人開始重

新從1報數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計一個程序求出出列順序。

［基本要求］

利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序卬出各人的編號。

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

m的初值為20；密碼：3,1,7,2,4,8,4（正確的結(jié)果應(yīng)為6,1,4,7,2,3,5）。

［實現(xiàn)提示］

程序運行后首先要求用戶指定初始報數(shù)上限值，然后讀取各人的密碼。設(shè)nW30。

［選作內(nèi)容］

向上述程序中添加在順序結(jié)構(gòu)上實現(xiàn)的部分。

長整數(shù)運算

［問題描述］

設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算。

［基本要求］

利用雙項循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整型變量。任何整型變量的范圍是-(215-1)~

(215-1)o輸入和輸出形式：按中國對于長整數(shù)的表示習(xí)慣，每四位?組，組間用逗號隔開。

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

(1)0；0；應(yīng)輸出“0”。

(2)-2345,6789；-7654,3211；應(yīng)輸出“-1,0000,0000”。

(3)-9999,9999；1,0000,0000,0000；應(yīng)輸出“9999,0000,0001”。

(4)1,0001,000；-1,0001,0001；應(yīng)輸出“0"。

(5)1,0001,0001；-1,0001,0000；應(yīng)輸出。

［實現(xiàn)提示］

(1)每個結(jié)點中可以存放的最大整數(shù)為215-1=32767,才能保證兩數(shù)相加不會溢出。但若這樣存，即

相當(dāng)于按32768進(jìn)制數(shù)存，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點中僅存十

進(jìn)制數(shù)的4位，即不超過9999的非負(fù)整數(shù)，整個鏈表視為萬進(jìn)制數(shù)。

(2)可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不

要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的?種方法。不能給長整數(shù)位數(shù)

規(guī)定上限。

［選作內(nèi)容］

修改上述程序，使它在整型量范圍是-(2n-l)'(2nT)的計算機(jī)上都能有效地運行。其中，n是由程

序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。

實習(xí)二棧、隊列與遞歸算法設(shè)計

僅僅認(rèn)識到棧和隊列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實習(xí)的目的在于使讀者深入了解棧和隊列

的特征，以便在實際問題背景下靈活運用它們；同時還將鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞

歸算法設(shè)計。

停車場管理

［問題描述］

設(shè)停車場內(nèi)只有?個的停放n輛汽車的狹長通道，且只有?個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車

輛到達(dá)時間的先后順序，依次由北向南排列(大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端)，

若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，?旦有車開走，則排在便道上的第一輛

車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大

門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納

費用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。

［測試數(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)。其中，

'A'表示到達(dá)；'D，表示離去，'E'表示輸入結(jié)束。

［基本要求］

以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸

入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入

數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上.的停車位置；若是車離去；

則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用(在便道上停留的時間不收費)。棧以順序結(jié)構(gòu)實現(xiàn)，隊

列以鏈表實現(xiàn)。

［實現(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)以滿足這種

要求。

實習(xí)三串及其應(yīng)用

本次實習(xí)的目的是熟悉串類型的實現(xiàn)方法和文本模式匹配方法，熟悉?般文字處理軟件的設(shè)計方法，較

復(fù)雜問題的分解求精方法，在第二次實習(xí)的基礎(chǔ)上，進(jìn)一步強(qiáng)化這樣一個觀念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在

其上的操作，此外還希望起到訓(xùn)練合作能力和熟悉文件操作的目的。本次實習(xí)的難度較大。

文學(xué)研究助手

［問題描述］

文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)

計系統(tǒng)，稱為“文學(xué)研究助手”。

［基本要求］

英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行

之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計。

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

以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計的詞匯集。

［實現(xiàn)提示］

設(shè)小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計每個詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行

的行號可以用鏈表存儲。若某行中出現(xiàn)了不止一次，不必存多個相同的行號。

如果讀者希望達(dá)到選作部分(1)和(2)所提出的要求，則首先應(yīng)把KMP算法改寫成如卜.的等價形式，再將

它推廣到多個模式的情形。

［選作內(nèi)容］

(1)模式匹配要基于KMP算法。

(2)整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。

(3)假設(shè)小說中的每個單詞或者從行首開始，或者前置以一個空格符。利用單詞匹配特點另寫一個高

效的統(tǒng)計程序，與KMP算法統(tǒng)計程序進(jìn)行效率比較。

(4)推廣到更一般的模式集匹配問題，并設(shè)待杳模式串可以跨行(提示：定義操作getachar)

簡單行編輯程序

［問題描述］

文本編輯程序是利用計算機(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)行插入。格式：i〈行號X回車〉〈文本X回車》

將〈文本》插入活區(qū)中第〈行號》行之后

(2)行刪除。格式:d〈行號1＞［□＜行號2＞"回車》

刪除活區(qū)中第〈行號1＞行(到第〈行號2＞行)。兩種格式的例子是：“diO/”和“即0口14/”

(3)活區(qū)切換。格式：n〈回車〉

將活區(qū)寫入輸出文件，并從輸入文件中讀入下?段，作為新的活區(qū)。

(4)活區(qū)顯示。格式：p＜回車)

逐頁地(每頁20行)顯示活區(qū)內(nèi)容，每顯示頁之后請用戶決定是否繼續(xù)顯示以后各頁(如果

存在)。印出的每一?行要前置以行號和一個空格符，行號固定占4位，增量為1。

各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第?行行

號減1,表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。

［實現(xiàn)提示］

(1)設(shè)活區(qū)的大小用行數(shù)activemaxlen(可設(shè)為100)來描述。考慮到文本文件行長通常為正態(tài)分布,

且峰值在60到70之間，用320Xactivemaxlen大小的字符數(shù)組實現(xiàn)存儲將造成大量浪費。可以以標(biāo)準(zhǔn)行塊

為單位為各行分配存儲，每個標(biāo)準(zhǔn)行塊含81個字符。這些行塊可以組成一個數(shù)組，也可以利用動態(tài)鏈表連

接起來。一行文字可能占多個行塊。行尾可用一個特殊的ASCII字符(如(012)8)標(biāo)識。此外，還應(yīng)記住活

區(qū)起始行號。行插入將引起隨后各行行號的順序下推。

(2)初始化過程包括：請用戶提供輸入文件名(空串表示無輸入文件)和輸出文件名，兩者不能相同。

然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlen-x。x的值可以自定，例如20。

(3)在執(zhí)行行插入命令的過程中，每接收到一行時到要檢杳活區(qū)大小是否已達(dá)activemaxlen。如果

是，則為了在插入這一行之后仍保持活區(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)行模式匹配等，格式可以為S〈行號〉叱

串1＞@〈串2〉〈回車〉和m〈串〉〈回車〉。

實習(xí)四樹、圖及其應(yīng)用

樹和圖是兩種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點。它們的特點在于非線性。廣義表本質(zhì)上

是樹結(jié)構(gòu)；稀疏矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu)，故也把它們歸在這次實習(xí)中。本章實習(xí)繼

續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計觀點，但根據(jù)這兩種結(jié)構(gòu)的非線性特點，將操作進(jìn)一步集中在遍歷操作

上，因為遍歷操作是其他眾多操作的基礎(chǔ)。遍歷邏輯的（或符號形式的）結(jié)構(gòu)，訪問動作可是任何操作。本

次實習(xí)還希望達(dá)到熟悉各種存儲結(jié)構(gòu)的特征，以及如何應(yīng)用樹和圖結(jié)構(gòu)解決具體問題（即原理與應(yīng)用的結(jié)合）

等目的。

圖遍歷的演示

［問題描述］

很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個程序，演示連通的無向圖上行邊全部

結(jié)點的操作。

［基本要求］

以鄰接多重表為存儲結(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點為起點，分

別輸出每種遍歷下的結(jié)點訪問序列和相應(yīng)生成樹的邊集。

［實現(xiàn)提示］

設(shè)圖的結(jié)點不超過30個，每個結(jié)點用一個編號表示（如果一個圖有n個結(jié)點，則它們的編號分別為

1,2,-,n）.通過輸入圖的全部邊輸入一個圖，每個邊為一個數(shù)對，可以對邊的輸入順序作出某種限制。注

意，生成樹的邊是有向邊，端點順序不能顛倒。

［選作內(nèi)容］

（1）借助于棧類型（自己定義和實現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實現(xiàn)。

（2）以鄰接表為存儲結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹。

實習(xí)五查找和排序

本次實習(xí)旨在集中對幾個專門的問題作較為深入的探討和理解，也不強(qiáng)調(diào)對某些特定的編程技術(shù)的訓(xùn)練。

哈希表設(shè)計

［問題描述］

針對某個集體中人名設(shè)計?個哈希表，使得平均查找長度不超過R,并完成相應(yīng)的建表和查表程序。

［基本要求〕

假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。

哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。

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

取讀者周圍較熟悉的30個人名。

［選作內(nèi)容］

（1）從教科書上介紹的集中哈希函數(shù)構(gòu)造方法中選出適用者并設(shè)計幾個不同的哈希函數(shù)，比較他們的

地址沖突率（可以用更大的名字集合作實驗）。

（2）研究這30個人名的特點，努力找一個哈希函數(shù)，使得對于不同的拼音名一定不發(fā)生地址沖突。

(3)在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考察平均查找長度的變化和造好的哈希

表中關(guān)鍵字的聚集性。

內(nèi)部排序算法比較

［問題描述］

各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機(jī)的

數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。

［基本要求］

(1)對以下10種常用的內(nèi)部排序算法進(jìn)行比較：直接插入排序；折半折入排序；二路插入排序；希

爾排序；起泡排序：快速排序；簡單選擇排序；堆排序；歸并排序：基數(shù)排序。

(2)待排序表的表長不少于100：其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入

數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字移動次數(shù)(關(guān)鍵字交換計為3次移動)。

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

由隨機(jī)產(chǎn)生器決定。

［實現(xiàn)提示］

主要工作是設(shè)法在程序中適當(dāng)?shù)牡胤讲迦胗嫈?shù)操作。程序還可以包括計算兒組數(shù)據(jù)得出結(jié)果波動大小的

解釋。注意分塊調(diào)試的方法。

［選作內(nèi)容］

對■不同的輸入表長做試驗，觀察檢查兩個指標(biāo)相關(guān)于表長的變化關(guān)系。還可以對穩(wěn)定性做驗證。

實驗指導(dǎo)書概述

“數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，是一門關(guān)鍵性核心課程。本課程系統(tǒng)地介紹

了軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)和實現(xiàn)算法，介紹了多種常用的查找和排序技術(shù)，并對其

進(jìn)行了性能分析和比較，內(nèi)容非常豐富。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計水平的提高打卜良

好的基礎(chǔ)。

由于以下原因，使得掌握這門課程具有較大難度：

?內(nèi)容多，時間短，給學(xué)習(xí)帶來困難；

?貫穿全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點和難點；

?隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點和難點；

?先修課程中所介紹的專業(yè)性知識不多，加大了學(xué)習(xí)難度。

由了數(shù)據(jù)結(jié)構(gòu)課程的技術(shù)性與實踐性，《數(shù)據(jù)結(jié)構(gòu)課程實驗》的設(shè)置十分必要。為了幫助學(xué)生更好地

學(xué)習(xí)本課程，理解和掌握算法設(shè)計所需的技術(shù)，為整個專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運用所學(xué)知識，上機(jī)解決一

些典型問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用到的一些技術(shù)。

數(shù)據(jù)結(jié)構(gòu)中稍微復(fù)雜一些的算法設(shè)計中可能同時要用到多種技術(shù)和方法，如算法設(shè)計的構(gòu)思方法，動態(tài)鏈表,

算法的編碼，遞歸技術(shù)，與特定問題相關(guān)的技術(shù)等，要求重點掌握線性鏈表、二叉樹和樹、圖結(jié)構(gòu)、數(shù)組結(jié)

構(gòu)相關(guān)算法的設(shè)計。在掌握基本算法的基礎(chǔ)匕掌握分析、解決實際問題的能力。通過實驗實踐內(nèi)容的訓(xùn)練,

突出構(gòu)造性思維訓(xùn)練的特征，提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力。

上機(jī)實習(xí)是對學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個教學(xué)

環(huán)節(jié)。較大的實習(xí)題比平時的習(xí)題要復(fù)雜得多，也更接近實際。實習(xí)著眼于原理與應(yīng)用的結(jié)合點，使學(xué)生學(xué)

會如何把書上學(xué)到的知識用于解決實際問題，培養(yǎng)軟件工作所需要的動手能力。實習(xí)還能使書上的知識變

“活”，達(dá)到深化理解和靈活掌握教學(xué)內(nèi)容的目的。平時的練習(xí)較偏重于如何編寫功能單一的“小”算法，

而實習(xí)題是軟件設(shè)計的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計，用戶界面設(shè)計，程序設(shè)計基本技能和技巧,

多人合作，以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，還有很重要的一點是：機(jī)器是比任何

教師都嚴(yán)格的檢杳者。

為了達(dá)到上述目的，本書安排了6個主實習(xí)單元，其中實習(xí)0的訓(xùn)練重點是抽象數(shù)據(jù)類型的定義與實

現(xiàn)方法，其它各單元的訓(xùn)練重點在于基本的數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法。各實習(xí)單元與教科書的各章只具有粗略的

對應(yīng)關(guān)系，一個實習(xí)題可能涉及幾部分教學(xué)內(nèi)容。在每個實習(xí)單元中安排有難度不等的2—5個實習(xí)題，每

人可以從中選做一個實習(xí)題。建議選做難度略高于自己所做過的最難題目的難度，切忌過分追求難題。較大

的題目適合于多人合作。

每個實習(xí)題采取了統(tǒng)一的格式，由問題描述、基本要求、測試數(shù)據(jù)、實現(xiàn)提示和選做內(nèi)容等5個部分

組成。

問題描述旨在為讀者建立問題提出的背景環(huán)境，指明問題“是什么”：

基本要求則對問題進(jìn)一步求精，劃出問題的邊界，指出具體的參量或前提條件，并規(guī)定該題的最低限

度要求；

測試數(shù)據(jù)部分旨在為檢查學(xué)生上機(jī)作業(yè)提供方便，在完成實習(xí)題時應(yīng)自己設(shè)計完整和嚴(yán)格的測試方

案，當(dāng)數(shù)據(jù)輸入量較大時，提倡以文件形式向程序提供輸入數(shù)據(jù)；

實現(xiàn)提示對實現(xiàn)中的難點及其解法思路等問題作了簡要提示，個別問題給出了參考實現(xiàn)；

選做內(nèi)容向那些尚有余力的讀者提出了更嚴(yán)峻的挑戰(zhàn)，同時也能開拓其他讀者的思路，在完成基本要

求時就力求避免就事論事的不良思想方法，盡可能尋求具有普遍意義的解法，使得程序結(jié)構(gòu)合理，容易修改

擴(kuò)充。

書中題目設(shè)計得比較詳細(xì)，給出了問題說明和問題分解求精的范例，使讀者在無形中學(xué)會模仿，它起

到把讀者的思路引上正軌的作用，避免不良結(jié)構(gòu)程序和壞習(xí)慣，同時也傳授了系統(tǒng)劃分方法和程序設(shè)計的一

些具體技術(shù)，保證實現(xiàn)預(yù)定的訓(xùn)練意圖，使某些難點和重點不會被繞過去，而且也便于教學(xué)檢查。題目設(shè)計

策略是：一方面使其難度和工作量都較大，另一方面給讀者提供的輔助和可以模仿的部分也較多。當(dāng)然還應(yīng)

指出的是，提示的實現(xiàn)方法未必是最好的，讀者不應(yīng)拘泥于此，而應(yīng)爭取找出更好的方法和結(jié)構(gòu)。

在實現(xiàn)的時候應(yīng)注意，要盡量減少依賴于具體機(jī)器計算環(huán)境的用法，若使用，也應(yīng)在注釋中指出。這樣得出

的程序易于在不同機(jī)器上運行，有好的可移植性。C語言是結(jié)構(gòu)化程序設(shè)計語言，具有遞歸能力，可移植性

也較好，是特別推薦的實現(xiàn)語言。

本書的一個特點是為實習(xí)制定了嚴(yán)格的規(guī)范。一種普遍存在的錯誤觀念是，調(diào)試程序全憑運氣。學(xué)生

花2個小時的機(jī)匕時間只找出一個錯誤，甚至一無所獲的情況是常見的。其原因在于，很多人只認(rèn)識到找錯

誤，而沒有認(rèn)識到努力預(yù)先避免錯誤的重要性，也不知道應(yīng)該如何努力。實際上，結(jié)構(gòu)不好、思路和概念不

清的程序可能是根本無法調(diào)試正確的。嚴(yán)格按照實習(xí)步驟規(guī)范進(jìn)行實習(xí)，不但能有效地避免上述種種問題，

更重要的是有利于培養(yǎng)軟件工作者不可缺少的科學(xué)工作方法和作風(fēng)。

在附錄中提供了一個完整的實習(xí)報告示例，在起到實習(xí)報告規(guī)格范例作用的同時I還隱含地提供了很

多有益的東西，比如基于數(shù)據(jù)類型的系統(tǒng)劃分方法以及所提倡的程序設(shè)計風(fēng)格等等。計算機(jī)學(xué)科在不斷發(fā)展,

可以使用的語言工具越來越豐富，在本書中的實習(xí)示例是應(yīng)用面向過程的語言進(jìn)行設(shè)計和編程，同樣的實習(xí)

題，也可以用面向?qū)ο蟮恼Z言來實現(xiàn)。希望書中的實習(xí)報告示例能起到一個拋磚引玉的作用，以引來讀者更

多更優(yōu)良的設(shè)計范例。

實習(xí)步驟

隨著計算機(jī)性能的提高，它所面臨的軟件開發(fā)的復(fù)雜度也日趨增加，因此軟件開發(fā)需要系統(tǒng)的方法。一

種常用的軟件開發(fā)方法，是將軟件開發(fā)過程分為分析、設(shè)計、實現(xiàn)和維護(hù)四個階段。雖然數(shù)據(jù)結(jié)構(gòu)課程中的

實習(xí)題的復(fù)雜度遠(yuǎn)不如實際中真正的軟件系統(tǒng)，但為了培養(yǎng)一個軟件工作者所應(yīng)具備的科學(xué)工作的方法和作

風(fēng)，我們制訂了如下所述完成實習(xí)的5個步驟：

1.問題分析和任務(wù)定義

通常，實習(xí)題目的陳述比較簡潔，或者說有模棱兩可的含義。因此，在進(jìn)行設(shè)計之前，首先應(yīng)該充分

地分析和理解問題，明確問題要求做什么，限制條件是什么。注意：本步驟強(qiáng)調(diào)的是做什么，而不是怎么做。

對問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是對所需完成的任務(wù)作出明確的回答。例如：輸入數(shù)據(jù)的

類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值的范圍及輸出的形式；若是會話式的輸入，則結(jié)束標(biāo)

志是什么，是否接受非法的輸入，對非法輸入的回答方式是什么等等。這?步還應(yīng)該為調(diào)試程序準(zhǔn)備好測試

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

2.數(shù)據(jù)類型和系統(tǒng)設(shè)計

在設(shè)計這一步驟中需分邏輯設(shè)計和詳細(xì)設(shè)計兩步實現(xiàn)。邏輯設(shè)計指的是，對問題描述中涉及的操作對

象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。

詳細(xì)設(shè)計則為定義相應(yīng)的存儲結(jié)構(gòu)并寫出各過程和函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能,

使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說

明盡可能明確具體。作為邏輯設(shè)計的結(jié)果，應(yīng)寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基

本操作的規(guī)格說明），各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。詳細(xì)設(shè)汁的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)

和基本操作的規(guī)格說明作出進(jìn)?步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，按照算法書寫規(guī)范用類c語言寫

出過程或函數(shù)形式的算法框架。在求精的過程中，應(yīng)盡量避免陷入語言細(xì)節(jié)，不必過早表述輔助數(shù)據(jù)結(jié)構(gòu)和

局部變量。

3.編碼實現(xiàn)和靜態(tài)檢查

編碼是把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。如何編寫程序才能較快地完成調(diào)試是特別

要注意的問題。程序的每行不要超過60個字符。每個過程(函數(shù))體一般不要超過40行，最長不得超過

60行，否則應(yīng)該分割成較小的過程(函數(shù))。要控制if語句連續(xù)嵌套的深度，分支過多時應(yīng)考慮使用switch

語句。對函數(shù)功能和重要變量進(jìn)行注釋。一定要按格式書寫程序，分清每條語句的層次，對齊括號，這樣便

于發(fā)現(xiàn)語法錯誤。

在上機(jī)之前，應(yīng)該用筆在紙上寫出詳細(xì)的程序編碼，并做認(rèn)真地靜態(tài)檢查。多數(shù)初學(xué)者在編好程序后

處于以下兩種狀態(tài)之一：一種是對自己的“精心作品”的正確性確信不疑；另一種是認(rèn)為上機(jī)前的任務(wù)已經(jīng)

完成，糾查錯誤是上機(jī)的工作。這兩種態(tài)度是極為有害的。對一般的程序設(shè)計者而言，當(dāng)編寫的程序長度超

過50行時，通常會含有語法錯誤或邏輯錯誤。上機(jī)動態(tài)調(diào)試決不能代替靜態(tài)檢查，否則調(diào)試效率將是極低

的。靜態(tài)檢查主要有兩種方法，一是用一組測試數(shù)據(jù)手工執(zhí)行程序(通常應(yīng)先檢查單個模塊)；二是通過閱

讀或給別人講解自己的程序而深入全面地理解程序邏輯，在這個過程中再加入一些注解。

4.上機(jī)準(zhǔn)備和上機(jī)調(diào)試

上機(jī)準(zhǔn)備包括以下幾個方面：

(1)熟悉c語言用戶手冊或程序設(shè)計指導(dǎo)書。

(2)注意TurboC、VC與標(biāo)準(zhǔn)C語言之間的細(xì)微差別。

(3)熟悉機(jī)器的操作系統(tǒng)和語言集成環(huán)境的用戶手冊，尤其是最常用的命令操作，以便順利進(jìn)行上

機(jī)的基本活動。

(4)掌握調(diào)試工具，考慮調(diào)試方案，設(shè)計測試數(shù)據(jù)并手工得出正確結(jié)果?！澳サ恫徽`砍柴工”。學(xué)生

應(yīng)該熟練運用高級語言的程序調(diào)試器DEBUG調(diào)試程序。

上機(jī)調(diào)試程序時要帶?本高級語言教材或手冊。調(diào)試最好分模塊進(jìn)行，自底向上，即先調(diào)試低層過程

或函數(shù)。必要時可以另寫一個調(diào)用驅(qū)動程序。這種表面上麻煩的工作實際上可以大大降低調(diào)試所面臨的復(fù)雜

性，提高調(diào)試工作效率。

在調(diào)試過程中可以不斷借助DEBUG的各種功能，提高調(diào)試效率。調(diào)試中遇到的各種異?，F(xiàn)象往往是預(yù)

料不到的，此時不應(yīng)“苦思冥想”，而應(yīng)借助系統(tǒng)提供的調(diào)試工具確定錯誤。調(diào)試正確后，認(rèn)真整理源程序

及其注釋，印出帶有完整注釋的且格式良好的源程序清單和結(jié)果。

5.總結(jié)和整理實習(xí)報告

實習(xí)報告規(guī)范

實習(xí)報告的開頭應(yīng)給出題目、班級、姓名、學(xué)號和完成日期，并包括以下7個內(nèi)容:

1.需求分析

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

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

(2)輸出的形式;

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

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

2.概要設(shè)計

說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。

3.詳細(xì)設(shè)計

實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽碼算法；對主程序和其他模塊也都需要

寫出偽碼算法(偽碼算法達(dá)到的詳細(xì)程度建議為：按照偽碼算法可以在計算機(jī)鍵盤直接輸入高級程序設(shè)計語

言程序)；畫出函數(shù)和過程的調(diào)用關(guān)系圖。

4.調(diào)試分析

內(nèi)容包括：

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

b.算法的時空分析(包括基本操作和其他算法的時間復(fù)雜度和空間復(fù)雜度的分析)和

改進(jìn)設(shè)想：

c.經(jīng)驗和體會等。

5.用戶使用說明

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

6.測試結(jié)果

列出你的測試結(jié)果，包拈輸入和輸出。這里的測試數(shù)據(jù)應(yīng)該完整和嚴(yán)格，最好多了需求分析中所列。

7.附錄

帶注釋的源程序。如果提交源程序軟盤，可以只列出程序文件名的清單。

在以下各實習(xí)單元中都提供了實習(xí)報告實例。值得注意的是，實習(xí)報告的各種文檔資料，如：上述中

的前三部分要在程序開發(fā)的過程中逐漸充實形成，而不是最后補(bǔ)寫（當(dāng)然可以也應(yīng)該最后用實驗報告紙譽(yù)清

或打?。?/p>

實習(xí)題目

實習(xí)。抽象數(shù)據(jù)類型

三元組ADT

［問題描述］

設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“三元組”。每個三元組由任意三個實數(shù)的序列構(gòu)成，基本操作包括：創(chuàng)建個

三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，

兩個三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘?個比例因子，顯示三元組，銷毀三元組等。

［基本要求］

實現(xiàn)創(chuàng)建一個三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求

三元組的最小分量，顯示三元組等基本操作。

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

由學(xué)生任意指定。

［實現(xiàn)提示］

用結(jié)構(gòu)體封裝“三元組”的三個分量，并利用typedef對結(jié)構(gòu)體或結(jié)構(gòu)體指針重新命名。注意：如果要

實現(xiàn)銷毀三元組，則應(yīng)利用typedef對結(jié)構(gòu)體指針重新命名，并使用C語言的動態(tài)分配庫函數(shù)。

［選作內(nèi)容］

實現(xiàn)兩個三元組的對應(yīng)分量相加或相減，給-：元組的各分量同乘一個比例因子，銷毀三元組等操作。

有理數(shù)ADT

［問題描述］

設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”。

［基本要求］

實現(xiàn)有理數(shù)的加法、減法，以及求有理數(shù)的分子、分母等基木操作。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如有理數(shù)0。

［實現(xiàn)提示］

用結(jié)構(gòu)體封裝與“有理數(shù)”對應(yīng)的分子和分母。

［選作內(nèi)容］

實現(xiàn)有理數(shù)的乘法、除法運算。

復(fù)數(shù)ADT

［問題描述］

設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“復(fù)數(shù)”。

［基本要求］

實現(xiàn)復(fù)數(shù)的加法、減法、乘法，以及求復(fù)數(shù)的實部、虛部等基本操作。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)白已確定。注意測試邊界數(shù)據(jù)，如復(fù)數(shù)0。

［實現(xiàn)提示］

用結(jié)構(gòu)體封裝與“復(fù)數(shù)”對應(yīng)的實部、虛部。

［選作內(nèi)容］

實現(xiàn)復(fù)數(shù)的除法運算。

實習(xí)一線性表

本次實習(xí)的主要目的在于熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)上的實現(xiàn)，其中以熟悉各種鏈表的操作

為側(cè)重點。通過本次實習(xí)還可幫助讀者復(fù)習(xí)高級語言的使用方法。

城市鏈表

［問題描述］

將若干城市的信息，存入一個帶頭結(jié)點的單鏈表。結(jié)點中的城市信息包括：城市名，城市的位置坐標(biāo)。

要求能夠利用城市名和位置坐標(biāo)進(jìn)行有關(guān)查找、插入、刪除、更新等操作。

［基本要求］

(1)給定一個城市名，返回其位置坐標(biāo)；

(2)給定一個位置坐標(biāo)P和一個距離D,返回所有與P的距離小于等于D的城市.

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。

約瑟夫環(huán)

［問題描述］

約瑟夫（Joeph）問題的?種描述是：編號為1,2,…,n的n個人按順時針方向圍坐圈，每人持有一個

密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始按順時針方向自1開始順序報

數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重

新從1報數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計一個程序求出出列順序。

［基本要求］

利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號。

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

加的初值為20：密碼：3,1,7,2,4,8,4（正確的結(jié)果應(yīng)為6,1,4,7,2,3,5）。

［實現(xiàn)提示］

程序運行后首先要求用戶指定初始報數(shù)上限值，然后讀取各人的密碼。設(shè)nW30。

［選作內(nèi)容］

向上述程序中添加在順序結(jié)構(gòu)上實現(xiàn)的部分。

線性表的逆置

［問題描述］

分別以不同存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置。線性表的就地逆置就是在原表的存儲空間內(nèi)將線性表

（al,a2,a3,???,an）逆置為（an>an-l>???,a2,al）。

［基本要求］

用順序存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置，并將結(jié)果輸出。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空表。

［實現(xiàn)提示］

設(shè)三個連續(xù)的指針，分別指向當(dāng)前結(jié)點、當(dāng)前結(jié)點的前趨、當(dāng)前結(jié)點的后繼。

［選作內(nèi)容］

利用單鏈表作為存儲結(jié)構(gòu)。首先先建立線性表的帶頭結(jié)點的單鏈表表示形式，之后在不借助輔助結(jié)點空

間的情況卜.實現(xiàn)單鏈表的逆置，并將結(jié)果輸出。

長整數(shù)運算

［問題描述］

設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算。

［基本要求］

利用雙項循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整型變量。任何整型變量的范圍是-(215-1)

~(215-1)。輸入和輸出形式：按中國對于長整數(shù)的表示習(xí)慣，每四位一組，組間用逗號隔開。

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

(1)0；0；應(yīng)輸出“0”<,

(2)-2345,6789；-7654,3211；應(yīng)輸出"-1,0000,0000”。

(3)-9999,9999；1,0000,0000,0000；應(yīng)輸出“9999,0000,0001”。

(4)1,0001,000；-1,0001,0001：應(yīng)輸出“0"。

(5)1,0001,0001；-1,0001,0000；應(yīng)輸出"1"。

［實現(xiàn)提示］

(1)每個結(jié)點中可以存放的最大整數(shù)為215-1=32767,才能保證兩數(shù)相加不會溢出。但若這樣存，即

相當(dāng)于按32768進(jìn)制數(shù)存，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點中僅存十

進(jìn)制數(shù)的4位，即不超過9999的非負(fù)整數(shù)，整個鏈表視為萬進(jìn)制數(shù)。

(2)可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不

要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的種方法。不能給長整數(shù)位數(shù)

規(guī)定上限。

［選作內(nèi)容］

修改上述程序，使它在整型量范圍是-(2nT)~(2nT)的計算機(jī)上都能有效地運行。其中，n是由程

序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。

實習(xí)二棧、隊列與遞歸算法設(shè)計

僅僅認(rèn)識到棧和隊列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實習(xí)的目的在于使讀者深入了解棧和隊列

的特征，以便在實際問題背景下靈活運用它們；同時還將鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞

歸算法設(shè)計。

數(shù)制轉(zhuǎn)換問題

［問題描述］

將十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是計算機(jī)實現(xiàn)計算的基本問題，其解決方案很多，其中最簡單方法

基于下列原理：即除d取余法。例如:(1348)10=(2504)8

NNdiv8Nmod8

13481684

168210

2125

202

從中我們可以看出，最先產(chǎn)生的余數(shù)4是轉(zhuǎn)換結(jié)果的最低位，這正好符合棧的特性即后進(jìn)先出的特性。

所以可以用順序棧來模擬這個過程。

［基本要求］

對于鍵盤輸入的任意一個非負(fù)的十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。由于上述的計算過程是從

低位到高位順序產(chǎn)生的八進(jìn)制數(shù)的各個數(shù)位，而打印輸出，一般來說應(yīng)從高位到地位進(jìn)行，恰好和計算過程

相反。因此可以先將計算過程中得到的八進(jìn)制數(shù)的各位進(jìn)棧，待相對應(yīng)的八進(jìn)制數(shù)的各位均產(chǎn)生以后，再使

其按順序出棧，并打印輸出。即得到了與輸入的十進(jìn)制數(shù)相對應(yīng)的八進(jìn)制數(shù)。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。

回文判斷

［問題描述］

試寫一個算法，判斷依次讀入的一個以@為結(jié)束符的字母序列，是否為形如'序列1&序列2,模式

的字符序列。其中序列1和序列2中都不含字符,且序列2是序列1的逆序列。例如，'a+b&b+a'

是屬該模式的字符序列，而T+3&3——則不是。

［實現(xiàn)提示］

首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如序列1和序列2均為空串。

商品貨架管理

［問題描述］

商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。匕貨時，需要倒貨

架，以保證生產(chǎn)日期較近的商品在較下的位置。

［基本要求］

針對一種特定商品，實現(xiàn)上述管理過程。

［實現(xiàn)提示］

用棧模擬貨架和周轉(zhuǎn)空間。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空棧。

括號匹配的檢驗

［問題描述］

假設(shè)表達(dá)式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即(()［］)或

［(［］［」)］等為正確格式，［(］)或(((］均為不正確的格式。檢驗括號是否匹配的方法可用“期待

的緊迫程度”這個概念來描述。例如：考慮下列的括號序列：

［(［］［］)］

12345678

當(dāng)計算機(jī)接受了第1個括號以后，他期待著與其匹配的第8個括號的出現(xiàn)，然而等來的卻是第2個括號,

此時第1個括號只能暫時靠邊，而迫切等待與第2個括號相匹配的第7個括號“)”的出現(xiàn)，類似的,

因只等來了第3個括號，此時，，其期待的緊迫程度較第2個括號更緊迫，則第2個括號只能靠邊，讓

位于第3個括號，顯然第3個括號的期待緊迫程度高于第2個括號，而第2個括號的期待緊迫程度高于第1

個括號；在接受了第4個括號之后，第3個括號的期待得到了滿足，消解之后，第2個括號的期待匹配就成

了最急迫的任務(wù)了，……，依次類推?？梢娺@個處理過程正好和棧的特點相吻合。

［基本要求］

讀入圓括號和方括號的任意序列，輸出“匹配”或“此串括號匹配不合法”。

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

輸入(［］()),結(jié)果“匹配”

輸入［()］,結(jié)果“此串括號匹配不合法”

［實現(xiàn)提示］

設(shè)置一個棧，每讀入一個括號，若是左括號，則作為一個新的更急迫的期待壓入棧中；若是右括號，并

且與當(dāng)前棧頂?shù)淖罄ㄌ栂嗥ヅ?，則將當(dāng)前棧頂?shù)淖罄ㄌ柾顺觯^續(xù)讀下一個括號，如果讀入的右括號與當(dāng)前

棧頂?shù)淖罄ㄌ柌黄ヅ洌瑒t屬于不合法的情況。在初始和結(jié)束時，棧應(yīng)該是空的。

［選作內(nèi)容］

考慮增加大括號的情況。

停車場管理

［問題描述］

設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有?個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車

輛到達(dá)時間的先后順序，依次由北向南排列(大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端)，

若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，?旦有車開走，則排在便道上的第?輛

車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大

門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納

費用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。

［測試數(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ù)包括三個數(shù)據(jù)項:汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，其中，'A'

表示到達(dá)：'D，表示離去，'E’表示輸入結(jié)束。

［基本要求］

以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸

入數(shù)據(jù)包拈三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入

數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；

則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用(在便道上停留的時間不收費)。棧以順序結(jié)構(gòu)實現(xiàn)，隊

列以鏈表實現(xiàn)。

［實現(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)以滿足這種

要求。

實習(xí)三串及其應(yīng)用

本次實習(xí)的目的是熟悉串類型的實現(xiàn)方法和文本模式匹配方法，熟悉一般文字處理軟件的設(shè)計方法，較

復(fù)雜問題的分解求精方法，在第二次實習(xí)的基礎(chǔ)上，進(jìn)步強(qiáng)化這樣?個觀念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在

其上的操作，此外還希望起到訓(xùn)練合作能力和熟悉文件操作的目的。本次實習(xí)的難度較大。

文學(xué)研究助手

［問題描述］

文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)

計系統(tǒng)，稱為“文學(xué)研究助手”。

［基本要求］

英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行

之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計。

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

以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計的詞匯集。

［實現(xiàn)提示］

設(shè)小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計每個詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行

的行號可以用鏈表存儲。若某行中出現(xiàn)了不止一次，不必存多個相同的行號。

如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價形式，

再將它推廣到多個模式的情形。

［選作內(nèi)容］

（1）模式匹配要基于KMP算法。

（2）整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。

（3）假設(shè)小說中的每個單詞或者從行首開始，或者前置以一個空格符。利用單詞匹配特點另寫一個高

效的統(tǒng)計程序，與K.MP算法統(tǒng)計程序進(jìn)行效率比較。

（4）推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）

簡單行編輯程序

［問題描述］

文本編輯程序是利用計算機(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)以F4條基本編輯命令：

（1）行插入。格式：i〈行號X回車X文本〉〈回車》

將〈文本》插入活區(qū)中第〈行號》行之后

（2）行刪除。格式：d〈行號1＞［口＜行號2＞"回車》

刪除活區(qū)中第〈行號1＞行（到第〈行號2＞行）。兩種格式的例子是：“diO/”和?dl0O14/M

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

將活區(qū)寫入輸出文件，并從輸入文件中讀入F一段，作為新的活區(qū)。

（4）活區(qū)顯示。格式：p〈回車〉

逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是否繼續(xù)顯示以后各頁（如果存在）。

印出的每一行要前置以行號和一個空格符，行號固定占4位，增量為1。

各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第一行行號減1,

表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如首行、尾行。

［實現(xiàn)提示］

（1）設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來描述?？紤]到文本文件行長通常為正態(tài)分布,

且峰值在60到70之間，用320Xactivemaxlen大小的字符數(shù)組實現(xiàn)存儲將造成大量浪費。可以以標(biāo)準(zhǔn)行塊

為單位為各行分配存儲，每個標(biāo)準(zhǔn)行塊含81個字符。這些行塊可以組成一個數(shù)組，也可以利用動態(tài)鏈表連

接起來。一行文字可能占多個行塊。行尾可用一個特殊的ASCII字符（如（012）8）標(biāo)識。此外，還應(yīng)記住活

區(qū)起始行號。行插入將引起隨后各行行號的順序卜.推。

（2）初始化過程包括：清用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。

然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlen-x。x的值可以自定，例如20。

（3）在執(zhí)行行插入命令的過程中，每接收到行時到要檢查活區(qū)大小是否已達(dá)activemaxlen。如果

是，則為了在插入這一行之后仍保持活區(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)行模式匹配等，格式可以為S〈行號〉@＜

串1＞@＜串2＞〈回車＞和m〈串X回車〉。

實習(xí)四樹、圖及其應(yīng)用

樹和圖是兩種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點。它們的特點在于非線性。廣義表本質(zhì)上

是樹結(jié)構(gòu)；稀疏矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu)，故也把它們歸在這次實習(xí)中。本章實習(xí)繼

續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計觀點，但根據(jù)這兩種結(jié)構(gòu)的非線性特點，將操作進(jìn)一步集中在遍歷操作

上，因為遍歷操作是其他眾多操作的基礎(chǔ)。遍歷邏輯的（或符號形式的）結(jié)構(gòu)，訪問動作可是任何操作。本

次實習(xí)還希望達(dá)到熟悉各種存儲結(jié)構(gòu)的特征，以及如何應(yīng)用樹和圖結(jié)構(gòu)解決具體問題（即原理與應(yīng)用的結(jié)合）

等目的。

二叉樹的建立與遍歷

［問題描述］

建立?棵：叉樹，并對其進(jìn)行遍歷（先序、中序、后序），打印輸出遍歷結(jié)果。

［基本要求］

從鍵盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），并采用遞歸算法

對其進(jìn)行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出。

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

ABC也"DE巾G巾"F小巾"（其中也表示空格字符）

則輸出結(jié)果為先序：ABCDEGF

中序：CBEGDFA

后序：CGBFDBA

［選作內(nèi)容］

采用非遞歸算法實現(xiàn)二叉樹遍歷。

打印二叉樹結(jié)構(gòu)

［問題描述］

按凹入表形式橫向打印二叉樹結(jié)構(gòu)，即二叉樹的根在屏幕的最左邊，二叉樹的左子樹在屏幕的下邊，二

叉樹的右子樹在屏幕的上邊。

例如：

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空二叉樹。

［實現(xiàn)提示］

(1)利用RDL遍歷方法;

(2)利用結(jié)點的深度控制橫向位置。

打印樹結(jié)構(gòu)

［問題描述］

按凹入表形式打印樹形結(jié)構(gòu)。

例如：

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空樹。

［實現(xiàn)提示］

（1）利用樹的先根遍歷方法；

（2）利用結(jié)點的深度控制橫向位置。

圖遍歷的演示

［問題描述］

很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個程序，演示無向圖的遍歷操作。

［基本要求］

以鄰接表為存儲結(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點為起點，分別輸

出每種遍歷下的結(jié)點訪問序列和相應(yīng)生成樹的邊集。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如單個結(jié)點。

［實現(xiàn)提示］

設(shè)圖的結(jié)點不超過30個，每個結(jié)點用一個編號表示（如果一個圖有n個結(jié)點，則它們的編號分別為

1,2,…,n）。通過輸入圖的全部邊輸入一個圖，每個邊為一個數(shù)對，可以對邊的輸入順序作出某種限制。注

意，生成樹的邊是有向邊，端點順序不能顛倒。

［選作內(nèi)容］

（1）借助于棧類型（自己定義和實現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實現(xiàn)。

（2）以鄰接多重表為存儲結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹

（3）實現(xiàn)有向圖的遍歷操作。

實習(xí)五查找和排序

本次實習(xí)旨在集中對幾個專門的問題作較為深入的探討和理解，不強(qiáng)調(diào)對某些特定的編程技術(shù)的訓(xùn)練。

二叉排序樹

［問題描述］

從鍵盤讀入?組數(shù)據(jù)，建立二叉排序樹并對其進(jìn)行查找、遍歷、格式化打印等有關(guān)操作。

［基本要求］

建立二叉排序樹并對其進(jìn)行查找，包括成功和不成功兩種情況，并給出查找長度。

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

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。

［選作內(nèi)容］

實現(xiàn)二叉排序樹的插入、刪除操作。

哈希表設(shè)計

［問題描述］

針對某個集體中人名設(shè)計?個哈希衣，使得平均查找長度不超過R,并完成相應(yīng)的建表和查表程序。

［基本要求］

假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。

哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。

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

取讀者周圍較熟悉的30個人名。

［選作內(nèi)容］