數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-資料下載頁(yè)
2025-01-18 22:34本頁(yè)面
【正文】 ndl （升序） endl （升序） endl （升序） endl （升序） endl （升序） endl endl endl。 coutendl 請(qǐng)選擇功能（輸入對(duì)應(yīng)功能的序號(hào)）：。 cinopt1。 } cout endl。 }}。endif // CONTROL_H_INCLUDED//includeincludeincludeiostreamusing namespace std。12.//主函數(shù)int main(){ Control a。 //控制類(lèi)Control類(lèi)對(duì)象 ()。 //控制函數(shù) return 0。}測(cè)試方法：使用排序程序前，先使用數(shù)據(jù)產(chǎn)生程序generator產(chǎn)生所需數(shù)據(jù)（整型，1000個(gè)記錄），包括3組無(wú)序數(shù)據(jù)（用rand（）與srand（）函數(shù)產(chǎn)生），一組完全正序數(shù)據(jù)和一組完全逆序數(shù)據(jù)，并分別存儲(chǔ)于5個(gè)不同的文本文件中。在排序程序中依次讀取5個(gè)數(shù)據(jù)文件并按照程序的提示對(duì)數(shù)據(jù)進(jìn)行排序，觀測(cè)輸出的排序序列并對(duì)關(guān)鍵詞比較次數(shù)和關(guān)鍵詞移動(dòng)次數(shù)進(jìn)行分析。測(cè)試數(shù)據(jù)：由數(shù)據(jù)產(chǎn)生程序generator產(chǎn)生，存儲(chǔ)于文件由數(shù)據(jù)產(chǎn)生程序generator產(chǎn)生，,(前三個(gè)為無(wú)序記錄文件，第四個(gè)為完全正序文件，第五個(gè)為完全逆序文件)中，記錄為整型數(shù)據(jù)， 規(guī)模為1000數(shù)量級(jí)。測(cè)試結(jié)果：起泡排序數(shù)據(jù)組別比較次數(shù)/次移動(dòng)次數(shù)/次排序時(shí)間/ms理論值（最好，最壞，平均）O（n），O(n2)，O(n2)0，O(n2)，O(n2)a49729676015212b49713975650716c49559674349912d99901e499500149850014直接插入排序數(shù)據(jù)組別比較次數(shù)/次移動(dòng)次數(shù)/次排序時(shí)間/ms理論值（最好，最壞，平均）O（n），O(n2)，O(n2)O（n），O(n2)，O(n2)a2543832553825b2531682541676c2488322498315d99919981e50049950149811簡(jiǎn)單選擇排序數(shù)據(jù)組別比較次數(shù)/次移動(dòng)次數(shù)/次排序時(shí)間/ms理論值（最好，最壞，平均）O(n2)，O(n2)，O(n2)0，O(n)，O(n)a49950029856b49950029766c49950029736d49950007e49950015009快速排序數(shù)據(jù)組別比較次數(shù)/次移動(dòng)次數(shù)/次排序時(shí)間/ms理論值（最好，最壞，平均）O(nlog2n)，O(nlog2n)，O(nlog2n)0，O(nlog2n)，O(nlog2n)a834182953b663983764c759382232d49950005e49950015006Shell排序數(shù)據(jù)組別比較次數(shù)/次移動(dòng)次數(shù)/次排序時(shí)間/ms理論值（最好，最壞，平均）O(n（log2n）2)O(n（log2n）2)a714181142199923b714136142195422c714210142202821d707818141563622e710908141872621堆排序數(shù)據(jù)組別比較次數(shù)/次移動(dòng)次數(shù)/次排序時(shí)間/ms理論值（最好，最壞，平均）O(nlog2n)O(nlog2n)a16892272611b16834271951c16836271591d17626291241e15982249481程序的使用說(shuō)明：運(yùn)行程序，輸入數(shù)據(jù)文件名（, ，，均存放在當(dāng)前目錄下），之后請(qǐng)用戶(hù)按照個(gè)人需求及程序界面提示選擇相應(yīng)排序功能，完成排序，并查看關(guān)鍵詞的比較次數(shù)，交換次數(shù)和排序時(shí)間！每次運(yùn)行只能讀取一個(gè)文件，可多次進(jìn)行排序。需要多次執(zhí)行程序以完成對(duì)5組記錄的排序與各項(xiàng)指標(biāo)的統(tǒng)計(jì)?？偨Y(jié)：（對(duì)程序進(jìn)行分析、評(píng)價(jià)運(yùn)行效果，總結(jié)遇到的問(wèn)題及解決辦法）總體評(píng)價(jià)：課程設(shè)計(jì)題目一難度較低，要求同學(xué)熟練掌握最基本的數(shù)據(jù)結(jié)構(gòu)知識(shí)和各種內(nèi)排序算法。整個(gè)完成過(guò)程基本順利，沒(méi)有遇到太大的問(wèn)題。運(yùn)行效果：程序的整體運(yùn)行基本穩(wěn)定、流暢，每次運(yùn)行都能得到測(cè)試結(jié)果。程序分析：本程序的核心是6個(gè)排序算法的編寫(xiě)，也是該課程設(shè)計(jì)的難點(diǎn)，靈活運(yùn)用數(shù)組及函數(shù)的調(diào)用關(guān)系顯得尤為重要。根據(jù)程序的運(yùn)行結(jié)果，除了shell排序外，其他排序算法的時(shí)間復(fù)雜度均完全符合理論值，快速排序在執(zhí)行效率上表現(xiàn)的最為高效。通過(guò)分析，可以發(fā)現(xiàn)該程序的運(yùn)行結(jié)果清晰直觀，除希爾排序外，其他排序的結(jié)果均與理論值完全吻合，也即結(jié)果正確。數(shù)據(jù)分析及結(jié)論：1. 起泡排序，直接插入排序，簡(jiǎn)單選擇排序三種O(n2)的算法率最低。希爾排序，快速排序，堆排序三種O(n（log2n）2)的算法效率高些2. 直接插入排序和冒泡排序在正序數(shù)據(jù)的情況下排序速度遠(yuǎn)遠(yuǎn)快于逆序數(shù)據(jù)的情況3. 快速排序在效率上的優(yōu)勢(shì)尤為明顯，堆排序和shell排序介于二者之間。4. 選擇排序的排序速度與所選取的數(shù)據(jù)的順序沒(méi)有關(guān)系，只要數(shù)據(jù)規(guī)模相同，記錄的比較次數(shù)和記錄的移動(dòng)次數(shù)均一致；5. 堆排序在平均情況下具有最穩(wěn)定的排序速度，在正序、逆序、亂序的情況下記錄的比較次數(shù)和記錄的移動(dòng)次數(shù)差別不大，所以在這6種算法中，對(duì)排序是受記錄的原始序影響最小的算法。 遇到的問(wèn)題：1. 文件讀取出現(xiàn)問(wèn)題，無(wú)法讀出數(shù)字。2. 每次產(chǎn)生偽隨機(jī)數(shù)都為相同的值。3. switch語(yǔ)句中無(wú)法定義對(duì)象。4. 涉及函數(shù)調(diào)用的排序算法無(wú)法用兩個(gè)整型變量記錄關(guān)鍵詞的 比較次數(shù)和移動(dòng)次數(shù)。 解決辦法：1. 借助istringstream類(lèi)讀出數(shù)字，具體實(shí)現(xiàn)請(qǐng)看源代碼。2. 了解了計(jì)算機(jī)產(chǎn)生隨機(jī)數(shù)原理，通過(guò)srand()函數(shù)改變r(jià)and()函數(shù)的初始值，得以產(chǎn)生不同的隨機(jī)數(shù)。3. 在switch復(fù)合結(jié)構(gòu)外定義并初始化。4. 使用整形數(shù)組進(jìn)行址傳遞，在不返回值的情況下即完成了對(duì)兩項(xiàng)指標(biāo)的記錄。個(gè)人感悟級(jí)總結(jié)：本次課程設(shè)計(jì)檢測(cè)了上學(xué)期學(xué)的相關(guān)知識(shí)，在這個(gè)過(guò)程中自己也發(fā)現(xiàn)了很多之前未出現(xiàn)過(guò)的問(wèn)題，在老師和同學(xué)的幫助下一一得以解決，對(duì)自己的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)和編程技巧有很大的提高。感謝老師和同學(xué)們?cè)谡麄€(gè)過(guò)程中的幫助，本題目已經(jīng)完成。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1