數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告格式

1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)大綱 一、 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)的地位與作用 “數(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)和實(shí)現(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í)中的重點(diǎn)也是難點(diǎn)；（3） 所用到的技術(shù)多，而在此之前的各門課程中所介紹的專業(yè)性知識又不多，因而加大了學(xué)

2、習(xí)難度；（4） 隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點(diǎn)和難點(diǎn)。 根據(jù)數(shù)據(jù)結(jié)構(gòu)課程課程本身的技術(shù)特性，設(shè)置數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)實(shí)踐環(huán)節(jié)十分重要。通過實(shí)驗(yàn)實(shí)踐內(nèi)容的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征, 目的是提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力。實(shí)驗(yàn)學(xué)時為18。二、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)的目的和要求不少學(xué)生在解答習(xí)題尤其是算法設(shè)計題時，覺得無從下手，做起來特別費(fèi)勁。實(shí)驗(yàn)中的內(nèi)容和教科書的內(nèi)容是密切相關(guān)的，解決題目要求所需的各種技術(shù)大多可從教科書中找到，只不過其出現(xiàn)的形式呈多樣化，因此需要仔細(xì)體會，在反復(fù)實(shí)踐的過程中才能掌握。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計所需的技術(shù)，為整個專業(yè)學(xué)習(xí)打好基礎(chǔ)

3、，要求運(yùn)用所學(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ù)等，要求重點(diǎn)掌握線性鏈表、二叉樹和樹、圖結(jié)構(gòu)、數(shù)組結(jié)構(gòu)相關(guān)算法的設(shè)計。在掌握基本算法的基礎(chǔ)上，掌握分析、解決實(shí)際問題的能力。三、 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)內(nèi)容課程實(shí)驗(yàn)共18學(xué)時，要求完成以下六個題目：實(shí)習(xí)一 約瑟夫環(huán)問題（2學(xué)時）用循環(huán)鏈表實(shí)現(xiàn)約瑟夫環(huán)問題，熟悉鏈表結(jié)構(gòu)的使用。實(shí)習(xí)二 停車場管理（4學(xué)時） 利用棧和隊列模擬停車場管理，學(xué)習(xí)利用

4、棧和隊列解決實(shí)際問題。實(shí)習(xí)三 二叉樹基本操作（3學(xué)時）創(chuàng)建、遍歷、插入、刪除、顯示二叉樹，通過二叉樹的基本操作，掌握樹結(jié)構(gòu)的處理方法。實(shí)習(xí)四 圖的基本操作（3學(xué)時）分別用鄰接矩陣和鄰接表實(shí)現(xiàn)以下操作：圖的創(chuàng)建、遍歷、插入、刪除、最短路徑。熟悉圖的常用存儲結(jié)構(gòu)和基本操作。實(shí)習(xí)五 哈希表設(shè)計（3學(xué)時）給定30個人的姓名，用除留余數(shù)法構(gòu)造哈希函數(shù)，用線性探測再散列法處理沖突，構(gòu)造哈希表，掌握哈希表的設(shè)計與使用。實(shí)習(xí)六 常用排序算法的對比分析（3學(xué)時）分別實(shí)現(xiàn)直接插入排序、冒泡排序、簡單選擇排序、希爾排序、快速排序、堆排序，并隨機(jī)生成30個數(shù)，比較各算法的時、空性能和穩(wěn)定性。掌握常用排序算法的特點(diǎn)，以

5、便根據(jù)實(shí)際情況選擇使用。 四、 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)考核方式采用上機(jī)情況、程序質(zhì)量、實(shí)習(xí)報告相結(jié)合的形式，滿分為100分。1 上機(jī)情況（30%）包括出勤情況、調(diào)試表現(xiàn)、是否上網(wǎng)、玩游戲。2 程序質(zhì)量（50%）3 實(shí)習(xí)報告（20%）實(shí)習(xí)一 線性表本次實(shí)習(xí)的主要目的在于熟悉線性表的基本運(yùn)算在兩種存儲結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點(diǎn)。通過本次實(shí)習(xí)還可幫助讀者復(fù)習(xí)高級語言的使用方法。 約瑟夫環(huán)問題描述約瑟夫（Joeph）問題的一種描述是：編號為1,2,n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，

