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

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

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

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

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

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

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

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

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

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

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

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

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

課程試驗(yàn)共18學(xué)時(shí)，要求完成以下六個(gè)題目：實(shí)習(xí)一約瑟夫環(huán)問(wèn)題（2學(xué)時(shí)）

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

利用棧和隊(duì)列模擬停車場(chǎng)管理，學(xué)習(xí)利用棧和隊(duì)列解決實(shí)際問(wèn)題。實(shí)習(xí)三二叉樹(shù)基本操作（3學(xué)時(shí)）

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

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

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

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

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

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

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

實(shí)習(xí)一線性表

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

約瑟夫環(huán)

[問(wèn)題描述]

約瑟夫（Joeph）問(wèn)題的一種描述是：編號(hào)為1,2,?,n的n個(gè)人按順時(shí)針?lè)较驀蝗Γ咳顺钟幸粋€(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)中止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较蛏系南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。[基本要求]

利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，依照出列的順序印出各人的編號(hào)。[測(cè)試數(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)行后首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼。設(shè)n≤30。[選作內(nèi)容]

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

長(zhǎng)整數(shù)運(yùn)算

[問(wèn)題描述]

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

利用雙項(xiàng)循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量。任何整型變量的范圍是-（215-1）~（215-1）。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。[測(cè)試數(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）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為215-1=32767，才能保證兩數(shù)相加不會(huì)溢出。但若這樣存，即相當(dāng)于按32768進(jìn)制數(shù)存，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不便利。故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表視為萬(wàn)進(jìn)制數(shù)。

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

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

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

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

停車場(chǎng)管理

[問(wèn)題描述]

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

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

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

（1）兩個(gè)棧共享空間，思考應(yīng)開(kāi)拓?cái)?shù)組的空間是多少？

（2）汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和1.5輛小汽車的占地面積一致，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。

（3）汽車可以直接從便道上開(kāi)走，此時(shí)派在它前面的汽車要先開(kāi)走讓路，然后再依次排到隊(duì)尾。（4）停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場(chǎng)的車低，請(qǐng)思考如何修改結(jié)構(gòu)以滿足這種要求。

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

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

文學(xué)研究助手

[問(wèn)題描述]

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

英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必需在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。[測(cè)試數(shù)據(jù)]

以你的源程序模擬英文小說(shuō)，程序語(yǔ)言保存字集作為待統(tǒng)計(jì)的詞匯集。[實(shí)現(xiàn)提醒]

設(shè)小說(shuō)中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次，不必存多個(gè)一致的行號(hào)。

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

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

（2）整個(gè)統(tǒng)計(jì)過(guò)程中只對(duì)小說(shuō)文字掃描一遍以提高效率。

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

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

簡(jiǎn)單行編輯程序

[問(wèn)題描述]

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

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

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

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

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

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

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

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

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

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

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

（1）對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。

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

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

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

圖遍歷的演示

[問(wèn)題描述]

好多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫(xiě)一個(gè)程序，演示連通的無(wú)向圖上行邊全部結(jié)點(diǎn)的操作。[基本要求]

以鄰接多重表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列和相應(yīng)生成樹(shù)的邊集。[實(shí)現(xiàn)提醒]

設(shè)圖的結(jié)點(diǎn)不超過(guò)30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示（假使一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號(hào)分別為1,2,?,n）。通過(guò)輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊的輸入順序作出某種限制。注意，生成樹(shù)的邊是有向邊，端點(diǎn)順序不能顛倒。[選作內(nèi)容]

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

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

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

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

哈希表設(shè)計(jì)

[問(wèn)題描述]

針對(duì)某個(gè)集體中人名設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，并完成相應(yīng)的建表和查表程序。[基本要求]

假設(shè)人名為中國(guó)人姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測(cè)再散列法或鏈地址法處理沖突。[測(cè)試數(shù)據(jù)]

取讀者周邊較熟悉的30個(gè)人名。[選作內(nèi)容]

（1）從教科書(shū)上介紹的集中哈希函數(shù)構(gòu)造方法中選出適用者并設(shè)計(jì)幾個(gè)不同的哈希函數(shù)，比較他們的地址沖突率（可以用更大的名字集合作試驗(yàn)）。

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

（3）在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考察平均查找長(zhǎng)度的變化和造好的哈希表中關(guān)鍵字的聚集性。

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

[問(wèn)題描述]

各種內(nèi)部排序算法的時(shí)間繁雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大約執(zhí)行時(shí)間。試通過(guò)隨機(jī)的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。[基本要求]

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

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

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

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

對(duì)不同的輸入表長(zhǎng)做試驗(yàn)，觀測(cè)檢查兩個(gè)指標(biāo)相關(guān)于表長(zhǎng)的變化關(guān)系。還可以對(duì)穩(wěn)定性做驗(yàn)證。

試驗(yàn)指導(dǎo)書(shū)概述

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

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

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

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

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

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

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

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

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

為了達(dá)到上述目的，本書(shū)安排了6個(gè)主實(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í)單元與教科書(shū)的各章只具有粗略的對(duì)應(yīng)關(guān)系，一個(gè)實(shí)習(xí)題可能涉及幾部分教學(xué)內(nèi)容。在每個(gè)實(shí)習(xí)單元中安排有難度不等的2—5個(gè)實(shí)習(xí)題，每人可以從中選做一個(gè)實(shí)習(xí)題。建議選做難度略高于自己所做過(guò)的最難題目的難度，切忌過(guò)分追求難題。較大的題目適合于多人合作。

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

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

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

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

實(shí)現(xiàn)提醒對(duì)實(shí)現(xiàn)中的難點(diǎn)及其解法思路等問(wèn)題作了簡(jiǎn)要提醒，個(gè)別問(wèn)題給出了參考實(shí)現(xiàn)；

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

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

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

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

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

實(shí)習(xí)步驟

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

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

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

2．?dāng)?shù)據(jù)類型和系統(tǒng)設(shè)計(jì)

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

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

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

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

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

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

