2017年數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)內(nèi)容

1、實(shí)驗(yàn)一線性表1實(shí)驗(yàn)?zāi)康耐ㄟ^選擇下面三個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：熟悉C+語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法學(xué)習(xí)指針、模板類、異常處理的使用掌握鏈?zhǔn)浇Y(jié)構(gòu)線性表的操作的實(shí)現(xiàn)方法學(xué)習(xí)使用線性表解決實(shí)際問題的能力2實(shí)驗(yàn)內(nèi)容2.1題目1基礎(chǔ)實(shí)驗(yàn)根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表， 并完成線性表的基本功能。線性表存儲(chǔ)結(jié)構(gòu)（五選一）：1、帶頭結(jié)點(diǎn)的單鏈表2、不帶頭結(jié)點(diǎn)的單鏈表3、循環(huán)鏈表4、雙鏈表5、靜態(tài)鏈表線性表的基本功能：1、構(gòu)造函數(shù)：包括構(gòu)造空鏈表、頭插法構(gòu)造鏈表、尾插法構(gòu)造鏈表2、復(fù)制構(gòu)造函數(shù)3、插入函數(shù)：可以在任意指定位置插入元素4、刪除函數(shù)：可以刪

2、出任意指定位置的結(jié)點(diǎn)5、查找：可以輸出任意指定位置的元素6、獲取鏈表長度7、打印鏈表數(shù)據(jù)8、析構(gòu)函數(shù)編寫測試main（）函數(shù)測試線性表的正確性。思考問題（選作）:1、若輸入為亂序的數(shù)組，編寫一個(gè)新的構(gòu)造函數(shù)，使得構(gòu)造的鏈表按升序 排列？2、若有兩個(gè)按升序排列的鏈表A和B，編寫一個(gè)合并函數(shù)，完成A=A B 的功能，使得合并后的鏈表沒有重復(fù)數(shù)據(jù)。3、編寫一個(gè)鏈表逆置函數(shù)，若鏈表中的每一個(gè)結(jié)點(diǎn)為正序排列，則執(zhí)行完 該函數(shù)，鏈表中的每一個(gè)結(jié)點(diǎn)倒序排列。2.2題目2應(yīng)用實(shí)驗(yàn)利用線性表實(shí)現(xiàn)一個(gè)通訊錄管理，通信錄的數(shù)據(jù)格式如下：struct DataTypeint ID;編號char name10;姓名ch

3、ar ch;性別char phone13;電話char addr31;地址;實(shí)現(xiàn)方式（三選一）：1可以在題目一實(shí)現(xiàn)的鏈表基礎(chǔ)上實(shí)現(xiàn)該通訊錄，通訊錄就相當(dāng)于鏈表 類的一個(gè)實(shí)例。2可以使STL中的vector或list實(shí)現(xiàn)該通訊錄，體會(huì)STL使用的好處。3可以單獨(dú)實(shí)現(xiàn)一個(gè)通訊錄類來實(shí)現(xiàn)。功能要求：實(shí)現(xiàn)通訊錄的建立、增加、刪除、修改、查詢等功能能夠?qū)崿F(xiàn)簡單的菜單交互，即可以根據(jù)用戶輸入的命令，選擇不同的操 作。能夠保存每次更新的數(shù)據(jù)（選作）能夠進(jìn)行通訊錄分類，比如班級類、好友類、黑名單等等（選作）編寫測試main（）函數(shù)測試通訊錄的正確性2.3題目3應(yīng)用實(shí)驗(yàn)利用線性表實(shí)現(xiàn)一個(gè)一元多項(xiàng)式Polynom

4、ial類。Polynomial的結(jié)點(diǎn)結(jié)構(gòu)如下：struct termfloat coef; 系數(shù)int expn;指數(shù)；實(shí)現(xiàn)方式（三選一）：1可以在題目一實(shí)現(xiàn)的鏈表基礎(chǔ)上實(shí)現(xiàn)該一元多項(xiàng)式，一元多項(xiàng)式就相 當(dāng)于鏈表類的一個(gè)派生類。2可以使STL中的vector或list實(shí)現(xiàn)該一元多項(xiàng)式，體會(huì)STL使用的好 處。3可以單獨(dú)實(shí)現(xiàn)一個(gè)一元多項(xiàng)式類來實(shí)現(xiàn)。功能要求：能夠?qū)崿F(xiàn)一元多項(xiàng)式的輸入和輸出能夠進(jìn)行一元多項(xiàng)式相加能夠計(jì)算一元多項(xiàng)式在x處的值能夠計(jì)算一元多項(xiàng)式的導(dǎo)數(shù)（選作）編寫測試main（）函數(shù)測試線性表的正確性3代碼要求1、必須要有異常處理，比如刪除空鏈表時(shí)需要拋出異常；2、保持良好的編程的風(fēng)格：