6、報到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）。實(shí)現(xiàn)提示程序運(yùn)行后首先要求用戶指定初始報數(shù)上限值，然后讀取各人的密碼。設(shè)n30。選作內(nèi)容向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。長整數(shù)運(yùn)算問題描述設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運(yùn)算?；疽罄秒p項(xiàng)循環(huán)鏈表實(shí)現(xiàn)長整數(shù)的存儲，每個結(jié)點(diǎn)含一個整型變量。任何整

7、型變量的范圍是-（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”。實(shí)現(xiàn)提示（1） 每個結(jié)點(diǎn)中可以存放的最大整數(shù)為215-1=32767，才能保證兩數(shù)相加不會溢出。但若這樣存，即

8、相當(dāng)于按32768進(jìn)制數(shù)存，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過9999的非負(fù)整數(shù)，整個鏈表視為萬進(jìn)制數(shù)。（2） 可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點(diǎn)數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。選作內(nèi)容修改上述程序，使它在整型量范圍是-（2n-1）（2n-1）的計算機(jī)上都能有效地運(yùn)行。其中，n是由程序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。實(shí)習(xí)二 棧、隊列與遞歸算法設(shè)計僅僅認(rèn)識到棧和隊列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)

9、習(xí)的目的在于使讀者深入了解棧和隊列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；同時還將鞏固這兩種結(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)入車場，每輛停放在車場的車在它離開停車場時

10、必須按它停留的時間長短交納費(fèi)用。試為停車場編制按上述要求進(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é)束?；疽笠詶ＤM停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；

11、則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用（在便道上停留的時間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊列以鏈表實(shí)現(xiàn)。實(shí)現(xiàn)提示需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項(xiàng)：汽車的牌照號碼和進(jìn)入停車場的時刻。選作內(nèi)容（1） 兩個棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？（2） 汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。（3） 汽車可以直接從便道上開走，此時派在它前面的汽車要先開走讓路，然后再

12、依次排到隊尾。（4） 停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。實(shí)習(xí)三 串及其應(yīng)用本次實(shí)習(xí)的目的是熟悉串類型的實(shí)現(xiàn)方法和文本模式匹配方法，熟悉一般文字處理軟件的設(shè)計方法，較復(fù)雜問題的分解求精方法，在第二次實(shí)習(xí)的基礎(chǔ)上，進(jìn)一步強(qiáng)化這樣一個觀念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在其上的操作，此外還希望起到訓(xùn)練合作能力和熟悉文件操作的目的。本次實(shí)習(xí)的難度較大。 文學(xué)研究助手問題描述文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)，稱為“文學(xué)研究助手”?；疽笥⑽男≌f存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完

13、畢，即統(tǒng)計工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計。測試數(shù)據(jù)以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計的詞匯集。實(shí)現(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è)小說中的每個單

14、詞或者從行首開始，或者前置以一個空格符。利用單詞匹配特點(diǎn)另寫一個高效的統(tǒng)計程序，與KMP算法統(tǒng)計程序進(jìn)行效率比較。（4） 推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）簡單行編輯程序問題描述文本編輯程序是利用計算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟(jì)，也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)。試按照這種方法實(shí)現(xiàn)一個簡單的行編輯程序。設(shè)文件每行不超過320個

15、字符，很少超過80字符?；疽髮?shí)現(xiàn)以下4條基本編輯命令：（1） 行插入。格式：i將插入活區(qū)中第行之后（2）行刪除。格式：d刪除活區(qū)中第行（到第行）。兩種格式的例子是：“d10”和“d1014”（3）活區(qū)切換。格式：n將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。（4）活區(qū)顯示。格式：p逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是否繼續(xù)顯示以后各頁（如果存在）。印出的每一行要前置以行號和一個空格符，行號固定占4位，增量為1。各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第一行行號減1，表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。實(shí)

16、現(xiàn)提示（1） 設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來描述。考慮到文本文件行長通常為正態(tài)分布，且峰值在60到70之間，用320activemaxlen大小的字符數(shù)組實(shí)現(xiàn)存儲將造成大量浪費(fèi)?？梢砸詷?biāo)準(zhǔn)行塊為單位為各行分配存儲，每個標(biāo)準(zhǔn)行塊含81個字符。這些行塊可以組成一個數(shù)組，也可以利用動態(tài)鏈表連接起來。一行文字可能占多個行塊。行尾可用一個特殊的ASCII字符（如(012)8）標(biāo)識。此外，還應(yīng)記住活區(qū)起始行號。行插入將引起隨后各行行號的順序下推。（2） 初始化過程包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但

