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

課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)班級(jí)：計(jì)科121實(shí)驗(yàn)日期：日期姓名：學(xué)號(hào)：指導(dǎo)教師：程欣宇實(shí)驗(yàn)序號(hào)：一實(shí)驗(yàn)成績(jī)：一、實(shí)驗(yàn)名稱(chēng)線性表及其應(yīng)用二、實(shí)驗(yàn)?zāi)康募耙?、 熟悉鏈表的創(chuàng)建，鏈表結(jié)點(diǎn)查找、插入和刪除；2、 理解鏈表用于存儲(chǔ)線性表的優(yōu)勢(shì)和劣勢(shì)；3、 掌握利用鏈表存儲(chǔ)一元多項(xiàng)式的數(shù)據(jù)結(jié)構(gòu)，及其運(yùn)算操作。三、實(shí)驗(yàn)環(huán)境VisualC++四、實(shí)驗(yàn)內(nèi)容1、 輸入并建立多項(xiàng)式；2、 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2,?.,cn,en,其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第I項(xiàng)的系數(shù)和指數(shù)，序列按照指數(shù)降序排列；3、 多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；4、 多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。五、算法描述及實(shí)驗(yàn)步驟使用鏈表存儲(chǔ)元多項(xiàng)式clXel+c2Xe2+..?+cnXen如下圖所示：頭結(jié)點(diǎn)—4clelc2e2__，一- an A■■■■ cnen如何實(shí)現(xiàn)這種線性鏈表表示的多項(xiàng)式的加法運(yùn)算？根據(jù)一元多項(xiàng)式相加的運(yùn)算規(guī)則：對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對(duì)應(yīng)系數(shù)相加，若其和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)不相同的項(xiàng)，則分別復(fù)抄到“和”多項(xiàng)式中去。實(shí)驗(yàn)步驟：1、2、3、六、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果詳細(xì)記錄程序在調(diào)試過(guò)程中出現(xiàn)的問(wèn)題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對(duì)上機(jī)實(shí)踐結(jié)果進(jìn)行分析，問(wèn)題回答，上機(jī)的心得體會(huì)及改進(jìn)意見(jiàn)。八、附錄源程序（核心代碼）清單或使用說(shuō)明書(shū)，可另附紙課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)班級(jí)：計(jì)科121實(shí)驗(yàn)日期：日期姓名：學(xué)號(hào)：指導(dǎo)教師：程欣宇實(shí)驗(yàn)序號(hào)：二實(shí)驗(yàn)成績(jī)：一、實(shí)驗(yàn)名稱(chēng)棧及其應(yīng)用二、實(shí)驗(yàn)?zāi)康募耙?、 熟悉棧的原理和實(shí)現(xiàn)方式；2、 理解使用棧消除函數(shù)遞歸調(diào)用的原理；3、 掌握后綴表達(dá)式計(jì)算的方法。三、實(shí)驗(yàn)環(huán)境VisualC++四、實(shí)驗(yàn)內(nèi)容1、 棧實(shí)現(xiàn)階乘函數(shù)；2、 棧實(shí)現(xiàn)后綴表達(dá)式的計(jì)算。五、算法描述及實(shí)驗(yà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)用的?？臻g使用棧消去遞歸的算法框架如下：初始化棧；將完整問(wèn)題參數(shù)壓棧；while（棧非空）{取出棧頂元素所描述的問(wèn)題如果可以直接解決，則直接解決否則分解為子問(wèn)題壓棧}后綴表達(dá)式是運(yùn)算符在運(yùn)算數(shù)之后的一種表達(dá)式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，不需要比較運(yùn)算符優(yōu)先級(jí)別，只需要每次讀到運(yùn)算數(shù)時(shí)壓棧，讀到運(yùn)算符時(shí)將運(yùn)算數(shù)出棧，將結(jié)果壓棧即可。最后的運(yùn)算結(jié)果存放在棧底。實(shí)驗(yàn)步驟1、2、3、六、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果詳細(xì)記錄程序在調(diào)試過(guò)程中出現(xiàn)的問(wèn)題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對(duì)上機(jī)實(shí)踐結(jié)果進(jìn)行分析，問(wèn)題回答，上機(jī)的心得體會(huì)及改進(jìn)意見(jiàn)。八、附錄源程序（核心代碼）清單或使用說(shuō)明書(shū)，可另附紙課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)班級(jí)：計(jì)科121實(shí)驗(yàn)日期：日期姓名：學(xué)號(hào)：指導(dǎo)教師：程欣宇實(shí)驗(yàn)序號(hào)：三實(shí)驗(yàn)成績(jī)：一、實(shí)驗(yàn)名稱(chēng)隊(duì)列及其應(yīng)用二、實(shí)驗(yàn)?zāi)康募耙?、 熟悉隊(duì)列的原理和實(shí)現(xiàn)方式；2、 理解使用隊(duì)列進(jìn)行搜索的原理；3、 掌握使用隊(duì)列進(jìn)行搜索的程序設(shè)計(jì)方法。三、實(shí)驗(yàn)環(huán)境VisualC++四、實(shí)驗(yàn)內(nèi)容1、使用隊(duì)列實(shí)現(xiàn)教科書(shū)P50頁(yè)說(shuō)描述的迷宮問(wèn)題。五、算法描述及實(shí)驗(yàn)步驟使用隊(duì)列進(jìn)行搜索的算法框架如下：初始化隊(duì)列；將搜索的出發(fā)點(diǎn)入隊(duì)；while（隊(duì)列非空）{取出隊(duì)首元素所描述的位置；如果到達(dá)搜索目標(biāo)，則完成搜索，推出循環(huán)；否則將該位置可以擴(kuò)展搜索的位置入隊(duì)待搜索。}實(shí)驗(yàn)步驟1、2、3、六、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果詳細(xì)記錄程序在調(diào)試過(guò)程中出現(xiàn)的問(wèn)題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對(duì)上機(jī)實(shí)踐結(jié)果進(jìn)行分析，問(wèn)題回答，上機(jī)的心得體會(huì)及改進(jìn)意見(jiàn)。八、附錄源程序（核心代碼）清單或使用說(shuō)明書(shū)，可另附紙

