《《算法與數(shù)據(jù)結(jié)構(gòu)》》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》（10頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號 實(shí)驗(yàn)1：線性表的操作（12學(xué)時） [問題描述] 假設(shè)一個班級內(nèi)有n個學(xué)生,定義一個學(xué)生類和一個班級類。學(xué)生類中包括學(xué)號、姓名、性別、年齡、專業(yè)等屬性；班級類包括一個學(xué)生對象鏈表。定義如下： class Student { int id; //學(xué)號 char name[20]; //姓名 int age; //年齡 //請?jiān)O(shè)置學(xué)生類中相應(yīng)的操作 } class MyClass{ Stud

2、ent *stu_head; //鏈表表頭指針 int total; //學(xué)生總數(shù) char manager[20];//班主任姓名 // ..... 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é)生，并輸出其信息

3、 void search( char *s); //按照姓名查找學(xué)生，如果有重名的學(xué)生，則輸出所有學(xué)生 void join(MyClass &class2 ); //將class2班合并到本班，合并后保證學(xué)號沒有重復(fù)并且按學(xué)號遞增 void seperate(MyClass &c1,MyClass &c2);//按照性別分成兩個班c1和c2 // 其它方法 } [實(shí)驗(yàn)?zāi)康腯 （1） 掌握鏈表的基本操作。 （2） 熟練類的定義以及類之間的關(guān)系 [實(shí)驗(yàn)內(nèi)容及要求] （1）實(shí)現(xiàn)MyClass類中所列出的方法； （2）編寫主函數(shù)測試類中的方法。 《算法與數(shù)據(jù)

4、結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號 實(shí)驗(yàn)2：利用棧將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式并進(jìn)行計(jì)算（3學(xué)時） [問題描述] 中綴表達(dá)式是最普通的一種書寫表達(dá)式的方式，而后綴表達(dá)式不需要用括號來表示，計(jì)算機(jī)可簡化對后綴表達(dá)式的計(jì)算過程，而該過程又是棧的一個典型應(yīng)用。 [實(shí)驗(yàn)?zāi)康腯 （1） 深入理解棧的特性。 （2） 掌握棧結(jié)構(gòu)的構(gòu)造方法。 [實(shí)驗(yàn)內(nèi)容及要求] （1） 中綴表達(dá)式中只包含＋、－、、/ 運(yùn)算及（ 和 ）。 （2） 可以輸入任意中綴表達(dá)式,數(shù)據(jù)為一位整數(shù)。 （3） 顯

5、示中綴表達(dá)式及轉(zhuǎn)換后的后綴表達(dá)式(為清楚起見，要求每輸出一個數(shù)據(jù)用逗 號隔開)。 （4） 對轉(zhuǎn)換后的后綴表達(dá)式進(jìn)行計(jì)算。 例如輸入：中綴表達(dá)式： 6＋3*(9-7)-8/2 輸出：轉(zhuǎn)換后的后綴表達(dá)式為：6,3,9,7,-,*,+,8,2,- 計(jì)算結(jié)果為：8 《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號 實(shí)驗(yàn)3：行編輯程序問題（3學(xué)時） [問題描述] 一個簡單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的

6、數(shù)據(jù)區(qū)。由于用戶在終端上進(jìn)行輸入時，不能保證不出差錯，因此，若在編輯程序中，“每接受一個字符即存入用戶數(shù)據(jù)區(qū)”的做法顯然不是最恰當(dāng)?shù)?。較好的做法是，設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。例如，當(dāng)用戶發(fā)現(xiàn)剛剛鍵入的一個字符是錯的時，可補(bǔ)進(jìn)一個退格符"#"，以表示前一個字符無效；如果發(fā)現(xiàn)當(dāng)前鍵入的行內(nèi)差錯較多或難以補(bǔ)救，則可以鍵入一個退行符"@"，以表示當(dāng)前行中的字符均無效。如果已經(jīng)在行首繼續(xù)輸入#符號無效。 [實(shí)驗(yàn)?zāi)康腯 （1） 深入理解棧的特性。 （2） 掌握使用遞歸實(shí)現(xiàn)某些問題。 （3） 設(shè)計(jì)出應(yīng)用棧解

