#《數(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ì)算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程， 是計(jì)算機(jī)專業(yè)的一門核心的 關(guān)鍵性課程。 本課程較系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)和實(shí)現(xiàn) 算法， 介紹了常用的多種查找和排序技術(shù)，并做了性能分析和比較，內(nèi)容非常豐富。本課程 的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計(jì)水平的提高打下良好的基礎(chǔ)。由于以下原因，使得掌握這門課程具有較大的難度：（ 1） 內(nèi)容豐富，學(xué)習(xí)量大，給學(xué)習(xí)帶來困難；（ 2） 貫穿全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點(diǎn)也是難點(diǎn)；（ 3） 所用到的技術(shù)多， 而在此之前的各門課程中所介紹的專業(yè)性知識又不多，

2、 因而加 大了學(xué)習(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é)時為10。二、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)的目的和要求不少學(xué)生在解答習(xí)題尤其是算法設(shè)計(jì)題時，覺得無從下手，做起來特別費(fèi)勁。實(shí)驗(yàn)中的 內(nèi)容和教科書的內(nèi)容是密切相關(guān)的，解決題目要求所需的各種技術(shù)大多可從教科書中找到， 只不過其出現(xiàn)的形式呈多樣化，因此需要仔細(xì)體會，在反復(fù)實(shí)踐的過程中才能掌握。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計(jì)所需

3、的技術(shù)，為整個專業(yè)學(xué)習(xí)打 好基礎(chǔ)，要求運(yùn)用所學(xué)知識，上機(jī)解決一些典型問題，通過分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán) 節(jié)的訓(xùn)練， 使學(xué)生深刻理解、 牢固掌握所用到的一些技術(shù)。 數(shù)據(jù)結(jié)構(gòu)中稍微復(fù)雜一些的算法 設(shè)計(jì)中可能同時要用到多種技術(shù)和方法，如算法設(shè)計(jì)的構(gòu)思方法，動態(tài)鏈表，算法的編碼， 遞歸技術(shù)，和特定問題相關(guān)的技術(shù)等，要求重點(diǎn)掌握線性鏈表、二叉樹和樹、圖結(jié)構(gòu)、數(shù)組 結(jié)構(gòu)相關(guān)算法的設(shè)計(jì)。在掌握基本算法的基礎(chǔ)上，掌握分析、解決實(shí)際問題的能力。三、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)內(nèi)容課程實(shí)驗(yàn)共 10 學(xué)時，要求完成以下五個題目：實(shí)習(xí)一 約瑟夫環(huán)問題（ 2 學(xué)時） 用循環(huán)鏈表實(shí)現(xiàn)約瑟夫環(huán)問題，熟悉鏈表結(jié)構(gòu)的使用。實(shí)習(xí)二 八皇

4、后問題 （2 學(xué)時）在8X8的棋盤上放置彼此不受攻擊的 8個皇后，熟悉遞歸和回溯程序設(shè)計(jì)方法。實(shí)習(xí)三 二叉樹基本操作（ 2 學(xué)時） 創(chuàng)建、遍歷、顯示二叉樹，通過二叉樹的基本操作，掌握樹結(jié)構(gòu)的處理方法。實(shí)習(xí)四 哈夫曼編碼和譯碼針對字符集A及其各字符的頻率值（可統(tǒng)計(jì)獲得）給出其中給字符哈夫曼編碼，并 針對一段文本（定義在 A上）進(jìn)行編碼和譯碼，實(shí)現(xiàn)一個哈夫曼編碼 /譯碼系統(tǒng)。實(shí)習(xí)五 最小生成樹問題（ 2 學(xué)時）在 n 個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。四、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)考核方式采用上機(jī)情況、程序質(zhì)量、實(shí)習(xí)報(bào)告相結(jié)合的形式，滿分為100 分。1 上機(jī)情況（ 30%）包括出勤

