1、算法與數據結構實驗報告學院專業姓名學號實驗1線性表的操作(12學時)問題描述假設一個班級內有n個學生，定義一個學生類和一個班級類。學生類中包括學號、姓名、性別、年齡、專業等屬性；班級類包括一個學生對象鏈表。定義如下：class Stude nt int id;/ 學號char name20; /姓名int age; / 年齡/請設置學生類中相應的操作class MyClassStude nt *stu_head; / 鏈表表頭指針int total;/學生總數char man ager20; 班主任姓名/ public:MyClass()創建新班，學生數為0void insertStu(Stu

2、dent s); /在班內中插入學生 s,插入后保持學號沒有重復并且按學號遞增void deleteStu(int i) ; /刪除學號為i的學生void display(); /顯示班內所有學生的信息和其它信息void search(int i);按照學號i查找學生，并輸出其信息void search( char *s); /按照姓名查找學生，如果有重名的學生，則輸出所有學生void join(MyClass &class2 ); II將class2班合并到本班，合并后保證學號沒有重復并且按學號遞增void seperate(MyClass &c1,MyClass &

3、c2);II 按照性別分成兩個班cl 和 c2II其它方法實驗目的（1）掌握鏈表的基本操作。（2）熟練類的定義以及類之間的關系實驗內容及要求（1）實現MyClass類中所列出的方法；（2）編寫主函數測試類中的方法。算法與數據結構實驗報告學院專業姓名學號實驗2:利用棧將中綴表達式轉換為后綴表達式并進行計算（3學時）問題描述中綴表達式是最普通的一種書寫表達式的方式，而后綴表達式不需要用括號來表示，計算 機可簡化對后綴表達式的計算過程，而該過程又是棧的一個典型應用。實驗目的（1）深入理解棧的特性。（2）掌握棧結構的構造方法。實驗內容及要求（1） 中綴表達式中只包含+、一、x、/運算及（和）。（2）可

4、以輸入任意中綴表達式，數據為一位整數。（3）顯示中綴表達式及轉換后的后綴表達式 （為清楚起見，要求每輸出一個數據用逗 號隔開）。（4）對轉換后的后綴表達式進行計算。例如輸入：中綴表達式：6 + 3*（9-7）-8/2輸出：轉換后的后綴表達式為：6,3,9,7,-,*,+,8,2,-計算結果為：8算法與數據結構實驗報告學院專業姓名學號實驗3:行編輯程序問題（3學時）問題描述一個簡單的行編輯程序的功能是：接受用戶從終端輸入的程序或數據，并存入用戶的數據區。由于用戶在終端 上進行輸入時，不能保證不出差錯，因此，若在編輯程序中，“每接受一個字符即存入用戶數據區”的做法顯然不是最恰當的。較好的做法是，設

5、立一個輸入緩沖區，用以接受用戶輸入的一行字符，然后逐行存入用戶數據區。允許用 戶輸入出差錯，并在發現有誤時可以及時更正。例如，當用戶發現剛剛鍵入的一個字符是錯的時，可補進一個退格符"#"，以表示前一個字符無效；如果發現當前鍵入的行內差錯較多或難以補救，則可以鍵入一個退行符”"，以表示當前行中的字符均無效。 如果已經在行首繼續輸入 #符號無效。實驗目的（1）深入理解棧的特性。（2）掌握使用遞歸實現某些問題。（3）設計出應用棧解決在實際問題背景下對較復雜問題的遞歸算法。實驗內容及要求（1）實現簡單行編輯器，可以輸入一個多行的字符序列。但行字符總數（包含退格符和退行 符

6、）不大于250。（2） 利用順序棧保存從終端接收的字符，每行回車時顯示經過編輯的本行字符，例如：用戶輸入為:voL#id mia#ai n() churchar ch;輸出為：void mai n() char ch;算法與數據結構實驗報告學院專業姓名學號實驗4:隊列的應用（6學時）問題描述實現一個簡單銀行叫號模擬系統。銀行有三個窗口可以同時辦理業務，當有用 戶到達銀行時，首先選擇自己要辦理的業務，可以選擇一種或多種。系統計算辦理 此業務所需的時間并顯示給用戶，然后系統查看有無空閑的窗口，如果有，通知用 戶到一個空閑窗口辦理，如果沒有空閑窗口，則需安排用戶到某個窗口等候，系統 先計算每個隊列中

7、用戶辦理業務的總時間，將用戶安排到時間最短的隊列等候。模 擬輸出多個用戶辦理業務的過程。輸入舉例如下：用戶1在時間1到達銀行，在1號窗口辦理業務，需要1分鐘用戶1在時間2結束，離開用戶2在時間3達到。在1號窗口開始辦理，辦理業務需要 4分鐘 用戶3在時間3到達，在2號窗口開始辦理，辦理業務需要 5分鐘用戶4在時間5到達，在3號窗口開始辦理，辦理需要8分鐘用戶5在時間6到達，在1號窗口等待，辦理業需要4分鐘用戶2在時間8辦理完業務，離開用戶5在時間8在1號窗口，辦理業需要4分鐘用戶6在時間8到達，在1號窗口等待，辦理業務需要 6分鐘用戶7在時間8到達，在2號窗口等待，辦理業務需要10分鐘實驗目的

