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

課程名稱：數(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)境VisualC++四、實驗內(nèi)容1、 輸入并建立多項式；2、 輸出多項式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2,?.,cn,en,其中n是多項式的項數(shù)，ci和ei分別是第I項的系數(shù)和指數(shù)，序列按照指數(shù)降序排列；3、 多項式a和b相加，建立多項式a+b；4、 多項式a和b相減，建立多項式a-b。五、算法描述及實驗步驟使用鏈表存儲元多項式clXel+c2Xe2+..?+cnXen如下圖所示：頭結(jié)點—4clelc2e2__，一- an A■■■■ cnen如何實現(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é)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名：學(xué)號：指導(dǎo)教師：程欣宇實驗序號：二實驗成績：一、實驗名稱棧及其應(yīng)用二、實驗?zāi)康募耙?、 熟悉棧的原理和實現(xiàn)方式；2、 理解使用棧消除函數(shù)遞歸調(diào)用的原理；3、 掌握后綴表達式計算的方法。三、實驗環(huán)境VisualC++四、實驗內(nèi)容1、 棧實現(xiàn)階乘函數(shù)；2、 棧實現(xiàn)后綴表達式的計算。五、算法描述及實驗步驟函數(shù)調(diào)用棧的結(jié)構(gòu)如下：＜調(diào)^＞用＞調(diào)^第n層調(diào)用（當(dāng)前函數(shù)局部變量空間）<回>^返^返.<5>第n-1層調(diào)用（當(dāng)前函數(shù)的主調(diào)函數(shù)變量空間）…第1層調(diào)用主函數(shù)局部變量空間函數(shù)調(diào)用的棧空間使用棧消去遞歸的算法框架如下：初始化棧；將完整問題參數(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é)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名：學(xué)號：指導(dǎo)教師：程欣宇實驗序號：三實驗成績：一、實驗名稱隊列及其應(yīng)用二、實驗?zāi)康募耙?、 熟悉隊列的原理和實現(xiàn)方式；2、 理解使用隊列進行搜索的原理；3、 掌握使用隊列進行搜索的程序設(shè)計方法。三、實驗環(huán)境VisualC++四、實驗內(nèi)容1、使用隊列實現(xiàn)教科書P50頁說描述的迷宮問題。五、算法描述及實驗步驟使用隊列進行搜索的算法框架如下：初始化隊列；將搜索的出發(fā)點入隊；while（隊列非空）{取出隊首元素所描述的位置；如果到達搜索目標(biāo)，則完成搜索，推出循環(huán)；否則將該位置可以擴展搜索的位置入隊待搜索。}實驗步驟1、2、3、六、調(diào)試過程及實驗結(jié)果詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙

課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名：學(xué)號：指導(dǎo)教師：程欣宇實驗序號：四實驗成績：一、實驗名稱串及其應(yīng)用二、實驗?zāi)康募耙?、 熟悉串的基本操作方法2、 掌握文本模式匹配算法。三、實驗環(huán)境VisualC++四、實驗內(nèi)容1、 輸入以回車作為結(jié)束符的一串字符作為主串；2、 求主串中指定的單個字符出現(xiàn)的次數(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é)對上機實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙

課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名：學(xué)號：指導(dǎo)教師：程欣宇實驗序號：五實驗成績：一、實驗名稱稀疏矩陣和多維數(shù)組的實現(xiàn)二、實驗?zāi)康募耙?、 熟悉三元組方式存儲稀疏矩陣的原理和算法；2、 掌握多維數(shù)組的存儲空間分配和訪問算法。三、實驗環(huán)境VisualC++四、實驗內(nèi)容1、 封裝個稀疏矩陣類。要求內(nèi)部使用三元組順序表表示。要求實現(xiàn)如下成員函數(shù)：a、 按三元組數(shù)組構(gòu)造b、 矩陣加法c、 矩陣轉(zhuǎn)置d、 矩陣乘法不要求實現(xiàn)性能最優(yōu)化算法，不要求使用運算符重載，要求構(gòu)造測試用例。2、 封裝一個三維數(shù)組類classArray3D內(nèi)部使用一維數(shù)組存儲數(shù)據(jù)。提供構(gòu)造函數(shù)提供訪問每一維長度的方法intgetLength(intdim)提供讀取任意元素的方法ElemTypeget(inti,intj,intk)提供與入取任意元素的方法voidset(inti,intj,intk,ElemTypevalue)五、 算法描述及實驗步驟三元組方式存儲稀疏數(shù)組：1、 表示稀疏矩陣的一個非零元素可以使用一個三元組：行號、列號、元素值。2、 使用n個三元元組表示一個稀疏矩陣，需要定義一個三元組的數(shù)組，數(shù)組大小等于n+1，其中第一個三元組存儲數(shù)組的最大行列號。多維數(shù)組的實現(xiàn)算法：1、 傳入三維數(shù)組各位大?。簄,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é)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序(核心代碼)清單或使用說明書，可另附紙

課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名：學(xué)號：指導(dǎo)教師：程欣宇實驗序號：六實驗成績：一、實驗名稱哈夫曼編碼/譯碼器二、實驗?zāi)康募耙?、 掌握二叉樹的存儲方法；2、 掌握Huffman二叉樹的構(gòu)造、編碼和譯碼算法；三、實驗環(huán)境VisualC++四、實驗內(nèi)容1、生成編碼二叉樹輸入為字符集和詞頻，輸出為哈夫曼二叉樹。字符集和詞頻如下：字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ詞頻2車357、編碼金入為一、譯碼金入為一639器設(shè)二叉卞9器設(shè)二叉卞15:計對和號計對和號1芝解碼48拍勺內(nèi)拍勺內(nèi)51］容，輸］容，輸80松出為松出為23J編碼J譯碼8/結(jié)果/內(nèi)容181161五、算法描述及實驗步驟哈夫曼二叉樹在創(chuàng)建過程中，最初為n個獨立的葉子結(jié)點，的葉子結(jié)點就是要編碼的字符，數(shù)量為n,最初為創(chuàng)建可以使用一個=實驗步驟1、2、3、六、調(diào)試過程及實驗結(jié)果詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機實踐結(jié)果進行分析，問題回答，上機的心得體會及改進意見。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙

課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：計科121實驗日期：日期姓名：學(xué)號：指導(dǎo)教師：程欣宇實驗序號：七實驗成績：一、實驗名稱圖及其應(yīng)用二、實驗?zāi)康募耙?、 熟悉圖的兩種常用存儲形式：鄰接矩陣、鄰接表；2、 熟悉圖的遍歷算法；3、 熟悉出度、入度的求法；4、 掌握拓撲排序算法；5、 掌握關(guān)鍵路徑求法。三、實驗環(huán)境VisualC++四、實驗內(nèi)容1、 定義出圖有向圖和無向圖兩種數(shù)據(jù)類型；2、 實現(xiàn)有向圖的鄰接矩陣和鄰接表；3、 實現(xiàn)無向圖的鄰接矩陣和鄰接表。4、 編寫圖的關(guān)鍵路徑算法五、算法描述及實驗步驟鄰接矩陣是使用一個二維數(shù)組存儲圖的方式，其元素c[i][j]記錄頂點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次）圖的各邊的頂點編號和權(quán)值：<i,j,w>,同時修改鄰接矩陣的a[