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

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)試驗報告格式《數(shù)據(jù)結(jié)構(gòu)課程試驗》大綱

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

“數(shù)據(jù)結(jié)構(gòu)〞是計算機專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，是計算機專業(yè)的一門核心的關(guān)鍵性課程。本課程較系統(tǒng)地介紹了軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)和實現(xiàn)算法，介紹了常用的多種查找和排序技術(shù)，并做了性能分析和比較，內(nèi)容十分豐富。本課程的學習將為后續(xù)課程的學習以及軟件設(shè)計水平的提高打下良好的基礎(chǔ)。

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

（1）內(nèi)容豐富，學習量大，給學習帶來困難；

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

（3）所用到的技術(shù)多，而在此之前的各門課程中所介紹的專業(yè)性知識又不多，因而加大了學習難度；（4）隱含在各部分的技術(shù)和方法豐富，也是學習的重點和難點。

根據(jù)《數(shù)據(jù)結(jié)構(gòu)課程》課程本身的技術(shù)特性，設(shè)置《數(shù)據(jù)結(jié)構(gòu)課程試驗》實踐環(huán)節(jié)十分重要。通過試驗實踐內(nèi)容的訓練，突出構(gòu)造性思維訓練的特征,目的是提高學生組織數(shù)據(jù)及編寫大型程序的能力。試驗學時為18。

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

不少學生在解答習題特別是算法設(shè)計題時，覺得無從下手，做起來特別吃力。試驗中的內(nèi)容和教科書的內(nèi)容是密切相關(guān)的，解決題目要求所需的各種技術(shù)大多可從教科書中找到，只不過其出現(xiàn)的形式呈多樣化，因此需要細心體會，在反復實踐的過程中才能把握。

為了幫助學生更好地學習本課程，理解和把握算法設(shè)計所需的技術(shù)，為整個專業(yè)學習打好基礎(chǔ)，要求運用所學知識，上機解決一些典型問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓練，使學生深刻理解、穩(wěn)固把握所用到的一些技術(shù)。數(shù)據(jù)結(jié)構(gòu)中稍微繁雜一些的算法設(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學時，要求完成以下六個題目：實習一約瑟夫環(huán)問題（2學時）

用循環(huán)鏈表實現(xiàn)約瑟夫環(huán)問題，熟悉鏈表結(jié)構(gòu)的使用。實習二停車場管理（4學時）

利用棧和隊列模擬停車場管理，學習利用棧和隊列解決實際問題。實習三二叉樹基本操作（3學時）

創(chuàng)立、遍歷、插入、刪除、顯示二叉樹，通過二叉樹的基本操作，把握樹結(jié)構(gòu)的處理方法。實習四圖的基本操作（3學時）

分別用鄰接矩陣和鄰接表實現(xiàn)以下操作：圖的創(chuàng)立、遍歷、插入、刪除、最短路徑。熟悉圖的常用存儲結(jié)構(gòu)和基本操作。實習五哈希表設(shè)計（3學時）

給定30個人的姓名，用除留余數(shù)法構(gòu)造哈希函數(shù)，用線性探測再散列法處理沖突，構(gòu)造哈希表，把握哈希表的設(shè)計與使用。實習六常用排序算法的對比分析（3學時）

分別實現(xiàn)直接插入排序、冒泡排序、簡單項選擇擇排序、希爾排序、快速排序、堆排序，并隨機生成30個數(shù)，比較各算法的時、空性能和穩(wěn)定性。把握常用排序算法的特點，以便根據(jù)實際狀況選擇使用。

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

采用上機狀況、程序質(zhì)量、實習報告相結(jié)合的形式，總分值為100分。1．上機狀況（30%）

包括出勤狀況、調(diào)試表現(xiàn)、是否上網(wǎng)、玩游戲。2．程序質(zhì)量（50%）3．實習報告（20%）

實習一線性表

本次實習的主要目的在于熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)上的實現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點。通過本次實習還可幫助讀者復習高級語言的使用方法。

約瑟夫環(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è)n≤30。[選作內(nèi)容]

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

長整數(shù)運算

[問題描述]

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

