數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書2

1、北 京 林 業(yè) 大 學(xué)實(shí) 驗(yàn) 任 務(wù) 書備注：實(shí)驗(yàn)共分4次，其中實(shí)驗(yàn)1實(shí)驗(yàn)3為設(shè)計(jì)性實(shí)驗(yàn)，實(shí)驗(yàn)4為綜合性實(shí)驗(yàn)，具體安排下面一一列出。北 京 林 業(yè) 大 學(xué)10學(xué)年11學(xué)年第 2學(xué)期 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)任務(wù)書專業(yè)名稱： 實(shí)驗(yàn)學(xué)時(shí)： 4 課程名稱：數(shù)據(jù)結(jié)構(gòu) 任課教師： 李冬梅 實(shí)驗(yàn)題目：線性表的基本操作 實(shí)驗(yàn)環(huán)境： Visual C+ 實(shí)驗(yàn)?zāi)康模?、掌握線性表的定義；2、掌握線性表的基本操作，如建立、查找、插入和刪除等。實(shí)驗(yàn)內(nèi)容：定義一個(gè)包含學(xué)生信息（學(xué)號(hào)，姓名，成績(jī)）的的順序表和鏈表，使其具有如下功能：(1) 根據(jù)指定學(xué)生個(gè)數(shù)，逐個(gè)輸入學(xué)生信息；(2) 逐個(gè)顯示學(xué)生表中所有學(xué)生的相關(guān)信息；(3) 根據(jù)

2、姓名進(jìn)行查找，返回此學(xué)生的學(xué)號(hào)和成績(jī)；(4) 根據(jù)指定的位置可返回相應(yīng)的學(xué)生信息（學(xué)號(hào)，姓名，成績(jī)）； (5) 給定一個(gè)學(xué)生信息，插入到表中指定的位置； (6) 刪除指定位置的學(xué)生記錄；(7) 統(tǒng)計(jì)表中學(xué)生個(gè)數(shù)。實(shí)驗(yàn)提示： 學(xué)生信息的定義：typedef struct char no8; /8位學(xué)號(hào) char name20; /姓名 int price; /成績(jī)Student;順序表的定義typedef struct Student *elem; /指向數(shù)據(jù)元素的基地址 int length; /線性表的當(dāng)前長(zhǎng)度 SqList；鏈表的定義：typedef struct LNode Studen

3、t data; /數(shù)據(jù)域 struct LNode *next; /指針域LNode,*LinkList; 實(shí)驗(yàn)要求：(1) 程序要添加適當(dāng)?shù)淖⑨?，程序的書寫要采用縮進(jìn)格式。(2) 程序要具在一定的健壯性，即當(dāng)輸入數(shù)據(jù)非法時(shí)，程序也能適當(dāng)?shù)刈龀龇磻?yīng)，如插入刪除時(shí)指定的位置不對(duì)等等。(3) 程序要做到界面友好，在程序運(yùn)行時(shí)用戶可以根據(jù)相應(yīng)的提示信息進(jìn)行操作。(4) 根據(jù)實(shí)驗(yàn)報(bào)告模板詳細(xì)書寫實(shí)驗(yàn)報(bào)告,在實(shí)驗(yàn)報(bào)告中給出鏈表根據(jù)姓名進(jìn)行查找的算法和插入算法的流程圖。(5) 上傳源程序和實(shí)驗(yàn)報(bào)告到ftp的相應(yīng)班級(jí)所在文件夾。順序表的源程序保存為SqList.cpp，鏈表的源程序保存為L(zhǎng)inkList.c

4、pp，實(shí)驗(yàn)報(bào)告命名為：實(shí)驗(yàn)報(bào)告1.doc。源程序和實(shí)驗(yàn)報(bào)告壓縮為一個(gè)文件（如果定義了頭文件則一起壓縮），按以下方式命名：學(xué)號(hào)姓名.rar，如070814101薛力.rar。北 京 林 業(yè) 大 學(xué)10學(xué)年11學(xué)年第 2 學(xué)期 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)任務(wù)書專業(yè)名稱： 實(shí)驗(yàn)學(xué)時(shí)： 4 課程名稱：數(shù)據(jù)結(jié)構(gòu) 任課教師： 李冬梅 實(shí)驗(yàn)題目：棧的應(yīng)用算術(shù)表達(dá)式求值 實(shí)驗(yàn)環(huán)境： Visual C+ 6.0 實(shí)驗(yàn)?zāi)康模?掌握棧的定義及實(shí)現(xiàn)；2掌握利用棧求解算術(shù)表達(dá)式的方法。實(shí)驗(yàn)內(nèi)容：通過(guò)修改完善教材中的算法3.4，利用棧來(lái)實(shí)現(xiàn)算術(shù)表達(dá)式求值的算法。對(duì)算法3.4中調(diào)用的幾個(gè)函數(shù)要給出其實(shí)現(xiàn)過(guò)程：(1) 函數(shù)In(c)：判斷

