級數(shù)據(jù)結(jié)構(gòu)實驗指導書-資料下載頁
2025-06-27 05:25本頁面
【正文】 （2） 原字符串及編碼串可從鍵盤輸入。（3） 生成Huffman樹的步驟如下：①由給定的 n 個權(quán)值{w1, w2, …, wn}構(gòu)成n棵二叉樹的集合（即森林）F = { T1, T2, …, Tn }，其中每棵二叉樹 Ti 中只有一個帶權(quán)為 wi 的根結(jié)點，其左右子樹均空。②在F 中選取兩棵根結(jié)點的權(quán)值最小的樹 做為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。③在F 中刪去這兩棵樹，同時將新得到的二叉樹加入 F中。④重復② 和③, 直到 F 只含一棵樹為止。這棵樹便是赫夫曼樹?！具x做內(nèi)容】（1） 字符的出現(xiàn)頻數(shù)能否從指定文件中統(tǒng)計而得？（2） 對指定的文件進行編碼/解碼。 實驗4 圖及其應(yīng)用實驗?zāi)康?. 加深對圖的結(jié)構(gòu)的理解；2. 熟練掌握圖的存儲結(jié)構(gòu)，特別是圖的鄰接表結(jié)構(gòu)；3. 熟練掌握圖的搜索算法原理及其實現(xiàn)；4. 掌握圖的常用的應(yīng)用方法。 實驗學時：建議2~4學時實驗內(nèi)容內(nèi)容1： 圖的搜索問題【問題描述】設(shè)計無向圖的鄰接表類并實現(xiàn)，演示在連通的無向圖上訪問全部結(jié)點的操作?！净疽蟆浚?）以鄰接表作為存儲結(jié)構(gòu)，并對圖進行深度優(yōu)先和廣度優(yōu)先搜索。（2）以指定結(jié)點為起點，分別輸出每種搜索方式下結(jié)點訪問序列和相應(yīng)生成樹邊集。【實現(xiàn)提示】（1）圖的每個結(jié)點用一個編號表示（如1~n）。通過輸入圖的全部邊來輸入一個圖，每個邊是一個數(shù)對。（2）數(shù)據(jù)結(jié)構(gòu)描述見教材。（3）無向圖的鄰接表類的主要成員函數(shù)：void createadjlist()；//建立圖的鄰接表void desttraverse(int k)；//圖的深度優(yōu)先搜索void besttraverse(int k)；//圖的廣度優(yōu)先搜索【選做內(nèi)容】借助棧，用非遞歸算法實現(xiàn)深度優(yōu)先搜索。內(nèi)容2： 教學計劃編制問題【問題描述】教學計劃中各課程之間必須滿足先修關(guān)系。每門課程的先修課程是確定的，可以有任意多門，也可以沒有。試在這樣的前提下設(shè)計一個教學計劃編制的程序?！净疽蟆浚?）輸入數(shù)據(jù)：學期總數(shù)、一學期學分上限、課程號、課程學分和先修課程課程號。（2）編排策略：使每學期的總學分數(shù)盡量均勻?！緦崿F(xiàn)提示】可設(shè)學期總數(shù)不超過12，課程總數(shù)不超過100?！具x做內(nèi)容】產(chǎn)生多種不同的方案，并使方案之間的差異盡可能大。 實驗5 查找實驗?zāi)康?．熟練掌握順序表和有序表的查找方法及算法實現(xiàn)。2．熟悉常用查找算法的編寫。3．理解靜態(tài)查找和折半查找的關(guān)系。4．熟練掌握二叉排序樹的構(gòu)造和查找方法。5．通過上機操作,理解如何科學地組織信息存儲,并選擇高效的查找算法。實驗學時：建議2學時實驗內(nèi)容內(nèi)容1： 基本查找算法【問題描述】設(shè)計一個程序，演示折半查找和二叉排序樹查找過程?！净疽蟆浚?）建立一棵二叉排序樹，采用二叉鏈表存儲結(jié)構(gòu)，并進行查找。（2）給出一組有序數(shù)，對其進行折半查找?！緦崿F(xiàn)提示】（1）可設(shè)計以下三個功能函數(shù)：status insertbst(bitree amp。bt,elemtype e)。//,插入e 并返回truesearchebst(bitree bt,keytype key)。//在根指針bt所指二叉樹中遞歸地查找關(guān)鍵字等于key的數(shù)據(jù)元素,若查找成功,則返回指向該數(shù)據(jù)元素結(jié)點的指針,否則返回空指針。int Search_Bin(SSTable ST，keytype key)；//折半查找算法（2）可設(shè)計遞歸算法?！具x做內(nèi)容】設(shè)計非遞歸算法。內(nèi)容2： 哈希表設(shè)計【問題描述】針對某集體中的“人名”設(shè)計一個哈希表類，完成相應(yīng)的建表和查表程序?！净疽蟆浚?）人名用漢語拼音，待填入哈希表的人名共30個。（2）哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法處理沖突。【實現(xiàn)提示】（1） 數(shù)據(jù)結(jié)構(gòu)設(shè)計人名用指向字符的指針表示，因而哈希表類可設(shè)計成線性結(jié)構(gòu)（即指針組）。（2） 設(shè)計以下的功能函數(shù)：status create_hash()。// 哈希表的建表操作int search_hash (name)。// 哈希表的查表操作【選做內(nèi)容】（1） 用鏈地址法處理沖突。（2） 通過分析給定人名的特點，設(shè)計出具有不（或較少）沖突的哈希函數(shù)。 實驗6 排序?qū)嶒災(zāi)康?．深刻理解排序的定義和各種排序方法的特點。2．了解各種方法的排序過程及其依據(jù)的原則。3．熟練掌握各種排序方法的時間復雜度的分析方法。4．了解排序的過程及適用場合。5．了解排序效果與采用算法的關(guān)系。6．通過上機,加深對排序算法的理解.實驗學時：建議2學時實驗內(nèi)容：內(nèi)部排序算法比較【問題描述】設(shè)計一個程序，通過隨機數(shù)據(jù)比較常用排序算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)?！净疽蟆浚?）對以下排序算法進行比較：起泡排序、簡單選擇排序、直接插入排序、快速排序。（2）用隨機數(shù)進行排序；至少用5組不同數(shù)據(jù)進行比較。（3）最后進行簡單分析?！緦崿F(xiàn)提示】在算法的適當位置插入對關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)的統(tǒng)計操作?！具x做內(nèi)容】對不同表長作試驗，觀察兩指標的變
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1