17、不超過activemaxlen-x。x的值可以自定，例如20。（3） 在執(zhí)行行插入命令的過程中，每接收到一行時到要檢查活區(qū)大小是否已達(dá)activemaxlen。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen，應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點(diǎn)為第一行之前，則只得將新插入的這一行輸出。（4） 若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開始編輯另一個文件。（5） 可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示。選作內(nèi)容（1） 對于命令格式非法等一切錯誤作嚴(yán)格檢查和適當(dāng)處理。（2） 加入更復(fù)雜

18、的編輯操作，如對某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為S和m。實(shí)習(xí)四 樹、圖及其應(yīng)用樹和圖是兩種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點(diǎn)。它們的特點(diǎn)在于非線性。廣義表本質(zhì)上是樹結(jié)構(gòu)；稀疏矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu)，故也把它們歸在這次實(shí)習(xí)中。本章實(shí)習(xí)繼續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計觀點(diǎn)，但根據(jù)這兩種結(jié)構(gòu)的非線性特點(diǎn)，將操作進(jìn)一步集中在遍歷操作上，因?yàn)楸闅v操作是其他眾多操作的基礎(chǔ)。遍歷邏輯的（或符號形式的）結(jié)構(gòu)，訪問動作可是任何操作。本次實(shí)習(xí)還希望達(dá)到熟悉各種存儲結(jié)構(gòu)的特征，以及如何應(yīng)用樹和圖結(jié)構(gòu)解決具體問題（即原理與應(yīng)用的結(jié)合）等目的。 圖遍歷的演示問題描述很多涉

19、及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個程序，演示連通的無向圖上行邊全部結(jié)點(diǎn)的操作?；疽笠脏徑佣嘀乇頌榇鎯Y(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。 實(shí)現(xiàn)提示設(shè)圖的結(jié)點(diǎn)不超過30個，每個結(jié)點(diǎn)用一個編號表示（如果一個圖有n個結(jié)點(diǎn)，則它們的編號分別為1,2,n）。通過輸入圖的全部邊輸入一個圖，每個邊為一個數(shù)對，可以對邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點(diǎn)順序不能顛倒。選作內(nèi)容（1） 借助于棧類型（自己定義和實(shí)現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。（2） 以鄰接表為存儲結(jié)構(gòu)建立深度優(yōu)先生成

20、樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹。 實(shí)習(xí)五 查找和排序本次實(shí)習(xí)旨在集中對幾個專門的問題作較為深入的探討和理解，也不強(qiáng)調(diào)對某些特定的編程技術(shù)的訓(xùn)練。哈希表設(shè)計問題描述 針對某個集體中人名設(shè)計一個哈希表，使得平均查找長度不超過R，并完成相應(yīng)的建表和查表程序?；疽蠹僭O(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。測試數(shù)據(jù)取讀者周圍較熟悉的30個人名。選作內(nèi)容（1） 從教科書上介紹的集中哈希函數(shù)構(gòu)造方法中選出適用者并設(shè)計幾個不同的哈希函數(shù)，比較他們的地址沖突率（可以用更大的名字集

21、合作實(shí)驗(yàn)）。（2） 研究這30個人名的特點(diǎn)，努力找一個哈希函數(shù)，使得對于不同的拼音名一定不發(fā)生地址沖突。（3） 在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考察平均查找長度的變化和造好的哈希表中關(guān)鍵字的聚集性。內(nèi)部排序算法比較問題描述各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機(jī)的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受?；疽螅?） 對以下10種常用的內(nèi)部排序算法進(jìn)行比較：直接插入排序；折半折入排序；二路插入排序；希爾排序；起泡排序；快速排序；簡單選擇排序；堆排序；歸并排序；基數(shù)排序。（2） 待排序表的表長不少于100；

22、其中的數(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)生器決定。實(shí)現(xiàn)提示主要工作是設(shè)法在程序中適當(dāng)?shù)牡胤讲迦胗嫈?shù)操作。程序還可以包括計算幾組數(shù)據(jù)得出結(jié)果波動大小的解釋。注意分塊調(diào)試的方法。選作內(nèi)容對不同的輸入表長做試驗(yàn)，觀察檢查兩個指標(biāo)相關(guān)于表長的變化關(guān)系。還可以對穩(wěn)定性做驗(yàn)證。實(shí)驗(yà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)和實(shí)現(xiàn)算法，介紹了多種常用的查找和排序技術(shù)，并對其進(jìn)行了性能分

