算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實驗1：線性表的操作（12學(xué)時）問題描述假設(shè)一個班級內(nèi)有n個學(xué)生,定義一個學(xué)生類和一個班級類。學(xué)生類中包括學(xué)號、姓名、性別、年齡、專業(yè)等屬性；班級類包括一個學(xué)生對象鏈表。定義如下：class Student int id; /學(xué)號 char name20; /姓名 int age; /年齡 /請設(shè)置學(xué)生類中相應(yīng)的操作 class MyClass Student *stu_head; /鏈表表頭指針 int total; /學(xué)生總數(shù) char manager20;/班主任姓名 / .public: MyClass()/創(chuàng)建新班,學(xué)生數(shù)為0 void insertStu(Student s); /在班內(nèi)中插入學(xué)生 s，插入后保持學(xué)號沒有重復(fù)并且按學(xué)號遞增 void deleteStu(int i) ; /刪除學(xué)號為i的學(xué)生 void display(); /顯示班內(nèi)所有學(xué)生的信息和其它信息 void search(int i);/按照學(xué)號i 查找學(xué)生，并輸出其信息 void search( char *s); /按照姓名查找學(xué)生，如果有重名的學(xué)生，則輸出所有學(xué)生 void join(MyClass &class2 ); /將class2班合并到本班，合并后保證學(xué)號沒有重復(fù)并且按學(xué)號遞增 void seperate(MyClass &c1,MyClass &c2);/按照性別分成兩個班c1和c2/ 其它方法 實驗?zāi)康模?） 掌握鏈表的基本操作。（2） 熟練類的定義以及類之間的關(guān)系實驗內(nèi)容及要求（1）實現(xiàn)MyClass類中所列出的方法；（2）編寫主函數(shù)測試類中的方法。算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實驗2：利用棧將中綴表達式轉(zhuǎn)換為后綴表達式并進行計算（3學(xué)時）問題描述 中綴表達式是最普通的一種書寫表達式的方式，而后綴表達式不需要用括號來表示，計算機可簡化對后綴表達式的計算過程，而該過程又是棧的一個典型應(yīng)用。實驗?zāi)康?（1） 深入理解棧的特性。（2） 掌握棧結(jié)構(gòu)的構(gòu)造方法。實驗內(nèi)容及要求（1） 中綴表達式中只包含、/ 運算及（ 和 ）。 （2） 可以輸入任意中綴表達式,數(shù)據(jù)為一位整數(shù)。（3） 顯示中綴表達式及轉(zhuǎn)換后的后綴表達式(為清楚起見，要求每輸出一個數(shù)據(jù)用逗號隔開)。（4） 對轉(zhuǎn)換后的后綴表達式進行計算。例如輸入：中綴表達式： 63*(9-7)-8/2 輸出：轉(zhuǎn)換后的后綴表達式為：6,3,9,7,-,*,+,8,2,- 計算結(jié)果為：8算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實驗3：行編輯程序問題（3學(xué)時）問題描述 一個簡單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。由于用戶在終端上進行輸入時，不能保證不出差錯，因此，若在編輯程序中，“每接受一個字符即存入用戶數(shù)據(jù)區(qū)”的做法顯然不是最恰當(dāng)?shù)?。較好的做法是，設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。例如，當(dāng)用戶發(fā)現(xiàn)剛剛鍵入的一個字符是錯的時，可補進一個退格符"#"，以表示前一個字符無效；如果發(fā)現(xiàn)當(dāng)前鍵入的行內(nèi)差錯較多或難以補救，則可以鍵入一個退行符""，以表示當(dāng)前行中的字符均無效。如果已經(jīng)在行首繼續(xù)輸入#符號無效。實驗?zāi)康模?） 深入理解棧的特性。（2） 掌握使用遞歸實現(xiàn)某些問題。（3） 設(shè)計出應(yīng)用棧解決在實際問題背景下對較復(fù)雜問題的遞歸算法。實驗內(nèi)容及要求（1）實現(xiàn)簡單行編輯器，可以輸入一個多行的字符序列。但行字符總數(shù)（包含退格符和退行符）不大于250。 （2）利用順序棧保存從終端接收的字符, 每行回車時顯示經(jīng)過編輯的本行字符, 例如：用戶輸入為：voL#idmia#ain()churchar ch;輸出為： void main() char ch;算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實驗4：隊列的應(yīng)用（6學(xué)時）問題描述實現(xiàn)一個簡單銀行叫號模擬系統(tǒng)。銀行有三個窗口可以同時辦理業(yè)務(wù)，當(dāng)有用戶到達銀行時，首先選擇自己要辦理的業(yè)務(wù)，可以選擇一種或多種。系統(tǒng)計算辦理此業(yè)務(wù)所需的時間并顯示給用戶，然后系統(tǒng)查看有無空閑的窗口，如果有，通知用戶到一個空閑窗口辦理，如果沒有空閑窗口，則需安排用戶到某個窗口等候，系統(tǒng)先計算每個隊列中用戶辦理業(yè)務(wù)的總時間，將用戶安排到時間最短的隊列等候。模擬輸出多個用戶辦理業(yè)務(wù)的過程。輸入舉例如下：用戶1在時間1到達銀行，在1號窗口辦理業(yè)務(wù)，需要1分鐘用戶1在時間2結(jié)束，離開用戶2在時間3達到。在1號窗口開始辦理，辦理業(yè)務(wù)需要4分鐘 用戶3在時間3到達，在2號窗口開始辦理，辦理業(yè)務(wù)需要5分鐘用戶4在時間5到達，在3號窗口開始辦理，辦理需要8分鐘用戶5在時間6到達，在1號窗口等待，辦理業(yè)需要4分鐘用戶2在時間8辦理完業(yè)務(wù)，離開用戶5在時間8在1號窗口，辦理業(yè)需要4分鐘用戶6在時間8到達，在1號窗口等待，辦理業(yè)務(wù)需要6分鐘用戶7在時間8到達，在2號窗口等待，辦理業(yè)務(wù)需要10分鐘 實驗?zāi)康模?）深入理解隊列的特性。（2）掌握使用隊列實現(xiàn)某些問題。實驗內(nèi)容及要求1建立3個隊列存儲在三個窗口等待的用戶2建立業(yè)務(wù)類，描述業(yè)務(wù)種類，業(yè)務(wù)所需時間3建立用戶類，描述用戶辦理的業(yè)務(wù)，用戶的狀態(tài)等4可以隨機產(chǎn)生用戶進入銀行的時間，讓用戶輸入所需辦理的業(yè)務(wù)。算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實驗5： 實現(xiàn)二叉樹的基本操作 (12學(xué)時)問題描述 樹和二叉樹是最常用的非線性結(jié)構(gòu)(樹型結(jié)構(gòu))，其中以二叉樹最為常見，本實驗題要求實現(xiàn)二叉樹的最基本操作，其中遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，它分為先序、中序和后序。實驗?zāi)康模?） 熟練掌握二叉樹的結(jié)構(gòu)特性。（2） 掌握二叉樹的各種存儲結(jié)構(gòu)的特點及實用范圍。（3） 通過二叉樹的基本操作的實現(xiàn)，從而思考一般樹的基本操作的實現(xiàn)。（4） 熟練掌握各種遍歷二叉樹的遞歸和非遞歸算法。實驗內(nèi)容及要求（1）用樹表示一個大家族的家譜。家譜樹中的結(jié)點表示家譜中的成員，包括編號，姓名，性別等信息。家譜樹的存儲結(jié)構(gòu)為二叉鏈表。根為祖先結(jié)點，每個結(jié)點的左子樹是其第一個孩子，右子樹是其下一個兄弟。（2）創(chuàng)建家譜樹：可以根據(jù)前序遍歷序列進行創(chuàng)建，也可以以其他方式創(chuàng)建。創(chuàng)建好之后寫入文件保存。（3）顯示家譜：在屏幕上以樹的形式或?qū)哟蔚男问斤@示家譜。（4）查詢：a.輸入一個結(jié)點值（編號或姓名），輸出其雙親及其所有子女，以及所有兄弟結(jié)點信息。 b. 輸入一個結(jié)點值（編號或姓名）,查詢他是祖先（根節(jié)點）的第幾代子孫。（5）插入：輸入一個結(jié)點值（編號姓名），插入一個結(jié)點作為其子女。（6）考慮家譜中是否允許有重名的情況。算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實驗6：查找算法（6學(xué)時）問題描述利用順序表實現(xiàn)順序查找、二分查找算法。實驗?zāi)康?、 掌握順序表的查找2、 掌握折半查找算法3、 對實際查找問題學(xué)會選用一種合適的查找算法求解4、比較不同查找算法的效率實驗內(nèi)容及要求（1）將實驗1的學(xué)生類Student中添加一個手機號碼屬性,在班級類Class中增加一個生成通訊錄的方法，該方法將全班同學(xué)的姓名（假設(shè)無重名）和手機號碼取出，存入一個順序結(jié)構(gòu)中，生成通訊錄，并寫入文件（以后可以直接從文件中讀取通訊錄）。（2）利用順序查找算法查找某學(xué)生的手機號碼。（3）按姓名排序，利用折半查找算法查找某學(xué)生的手機號碼。（4）統(tǒng)計并比較兩種算法中關(guān)鍵字的比較次數(shù)。（5）建議定義一個通訊錄類，將有關(guān)屬性和方法進行封裝。算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實驗7：哈夫曼樹的編/譯碼器系統(tǒng)的設(shè)計(9學(xué)時)問題描述利用哈夫曼編碼進行通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)進行預(yù)先編碼；在接受端將傳來的數(shù)據(jù)進行解碼（復(fù)原）。對于可以雙向傳輸?shù)男诺?，每端都要有一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。 實驗?zāi)康?（1） 通過哈夫曼樹的定義，掌握構(gòu)造哈夫曼樹的意義。（2） 掌握構(gòu)造哈夫曼樹的算法思想。（3） 通過具體構(gòu)造哈夫曼樹，進一步理解構(gòu)造哈夫曼樹編碼的意義。實驗內(nèi)容及要求(1) 建立哈夫曼樹：從終端讀入字符集大小為n（即字符的個數(shù)），逐一輸入n個字符和相應(yīng)的n個權(quán)值（即字符出現(xiàn)的頻度）如表1所示，建立哈夫曼樹，將它存于文件 hfmtree 中。并將建立好的哈夫曼樹以樹或凹入法形式輸出;對每個字符進行編碼并且輸出。(2) 編碼：利用已建好的哈夫曼編碼樹 ，對鍵盤輸入的正文進行譯碼。輸出字符正文，再輸出該文的二進制碼。 (3)譯碼：輸入一串二進制編碼，利用你建立的哈夫曼樹，將其進行譯碼，輸出字符正文。表1：字符集和及其頻度：字符ABCDEFGHIJKLMN頻度641322321032115475715322057字符OPQRSTUVWXYZ空格頻度63151485180238181161168并實現(xiàn)以下報文的譯碼和輸出：THIS PROGRAM IS MY FAVORITE 算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實 驗8：校園導(dǎo)游（12學(xué)時）問題描述 設(shè)計校園景點圖，包含校園各景點以及景點之間的路徑，所含景點不少于8個。以圖中頂點表示校園內(nèi)各景點，存放景點名稱、代號、簡介等信息，以邊表示景點之間的路徑，邊的權(quán)值表示路徑長度。設(shè)計一個校園導(dǎo)游程序，提供校園導(dǎo)游信息。 實驗?zāi)康?（1） 熟悉圖的兩種常用的存儲結(jié)構(gòu)。（2） 掌握對圖的兩種遍歷方法，即深度優(yōu)先遍歷和廣度優(yōu)先遍歷。進一步掌握利用遞歸或隊列結(jié)構(gòu)進行算法設(shè)計方法。（3） 掌握prime算法和最短路徑算法實驗內(nèi)容及要求（1）景點查詢：輸入景點名稱或編號，提供景點相關(guān)信息的查詢。（2）分別按照深度優(yōu)先和廣度優(yōu)先算法，將校園每個景點的信息輸出且僅輸出一次。（3）利用Priml算法求圖的最小生成樹，設(shè)計使各個景點之間連通代價最小的一種方案。（4）提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短路徑。算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學(xué)院 專業(yè) 姓名 學(xué)號 實 驗9：內(nèi)部排序算法比較 （9學(xué)時）問題描述排序是計算機程序設(shè)計中一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列重新排列成一個按關(guān)鍵字有序的序列。本實驗熟悉幾種典型的排序方法，并對各種算法的特點、使用范圍和效率進行進一步的了解。實驗?zāi)康?（1） 深刻理解排序的定義和各類排序的算法思想，并能靈活應(yīng)用。（2） 掌握各類排序的時間復(fù)雜度的分析方法，能從“關(guān)鍵字間的比較次數(shù)”分析算法的平均情況、最好情況和最壞情況。（3） 理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。實驗內(nèi)容及要求 數(shù)據(jù)由輸入或隨機函數(shù)產(chǎn)生。 實現(xiàn)簡單插入排序、簡單選擇排序、快速排序、堆排序和歸并排序算法等。 至少要用5組不同的輸入數(shù)據(jù)做比較（每組數(shù)據(jù)不小于100，應(yīng)考慮正序、逆序和隨機序列），統(tǒng)計關(guān)鍵字的比較次數(shù)和移動次數(shù)（需在算法的適當(dāng)位置插入對關(guān)鍵字的比較次數(shù)和移動次數(shù)的計數(shù)）、穩(wěn)定性、最好情況、最壞情況、平均情況等。 對結(jié)果做出簡單的分析。 第10頁