《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與課程設(shè)計(jì)》實(shí)驗(yàn)教學(xué)大綱

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與課程設(shè)計(jì)實(shí)驗(yàn)教學(xué)大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與課程設(shè)計(jì)英文名稱： Experiment and Course Project of Data Structure課程編號(hào)：2215201101 107課程性質(zhì)：課程類型：專業(yè)基礎(chǔ)課是否為獨(dú)立設(shè)課的實(shí)驗(yàn)課：是適用專業(yè)：計(jì)算機(jī)與軟件學(xué)院學(xué)時(shí)與學(xué)分：總學(xué)時(shí)：72總學(xué)分：2實(shí)驗(yàn)學(xué)時(shí)：72實(shí)驗(yàn)學(xué)分：2執(zhí)筆人：蔡茂國制定時(shí)間：2012年9月一、實(shí)驗(yàn)課的任務(wù)、性質(zhì)與目的本實(shí)驗(yàn)課程與 數(shù)據(jù)結(jié)構(gòu)理論課堂教學(xué)有機(jī)結(jié)合，相輔相成。在理論課堂教學(xué)中，比較全面、概括性地講述數(shù)據(jù)結(jié)構(gòu)學(xué)科中一些基礎(chǔ)性知識(shí)、重要概念及各種算法，而在本實(shí)驗(yàn)課程中， 將這些基礎(chǔ)性知識(shí)、

2、重要概念及各種算法，在計(jì)算機(jī)上編程實(shí)現(xiàn)，使學(xué)生能夠達(dá)到以下教學(xué)目標(biāo)：、掌握計(jì)算機(jī)處理數(shù)據(jù)的基本方法、了解算法需用的時(shí)間及空間分析方法、能夠?yàn)閷?shí)際應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法、通過在計(jì)算機(jī)上編程實(shí)現(xiàn)課程中介紹的各種算法，在程序設(shè)計(jì)能力方面得到提升。二、主要儀器設(shè)備及環(huán)境1. 計(jì)算機(jī)2. Windows軟件環(huán)境3. TurboC/VC編程環(huán)境三、實(shí)驗(yàn)項(xiàng)目的設(shè)置與實(shí)驗(yàn)內(nèi)容在舁 廳P實(shí)驗(yàn)項(xiàng)目 名稱實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)算法實(shí)驗(yàn) 要求實(shí)驗(yàn) 時(shí)數(shù)每組 人數(shù)實(shí)驗(yàn)1順序表實(shí) 驗(yàn)順序表類定義 順序表創(chuàng)建、插 入、刪除、查找 等功能的實(shí)現(xiàn) 順序表的測(cè)試運(yùn) 行(1)順序表的存儲(chǔ)結(jié)構(gòu)包含三個(gè)部分：數(shù)

3、據(jù) 數(shù)組、最大長度、實(shí)際長度(2)順序表的創(chuàng)建：分配空間、參數(shù)初始化(3)順序表的插入：位置i和后面的數(shù)據(jù)全 部后移一位，在指定位置 i插入一個(gè)數(shù)據(jù)， 長度加1(4)順序表的刪除：位置i后面的數(shù)據(jù)全部 前移一位，覆蓋掉位置i的數(shù)據(jù)，長度減一(5)順序表的查找：給出位置 i的數(shù)據(jù)必做41驗(yàn)證2單鏈表實(shí) 驗(yàn)1、鏈表結(jié)點(diǎn)表類 定義2、單鏈表類定義3、單鏈表的創(chuàng) 建、插入、刪除、 查找等功能的實(shí) 現(xiàn)4、單鏈表的測(cè)試 運(yùn)行(1)鏈表結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)包含兩部分：數(shù)據(jù)、下一結(jié)點(diǎn)指針(2)單鏈表的創(chuàng)建：分配空間、參數(shù)初始化(3)單鏈表的插入：創(chuàng)建新的結(jié)點(diǎn)，在位置i-1和位置i之間插入新的結(jié)點(diǎn)，修改相關(guān)指 針指向

4、，長度加1(4)單鏈表的刪除：修改位置 i-1結(jié)點(diǎn)的下 一結(jié)點(diǎn)指針指向i+1結(jié)點(diǎn)，刪除位置i結(jié)點(diǎn)， 長度減一(5)單鏈表的查找：給出位置 i結(jié)點(diǎn)的數(shù)據(jù)必做41驗(yàn)證算術(shù)表達(dá)式中右括號(hào)和左括號(hào)匹配的次序正力工為Zk不【件星土址 ITT而口 的二玨土山 ,3堆棧應(yīng)用 括號(hào)匹配1、順序棧類的定 義2、成員函數(shù)，包 括入棧、出棧、 取棧頂元素3、匹配判斷函數(shù)好個(gè)占后到拈勺要坂冗狼匹配日g后世用山堆棧操作特點(diǎn)，因此可以借用一個(gè)堆棧來進(jìn) 行判斷。具體方法：順序掃描算術(shù)表達(dá)式(表現(xiàn)才-個(gè)字符 串)； 當(dāng)遇到三種類型的左括號(hào)時(shí)，讓該括號(hào) 進(jìn)棧； 當(dāng)遇到某一種類型的右括號(hào)時(shí)，比較當(dāng) 前棧頂括號(hào)是否與之匹配，(4)

