貴州大學(xué)數(shù)據(jù)結(jié)構(gòu)實驗任務(wù)指導(dǎo)書(實驗報告版)

1、貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)系上機實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名： 學(xué)號：指導(dǎo)教師：程欣宇實驗序號：一實驗成績：一、實驗名稱線性表及其應(yīng)用二、實驗?zāi)康募耙?、熟悉鏈表的創(chuàng)建，鏈表結(jié)點查找、插入和刪除；2、理解鏈表用于存儲線性表的優(yōu)勢和劣勢；3、掌握利用鏈表存儲一元多項式的數(shù)據(jù)結(jié)構(gòu)，及其運算操作。三、實驗環(huán)境Visual C+四、實驗內(nèi)容1、輸入并建立多項式；2、輸出多項式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2,.,cn,en, 其中n是多項式的項數(shù)，ci和ei分別是第I項的系數(shù)和指數(shù)，序列按照指數(shù)降序排列；3、多項式a和b相加，建立多項

2、式a+b；4、多項式a和b相減，建立多項式a-b。五、算法描述及實驗步驟使用鏈表存儲一元多項式c1 X e1+ c2 X e2+ cn X en如下圖所示：頭結(jié)點c1e1c2e2cnen如何實現(xiàn)這種線性鏈表表示的多項式的加法運算？根據(jù)一元多項式相加的運算規(guī)則：對于兩個一元多項式中所有指數(shù)相同的項，對應(yīng)系數(shù)相加，若其和不為零，則構(gòu)成“和多項式”中的一項；對于兩個一元多項式中所有指數(shù)不相同的項，則分別復(fù)抄到“和”多項式中去。實驗步驟：1、2、3、六、調(diào)試過程及實驗結(jié)果詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見

3、。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)系上機實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名： 學(xué)號：指導(dǎo)教師：程欣宇實驗序號：二實驗成績：一、實驗名稱棧及其應(yīng)用二、實驗?zāi)康募耙?、熟悉棧的原理和實現(xiàn)方式；2、理解使用棧消除函數(shù)遞歸調(diào)用的原理；3、掌握后綴表達式計算的方法。三、實驗環(huán)境Visual C+四、實驗內(nèi)容1、棧實現(xiàn)階乘函數(shù)；2、棧實現(xiàn)后綴表達式的計算。五、算法描述及實驗步驟函數(shù)調(diào)用棧的結(jié)構(gòu)如下：第n層調(diào)用調(diào)用返回（當(dāng)前函數(shù)局部變量空間）返回第n-1層調(diào)用調(diào)用（當(dāng)前函數(shù)的主調(diào)函數(shù)變量空間）調(diào)用返回調(diào)用返回第1層調(diào)

4、用主函數(shù)局部變量空間函數(shù)調(diào)用的?？臻g使用棧消去遞歸的算法框架如下：初始化棧；將完整問題參數(shù)壓棧；while(棧非空)取出棧頂元素所描述的問題如果可以直接解決，則直接解決否則分解為子問題壓棧后綴表達式是運算符在運算數(shù)之后的一種表達式存儲的數(shù)據(jù)結(jié)構(gòu)，不需要比較運算符優(yōu)先級別，只需要每次讀到運算數(shù)時壓棧，讀到運算符時將運算數(shù)出棧，將結(jié)果壓棧即可。最后的運算結(jié)果存放在棧底。實驗步驟1、2、3、六、調(diào)試過程及實驗結(jié)果詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙貴州

5、大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)系上機實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名： 學(xué)號：指導(dǎo)教師：程欣宇實驗序號：三實驗成績：一、實驗名稱隊列及其應(yīng)用二、實驗?zāi)康募耙?、熟悉隊列的原理和實現(xiàn)方式；2、理解使用隊列進行搜索的原理；3、掌握使用隊列進行搜索的程序設(shè)計方法。三、實驗環(huán)境Visual C+四、實驗內(nèi)容1、使用隊列實現(xiàn)教科書P50頁說描述的迷宮問題。五、算法描述及實驗步驟使用隊列進行搜索的算法框架如下：初始化隊列；將搜索的出發(fā)點入隊；while(隊列非空)取出隊首元素所描述的位置；如果到達搜索目標(biāo)，則完成搜索，推出循環(huán)；否則將該位置可以擴展搜索的位置入隊待搜

6、索。實驗步驟1、2、3、六、調(diào)試過程及實驗結(jié)果詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)系上機實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名： 學(xué)號：指導(dǎo)教師：程欣宇實驗序號：四實驗成績：一、實驗名稱串及其應(yīng)用二、實驗?zāi)康募耙?、熟悉串的基本操作方法2、掌握文本模式匹配算法。三、實驗環(huán)境Visual C+四、實驗內(nèi)容1、輸入以回車作為結(jié)束符的一串字符作為主串；2、求主串中指定的單個字符出現(xiàn)的次

7、數(shù)和位置；3、求主串中指定子串出現(xiàn)的次數(shù)和位置；4、求主串中指定單詞出現(xiàn)的次數(shù)和位置,注意單詞與子串的區(qū)別。五、算法描述及實驗步驟算法描述：1、統(tǒng)計指定單個字符出現(xiàn)的次數(shù)和位置，只需遍歷主串的每一個字符即可。2、求指定子串出現(xiàn)的位置，可以采用逐位置滑動的匹配方法和KMP快速匹配算法。3、求指定單詞出現(xiàn)的位置，關(guān)鍵是考慮單詞和子串的不同，即：單詞首尾要么是空格要么是主串的首尾，所以在匹配到子串后，作此檢查即可。另外，也可以考慮采用在主串和單詞首尾加入空格的方法，進行子串搜索。實驗步驟1、2、3、六、調(diào)試過程及實驗結(jié)果詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機

