數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 多關(guān)鍵字排序 高考排序

1、淮 海 工 學(xué) 院 計(jì)算機(jī)工程學(xué)院課程設(shè)計(jì)報(bào)告姓 學(xué) 系 成績(jī)：簽名：年月日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 1 頁(yè)，共頁(yè)題目：0至 5 。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 2 頁(yè)，共頁(yè)3課程設(shè)計(jì)說(shuō)明書(shū)、 、121、4、5、 6、系統(tǒng)用到的抽象數(shù)據(jù)類(lèi)型定義/按第一個(gè)關(guān)鍵字代表的學(xué)科成績(jī)用冒泡法排序執(zhí)行的時(shí)間/冒泡法排序的總時(shí)間/按第一個(gè)關(guān)鍵字代表的學(xué)科成績(jī)用分配和收集的方法執(zhí)行的時(shí)間DCTime2,DCTime3,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 3 頁(yè)，共/分配和收集法排序的總時(shí)間頁(yè)DCTime4,DCTimeSum;int score100005, /隨機(jī)創(chuàng)建的模擬學(xué)生記錄源數(shù)組bubble100005, /進(jìn)行數(shù)組中

2、的記錄發(fā)生交換copy100005;struct LSD d301;/從模擬的學(xué)生記錄源 txt 文件中讀取學(xué)生記錄到該數(shù)組/分配數(shù)組，該處考慮到把總分（ 0-300）也列入優(yōu)先級(jí)序7、系統(tǒng)中的各個(gè)函數(shù)模塊1： c ） / /、242和3數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 4 頁(yè)，共頁(yè)MAIN：該數(shù)據(jù)類(lèi)型是在分配和收集的時(shí)候存放分配成績(jī)數(shù)組1抽象數(shù)據(jù)類(lèi)型struct LSD2CreatScore(int scoreRecordNumberKeyNumber)函數(shù)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 5 頁(yè)，共頁(yè) 3收集函數(shù)Collect(struct LSD dQueueNumber,int *cRecordNumbe

3、r)c* dc當(dāng)前位置有學(xué)生的成績(jī)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 6 頁(yè)，共頁(yè)YNp4初始化分配數(shù)組InitDivide(struct LSD dQueueNumber)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 7 頁(yè)，共頁(yè)d 5分配和收集方法排序double DCSort(struct LSD dQueueNumber,int*cRecordNumber,int n)cnn dQueueNumber d c中6冒泡法排序double BubbleSort(int bubbleRecordNumberQueueNumber)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 8 頁(yè)，共頁(yè) 7Print()函數(shù)8savesources(int sc

4、oreRecordNumberKeyNumber,intn)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 9 頁(yè)，共頁(yè)只寫(xiě)10 load(int scoreRecordNumberKeyNumber)這是一種“低位優(yōu)先”的排序方法，借助一趟基數(shù)排序的方法，先按最低位的值對(duì)記錄進(jìn)行初步排序，在此基礎(chǔ)上再按次低位的值進(jìn)行進(jìn)一步排序。以此類(lèi)推，有低位到高位，每一趟都是在前一趟的基礎(chǔ)上，根據(jù)關(guān)鍵字的某一位對(duì)所有的記錄進(jìn)行排序，直至最高位，這樣就完成了基數(shù)排序的全過(guò)程。從算法中可以看出，對(duì)于 n 個(gè)記錄(每個(gè)記錄含 d 個(gè)子關(guān)鍵字，每個(gè)子關(guān)鍵字的取值范圍為RADIX個(gè)值)進(jìn)行鏈?zhǔn)脚判虻臅r(shí)間復(fù)雜度為O(d(n+RADIX),其

5、中每一趟分配算法的時(shí)間復(fù)雜度為 O(n)，每一趟收集的算法的時(shí)間復(fù)雜度為O(RADIX)，整個(gè)排序進(jìn)行d 趟分配和收集，所需輔助空間為 2*RADIX 個(gè)隊(duì)列指針。由于需要鏈表作為存儲(chǔ)結(jié)構(gòu)，則相對(duì)于其他以順序結(jié)構(gòu)存儲(chǔ)記錄的排序方法而言，還增加了 n 個(gè)指針域的空間。該排序是比較簡(jiǎn)單的交換類(lèi)排序方法，通過(guò)相鄰數(shù)據(jù)元素的交換，逐步將帶排序列變成有序序列的過(guò)程。最壞情況下，待排序的記錄按關(guān)鍵字的逆序進(jìn)行排列，此時(shí)，每一趟冒泡排序需要進(jìn)行i n-1 N=i=n(n-1)/2,n=1， 3n(n-1)/2 次，因此該算法的時(shí)間復(fù)雜度為O(n*n)，空間復(fù)雜度為 O(1)。另外，冒泡排序法是一種穩(wěn)定的每部

6、排序法。五 附錄（源程序清單） /上 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 13 頁(yè)，共頁(yè) 數(shù) 中/數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 14 頁(yè)，共頁(yè) / n中 /數(shù) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 15 頁(yè)，共頁(yè) /只寫(xiě)格 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 16 頁(yè)，共頁(yè)排序系統(tǒng)開(kāi)始運(yùn)行 cd cnn *c10000 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 17 頁(yè)，共頁(yè)d c中= 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告第 18 頁(yè)，共頁(yè) 只寫(xiě)格進(jìn)入程序后的界面如下：這次課程設(shè)計(jì)收獲很大，從一開(kāi)始的迷迷糊糊不明白題意，到現(xiàn)在很清楚該設(shè)計(jì)的各個(gè)方面，我在無(wú)數(shù)次的調(diào)試過(guò)程中學(xué)到了很多有用的東西1、模塊化的思想。使程序模塊化之后，可以很方便的調(diào)用和對(duì)某個(gè)模塊的修改，我由于一

7、開(kāi)始對(duì)題目的要求不到位，在最后驗(yàn)收的時(shí)候發(fā)現(xiàn)一些功能未實(shí)現(xiàn)的問(wèn)題，如果我的程序很亂，函數(shù)之間沒(méi)有清晰的調(diào)用關(guān)系，參數(shù)傳遞混亂的話，我就很難修改它，但是我用了模塊化的思想，在很短的時(shí)間之內(nèi)就將程序添加了文件流操作的功能，使程序更加滿(mǎn)足實(shí)際要求，也更加清晰?，F(xiàn)在可以很容易添加一個(gè)不同的功能模塊。Cpp1.obj:errorLNK2001:unresolvedexternalsymbolvoid_cdeclCreatScore(int(* const)5) (?CreatScoreYAXQAY04HZ)Debug/Cpp1.exe : fatal error LNK1120: 1 unresolve

8、d externals。根據(jù)以前的經(jīng)驗(yàn)知道這是連接上出了錯(cuò)，而且以前遇到類(lèi)似的錯(cuò)誤是因?yàn)閭鬟f的參數(shù)不同而導(dǎo)致的，現(xiàn)在也想到估計(jì)是同樣的問(wèn)題，但是看程序，參數(shù)傳遞正常。后來(lái)在找CreatScore時(shí)發(fā)現(xiàn)我不知道什么時(shí)候把它剪切了，這就好像是聲明了程序要用CreatScore，而且也用了，但是并沒(méi)有說(shuō)明CreatScore是什么，它是怎樣實(shí)現(xiàn)的。3、調(diào)試技巧。調(diào)試的時(shí)候我一般都是用F10和F20進(jìn)行調(diào)試，問(wèn)老師的時(shí)候又學(xué)到了設(shè)置斷點(diǎn)的方法調(diào)試程序，這樣可以通過(guò)猜想，對(duì)某一段代碼進(jìn)行調(diào)試，省去了很多步驟。4、分析問(wèn)題的技巧。這個(gè)和設(shè)置斷點(diǎn)的方法類(lèi)似，例如在判斷打開(kāi)文件是否成功時(shí)，由于有三個(gè)函數(shù)要打開(kāi)

