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

1、算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)1：線性表的操作（12學(xué)時(shí)）問(wèn)題描述假設(shè)一個(gè)班級(jí)內(nèi)有n個(gè)學(xué)生,定義一個(gè)學(xué)生類和一個(gè)班級(jí)類。學(xué)生類中包括學(xué)號(hào)、姓名、性別、年齡、專業(yè)等屬性；班級(jí)類包括一個(gè)學(xué)生對(duì)象鏈表。定義如下：class Student int id; /學(xué)號(hào) char name20; /姓名 int age; /年齡 /請(qǐng)?jiān)O(shè)置學(xué)生類中相應(yīng)的操作 class MyClass Student *stu_head; /鏈表表頭指針 int total; /學(xué)生總數(shù) char manager20;/班主任姓名 / .public: MyClass()/創(chuàng)建新班,學(xué)生數(shù)為0 void

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

3、yClass &c2);/按照性別分成兩個(gè)班c1和c2/ 其它方法 實(shí)驗(yàn)?zāi)康模?） 掌握鏈表的基本操作。（2） 熟練類的定義以及類之間的關(guān)系實(shí)驗(yàn)內(nèi)容及要求（1）實(shí)現(xiàn)MyClass類中所列出的方法；（2）編寫主函數(shù)測(cè)試類中的方法。算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)2：利用棧將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式并進(jìn)行計(jì)算（3學(xué)時(shí)）問(wèn)題描述 中綴表達(dá)式是最普通的一種書寫表達(dá)式的方式，而后綴表達(dá)式不需要用括號(hào)來(lái)表示，計(jì)算機(jī)可簡(jiǎn)化對(duì)后綴表達(dá)式的計(jì)算過(guò)程，而該過(guò)程又是棧的一個(gè)典型應(yīng)用。實(shí)驗(yàn)?zāi)康?（1） 深入理解棧的特性。（2） 掌握棧結(jié)構(gòu)的構(gòu)造方法。實(shí)驗(yàn)內(nèi)容及要求（1） 中綴表達(dá)式中只包含、/ 運(yùn)

4、算及（ 和 ）。 （2） 可以輸入任意中綴表達(dá)式,數(shù)據(jù)為一位整數(shù)。（3） 顯示中綴表達(dá)式及轉(zhuǎn)換后的后綴表達(dá)式(為清楚起見，要求每輸出一個(gè)數(shù)據(jù)用逗號(hào)隔開)。（4） 對(duì)轉(zhuǎn)換后的后綴表達(dá)式進(jìn)行計(jì)算。例如輸入：中綴表達(dá)式： 63*(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é)號(hào) 實(shí)驗(yàn)3：行編輯程序問(wèn)題（3學(xué)時(shí)）問(wèn)題描述 一個(gè)簡(jiǎn)單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。由于用戶在終端上進(jìn)行輸入時(shí)，不能保證不出差錯(cuò)，因此，若在編輯程序中，“每接受一個(gè)字符即存入用戶數(shù)據(jù)區(qū)”的做

5、法顯然不是最恰當(dāng)?shù)?。較好的做法是，設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。例如，當(dāng)用戶發(fā)現(xiàn)剛剛鍵入的一個(gè)字符是錯(cuò)的時(shí)，可補(bǔ)進(jìn)一個(gè)退格符#，以表示前一個(gè)字符無(wú)效；如果發(fā)現(xiàn)當(dāng)前鍵入的行內(nèi)差錯(cuò)較多或難以補(bǔ)救，則可以鍵入一個(gè)退行符，以表示當(dāng)前行中的字符均無(wú)效。如果已經(jīng)在行首繼續(xù)輸入#符號(hào)無(wú)效。實(shí)驗(yàn)?zāi)康模?） 深入理解棧的特性。（2） 掌握使用遞歸實(shí)現(xiàn)某些問(wèn)題。（3） 設(shè)計(jì)出應(yīng)用棧解決在實(shí)際問(wèn)題背景下對(duì)較復(fù)雜問(wèn)題的遞歸算法。實(shí)驗(yàn)內(nèi)容及要求（1）實(shí)現(xiàn)簡(jiǎn)單行編輯器，可以輸入一個(gè)多行的字符序列。但行字符總數(shù)（包含退格符和退行符）不