5、情況、調(diào)試表現(xiàn)、是否上網(wǎng)、玩游戲。2 程序質(zhì)量（ 50%）3 實(shí)習(xí)報(bào)告（ 20%）數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)指導(dǎo)書實(shí)習(xí)一 線性表本次實(shí)習(xí)的主要目的在于熟悉線性表的基本運(yùn)算在兩種存儲結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點(diǎn)。通過本次實(shí)習(xí)還可幫助讀者復(fù)習(xí)高級語言的使用方法。1、城市鏈表 問題描述 將若干城市的信息， 存入一個帶頭結(jié)點(diǎn)的單鏈表。結(jié)點(diǎn)中的城市信息包括：城市名，城 市的位置坐標(biāo)。要求能夠利用城市名和位置坐標(biāo)進(jìn)行有關(guān)查找、插入、刪除、更新等操作。 基本要求 （ 1） 給定一個城市名，返回其位置坐標(biāo)；（2）給定一個位置坐標(biāo) P和一個距離D,返回所有和P的距離小于等于 D的城市。 測試數(shù)據(jù) 由學(xué)生

6、依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2、約瑟夫環(huán) 問題描述 約瑟夫（Joeph）問題的一種描述是：編號為1,2,n的n個人按順時針方向圍坐一圈， 每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報(bào)數(shù)上限值 m,從第一個人開始 按順時針方向自1開始順序報(bào)數(shù)，報(bào)到m時停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的 m值，從他在順時針方向上的下一個人開始重新從 1報(bào)數(shù)，如此下去，直至所有人全部出列 為止。試設(shè)計(jì)一個程序求出出列順序。 基本要求 利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程,按照出列的順序印出各人的編號。 測試數(shù)據(jù) m的初值為20;密碼：3, 1, 7, 2, 4, 8, 4 （正

7、確的結(jié)果應(yīng)為 6, 1, 4, 7, 2, 3, 5）。 實(shí)現(xiàn)提示 程序運(yùn)行后首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼。設(shè)nW 30。 選作內(nèi)容 向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。3、線性表的逆置 問題描述 分別以不同存儲結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置。 線性表的就地逆置就是在原表的存儲空間內(nèi)將線性表（a1,a2,a3,an）逆置為（ an, an-1，a2, al）。 基本要求 用順序存儲結(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)的后繼。

8、 選作內(nèi)容 利用單鏈表作為存儲結(jié)構(gòu)。 首先先建立線性表的帶頭結(jié)點(diǎn)的單鏈表表示形式, 之后在不 借助輔助結(jié)點(diǎn)空間的情況下實(shí)現(xiàn)單鏈表的逆置,并將結(jié)果輸出。4、長整數(shù)運(yùn)算 問題描述 設(shè)計(jì)一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運(yùn)算。 基本要求 利用雙項(xiàng)循環(huán)鏈表實(shí)現(xiàn)長整數(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,0

9、000,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ù)相加不會溢出。 但若這樣存, 即相當(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ù)的符號。用其絕對值表示

10、元素結(jié)點(diǎn)數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。 兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的 一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。 選作內(nèi)容 修改上述程序,使它在整型量范圍是 - （ 2n-1 ） （ 2n-1 ）的計(jì)算機(jī)上都能有效地運(yùn)行。 其中, n 是由程序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。實(shí)習(xí)二 棧、隊(duì)列和遞歸算法設(shè)計(jì)僅僅認(rèn)識到棧和隊(duì)列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的, 本次實(shí)習(xí)的目的在于使讀者深 入了解棧和隊(duì)列的特征, 以便在實(shí)際問題背景下靈活運(yùn)用它們； 同時還將鞏固這兩種結(jié)構(gòu)的 構(gòu)造方法,接觸較復(fù)雜問題的遞歸算法設(shè)計(jì)。1 、數(shù)制轉(zhuǎn)換問題 問題描述 將十進(jìn)制數(shù)N和其它d進(jìn)制