23、析和比較，內(nèi)容非常豐富。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計水平的提高打下良好的基礎(chǔ)。 由于以下原因，使得掌握這門課程具有較大難度： 內(nèi)容多，時間短，給學(xué)習(xí)帶來困難； 貫穿全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點(diǎn)和難點(diǎn)； 隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點(diǎn)和難點(diǎn)； 先修課程中所介紹的專業(yè)性知識不多，加大了學(xué)習(xí)難度。 由于數(shù)據(jù)結(jié)構(gòu)課程的技術(shù)性與實(shí)踐性，數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)的設(shè)置十分必要。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計所需的技術(shù)，為整個專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運(yùn)用所學(xué)知識，上機(jī)解決一些典型問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用

24、到的一些技術(shù)。數(shù)據(jù)結(jié)構(gòu)中稍微復(fù)雜一些的算法設(shè)計中可能同時要用到多種技術(shù)和方法，如算法設(shè)計的構(gòu)思方法，動態(tài)鏈表，算法的編碼，遞歸技術(shù)，與特定問題相關(guān)的技術(shù)等，要求重點(diǎn)掌握線性鏈表、二叉樹和樹、圖結(jié)構(gòu)、數(shù)組結(jié)構(gòu)相關(guān)算法的設(shè)計。在掌握基本算法的基礎(chǔ)上，掌握分析、解決實(shí)際問題的能力。通過實(shí)驗(yàn)實(shí)踐內(nèi)容的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征, 提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力。 上機(jī)實(shí)習(xí)是對學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個教學(xué)環(huán)節(jié)。較大的實(shí)習(xí)題比平時的習(xí)題要復(fù)雜得多，也更接近實(shí)際。實(shí)習(xí)著眼于原理與應(yīng)用的結(jié)合點(diǎn)，使學(xué)生學(xué)會如何把書上學(xué)到的知識用于解決實(shí)際問題，培養(yǎng)軟件工

25、作所需要的動手能力。實(shí)習(xí)還能使書上的知識變“活”，達(dá)到深化理解和靈活掌握教學(xué)內(nèi)容的目的。平時的練習(xí)較偏重于如何編寫功能單一的“小”算法，而實(shí)習(xí)題是軟件設(shè)計的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計，用戶界面設(shè)計，程序設(shè)計基本技能和技巧，多人合作，以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，還有很重要的一點(diǎn)是：機(jī)器是比任何教師都嚴(yán)格的檢查者。 為了達(dá)到上述目的，本書安排了6個主實(shí)習(xí)單元，其中實(shí)習(xí)0的訓(xùn)練重點(diǎn)是抽象數(shù)據(jù)類型的定義與實(shí)現(xiàn)方法，其它各單元的訓(xùn)練重點(diǎn)在于基本的數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法。各實(shí)習(xí)單元與教科書的各章只具有粗略的對應(yīng)關(guān)系，一個實(shí)習(xí)題可能涉及幾部分教學(xué)內(nèi)容。在每個實(shí)習(xí)單元中安排有難度

26、不等的25個實(shí)習(xí)題，每人可以從中選做一個實(shí)習(xí)題。建議選做難度略高于自己所做過的最難題目的難度，切忌過分追求難題。較大的題目適合于多人合作。 每個實(shí)習(xí)題采取了統(tǒng)一的格式，由問題描述、基本要求、測試數(shù)據(jù)、實(shí)現(xiàn)提示和選做內(nèi)容等5個部分組成。 問題描述旨在為讀者建立問題提出的背景環(huán)境，指明問題“是什么”； 基本要求則對問題進(jìn)一步求精，劃出問題的邊界，指出具體的參量或前提條件，并規(guī)定該題的最低限度要求； 測試數(shù)據(jù)部分旨在為檢查學(xué)生上機(jī)作業(yè)提供方便，在完成實(shí)習(xí)題時應(yīng)自己設(shè)計完整和 嚴(yán)格的測試方案，當(dāng)數(shù)據(jù)輸入量較大時，提倡以文件形式向程序提供輸入數(shù)據(jù)； 實(shí)現(xiàn)提示對實(shí)現(xiàn)中的難點(diǎn)及其解法思路等問題作了簡要提示，

