#《數(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)的存儲(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） 貫穿全書的動(dòng)態(tài)鏈表存儲(chǔ)結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點(diǎn)也是難點(diǎn)；（ 3） 所用到的技術(shù)多， 而在此之前的各門課程中所介紹的專業(yè)性知識(shí)又不多，

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

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

4、后問(wèn)題 （2 學(xué)時(shí)）在8X8的棋盤上放置彼此不受攻擊的 8個(gè)皇后，熟悉遞歸和回溯程序設(shè)計(jì)方法。實(shí)習(xí)三 二叉樹基本操作（ 2 學(xué)時(shí)） 創(chuàng)建、遍歷、顯示二叉樹，通過(guò)二叉樹的基本操作，掌握樹結(jié)構(gòu)的處理方法。實(shí)習(xí)四 哈夫曼編碼和譯碼針對(duì)字符集A及其各字符的頻率值（可統(tǒng)計(jì)獲得）給出其中給字符哈夫曼編碼，并 針對(duì)一段文本（定義在 A上）進(jìn)行編碼和譯碼，實(shí)現(xiàn)一個(gè)哈夫曼編碼 /譯碼系統(tǒng)。實(shí)習(xí)五 最小生成樹問(wèn)題（ 2 學(xué)時(shí)）在 n 個(gè)城市之間建設(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)算在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點(diǎn)。通過(guò)本次實(shí)習(xí)還可幫助讀者復(fù)習(xí)高級(jí)語(yǔ)言的使用方法。1、城市鏈表 問(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é)生

6、依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)。2、約瑟夫環(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 （正

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、線性表的逆置 問(wèn)題描述 分別以不同存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置。 線性表的就地逆置就是在原表的存儲(chǔ)空間內(nèi)將線性表（a1,a2,a3,an）逆置為（ an, an-1，a2, al）。 基本要求 用順序存儲(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)的后繼。

8、 選作內(nèi)容 利用單鏈表作為存儲(chǔ)結(jié)構(gòu)。 首先先建立線性表的帶頭結(jié)點(diǎn)的單鏈表表示形式, 之后在不 借助輔助結(jié)點(diǎn)空間的情況下實(shí)現(xiàn)單鏈表的逆置,并將結(jié)果輸出。4、長(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,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） 每個(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ì)值表示

10、元素結(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í)還將鞏固這兩種結(jié)構(gòu)的 構(gòu)造方法,接觸較復(fù)雜問(wèn)題的遞歸算法設(shè)計(jì)。1 、數(shù)制轉(zhuǎn)換問(wèn)題 問(wèn)題描述 將十進(jìn)制數(shù)N和其它d進(jìn)制

11、數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題，其解決方案很多, 其中最簡(jiǎn)單方法基于下列原理：即除 d 取余法。例如： （1348）10=（2504）8NN div 8N mod 8134816841682102125202從中我們可以看出，最先產(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)棧

12、， 待相對(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ù)。2、回文判斷 問(wèn)題描述 試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如序列1 &序列 2'模式的字符序列。其中序列1和序列 2 中都不含字符 &'，且序列 2 是序列 1的逆序列。例如， a+b&b+a是屬該模式的字符序列，而1+3 &3 1'則不是。 實(shí)現(xiàn)提示 首先，序列 1 進(jìn)棧，然后序列 1 出棧并和序列 2 比較。 測(cè)試數(shù)據(jù) 由

13、學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。 注意測(cè)試邊界數(shù)據(jù)， 如序列 1 和序列 2均為 空串。3、商品貨架管理 問(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ù)，如空棧。4、括號(hào)匹配的檢驗(yàn) 問(wèn)題描述 假設(shè)表達(dá)式中允許有兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即（ （） ）或（ ）等為正確格式， （ ）或（均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可

14、用“期待的緊迫程度”這個(gè)概念來(lái)描述。例如：考慮下列的括號(hào)序列： （ ） 1 2 3 4 5 6 7 8當(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)的期待得到了滿足，

15、 消解之后， 第 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)不匹配， 則屬于不合法的情況。 在初始和結(jié)束 時(shí)，棧應(yīng)該是空的。 選作內(nèi)容 考慮增加大括號(hào)的情況。5、停車場(chǎng)管理

16、 問(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ù)為：

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

18、或“離去”信息、 汽車牌照號(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)辟數(shù)組的空間是多少？（ 2） 汽車可有不同種類，則它

19、們的占地面積不同，收費(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í)三 串及其使用本次實(shí)習(xí)的目的是熟悉串類型的實(shí)現(xiàn)方法和文本模式匹配方法， 熟悉一般文字處理軟件 的設(shè)計(jì)方法， 較復(fù)雜問(wèn)題的分解求精方法， 在第二次實(shí)習(xí)的基礎(chǔ)上， 進(jìn)一步強(qiáng)化這樣一個(gè)觀 念：程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在其上的操作， 此外還希望起到訓(xùn)練合作能力和熟悉文件

20、操作 的目的。本次實(shí)習(xí)的難度較大。1、文學(xué)研究助手 問(wèn)題描述 文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。 試寫一個(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)了

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

22、文件的插入、 刪除等修改操作。限制這些操作以行為單位進(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 行號(hào)回車文本回車 將文本 插入活區(qū)中第 行號(hào)行之后(2) 行刪除。格式：d行號(hào)1 行號(hào)2回車刪除活區(qū)中第 行號(hào)1行(到第 行號(hào)2行)。兩種格式的例子是：“ d10/”和“

23、 d10口 14/”(3) 活區(qū)切換。格式： *回車將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(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ù) activemaxle

24、n (可設(shè)為 100)來(lái)描述?？紤]到文本文件行長(zhǎng)通常為正態(tài)分布，且峰值在60到70之間，用320x 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ò)act