8、實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)系上機實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名： 學(xué)號：指導(dǎo)教師：程欣宇實驗序號：五實驗成績：一、實驗名稱稀疏矩陣和多維數(shù)組的實現(xiàn)二、實驗?zāi)康募耙?、熟悉三元組方式存儲稀疏矩陣的原理和算法；2、掌握多維數(shù)組的存儲空間分配和訪問算法。三、實驗環(huán)境Visual C+四、實驗內(nèi)容1、封裝一個稀疏矩陣類。要求內(nèi)部使用三元組順序表表示。要求實現(xiàn)如下成員函數(shù)：a、按三元組數(shù)組構(gòu)造b、矩陣加法c、矩陣轉(zhuǎn)置d、矩陣乘法 不要求實現(xiàn)性能最優(yōu)化

9、算法，不要求使用運算符重載，要求構(gòu)造測試用例。 2、封裝一個三維數(shù)組類class Array3D內(nèi)部使用一維數(shù)組存儲數(shù)據(jù)。提供構(gòu)造函數(shù)提供訪問每一維長度的方法int getLength(int dim)提供讀取任意一元素的方法ElemType get(int i,int j,int k)提供寫入取任意一元素的方法void set(int i,int j,int k,ElemType value)五、算法描述及實驗步驟三元組方式存儲稀疏數(shù)組：1、表示稀疏矩陣的一個非零元素可以使用一個三元組：行號、列號、元素值。2、使用n個三元元組表示一個稀疏矩陣，需要定義一個三元組的數(shù)組，數(shù)組大小等于n+1，其

10、中第一個三元組存儲數(shù)組的最大行列號。多維數(shù)組的實現(xiàn)算法：1、傳入三維數(shù)組各位大小：n,m,p，動態(tài)申請內(nèi)存空間，size=n*m*p；2、訪問元素需要傳入下標(biāo)數(shù)組：i,j,k，其對應(yīng)存儲空間為：Loc(i,j,k)=i*p*m+j*p+k實驗步驟1、2、3、六、調(diào)試過程及實驗結(jié)果詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)系上機實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名： 學(xué)號：指導(dǎo)教師：程欣

11、宇實驗序號：六實驗成績：一、實驗名稱哈夫曼編碼/譯碼器 二、實驗?zāi)康募耙?、掌握二叉樹的存儲方法；2、掌握Huffman二叉樹的構(gòu)造、編碼和譯碼算法；三、實驗環(huán)境Visual C+四、實驗內(nèi)容1、生成編碼二叉樹輸入為字符集和詞頻，輸出為哈夫曼二叉樹。字符集和詞頻如下： 字符空格 A B C D E F G H I J K L M 頻度186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z 詞頻5763151 48 51 80 23 8 18 1 16 1 2、編碼器設(shè)計輸入為二叉樹和要編碼的內(nèi)容，輸出為編碼結(jié)

12、果3、譯碼器設(shè)計輸入為二叉樹和要解碼的內(nèi)容，輸出為譯碼內(nèi)容五、算法描述及實驗步驟哈夫曼二叉樹在創(chuàng)建過程中，最初為n個獨立的葉子結(jié)點，的葉子結(jié)點就是要編碼的字符，數(shù)量為n，最初為創(chuàng)建可以使用一個=實驗步驟1、2、3、六、調(diào)試過程及實驗結(jié)果詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)系上機實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名： 學(xué)號：指導(dǎo)教師：程欣宇實驗序號：七實驗成績：一、實驗名稱圖及其應(yīng)

13、用 二、實驗?zāi)康募耙?、熟悉圖的兩種常用存儲形式：鄰接矩陣、鄰接表；2、熟悉圖的遍歷算法；3、熟悉出度、入度的求法；4、掌握拓撲排序算法；5、掌握關(guān)鍵路徑求法。三、實驗環(huán)境Visual C+四、實驗內(nèi)容1、定義出圖有向圖和無向圖兩種數(shù)據(jù)類型；2、實現(xiàn)有向圖的鄰接矩陣和鄰接表；3、實現(xiàn)無向圖的鄰接矩陣和鄰接表。4、編寫圖的關(guān)鍵路徑算法五、算法描述及實驗步驟鄰接矩陣是使用一個二維數(shù)組存儲圖的方式，其元素cij記錄頂點Vi和頂點Vj的關(guān)聯(lián)情況。鄰接鏈表使用一個頂點數(shù)組存儲頂點信息，頂點數(shù)組中每條記錄指向一條弧鏈表，第i條鏈表紀錄了所有從頂點Vi 出去的弧的信息。拓撲排序是講一個偏序關(guān)系確定為一個全序關(guān)系的過程，其算法是使用一個棧紀錄當(dāng)前入度為0的頂點，然后每次選擇棧頂元素出棧和作相應(yīng)調(diào)整，最后得到的出棧順序就是拓撲序。在求關(guān)鍵路徑中需要用到拓撲排序方式求得每個頂點的最早開始時間，對于活動結(jié)束狀態(tài)來說，然后規(guī)定整個工程不能超過其最早開始時間，然后倒推得到每個活動的最晚開始時間。最早開始時間等于最晚開始時間的活動就是關(guān)鍵活動，由此得到關(guān)鍵路徑。實驗步驟1、輸入頂點數(shù)量n；2、輸入邊的數(shù)量m；3、依次輸入（一共m次）圖的各邊的頂點編號