11、數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，其解決方案很多, 其中最簡單方法基于下列原理：即除 d 取余法。例如： （1348）10=（2504）8NN div 8N mod 8134816841682102125202從中我們可以看出，最先產(chǎn)生的余數(shù) 4 是轉(zhuǎn)換結(jié)果的最低位， 這正好符合棧的特性即后進(jìn)先出的特性。所以可以用順序棧來模擬這個過程。 基本要求 對于鍵盤輸入的任意一個非負(fù)的十進(jìn)制整數(shù)， 打印輸出和其等值的八進(jìn)制數(shù)。 由于上述 的計(jì)算過程是從低位到高位順序產(chǎn)生的八進(jìn)制數(shù)的各個數(shù)位，而打印輸出， 一般來說應(yīng)從高位到地位進(jìn)行， 恰好和計(jì)算過程相反。 因此可以先將計(jì)算過程中得到的八進(jìn)制數(shù)的各位進(jìn)棧

12、， 待相對應(yīng)的八進(jìn)制數(shù)的各位均產(chǎn)生以后， 再使其按順序出棧， 并打印輸出。 即得到了和輸入 的十進(jìn)制數(shù)相對應(yīng)的八進(jìn)制數(shù)。 測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2、回文判斷 問題描述 試寫一個算法，判斷依次讀入的一個以為結(jié)束符的字母序列，是否為形如序列1 &序列 2'模式的字符序列。其中序列1和序列 2 中都不含字符 &'，且序列 2 是序列 1的逆序列。例如， a+b&b+a是屬該模式的字符序列，而1+3 &3 1'則不是。 實(shí)現(xiàn)提示 首先，序列 1 進(jìn)棧，然后序列 1 出棧并和序列 2 比較。 測試數(shù)據(jù) 由

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

14、用“期待的緊迫程度”這個概念來描述。例如：考慮下列的括號序列： （ ） 1 2 3 4 5 6 7 8當(dāng)計(jì)算機(jī)接受了第 1 個括號以后， 他期待著和其匹配的第 8 個括號的出現(xiàn)， 然而等來的 卻是第 2個括號，此時第 1個括號“ ”只能暫時靠邊， 而迫切等待和第 2 個括號相匹配的 第 7 個括號“）”的出現(xiàn)，類似的，因只等來了第3 個括號“ ”，此時，其期待的緊迫程度較第2個括號更緊迫， 則第2個括號只能靠邊， 讓位于第 3個括號，顯然第 3個括號的期待 緊迫程度高于第 2 個括號，而第 2 個括號的期待緊迫程度高于第 1 個括號；在接受了第 4 個括號之后， 第 3個括號的期待得到了滿足，

15、 消解之后， 第 2個括號的期待匹配就成了最急 迫的任務(wù)了，依次類推?？梢娺@個處理過程正好和棧的特點(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)容 考慮增加大括號的情況。5、停車場管理

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

17、（ 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ù)項(xiàng)： 汽車“到達(dá)”或“離去”信息、 汽車牌照號碼及到達(dá) 或離去的時刻，其中， A'表示到達(dá)；D'表示離去，E'表示輸入結(jié)束。 基本要求 以棧模擬停車場, 以隊(duì)列模擬車場外的便道, 按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬 管理。 每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)： 汽車“到達(dá)”