課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)班級(jí)：計(jì)科121實(shí)驗(yàn)日期：日期姓名：學(xué)號(hào)：指導(dǎo)教師：程欣宇實(shí)驗(yàn)序號(hào)：四實(shí)驗(yàn)成績(jī)：一、實(shí)驗(yàn)名稱(chēng)串及其應(yīng)用二、實(shí)驗(yàn)?zāi)康募耙?、 熟悉串的基本操作方法2、 掌握文本模式匹配算法。三、實(shí)驗(yàn)環(huán)境VisualC++四、實(shí)驗(yàn)內(nèi)容1、 輸入以回車(chē)作為結(jié)束符的一串字符作為主串；2、 求主串中指定的單個(gè)字符出現(xiàn)的次數(shù)和位置；3、 求主串中指定子串出現(xiàn)的次數(shù)和位置；4、 求主串中指定單詞出現(xiàn)的次數(shù)和位置，注意單詞與子串的區(qū)別。五、算法描述及實(shí)驗(yàn)步驟算法描述：1、 統(tǒng)計(jì)指定單個(gè)字符出現(xiàn)的次數(shù)和位置，只需遍歷主串的每一個(gè)字符即可。2、 求指定子串出現(xiàn)的位置，可以采用逐位置滑動(dòng)的匹配方法和KMP快速匹配算法。3、 求指定單詞出現(xiàn)的位置，關(guān)鍵是考慮單詞和子串的不同，即：?jiǎn)卧~首尾要么是空格要么是主串的首尾，所以在匹配到子串后，作此檢查即可。另外，也可以考慮采用在主串和單詞首尾加入空格的方法，進(jìn)行子串搜索。實(shí)驗(yàn)步驟1、2、3、六、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果詳細(xì)記錄程序在調(diào)試過(guò)程中出現(xiàn)的問(wèn)題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對(duì)上機(jī)實(shí)踐結(jié)果進(jìn)行分析，問(wèn)題回答，上機(jī)的心得體會(huì)及改進(jìn)意見(jiàn)。八、附錄源程序（核心代碼）清單或使用說(shuō)明書(shū)，可另附紙