利用雙項循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整型變量。任何整型變量的范圍是-（215-1）~（215-1）。輸入和輸出形式：按中國對于長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。[測試數(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ù)相加不會溢出。但若這樣存，即相當于按32768進制數(shù)存，在十進制數(shù)與32768進制數(shù)之間的轉(zhuǎn)換十分不便利。故可以在每個結(jié)點中僅存十進制數(shù)的4位，即不超過9999的非負整數(shù)，整個鏈表視為萬進制數(shù)。

（2）可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。[選作內(nèi)容]

修改上述程序，使它在整型量范圍是-（2n-1）~（2n-1）的計算機上都能有效地運行。其中，n是由程序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。

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

僅僅認識到棧和隊列是兩種特別的線性表是遠遠不夠的，本次實習的目的在于使讀者深入了解棧和隊列的特征，以便在實際問題背景下靈活運用它們；同時還將穩(wěn)定這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較繁雜問題的遞歸算法設(shè)計。

停車場管理

[問題描述]

設(shè)停車場內(nèi)只有一個的停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后開入的車輛必需先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必需按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。[測試數(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’表示離去，‘E’表示輸入終止。[基本要求]

以棧模擬停車場，以隊列模擬車場外的便道，依照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達〞或“離去〞信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。[實現(xiàn)提醒]

需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。[選作內(nèi)容]

（1）兩個棧共享空間，思考應(yīng)開拓數(shù)組的空間是多少？

（2）汽車可有不同種類，則它們的占地面積不同，收費標準也不同，如1輛客車和1.5輛小汽車的占地面積一致，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。

（3）汽車可以直接從便道上開走，此時派在它前面的汽車要先開走讓路，然后再依次排到隊尾。（4）停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。

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

本次實習的目的是熟悉串類型的實現(xiàn)方法和文本模式匹配方法，熟悉一般文字處理軟件的設(shè)計方法，較繁雜問題的分解求精方法，在其次次實習的基礎(chǔ)上，進一步加強這樣一個觀念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在其上的操作，此外還希望起到訓練合作能力和熟悉文件操作的目的。本次實習的難度較大。

文學研究助手

[問題描述]

文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學研究助手〞。[基本要求]

英文小說存于一個文本文件中。待統(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)了不止一次，不必存多個一致的行號。

假使讀者希望達到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價形式，再將它推廣到多個模式的情形。[選作內(nèi)容]

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

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

（3）假設(shè)小說中的每個單詞或者從行首開始，或者前置以一個空格符。利用單詞匹配特點另寫一個高效的統(tǒng)計程序，與KMP算法統(tǒng)計程序進行效率比較。

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

簡單行編輯程序

[問題描述]

文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。

被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟，也不總能實現(xiàn)。一種解決方法是逐段地編輯。任何時刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)。試依照這種方法實現(xiàn)一個簡單的行編輯程序。設(shè)文件每行不超過320個字符，很少超過80字符。[基本要求]

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

（1）行插入。格式：i將插入活區(qū)中第行之后（2）行刪除。格式：d[□]

刪除活區(qū)中第行（到第行）。兩種格式的例子是：“d10↙〞和“d10□14↙〞（3）活區(qū)切換。格式：n

將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。（4）活區(qū)顯示。格式：p

逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是否繼續(xù)顯示以后各頁（假使存在）。印出的每一行要前置以行號和一個空格符，行號固定占4位，增量為1。

各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第一行行號減1，表示插入當前屏幕中第一行之前，否則命令參數(shù)非法。[實現(xiàn)提醒]

（1）設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來描述。考慮到文本文件行長尋常為正態(tài)分布，且峰值在60到70之間，用320×activemaxlen大小的字符數(shù)組實現(xiàn)存儲將造成大量浪費?？梢砸詷藴市袎K為單位為各行分派存儲，每個標準行塊含81個字符。這些行塊可以組成一個數(shù)組，也可以利用動態(tài)鏈表連接起來。一行文字可能占多個行塊。行尾可用一個特別的ASCII字符（如(012)8）標識。此外，還應(yīng)記住活區(qū)起始行號。行插入將引起隨后各行行號的順序下推。

（2）初始化過程包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能一致。然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlen-x。x的值可以自定，例如20。（3）在執(zhí)行行插入命令的過程中，每接收到一行時到要檢查活區(qū)大小是否已達activemaxlen。假使是，則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen，應(yīng)將插入點之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點為第一行之前，則只得將新插入的這一行輸出。

（4）若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最終幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著終止編輯或開始編輯另一個文件。（5）可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示。[選作內(nèi)容]

（1）對于命令格式非法等一切錯誤作嚴格檢查和適當處理。

（2）參與更繁雜的編輯操作，如對某行進行串替換；在活區(qū)內(nèi)進行模式匹配等，格式可以為S@@和m。

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

樹和圖是兩種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點。它們的特點在于非線性。廣義表本質(zhì)上是樹結(jié)構(gòu)；稀疏矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu)，故也把它們歸在這次實習中。本章實習繼續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計觀點，但根據(jù)這兩種結(jié)構(gòu)的非線性特點，將操作進一步集中在遍歷操作上，由于遍歷操作是其他眾多操作的基礎(chǔ)。遍歷規(guī)律的（或符號形式的）結(jié)構(gòu)，訪問動作可是任何操作。本次實習還希望達到熟悉各種存儲結(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)先生成樹，再按凹入表或樹形打印生成樹。

實習五查找和排序

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

哈希表設(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)部排序算法的時間繁雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大約執(zhí)行時間。試通過隨機的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。[基本要求]

（1）對以下10種常用的內(nèi)部排序算法進行比較：直接插入排序；折半折入排序；二路插入排序；希爾排序；起泡排序；快速排序；簡單項選擇擇排序；堆排序；歸并排序；基數(shù)排序。

（2）待排序表的表長不少于100；其中的數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標為有關(guān)鍵字參與的比較次數(shù)和關(guān)鍵字移動次數(shù)（關(guān)鍵字交換計為3次移動）。[測試數(shù)據(jù)]

由隨機產(chǎn)生器決定。[實現(xiàn)提醒]

主要工作是設(shè)法在程序中適當?shù)牡胤讲迦胗嫈?shù)操作。程序還可以包括計算幾組數(shù)據(jù)得出結(jié)果波動大小的解釋。注意分塊調(diào)試的方法。[選作內(nèi)容]

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