5、c是否為運(yùn)算符；(2) 函數(shù)Precede(t1,t2)：判斷運(yùn)算符t1和t2的優(yōu)先級(jí)；(3) 函數(shù)Operate(a,theta,b)：對(duì)a和b進(jìn)行二元運(yùn)算theta。程序運(yùn)行時(shí)，輸入合法的算術(shù)表達(dá)式（中間值及最終結(jié)果要在09之間，可以包括加減乘除和括號(hào)），便可輸出相應(yīng)的計(jì)算結(jié)果。如下圖：實(shí)驗(yàn)提示：（僅供參考，每個(gè)函數(shù)的具體實(shí)現(xiàn)可以有多種方法，希望有創(chuàng)新）1. 將棧的定義和實(shí)現(xiàn)單獨(dú)保存在頭文件“stack.h”中，然后在表達(dá)式求值的源程序sy2.cpp中包含此頭文件（即#include“stack.h”）。2.表達(dá)式求值源程序sy2.cpp的具體實(shí)現(xiàn)(1) 主函數(shù)如下：void main()

6、 cout<<"請(qǐng)輸入算術(shù)表達(dá)式,并以#結(jié)束."<<endl; cout<<EvaluateExpression()<endl; (2) 函數(shù)EvaluateExpression的實(shí)現(xiàn)見算法3.10(3) 函數(shù)In(c)的實(shí)現(xiàn)可以采用以下方式：Status In(SElemType c)/ 應(yīng)在前面有定義typedef char SElemType; / 判斷c是否為運(yùn)算符 switch(c) case'+':return TRUE; /補(bǔ)充完整default:return FALSE; (4) 函數(shù)Precede(

7、t1,t2)的實(shí)現(xiàn)可以采用以下形式：SElemType Precede(SElemType t1,SElemType t2) /根據(jù)教材表3.1，判斷兩個(gè)運(yùn)算符的優(yōu)先關(guān)系 SElemType f; switch(t2) case '+': case '-':if(t1='('|t1='#') f='<' else f='>' break;/補(bǔ)充完整 return f;(5) 函數(shù)Operate(a,theta,b)的實(shí)現(xiàn)可以采用以下方式：SElemType Operate(SElemTy

8、pe a,SElemType theta,SElemType b) SElemType c; a=a-48; b=b-48; switch(theta) case'+':c=a+b+48; break;/補(bǔ)充完整 return c; 選做內(nèi)容1：進(jìn)一步改進(jìn)，使表達(dá)式的中間值及最終結(jié)果不局限于09之間的個(gè)位數(shù)。（如果完成要在實(shí)驗(yàn)報(bào)告中注明），如下圖：選做內(nèi)容2：將表達(dá)式轉(zhuǎn)化成后綴表達(dá)式輸出，利用后綴表達(dá)式求表達(dá)式的值并輸出。將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式存儲(chǔ)在隊(duì)列中，然后利用后綴表達(dá)式求表達(dá)式的值并輸出。l 將中綴表達(dá)式轉(zhuǎn)化成后綴的思想：（1）創(chuàng)建一空隊(duì)列，用來(lái)存放后綴表達(dá)式，建立

9、并初始化操作符棧OPTR，將表達(dá)式起始符“#”壓入OPTR棧。（2）依次讀入表達(dá)式中每個(gè)字符ch，循環(huán)執(zhí)行（3）至（5），直至求出整個(gè)表達(dá)式轉(zhuǎn)換完畢。（3）取出OPTR的棧頂元素，當(dāng)OPTR的棧頂元素和當(dāng)前讀入的字符ch均為“#”時(shí)，整個(gè)中綴表達(dá)式轉(zhuǎn)換完畢。（4）若ch不是運(yùn)算符，則進(jìn)隊(duì)，讀入下一字符ch。（5）若ch是運(yùn)算符，則根據(jù)OPTR的棧頂元素和ch的優(yōu)先權(quán)比較結(jié)果，做不同的處理。 若是小于，則ch壓入OPTR棧，讀入下一字符ch。 若是大于，則彈出OPTR棧頂?shù)倪\(yùn)算符，進(jìn)隊(duì)。 若是等于，則OPTR的棧頂元素是“(”且ch是“)”，這時(shí)彈出OPTR棧頂?shù)摹?”，相當(dāng)于去掉括號(hào)，然后讀入