27、個別問題給出了參考實(shí)現(xiàn)； 選做內(nèi)容向那些尚有余力的讀者提出了更嚴(yán)峻的挑戰(zhàn)，同時也能開拓其他讀者的思路，在完成基本要求時就力求避免就事論事的不良思想方法，盡可能尋求具有普遍意義的解法，使得程序結(jié)構(gòu)合理，容易修改擴(kuò)充。 書中題目設(shè)計得比較詳細(xì)，給出了問題說明和問題分解求精的范例，使讀者在無形中學(xué)會模仿，它起到把讀者的思路引上正軌的作用，避免不良結(jié)構(gòu)程序和壞習(xí)慣，同時也傳授了系統(tǒng)劃分方法和程序設(shè)計的一些具體技術(shù)，保證實(shí)現(xiàn)預(yù)定的訓(xùn)練意圖，使某些難點(diǎn)和重點(diǎn)不會被繞過去，而且也便于教學(xué)檢查。題目設(shè)計策略是：一方面使其難度和工作量都較大，另方面給讀者提供的輔助和可以模仿的部分也較多。當(dāng)然還應(yīng)指出的是，提示的

28、實(shí)現(xiàn)方法未必是最好的，讀者不應(yīng)拘泥于此，而應(yīng)爭取找出更好的方法和結(jié)構(gòu)。在實(shí)現(xiàn)的時候應(yīng)注意，要盡量減少依賴于具體機(jī)器計算環(huán)境的用法，若使用，也應(yīng)在注釋中指出。這樣得出的程序易于在不同機(jī)器上運(yùn)行，有好的可移植性。C語言是結(jié)構(gòu)化程序設(shè)計語言，具有遞歸能力，可移植性也較好，是特別推薦的實(shí)現(xiàn)語言。 本書的一個特點(diǎn)是為實(shí)習(xí)制定了嚴(yán)格的規(guī)范。一種普遍存在的錯誤觀念是，調(diào)試程序全憑運(yùn)氣。學(xué)生花2個小時的機(jī)上時間只找出一個錯誤，甚至一無所獲的情況是常見的。其原因在于，很多人只認(rèn)識到找錯誤，而沒有認(rèn)識到努力預(yù)先避免錯誤的重要性，也不知道應(yīng)該如何努力。實(shí)際上，結(jié)構(gòu)不好、思路和概念不清的程序可能是根本無法調(diào)試正確的。

29、嚴(yán)格按照實(shí)習(xí)步驟規(guī)范進(jìn)行實(shí)習(xí)，不但能有效地避免上述種種問題，更重要的是有利于培養(yǎng)軟件工作者不可缺少的科學(xué)工作方法和作風(fēng)。 在附錄中提供了一個完整的實(shí)習(xí)報告示例，在起到實(shí)習(xí)報告規(guī)格范例作用的同時，還隱含地提供了很多有益的東西，比如基于數(shù)據(jù)類型的系統(tǒng)劃分方法以及所提倡的程序設(shè)計風(fēng)格等等。計算機(jī)學(xué)科在不斷發(fā)展，可以使用的語言工具越來越豐富，在本書中的實(shí)習(xí)示例是應(yīng)用面向過程的語言進(jìn)行設(shè)計和編程，同樣的實(shí)習(xí)題，也可以用面向?qū)ο蟮恼Z言來實(shí)現(xiàn)。希望書中的實(shí)習(xí)報告示例能起到一個拋磚引玉的作用，以引來讀者更多更優(yōu)良的設(shè)計范例。實(shí)習(xí)步驟隨著計算機(jī)性能的提高，它所面臨的軟件開發(fā)的復(fù)雜度也日趨增加，因此軟件開發(fā)需要系

30、統(tǒng)的方法。一種常用的軟件開發(fā)方法，是將軟件開發(fā)過程分為分析、設(shè)計、實(shí)現(xiàn)和維護(hù)四個階段。雖然數(shù)據(jù)結(jié)構(gòu)課程中的實(shí)習(xí)題的復(fù)雜度遠(yuǎn)不如實(shí)際中真正的軟件系統(tǒng)，但為了培養(yǎng)一個軟件工作者所應(yīng)具備的科學(xué)工作的方法和作風(fēng)，我們制訂了如下所述完成實(shí)習(xí)的5個步驟：1問題分析和任務(wù)定義 通常，實(shí)習(xí)題目的陳述比較簡潔，或者說有模棱兩可的含義。因此，在進(jìn)行設(shè)計之前，首先應(yīng)該充分地分析和理解問題，明確問題要求做什么，限制條件是什么。注意：本步驟強(qiáng)調(diào)的是做什么，而不是怎么做。對問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是對所需完成的任務(wù)作出明確的回答。例如：輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值的范圍及輸