試驗指導書概述

“數(shù)據(jù)結(jié)構(gòu)〞是計算機專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，是一門關(guān)鍵性核心課程。本課程系統(tǒng)地介紹了軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)和實現(xiàn)算法，介紹了多種常用的查找和排序技術(shù)，并對其進行了性能分析和比較，內(nèi)容十分豐富。本課程的學習將為后續(xù)課程的學習以及軟件設(shè)計水平的提高打下良好的基礎(chǔ)。

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

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

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

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

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

由于數(shù)據(jù)結(jié)構(gòu)課程的技術(shù)性與實踐性，《數(shù)據(jù)結(jié)構(gòu)課程試驗》的設(shè)置十分必要。為了幫助學生更好地學習本課程，理解和把握算法設(shè)計所需的技術(shù)，為整個專業(yè)學習打好基礎(chǔ)，要求運用所學知識，上機解決一些典型問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓練，使學生深刻理解、穩(wěn)固把握所用到的一些技術(shù)。數(shù)據(jù)結(jié)構(gòu)中稍微繁雜一些的算法設(shè)計中可能同時要用到多種技術(shù)和方法，如算法設(shè)計的構(gòu)思方法，動態(tài)鏈表，算法的編碼，遞歸技術(shù)，與特定問題相關(guān)的技術(shù)等，要求重點把握線性鏈表、二叉樹和樹、圖結(jié)構(gòu)、數(shù)組結(jié)

構(gòu)相關(guān)算法的設(shè)計。在把握基本算法的基礎(chǔ)上，把握分析、解決實際問題的能力。通過試驗實踐內(nèi)容的訓練，突出構(gòu)造性思維訓練的特征,提高學生組織數(shù)據(jù)及編寫大型程序的能力。

上機實習是對學生的一種全面綜合訓練，是與課堂聽講、自學和練習相輔相成的必不可少的一個教學環(huán)節(jié)。較大的實習題比平日的習題要繁雜得多，也更接近實際。實習著眼于原理與應(yīng)用的結(jié)合點，使學生學會如何把書上學到的知識用于解決實際問題，培養(yǎng)軟件工作所需要的動手能力。實習還能使書上的知識變“活〞，達到深化理解和靈活把握教學內(nèi)容的目的。平日的練習較偏重于如何編寫功能單一的“小〞算法，而實習題是軟件設(shè)計的綜合訓練，包括問題分析，總體結(jié)構(gòu)設(shè)計，用戶界面設(shè)計，程序設(shè)計基本技能和技巧，多人合作，以至一整套軟件工作規(guī)范的訓練和科學作風的培養(yǎng)。此外，還有很重要的一點是：機器是比任何教師都嚴格的檢查者。