25、ivemaxlen-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ù)性；否則，它意味著結(jié)束編輯或開(kāi)始編輯另一個(gè)文件。( 5) 可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。 選作內(nèi)容 ( 1 ) 對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和

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

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

28、的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如空樹。 實(shí)現(xiàn)提示（1）利用樹的先根遍歷方法；（2）禾U用結(jié)點(diǎn)的深度控制橫向位置。3、哈夫曼編碼/譯碼器重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為【問(wèn)題描述】 設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)， 止。【基本要求】(1) 初始化：鍵盤輸入字符集大小 n、n個(gè)字符和n個(gè)權(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、圖遍歷的演示 問(wèn)題描述 很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。 試寫一個(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)生成樹的邊集。 測(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)表示

30、(如果一個(gè)圖有 n 個(gè)結(jié)點(diǎn)，則它們 的編號(hào)分別為1,2,n )。通過(guò)輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊 的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點(diǎn)順序不能顛倒。 選作內(nèi)容 (1) 借助于棧類型(自己定義和實(shí)現(xiàn))將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。( 2) 以鄰接多重表為存儲(chǔ)結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹(3) 實(shí)現(xiàn)有向圖的遍歷操作。實(shí)習(xí)五 查找和排序本次實(shí)習(xí)旨在集中對(duì)幾個(gè)專門的問(wèn)題作較為深入的探討和理解，不強(qiáng)調(diào)對(duì)某些特定的編程技術(shù)的訓(xùn)練。1 、二叉排序樹 問(wèn)題描述 從鍵盤讀入一組數(shù)據(jù)， 建立二叉排序樹并對(duì)其進(jìn)行查找、 遍歷、格式化打

31、印等有關(guān)操作。 基本要求 建立二叉排序樹并對(duì)其進(jìn)行查找，包括成功和不成功兩種情況，并給出查找長(zhǎng)度。 測(cè)試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)。 選作內(nèi)容 實(shí)現(xiàn)二叉排序樹的插入、刪除操作。2、哈希表設(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ù)構(gòu)造方法中選

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

33、序；起泡排序；快速排序；簡(jiǎn)單選擇排序；堆排序；歸并排序；基數(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)， 觀察檢查兩個(gè)指標(biāo)相關(guān)于表長(zhǎng)的變化關(guān)系。 還可以對(duì)穩(wěn)定性 做驗(yàn)證。3、統(tǒng)計(jì)成績(jī) 問(wèn)題描述 給出n個(gè)學(xué)生的m門測(cè)試的成績(jī)表，每個(gè)學(xué)生的信息由學(xué)號(hào)

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

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

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