31、出的形式；若是會話式的輸入，則結(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è)計兩步實(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ù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。作為邏輯設(shè)

32、計的結(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編碼實(shí)現(xiàn)和靜態(tài)檢查 編碼是把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。如何編寫程序才能較快地完成調(diào)試是特別要注意的問題。程序的每行不要超過60個字符。每個過程（函數(shù)）體一般不要超過40行，最長不得超過60行，否則應(yīng)該分割成較小的過程（函數(shù)

33、）。要控制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í)

34、行程序（通常應(yīng)先檢查單個模塊）；二是通過閱讀或給別人講解自己的程序而深入全面地理解程序邏輯，在這個過程中再加入一些注解。4上機(jī)準(zhǔn)備和上機(jī)調(diào)試 上機(jī)準(zhǔn)備包括以下幾個方面：（1）熟悉C語言用戶手冊或程序設(shè)計指導(dǎo)書。（2）注意Turbo C、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)該熟練運(yùn)用高級語言的程序調(diào)試器DEBUG調(diào)試程序。 上機(jī)調(diào)試程序時要帶一本高級語言教材或手冊。調(diào)試最好分模塊進(jìn)行，自底向上，即先調(diào)試

35、低層過程或函數(shù)。必要時可以另寫一個調(diào)用驅(qū)動程序。這種表面上麻煩的工作實(shí)際上可以大大降低調(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é)和整理實(shí)習(xí)報告實(shí)習(xí)報告規(guī)范實(shí)習(xí)報告的開頭應(yīng)給出題目、班級、姓名、學(xué)號和完成日期，并包括以下7個內(nèi)容：1需求分析以無歧義的陳述說明程序設(shè)計的任務(wù)，強(qiáng)調(diào)的是程序要做什么？并明確規(guī)定：(1) 輸入的形式和輸入值的范圍；(2) 輸出

36、的形式；(3) 程序所能達(dá)到的功能；(4) 測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。2概要設(shè)計說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。3詳細(xì)設(shè)計實(shí)現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽碼算法；對主程序和其他模塊也都需要寫出偽碼算法(偽碼算法達(dá)到的詳細(xì)程度建議為：按照偽碼算法可以在計算機(jī)鍵盤直接輸入高級程序設(shè)計語言程序)；畫出函數(shù)和過程的調(diào)用關(guān)系圖。4調(diào)試分析內(nèi)容包括：a調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實(shí)現(xiàn)的回顧討論和分析；b算法的時空分析(包括基本操作和其他算法的時間復(fù)雜度和空間復(fù)雜度的分

37、析)和改進(jìn)設(shè)想；c經(jīng)驗(yàn)和體會等。5用戶使用說明說明如何使用你編寫的程序，詳細(xì)列出每一步的操作步驟。6測試結(jié)果列出你的測試結(jié)果，包括輸入和輸出。這里的測試數(shù)據(jù)應(yīng)該完整和嚴(yán)格，最好多于需求分析中所列。7附錄帶注釋的源程序。如果提交源程序軟盤，可以只列出程序文件名的清單。在以下各實(shí)習(xí)單元中都提供了實(shí)習(xí)報告實(shí)例。值得注意的是，實(shí)習(xí)報告的各種文檔資 料，如：上述中的前三部分要在程序開發(fā)的過程中逐漸充實(shí)形成，而不是最后補(bǔ)寫(當(dāng)然可以也應(yīng)該最后用實(shí)驗(yàn)報告紙謄清或打印)。 實(shí)習(xí)題目實(shí)習(xí) 抽象數(shù)據(jù)類型三元組ADT問題描述設(shè)計實(shí)現(xiàn)抽象數(shù)據(jù)類型“三元組”。每個三元組由任意三個實(shí)數(shù)的序列構(gòu)成，基本操作包括：創(chuàng)建一個三