7、決在實(shí)際問題背景下對較復(fù)雜問題的遞歸算法。 [實(shí)驗(yàn)內(nèi)容及要求] （1）實(shí)現(xiàn)簡單行編輯器，可以輸入一個多行的字符序列。但行字符總數(shù)（包含退格符和退行符）不大于250。 （2）利用順序棧保存從終端接收的字符, 每行回車時顯示經(jīng)過編輯的本行字符, 例如：用戶輸入為： voL#idmia##ain(){ chur@char ch; 輸出為： void main(){ char ch; 《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號 實(shí)驗(yàn)4：隊(duì)列

8、的應(yīng)用（6學(xué)時） [問題描述] 實(shí)現(xiàn)一個簡單銀行叫號模擬系統(tǒng)。銀行有三個窗口可以同時辦理業(yè)務(wù)，當(dāng)有用戶到達(dá)銀行時，首先選擇自己要辦理的業(yè)務(wù)，可以選擇一種或多種。系統(tǒng)計(jì)算辦理此業(yè)務(wù)所需的時間并顯示給用戶，然后系統(tǒng)查看有無空閑的窗口，如果有，通知用戶到一個空閑窗口辦理，如果沒有空閑窗口，則需安排用戶到某個窗口等候，系統(tǒng)先計(jì)算每個隊(duì)列中用戶辦理業(yè)務(wù)的總時間，將用戶安排到時間最短的隊(duì)列等候。模擬輸出多個用戶辦理業(yè)務(wù)的過程。輸入舉例如下： 用戶1在時間1到達(dá)銀行，在1號窗口辦理業(yè)務(wù)，需要1分鐘 用戶1在時間2結(jié)束，離開 用戶2在時間3達(dá)到。在1號窗口開始辦理，辦理業(yè)務(wù)需要4分鐘 用戶3在時

9、間3到達(dá)，在2號窗口開始辦理，辦理業(yè)務(wù)需要5分鐘 用戶4在時間5到達(dá)，在3號窗口開始辦理，辦理需要8分鐘 用戶5在時間6到達(dá)，在1號窗口等待，辦理業(yè)需要4分鐘 用戶2在時間8辦理完業(yè)務(wù)，離開 用戶5在時間8在1號窗口，辦理業(yè)需要4分鐘 用戶6在時間8到達(dá)，在1號窗口等待，辦理業(yè)務(wù)需要6分鐘 用戶7在時間8到達(dá)，在2號窗口等待，辦理業(yè)務(wù)需要10分鐘 [實(shí)驗(yàn)?zāi)康腯 （1）深入理解隊(duì)列的特性。 （2）掌握使用隊(duì)列實(shí)現(xiàn)某些問題。 [實(shí)驗(yàn)內(nèi)容及要求] 1．建立3個隊(duì)列存儲在三個窗口等待的用戶 2．建立業(yè)務(wù)類，描述業(yè)務(wù)種類，業(yè)務(wù)所需時間 3．建立用戶類，描述用戶辦理的業(yè)務(wù)，用戶

10、的狀態(tài)等 4．可以隨機(jī)產(chǎn)生用戶進(jìn)入銀行的時間，讓用戶輸入所需辦理的業(yè)務(wù)。 《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號 實(shí)驗(yàn)5： 實(shí)現(xiàn)二叉樹的基本操作 (12學(xué)時) [問題描述] 樹和二叉樹是最常用的非線性結(jié)構(gòu)(樹型結(jié)構(gòu))，其中以二叉樹最為常見，本實(shí)驗(yàn)題要求實(shí)現(xiàn)二叉樹的最基本操作，其中遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，它分為先序、中序和后序。 [實(shí)驗(yàn)?zāi)康腯 （1） 熟練掌握二叉樹的結(jié)構(gòu)特性。 （2） 掌握二叉樹的各種存儲結(jié)構(gòu)的特點(diǎn)及實(shí)用范圍。 （3） 通過二叉樹

