【文章內(nèi)容簡介】 實(shí)驗(yàn)7 排序一、實(shí)驗(yàn)?zāi)康暮鸵螅?）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。（2）掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點(diǎn)。二、實(shí)驗(yàn)儀器和設(shè)備turbo c ++三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖）必做題用隨機(jī)數(shù)產(chǎn)生100000個(gè)待排序數(shù)據(jù)元素的關(guān)鍵字值。測試下列各排序函數(shù)的機(jī)器實(shí)際執(zhí)行時(shí)間（至少測試兩個(gè)）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、堆排序。選做題假設(shè)含n個(gè)記錄的序列中，其所有關(guān)鍵字為值介于v和w之間的整數(shù)，且其中很多關(guān)鍵字的值是相同的。則可按如下方法排序：另設(shè)數(shù)組number[v…w]，令number[i]統(tǒng)計(jì)關(guān)鍵字為整數(shù)i的紀(jì)錄個(gè)數(shù)，然后按number重排序列以達(dá)到有序。試編寫算法實(shí)現(xiàn)上述排序方法，并討論此種方法的優(yōu)缺點(diǎn)。程序清單：金陵科技學(xué)院實(shí)驗(yàn)報(bào)告四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）金陵科技學(xué)院實(shí)驗(yàn)報(bào)告五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會）金陵科技學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目名稱： 查找 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間：金陵科技學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)8 查找一、實(shí)驗(yàn)?zāi)康暮鸵螅?）掌握順序表查找、有序表查找、索引順序表查找的各種算法。（2）掌握哈希表設(shè)計(jì)。二、實(shí)驗(yàn)儀器和設(shè)備turbo c ++三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖）必做題（1）在一個(gè)遞增有序的線性表中利用二分查找法查找數(shù)據(jù)元素x。選做題（2）構(gòu)造一個(gè)哈希表，哈希函數(shù)采用除留余數(shù)法，哈希沖突解決方法采用鏈地址法。設(shè)計(jì)一個(gè)測試程序進(jìn)行測試。提示：構(gòu)造哈希表只是完成查找的第一步，大家應(yīng)該掌握在哈希表上進(jìn)行查找的過程，可以試著編程序?qū)崿F(xiàn)。程序清單：金陵科技學(xué)院實(shí)驗(yàn)報(bào)告四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會）算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)總結(jié)篇三北 京 郵 電 大 學(xué)計(jì) 算 機(jī) 科 學(xué) 與 技 術(shù) 學(xué) 院算 法 與 數(shù) 據(jù) 結(jié) 構(gòu)實(shí) 驗(yàn) 指 導(dǎo) 書楊俊、徐塞虹、漆濤 編著2006年9月 算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)指導(dǎo)書目錄實(shí)驗(yàn)要求....................................................................................................................................3 試驗(yàn)一、約瑟夫環(huán)..............................................................................…………………..……4 試驗(yàn)二、長整數(shù)四則運(yùn)算運(yùn)算………………………………………………………………4 實(shí)驗(yàn)三、八皇后.....................................……..........................................................................5 實(shí)驗(yàn)四、騎士遍歷......................................……………………..............................................5 實(shí)驗(yàn)五、桌面計(jì)算器...............................……………..............................................................6 實(shí)驗(yàn)六、平衡排序二叉樹....................…...…….....................................................................6 試驗(yàn)七、多重集合的實(shí)現(xiàn)……......................................………………………………………7 試驗(yàn)八、圖論………………………………………………………………………….……..8 實(shí)驗(yàn)八、內(nèi)部排序性能的比較..........………………….............................................................8 教材及主要參考文獻(xiàn)………………………………………………………………………………..9 2 北京郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)要求一、本課程在講課期間需要做上機(jī)實(shí)驗(yàn)，目的之一是檢查學(xué)生對所學(xué)算法的掌握和理解程度；其次是鍛煉學(xué)生的團(tuán)隊(duì)合作精神。二、成績：編碼：占整個(gè)實(shí)驗(yàn)成績的50%；測試：占整個(gè)實(shí)驗(yàn)成績的20%；文檔：占整個(gè)實(shí)驗(yàn)成績的30%。三、按時(shí)提交上機(jī)文檔，實(shí)驗(yàn)文檔包含以下各項(xiàng)：問題描述：實(shí)驗(yàn)題目、內(nèi)容和要求；算法思路：實(shí)驗(yàn)小組對問題的解決方法的文字描述；算法描述：用類算法語言等對算法進(jìn)行描述；源程序及驅(qū)動程序：上機(jī)實(shí)驗(yàn)編制的代碼源程序及程序運(yùn)行環(huán)境；測試數(shù)據(jù)：對算法的測試用例；結(jié)果分析和結(jié)論：對算法及測試結(jié)果的分析及結(jié)論；心得體會：通過實(shí)驗(yàn)獲得的心得體會；分工及簽名：最后是小組成員的分工及簽名。北京郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)一、約瑟夫環(huán)一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：約瑟夫環(huán)問題是：n個(gè)人p0,p1,…pn 圍坐成一個(gè)圓環(huán)。每個(gè)人pk持有一個(gè)秘密的數(shù)字ck。0 ck = m。開始時(shí)隨機(jī)選取一個(gè)數(shù) c = c0。每個(gè)人從p0 開始從1開始報(bào)數(shù)。報(bào)到數(shù)c 的人出對。然后以出隊(duì)的人的秘密數(shù)字作為新的c 值。從出隊(duì)者的下一個(gè)人順時(shí)針從1 開始再報(bào)數(shù)。直到所有的人全部出隊(duì)。三、實(shí)驗(yàn)?zāi)康模簷z查學(xué)生對各種線性表的實(shí)現(xiàn)的掌握程度。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：1人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：各種隊(duì)列的實(shí)現(xiàn)。八、實(shí)驗(yàn)內(nèi)容和要求：至少用3種以上的線性表來完成此試驗(yàn)?？梢栽趲ь^節(jié)點(diǎn)的和不帶頭節(jié)點(diǎn)的線性表、循環(huán)的和非循環(huán)線性表、動態(tài)鏈表和靜態(tài)鏈表以及向量（數(shù)組）之間選擇三種。從空表開始，為每個(gè)人生成一個(gè)隨機(jī)數(shù)。然后將此人加入到線性表之中。九、可研究與探索的問題：給出各種實(shí)現(xiàn)的優(yōu)缺點(diǎn)比較。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。給出各種線性表實(shí)現(xiàn)的優(yōu)缺點(diǎn)分析。實(shí)驗(yàn)二、長整數(shù)四則運(yùn)算一、實(shí)驗(yàn)類別：驗(yàn)證實(shí)驗(yàn)。二、問題描述：計(jì)算機(jī)cpu本身可以做32位或者64位的整數(shù)四則運(yùn)算。本試驗(yàn)要求對任意大小的整數(shù)實(shí)現(xiàn)其四則運(yùn)算。將一個(gè)整數(shù)n表示為n = 177。(d0 + d1*b + d2*b2 + ….+ bk*bk)其中 1 b = 256 為一個(gè)取定的整數(shù)。0 = dk b。用線性表存儲{bk}。給出整數(shù)的四則運(yùn)算程序。三、實(shí)驗(yàn)?zāi)康模簩唧w的問題選擇適當(dāng)?shù)木€性表實(shí)現(xiàn)。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：各種隊(duì)列的實(shí)現(xiàn)。八、實(shí)驗(yàn)內(nèi)容和要求：至少用2種以上的線性表來完成此試驗(yàn)。比較不同線性表實(shí)現(xiàn)的速度。九、可研究與探索的問題：1）對具體問題選擇合適的線性表實(shí)現(xiàn)。2）b 的選取問題。可 否選擇更大的基b。b的選擇所應(yīng)考慮的因素。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。能夠得出用向量（數(shù)組）實(shí)現(xiàn)的線性表速度最快。實(shí)驗(yàn)三、八皇后問題一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：在n*n 的國際象棋棋盤上放置n個(gè)皇后，使每個(gè)皇后不受其他皇后的攻擊。三、實(shí)驗(yàn)?zāi)康模簷z查學(xué)生對堆棧和遞歸程序掌握程度。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：1人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：遞歸程序與堆棧八、實(shí)驗(yàn)內(nèi)容和要求： 分別用遞歸和堆棧完成此試驗(yàn)。統(tǒng)計(jì)程序運(yùn)行時(shí)間與問題規(guī)模n 的關(guān)系。九、可研究與探索的問題：問題的復(fù)雜度。當(dāng)n 比較大時(shí)，討論提高程序運(yùn)行的方法。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。找出程序運(yùn)行速度的瓶頸。實(shí)驗(yàn)四、騎士遍歷一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：在國際象棋n*n的棋盤中，一匹馬從棋盤中任意一格出發(fā)，要求用n21步走完所有的n2個(gè)格子。每個(gè)格子走且只走過一次。應(yīng)如何走？ 試給出算法實(shí)現(xiàn)。三、實(shí)驗(yàn)?zāi)康模簷z查學(xué)生對堆棧與回溯算法的掌握。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：堆棧與回溯八、實(shí)驗(yàn)內(nèi)容和要求：用堆棧完成此試驗(yàn)。統(tǒng)計(jì)程序運(yùn)行時(shí)間與問題規(guī)模n 的關(guān)系。九、可研究與探索的問題：怎樣枚舉所有馬下一步可走的位置。選擇下一步所走位置的策略。注意由于這個(gè)程序非常耗時(shí)，在初期程序調(diào)試時(shí)應(yīng)取較小的n。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。找出程序運(yùn)行速度的瓶頸。給出不同選擇策略的程序運(yùn)行 速度的比較結(jié)果。實(shí)驗(yàn)五、桌面計(jì)算器（表達(dá)式求值）一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：模仿unix系統(tǒng)下的dc命令。輸入表達(dá)式字符串，按回車鍵后給出表達(dá)式的值。操作數(shù)為實(shí)數(shù)。1）操作符有 “+”、“”、“*”、“/”、“^”（乘方）2）還可以有臨時(shí)變量。用法如 pi = ，r = 3, r*pi^2 3）還可以有事先定義的函數(shù)如：“sin()”（正弦）、“cos()”（余弦）、“l(fā)og()”（對數(shù)）、“l(fā)n()”（自然對數(shù)）等函數(shù)。三、實(shí)驗(yàn)?zāi)康模簷z查學(xué)生用堆棧解決實(shí)際問題。為本課程后續(xù)的內(nèi)容提供伏筆。也為后繼的課程如編譯原理預(yù)習(xí)。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：堆棧，線性表，命令行參數(shù)的處理。八、實(shí)驗(yàn)內(nèi)容和要求：學(xué)生應(yīng)至少應(yīng)實(shí)現(xiàn)處理五個(gè)運(yùn)算符：“+”、“”、“*”、“/”、“^”（乘方）?？梢杂靡粋€(gè)線性表來存儲臨時(shí)變量。另一個(gè)線性表來存儲預(yù)定義的函數(shù)名。九、可研究與探索的問題：查找臨時(shí)變量名的不同方法。如哈希表，二叉樹。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。實(shí)驗(yàn)六、平衡排序二叉樹一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：隨機(jī)生成一組整數(shù)p0,p1,…pn－１。將這組整數(shù)按生成的次序插入到一個(gè)平衡排序二叉樹中。然后將p0,p1,…pn－１隨機(jī)重新排列為q0,q1,…qn－１。再按照次次序?qū)⑦@些整數(shù)從生成的平衡排序二叉樹刪除。三、實(shí)驗(yàn)?zāi)康模浩胶馀判蚨鏄涞牟迦牒蛣h除。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：平衡排序二叉樹的插入和刪除中的旋轉(zhuǎn)。八、實(shí)驗(yàn)內(nèi)容和要求：統(tǒng)計(jì)在平衡排序二叉樹的插入和刪除過程中各種旋轉(zhuǎn)的出現(xiàn)次數(shù)。九、可研究與探索的問題：研究平衡排序二叉樹與一般的排序二叉樹在插入和刪除方面的性能比較。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。給出在均勻的隨機(jī)分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。實(shí)驗(yàn)七、多重集合的實(shí)現(xiàn)一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：實(shí)現(xiàn)數(shù)學(xué)上多重集合。所謂的多重集合類似于集合，但是一件東西可以放置多個(gè)副本。就如一個(gè)菜籃子里面可以放兩個(gè)蘋果。三、實(shí)驗(yàn)?zāi)康模翰檎医Y(jié)構(gòu)的各種實(shí)現(xiàn)。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：平衡排序二叉樹的插入和刪除、遍歷，查找。哈希查找結(jié)構(gòu)。八、實(shí)驗(yàn)內(nèi)容和要求： 假設(shè)集合中包含的元素是可以排序的。將多重集合封裝成一個(gè)類。具體的實(shí)現(xiàn)可以是中序線索化的平衡排序二叉樹，或者帶父節(jié)點(diǎn)指針的平衡排序二叉樹。多重集合的界面如下：template//假設(shè)類型 t 是可以排序的 class multi_set{multi_set(void)。//構(gòu)造函數(shù)，初始化為空集合~multi_set(void)。//析構(gòu)函數(shù)multi_setamp。 operator=(multi_set const a)。//重載運(yùn)算符=bool contains(t constamp。 v)const。//如果集合包含v 則返回true，否則返回falsemulti_setamp。 operator+=(multi_set constamp。a)。//將集合a 并到自身中。multi_setamp。 operator=(multi_set constamp。 a)。//自身減去集合amulti_setamp。 operator=(t constamp。 a)。//自身減去一個(gè)元素a}。//~class multi_set//返回集合a,b的并templatemulti_setmult_set:: operator+(multi_setconstamp。 a，multi_setconstamp。 b)。//返回集合a,b的差templatemulti_setmult_set:: operator(multi_setconstamp。 a，multi_setconstamp。 b)。//返回 a –{v}templatemulti_setmulti_set::operator(multi_set constamp。 a,t constamp。 v)。九