38、元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，兩個三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘一個比例因子，顯示三元組，銷毀三元組等?；疽髮?shí)現(xiàn)創(chuàng)建一個三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，顯示三元組等基本操作。測試數(shù)據(jù)由學(xué)生任意指定。實(shí)現(xiàn)提示用結(jié)構(gòu)體封裝“三元組”的三個分量，并利用typedef對結(jié)構(gòu)體或結(jié)構(gòu)體指針重新命名。注意：如果要實(shí)現(xiàn)銷毀三元組，則應(yīng)利用typedef對結(jié)構(gòu)體指針重新命名，并使用C語言的動態(tài)分配庫函數(shù)。選作內(nèi)容實(shí)現(xiàn)兩個三元組的對應(yīng)分量相加或相減，給三元組的各分

39、量同乘一個比例因子，銷毀三元組等操作。 有理數(shù)ADT問題描述設(shè)計實(shí)現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”?；疽髮?shí)現(xiàn)有理數(shù)的加法、減法，以及求有理數(shù)的分子、分母等基本操作。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如有理數(shù)0。實(shí)現(xiàn)提示用結(jié)構(gòu)體封裝與“有理數(shù)”對應(yīng)的分子和分母。選作內(nèi)容實(shí)現(xiàn)有理數(shù)的乘法、除法運(yùn)算。復(fù)數(shù)ADT問題描述設(shè)計實(shí)現(xiàn)抽象數(shù)據(jù)類型“復(fù)數(shù)”?；疽髮?shí)現(xiàn)復(fù)數(shù)的加法、減法、乘法，以及求復(fù)數(shù)的實(shí)部、虛部等基本操作。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如復(fù)數(shù)0。實(shí)現(xiàn)提示用結(jié)構(gòu)體封裝與“復(fù)數(shù)”對應(yīng)的實(shí)部、虛部。選作內(nèi)容實(shí)現(xiàn)復(fù)數(shù)的除法運(yùn)算。實(shí)習(xí)一 線

40、性表本次實(shí)習(xí)的主要目的在于熟悉線性表的基本運(yùn)算在兩種存儲結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點(diǎn)。通過本次實(shí)習(xí)還可幫助讀者復(fù)習(xí)高級語言的使用方法。 城市鏈表問題描述將若干城市的信息，存入一個帶頭結(jié)點(diǎn)的單鏈表。結(jié)點(diǎn)中的城市信息包括：城市名，城市的位置坐標(biāo)。要求能夠利用城市名和位置坐標(biāo)進(jìn)行有關(guān)查找、插入、刪除、更新等操作?；疽螅?） 給定一個城市名，返回其位置坐標(biāo)；（2） 給定一個位置坐標(biāo)P和一個距離D，返回所有與P的距離小于等于D的城市。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。約瑟夫環(huán)問題描述約瑟夫（Joeph）問題的一種描述是：編號為1,2,n的n個人按順時針