5、代碼段與段之間要有空行和縮近標(biāo)識符名稱應(yīng)該與其代表的意義一致函數(shù)名之前應(yīng)該添加注釋說明該函數(shù)的功能關(guān)鍵代碼應(yīng)添加注釋說明其功能3、代碼中需要標(biāo)注每一個(gè)函數(shù)的時(shí)間復(fù)雜度實(shí)驗(yàn)二樹1實(shí)驗(yàn)?zāi)康耐ㄟ^選擇下面兩個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：掌握二叉樹基本操作的實(shí)現(xiàn)方法 了解赫夫曼樹的思想和相關(guān)概念學(xué)習(xí)使用二叉樹解決實(shí)際問題的能力2實(shí)驗(yàn)內(nèi)容2.1題目1基礎(chǔ)實(shí)驗(yàn)根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉樹。完成二叉樹的基本功能：1、二叉樹的建立2、二叉樹的復(fù)制3、前序遍歷二叉樹4、中序遍歷二叉樹5、后序遍歷二叉樹6、按層序遍歷二叉樹7、求二叉樹的結(jié)點(diǎn)數(shù)8、二叉樹的銷毀編寫測試main()函數(shù)

6、測試線性表的正確性。思考問題(選作)：1、若數(shù)據(jù)量非常大，如何使得構(gòu)造二叉樹時(shí)棧不溢出？使用非遞歸方式編 寫新的二叉樹的構(gòu)造函數(shù)，建立二叉樹。提示：可以使用STL中的stack來輔助 實(shí)現(xiàn)。2、若二叉樹的每一個(gè)結(jié)點(diǎn)具有數(shù)值，如何搜索二叉樹，找到指定值的葉子 結(jié)點(diǎn)？3、若已知葉子結(jié)點(diǎn)的指針，如何輸出從根到該葉子的路徑？2.2題目2基礎(chǔ)實(shí)驗(yàn)根據(jù)二叉排序樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉排序樹。 提示：二叉排序樹的理論內(nèi)容見教材第7章。二叉排序樹的基本功能：1、二叉排序樹的建立2、二叉排序樹的查找3、二叉排序樹的插入4、二叉排序樹的刪除5、二叉排序樹的銷毀編寫測試main()函數(shù)測試二

7、叉排序樹的正確性。思考問題(選作)：1、如何判斷建立的二叉排序樹是否平衡？編寫一個(gè)函數(shù)，完成該功能。3代碼要求1、必須要有異常處理，比如刪除空鏈表時(shí)需要拋出異常；2、保持良好的編程的風(fēng)格：代碼段與段之間要有空行和縮近標(biāo)識符名稱應(yīng)該與其代表的意義一致函數(shù)名之前應(yīng)該添加注釋說明該函數(shù)的功能關(guān)鍵代碼應(yīng)添加注釋說明其功能3、遞歸程序注意調(diào)用的過程，防止棧溢出4、代碼中需要標(biāo)注每一個(gè)函數(shù)的時(shí)間復(fù)雜度實(shí)驗(yàn)三圖1實(shí)驗(yàn)?zāi)康耐ㄟ^完成圖的相關(guān)算法的實(shí)現(xiàn)，掌握如下內(nèi)容：掌握圖的兩種基本的存儲(chǔ)結(jié)構(gòu)，以及圖的基本算法的實(shí)現(xiàn)方法 了解最小生成樹的思想和相關(guān)概念 了解最短路徑的思想和相關(guān)概念學(xué)習(xí)使用圖解決實(shí)際問題的能力2實(shí)

