《《算法與數據結構》》由會員分享，可在線閱讀，更多相關《《算法與數據結構》（10頁珍藏版）》請在裝配圖網上搜索。

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

2、ent *stu_head; //鏈表表頭指針 int total; //學生總數 char manager[20];//班主任姓名 // ..... public: MyClass()//創(chuàng)建新班,學生數為0 void insertStu(Student s); //在班內中插入學生 s，插入后保持學號沒有重復并且按學號遞增 void deleteStu(int i) ; //刪除學號為i的學生 void display(); //顯示班內所有學生的信息和其它信息 void search(int i);//按照學號i 查找學生，并輸出其信息

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

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

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

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

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

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

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

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

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

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

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

14、 實驗7：哈夫曼樹的編/譯碼器系統的設計(9學時) [問題描述] 利用哈夫曼編碼進行通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統對待傳數據進行預先編碼；在接受端將傳來的數據進行解碼（復原）。對于可以雙向傳輸的信道，每端都要有一個完整的編/譯碼系統。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統。 [實驗目的] （1） 通過哈夫曼樹的定義，掌握構造哈夫曼樹的意義。 （2） 掌握構造哈夫曼樹的算法思想。 （3） 通過具體構造哈夫曼樹，進一步理解構造哈夫曼樹編碼的意義。 [實驗內容及要求] (1) 建立哈夫曼樹：從

15、終端讀入字符集大小為n（即字符的個數），逐一輸入n個字符和相應的n個權值（即字符出現的頻度）如表1所示，建立哈夫曼樹，將它存于文件 hfmtree 中。并將建立好的哈夫曼樹以樹或凹入法形式輸出;對每個字符進行編碼并且輸出。 (2) 編碼：利用已建好的哈夫曼編碼樹 ，對鍵盤輸入的正文進行譯碼。輸出字符正文，再輸出該文的二進制碼。 (3)譯碼：輸入一串二進制編碼，利用你建立的哈夫曼樹，將其進行譯碼，輸出字符正文。 表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 并實現以下報文的譯碼和輸出：THIS PROGRAM IS MY FAVORITE 《算法與數據結構》實驗報告 學院 專業(yè) 姓名 學號 實 驗8：校園導游（12學時） [問題描述] 設計校園景點圖，包含校

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

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

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