9、和關(guān)閉文件，而且從無(wú)提示都一樣：文件打開(kāi)失敗。這樣在運(yùn)行程序時(shí)，如果文件真的打開(kāi)失敗了，就很難知道哪塊函數(shù)出問(wèn)題了，所以可以設(shè)置不同的提示信息，來(lái)很清楚的追蹤到程序的運(yùn)行，還有就是發(fā)送錯(cuò)誤報(bào)告，這種問(wèn)題出現(xiàn)時(shí)總感覺(jué)序已經(jīng)運(yùn)行到這里了”這樣我們就可以從它是否輸出該提示信息來(lái)了解程序是否正常運(yùn)行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告到某個(gè)位置。第 22 頁(yè)，共頁(yè)5、在修改錯(cuò)誤的時(shí)候也要有至頂向下的修改方法，因?yàn)楹竺娴腻e(cuò)誤很可能就是勤勉的定義錯(cuò)誤，從上到下改，我們可以發(fā)現(xiàn)有時(shí)候錯(cuò)誤從80 多個(gè)一下子就變成兩三個(gè)了，通過(guò)這個(gè)我們也可以看到不同的錯(cuò)誤所影響的范圍，對(duì)我們變成中的側(cè)重點(diǎn)也有幫助6、指針和地址的使用。在進(jìn)行文

10、件操作時(shí)，我有一個(gè)功能就是從文件中讀取學(xué)生記錄到一個(gè)二維數(shù)組中，感覺(jué)寫(xiě)的沒(méi)錯(cuò)，可是輸出來(lái)的結(jié)果總是一個(gè)符合格式要求的地址結(jié)果，經(jīng)過(guò)老師的指導(dǎo)，我知道了在讀取的時(shí)候應(yīng)該把數(shù)據(jù)存放在數(shù)組的地址中，而我卻是按賦值的錯(cuò)誤想法做的。直接自己寫(xiě)了一個(gè)冒泡排序，而且一直深信我的這個(gè)排序是正確的，可是結(jié)果總是出現(xiàn)錯(cuò)誤，排序結(jié)果并不正確，后來(lái)按照書(shū)上的算法做很正確。所以在程序設(shè)計(jì)時(shí)要對(duì)算法絕對(duì)重視，要考慮到很多可能的會(huì)出現(xiàn)的情況，必須詳細(xì)具體。8、參數(shù)的傳遞和程序中的計(jì)算問(wèn)題。開(kāi)始我用101 個(gè)隊(duì)列進(jìn)行分配，但是都出現(xiàn)錯(cuò)誤了，即排出的結(jié)果有個(gè)別變成了地址，而且有向同學(xué)好的考生的信息輸出，調(diào)試了一天多也不知道到底是哪里出錯(cuò)了，后來(lái)發(fā)現(xiàn)錯(cuò)誤很簡(jiǎn)單