5、若匹配則退棧，轉(zhuǎn)(1)繼續(xù)進(jìn)行判斷；必做41驗(yàn)證4、主程序 若小匹配，則左右括號(hào)配對(duì)次序小止確， 結(jié)束。(6)若字符串當(dāng)前為某一類型的右括號(hào)而堆 棧為空，則右括號(hào)多于左括號(hào)，結(jié)束。 若字符串掃描結(jié)束而堆棧非空，則左括 號(hào)多于右括號(hào)，結(jié)束。若字符串掃描結(jié)束而堆棧為空，則左右 括號(hào)匹配正確，結(jié)束。4堆棧和隊(duì) 列應(yīng)用回 文創(chuàng)建隊(duì)列節(jié)點(diǎn)類 和鏈?zhǔn)疥?duì)列類 鏈?zhǔn)疥?duì)列的實(shí) 現(xiàn)，包括構(gòu)造函 數(shù)、析構(gòu)函數(shù)及 入隊(duì)、出隊(duì)、隊(duì) 列空否等成員函 數(shù)創(chuàng)建堆棧節(jié)點(diǎn)類 和鏈?zhǔn)蕉褩ｎ?鏈?zhǔn)蕉褩５膶?shí) 現(xiàn)，包括構(gòu)造函 數(shù)、析構(gòu)函數(shù)及設(shè)字符數(shù)組str中存放了要判斷的字符 串。把字符數(shù)組中字符逐個(gè)分別存入一個(gè)隊(duì) 列和一個(gè)堆棧，然后逐

6、個(gè)出隊(duì)列和退棧并比 較出隊(duì)列的字符和退棧的字符是否相等，若 全部相等則該字符序列是回文，否則就不是 回文。選做41驗(yàn)證進(jìn)棧、退棧、堆 ?？辗竦瘸蓡T函 數(shù)判斷是否回文函 數(shù)5串應(yīng)用KMP算法1、順序串類的定 義，包括構(gòu)造函 數(shù)、析構(gòu)函數(shù)2、模式子串的 nextj函數(shù)3、KMP匹配算法 函數(shù)4、主程序?qū)⒅鞔湍Ｊ阶哟畯牡谝晃贿M(jìn)行一比較，號(hào)-趟匹配過程中出現(xiàn)字符比較不等（失配）時(shí)，不需回溯主串指針i ,而是利用已經(jīng)得到 的“部分匹配”的結(jié)果，將模式子串向右“滑 動(dòng)”盡可能遠(yuǎn)的一段距離（nextj） 后，繼續(xù) 進(jìn)行比較。必做41驗(yàn)證6二叉樹的 遍歷及相 關(guān)應(yīng)用1、定義二叉樹結(jié)點(diǎn)類 BiTreeNode

7、2、定義二叉樹類BiTree3、編寫主程序2.先序遍歷遞歸算法（1）、若一叉樹為空，則返回；否則：（2）、訪問根結(jié)點(diǎn)（D）（3）、先序遍歷&于樹（L）（4）、先序遍歷右子樹（R）選做41設(shè)計(jì)7Huffman 編 碼的設(shè)計(jì) 與應(yīng)用1、定義 huffman 樹的結(jié)點(diǎn)結(jié)構(gòu) HuffNode2、定義存放哈夫 曼編碼的數(shù)據(jù)元 素結(jié)構(gòu)Code3、定義 huffman 類4、編寫主程序、從huffman樹的隼-個(gè)葉子結(jié)點(diǎn)開始、依次沿結(jié)點(diǎn)到根的路徑，判斷該結(jié)點(diǎn)是 父親結(jié)點(diǎn)的左孩子還是右孩子，如果是左孩 子則得到編碼0,否則得到編碼1,先得到的 編碼放在后面、直到到達(dá)根結(jié)點(diǎn)，編碼序列即為該結(jié)點(diǎn) 的編碼的