41、方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計一個程序求出出列順序?；疽罄脝蜗蜓h(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）。實(shí)現(xiàn)提示程序運(yùn)行后首先要求用戶指定初始報數(shù)上限值，然后讀取各人的密碼。設(shè)n30。選作內(nèi)容向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。線性表的

42、逆置問題描述分別以不同存儲結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置。線性表的就地逆置就是在原表的存儲空間內(nèi)將線性表（a1,a2,a3,an）逆置為（an，an-1，a2，a1）?；疽笥庙樞虼鎯Y(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置，并將結(jié)果輸出。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空表。實(shí)現(xiàn)提示設(shè)三個連續(xù)的指針，分別指向當(dāng)前結(jié)點(diǎn)、當(dāng)前結(jié)點(diǎn)的前趨、當(dāng)前結(jié)點(diǎn)的后繼。選作內(nèi)容利用單鏈表作為存儲結(jié)構(gòu)。首先先建立線性表的帶頭結(jié)點(diǎn)的單鏈表表示形式，之后在不借助輔助結(jié)點(diǎn)空間的情況下實(shí)現(xiàn)單鏈表的逆置，并將結(jié)果輸出。長整數(shù)運(yùn)算問題描述設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運(yùn)算?；疽罄秒p項(xiàng)循環(huán)鏈表實(shí)現(xiàn)長整

43、數(shù)的存儲，每個結(jié)點(diǎn)含一個整型變量。任何整型變量的范圍是-（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”。實(shí)現(xiàn)提示（1） 每個結(jié)點(diǎn)中可以存放的最大整數(shù)為215-1=32767，

44、才能保證兩數(shù)相加不會溢出。但若這樣存，即相當(dāng)于按32768進(jìn)制數(shù)存，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過9999的非負(fù)整數(shù)，整個鏈表視為萬進(jìn)制數(shù)。（2） 可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點(diǎn)數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。選作內(nèi)容修改上述程序，使它在整型量范圍是-（2n-1）（2n-1）的計算機(jī)上都能有效地運(yùn)行。其中，n是由程序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。實(shí)習(xí)二 棧、隊列與遞歸算法設(shè)計僅僅認(rèn)識到棧和隊

45、列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在于使讀者深入了解棧和隊列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；同時還將鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計。 數(shù)制轉(zhuǎn)換問題問題描述將十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是計算機(jī)實(shí)現(xiàn)計算的基本問題，其解決方案很多，其中最簡單方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8NN div 8N mod 81348 168 416821021 2 520 2從中我們可以看出，最先產(chǎn)生的余數(shù)4是轉(zhuǎn)換結(jié)果的最低位，這正好符合棧的特性即后進(jìn)先出的特性。所以可以用順序棧來模擬這個過程?；疽髮τ阪I盤輸入的任意一個非負(fù)的十

46、進(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是屬該模式的字符序列，而+&則

47、不是。實(shí)現(xiàn)提示首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如序列1和序列2均為空串。商品貨架管理問題描述商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時，需要倒貨架，以保證生產(chǎn)日期較近的商品在較下的位置?；疽筢槍σ环N特定商品，實(shí)現(xiàn)上述管理過程。實(shí)現(xiàn)提示用棧模擬貨架和周轉(zhuǎn)空間。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空棧。括號匹配的檢驗(yàn)問題描述假設(shè)表達(dá)式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即（） ）或（ ）等為正確格式，（ ）或（均為不正確的格式。檢驗(yàn)括

48、號是否匹配的方法可用“期待的緊迫程度”這個概念來描述。例如：考慮下列的括號序列：()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ù)了， ，依次類推。

49、可見這個處理過程正好和棧的特點(diǎn)相吻合。基本要求讀入圓括號和方括號的任意序列，輸出“匹配”或“此串括號匹配不合法”。測試數(shù)據(jù) 輸入（ （），結(jié)果“匹配”輸入 （ ），結(jié)果“此串括號匹配不合法”實(shí)現(xiàn)提示設(shè)置一個棧，每讀入一個括號，若是左括號，則作為一個新的更急迫的期待壓入棧中；若是右括號，并且與當(dāng)前棧頂?shù)淖罄ㄌ栂嗥ヅ?，則將當(dāng)前棧頂?shù)淖罄ㄌ柾顺?，繼續(xù)讀下一個括號，如果讀入的右括號與當(dāng)前棧頂?shù)淖罄ㄌ柌黄ヅ?，則屬于不合法的情況。在初始和結(jié)束時，棧應(yīng)該是空的。選作內(nèi)容考慮增加大括號的情況。停車場管理問題描述設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間

50、的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費(fèi)用。試為停車場編制按上述要求進(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

51、，0）。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束?；疽笠詶ＤM停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用（在便道上停留的時間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊列以鏈表實(shí)現(xiàn)。實(shí)現(xiàn)提示需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退

52、出來的汽車，也用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項(xiàng)：汽車的牌照號碼和進(jìn)入停車場的時刻。選作內(nèi)容（1） 兩個棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？（2） 汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。（3） 汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。（4） 停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。實(shí)習(xí)三 串及其應(yīng)用本次實(shí)習(xí)的目的是熟悉串類型的實(shí)現(xiàn)方法和文

53、本模式匹配方法，熟悉一般文字處理軟件的設(shè)計方法，較復(fù)雜問題的分解求精方法，在第二次實(shí)習(xí)的基礎(chǔ)上，進(jìn)一步強(qiáng)化這樣一個觀念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在其上的操作，此外還希望起到訓(xùn)練合作能力和熟悉文件操作的目的。本次實(shí)習(xí)的難度較大。 文學(xué)研究助手問題描述文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)，稱為“文學(xué)研究助手”?；疽笥⑽男≌f存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計。測試數(shù)據(jù)以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計的詞匯集。實(shí)現(xiàn)提示設(shè)小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計每個詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的