8、（1）深入理解隊列的特性。（2）掌握使用隊列實現某些問題。實驗內容及要求1 建立3個隊列存儲在三個窗口等待的用戶2建立業務類，描述業務種類，業務所需時間3. 建立用戶類，描述用戶辦理的業務，用戶的狀態等4可以隨機產生用戶進入銀行的時間，讓用戶輸入所需辦理的業務算法與數據結構實驗報告學院專業姓名學號實驗5:實現二叉樹的基本操作（12學時）問題描述樹和二叉樹是最常用的非線性結構 （樹型結構），其中以二叉樹最為常見，本實驗題要求實現二叉樹的最基本操作，其中遍歷二叉樹是二叉樹各種操作的基礎，它分為先序、中序和后序。實驗目的（1）熟練掌握二叉樹的結構特性。（2）掌握二叉樹的各種存儲結構的特點及實用范圍。

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

10、詢他是祖先（根節點）的第幾代子孫。（5） 插入：輸入一個結點值（編號姓名），插入一個結點作為其子女。6）考慮家譜中是否允許有重名的情況。算法與數據結構實驗報告學院專業姓名學號實驗6:查找算法（6學時）問題描述利用順序表實現順序查找、二分查找算法。實驗目的1、掌握順序表的查找2、掌握折半查找算法3、對實際查找問題學會選用一種合適的查找算法求解4、比較不同查找算法的效率實驗內容及要求（1）將實驗1的學生類Student中添加一個手機號碼屬性,在班級類Class中增 加一個生成通訊錄的方法，該方法將全班同學的姓名（假設無重名）和手機號碼取出，存入一個順序結構中，生成通訊錄，并寫入文件（以后可以直接從

11、文件中讀取 通訊錄）。（2）利用順序查找算法查找某學生的手機號碼。（3）按姓名排序，利用折半查找算法查找某學生的手機號碼。（4）統計并比較兩種算法中關鍵字的比較次數。（5）建議定義一個通訊錄類，將有關屬性和方法進行圭寸裝。算法與數據結構實驗報告學院專業姓名學號實驗7:哈夫曼樹的編/譯碼器系統的設計（9學時）問題描述利用哈夫曼編碼進行通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。 但是，這要求在發送端通過一個編碼系統對待傳數據進行預先編碼；在接受端將傳來的數據進 行解碼（復原）。對于可以雙向傳輸的信道，每端都要有一個完整的編/譯碼系統。試為這樣的信息收發站寫一個哈夫曼的編譯碼系統。

12、實驗目的（1）通過哈夫曼樹的定義，掌握構造哈夫曼樹的意義。（2）掌握構造哈夫曼樹的算法思想。（3）通過具體構造哈夫曼樹，進一步理解構造哈夫曼樹編碼的意義。實驗內容及要求(1) 建立哈夫曼樹：從終端讀入字符集大小為 n (即字符的個數)，逐一輸入 n個字符和相應的n個權值(即字符出現的頻度)如表 1所示，建立哈夫曼樹，將它存于文件 hfmtree中。 并將建立好的哈夫曼樹以樹或凹入法形式輸出；對每個字符進行編碼并且輸出。(2) 編碼：利用已建好的哈夫曼編碼樹，對鍵盤輸入的正文進行譯碼。輸出字符正文，再輸出該文的二進制碼。(3) 譯碼：輸入一串二進制編碼，利用你建立的哈夫曼樹，將其進行譯碼，輸出字

13、符正文。表1：字符集和及其頻度：字符ABCDEFGHIJKLMN頻度641322321032115475715322057字符OPQRSTUVWXYZ空格頻度63151485180238181161168并實現以下報文的譯碼和輸出：THIS PROGRAM IS MY FA VORITE算法與數據結構實驗報告學院專業姓名學號實驗8：校園導游(12學時)問題描述設計校園景點圖，包含校園各景點以及景點之間的路徑， 所含景點不少于8個 以圖中頂點表示校園內各景點，存放景點名稱、代號、簡介等信息，以邊表示景點 之間的路徑，邊的權值表示路徑長度。設計一個校園導游程序，提供校園導游信息。實驗目的(1) 熟

14、悉圖的兩種常用的存儲結構（2）掌握對圖的兩種遍歷方法，即深度優先遍歷和廣度優先遍歷。進一步掌握利用遞歸或隊列結構進行算法設計方法。（3）掌握prime算法和最短路徑算法實驗內容及要求（1）景點查詢：輸入景點名稱或編號，提供景點相關信息的查詢。（2）分別按照深度優先和廣度優先算法，將校園每個景點的信息輸出且僅輸出一次。（3）利用Priml算法求圖的最小生成樹，設計使各個景點之間連通代價最小的一種（4）提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短路徑。算法與數據結構實驗報告學院專業姓名學號實 驗9:內部排序算法比較（9學時）問題描述排序是計算機程序設計中一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列重新排列成一個按關鍵字有序的序列。本實驗熟悉幾種典型的排序方法，并對各種算法的特 點、使用范圍和效率進行進一步的了解。實驗目的（1）深刻理解排序的定義和各類排序的算法思想，并能靈活應用。（2）掌握各類排序的時間復雜度的分析方法，能從“關鍵字間的比較次