1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實驗講義課程簡介課程名稱：數(shù)據(jù)結(jié)構(gòu)授課對象：計算機科學(xué)與技術(shù) 本科教材版本：數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社學(xué)時：85 其中：理論：68 實驗：17授課教師：高云電子郵箱：gaoyunchina實驗一(必做, 基本實驗，4學(xué)時)實驗題目：多項式乘法問題實驗?zāi)康模涸O(shè)計一個一元稀疏多項式簡單計算器。實驗內(nèi)容與要求 一元稀疏多項式簡單計算器的基本功能是： （1)輸入并建立多項式； （2）輸出多項式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2,.,cn,en,其中n是多項式的項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列。 （3）多項式a與多項式b

2、相乘，建立多項式。實驗內(nèi)容和實驗步驟：（由學(xué)生填寫）實驗用測試數(shù)據(jù)和相關(guān)結(jié)果分析：（由學(xué)生填寫）實驗總結(jié)：（由學(xué)生填寫）實驗二(必做, 設(shè)計性實驗，4學(xué)時)實驗題目：迷宮的求解實驗內(nèi)容與要求： 迷宮只有兩個門，一個叫做入口，另一個叫做出口。把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口。求解迷宮問題，即找出從入口到出口的路徑。 【知識要點】 迷宮問題是棧應(yīng)用的一個典型例子。求解過程可采用回溯法?；厮莘ㄊ且环N不斷試探且及時糾正錯誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通

3、（未走過的），即某處可以到達，則到達新點，否則試探下一方向 ; 若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點。在求解過程中，為了保證在到達某一點后不能向前繼續(xù)行走（無路）時，能正確返回前一點以便繼續(xù)從下一個方向向前試探，則需要用一個棧保存所能夠到達的每一點的下標及從該點前進的方向，棧中保存的就是一條迷宮的通路。 為了確保程序能夠終止，調(diào)整時，必須保證曾被放棄過的填數(shù)序列不被再次試驗，即要求按某種有序模型生成填數(shù)序列。給解的候選者設(shè)定一個被檢驗的順序，按這個順序逐一生成候選者并檢驗。 【實現(xiàn)提示】 對于迷

4、宮問題，用回溯法的難點就在如何為解空間排序，以確保曾被放棄過的填數(shù)序列不被再次試驗，在二維迷宮里面，從出發(fā)點開始，每個點按四鄰域算，按照右、上、左、下的順序搜索下一落腳點，有路則進，無路即退，前點再從下一個方向搜索，即可構(gòu)成一有序模型。實驗內(nèi)容和實驗步驟：（由學(xué)生填寫）實驗用測試數(shù)據(jù)和相關(guān)結(jié)果分析：（由學(xué)生填寫）實驗總結(jié)：（由學(xué)生填寫）實驗三（必做，基本實驗，4學(xué)時）實驗題目：Huffman樹及Huffman編碼的算法實現(xiàn)實驗?zāi)康模?、 了解該樹的應(yīng)用實例，熟悉掌握Huffman樹的構(gòu)造方法及Huffman編碼的應(yīng)用，2、 了解Huffman樹在通信、編碼領(lǐng)域的應(yīng)用過程。實驗要求：1、 輸入一

5、段100200字的英文短文，存入一文件a中。Mr. JohnsonZ had never been up in an aerophane before and he had read a lot about air accidents, so one day when a friend offered to take him for a ride in his own small phane, Mr. Johnson was very worried about accepting. Finally, however, his friend persuaded him that it was

6、very safe, and Mr. Johnson boarded the plane. His friend started the engine and began to taxi onto the runway of the airport. Mr. Johnson had heard that the most dangerous part of a flight were the take-off and the landing, so he was extremely frightened and closed his eyes. After a minute or two he

7、 opened them again, looked out of the window of the plane, and said to his friend, "Look at those people down there. They look as small as ants, don't they?" "Those are ants," answered his friend. "We're still on the ground."2、寫函數(shù)統(tǒng)計短文出現(xiàn)的字母個數(shù)n及每個字母的出現(xiàn)次數(shù)3、寫函數(shù)以字母出現(xiàn)

8、次數(shù)作權(quán)值，建Haffman樹（n個葉子），給出每個字母的Haffman編碼。4、用每個字母編碼對原短文進行編碼，碼文存入文件b中。5、用Haffman樹對b中碼文進行譯碼，結(jié)果存入文件c中，比較a,c是否一致，以檢驗編碼、譯碼的正確性。實驗內(nèi)容和實驗步驟：（由學(xué)生填寫）實驗用測試數(shù)據(jù)和相關(guān)結(jié)果分析：（由學(xué)生填寫）實驗總結(jié)：（由學(xué)生填寫）實驗四（必做，設(shè)計性實驗，6學(xué)時）實驗題目：校園導(dǎo)游咨詢實驗?zāi)康模赫莆請D的存儲方法和最短路經(jīng)算法。實驗內(nèi)容：設(shè)計一個校園導(dǎo)游程序，為來訪客人提供各種信息查詢服務(wù)。測試數(shù)據(jù)根據(jù)實際情況指定。提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向圖。頂

9、點和邊均含有相關(guān)信息。實驗要求： 1、設(shè)計所在學(xué)校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。 2、為來訪客人提供圖中任意景點相關(guān)信息的查詢。 3、為來訪客人提供圖中任意景點的紋路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。實驗內(nèi)容和實驗步驟：（由學(xué)生填寫）實驗用測試數(shù)據(jù)和相關(guān)結(jié)果分析：（由學(xué)生填寫）實驗總結(jié)：（由學(xué)生填寫）附錄：實驗報告的要求實驗報告是反映學(xué)生實驗效果的最主要的依據(jù)，也是學(xué)生正確地表達問題、綜合問題和發(fā)現(xiàn)問題的能力的基本培養(yǎng)手段，因而是非常重要的內(nèi)容，本課程的實驗報告中要包括以下幾項內(nèi)容： （一） 實驗題目；（二） 實驗?zāi)康?；（三?實驗要求；（四） 實驗內(nèi)容和實驗步驟；1需求分析：陳述程序設(shè)計的任務(wù)，強調(diào)程序要做什么，明確規(guī)定： （1）輸入的形式和輸入值的范圍； （2）輸出的形式； （3）程序所能實現(xiàn)的功能； 2概要設(shè)計：說明用到的數(shù)據(jù)結(jié)構(gòu)定義、主程序的流程及各程序模塊之間的調(diào)用關(guān)系。 3詳細設(shè)計：提交帶注釋的源程序或者用