18、或“離去”信息、 汽車牌照號碼及到 達(dá)或離去的時刻, 對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為： 若是車輛到達(dá), 則輸出汽車 在停車場內(nèi)或便道上的停車位置； 若是車離去； 則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納 的費(fèi)用（在便道上停留的時間不收費(fèi)） 。棧以順序結(jié)構(gòu)實(shí)現(xiàn),隊(duì)列以鏈表實(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） 汽車可有不同種類，則它

19、們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1 輛客車和1.5 輛小汽車的占地面積相同， 1 輛十輪卡車占地面積相當(dāng)于 3 輛小汽車的占地面積。（ 3） 汽車可以直接從便道上開走， 此時排在它前面的汽車要先開走讓路，然后再依次 排到隊(duì)尾。（ 4） 停放在便道上的汽車也收費(fèi)， 收費(fèi)標(biāo)準(zhǔn)比停放在停車場的車低， 請思考如何修改 結(jié)構(gòu)以滿足這種要求。實(shí)習(xí)三 串及其使用本次實(shí)習(xí)的目的是熟悉串類型的實(shí)現(xiàn)方法和文本模式匹配方法， 熟悉一般文字處理軟件 的設(shè)計(jì)方法， 較復(fù)雜問題的分解求精方法， 在第二次實(shí)習(xí)的基礎(chǔ)上， 進(jìn)一步強(qiáng)化這樣一個觀 念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在其上的操作， 此外還希望起到訓(xùn)練合作能力和熟悉文件

20、操作 的目的。本次實(shí)習(xí)的難度較大。1、文學(xué)研究助手 問題描述 文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。 試寫一個實(shí)現(xiàn)這 一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”。 基本要求 英文小說存于一個文本文件中。 待統(tǒng)計(jì)的詞匯集合要一次輸入完畢， 即統(tǒng)計(jì)工作必須在 程序的一次運(yùn)行之后就全部完成。 程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的 行號，格式自行設(shè)計(jì)。 測試數(shù)據(jù) 以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計(jì)的詞匯集。 實(shí)現(xiàn)提示 設(shè)小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個詞在這行中的出現(xiàn)次數(shù)。 出現(xiàn)位置所在行的行號可以用鏈表存儲。 若某行中出現(xiàn)了

21、不止一次， 不必存多個相同的行號。如果讀者希望達(dá)到選作部分（1 ）和（2）所提出的要求，則首先應(yīng)把 KMP算法改寫成如 下的等價形式，再將它推廣到多個模式的情形。 選作內(nèi)容 （1）模式匹配要基于 KMP算法。（ 2） 整個統(tǒng)計(jì)過程中只對小說文字掃描一遍以提高效率。（ 3） 假設(shè)小說中的每個單詞或者從行首開始，或者前置以一個空格符。利用單詞匹配 特點(diǎn)另寫一個高效的統(tǒng)計(jì)程序，和KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。（ 4） 推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作 getachar ）2、簡單行編輯程序 問題描述 文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對文本

22、文件的插入、 刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟(jì)， 也不總能實(shí)現(xiàn)。 一種解決方法是逐段地編輯。 任何時刻只把待編輯文件的一段放在內(nèi)存， 稱 為活區(qū)。 試按照這種方法實(shí)現(xiàn)一個簡單的行編輯程序。 設(shè)文件每行不超過 320 個字符， 很少 超過 80 字符。 基本要求 實(shí)現(xiàn)以下 4 條基本編輯命令：(1) 行插入。格式： i 行號回車文本回車 將文本 插入活區(qū)中第 行號行之后(2) 行刪除。格式：d行號1 行號2回車刪除活區(qū)中第 行號1行(到第 行號2行)。兩種格式的例子是：“ d10/”和“

23、 d10口 14/”(3) 活區(qū)切換。格式： *回車將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(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ù)，如首行、尾行。 實(shí)現(xiàn)提示 (1) 設(shè)活區(qū)的大小用行數(shù) activemaxle

24、n (可設(shè)為 100)來描述?？紤]到文本文件行長通常為正態(tài)分布，且峰值在60到70之間，用320x activemaxlen 大小的字符數(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) 初始化過程包括： 請用戶提供輸入文件名 (空串表示無輸入文件) 和輸出文件名， 兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過act

25、ivemaxlen-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)格檢查和