8、、對(duì)所有的葉子結(jié)點(diǎn)重復(fù) 2, 3得到編碼。必做41驗(yàn)證8圖的深度 優(yōu)先搜索 實(shí)驗(yàn)1、深度優(yōu)先搜索 類的定義2、生成圖的鄰接 矩陣3、深度優(yōu)先搜索、所有頂點(diǎn)訪問標(biāo)志visited口設(shè)置為FALSE、從某頂點(diǎn)v0開始，設(shè)v=v0、如果visitedv=FALSE ,則訪問該頂點(diǎn)v,并將頂點(diǎn)v壓入棧中，且設(shè) visitedv=TRUE、如果找到當(dāng)前頂點(diǎn)的一個(gè)新的相鄰頂點(diǎn)w（即 visitedw = FALSE ）,設(shè) v=w,重復(fù)否則（說明當(dāng)前頂點(diǎn)的所有相鄰頂點(diǎn)都已被訪問過，或者當(dāng)前頂點(diǎn)沒有相鄰頂點(diǎn)），如果當(dāng)前頂點(diǎn)是v0,退出；否則返回上一級(jí)頂點(diǎn)（即從棧中彈出一個(gè)頂點(diǎn)），重復(fù)必做41驗(yàn)證9圖的最小

9、生成樹實(shí) 驗(yàn)1、最小生成樹類 的定義2、生成圖的邊3、最小生成樹、假設(shè)N=（V,E）是連通網(wǎng)、TE是N上最小生成樹中邊的集合、U=u0 , （u0V）, TE=、在所有u UI, v V-U的邊（u,v） E中找選做41驗(yàn)證一條代價(jià)最小的邊（u,v0）并入集合TE, 同時(shí)v0并入U(xiǎn)、重復(fù)，直到 U=V10圖的拓?fù)?排序?qū)嶒?yàn)1、拓?fù)渑判蝾惖?定義2、生成圖的鄰接 矩陣3、拓?fù)渑判?、在有向圖中個(gè)沒有前驅(qū)的頂點(diǎn)且輸 出之、從圖中刪除該頂點(diǎn)和所有以它為尾的弧 重復(fù)、兩步，直到所有頂點(diǎn)輸出為止選做41驗(yàn)證11最短路徑 實(shí)驗(yàn)1、最短路徑類的 定義2、生成圖的鄰接 矩陣3、最短路徑、設(shè)V0為始點(diǎn)，S為已求得

10、的最短路徑的 終點(diǎn)的集合、j是最新求得的S中的結(jié)點(diǎn)，則下一條最 短路徑（設(shè)其終點(diǎn)為 Vi）為以下之一：、中間只經(jīng)過 S中的頂點(diǎn)j而后到達(dá)頂點(diǎn)Vi的路徑、弧 <V0, Vi>必做41驗(yàn)證12順序查找 實(shí)驗(yàn)1、順序查找類SeqSearch 的定 義2、生成順序表3、順序查找4、結(jié)果輸出、從表中最舟-個(gè)記錄開始、逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較、若某個(gè)記錄比較相等，則查找成功、若直到第1個(gè)記錄都比較不等，則查找不成功必做41驗(yàn)證13折半查找1、折半查找類BinSearch 的定義2、生成有序序列3、折半查找、n個(gè)對(duì)象從小到大存放在啟序順序表ST中，k為給定值、設(shè)low、high指向待查

11、元素所在區(qū)間的下界、上界，即 low=1, high=n、設(shè)mid指向待查區(qū)間的中點(diǎn)，即mid=（low+high）/2、讓k與mid指向的記錄比較若k=STmid.key ,查找成功，結(jié)束若 k<STmid.key ,則 high=mid-1若 k>STmid.key ,則 low=mid+1、重復(fù)、操作，直至 low>high時(shí)，查找失敗。必做41驗(yàn)證14二叉排序 樹二叉排序樹結(jié)點(diǎn) 的定義二叉排序樹類的 定義建立一棵二叉排 序樹插入一個(gè)結(jié)點(diǎn) 顯示二叉排序樹 實(shí)現(xiàn)二叉排序樹 的查找給定值與根結(jié)點(diǎn)比較：、若相等，查找成功、右小于，查找左樹；如果左樹為仝， 作插入操作；、若大于