課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)班級(jí)：計(jì)科121實(shí)驗(yàn)日期：日期姓名：學(xué)號(hào)：指導(dǎo)教師：程欣宇實(shí)驗(yàn)序號(hào)：五實(shí)驗(yàn)成績(jī)：一、實(shí)驗(yàn)名稱(chēng)稀疏矩陣和多維數(shù)組的實(shí)現(xiàn)二、實(shí)驗(yàn)?zāi)康募耙?、 熟悉三元組方式存儲(chǔ)稀疏矩陣的原理和算法；2、 掌握多維數(shù)組的存儲(chǔ)空間分配和訪問(wèn)算法。三、實(shí)驗(yàn)環(huán)境VisualC++四、實(shí)驗(yàn)內(nèi)容1、 封裝個(gè)稀疏矩陣類(lèi)。要求內(nèi)部使用三元組順序表表示。要求實(shí)現(xiàn)如下成員函數(shù)：a、 按三元組數(shù)組構(gòu)造b、 矩陣加法c、 矩陣轉(zhuǎn)置d、 矩陣乘法不要求實(shí)現(xiàn)性能最優(yōu)化算法，不要求使用運(yùn)算符重載，要求構(gòu)造測(cè)試用例。2、 封裝一個(gè)三維數(shù)組類(lèi)classArray3D內(nèi)部使用一維數(shù)組存儲(chǔ)數(shù)據(jù)。提供構(gòu)造函數(shù)提供訪問(wèn)每一維長(zhǎng)度的方法intgetLength(intdim)提供讀取任意元素的方法ElemTypeget(inti,intj,intk)提供與入取任意元素的方法voidset(inti,intj,intk,ElemTypevalue)五、 算法描述及實(shí)驗(yàn)步驟三元組方式存儲(chǔ)稀疏數(shù)組：1、 表示稀疏矩陣的一個(gè)非零元素可以使用一個(gè)三元組：行號(hào)、列號(hào)、元素值。2、 使用n個(gè)三元元組表示一個(gè)稀疏矩陣，需要定義一個(gè)三元組的數(shù)組，數(shù)組大小等于n+1，其中第一個(gè)三元組存儲(chǔ)數(shù)組的最大行列號(hào)。多維數(shù)組的實(shí)現(xiàn)算法：1、 傳入三維數(shù)組各位大?。簄,m,p，動(dòng)態(tài)申請(qǐng)內(nèi)存空間，size=n*m*p；2、 訪問(wèn)元素需要傳入下標(biāo)數(shù)組：i,j,k，其對(duì)應(yīng)存儲(chǔ)空間為：Loc(i,j,k)=i*p*m+j*p+k實(shí)驗(yàn)步驟1、2、3、六、 調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果詳細(xì)記錄程序在調(diào)試過(guò)程中出現(xiàn)的問(wèn)題及解決方法。記錄程序執(zhí)行的結(jié)果。七、總結(jié)對(duì)上機(jī)實(shí)踐結(jié)果進(jìn)行分析，問(wèn)題回答，上機(jī)的心得體會(huì)及改進(jìn)意見(jiàn)。八、附錄源程序(核心代碼)清單或使用說(shuō)明書(shū)，可另附紙

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

課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)班級(jí)：計(jì)科121實(shí)驗(yàn)日期：日期姓名：學(xué)號(hào)：指導(dǎo)教師：程欣宇實(shí)驗(yàn)序號(hào)：七實(shí)驗(yàn)成績(jī)：一、實(shí)驗(yàn)名稱(chēng)圖及其應(yīng)用二、實(shí)驗(yàn)?zāi)康募耙?、 熟悉圖的兩種常用存儲(chǔ)形式：鄰接矩陣、鄰接表；2、 熟悉圖的遍歷算法；3、 熟悉出度、入度的求法；4、 掌握拓?fù)渑判蛩惴ǎ?、 掌握關(guān)鍵路徑求法。三、實(shí)驗(yàn)環(huán)境VisualC++四、實(shí)驗(yàn)內(nèi)容1、 定義出圖有向圖和無(wú)向圖兩種數(shù)據(jù)類(lèi)型；2、 實(shí)現(xiàn)有向圖的鄰接矩陣和鄰接表；3、 實(shí)現(xiàn)無(wú)向圖的鄰接矩陣和鄰接表。4、 編寫(xiě)圖的關(guān)鍵路徑算法五、算法描述及實(shí)驗(yàn)步驟鄰接矩陣是使用一個(gè)二維數(shù)組存儲(chǔ)圖的方式，其元素c[i][j]記錄頂點(diǎn)Vi和頂點(diǎn)Vj的關(guān)聯(lián)情況。鄰接鏈表使用一個(gè)頂點(diǎn)數(shù)組存儲(chǔ)頂點(diǎn)信息，頂點(diǎn)數(shù)組中每條記錄指向一條弧鏈表，第i條鏈表紀(jì)錄了所有從頂點(diǎn)Vi出去的弧的信息。拓?fù)渑判蚴侵v一個(gè)偏序關(guān)系確定為一個(gè)全序關(guān)系的過(guò)程，其算法是使用一個(gè)棧紀(jì)錄當(dāng)前入度為0的頂點(diǎn)，然后每次選擇棧頂元素出棧和作相應(yīng)調(diào)整，最后得到的出棧順序就是拓?fù)湫?。在求關(guān)鍵路徑中需要用到拓?fù)渑判蚍绞角蟮妹總€(gè)頂點(diǎn)的最早開(kāi)始時(shí)間，對(duì)于活動(dòng)結(jié)束狀態(tài)來(lái)說(shuō)，然后規(guī)定整個(gè)工程不能超過(guò)其最早開(kāi)始時(shí)間，然后倒推得到每個(gè)活動(dòng)的最晚開(kāi)始時(shí)間。最早開(kāi)始時(shí)間等?于最晚開(kāi)始時(shí)間的活動(dòng)就是關(guān)鍵活動(dòng)，由此得到關(guān)鍵路徑。實(shí)驗(yàn)步驟1、輸入頂點(diǎn)數(shù)量n；2、 輸入邊的數(shù)量m；3、 依次輸入（一共m次）圖的各邊的頂點(diǎn)編號(hào)和權(quán)值：<i,j,w>,同時(shí)修改鄰接矩陣的a[