11、的基本操作的實(shí)現(xiàn)，從而思考一般樹的基本操作的實(shí)現(xiàn)。 （4） 熟練掌握各種遍歷二叉樹的遞歸和非遞歸算法。 [實(shí)驗(yàn)內(nèi)容及要求] （1）用樹表示一個大家族的家譜。家譜樹中的結(jié)點(diǎn)表示家譜中的成員，包括編號，姓名，性別等信息。家譜樹的存儲結(jié)構(gòu)為二叉鏈表。根為祖先結(jié)點(diǎn)，每個結(jié)點(diǎn)的左子樹是其第一個孩子，右子樹是其下一個兄弟。 （2）創(chuàng)建家譜樹：可以根據(jù)前序遍歷序列進(jìn)行創(chuàng)建，也可以以其他方式創(chuàng)建。創(chuàng)建好之后寫入文件保存。 （3）顯示家譜：在屏幕上以樹的形式或?qū)哟蔚男问斤@示家譜。 （4）查詢：a.輸入一個結(jié)點(diǎn)值（編號或姓名），輸出其雙親及其所有子女，以及所有兄弟結(jié)點(diǎn)信息。 b.

12、 輸入一個結(jié)點(diǎn)值（編號或姓名）,查詢他是祖先（根節(jié)點(diǎn)）的第幾代子孫。 （5）插入：輸入一個結(jié)點(diǎn)值（編號姓名），插入一個結(jié)點(diǎn)作為其子女。 （6）考慮家譜中是否允許有重名的情況。 《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號 實(shí)驗(yàn)6：查找算法（6學(xué)時） [問題描述] 利用順序表實(shí)現(xiàn)順序查找、二分查找算法。 [實(shí)驗(yàn)?zāi)康腯 1、 掌握順序表的查找 2、 掌握折半查找算法 3、 對實(shí)際查找問題學(xué)會選用一種合適的查找算法求解 4、比較不同查找算法的效率 [實(shí)驗(yàn)內(nèi)容及要求

13、] （1）將實(shí)驗(yàn)1的學(xué)生類Student中添加一個手機(jī)號碼屬性,在班級類Class中增加一個生成通訊錄的方法，該方法將全班同學(xué)的姓名（假設(shè)無重名）和手機(jī)號碼取出，存入一個順序結(jié)構(gòu)中，生成通訊錄，并寫入文件（以后可以直接從文件中讀取通訊錄）。 （2）利用順序查找算法查找某學(xué)生的手機(jī)號碼。 （3）按姓名排序，利用折半查找算法查找某學(xué)生的手機(jī)號碼。 （4）統(tǒng)計(jì)并比較兩種算法中關(guān)鍵字的比較次數(shù)。 （5）建議定義一個通訊錄類，將有關(guān)屬性和方法進(jìn)行封裝。 《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號

14、 實(shí)驗(yàn)7：哈夫曼樹的編/譯碼器系統(tǒng)的設(shè)計(jì)(9學(xué)時) [問題描述] 利用哈夫曼編碼進(jìn)行通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)進(jìn)行預(yù)先編碼；在接受端將傳來的數(shù)據(jù)進(jìn)行解碼（復(fù)原）。對于可以雙向傳輸?shù)男诺溃慷硕家幸粋€完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。 [實(shí)驗(yàn)?zāi)康腯 （1） 通過哈夫曼樹的定義，掌握構(gòu)造哈夫曼樹的意義。 （2） 掌握構(gòu)造哈夫曼樹的算法思想。 （3） 通過具體構(gòu)造哈夫曼樹，進(jìn)一步理解構(gòu)造哈夫曼樹編碼的意義。 [實(shí)驗(yàn)內(nèi)容及要求] (1) 建立哈夫曼樹：從