為了達到上述目的，本書安排了6個主實習單元，其中實習0的訓練重點是抽象數(shù)據(jù)類型的定義與實現(xiàn)方法，其它各單元的訓練重點在于基本的數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法。各實習單元與教科書的各章只具有粗略的對應(yīng)關(guān)系，一個實習題可能涉及幾部分教學內(nèi)容。在每個實習單元中安排有難度不等的2—5個實習題，每人可以從中選做一個實習題。建議選做難度略高于自己所做過的最難題目的難度，切忌過分追求難題。較大的題目適合于多人合作。

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

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

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

測試數(shù)據(jù)部分旨在為檢查學生上機作業(yè)提供便利，在完成實習題時應(yīng)自己設(shè)計完整和嚴格的測試方案，當數(shù)據(jù)輸入量較大時，提倡以文件形式向程序提供輸入數(shù)據(jù)；

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

選做內(nèi)容向那些尚有余力的讀者提出了更嚴峻的挑戰(zhàn)，同時也能開拓其他讀者的思路，在完成基本要求時就力求避免就事論事的不良思想方法，盡可能尋求具有普遍意義的解法，使得程序結(jié)構(gòu)合理，簡單修改擴展。

書中題目設(shè)計得比較詳細，給出了問題說明和問題分解求精的范例，使讀者在無形中學會模仿，它起到把讀者的思路引上正軌的作用，避免不良結(jié)構(gòu)程序和壞習慣，同時也傳授了系統(tǒng)劃分方法和程序設(shè)計的一些具體技術(shù)，保證明現(xiàn)預定的訓練意圖，使某些難點和重點不會被繞過去，而且也便于教學檢查。題目設(shè)策略略是：一方面使其難度和工作量都較大，另—方面給讀者提供的輔助和可以模仿的部分也較多。當然還應(yīng)指出的是，提醒的實現(xiàn)方法未必是最好的，讀者不應(yīng)拘泥于此，而應(yīng)爭取找出更好的方法和結(jié)構(gòu)。在實現(xiàn)的時候應(yīng)注意，要盡量減少依靠于具體機器計算環(huán)境的用法，若使用，也應(yīng)在解釋中指出。這樣得出的程序易于在不同機器上運行，有好的可移植性。C語言是結(jié)構(gòu)化程序設(shè)計語言，具有遞歸能力，可移植性也較好，是特別推薦的實現(xiàn)語言。

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

花2個小時的機上時間只找出一個錯誤，甚至一無所獲的狀況是常見的。其原因在于，好多人只認識到找錯誤，而沒有認識到努力預先避免錯誤的重要性，也不知道應(yīng)當如何努力。實際上，結(jié)構(gòu)不好、思路和概念不清的程序可能是根本無法調(diào)試正確的。嚴格依照實習步驟規(guī)范進行實習，不但能有效地避免上述種種問題，更重要的是有利于培養(yǎng)軟件工不可缺少的科學工作方法和作風。

在附錄中提供了一個完整的實習報告例如，在起到實習報告規(guī)格范例作用的同時，還隱含地提供了好多有益的東西，譬如基于數(shù)據(jù)類型的系統(tǒng)劃分方法以及所提倡的程序設(shè)計風格等等。計算機學科在不斷發(fā)展，可以使用的語言工具越來越豐富，在本書中的實習例如是應(yīng)用面向過程的語言進行設(shè)計和編程，同樣的實習題，也可以用面向?qū)ο蟮恼Z言來實現(xiàn)。希望書中的實習報告例如能起到一個拋磚引玉的作用，以引來讀者更多更優(yōu)良的設(shè)計范例。

實習步驟

隨著計算機性能的提高，它所面臨的軟件開發(fā)的繁雜度也日趨增加，因此軟件開發(fā)需要系統(tǒng)的方法。一種常用的軟件開發(fā)方法，是將軟件開發(fā)過程分為分析、設(shè)計、實現(xiàn)和維護四個階段。雖然數(shù)據(jù)結(jié)構(gòu)課程中的實習題的繁雜度遠不如實際中真正的軟件系統(tǒng)，但為了培養(yǎng)一個軟件工所應(yīng)具備的科學工作的方法和作風，我們制訂了如下所述完成實習的5個步驟：

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

尋常，實習題目的陳述比較簡單，或者說有模棱兩可的含義。因此，在進行設(shè)計之前，首先應(yīng)當充分地分析和理解問題，明確問題要求做什么，限制條件是什么。注意：本步驟強調(diào)的是做什么，而不是怎么做。對問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是對所需完成的任務(wù)作出明確的回復。例如：輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值的范圍及輸出的形式；若是會話式的輸入，則終止標志是什么，是否接受非法的輸入，對非法輸入的回復方式是什么等等。這一步還應(yīng)當為調(diào)試程序準備好測試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非法形式輸入的數(shù)據(jù)。

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