6、大于250。 （2）利用順序棧保存從終端接收的字符, 每行回車時(shí)顯示經(jīng)過(guò)編輯的本行字符, 例如：用戶輸入為：voL#idmia#ain()churchar ch;輸出為： void main() char ch;算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)4：隊(duì)列的應(yīng)用（6學(xué)時(shí)）問(wèn)題描述實(shí)現(xiàn)一個(gè)簡(jiǎn)單銀行叫號(hào)模擬系統(tǒng)。銀行有三個(gè)窗口可以同時(shí)辦理業(yè)務(wù)，當(dāng)有用戶到達(dá)銀行時(shí)，首先選擇自己要辦理的業(yè)務(wù)，可以選擇一種或多種。系統(tǒng)計(jì)算辦理此業(yè)務(wù)所需的時(shí)間并顯示給用戶，然后系統(tǒng)查看有無(wú)空閑的窗口，如果有，通知用戶到一個(gè)空閑窗口辦理，如果沒(méi)有空閑窗口，則需安排用戶到某個(gè)窗口等候，系統(tǒng)先計(jì)算每個(gè)隊(duì)列中用戶辦

7、理業(yè)務(wù)的總時(shí)間，將用戶安排到時(shí)間最短的隊(duì)列等候。模擬輸出多個(gè)用戶辦理業(yè)務(wù)的過(guò)程。輸入舉例如下：用戶1在時(shí)間1到達(dá)銀行，在1號(hào)窗口辦理業(yè)務(wù)，需要1分鐘用戶1在時(shí)間2結(jié)束，離開用戶2在時(shí)間3達(dá)到。在1號(hào)窗口開始辦理，辦理業(yè)務(wù)需要4分鐘 用戶3在時(shí)間3到達(dá)，在2號(hào)窗口開始辦理，辦理業(yè)務(wù)需要5分鐘用戶4在時(shí)間5到達(dá)，在3號(hào)窗口開始辦理，辦理需要8分鐘用戶5在時(shí)間6到達(dá)，在1號(hào)窗口等待，辦理業(yè)需要4分鐘用戶2在時(shí)間8辦理完業(yè)務(wù)，離開用戶5在時(shí)間8在1號(hào)窗口，辦理業(yè)需要4分鐘用戶6在時(shí)間8到達(dá)，在1號(hào)窗口等待，辦理業(yè)務(wù)需要6分鐘用戶7在時(shí)間8到達(dá)，在2號(hào)窗口等待，辦理業(yè)務(wù)需要10分鐘 實(shí)驗(yàn)?zāi)康模?）深入理

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

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

10、查詢他是祖先（根節(jié)點(diǎn)）的第幾代子孫。（5）插入：輸入一個(gè)結(jié)點(diǎn)值（編號(hào)姓名），插入一個(gè)結(jié)點(diǎn)作為其子女。（6）考慮家譜中是否允許有重名的情況。算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)6：查找算法（6學(xué)時(shí)）問(wèn)題描述利用順序表實(shí)現(xiàn)順序查找、二分查找算法。實(shí)驗(yàn)?zāi)康?、 掌握順序表的查找2、 掌握折半查找算法3、 對(duì)實(shí)際查找問(wèn)題學(xué)會(huì)選用一種合適的查找算法求解4、比較不同查找算法的效率實(shí)驗(yàn)內(nèi)容及要求（1）將實(shí)驗(yàn)1的學(xué)生類Student中添加一個(gè)手機(jī)號(hào)碼屬性,在班級(jí)類Class中增加一個(gè)生成通訊錄的方法，該方法將全班同學(xué)的姓名（假設(shè)無(wú)重名）和手機(jī)號(hào)碼取出，存入一個(gè)順序結(jié)構(gòu)中，生成通訊錄，并寫入文件（

11、以后可以直接從文件中讀取通訊錄）。（2）利用順序查找算法查找某學(xué)生的手機(jī)號(hào)碼。（3）按姓名排序，利用折半查找算法查找某學(xué)生的手機(jī)號(hào)碼。（4）統(tǒng)計(jì)并比較兩種算法中關(guān)鍵字的比較次數(shù)。（5）建議定義一個(gè)通訊錄類，將有關(guān)屬性和方法進(jìn)行封裝。算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)7：哈夫曼樹的編/譯碼器系統(tǒng)的設(shè)計(jì)(9學(xué)時(shí))問(wèn)題描述利用哈夫曼編碼進(jìn)行通訊可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)進(jìn)行預(yù)先編碼；在接受端將傳來(lái)的數(shù)據(jù)進(jìn)行解碼（復(fù)原）。對(duì)于可以雙向傳輸?shù)男诺?，每端都要有一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼

12、的編譯碼系統(tǒng)。 實(shí)驗(yàn)?zāi)康?（1） 通過(guò)哈夫曼樹的定義，掌握構(gòu)造哈夫曼樹的意義。（2） 掌握構(gòu)造哈夫曼樹的算法思想。（3） 通過(guò)具體構(gòu)造哈夫曼樹，進(jìn)一步理解構(gòu)造哈夫曼樹編碼的意義。實(shí)驗(yàn)內(nèi)容及要求(1) 建立哈夫曼樹：從終端讀入字符集大小為n（即字符的個(gè)數(shù)），逐一輸入n個(gè)字符和相應(yīng)的n個(gè)權(quán)值（即字符出現(xiàn)的頻度）如表1所示，建立哈夫曼樹，將它存于文件 hfmtree 中。并將建立好的哈夫曼樹以樹或凹入法形式輸出;對(duì)每個(gè)字符進(jìn)行編碼并且輸出。(2) 編碼：利用已建好的哈夫曼編碼樹 ，對(duì)鍵盤輸入的正文進(jìn)行譯碼。輸出字符正文，再輸出該文的二進(jìn)制碼。 (3)譯碼：輸入一串二進(jìn)制編碼，利用你建立的哈夫曼樹，將

13、其進(jìn)行譯碼，輸出字符正文。表1：字符集和及其頻度：字符ABCDEFGHIJKLMN頻度641322321032115475715322057字符OPQRSTUVWXYZ空格頻度63151485180238181161168并實(shí)現(xiàn)以下報(bào)文的譯碼和輸出：THIS PROGRAM IS MY FAVORITE 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí) 驗(yàn)8：校園導(dǎo)游（12學(xué)時(shí)）問(wèn)題描述 設(shè)計(jì)校園景點(diǎn)圖，包含校園各景點(diǎn)以及景點(diǎn)之間的路徑，所含景點(diǎn)不少于8個(gè)。以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息，以邊表示景點(diǎn)之間的路徑，邊的權(quán)值表示路徑長(zhǎng)度。設(shè)計(jì)一個(gè)校園導(dǎo)游程序，提供校園導(dǎo)

14、游信息。 實(shí)驗(yàn)?zāi)康?（1） 熟悉圖的兩種常用的存儲(chǔ)結(jié)構(gòu)。（2） 掌握對(duì)圖的兩種遍歷方法，即深度優(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)名稱或編號(hào)，提供景點(diǎn)相關(guān)信息的查詢。（2）分別按照深度優(yōu)先和廣度優(yōu)先算法，將校園每個(gè)景點(diǎn)的信息輸出且僅輸出一次。（3）利用Priml算法求圖的最小生成樹，設(shè)計(jì)使各個(gè)景點(diǎn)之間連通代價(jià)最小的一種方案。（4）提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短路徑。算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí) 驗(yàn)9：內(nèi)部排序算法比較 （9學(xué)時(shí)）問(wèn)題描

15、述排序是計(jì)算機(jī)程序設(shè)計(jì)中一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列重新排列成一個(gè)按關(guān)鍵字有序的序列。本實(shí)驗(yàn)熟悉幾種典型的排序方法，并對(duì)各種算法的特點(diǎn)、使用范圍和效率進(jìn)行進(jìn)一步的了解。實(shí)驗(yàn)?zāi)康?（1） 深刻理解排序的定義和各類排序的算法思想，并能靈活應(yīng)用。（2） 掌握各類排序的時(shí)間復(fù)雜度的分析方法，能從“關(guān)鍵字間的比較次數(shù)”分析算法的平均情況、最好情況和最壞情況。（3） 理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。實(shí)驗(yàn)內(nèi)容及要求 數(shù)據(jù)由輸入或隨機(jī)函數(shù)產(chǎn)生。 實(shí)現(xiàn)簡(jiǎn)單插入排序、簡(jiǎn)單選擇排序、快速排序、堆排序和歸并排序算法等。 至少要用5組不同的輸入數(shù)據(jù)做比較（每組數(shù)據(jù)不小于100，應(yīng)考慮正序、逆序和隨機(jī)序列），統(tǒng)計(jì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)（需在算法的適當(dāng)位置插入對(duì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)數(shù)）、穩(wěn)定性、最好情況、最壞情況、平均情況等。 對(duì)結(jié)果做出簡(jiǎn)單的分析。 第10頁(yè)