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

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

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

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

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

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

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

7、t1,t2)的實現(xiàn)可以采用以下形式：SElemType Precede(SElemType t1,SElemType t2) /根據(jù)教材表3.1，判斷兩個運算符的優(yōu)先關(guān)系 SElemType f; switch(t2) case '+': case '-':if(t1='('|t1='#') f='<' else f='>' break;/補充完整 return f;(5) 函數(shù)Operate(a,theta,b)的實現(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;/補充完整 return c; 選做內(nèi)容1：進一步改進，使表達式的中間值及最終結(jié)果不局限于09之間的個位數(shù)。（如果完成要在實驗報告中注明），如下圖：選做內(nèi)容2：將表達式轉(zhuǎn)化成后綴表達式輸出，利用后綴表達式求表達式的值并輸出。將中綴表達式轉(zhuǎn)化成后綴表達式存儲在隊列中，然后利用后綴表達式求表達式的值并輸出。l 將中綴表達式轉(zhuǎn)化成后綴的思想：（1）創(chuàng)建一空隊列，用來存放后綴表達式，建立

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

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

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

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

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

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

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