在設(shè)計這一步驟中需分規(guī)律設(shè)計和詳細設(shè)計兩步實現(xiàn)。規(guī)律設(shè)計指的是，對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并依照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。詳細設(shè)計則為定義相應(yīng)的存儲結(jié)構(gòu)并寫出各過程和函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)明了、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。作為規(guī)律設(shè)計的結(jié)果，應(yīng)寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的規(guī)格說明），各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。詳細設(shè)汁的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作的規(guī)格說明作出進一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，依照算法書寫規(guī)范用類C語言寫出過程或函數(shù)形式的算法框架。在求精的過程中，應(yīng)盡量避免陷入語言細節(jié)，不必過早表述輔助數(shù)據(jù)結(jié)構(gòu)和局部變量。

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

編碼是把詳細設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序。如何編寫程序才能較快地完成調(diào)試是特別要注意的問題。程序的每行不要超過60個字符。每個過程（函數(shù)）體一般不要超過40行，最長不得超過60行，否則應(yīng)當分割成較小的過程（函數(shù)）。要控制if語句連續(xù)嵌套的深度，分支過多時應(yīng)考慮使用switch語句。對函數(shù)功能和重要變量進行解釋。一定要按格式書寫程序，分清每條語句的層次，對齊括號，這樣便于發(fā)現(xiàn)語法錯誤。

在上機之前，應(yīng)當用筆在紙上寫出詳細的程序編碼，并做認真地靜態(tài)檢查。多數(shù)初學者在編好程序后處于以下兩種狀態(tài)之一：一種是對自己的“精心作品〞的正確性確信不疑；另一種是認為上機前的任務(wù)已經(jīng)完成，糾查錯誤是上機的工作。這兩種態(tài)度是極為有害的。對一般的程序設(shè)計者而言，當編寫的程序長度超過50行時，尋常會含有語法錯誤或規(guī)律錯誤。上機動態(tài)調(diào)試決不能代替靜態(tài)檢查，否則調(diào)試效率將是極低的。靜態(tài)檢查主要有兩種方法，一是用一組測試數(shù)據(jù)手工執(zhí)行程序（尋常應(yīng)先檢查單個模塊）；二是通過閱讀或給別人講解自己的程序而深入全面地理解程序規(guī)律，在這個過程中再參與一些注解。

4．上機準備和上機調(diào)試

上機準備包括以下幾個方面：

（1）熟悉C語言用戶手冊或程序設(shè)計指導書。（2）注意TurboC、VC與標準C語言之間的微弱區(qū)別。

（3）熟悉機器的操作系統(tǒng)和語言集成環(huán)境的用戶手冊，特別是最常用的命令操作，以便順利進行上機的基本活動。

