實驗一線性表1實驗目的通過選擇下面三個題目之一進行實現(xiàn)，掌握如下內(nèi)容：＞熟悉C++語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法＞學習指針、模板類、異常處理的使用＞掌握鏈式結(jié)構(gòu)線性表的操作的實現(xiàn)方法＞學習使用線性表解決實際問題的能力2實驗內(nèi)容2.1題目1——基礎(chǔ)實驗根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈式結(jié)構(gòu)實現(xiàn)線性表并完成線性表的基本功能。線性表存儲結(jié)構(gòu)（五選一）：1、 帶頭結(jié)點的單鏈表2、 不帶頭結(jié)點的單鏈表3、 循環(huán)鏈表4、 雙鏈表5、 靜態(tài)鏈表線性表的基本功能：1、 構(gòu)造函數(shù)：包括構(gòu)造空鏈表、頭插法構(gòu)造鏈表、尾插法構(gòu)造鏈表2、 復制構(gòu)造函數(shù)3、 插入函數(shù)：可以在任意指定位置插入元素4、 刪除函數(shù)：可以刪出任意指定位置的結(jié)點5、 查找：可以輸出任意指定位置的元素6、 獲取鏈表長度7、 打印鏈表數(shù)據(jù)8、 析構(gòu)函數(shù)編寫測試main（）函數(shù)測試線性表的正確性。思考問題（選作）：1、若輸入為亂序的數(shù)組，編寫一個新的構(gòu)造函數(shù)，使得構(gòu)造的鏈表按升序排列？2、 若有兩個按升序排列的鏈表A和B,編寫一個合并函數(shù)，完成A=AB的功能，使得合并后的鏈表沒有重復數(shù)據(jù)。3、 編寫一個鏈表逆置函數(shù)，若鏈表中的每一個結(jié)點為正序排列，則執(zhí)行完該函數(shù)，鏈表中的每一個結(jié)點倒序排列。2.2題目2——應用實驗利用線性表實現(xiàn)一個通訊錄管理，通信錄的數(shù)據(jù)格式如下：structDataType{intID;//編號charname[10];//姓名charch;//性別charphone[13];//電話charaddr[31];//地址};實現(xiàn)方式（三選一）：可以在題目一實現(xiàn)的鏈表基礎(chǔ)上實現(xiàn)該通訊錄，通訊錄就相當于鏈表類的一個實例。可以使STL中的vector或list實現(xiàn)該通訊錄，體會STL使用的好處?？梢詥为殞崿F(xiàn)一個通訊錄類來實現(xiàn)。功能要求：＞實現(xiàn)通訊錄的建立、增加、刪除、修改、查詢等功能＞能夠?qū)崿F(xiàn)簡單的菜單交互，即可以根據(jù)用戶輸入的命令，選擇不同的操作。＞能夠保存每次更新的數(shù)據(jù)（選作）＞能夠進行通訊錄分類，比如班級類、好友類、黑名單等等（選作）編寫測試main（）函數(shù)測試通訊錄的正確性2.3題目3——應用實驗利用線性表實現(xiàn)一個一元多項式Polynomial類。Polynomial的結(jié)點結(jié)構(gòu)如下：structterm{floatcoef;//系數(shù)intexpn; //指數(shù)};實現(xiàn)方式（三選一）：可以在題目一實現(xiàn)的鏈表基礎(chǔ)上實現(xiàn)該一元多項式，一元多項式就相當于鏈表類的一個派生類?？梢允筍TL中的vector或list實現(xiàn)該一元多項式，體會STL使用的好處?？梢詥为殞崿F(xiàn)一個一元多項式類來實現(xiàn)。功能要求：＞能夠?qū)崿F(xiàn)一元多項式的輸入和輸出＞能夠進行一元多項式相加＞能夠計算一元多項式在X處的值＞能夠計算一元多項式的導數(shù)（選作）編寫測試main（）函數(shù)測試線性表的正確性3代碼要求1、 必須要有異常處理，比如刪除空鏈表時需要拋出異常2、 保持良好的編程的風格：＞代碼段與段之間要有空行和縮近＞標識符名稱應該與其代表的意義一致＞函數(shù)名之前應該添加注釋說明該函數(shù)的功能＞關(guān)鍵代碼應添加注釋說明其功能3、 代碼中需要標注每一個函數(shù)的時間復雜度實驗二樹1實驗目的通過選擇下面兩個題目之一進行實現(xiàn)，掌握如下內(nèi)容：＞掌握二叉樹基本操作的實現(xiàn)方法＞ 了解赫夫曼樹的思想和相關(guān)概念＞學習使用二叉樹解決實際問題的能力2實驗內(nèi)容2.1題目1——基礎(chǔ)實驗根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實現(xiàn)一個二叉樹完成二叉樹的基本功能：1、 二叉樹的建立2、 二叉樹的復制3、 前序遍歷二叉樹4、 中序遍歷二叉樹5、 后序遍歷二叉樹6、 按層序遍歷二叉樹7、 求二叉樹的結(jié)點數(shù)8、 二叉樹的銷毀編寫測試main()函數(shù)測試線性表的正確性。思考問題(選作)：1、 若數(shù)據(jù)量非常大，如何使得構(gòu)造二叉樹時棧不溢出？使用非遞歸方式編寫新的二叉樹的構(gòu)造函數(shù)，建立二叉樹。提示：可以使用STL中的stack來輔助實現(xiàn)。2、 若二叉樹的每一個結(jié)點具有數(shù)值，如何搜索二叉樹，找到指定值的葉子結(jié)點？3、 若已知葉子結(jié)點的指針，如何輸出從根到該葉子的路徑？2.2題目2——基礎(chǔ)實驗根據(jù)二叉排序樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實現(xiàn)一個二叉排序樹。提示：二叉排序樹的理論內(nèi)容見教材第7章。二叉排序樹的基本功能：1、二叉排序樹的建立2、二叉排序樹的查找3、二叉排序樹的插入4、二叉排序樹的刪除5、二叉排序樹的銷毀編寫測試main()函數(shù)測試二叉排序樹的正確性。思考問題(選作)：1、 如何判斷建立的二叉排序樹是否平衡？編寫一個函數(shù)，完成該功能。3代碼要求1、必須要有異常處理，比如刪除空鏈表時需要拋出異常；2、 保持良好的編程的風格：＞代碼段與段之間要有空行和縮近＞標識符名稱應該與其代表的意義一致＞函數(shù)名之前應該添加注釋說明該函數(shù)的功能＞關(guān)鍵代碼應添加注釋說明其功能3、 遞歸程序注意調(diào)用的過程，防止棧溢出4、 代碼中需要標注每一個函數(shù)的時間復雜度實驗三圖1實驗目的通過完成圖的相關(guān)算法的實現(xiàn)，掌握如下內(nèi)容：＞掌握圖的兩種基本的存儲結(jié)構(gòu)，以及圖的基本算法的實現(xiàn)方法＞了解最小生成樹的思想和相關(guān)概念＞了解最短路徑的思想和相關(guān)概念＞學習使用圖解決實際問題的能力2實驗內(nèi)容2.1題目1——基礎(chǔ)實驗根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實現(xiàn)一個圖圖的基本功能：1、 圖的建立2、 圖的銷毀3、 深度優(yōu)先遍歷圖4、 廣度優(yōu)先遍歷圖5、 使用普里姆算法生成最小生成樹6、 使用克魯斯卡爾算法生成最小生成樹7、 求指定頂點到其他各頂點的最短路徑編寫測試main()函數(shù)測試圖的正確性思考問題(選作)：1、 若測試數(shù)據(jù)量較大，如何使得棧不溢出？使用非遞歸方式編寫新的深度優(yōu)先遍歷函數(shù)。提示：可以使用STL中的stack來輔助實現(xiàn)。2、 最短路徑D算法，是否可以優(yōu)化？請寫出優(yōu)化的思路并計算時間復雜度，同時實現(xiàn)一個新的優(yōu)化的最短路徑算法。3代碼要求1、必須要有異常處理，比如刪除空鏈表時需要拋出異常2、 保持良好的編程的風格：＞代碼段與段之間要有空行和縮近＞標識符名稱應該與其代表的意義一致＞函數(shù)名之前應該添加注釋說明該函數(shù)的功能＞關(guān)鍵代碼應添加注釋說明其功能3、 遞歸程序注意調(diào)用的過程，防止棧溢出1實驗目的本實驗為可選實驗，用于提高同學們使用數(shù)據(jù)結(jié)構(gòu)解決實際問題的能力。通過選擇下面5個題目之一進行實現(xiàn)，掌握如下內(nèi)容：＞深度了解內(nèi)存分配和釋放的原理＞熟練掌握棧和遞歸的進一步應用＞學習矩陣的相關(guān)算法在BMP圖像中的應用＞深入掌握二叉樹在哈夫曼編碼中的算法實現(xiàn)＞了解圖的相關(guān)算法的應用A進一步提高編程能力4.1題目1——動態(tài)內(nèi)存管理動態(tài)內(nèi)存管理是操作系統(tǒng)的基本功能之一，用于響應用戶程序?qū)?nèi)存的申請和釋放請求。初始化時，系統(tǒng)只有一塊連續(xù)的空閑內(nèi)存；然后，當不斷有用戶申請內(nèi)存時，系統(tǒng)會根據(jù)某種策略選擇一塊合適的連續(xù)內(nèi)存供用戶程序使用；當用戶程序釋放內(nèi)存時，系統(tǒng)將其回收，供以后重新分配，釋放時需要計算該內(nèi)存塊的左右是否也為空閑塊，若是，則需要合并變成更大的空閑塊。試設(shè)計用于模擬動態(tài)內(nèi)存管理的內(nèi)存池類?；疽螅?、 實現(xiàn)內(nèi)存池MemoryPool(intsize)的初始化2、 實現(xiàn)Allocatedntsize)接口3、 實現(xiàn)Free(void*p)接口4、 實現(xiàn)內(nèi)存池的析構(gòu)5、 在分配內(nèi)存空間時，可選擇不同的內(nèi)存分配策略：最佳擬合策略、最差擬合策略或最先擬合策略。實現(xiàn)其中至少兩種分配策略。編寫測試main()函數(shù)對類中各個接口和各種分配策略進行測試，并實時顯示內(nèi)存池中的占用塊和空閑塊的變化情況。4.2題目2——表達式求值表達式求值是程序設(shè)計語言編譯中最近本的問題，它要求把一個表達式翻譯成能夠直接求值的序列。例如用戶輸入字符串“14+((13-2)*2-11*5)*2”，程序可以自動計算得到最終的結(jié)果。在這里，我們將問題簡化，假定算數(shù)表達式的值均為非負整數(shù)常數(shù)，不包含變量、小數(shù)和字符常量。試設(shè)計一個算術(shù)四則運算表達式求值的簡單計算器?；疽螅?、 操作數(shù)均為非負整數(shù)常數(shù)，操作符僅為+、-、*、/、(和)；2、 編寫main函數(shù)進行測試。4.3題目3——bmp圖像處理實現(xiàn)一個識別BMP文件的圖像類，能夠進行以下圖像處理?；疽螅?、能夠?qū)?4位真彩色Bmp文件讀入內(nèi)存；2、 能夠?qū)?4位真彩色Bmp文件重新寫入文件；3、 能夠?qū)?4位真彩色Bmp文件進行24位灰度處理；4、 能夠?qū)?4位灰度Bmp文件進行8位灰度處理；5、 能夠?qū)?位灰度Bmp文件轉(zhuǎn)化成黑白圖像；6、 能夠?qū)D像進行平滑處理；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、 平滑處理采用鄰域平均法進行，分成4鄰域和8鄰域平滑，基本原理就是將每一個像素點的值設(shè)置為其周圍各點像素值得平均值。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)整對比度的時候容易發(fā)生越界，需要進行邊界處理6、24位真彩色轉(zhuǎn)256色，需要手動添加顏色表在BMP頭結(jié)構(gòu)中，可以使用位截斷法、流行色算法、中位切分算法、八叉樹算法等方法實現(xiàn)。4.4題目4——哈夫曼樹利用二叉樹結(jié)構(gòu)實現(xiàn)哈夫曼編/解碼器。基本要求：1、 初始化(Init)：能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立赫夫曼樹2、 建立編碼表(CreateTable):利用已經(jīng)建好的赫夫曼樹進行編碼，并將每個字符的編碼輸出。3、 編碼(Encoding)：根據(jù)編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。4、 譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結(jié)果。5、 打印(Print)：以直觀的方式打印赫夫曼樹(選作)6、 計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論赫夫曼編碼的壓縮效果。測試數(shù)據(jù)：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、 用戶界面可以設(shè)計為“菜單”方式：能夠進行交互。2、 根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度，對沒有出現(xiàn)的字符一律不用編碼。4.5題目5——運動會比賽問題問題：設(shè)某個田徑運動會共有七個項目的比賽，分別為100米、200米、跳高、跳遠、鉛球、鐵餅和標槍。每個選手最多參加3個項目，現(xiàn)有六名選手參賽，他們選擇的項目如表1-1所示。考慮到每個選手的參加的各個項目不能同時進行，則如何設(shè)計合理的