


版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
1、數(shù)據(jù)結(jié)構(gòu)課程實驗大綱一、數(shù)據(jù)結(jié)構(gòu)課程實驗的地位和作用“數(shù)據(jù)結(jié)構(gòu)”是計算機專業(yè)一門重要的專業(yè)技術基礎課程, 是計算機專業(yè)的一門核心的 關鍵性課程。 本課程較系統(tǒng)地介紹了軟件設計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應的存儲結(jié)構(gòu)和實現(xiàn) 算法, 介紹了常用的多種查找和排序技術,并做了性能分析和比較,內(nèi)容非常豐富。本課程 的學習將為后續(xù)課程的學習以及軟件設計水平的提高打下良好的基礎。由于以下原因,使得掌握這門課程具有較大的難度:( 1) 內(nèi)容豐富,學習量大,給學習帶來困難;( 2) 貫穿全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術是學習中的重點也是難點;( 3) 所用到的技術多, 而在此之前的各門課程中所介紹的專業(yè)性知識又不多,
2、 因而加 大了學習難度;( 4) 隱含在各部分的技術和方法豐富,也是學習的重點和難點。根據(jù)數(shù)據(jù)結(jié)構(gòu)課程課程本身的技術特性,設置數(shù)據(jù)結(jié)構(gòu)課程實驗實踐環(huán)節(jié)十 分重要。 通過實驗實踐內(nèi)容的訓練, 突出構(gòu)造性思維訓練的特征 , 目的是提高學生組織數(shù)據(jù) 及編寫大型程序的能力。實驗學時為10。二、數(shù)據(jù)結(jié)構(gòu)課程實驗的目的和要求不少學生在解答習題尤其是算法設計題時,覺得無從下手,做起來特別費勁。實驗中的 內(nèi)容和教科書的內(nèi)容是密切相關的,解決題目要求所需的各種技術大多可從教科書中找到, 只不過其出現(xiàn)的形式呈多樣化,因此需要仔細體會,在反復實踐的過程中才能掌握。為了幫助學生更好地學習本課程,理解和掌握算法設計所需
3、的技術,為整個專業(yè)學習打 好基礎,要求運用所學知識,上機解決一些典型問題,通過分析、設計、編碼、調(diào)試等各環(huán) 節(jié)的訓練, 使學生深刻理解、 牢固掌握所用到的一些技術。 數(shù)據(jù)結(jié)構(gòu)中稍微復雜一些的算法 設計中可能同時要用到多種技術和方法,如算法設計的構(gòu)思方法,動態(tài)鏈表,算法的編碼, 遞歸技術,和特定問題相關的技術等,要求重點掌握線性鏈表、二叉樹和樹、圖結(jié)構(gòu)、數(shù)組 結(jié)構(gòu)相關算法的設計。在掌握基本算法的基礎上,掌握分析、解決實際問題的能力。三、數(shù)據(jù)結(jié)構(gòu)課程實驗內(nèi)容課程實驗共 10 學時,要求完成以下五個題目:實習一 約瑟夫環(huán)問題( 2 學時) 用循環(huán)鏈表實現(xiàn)約瑟夫環(huán)問題,熟悉鏈表結(jié)構(gòu)的使用。實習二 八皇
4、后問題 (2 學時)在8X8的棋盤上放置彼此不受攻擊的 8個皇后,熟悉遞歸和回溯程序設計方法。實習三 二叉樹基本操作( 2 學時) 創(chuàng)建、遍歷、顯示二叉樹,通過二叉樹的基本操作,掌握樹結(jié)構(gòu)的處理方法。實習四 哈夫曼編碼和譯碼針對字符集A及其各字符的頻率值(可統(tǒng)計獲得)給出其中給字符哈夫曼編碼,并 針對一段文本(定義在 A上)進行編碼和譯碼,實現(xiàn)一個哈夫曼編碼 /譯碼系統(tǒng)。實習五 最小生成樹問題( 2 學時)在 n 個城市之間建設網(wǎng)絡,只需保證連通即可,求最經(jīng)濟的架設方法。四、數(shù)據(jù)結(jié)構(gòu)課程實驗考核方式采用上機情況、程序質(zhì)量、實習報告相結(jié)合的形式,滿分為100 分。1 上機情況( 30%)包括出勤
5、情況、調(diào)試表現(xiàn)、是否上網(wǎng)、玩游戲。2 程序質(zhì)量( 50%)3 實習報告( 20%)數(shù)據(jù)結(jié)構(gòu)課程實驗指導書實習一 線性表本次實習的主要目的在于熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)上的實現(xiàn),其中以熟悉各種鏈表的操作為側(cè)重點。通過本次實習還可幫助讀者復習高級語言的使用方法。1、城市鏈表 問題描述 將若干城市的信息, 存入一個帶頭結(jié)點的單鏈表。結(jié)點中的城市信息包括:城市名,城 市的位置坐標。要求能夠利用城市名和位置坐標進行有關查找、插入、刪除、更新等操作。 基本要求 ( 1) 給定一個城市名,返回其位置坐標;(2)給定一個位置坐標 P和一個距離D,返回所有和P的距離小于等于 D的城市。 測試數(shù)據(jù) 由學生
6、依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù)。2、約瑟夫環(huán) 問題描述 約瑟夫(Joeph)問題的一種描述是:編號為1,2,n的n個人按順時針方向圍坐一圈, 每人持有一個密碼(正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值 m,從第一個人開始 按順時針方向自1開始順序報數(shù),報到m時停止報數(shù)。報m的人出列,將他的密碼作為新的 m值,從他在順時針方向上的下一個人開始重新從 1報數(shù),如此下去,直至所有人全部出列 為止。試設計一個程序求出出列順序。 基本要求 利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程,按照出列的順序印出各人的編號。 測試數(shù)據(jù) m的初值為20;密碼:3, 1, 7, 2, 4, 8, 4 (正
7、確的結(jié)果應為 6, 1, 4, 7, 2, 3, 5)。 實現(xiàn)提示 程序運行后首先要求用戶指定初始報數(shù)上限值,然后讀取各人的密碼。設nW 30。 選作內(nèi)容 向上述程序中添加在順序結(jié)構(gòu)上實現(xiàn)的部分。3、線性表的逆置 問題描述 分別以不同存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置。 線性表的就地逆置就是在原表的存儲空間內(nèi)將線性表(a1,a2,a3,an)逆置為( an, an-1,a2, al)。 基本要求 用順序存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置,并將結(jié)果輸出。 測試數(shù)據(jù) 由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù),如空表。 實現(xiàn)提示 設三個連續(xù)的指針,分別指向當前結(jié)點、當前結(jié)點的前趨、當前結(jié)點的后繼。
8、 選作內(nèi)容 利用單鏈表作為存儲結(jié)構(gòu)。 首先先建立線性表的帶頭結(jié)點的單鏈表表示形式, 之后在不 借助輔助結(jié)點空間的情況下實現(xiàn)單鏈表的逆置,并將結(jié)果輸出。4、長整數(shù)運算 問題描述 設計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算。 基本要求 利用雙項循環(huán)鏈表實現(xiàn)長整數(shù)的存儲, 每個結(jié)點含一個整型變量。 任何整型變量的范圍 是 -(215-1 ) (215-1 )。輸入和輸出形式:按中國對于長整數(shù)的表示習慣,每四位一組, 組間用逗號隔開。 測試數(shù)據(jù) (1)0 ;0;應輸出“ 0”。(2)-2345,6789 ;-7654,3211 ;應輸出“ -1,0000,0000”。(3)-9999,9999 ;1,0
9、000,0000,0000 ;應輸出“ 9999,0000,0001 ”。(4)1,0001,000 ;-1,0001,0001 ;應輸出“ 0”。(5)1,0001,0001 ;-1,0001,0000 ;應輸出“ 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ù)的符號。用其絕對值表示
10、元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。 兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的 一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。 選作內(nèi)容 修改上述程序,使它在整型量范圍是 - ( 2n-1 ) ( 2n-1 )的計算機上都能有效地運行。 其中, n 是由程序讀入的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。實習二 棧、隊列和遞歸算法設計僅僅認識到棧和隊列是兩種特殊的線性表是遠遠不夠的, 本次實習的目的在于使讀者深 入了解棧和隊列的特征, 以便在實際問題背景下靈活運用它們; 同時還將鞏固這兩種結(jié)構(gòu)的 構(gòu)造方法,接觸較復雜問題的遞歸算法設計。1 、數(shù)制轉(zhuǎn)換問題 問題描述 將十進制數(shù)N和其它d進制
11、數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題,其解決方案很多, 其中最簡單方法基于下列原理:即除 d 取余法。例如: (1348)10=(2504)8NN div 8N mod 8134816841682102125202從中我們可以看出,最先產(chǎn)生的余數(shù) 4 是轉(zhuǎn)換結(jié)果的最低位, 這正好符合棧的特性即后進先出的特性。所以可以用順序棧來模擬這個過程。 基本要求 對于鍵盤輸入的任意一個非負的十進制整數(shù), 打印輸出和其等值的八進制數(shù)。 由于上述 的計算過程是從低位到高位順序產(chǎn)生的八進制數(shù)的各個數(shù)位,而打印輸出, 一般來說應從高位到地位進行, 恰好和計算過程相反。 因此可以先將計算過程中得到的八進制數(shù)的各位進棧
12、, 待相對應的八進制數(shù)的各位均產(chǎn)生以后, 再使其按順序出棧, 并打印輸出。 即得到了和輸入 的十進制數(shù)相對應的八進制數(shù)。 測試數(shù)據(jù) 由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù)。2、回文判斷 問題描述 試寫一個算法,判斷依次讀入的一個以為結(jié)束符的字母序列,是否為形如序列1 &序列 2'模式的字符序列。其中序列1和序列 2 中都不含字符 &',且序列 2 是序列 1的逆序列。例如, a+b&b+a是屬該模式的字符序列,而1+3 &3 1'則不是。 實現(xiàn)提示 首先,序列 1 進棧,然后序列 1 出棧并和序列 2 比較。 測試數(shù)據(jù) 由
13、學生依據(jù)軟件工程的測試技術自己確定。 注意測試邊界數(shù)據(jù), 如序列 1 和序列 2均為 空串。3、商品貨架管理 問題描述 商品貨架可以看成一個棧, 棧頂商品的生產(chǎn)日期最早, 棧底商品的生產(chǎn)日期最近。 上 貨時,需要倒貨架,以保證生產(chǎn)日期較近的商品在較下的位置。 基本要求 針對一種特定商品,實現(xiàn)上述管理過程。 實現(xiàn)提示 用棧模擬貨架和周轉(zhuǎn)空間。 測試數(shù)據(jù) 由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù),如空棧。4、括號匹配的檢驗 問題描述 假設表達式中允許有兩種括號:圓括號和方括號,其嵌套的順序隨意,即( () )或( )等為正確格式, ( )或(均為不正確的格式。檢驗括號是否匹配的方法可
14、用“期待的緊迫程度”這個概念來描述。例如:考慮下列的括號序列: ( ) 1 2 3 4 5 6 7 8當計算機接受了第 1 個括號以后, 他期待著和其匹配的第 8 個括號的出現(xiàn), 然而等來的 卻是第 2個括號,此時第 1個括號“ ”只能暫時靠邊, 而迫切等待和第 2 個括號相匹配的 第 7 個括號“)”的出現(xiàn),類似的,因只等來了第3 個括號“ ”,此時,其期待的緊迫程度較第2個括號更緊迫, 則第2個括號只能靠邊, 讓位于第 3個括號,顯然第 3個括號的期待 緊迫程度高于第 2 個括號,而第 2 個括號的期待緊迫程度高于第 1 個括號;在接受了第 4 個括號之后, 第 3個括號的期待得到了滿足,
15、 消解之后, 第 2個括號的期待匹配就成了最急 迫的任務了,依次類推??梢娺@個處理過程正好和棧的特點相吻合。 基本要求 讀入圓括號和方括號的任意序列,輸出“匹配”或“此串括號匹配不合法”。 測試數(shù)據(jù) 輸入( (),結(jié)果“匹配”輸入 ( ) ,結(jié)果“此串括號匹配不合法” 實現(xiàn)提示 設置一個棧,每讀入一個括號,若是左括號,則作為一個新的更急迫的期待壓入棧中; 若是右括號, 并且和當前棧頂?shù)淖罄ㄌ栂嗥ヅ洌?則將當前棧頂?shù)淖罄ㄌ柾顺觯?繼續(xù)讀下一個 括號, 如果讀入的右括號和當前棧頂?shù)淖罄ㄌ柌黄ヅ洌?則屬于不合法的情況。 在初始和結(jié)束 時,棧應該是空的。 選作內(nèi)容 考慮增加大括號的情況。5、停車場管理
16、 問題描述 設停車場內(nèi)只有一個可停放 n 輛汽車的狹長通道, 且只有一個大門可供汽車進出。 汽車 在停車場內(nèi)按車輛到達時間的先后順序, 依次由北向南排列 (大門在最南端, 最先到達的第 一輛車停放在車場的最北端) ,若車場內(nèi)已停滿 n 輛汽車,則后來的汽車只能在門外的便道 上等候,一旦有車開走,則排在便道上的第一輛車即可開入;當停車場內(nèi)某輛車要離開時, 在它之后開入的車輛必須先退出車場為它讓路, 待該輛車開出大門外, 其它車輛再按原次序 進入車場, 每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。 測試數(shù)據(jù) 設 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ù)項: 汽車“到達”或“離去”信息、 汽車牌照號碼及到達 或離去的時刻,其中, A'表示到達;D'表示離去,E'表示輸入結(jié)束。 基本要求 以棧模擬停車場, 以隊列模擬車場外的便道, 按照從終端讀入的輸入數(shù)據(jù)序列進行模擬 管理。 每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項: 汽車“到達”
18、或“離去”信息、 汽車牌照號碼及到 達或離去的時刻, 對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為: 若是車輛到達, 則輸出汽車 在停車場內(nèi)或便道上的停車位置; 若是車離去; 則輸出汽車在停車場內(nèi)停留的時間和應交納 的費用(在便道上停留的時間不收費) 。棧以順序結(jié)構(gòu)實現(xiàn),隊列以鏈表實現(xiàn)。 實現(xiàn)提示 需另設一個棧, 臨時停放為給要離去的汽車讓路而從停車場退出來的汽車,也用順序存 儲結(jié)構(gòu)實現(xiàn)。 輸入數(shù)據(jù)按到達或離去的時刻有序。 棧中每個元素表示一輛汽車, 包含兩個數(shù) 據(jù)項:汽車的牌照號碼和進入停車場的時刻。 選作內(nèi)容 ( 1) 兩個棧共享空間,思考應開辟數(shù)組的空間是多少?( 2) 汽車可有不同種類,則它
19、們的占地面積不同,收費標準也不同,如1 輛客車和1.5 輛小汽車的占地面積相同, 1 輛十輪卡車占地面積相當于 3 輛小汽車的占地面積。( 3) 汽車可以直接從便道上開走, 此時排在它前面的汽車要先開走讓路,然后再依次 排到隊尾。( 4) 停放在便道上的汽車也收費, 收費標準比停放在停車場的車低, 請思考如何修改 結(jié)構(gòu)以滿足這種要求。實習三 串及其使用本次實習的目的是熟悉串類型的實現(xiàn)方法和文本模式匹配方法, 熟悉一般文字處理軟件 的設計方法, 較復雜問題的分解求精方法, 在第二次實習的基礎上, 進一步強化這樣一個觀 念:程序是數(shù)據(jù)結(jié)構(gòu)結(jié)合定義在其上的操作, 此外還希望起到訓練合作能力和熟悉文件
20、操作 的目的。本次實習的難度較大。1、文學研究助手 問題描述 文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。 試寫一個實現(xiàn)這 一目標的文字統(tǒng)計系統(tǒng),稱為“文學研究助手”。 基本要求 英文小說存于一個文本文件中。 待統(tǒng)計的詞匯集合要一次輸入完畢, 即統(tǒng)計工作必須在 程序的一次運行之后就全部完成。 程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的 行號,格式自行設計。 測試數(shù)據(jù) 以你的源程序模擬英文小說,程序語言保留字集作為待統(tǒng)計的詞匯集。 實現(xiàn)提示 設小說中的詞匯一律不跨行。這樣,每讀入一行,就統(tǒng)計每個詞在這行中的出現(xiàn)次數(shù)。 出現(xiàn)位置所在行的行號可以用鏈表存儲。 若某行中出現(xiàn)了
21、不止一次, 不必存多個相同的行號。如果讀者希望達到選作部分(1 )和(2)所提出的要求,則首先應把 KMP算法改寫成如 下的等價形式,再將它推廣到多個模式的情形。 選作內(nèi)容 (1)模式匹配要基于 KMP算法。( 2) 整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。( 3) 假設小說中的每個單詞或者從行首開始,或者前置以一個空格符。利用單詞匹配 特點另寫一個高效的統(tǒng)計程序,和KMP算法統(tǒng)計程序進行效率比較。( 4) 推廣到更一般的模式集匹配問題,并設待查模式串可以跨行(提示:定義操作 getachar )2、簡單行編輯程序 問題描述 文本編輯程序是利用計算機進行文字加工的基本軟件工具,實現(xiàn)對文本
22、文件的插入、 刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大,全部讀入編輯程序的數(shù)據(jù)空間(內(nèi)存)的做法既不經(jīng)濟, 也不總能實現(xiàn)。 一種解決方法是逐段地編輯。 任何時刻只把待編輯文件的一段放在內(nèi)存, 稱 為活區(qū)。 試按照這種方法實現(xiàn)一個簡單的行編輯程序。 設文件每行不超過 320 個字符, 很少 超過 80 字符。 基本要求 實現(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,表示插入當前屏幕中第一行之前,否則命令參數(shù)非法。 測試數(shù)據(jù) 由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù),如首行、尾行。 實現(xiàn)提示 (1) 設活區(qū)的大小用行數(shù) activemaxle
24、n (可設為 100)來描述??紤]到文本文件行長通常為正態(tài)分布,且峰值在60到70之間,用320x activemaxlen 大小的字符數(shù)組實現(xiàn)存儲 將造成大量浪費??梢砸詷藴市袎K為單位為各行分配存儲,每個標準行塊含81 個字符。這些行塊可以組成一個數(shù)組, 也可以利用動態(tài)鏈表連接起來。 一行文字可能占多個行塊。 行尾 可用一個特殊的 ASCII 字符(如 (012)8 )標識。此外,還應記住活區(qū)起始行號。行插入將引 起隨后各行行號的順序下推。( 2) 初始化過程包括: 請用戶提供輸入文件名 (空串表示無輸入文件) 和輸出文件名, 兩者不能相同。然后盡可能多地從輸入文件中讀入各行,但不超過act
25、ivemaxlen-x °x的值可以自定,例如 20。( 3) 在執(zhí)行行插入命令的過程中,每接收到一行時到要檢查活區(qū)大小是否已達 activemaxlen 。如果是,則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen ,應將插入點之前的活區(qū)部分中第一行輸出到輸出文件中; 若插入點為第一行之前, 則只得將 新插入的這一行輸出。( 4) 若輸入文件尚未讀完,活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部,以保持閱讀連續(xù)性;否則,它意味著結(jié)束編輯或開始編輯另一個文件。( 5) 可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示。 選作內(nèi)容 ( 1 ) 對于命令格式非法等一切錯誤作嚴格檢查和
26、適當處理。(2) 加入更復雜的編輯操作,如對某行進行串替換;在活區(qū)內(nèi)進行模式匹配等,格式可以為S亍號串1串 2回車和口串 回車。實習四 樹、圖及其使用樹和圖是兩種使用極為廣泛的數(shù)據(jù)結(jié)構(gòu), 也是這門課程的重點。 它們的特點在于非線性。廣義表本質(zhì)上是樹結(jié)構(gòu);稀疏矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu),故也把它們歸在這次實習中。本章實習繼續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設計觀點,但根據(jù)這兩種結(jié)構(gòu)的非線性特點,將操作進一步集中在遍歷操作上,因為遍歷操作是其他眾多操作的基礎。遍歷邏輯的(或符號形式的)結(jié)構(gòu),訪問動作可是任何操作。本次實習還希望達到熟悉各種存 儲結(jié)構(gòu)的特征,以及如何使用樹和圖結(jié)構(gòu)解決具體問
27、題(即原理和使用的結(jié)合)等目的。1、二叉樹的建立和遍歷問題描述建立一棵二叉樹,并對其進行遍歷(先序、中序、后序),打印輸出遍歷結(jié)果?;疽髲逆I盤接受輸入(先序),以二叉鏈表作為存儲結(jié)構(gòu),建立二叉樹(以先序來建立),并采用遞歸算法對其進行遍歷(先序、中序、后序),將遍歷結(jié)果打印輸出。測試數(shù)據(jù)ABG © DE©F© ©© (其中©表示空格字符)則輸出結(jié)果為先序:ABCDEGF中序:CBEGDFA后序:CGBFDBA選作內(nèi)容采用非遞歸算法實現(xiàn)二叉樹遍歷。2、打印樹結(jié)構(gòu)問題描述按凹入表形式打印樹形結(jié)構(gòu)。CFEADB測試數(shù)據(jù)由學生依據(jù)軟件工程
28、的測試技術自己確定。注意測試邊界數(shù)據(jù),如空樹。 實現(xiàn)提示(1)利用樹的先根遍歷方法;(2)禾U用結(jié)點的深度控制橫向位置。3、哈夫曼編碼/譯碼器重復地顯示并處理以下項目,直到選擇退出為【問題描述】 設計一個利用哈夫曼算法的編碼和譯碼系統(tǒng), 止?!净疽蟆?1) 初始化:鍵盤輸入字符集大小 n、n個字符和n個權(quán)值,建立哈夫曼樹;(2) 編碼:利用建好的哈夫曼樹生成哈夫曼編碼;(3) 輸出編碼;(4) 設字符集及頻度如下表:字符 空格 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) 界面設計的優(yōu)化。4、圖遍歷的演示 問題描述 很多涉及圖上操作的算法都是以圖的遍歷操作為基礎的。 試寫一個程序, 演示無向圖的 遍歷操作。 基本要求 以鄰接表為存儲結(jié)構(gòu), 實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。 以用戶指定的結(jié)點 為起點,分別輸出每種遍歷下的結(jié)點訪問序列和相應生成樹的邊集。 測試數(shù)據(jù) 由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù),如單個結(jié)點。 實現(xiàn)提示 設圖的結(jié)點不超過 30 個,每個結(jié)點用一個編號表示
30、(如果一個圖有 n 個結(jié)點,則它們 的編號分別為1,2,n )。通過輸入圖的全部邊輸入一個圖,每個邊為一個數(shù)對,可以對邊 的輸入順序作出某種限制。注意,生成樹的邊是有向邊,端點順序不能顛倒。 選作內(nèi)容 (1) 借助于棧類型(自己定義和實現(xiàn))將深度優(yōu)先遍歷用非遞歸算法實現(xiàn)。( 2) 以鄰接多重表為存儲結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹,再按凹入表或樹形打印生成樹(3) 實現(xiàn)有向圖的遍歷操作。實習五 查找和排序本次實習旨在集中對幾個專門的問題作較為深入的探討和理解,不強調(diào)對某些特定的編程技術的訓練。1 、二叉排序樹 問題描述 從鍵盤讀入一組數(shù)據(jù), 建立二叉排序樹并對其進行查找、 遍歷、格式化打
31、印等有關操作。 基本要求 建立二叉排序樹并對其進行查找,包括成功和不成功兩種情況,并給出查找長度。 測試數(shù)據(jù) 由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù)。 選作內(nèi)容 實現(xiàn)二叉排序樹的插入、刪除操作。2、哈希表設計 問題描述 針對某個集體中人名設計一個哈希表,使得平均查找長度不超過R,并完成相應的建表和查表程序。 基本要求 假設人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30 個,取平均查找長度的上限為 2。哈希函數(shù)用除留余數(shù)法構(gòu)造,用線性探測再散列法或鏈地址法處理沖突。 測試數(shù)據(jù) 取讀者周圍較熟悉的 30 個人名。 選作內(nèi)容 (1)從教科書上介紹的集中哈希函數(shù)構(gòu)造方法中選
32、出適用者并設計幾個不同的哈希函 數(shù),比較他們的地址沖突率(可以用更大的名字集合作實驗) 。(2)研究這 30 個人名的特點,努力找一個哈希函數(shù),使得對于不同的拼音名一定不 發(fā)生地址沖突。(3) 在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法,考察平均查找長度的變 化和造好的哈希表中關鍵字的聚集性。3、內(nèi)部排序算法比較 問題描述 各種內(nèi)部排序算法的時間復雜度分析結(jié)果只給出了算法執(zhí)行時間的階,或大概執(zhí)行時 間。試通過隨機的數(shù)據(jù)比較各算法的關鍵字比較次數(shù)和關鍵字移動次數(shù),以取得直觀感受。 基本要求 (1)對以下 10 種常用的內(nèi)部排序算法進行比較:直接插入排序;折半折入排序;二 路插入排序;希爾排
33、序;起泡排序;快速排序;簡單選擇排序;堆排序;歸并排序;基數(shù)排 序。(2)待排序表的表長不少于 100;其中的數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生;至少要用5 組不同的輸入數(shù)據(jù)作比較;比較的指標為有關鍵字參加的比較次數(shù)和關鍵字移動次數(shù)(關 鍵字交換計為 3 次移動)。 測試數(shù)據(jù) 由隨機產(chǎn)生器決定。 實現(xiàn)提示 主要工作是設法在程序中適當?shù)牡胤讲迦胗嫈?shù)操作。 程序還可以包括計算幾組數(shù)據(jù)得出 結(jié)果波動大小的解釋。注意分塊調(diào)試的方法。 選作內(nèi)容 對不同的輸入表長做試驗, 觀察檢查兩個指標相關于表長的變化關系。 還可以對穩(wěn)定性 做驗證。3、統(tǒng)計成績 問題描述 給出n個學生的m門測試的成績表,每個學生的信息由學號
34、、姓名以及各科成績組成。 對學生的測試成績進行有關統(tǒng)計,并打印統(tǒng)計表。 基本要求 (1)按總數(shù)高低次序,打印出名次表,分數(shù)相同的為同一名次;(2)按名次打印出每個學生的學號、姓名、總分以及各科成績。 測試數(shù)據(jù) 由學生依據(jù)軟件工程的測試技術自己確定。注意測試邊界數(shù)據(jù)。 選作內(nèi)容 對各科成績設置不同的權(quán)值。附錄 2 實驗報告示例級 班 年 月日 姓名 學號 電話1實驗題目編制一個演示單鏈表插入、刪除、查找等操作的程序2需求分析本演示程序用TC編寫,完成單鏈表的生成,任意位置的插入、刪除,以及確定某一元 素在單鏈表中的位置。 輸入的形式和輸入值的范圍:插入元素時需要輸入插入的位置和元素的值;刪除元
35、素時輸入刪除元素的位置; 查找操作時需要輸入元素的值。 在所有輸入中, 元素的值都是整 數(shù) 輸出的形式:在所有三種操作中都顯示操作是否正確以及操作后單鏈表的內(nèi)容。其 中刪除操作后顯示刪除的元素的值,查找操作后顯示要查找元素的位置。 程序所能達到的功能:完成單鏈表的生成(通過插入操作) 、插入、刪除、查找操作 測試數(shù)據(jù):A 插入操作中依次輸入B 查找操作中依次輸入C 刪除操作中依次輸入11, 12, 13, 14, 15, 16,生成一個單鏈表12, 15, 22 返回這 3 個元素在單鏈表中的位置2, 5,刪除位于 2 和 5 的元素3概要設計1) 為了實現(xiàn)上述程序功能,需要定義單鏈表的抽象數(shù)
36、據(jù)類型:ADT LinkList 數(shù)據(jù)對象:D=ai|ai IntegerSet,i=0,1,2,n,n > 0數(shù)據(jù)關系: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ù)間關系如下:mainInitLinkListJlenuDispLinkList InsLinkListDelLinkList L
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 公司聯(lián)誼現(xiàn)場活動方案
- 公司擺攤美食活動方案
- 公司自制活動策劃方案
- 公司男女活動策劃方案
- 公司春季燒烤活動方案
- 公司旅游活動策劃方案
- 公司組員聚會活動方案
- 公司洞頭團建活動方案
- 公司聚餐系列活動方案
- 公司組織撕名牌活動方案
- 浙江省強基聯(lián)盟學考模擬2024-2025學年高二下學期6月學考模擬地理試題(含答案)
- 中國美術學院非教學崗位招聘筆試真題2024
- 人形機器人深度研究系列八:諧波減速器:差齒傳動持續(xù)進化
- 公立醫(yī)院風險評估報告
- 腫瘤婦科進修匯報
- 麻醉意外與并發(fā)癥處理規(guī)范與流程
- 危險化學品臨界量表(參考)
- 墻柱梁板混凝土同時澆筑方案.doc
- 新生兒視覺訓練黑白卡(整理90張必備圖卡)
- 礦山地質(zhì)環(huán)境恢復治理方案治理經(jīng)費估算計算部分
- 大學遺傳學期末考試題庫及答案參考
評論
0/150
提交評論