12、，查找右子樹；如果右子樹為空， 作插入操作。必做41驗(yàn)證刪除二叉排序樹 結(jié)點(diǎn)15B+樹實(shí)驗(yàn)1、B+樹結(jié)點(diǎn)的定 義2、B+樹類的定義3、建立一棵 B+ 序樹4、B+中插入一個(gè) 結(jié)點(diǎn)5、B+中刪除一個(gè) 結(jié)點(diǎn)6、顯示B+樹7、實(shí)現(xiàn)B+樹的 查找查找算法：給定值與根結(jié)點(diǎn)中的關(guān)鍵比較：、若相等，查找成功、若小于杲個(gè)關(guān)鍵字的值，則查找對(duì)應(yīng)子樹、若大于最舟-個(gè)關(guān)鍵字的值,則查找最3-個(gè)關(guān)鍵字對(duì)應(yīng)的子樹插入記錄算法：、根據(jù)查找算法，找到最低層葉子結(jié)點(diǎn) (所 有的子樹指針為空)、如果關(guān)鍵字的數(shù)據(jù)小于m,則在結(jié)點(diǎn)的合適位置加入關(guān)鍵字； 否則，將結(jié)點(diǎn)分裂 成兩個(gè)結(jié)點(diǎn)，前一個(gè)結(jié)點(diǎn)有 (m+1)/2個(gè)關(guān) 鍵子，斤-個(gè)結(jié)

13、點(diǎn)有m-(m+1)/2個(gè)關(guān)鍵子， 而且要在雙親結(jié)點(diǎn)中重復(fù)本步(如果沒有 雙親結(jié)點(diǎn)(即為根)，則生成一個(gè)新的根 結(jié)點(diǎn))選做41驗(yàn)證16哈希查找 實(shí)驗(yàn)1、哈希表的定義2、哈希查找類BinSearch 的定義3、哈希函數(shù)4、查找哈希表5、生成哈希表6、超小哈布表、利用哈希函數(shù)(除留余數(shù)法，哈希表長 為5)及記錄的關(guān)鍵字計(jì)算出記錄的存儲(chǔ)地址 、直接到指定地址進(jìn)行查找、如果查找不成功，則采用(表頭插入) 鏈地址法，將記錄插入到指定地址所在鏈 表的頭上。必做41設(shè)計(jì)17快速排序 實(shí)驗(yàn)1、快速排序算法 類的定義2、快速排序算法3、主程序4、結(jié)果輸出對(duì)rst中記錄進(jìn)彳L趟快速排序， 附設(shè) 兩個(gè)指針i和j ,設(shè)

14、樞軸記錄 rp=rs, x=rp.key、初始時(shí)令i=s,j=t(2)、首先從j所指位置向前搜索A個(gè)關(guān)鍵字小于x的記錄，并和rp交換(3)、再從i所指位置起向后搜索，找到第一個(gè)關(guān)鍵子大丁 x的記錄，和rp交換(4)、重復(fù)上述兩步，直至 i=j為止(5)、再分別對(duì)兩個(gè)子序列進(jìn)行快速排序， 直到每個(gè)子序列只含有一個(gè)記錄為止必做41驗(yàn)證18希爾排序 實(shí)驗(yàn)1、希爾排序算法類的定義2、希爾排序算法3、主程序(1)取一個(gè)正整數(shù)d1<n,把所有相隔d1的記 錄放一組，組內(nèi)進(jìn)行直接插入排序；(2)取d2<d1,重復(fù)上述分組和排序操作；(3)直至di=1 ,即所有記錄放進(jìn)一個(gè)組中排序必做41驗(yàn)證4、

15、結(jié)果輸出為止19鏈?zhǔn)交鶖?shù) 排序?qū)嶒?yàn)1、基數(shù)排序類的 定義2、建立鏈?zhǔn)酱鎯?chǔ) 隊(duì)列3、實(shí)現(xiàn)基數(shù)排序基數(shù)排序：借助“分配”和“收集”對(duì)關(guān)鍵字進(jìn)行排序的一種方法鏈?zhǔn)交鶖?shù)排序方法：用鏈表作存儲(chǔ)結(jié)構(gòu)的基 數(shù)排序設(shè)置10個(gè)隊(duì)列，fi和ei分別為第i個(gè)隊(duì) 列的頭指針和尾指針第i趟分配：根據(jù)第i位關(guān)鍵字的值，改變 記錄的指針，將鏈表中記錄分配至 10個(gè)鏈隊(duì) 列中，每個(gè)隊(duì)列中記錄關(guān)鍵字的第i位關(guān)鍵字相同第i趟收集：改變所有非空隊(duì)列的隊(duì)尾記錄 的指針域，令其指向卜一個(gè)非空隊(duì)列的隊(duì)頭 記錄，重新將10個(gè)隊(duì)列鏈成一個(gè)鏈表 從最低位至最高位， 逐位執(zhí)行上述兩步操作， 最后得到一個(gè)后序序列選做41驗(yàn)證四、教材、實(shí)驗(yàn)教材（指導(dǎo)書）理論教材：嚴(yán)蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)，C語言版，清華大學(xué)出版社，2011.11實(shí)驗(yàn)教材：自編五、考核方式與評(píng)分辦法本課程的考核分為平時(shí)成