26、適當(dāng)處理。(2) 加入更復(fù)雜的編輯操作，如對某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為S亍號串1串 2回車和口串 回車。實(shí)習(xí)四 樹、圖及其使用樹和圖是兩種使用極為廣泛的數(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è)計(jì)觀點(diǎn)，但根據(jù)這兩種結(jié)構(gòu)的非線性特點(diǎn)，將操作進(jìn)一步集中在遍歷操作上，因?yàn)楸闅v操作是其他眾多操作的基礎(chǔ)。遍歷邏輯的（或符號形式的）結(jié)構(gòu)，訪問動作可是任何操作。本次實(shí)習(xí)還希望達(dá)到熟悉各種存 儲結(jié)構(gòu)的特征，以及如何使用樹和圖結(jié)構(gòu)解決具體問

27、題（即原理和使用的結(jié)合）等目的。1、二叉樹的建立和遍歷問題描述建立一棵二叉樹，并對其進(jìn)行遍歷（先序、中序、后序），打印輸出遍歷結(jié)果。基本要求從鍵盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），并采用遞歸算法對其進(jìn)行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出。測試數(shù)據(jù)ABG © DE©F© ©© （其中©表示空格字符）則輸出結(jié)果為先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA選作內(nèi)容采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。2、打印樹結(jié)構(gòu)問題描述按凹入表形式打印樹形結(jié)構(gòu)。CFEADB測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程

28、的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空樹。 實(shí)現(xiàn)提示（1）利用樹的先根遍歷方法；（2）禾U用結(jié)點(diǎn)的深度控制橫向位置。3、哈夫曼編碼/譯碼器重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為【問題描述】 設(shè)計(jì)一個利用哈夫曼算法的編碼和譯碼系統(tǒng)， 止。【基本要求】(1) 初始化：鍵盤輸入字符集大小 n、n個字符和n個權(quán)值，建立哈夫曼樹；(2) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；(3) 輸出編碼；(4) 設(shè)字符集及頻度如下表：字符 空格 A B C D E F G H I J K L M頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R

29、S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 【選做內(nèi)容】(1) 譯碼功能；(2) 顯示哈夫曼樹；(3) 界面設(shè)計(jì)的優(yōu)化。4、圖遍歷的演示 問題描述 很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。 試寫一個程序， 演示無向圖的 遍歷操作。 基本要求 以鄰接表為存儲結(jié)構(gòu)， 實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。 以用戶指定的結(jié)點(diǎn) 為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。 測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如單個結(jié)點(diǎn)。 實(shí)現(xiàn)提示 設(shè)圖的結(jié)點(diǎn)不超過 30 個，每個結(jié)點(diǎn)用一個編號表示

30、(如果一個圖有 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)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹(3) 實(shí)現(xiàn)有向圖的遍歷操作。實(shí)習(xí)五 查找和排序本次實(shí)習(xí)旨在集中對幾個專門的問題作較為深入的探討和理解，不強(qiáng)調(diào)對某些特定的編程技術(shù)的訓(xùn)練。1 、二叉排序樹 問題描述 從鍵盤讀入一組數(shù)據(jù)， 建立二叉排序樹并對其進(jìn)行查找、 遍歷、格式化打

31、印等有關(guān)操作。 基本要求 建立二叉排序樹并對其進(jìn)行查找，包括成功和不成功兩種情況，并給出查找長度。 測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。 選作內(nèi)容 實(shí)現(xiàn)二叉排序樹的插入、刪除操作。2、哈希表設(shè)計(jì) 問題描述 針對某個集體中人名設(shè)計(jì)一個哈希表，使得平均查找長度不超過R,并完成相應(yīng)的建表和查表程序。 基本要求 假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30 個，取平均查找長度的上限為 2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。 測試數(shù)據(jù) 取讀者周圍較熟悉的 30 個人名。 選作內(nèi)容 （1）從教科書上介紹的集中哈希函數(shù)構(gòu)造方法中選

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