（1）熟悉C語(yǔ)言用戶手冊(cè)或程序設(shè)計(jì)指導(dǎo)書(shū)。（2）注意TurboC、VC與標(biāo)準(zhǔn)C語(yǔ)言之間的微弱區(qū)別。

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

（4）把握調(diào)試工具，考慮調(diào)試方案，設(shè)計(jì)測(cè)試數(shù)據(jù)并手工得出正確結(jié)果。“磨刀不誤砍柴工〞。學(xué)生應(yīng)當(dāng)熟練運(yùn)用高級(jí)語(yǔ)言的程序調(diào)試器DEBUG調(diào)試程序。

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

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

5．總結(jié)和整理實(shí)習(xí)報(bào)告

實(shí)習(xí)報(bào)告規(guī)范

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

1．需求分析

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

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

(2)輸出的形式；

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

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

2．概要設(shè)計(jì)

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

3．詳細(xì)設(shè)計(jì)

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

4．調(diào)試分析

內(nèi)容包括：

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

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

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

c．經(jīng)驗(yàn)和體會(huì)等。

5．用戶使用說(shuō)明

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

6．測(cè)試結(jié)果

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

7．附錄

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

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

實(shí)習(xí)題目

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

三元組ADT

[問(wèn)題描述]

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

[基本要求]

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

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

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

[實(shí)現(xiàn)提醒]

用結(jié)構(gòu)體封裝“三元組〞的三個(gè)分量，并利用typedef對(duì)結(jié)構(gòu)體或結(jié)構(gòu)體指針重新命名。注意：假使要實(shí)現(xiàn)銷毀三元組，則應(yīng)利用typedef對(duì)結(jié)構(gòu)體指針重新命名，并使用C語(yǔ)言的動(dòng)態(tài)分派庫(kù)函數(shù)。

[選作內(nèi)容]

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

有理數(shù)ADT

[問(wèn)題描述]

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

[基本要求]

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

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

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

[實(shí)現(xiàn)提醒]

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

[選作內(nèi)容]

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

復(fù)數(shù)ADT

[問(wèn)題描述]

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

[基本要求]

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

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

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

[實(shí)現(xiàn)提醒]

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

[選作內(nèi)容]

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

實(shí)習(xí)一線性表

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

為側(cè)重點(diǎn)。通過(guò)本次實(shí)習(xí)還可幫助讀者復(fù)習(xí)高級(jí)語(yǔ)言的使用方法。

城市鏈表

[問(wèn)題描述]

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

[基本要求]

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

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

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

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

約瑟夫環(huán)

[問(wèn)題描述]

約瑟夫（Joeph）問(wèn)題的一種描述是：編號(hào)為1,2,?,n的n個(gè)人按順時(shí)針?lè)较驀蝗?，每人持有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)中止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较蛏系南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。

[基本要求]

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