10、下一字符ch。l 對(duì)后綴表達(dá)式進(jìn)行計(jì)算的具體步驟為： 建立一個(gè)棧S從左到右讀后綴表達(dá)式，讀到數(shù)字就將它轉(zhuǎn)換為數(shù)值壓入棧S中，讀到運(yùn)算符則從棧中依次彈出兩個(gè)數(shù)分別到Y(jié)和X，然后以“X運(yùn)算符Y”的形式計(jì)算出結(jié)果，再壓進(jìn)棧S中。如果后綴表達(dá)式未讀完，重復(fù)執(zhí)行上面過(guò)程，最后輸出棧頂?shù)臄?shù)值即可結(jié)束。實(shí)驗(yàn)要求：(1) 程序要添加適當(dāng)?shù)淖⑨?，程序的書寫要采用縮進(jìn)格式。(2) 程序要具在一定的健壯性，即當(dāng)輸入數(shù)據(jù)非法時(shí)，程序也能適當(dāng)?shù)刈龀龇磻?yīng)。(3) 程序要做到界面友好，在程序運(yùn)行時(shí)用戶可以根據(jù)相應(yīng)的提示信息進(jìn)行操作。(4) 根據(jù)實(shí)驗(yàn)報(bào)告模板詳細(xì)書寫實(shí)驗(yàn)報(bào)告,在實(shí)驗(yàn)報(bào)告中給出表達(dá)式求值算法的流程圖。(5) 將

11、棧的定義和實(shí)現(xiàn)單獨(dú)保存在一個(gè)頭文件“stack.h”中，表達(dá)式求值的源程序保存為“calculator.cpp”，實(shí)驗(yàn)報(bào)告命名為“實(shí)驗(yàn)報(bào)告2.doc”。將stack.h、calculator.cpp和“實(shí)驗(yàn)報(bào)告2.doc”三個(gè)文件壓縮為一個(gè)文件，按以下方式命名：學(xué)號(hào)姓名.rar，上傳到ftp的相應(yīng)班級(jí)所在文件夾。北 京 林 業(yè) 大 學(xué)10學(xué)年11學(xué)年第 2 學(xué)期 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)任務(wù)書專業(yè)名稱： 實(shí)驗(yàn)學(xué)時(shí)： 4 課程名稱：數(shù)據(jù)結(jié)構(gòu) 任課教師： 李冬梅 實(shí)驗(yàn)題目： 哈夫曼編碼算法的實(shí)現(xiàn) 實(shí)驗(yàn)環(huán)境： Visual C+ 實(shí)驗(yàn)?zāi)康模?掌握二叉樹的定義；2掌握哈夫曼樹和哈夫曼編碼算法的實(shí)現(xiàn)。 實(shí)驗(yàn)內(nèi)容：實(shí)

12、現(xiàn)一個(gè)哈夫曼編碼系統(tǒng)，系統(tǒng)包括以下功能：(1) 字符信息統(tǒng)計(jì)：讀取待編碼的源文件SourceFile.txt，統(tǒng)計(jì)出現(xiàn)的字符及其頻率。(2) 建立哈夫曼樹：根據(jù)統(tǒng)計(jì)結(jié)果建立哈夫曼樹。(3) 建立哈夫曼碼表：利用得到的哈夫曼樹，將各字符對(duì)應(yīng)的編碼表保存在文件Code.txt中。(4) 對(duì)源文件進(jìn)行編碼：根據(jù)哈夫曼碼表，將SourceFile.txt中的字符轉(zhuǎn)換成相應(yīng)的編碼文件ResultFile.txt。實(shí)現(xiàn)提示：(1) 字符信息統(tǒng)計(jì)：假設(shè)源文件SourceFile.txt中的字符只有大小寫英文字母（同一個(gè)字母的大小寫看作一個(gè)字符），則字符統(tǒng)計(jì)算法的實(shí)現(xiàn)過(guò)程可以歸納為：先定義一個(gè)含有26個(gè)元素的