33、序；起泡排序；快速排序；簡單選擇排序；堆排序；歸并排序；基數(shù)排 序。（2）待排序表的表長不少于 100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；至少要用5 組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字移動次數(shù)（關(guān) 鍵字交換計(jì)為 3 次移動）。 測試數(shù)據(jù) 由隨機(jī)產(chǎn)生器決定。 實(shí)現(xiàn)提示 主要工作是設(shè)法在程序中適當(dāng)?shù)牡胤讲迦胗?jì)數(shù)操作。 程序還可以包括計(jì)算幾組數(shù)據(jù)得出 結(jié)果波動大小的解釋。注意分塊調(diào)試的方法。 選作內(nèi)容 對不同的輸入表長做試驗(yàn)， 觀察檢查兩個指標(biāo)相關(guān)于表長的變化關(guān)系。 還可以對穩(wěn)定性 做驗(yàn)證。3、統(tǒng)計(jì)成績 問題描述 給出n個學(xué)生的m門測試的成績表，每個學(xué)生的信息由學(xué)號

34、、姓名以及各科成績組成。 對學(xué)生的測試成績進(jìn)行有關(guān)統(tǒng)計(jì)，并打印統(tǒng)計(jì)表。 基本要求 （1）按總數(shù)高低次序，打印出名次表，分?jǐn)?shù)相同的為同一名次；（2）按名次打印出每個學(xué)生的學(xué)號、姓名、總分以及各科成績。 測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。 選作內(nèi)容 對各科成績設(shè)置不同的權(quán)值。附錄 2 實(shí)驗(yàn)報(bào)告示例級 班 年 月日 姓名 學(xué)號 電話1實(shí)驗(yàn)題目編制一個演示單鏈表插入、刪除、查找等操作的程序2需求分析本演示程序用TC編寫，完成單鏈表的生成，任意位置的插入、刪除，以及確定某一元 素在單鏈表中的位置。 輸入的形式和輸入值的范圍：插入元素時需要輸入插入的位置和元素的值；刪除元

35、素時輸入刪除元素的位置； 查找操作時需要輸入元素的值。 在所有輸入中， 元素的值都是整 數(shù) 輸出的形式：在所有三種操作中都顯示操作是否正確以及操作后單鏈表的內(nèi)容。其 中刪除操作后顯示刪除的元素的值，查找操作后顯示要查找元素的位置。 程序所能達(dá)到的功能：完成單鏈表的生成(通過插入操作) 、插入、刪除、查找操作 測試數(shù)據(jù)：A 插入操作中依次輸入B 查找操作中依次輸入C 刪除操作中依次輸入11， 12， 13， 14， 15， 16，生成一個單鏈表12， 15， 22 返回這 3 個元素在單鏈表中的位置2， 5，刪除位于 2 和 5 的元素3概要設(shè)計(jì)1) 為了實(shí)現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)

36、據(jù)類型：ADT LinkList 數(shù)據(jù)對象：D=ai|ai IntegerSet,i=0,1,2,n,n > 0數(shù)據(jù)關(guān)系：R=<ai,ai+1>|ai,ai+1 D基本操作：InitLinkList(&L)操作結(jié)果：構(gòu)造一個空的單鏈表 L.InsLinkList(&L,pos,e)初始條件：單鏈表 L 已存在操作結(jié)果：將元素 e插入到單鏈表L的pos位置DelLinkList(&L,pos,&e)初始條件：單鏈表 L 已存在操作結(jié)果：將單鏈表 L 中 pos 位置的元素刪除， 元素值置入 e 中返回LocLinkList(L,e)初始條件：單鏈表 L 依存在操作結(jié)果：單鏈表 L 中查找是否元素 e，若存在，返回元素在表中的位置；若不存在，返回 -1.Menu()操作結(jié)果：在屏幕上顯示操作菜單2) 本程序包含7個函數(shù)： 主函數(shù) main() 初始化單鏈表函數(shù)InitLinkList() 顯示操作菜單函數(shù)menu() 顯示單鏈表內(nèi)容函數(shù)dispLinkList() 插入元素函數(shù)InsLinkList() 刪除元素函數(shù)DelLinkList() 查找元素函數(shù)LocLinkList()各函數(shù)間關(guān)系如下：mainInitLinkListJlenuDispLinkList InsLinkListDelLinkList L