8、驗(yàn)內(nèi)容2.1題目1基礎(chǔ)實(shí)驗(yàn)根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實(shí)現(xiàn)一個(gè)圖。圖的基本功能：1、圖的建立2、圖的銷毀3、深度優(yōu)先遍歷圖4、廣度優(yōu)先遍歷圖5、使用普里姆算法生成最小生成樹6、使用克魯斯卡爾算法生成最小生成樹7、求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑編寫測試main()函數(shù)測試圖的正確性思考問題(選作)：1、若測試數(shù)據(jù)量較大，如何使得棧不溢出？使用非遞歸方式編寫新的深度 優(yōu)先遍歷函數(shù)。提示：可以使用STL中的stack來輔助實(shí)現(xiàn)。2、最短路徑D算法，是否可以優(yōu)化？請寫出優(yōu)化的思路并計(jì)算時(shí)間復(fù)雜度， 同時(shí)實(shí)現(xiàn)一個(gè)新的優(yōu)化的最短路徑算法。3代碼要求1、必須要有異常處理，比如刪除空鏈表

9、時(shí)需要拋出異常;2、保持良好的編程的風(fēng)格：代碼段與段之間要有空行和縮近標(biāo)識符名稱應(yīng)該與其代表的意義一致函數(shù)名之前應(yīng)該添加注釋說明該函數(shù)的功能關(guān)鍵代碼應(yīng)添加注釋說明其功能3、遞歸程序注意調(diào)用的過程，防止棧溢出實(shí)驗(yàn)四1實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)為可選實(shí)驗(yàn)，用于提高同學(xué)們使用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的能力。通 過選擇下面5個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：深度了解內(nèi)存分配和釋放的原理熟練掌握棧和遞歸的進(jìn)一步應(yīng)用學(xué)習(xí)矩陣的相關(guān)算法在BMP圖像中的應(yīng)用深入掌握二叉樹在哈夫曼編碼中的算法實(shí)現(xiàn) 了解圖的相關(guān)算法的應(yīng)用A進(jìn)一步提高編程能力4.1題目1動(dòng)態(tài)內(nèi)存管理動(dòng)態(tài)內(nèi)存管理是操作系統(tǒng)的基本功能之一，用于響應(yīng)用戶程序?qū)?nèi)存的申

10、請 和釋放請求。初始化時(shí)，系統(tǒng)只有一塊連續(xù)的空閑內(nèi)存；然后，當(dāng)不斷有用戶申 請內(nèi)存時(shí)，系統(tǒng)會(huì)根據(jù)某種策略選擇一塊合適的連續(xù)內(nèi)存供用戶程序使用；當(dāng)用 戶程序釋放內(nèi)存時(shí)，系統(tǒng)將其回收，供以后重新分配，釋放時(shí)需要計(jì)算該內(nèi)存塊 的左右是否也為空閑塊，若是，則需要合并變成更大的空閑塊。試設(shè)計(jì)用于模擬動(dòng)態(tài)內(nèi)存管理的內(nèi)存池類?；疽螅?、實(shí)現(xiàn)內(nèi)存池MemoryPool(int size)的初始化2、實(shí)現(xiàn) Allocate(int size)接口3、實(shí)現(xiàn) Free(void *p)接口4、實(shí)現(xiàn)內(nèi)存池的析構(gòu)5、在分配內(nèi)存空間時(shí)，可選擇不同的內(nèi)存分配策略：最佳擬合策略、 最差擬合策略或最先擬合策略。實(shí)現(xiàn)其中至少

11、兩種分配策略。編寫測試main()函數(shù)對類中各個(gè)接口和各種分配策略進(jìn)行測試，并實(shí)時(shí)顯示 內(nèi)存池中的占用塊和空閑塊的變化情況。表達(dá)式求值是程序設(shè)計(jì)語言編譯中最近本的問題，它要求把一個(gè)表達(dá)式翻譯 成能夠直接求值的序列。例如用戶輸入字符串“ 14+(13-2)*2-11*5)*2”，程序可 以自動(dòng)計(jì)算得到最終的結(jié)果。在這里，我們將問題簡化，假定算數(shù)表達(dá)式的值均 為非負(fù)整數(shù)常數(shù)，不包含變量、小數(shù)和字符常量。試設(shè)計(jì)一個(gè)算術(shù)四則運(yùn)算表達(dá)式求值的簡單計(jì)算器。基本要求：1、操作數(shù)均為非負(fù)整數(shù)常數(shù)，操作符僅為+、-、*、/、(和)；2、編寫main函數(shù)進(jìn)行測試。4.3題目3bmp圖像處理實(shí)現(xiàn)一個(gè)識別BMP文件的