[測(cè)試數(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)行后首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼。設(shè)n≤30。

[選作內(nèi)容]

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

線性表的逆置

[問(wèn)題描述]

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

[基本要求]

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

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

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

[實(shí)現(xiàn)提醒]

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

[選作內(nèi)容]

利用單鏈表作為存儲(chǔ)結(jié)構(gòu)。首先先建立線性表的帶頭結(jié)點(diǎn)的單鏈表表示形式，之后在不借助輔助結(jié)點(diǎn)空間的狀況下實(shí)現(xiàn)單鏈表的逆置，并將結(jié)果輸出。

長(zhǎng)整數(shù)運(yùn)算

[問(wèn)題描述]

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

[基本要求]

利用雙項(xiàng)循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量。任何整型變量的范圍是-（215-1）~（215-1）。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。

[測(cè)試數(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）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為215-1=32767，才能保證兩數(shù)相加不會(huì)溢出。但若這樣存，即相當(dāng)于按32768進(jìn)制數(shù)存，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不便利。故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表視為萬(wàn)進(jìn)制數(shù)。

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

[選作內(nèi)容]

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

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

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

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

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

[問(wèn)題描述]

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

2125202

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

[基本要求]

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

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

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

回文判斷

[問(wèn)題描述]

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

[實(shí)現(xiàn)提醒]

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

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

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

商品貨架管理

[問(wèn)題描述]

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

[基本要求]

針對(duì)一種特定商品，實(shí)現(xiàn)上述管理過(guò)程。

[實(shí)現(xiàn)提醒]

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

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

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

括號(hào)匹配的檢驗(yàn)

[問(wèn)題描述]

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

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

當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的出現(xiàn)，然而等來(lái)的卻是第2個(gè)括號(hào)，此時(shí)第1個(gè)括號(hào)“[〞只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號(hào)相匹配的第7個(gè)括號(hào)“）〞的出現(xiàn)，類似的，因只等來(lái)了第3個(gè)括號(hào)“[〞，此時(shí)，其期待的緊迫程度較第2個(gè)括號(hào)更緊迫，則第2個(gè)括號(hào)只能靠邊，讓位于第3個(gè)括號(hào)，顯然第3個(gè)括號(hào)的期待緊迫程度高于第2個(gè)括號(hào)，而第2個(gè)括號(hào)的期待緊迫程度高于第1個(gè)括號(hào)；在接受了第4個(gè)括號(hào)之后，第3個(gè)括號(hào)的期待得到了滿足，消解之后，第2個(gè)括號(hào)的期待匹配就成了最急迫的任務(wù)了，??，依次類推?？梢?jiàn)這個(gè)處理過(guò)程正好和棧的特點(diǎn)相吻合。

[基本要求]

讀入圓括號(hào)和方括號(hào)的任意序列，輸出“匹配〞或“此串括號(hào)匹配不合法〞。

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

輸入（[]（）），結(jié)果“匹配〞

輸入[（）]，結(jié)果“此串括號(hào)匹配不合法〞

[實(shí)現(xiàn)提醒]

設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，若是左括號(hào)，則作為一個(gè)新的更急迫的期待壓入棧中；若是右括號(hào)，并且與當(dāng)前棧頂?shù)淖罄ㄌ?hào)相匹配，則將當(dāng)前棧頂?shù)淖罄ㄌ?hào)退出，繼續(xù)讀下一個(gè)括號(hào)，假使讀入的右括號(hào)與當(dāng)前棧頂?shù)淖罄ㄌ?hào)不匹配，則屬于不合法的狀況。在初始和終止時(shí)，棧應(yīng)當(dāng)是空的。

[選作內(nèi)容]

考慮增加大括號(hào)的狀況。

停車場(chǎng)管理

[問(wèn)題描述]

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

[測(cè)試數(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ù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)〞或“離去〞信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入終止。

[基本要求]

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

[實(shí)現(xiàn)提醒]

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

[選作內(nèi)容]

（1）兩個(gè)棧共享空間，思考應(yīng)開(kāi)拓?cái)?shù)組的空間是多少？

（2）汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和1.5輛小汽車的占地面積一致，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。

（3）汽車可以直接從便道上開(kāi)走，此時(shí)排在它前面的汽車要先開(kāi)走讓路，然后再依次排到隊(duì)尾。（4）停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場(chǎng)的車低，請(qǐng)思考如何修改結(jié)構(gòu)以滿足這種要求。

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

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

文學(xué)研究助手

[問(wèn)題描述]

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

[基本要求]

英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必需在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。

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

以你的源程序模擬英文小說(shuō)，程序語(yǔ)言保存字集作為待統(tǒng)計(jì)的詞匯集。

[實(shí)現(xiàn)提醒]

設(shè)小說(shuō)中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次，不必存多個(gè)一致的行號(hào)。

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

[選作內(nèi)容]

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

（2）整個(gè)統(tǒng)計(jì)過(guò)程中只對(duì)小說(shuō)文字掃描一遍以提高效率。

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

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

簡(jiǎn)單行編輯程序

[問(wèn)題描述]

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

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

[基本要求]

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

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

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

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

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

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

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

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

[實(shí)現(xiàn)提醒]

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

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

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

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

[選作內(nèi)容]

（1）對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。

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

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

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

二叉樹(shù)的建立與遍歷

[問(wèn)題描述]

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

[基本要求]

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

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

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

[選作內(nèi)容]

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

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

數(shù)據(jù)對(duì)象：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é)點(diǎn)，其data域沒(méi)有意義。

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．使用說(shuō)明

程序名為L(zhǎng)inkList.exe，運(yùn)行環(huán)境為DOS。程序執(zhí)行后顯示========================0EXIT1INSERT2DELETE3LOCATE

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

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

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

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

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

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

7．測(cè)試結(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），顯示輸入錯(cuò)誤?選擇1輸入（7，2），顯示輸入錯(cuò)誤

?選擇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。返回輸入錯(cuò)誤4）查找

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

[問(wèn)題描述]

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

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

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

（1）利用RDL遍歷方法；

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

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

[問(wèn)題描述]

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

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

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

[實(shí)現(xiàn)提醒]

（1）利用樹(shù)的先根遍歷方法；（2）利用結(jié)點(diǎn)的深度控制橫向位置。

圖遍歷的演示

[問(wèn)題描述]

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

[基本要求]

以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列和相應(yīng)生成樹(shù)的邊集。

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

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

[實(shí)現(xiàn)提醒]

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