（4）把握調(diào)試工具，考慮調(diào)試方案，設(shè)計測試數(shù)據(jù)并手工得出正確結(jié)果?！澳サ恫徽`砍柴工〞。學生應(yīng)當熟練運用高級語言的程序調(diào)試器DEBUG調(diào)試程序。

上機調(diào)試程序時要帶一本高級語言教材或手冊。調(diào)試最好分模塊進行，自底向上，即先調(diào)試低層過程或函數(shù)。必要時可以另寫一個調(diào)用驅(qū)動程序。這種表面上麻煩的工作實際上可以大大降低調(diào)試所面臨的繁雜性，提高調(diào)試工作效率。

在調(diào)試過程中可以不斷借助DEBUG的各種功能，提高調(diào)試效率。調(diào)試中遇到的各種異常現(xiàn)象往往是預料不到的，此時不應(yīng)“苦思冥想〞，而應(yīng)借助系統(tǒng)提供的調(diào)試工具確定錯誤。調(diào)試正確后，認真整理源程序及其解釋，印出帶有完整解釋的且格式良好的源程序清單和結(jié)果。

5．總結(jié)和整理實習報告

實習報告規(guī)范

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

1．需求分析

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

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

(2)輸出的形式；

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

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

2．概要設(shè)計

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

3．詳細設(shè)計

實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽碼算法；對主程序和其他模塊也都需要寫出偽碼算法(偽碼算法達到的詳細程度建議為：依照偽碼算法可以在計算機鍵盤直接輸入高級程序設(shè)計語言程序)；畫出函數(shù)和過程的調(diào)用關(guān)系圖。

4．調(diào)試分析

內(nèi)容包括：

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

b．算法的時空分析(包括基本操作和其他算法的時間繁雜度和空間繁雜度的分析)和

改進設(shè)想；

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

5．用戶使用說明

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

6．測試結(jié)果

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

7．附錄

帶解釋的源程序。假使提交源程序軟盤，可以只列出程序文件名的清單。

在以下各實習單元中都提供了實習報告實例。值得注意的是，實習報告的各種文檔資料，如：上述中的前三部分要在程序開發(fā)的過程中逐漸充實形成，而不是最終補寫(當然可以也應(yīng)當最終用試驗報告紙謄清或打印)。

實習題目

實習○抽象數(shù)據(jù)類型

三元組ADT

[問題描述]

設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“三元組〞。每個三元組由任意三個實數(shù)的序列構(gòu)成，基本操作包括：創(chuàng)立一個三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，兩個三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘一個比例因子，顯示三元組，銷毀三元組等。

[基本要求]

實現(xiàn)創(chuàng)立一個三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，顯示三元組等基本操作。

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

由學生任意指定。

[實現(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ù)]

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

[實現(xiàn)提醒]

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

[選作內(nèi)容]

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

復數(shù)ADT

[問題描述]

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

[基本要求]

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

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

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

[實現(xiàn)提醒]

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

[選作內(nèi)容]

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

實習一線性表

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

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

城市鏈表

[問題描述]

將若干城市的信息，存入一個帶頭結(jié)點的單鏈表。結(jié)點中的城市信息包括：城市名，城市的位置坐標。要求能夠利用城市名和位置坐標進行有關(guān)查找、插入、刪除、更新等操作。

[基本要求]

（1）給定一個城市名，返回其位置坐標；

（2）給定一個位置坐標P和一個距離D，返回所有與P的距離小于等于D的城市。

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

由學生依據(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ù)]

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

[實現(xiàn)提醒]

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

[選作內(nèi)容]

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

線性表的逆置

[問題描述]

分別以不同存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置。線性表的就地逆置就是在原表的存儲空間內(nèi)將線性表（a1,a2,a3,?,an）逆置為（an，an-1，?，a2，a1）。

[基本要求]

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

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

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

[實現(xiàn)提醒]

設(shè)三個連續(xù)的指針，分別指向當前結(jié)點、當前結(jié)點的前趨、當前結(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ù)的表示習慣，每四位一組，組間用逗號隔開。

[測試數(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ù)相加不會溢出。但若這樣存，即相當于按32768進制數(shù)存，在十進制數(shù)與32768進制數(shù)之間的轉(zhuǎn)換十分不便利。故可以在每個結(jié)點中僅存十進制數(shù)的4位，即不超過9999的非負整數(shù)，整個鏈表視為萬進制數(shù)。

（2）可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。

[選作內(nèi)容]

修改上述程序，使它在整型量范圍是-（2n-1）~（2n-1）的計算機上都能有效地運行。其中，n是由程序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。

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

僅僅認識到棧和隊列是兩種特別的線性表是遠遠不夠的，本次實習的目的在于使讀者深入了解棧和隊列

的特征，以便在實際問題背景下靈活運用它們；同時還將穩(wěn)定這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較繁雜問題的遞歸算法設(shè)計。

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

[問題描述]

將十進制數(shù)N和其它d進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方案好多，其中最簡單方法基于以下原理：即除d取余法。例如：（1348）10=（2504）8NNdiv8Nmod813481684168210

2125202

從中我們可以看出，最先產(chǎn)生的余數(shù)4是轉(zhuǎn)換結(jié)果的最低位，這正好符合棧的特性即后進先出的特性。所以可以用順序棧來模擬這個過程。

[基本要求]

對于鍵盤輸入的任意一個非負的十進制整數(shù)，打印輸出與其等值的八進制數(shù)。由于上述的計算過程是從低位到高位順序產(chǎn)生的八進制數(shù)的各個數(shù)位，而打印輸出，一般來說應(yīng)從高位到地位進行，恰好和計算過程相反。因此可以先將計算過程中得到的八進制數(shù)的各位進棧，待相對應(yīng)的八進制數(shù)的各位均產(chǎn)生以后，再使其按順序出棧，并打印輸出。即得到了與輸入的十進制數(shù)相對應(yīng)的八進制數(shù)。

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

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

回文判斷

[問題描述]

試寫一個算法，判斷依次讀入的一個以@為終止符的字母序列，是否為形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘１+３&３－１’則不是。

[實現(xiàn)提醒]

首先，序列1進棧，然后序列1出棧并與序列2比較。

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

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

商品貨架管理

[問題描述]

商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時，需要倒貨架，以保證生產(chǎn)日期較近的商品在較下的位置。

[基本要求]

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

[實現(xiàn)提醒]

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

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

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

括號匹配的檢驗

[問題描述]

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

[（[][]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗括號是否匹配的方法可用“期待的緊迫程度〞這個概念來描述。例如：考慮以下的括號序列：[([][])]12345678

當計算機接受了第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è)置一個棧，每讀入一個括號，若是左括號，則作為一個新的更急迫的期待壓入棧中；若是右括號，并且與當前棧頂?shù)淖罄ㄌ栂嗥ヅ?，則將當前棧頂?shù)淖罄ㄌ柾顺觯^續(xù)讀下一個括號，假使讀入的右括號與當前棧頂?shù)淖罄ㄌ柌黄ヅ洌瑒t屬于不合法的狀況。在初始和終止時，棧應(yīng)當是空的。

[選作內(nèi)容]

考慮增加大括號的狀況。

停車場管理

[問題描述]

設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后開入的車輛必需先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必需按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。

[測試數(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ù)項：汽車“到達〞或“離去〞信息、汽車牌照號碼及到達或離去的時刻，其中，‘A’表示到達；‘D’表示離去，‘E’表示輸入終止。

[基本要求]

以棧模擬停車場，以隊列模擬車場外的便道，依照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達〞或“離去〞信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。

[實現(xiàn)提醒]

需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。

[選作內(nèi)容]

（1）兩個棧共享空間，思考應(yīng)開拓數(shù)組的空間是多少？

（2）汽車可有不同種類，則它們的占地面積不同，收費標準也不同，如1輛客車和1.5輛小汽車的占地面積一致，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。

（3）汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。（4）停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。

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

本次實習的目的是熟悉串類型的實現(xiàn)方法和文本模式匹配方法，熟悉一般文字處理軟件的設(shè)計方法，較繁雜問題的分解求精方法，在其次次實習的基礎(chǔ)上，進一步加強這樣一個觀念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在其上的操作，此外還希望起到訓練合作能力和熟悉文件操作的目的。本次實習的難度較大。

文學研究助手

[問題描述]

文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學研究助手〞。

[基本要求]

英文小說存于一個文本文件中。待統(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)了不止一次，不必存多個一致的行號。

假使讀者希望達到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價形式，再將它推廣到多個模式的情形。

[選作內(nèi)容]

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

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

（3）假設(shè)小說中的每個單詞或者從行首開始，或者前置以一個空格符。利用單詞匹配特點另寫一個高效的統(tǒng)計程序，與KMP算法統(tǒng)計程序進行效率比較。

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

簡單行編輯程序

[問題描述]

文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。

被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟，也不總能實現(xiàn)。一種解決方法是逐段地編輯。任何時刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)。試依照這種方法實現(xiàn)一個簡單的行編輯程序。設(shè)文件每行不超過320個字符，很少超過80字符。

[基本要求]

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

（1）行插入。格式：i將插入活區(qū)中第行之后（2）行刪除。格式：d[□]

刪除活區(qū)中第行（到第行）。兩種格式的例子是：“d10↙〞和“d10□14↙〞（3）活區(qū)切換。格式：n

將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。（4）活區(qū)顯示。格式：p

逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是否繼續(xù)顯示以后各頁（假使存在）。印出的每一行要前置以行號和一個空格符，行號固定占4位，增量為1。

各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第一行行號減1，表示插入當前屏幕中第一行之前，否則命令參數(shù)非法。

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

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

[實現(xiàn)提醒]

（1）設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來描述?？紤]到文本文件行長尋常為正態(tài)分布，且峰值在60到70之間，用320×activemaxlen大小的字符數(shù)組實現(xiàn)存儲將造成大量浪費。可以以標準行塊為單位為各行分派存儲，每個標準行塊含81個字符。這些行塊可以組成一個數(shù)組，也可以利用動態(tài)鏈表連

接起來。一行文字可能占多個行塊。行尾可用一個特別的ASCII字符（如(012)8）標識。此外，還應(yīng)記住活區(qū)起始行號。行插入將引起隨后各行行號的順序下推。

（2）初始化過程包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能一致。然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlen-x。x的值可以自定，例如20。（3）在執(zhí)行行插入命令的過程中，每接收到一行時到要檢查活區(qū)大小是否已達activemaxlen。假使是，則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen，應(yīng)將插入點之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點為第一行之前，則只得將新插入的這一行輸出。

（4）若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最終幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著終止編輯或開始編輯另一個文件。（5）可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示。

[選作內(nèi)容]

（1）對于命令格式非法等一切錯誤作嚴格檢查和適當處理。

（2）參與更繁雜的編輯操作，如對某行進行串替換；在活區(qū)內(nèi)進行模式匹配等，格式可以為S@@和m。

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

樹和圖是兩種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點。它們的特點在于非線性。廣義表本質(zhì)上是樹結(jié)構(gòu)；稀疏矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu)，故也把它們歸在這次實習中。本章實習繼續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計觀點，但根據(jù)這兩種結(jié)構(gòu)的非線性特點，將操作進一步集中在遍歷操作上，由于遍歷操作是其他眾多操作的基礎(chǔ)。遍歷規(guī)律的（或符號形式的）結(jié)構(gòu)，訪問動作可是任何操作。本次實習還希望達到熟悉各種存儲結(jié)構(gòu)的特征，以及如何應(yīng)用樹和圖結(jié)構(gòu)解決具體問題（即原理與應(yīng)用的結(jié)合）等目的。

二叉樹的建立與遍歷

[問題描述]

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

[基本要求]

從鍵盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），并采用遞歸算法對其進行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出。

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

ABCффDEфGффFффф（其中ф表示空格字符）則輸出結(jié)果為先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA

[選作內(nèi)容]

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

1）為了實現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：ADTLinkList{

數(shù)據(jù)對象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R={|ai,ai+1∈D}基本操作：InitLinkList(

structnode*next;}Node,*LinkListl;2)單鏈表的基本操作

為了便利，在單鏈表中設(shè)頭結(jié)點，其data域沒有意義。

boolInitLinkList(LinkList&L)（偽碼算法）

voidDispLinkList(LinkListL)（偽碼算法）voidmenu()（偽碼算法）

boolInsLinkList(LinkList&L,intpos,inte)（偽碼算法）

boolDelLinkList(LinkList&L,intpos,int&e)（偽碼算法）

intLocLinkList(LinkListL,inte)（偽碼算法）3)其他模塊偽碼算法

5．調(diào)試分析

(略)

6．使用說明

程序名為LinkList.exe，運行環(huán)境為DOS。程序執(zhí)行后顯示========================0EXIT1INSERT2DELETE3LOCATE

=======================SELECT:

在select后輸入數(shù)字選擇執(zhí)行不同的功能。要求首先輸入足夠多的插入元素，才可以進行其他的操作。每執(zhí)行一次功能，就會顯示執(zhí)行的結(jié)果（正確或錯誤）以及執(zhí)行后單鏈表的內(nèi)容。選擇0：退出程序

選擇1：顯示“INSERTpos,e=〞，

要求輸入要插入的位置和元素的值（都是整數(shù)）。選擇2：顯示“DELETEpos=〞，

要求輸入要刪除元素的位置，執(zhí)行成功后返回元素的值。選擇3：顯示“LOCATEe=〞，

要求輸入要查找元素的值，執(zhí)行成功后返回元素在表中的位置

7．測試結(jié)果

1）建立單鏈表：

?選擇1，分別輸入（0，11），（0，12），（0，13），（0，14）（0，15）。得到單鏈表（15，14，13，12，11）2）插入：

?選擇1輸入（1，100），得到單鏈表（15，100，14，13，12，11）?選擇1輸入（-1，2），顯示輸入錯誤?選擇1輸入（7，2），顯示輸入錯誤

?選擇1輸入（6，2），得到單鏈表（15，100，14，13，12，11，2）3）刪除：

?選擇2，輸入1。返回e=100，得到單鏈表（15，14，13，12，11，2）?選擇2，輸入0。返回e=15，得到單鏈表（14，13，12，11，2）?選擇2，輸入4。返回e=2，得到單鏈表（14，13，12，11）?選擇2，輸入5。返回輸入錯誤4）查找

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

[問題描述]

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

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

由學生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空二叉樹。[實現(xiàn)提醒]

（1）利用RDL遍歷方法；

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

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

[問題描述]

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

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

由學生依據(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ù)]

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

[實現(xiàn)提醒]

設(shè)圖的結(jié)點不超過30個，每個結(jié)點用一個編號表示（假使一個圖有n個結(jié)點，則它們的編號分別為1,2,?,n）。通過輸入圖的全部邊輸入一個圖，每