12、圖像類，能夠進(jìn)行以下圖像處理?；疽螅?、能夠?qū)?4位真彩色Bmp文件讀入內(nèi)存；2、能夠?qū)?4位真彩色Bmp文件重新寫入文件；3、能夠?qū)?4位真彩色Bmp文件進(jìn)行24位灰度處理；4、能夠?qū)?4位灰度Bmp文件進(jìn)行8位灰度處理；5、能夠?qū)?位灰度Bmp文件轉(zhuǎn)化成黑白圖像；6、能夠?qū)D像進(jìn)行平滑處理；7、其他：自定義操作，比如翻轉(zhuǎn)、亮度調(diào)節(jié)、對比度調(diào)節(jié)、24位真彩色轉(zhuǎn) 256色等。提示：1、參考教材數(shù)據(jù)結(jié)構(gòu)與STL第四章4.4小節(jié)。2、灰度處理的轉(zhuǎn)換公式Grey=0.3*Red+0.59*Blue+0.11*Green3、平滑處理采用鄰域平均法進(jìn)行，分成4鄰域和8鄰域平滑，基本原理就 是將每一個(gè)

13、像素點(diǎn)的值設(shè)置為其周圍各點(diǎn)像素值得平均值。4、亮度調(diào)節(jié)公式，a為亮度調(diào)節(jié)參數(shù)，0 a 1,越接近0，變化越大R = pow (R, a) * pow (255, 1 - a)G = pow (G, a) * pow (255, 1 - a)B = pow (B, a) * pow (255, 1 - a)5、對比度調(diào)節(jié)公式，a為對比度調(diào)節(jié)參數(shù)，-1 a 1，(中間值一般為128)R=中間值+(R-中間值)*(1+a)G=中間值+(G-中間值)*(1+a)B=中間值+(B-中間值)*(1+a)注意：調(diào)整對比度的時(shí)候容易發(fā)生越界，需要進(jìn)行邊界處理6、24位真彩色轉(zhuǎn)256色，需要手動(dòng)添加顏色表在BM

14、P頭結(jié)構(gòu)中，可以使 用位截?cái)喾ā⒘餍猩惴?、中位切分算法、八叉樹算法等方法?shí)現(xiàn)。4.4題目4哈夫曼樹利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編/解碼器?；疽螅?、初始化(Init)：能夠?qū)斎氲娜我忾L度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè) 字符的頻度，并建立赫夫曼樹2、建立編碼表(CreateTable):利用已經(jīng)建好的赫夫曼樹進(jìn)行編碼，并將 每個(gè)字符的編碼輸出。3、編碼(Encoding)：根據(jù)編碼表對輸入的字符串進(jìn)行編碼，并將編碼后 的字符串輸出。4、譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對編碼后的字符串進(jìn)行譯 碼，并輸出譯碼結(jié)果。5、打印(Print)：以直觀的方式打印赫夫曼樹(選作)6、計(jì)算輸入

15、的字符串編碼前和編碼后的長度，并進(jìn)行分析，討論赫夫 曼編碼的壓縮效果。測試數(shù)據(jù)：I love data Structure, I love Computer。I will try my best to study data Structure.提示：1、用戶界面可以設(shè)計(jì)為“菜單”方式：能夠進(jìn)行交互。2、根據(jù)輸入的字符串中每個(gè)字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對沒有出現(xiàn)的 字符一律不用編碼。4.5題目5運(yùn)動(dòng)會(huì)比賽問題問題：設(shè)某個(gè)田徑運(yùn)動(dòng)會(huì)共有七個(gè)項(xiàng)目的比賽，分別為100米、200米、跳 高、跳遠(yuǎn)、鉛球、鐵餅和標(biāo)槍。每個(gè)選手最多參加3個(gè)項(xiàng)目，現(xiàn)有六名選手參賽， 他們選擇的項(xiàng)目如表1-1所示?？紤]到每個(gè)選手的參加的各個(gè)項(xiàng)目不能同時(shí)進(jìn)行，則如何設(shè)計(jì)合理的比賽日程，使運(yùn)動(dòng)會(huì)在盡可能