13、整形數(shù)組，用來(lái)存儲(chǔ)各個(gè)字母出現(xiàn)的次數(shù)，最后還要排除其中出現(xiàn)次數(shù)為0的數(shù)組元素。(2) 建立哈夫曼樹：參考教材算法5.10，補(bǔ)充函數(shù)Select的實(shí)現(xiàn)。(3) 建立哈夫曼碼表：參考教材算法5.11，將編譯表HC中的內(nèi)容寫到文件Code.txt中。(4) 對(duì)源文件進(jìn)行編碼：依次讀入文件SourceFile.txt中的字符 c，在編碼表 HC 中找到此字符，將字符c轉(zhuǎn)換為編碼表中存放的編碼串，寫入編碼文件ResultFile.txt中，直到所有的字符處理完畢為止。選做內(nèi)容:完成譯碼功能：對(duì)任意一個(gè)給定的由01組成的文件，根據(jù)哈夫曼碼表翻譯成由字符組成的源文件。提示：對(duì)文

14、件進(jìn)行譯碼的過(guò)程必須借助于哈夫曼樹。具體過(guò)程是：依次讀入文件的二進(jìn)制碼，從哈夫曼樹的根結(jié)點(diǎn)（即HTm）出發(fā)，若當(dāng)前讀入0，則走向左孩子，否則走向右孩子。一旦到達(dá)某一葉子HTi時(shí)便譯出相應(yīng)的字符編碼HCi。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。實(shí)驗(yàn)要求：(1) 程序要具在一定的健壯性，即當(dāng)輸入數(shù)據(jù)非法時(shí)，程序也能適當(dāng)?shù)刈龀龇磻?yīng)。(2) 程序要添加適當(dāng)?shù)淖⑨專绦虻臅鴮懸捎每s進(jìn)格式。(3) 待編碼的源文件命名為SourceFile.txt，中，源程序保存為“Huffman.cpp”，實(shí)驗(yàn)報(bào)告命名為“實(shí)驗(yàn)報(bào)告3.doc”。將這三個(gè)文件壓縮為一個(gè)文件，按以下方式命名：學(xué)號(hào)姓名.rar，上傳到ftp

15、的相應(yīng)班級(jí)所在文件夾。 北 京 林 業(yè) 大 學(xué)10學(xué)年11學(xué)年第 2學(xué)期 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)任務(wù)書專業(yè)名稱： 實(shí)驗(yàn)學(xué)時(shí)： 4 課程名稱：數(shù)據(jù)結(jié)構(gòu) 任課教師： 李冬梅 實(shí)驗(yàn)題目：學(xué)生管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 實(shí)驗(yàn)環(huán)境： 實(shí)驗(yàn)?zāi)康模?掌握重要的排序算法插入排序和快速排序；2掌握折半查找算法。3. 綜合運(yùn)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，提高解決實(shí)際問(wèn)題的能力。實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)并實(shí)現(xiàn)一個(gè)學(xué)生管理系統(tǒng)，即定義一個(gè)包含學(xué)生信息（學(xué)號(hào)，姓名，成績(jī)）的的順序表，可以不考慮重名的情況，系統(tǒng)至少包含以下功能：(1) 根據(jù)指定學(xué)生個(gè)數(shù)，逐個(gè)輸入學(xué)生信息；(2) 逐個(gè)顯示學(xué)生表中所有學(xué)生的相關(guān)信息；(3) 給定一個(gè)學(xué)生信息，插入到表中指定的位置；(4) 刪除指定位置的學(xué)生記錄；(5) 統(tǒng)計(jì)表中學(xué)生個(gè)數(shù)；(6) 利用直接插入排序或者折半插入排序按照姓名進(jìn)行排序；(7) 利用快速排序按照學(xué)號(hào)進(jìn)行排序；(8) 根據(jù)姓名進(jìn)行折半查找，要求使用遞歸算法實(shí)現(xiàn)，成功返回此學(xué)生的學(xué)號(hào)和成績(jī)；(9) 根據(jù)學(xué)號(hào)進(jìn)行折半查找，要求使用非遞歸算法實(shí)現(xiàn)，成功返回此學(xué)生的姓名和成績(jī)