15、終端讀入字符集大小為n（即字符的個數(shù)），逐一輸入n個字符和相應(yīng)的n個權(quán)值（即字符出現(xiàn)的頻度）如表1所示，建立哈夫曼樹，將它存于文件 hfmtree 中。并將建立好的哈夫曼樹以樹或凹入法形式輸出;對每個字符進(jìn)行編碼并且輸出。 (2) 編碼：利用已建好的哈夫曼編碼樹 ，對鍵盤輸入的正文進(jìn)行譯碼。輸出字符正文，再輸出該文的二進(jìn)制碼。 (3)譯碼：輸入一串二進(jìn)制編碼，利用你建立的哈夫曼樹，將其進(jìn)行譯碼，輸出字符正文。 表1：字符集和及其頻度： 字符 A B C D E F G H I J K L M N 頻度 64 13 22 32 103

16、21 15 47 57 1 5 32 20 57 字符 O P Q R S T U V W X Y Z 空格 頻度 63 15 1 48 51 80 23 8 18 1 16 1 168 并實(shí)現(xiàn)以下報(bào)文的譯碼和輸出：THIS PROGRAM IS MY FAVORITE 《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號 實(shí) 驗(yàn)8：校園導(dǎo)游（12學(xué)時） [問題描述] 設(shè)計(jì)校園景點(diǎn)圖，包含校

17、園各景點(diǎn)以及景點(diǎn)之間的路徑，所含景點(diǎn)不少于8個。以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號、簡介等信息，以邊表示景點(diǎn)之間的路徑，邊的權(quán)值表示路徑長度。設(shè)計(jì)一個校園導(dǎo)游程序，提供校園導(dǎo)游信息。 [實(shí)驗(yàn)?zāi)康腯 （1） 熟悉圖的兩種常用的存儲結(jié)構(gòu)。 （2） 掌握對圖的兩種遍歷方法，即深度優(yōu)先遍歷和廣度優(yōu)先遍歷。進(jìn)一步掌握利用遞歸或隊(duì)列結(jié)構(gòu)進(jìn)行算法設(shè)計(jì)方法。 （3） 掌握prime算法和最短路徑算法 [實(shí)驗(yàn)內(nèi)容及要求] （1）景點(diǎn)查詢：輸入景點(diǎn)名稱或編號，提供景點(diǎn)相關(guān)信息的查詢。 （2）分別按照深度優(yōu)先和廣度優(yōu)先算法，將校園每個景點(diǎn)的信息輸出且僅輸出一次。 （3）利用Priml

18、算法求圖的最小生成樹，設(shè)計(jì)使各個景點(diǎn)之間連通代價(jià)最小的一種方案。 （4）提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€景點(diǎn)之間的一條最短路徑。 《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 學(xué)院 專業(yè) 姓名 學(xué)號 實(shí) 驗(yàn)9：內(nèi)部排序算法比較 （9學(xué)時） [問題描述] 排序是計(jì)算機(jī)程序設(shè)計(jì)中一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列重新排列成一個按關(guān)鍵字有序的序列。本實(shí)驗(yàn)熟悉幾種典型的排序方法，并對各種算法的特點(diǎn)、使用范圍和效率進(jìn)行進(jìn)一步的了解。 [實(shí)驗(yàn)?zāi)康腯 （1） 深刻理解排

19、序的定義和各類排序的算法思想，并能靈活應(yīng)用。 （2） 掌握各類排序的時間復(fù)雜度的分析方法，能從“關(guān)鍵字間的比較次數(shù)”分析算法的平均情況、最好情況和最壞情況。 （3） 理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。 [實(shí)驗(yàn)內(nèi)容及要求] ① 數(shù)據(jù)由輸入或隨機(jī)函數(shù)產(chǎn)生。 ② 實(shí)現(xiàn)簡單插入排序、簡單選擇排序、快速排序、堆排序和歸并排序算法等。 ③ 至少要用5組不同的輸入數(shù)據(jù)做比較（每組數(shù)據(jù)不小于100，應(yīng)考慮正序、逆序和隨機(jī)序列），統(tǒng)計(jì)關(guān)鍵字的比較次數(shù)和移動次數(shù)（需在算法的適當(dāng)位置插入對關(guān)鍵字的比較次數(shù)和移動次數(shù)的計(jì)數(shù)）、穩(wěn)定性、最好情況、最壞情況、平均情況等。 ④ 對結(jié)果做出簡單的分析。 第10頁