《算法與數(shù)據(jù)結構》

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