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

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計多關(guān)鍵字排序高考排序》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計多關(guān)鍵字排序高考排序（23頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 淮 海 工 學(xué) 院 計算機(jī)工程學(xué)院 課程設(shè)計報告 設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 選題名稱： 多關(guān)鍵字排序 姓 名： 周宣 學(xué) 號： 110821120 專業(yè)班級： 網(wǎng)絡(luò)工程081 系 （院）： 計算機(jī)工程學(xué)院 設(shè)計時間： 2009.12.28~2010.1.12 設(shè)計地點(diǎn)： 軟件工程實(shí)驗(yàn)室、教室

2、 成績： 指導(dǎo)教師評語： 簽名： 年 月 日 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 第 22 頁，共 頁 1．課程設(shè)計目的 1、訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識，編寫程序求解指定問題。 2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能； 3.提高綜合運(yùn)用所學(xué)的理論知識和方法

3、獨(dú)立分析和解決問題的能力； 4.訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生的理論知識，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。 2．課程設(shè)計任務(wù)與要求： 任務(wù) 題目：多關(guān)鍵字的排序 【問題描述】 多關(guān)鍵字的排序有其一定的實(shí)用范圍。例如：在進(jìn)行高考分?jǐn)?shù)處理時，除了需對總分進(jìn)行排序外，不同的專業(yè)對單科分?jǐn)?shù)的要求不同，因此尚需在總分相同的情況下，按用戶提出的單科分?jǐn)?shù)的次序要求排出考生錄取的次序。 【基本要求】 （1）假設(shè)待排序的記錄不超過10000，表中記錄的關(guān)鍵字?jǐn)?shù)不超過5，各個學(xué)科關(guān)鍵字

4、的范圍均為0至100，總分關(guān)鍵字的范圍是0-300。按用戶給定的進(jìn)行排序的關(guān)鍵字的優(yōu)先關(guān)系，輸出排序結(jié)果。 （2）約定按LSD法進(jìn)行多關(guān)鍵字的排序。在對各個關(guān)鍵字進(jìn)行排序時采用兩種策略：其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用“分配”和“收集”的方法。并綜合比較這兩種策略。 【測試數(shù)據(jù)】 由隨機(jī)數(shù)產(chǎn)生器生成。 【實(shí)現(xiàn)提示】 由于是按LSD方法進(jìn)行排序，則對每個關(guān)鍵字均可進(jìn)行整個序列的排序，但在利用通常的內(nèi)部排序方法進(jìn)行排序時，必須選用穩(wěn)定的排序方法 要求： 1、在處理每個題目時，要求從分析題目的需求

5、入手，按設(shè)計抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的分析報告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī)調(diào)試工作的效率。在程序設(shè)計階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。 2、.設(shè)計的題目要求達(dá)到一定工作量（300行以上代碼），并具有一定的深度和難度。 3、程序設(shè)計語言推薦使用C/C++，程序書寫規(guī)范，源程序需加必要的注釋; 4、每位同學(xué)需提交可獨(dú)立運(yùn)行的程序； 5 、每位同學(xué)需獨(dú)立提交設(shè)計報告書（每人一份），要求編排格式統(tǒng)一、規(guī)范、內(nèi)容充實(shí)，不少于10頁（代碼不算）； 6、課程設(shè)計實(shí)踐作為培養(yǎng)學(xué)生動手能力的一種

6、手段，單獨(dú)考核。 3．課程設(shè)計說明書 一 需求分析 1）選題功能分析 【題目的意義】 1、 對高考分?jǐn)?shù)按照總分和不同學(xué)科的分?jǐn)?shù)按照優(yōu)先級順序排出考生錄取的次序，以滿足不同專業(yè)對單科分?jǐn)?shù)的要求。 2、 對不同排序策略進(jìn)行綜合比較。 【實(shí)現(xiàn)的功能】 1、 用C語言設(shè)計實(shí)現(xiàn)一個高考成績排序系統(tǒng)。 2、 創(chuàng)建模擬的高考考生成績表，存放到txt文檔中?？忌继枮?，2，3…用偽隨機(jī)數(shù)生成器生成各考號學(xué)生的各個學(xué)科成績，并計算總分成績。 3、 由于實(shí)際中高考考生成績表是已知的（模擬創(chuàng)建的txt文檔），程序能從文件中讀取數(shù)據(jù)。從創(chuàng)建的考生成績表中讀取數(shù)據(jù)，并對數(shù)據(jù)處理 4、 按照

7、學(xué)科的優(yōu)先級順序，對學(xué)生的成績排序。既可以以某一學(xué)科的單科成績優(yōu)先級最高排序，也可以先按總分優(yōu)先級最高來排序。 5、 在對各個關(guān)鍵字即單科成績進(jìn)行排序的時候，分別用穩(wěn)定的內(nèi)部排序法（冒泡法）以及“‘分配’和‘搜集’”的方法進(jìn)行排序。 6、 能夠?qū)γ芭莘ㄅ判虿呗院汀啊峙洹汀鸭狈椒ㄅ判虿呗赃M(jìn)行的執(zhí)行時間進(jìn)行比較。 7、 輸入數(shù)據(jù)：1各科英文首字母的代號，字符型，如smce 2整型數(shù)，0-10000 1輸出程序用兩種方法進(jìn)行排序的進(jìn)程和執(zhí)行時間 2輸出前n名學(xué)生的信息 二 概要設(shè)計 1、 偽隨機(jī)生成的數(shù)據(jù)包含語文、

8、數(shù)學(xué)、英語三科成績?？偝煽?yōu)檎Z文、數(shù)學(xué)、英語三科成績的和。學(xué)號按成績數(shù)組的下標(biāo)賦值，生成學(xué)生成績記錄，將該記錄保存到txt文檔中 2、 從上面的txt文檔中讀取數(shù)據(jù)到一個二維數(shù)組中，以便對學(xué)生信息進(jìn)行處理 3、 給出排序的優(yōu)先關(guān)系，根據(jù)優(yōu)先關(guān)系由低位向高位逐個關(guān)鍵字進(jìn)行排序。 4、 對單科成績進(jìn)行排序的時候，單科成績雖然是0-100，但總成績是0-300，所以要建301個隊(duì)列進(jìn)行排序，先按“分配”和“搜集”的方法進(jìn)行一趟“基數(shù)排序”；然后再按照穩(wěn)定的內(nèi)部排序法（冒泡法）進(jìn)行排序。將搜集好的或排序好的序列存儲，以進(jìn)行對次優(yōu)先級的關(guān)鍵字進(jìn)行再排序。 5、 將排序好的學(xué)生成績按照用戶提出的提

9、取人數(shù)的要求，保存到另一個txt文檔中，并輸出到屏幕 6、 系統(tǒng)用到的抽象數(shù)據(jù)類型定義 double BubTime1, //按第一個關(guān)鍵字代表的學(xué)科成績用冒泡法排序執(zhí)行的時間 BubTime2, BubTime3, BubTime4, BubTimeSum, //冒泡法排序的總時間 DCTime1, //按第一個關(guān)鍵字代表的學(xué)科成績用分配和收集的方法執(zhí)行的時間 DCTime2, DCTime3, DCTime4, DCTimeSum; //分配和收集法排序的總時間 int score[10000][5], //隨

10、機(jī)創(chuàng)建的模擬學(xué)生記錄源數(shù)組 bubble[10000][5], //進(jìn)行冒泡法排序時用來存放學(xué)生記錄源數(shù)組，并且隨排序進(jìn)行數(shù)組中的記錄發(fā)生交換 copy[10000][5]; //從模擬的學(xué)生記錄源txt文件中讀取學(xué)生記錄到該數(shù)組 struct LSD d[301]; //分配數(shù)組，該處考慮到把總分（0-300）也列入優(yōu)先級序列中，因此建立了301個隊(duì)列 int *c[10000]; //用來存放收集到的學(xué)生記錄 char x[5]; //存放有優(yōu)先關(guān)系的學(xué)科代號序列 7、 系統(tǒng)中的各個函數(shù)模塊 1：void CreatScore

11、(int score[10000][5]); //隨機(jī)創(chuàng)建學(xué)生記錄表score。正常高考中該表是已知的，不必創(chuàng)建 2：void Collect(struct LSD d[301],int *c[10000]); //LSD法排序中的收集函數(shù)，即將分配好的記錄收集到c指針數(shù)組保存 3：void InitDivide(struct LSD d[301]); //用于初始化臨時分配數(shù)組，在每一次收集后必須做的工作 4：double DCSort(struct LSD d[301],int *c[10000],int n); //分配（Divide）和收集（Collect）排序

12、的方法 5：double BubbleSort(int score[10000][5],int n); //冒泡法排序 6：void Print(); //將排序結(jié)果文件中的記錄數(shù)據(jù)輸出到屏幕上 7：void savesources(int score[10000][5],int n); //將模擬創(chuàng)建的高考學(xué)生信息記錄存放到文件中 8：void saveresults(int score[10000][5],int n); //按照用戶的要求（總成績在前多少名的學(xué)生記錄），將這n條學(xué)生的記錄存放到新的文件中 9:void load(int score

13、[10000][5]); //從學(xué)生高考記錄源文件中讀取記錄到該二維數(shù)組中 8、 各函數(shù)之間的調(diào)用關(guān)系 1:主函數(shù)可以調(diào)用除子函數(shù)2之外的所有函數(shù) 2：子函數(shù)4可以調(diào)用子函數(shù)2和3 【功能模塊圖】 M A I N InitDivide(d) CreateScore(score) Savesources(score.10000) Lode(copy) DcSort(d,c,0) 返回執(zhí)行時間 Collect(d,c) InitDivide(d) BubbleSort(bubble,0) 返回執(zhí)行時間

14、 Saveresults(bubble,n) Print() 三 詳細(xì)設(shè)計 1.抽象數(shù)據(jù)類型： 該數(shù)據(jù)類型是在分配和收集的時候存放分配成績數(shù)組 1’ 抽象數(shù)據(jù)類型struct LSD struct LSD//隊(duì)列的結(jié)構(gòu)類型，鏈表存儲結(jié)構(gòu)類型 { int *cur;//當(dāng)前位置 struct LSD *next;//隊(duì)列中下一個位置 }; 2’ CreatScore(int score[RecordNumber][KeyNumber])函數(shù) /*創(chuàng)建一個含有RecordNumber名學(xué)生成績記錄的score,包含語文、數(shù)學(xué)、英語、總分和學(xué)號,隨機(jī)生成語文

15、、數(shù)學(xué)、英語的成績。 *傳遞的參數(shù)是成績數(shù)組score，無返回值 */ void CreatScore(int score[RecordNumber][KeyNumber]) { /*偽隨機(jī)生成語文、數(shù)學(xué)、英語的成績*/ for(i=0;i< RecordNumber;i++) { for(j=0;j<3;j++) { score[i][j]=rand()%101; //成績的范圍是0-100 } } /*總分成績初始化*/ for(i=0;i< RecordNumber;i++) { score[i][3]=sc

16、ore[i][0]+score[i][1]+score[i][2]; //總成績?yōu)楦骺瞥煽冎? } /*學(xué)號的初始化*/ for(i=0;i< RecordNumber;i++) score[i][4]=i+1; //學(xué)號是按從前到后的順序依次賦值的 } start 創(chuàng)建Score[1000][5] 含語文、數(shù)學(xué)、英語、總分和學(xué)號 偽隨機(jī)生成語文、數(shù)學(xué)、英語的成績 初始化總分 生成學(xué)號，按從前到后順序 結(jié)束 3’收集函數(shù)Collect(struct LSD d[QueueNumber],int *c[RecordNumber]) /*

17、將分配好的成績數(shù)組d，收集到c指針數(shù)組保存 * 傳遞的參數(shù)為分配好的數(shù)組d和收集的指針數(shù)組c，無返回值 */ void { struct LSD *p; for(i=QueueNumber-1; i>=0; i--) { if(d[i].cur!=NULL) //當(dāng)前隊(duì)列不空，即有學(xué)生的成績分配到該隊(duì)列 { p=&d[i]; while(p->cur!=NULL) //當(dāng)前位置有學(xué)生的成績 { c[j]=p->cur; //收集到c指針數(shù)組中 j++;

18、p=p->next; //指針p指向該隊(duì)列的下一個位置 } } } } 當(dāng)前位置有學(xué)生的成績開始 初始化指針數(shù)組 建立300個隊(duì)列 隊(duì)列為空 Y N 當(dāng)前位置學(xué)生的成績收集到指針數(shù)組中 指針p指向該隊(duì)列的下一個位置 結(jié)束 4’初始化分配數(shù)組InitDivide(struct LSD d[QueueNumber]) /*初始化d數(shù)組即置空，在每一次收集后必須做的工作 *傳遞的參數(shù)是struct LSD d[QueueNumber]，無返回值 */ void InitDivide(stru

19、ct LSD d[QueueNumber]) { for(int i=0;i

20、針數(shù)組int *c[RecordNumber]，關(guān)鍵字代表的學(xué)科在數(shù)組中的下標(biāo) */ double DCSort(struct LSD d[QueueNumber],int *c[RecordNumber],int n) { /*按關(guān)鍵字代表的學(xué)科成績將成績分配到d中*/ for(j=0;j

21、添加到該隊(duì)列中 p=&d[temp]; p1=(struct LSD *)malloc(LENGTH); p1->cur=NULL; p1->next=NULL; p->next=p1; //初始化剛剛添加了學(xué)生記錄的隊(duì)列 } else //當(dāng)前隊(duì)列不為空 { p=&d[temp]; /*循環(huán)，一直到隊(duì)列的結(jié)尾*/ while(p->cur!=NULL) p=p->next; p->cur=c[j]; //將c[j]代表的學(xué)生的

22、成績添加到該隊(duì)列中 p1=(struct LSD *)malloc(LENGTH); //新申請一個空間來存放學(xué)生成績 p1->cur=NULL; p1->next=NULL; p->next=p1; } } //分配完畢 Collect(d,c); //將分配好的成績序列收集到c中 InitDivide(d); //初始化分配數(shù)組 return time; //返回執(zhí)行時間 } 6’冒泡法排序double BubbleSo

23、rt(int bubble[RecordNumber][QueueNumber]) /*冒泡法排序 *傳遞的參數(shù)是學(xué)生成績記錄int bubble[RecordNumber][KeyNumber]，關(guān)鍵字所代表學(xué)科成績在數(shù)組中的下標(biāo) */ double BubbleSort(int bubble[RecordNumber][KeyNumber],int n) { for(int i=0;i

24、][n]) { /*交換學(xué)生的各科成績*/ for(int m=0;m

25、t() { FILE *fp; if((fp=fopen("D:\\recordresults.txt","rb"))==NULL) printf("文件打開失敗!\n"); else printf("文件打開成功!\n"); char t; while(fscanf(fp,"%c",&t)&&!feof(fp)) { if(t!=EOF) printf("%c",t); } //如果讀到結(jié)束符，循環(huán)結(jié)束，輸出結(jié)束 fclose(fp); //關(guān)閉文件 } 8’ s

26、avesources(int score[RecordNumber][KeyNumber],int n) /*保存學(xué)生記錄的函數(shù) *參數(shù)為要保存的學(xué)生記錄和記錄條數(shù) *無返回值 */ void savesources(int score[RecordNumber][KeyNumber],int n) { FILE *fp; //指向文件的指針 if((fp=fopen("D:\\recordsources.txt","wb"))==NULL) //只寫 { printf("文件打開失敗!\n"); exit(1); } fprintf(f

27、p,"%d",n); //將記錄條數(shù)寫入文件 fprintf(fp,"\r\n"); //將換行符號寫入文件 for(i=0;i

28、ordNumber][KeyNumber],int n) /*保存學(xué)生記錄的函數(shù) *參數(shù)為要保存的學(xué)生記錄和記錄條數(shù) *無返回值 */ void saveresults(int score[RecordNumber][KeyNumber],int n) { FILE *fp; //指向文件的指針 if((fp=fopen("D:\\recordresults.txt","wb"))==NULL) //只寫,打開或建立一個二進(jìn)制文件，只允許寫數(shù)據(jù) { printf("文件打開失敗!\n"); exit(1); } fpr

29、intf(fp,"%d",n); //將記錄條數(shù)寫入文件 fprintf(fp,"\r\n"); //將換行符號寫入文件 for(i=0;i

30、(int score[RecordNumber][KeyNumber]) /*讀入函數(shù)，把文件中的記錄度入到二維數(shù)組中 *參數(shù)為結(jié)構(gòu)體數(shù)組 */ void load(int score[RecordNumber][KeyNumber]) { FILE *fp; if((fp=fopen("D:\\recordsources.txt","rt"))==NULL) //打開文件 { printf("文件打開失敗!\n"); exit(1); } fscanf(fp,"%d",&n); //讀入記錄數(shù) for(i=0;

31、i

32、位，每一趟都是在前一趟的基礎(chǔ)上，根據(jù)關(guān)鍵字的某一位對所有的記錄進(jìn)行排序，直至最高位，這樣就完成了基數(shù)排序的全過程。 從算法中可以看出，對于n個記錄(每個記錄含d個子關(guān)鍵字，每個子關(guān)鍵字的取值范圍為RADIX個值)進(jìn)行鏈?zhǔn)脚判虻臅r間復(fù)雜度為O(d(n+RADIX)),其中每一趟分配算法的時間復(fù)雜度為O(n)，每一趟收集的算法的時間復(fù)雜度為O(RADIX)，整個排序進(jìn)行d趟分配和收集，所需輔助空間為2*RADIX個隊(duì)列指針。由于需要鏈表作為存儲結(jié)構(gòu)，則相對于其他以順序結(jié)構(gòu)存儲記錄的排序方法而言，還增加了n個指針域的空間。 2） 冒泡法排序： 該排序是比較簡單的交換類排序方法，通過相鄰數(shù)據(jù)元素

33、的交換，逐步將帶排序列變成有序序列的過程。 最壞情況下，待排序的記錄按關(guān)鍵字的逆序進(jìn)行排列，此時，每一趟冒泡排序需要進(jìn)行i次比較，3i次移動。經(jīng)過n-1趟冒泡排序后，總的比較次數(shù)為N=∑i=n(n-1)/2,n=1，2，…，n-1.總的移動次數(shù)為3n(n-1)/2次，因此該算法的時間復(fù)雜度為O(n*n)，空間復(fù)雜度為O(1)。另外，冒泡排序法是一種穩(wěn)定的每部排序法。 四 測試成果 五 附錄（源程序清單） #include #include #include #include str

34、uct LSD //抽象類型定義，隊(duì)列的結(jié)構(gòu)類型，由于是按LSD法進(jìn)行的排序，所以命名為LSD { int *cur; //當(dāng)前位置 struct LSD *next; }; #define LENGTH sizeof(struct LSD) void CreatScore(int score[10000][5]); //隨機(jī)創(chuàng)建學(xué)生記錄表score。正常高考中該表是已知的，不必創(chuàng)建 void savesources(int score[10000][5],int n); //將模擬創(chuàng)建的高考學(xué)生信息記錄存放到文件中 void load

35、(int score[10000][5]); //從學(xué)生高考記錄源文件中讀取記錄到該二維數(shù)組中 void Collect(struct LSD d[301],int *c[10000]); //LSD法排序中的收集函數(shù)，即將分配好的記錄收集到c指針數(shù)組保存 void InitDivide(struct LSD d[301]); //用于初始化臨時分配數(shù)組，在每一次收集后必須做的工作 double DCSort(struct LSD d[301],int *c[10000],int n); //分配（Divide）和收集（Collect）排序的方法 double

36、 BubbleSort(int score[10000][5],int n); //冒泡法排序 void saveresults(int score[10000][5],int n); //按照用戶的要求（總成績在前多少名的學(xué)生記錄），將這n條學(xué)生的記錄存放到新的文件中 void Print(); //將排序結(jié)果文件中的記錄數(shù)據(jù)輸出到屏幕上 int main() { double BubTime1, //按第一個關(guān)鍵字代表的學(xué)科成績用冒泡法排序執(zhí)行的時間 BubTime2, BubTime3, BubTime4, BubT

37、imeSum, //冒泡法排序的總時間 DCTime1, //按第一個關(guān)鍵字代表的學(xué)科成績用分配和收集的方法執(zhí)行的時間 DCTime2, DCTime3, DCTime4, DCTimeSum; //分配和收集法排序的總時間 int score[10000][5], //隨機(jī)創(chuàng)建的模擬學(xué)生記錄源數(shù)組 bubble[10000][5], //進(jìn)行冒泡法排序時用來存放學(xué)生記錄源數(shù)組，并且隨排序進(jìn)行數(shù)組中的記錄發(fā)生交換 copy[10000][5]; //從模擬的學(xué)生記錄源txt文件中讀取學(xué)生記錄到該數(shù)組 struct LSD d[30

38、1]; //分配數(shù)組，該處考慮到把總分（0-300）也列入優(yōu)先級序列中，因此建立了301個隊(duì)列 int *c[10000]; //用來存放收集到的學(xué)生記錄 char x[5]; //存放有優(yōu)先關(guān)系的學(xué)科代號序列 /*初始化c，使其與score函數(shù)"同步"*/ for(int i=0;i<10000;i++) c[i]=score[i]; InitDivide(d); //初始化隊(duì)列 /*在實(shí)際中全部學(xué)生的高考記錄是存放在一個文件中的，程序運(yùn)行時是從該文件中讀取的源記錄數(shù)據(jù)。 *本程序要求隨機(jī)模擬創(chuàng)建該文件，所以

39、下面要創(chuàng)建每個學(xué)生的記錄（CreatScore()）并保存到一個文件中（save()） *調(diào)用這兩個函數(shù)后就生成了全部學(xué)生的記錄 */ CreatScore(score); //偽隨機(jī)生成各科成績，并將考號和總成績一并生成在score數(shù)組中 savesources(score,10000); //將隨機(jī)生成的記錄信息保存在record.txt中，該文件在程序運(yùn)行的時候是不變的 load(copy); //從源記錄文件record.txt中讀取學(xué)生記錄到數(shù)組copy中 /*為了防止改變源記錄，在進(jìn)行冒泡法排序的時候用bubble這個數(shù)組*/

40、 for(i=0;i<10000;i++) for(int j=0;j<5;j++) bubble[i][j]=copy[i][j]; //將源記錄賦值給bubble數(shù)組 printf("請輸入您要按照哪種優(yōu)先級順序?qū)W(xué)生成績進(jìn)行排序：比如（總分，數(shù)學(xué)，語文，英語）\n就請輸入smce(即各科的英文首字母序列)"); scanf("%s",x); //輸入進(jìn)行排序的關(guān)鍵字的優(yōu)先序列 for(i=3;i>=0;i--) { printf("\n\n現(xiàn)在程序正在按%c代表的學(xué)科進(jìn)行成績分配，請稍后…",x[i]); swit

41、ch(x[i]) { case c: //Chinese DCTime1=DCSort(d,c,0); //按語文這個關(guān)鍵字用分配和收集法排序，并返回時間 BubTime1=BubbleSort(bubble,0); //按語文這個關(guān)鍵字用冒泡法排序 break; case m: //Math DCTime2=DCSort(d,c,1); BubTime2=BubbleSort(bubble,1); break; case e: //English DCTime3

42、=DCSort(d,c,2); BubTime3=BubbleSort(bubble,2); break; case s: //Sum DCTime4=DCSort(d,c,3); BubTime4=BubbleSort(bubble,3); break; default: printf("您輸入的科目代號錯誤\n"); //輸入代號錯誤提示 break; } } DCTimeSum=DCTime1+DCTime2+DCTime3+DCTime4; //分配排序法的總時間等于按照各個關(guān)鍵字進(jìn)行

43、排序的分時間的和 BubTimeSum=BubTime1+BubTime2+BubTime3+BubTime4; printf("\n用分配和收集的方法排序，執(zhí)行的總時間為：%.3f\n",DCTimeSum); printf("用冒泡法排序,執(zhí)行的總時間為：%.3f\n",BubTimeSum); printf("\n請問您要提取多少條學(xué)生的成績信息（0-10000）："); int n; scanf("%d",&n); saveresults(bubble,n); //將前n名學(xué)生的記錄保存在結(jié)果文件recordresults.txt中 Pri

44、nt(); //從結(jié)果文件recordresults.txt中讀取記錄到屏幕上 return 0; } /*創(chuàng)建一個含有10000名學(xué)生成績記錄的score,包含語文、數(shù)學(xué)、英語、總分和學(xué)號,隨機(jī)生成語文、數(shù)學(xué)、英語的成績。 *傳遞的參數(shù)是成績數(shù)組score，無返回值 */ void CreatScore(int score[10000][5]) { int i, j; srand(time(NULL)); //利用時間設(shè)置隨機(jī)種子產(chǎn)生隨機(jī)數(shù) /*偽隨機(jī)生成語文、數(shù)學(xué)、英語的成績*/ for(i=0;i<10

45、000;i++) { for(j=0;j<3;j++) { score[i][j]=rand()%101; //成績的范圍是0-100 } } /*總分成績初始化*/ for(i=0;i<10000;i++) { score[i][3]=score[i][0]+score[i][1]+score[i][2]; //總成績?yōu)楦骺瞥煽冎? } /*學(xué)號的初始化*/ for(i=0;i<10000;i++) score[i][4]=i+1; //學(xué)號是按從前到后的順序依次賦值的 }

46、/*保存學(xué)生記錄的函數(shù) *參數(shù)為要保存的學(xué)生記錄和記錄條數(shù) *無返回值 */ void savesources(int score[10000][5],int n) { printf("\n程序正在模擬創(chuàng)建10000條高考成績記錄并保存到文件D:\\recordresources.txt中，\n請稍后…\n"); //輸出提示信息 int i; FILE *fp; //指向文件的指針 if((fp=fopen("D:\\recordsources.txt","wb"))==NULL) //只寫,打開或建立一個二進(jìn)制文件，只允許寫數(shù)據(jù) {

47、 printf("文件打開失敗!\n"); exit(1); } fprintf(fp,"%d",n); //將記錄條數(shù)寫入文件 fprintf(fp,"\r\n"); //將換行符號寫入文件 for(i=0;i

48、換行符號寫入文件 } fclose(fp); printf("文件創(chuàng)建并保存成功!\n您可以通過路徑D:\\recordsources.txt進(jìn)行查看。\n\n\n"); } /*讀入函數(shù)，把文件中的記錄度入到二維數(shù)組中 *參數(shù)為結(jié)構(gòu)體數(shù)組 */ void load(int score[10000][5]) { int i, n; FILE *fp; if((fp=fopen("D:\\recordsources.txt","rt"))==NULL) //打開文件 { printf("文件打開失敗!\n"); exi

49、t(1); } fscanf(fp,"%d",&n); //讀入記錄數(shù) for(i=0;i

50、**********排序系統(tǒng)開始運(yùn)行********************************\n"); printf("首先是從模擬高考成績源文件recordsources.txt中讀取數(shù)據(jù)!\n正在讀取數(shù)據(jù)，請稍后…\n"); printf("成功從源文件中讀取 %d 條記錄到排序系統(tǒng)中\(zhòng)n\n", n); } /*將分配好的成績數(shù)組d，收集到c指針數(shù)組保存 * 傳遞的參數(shù)為分配好的數(shù)組d和收集的指針數(shù)組c，無返回值 */ void Collect(struct LSD d[301],int *c[10000]) { int i

51、, j=0; struct LSD *p; for(i=300; i>=0; i--) //因?yàn)榘偝煽儯?-300）的優(yōu)先級，所以共分配的隊(duì)列為0-300 { if(d[i].cur!=NULL) //當(dāng)前隊(duì)列不空，即有學(xué)生的成績分配到該隊(duì)列 { p=&d[i]; while(p->cur!=NULL) //當(dāng)前位置有學(xué)生的成績 { c[j]=p->cur; //收集到c指針數(shù)組中 j++; p=p->next; //指針p指向該隊(duì)列的下一個

52、位置 } } } } /*初始化d數(shù)組即置空，在每一次收集后必須做的工作 *傳遞的參數(shù)是struct LSD d[301] */ void InitDivide(struct LSD d[301]) { for(int i=0;i<301;i++) { d[i].cur=NULL; d[i].next=NULL; } } /*"分配"和"收集"方法排序 *分配數(shù)組為d，收集數(shù)組為c *進(jìn)行排序的關(guān)鍵字所代表的學(xué)科成績n在分配數(shù)組中的位置就是n *傳遞的參數(shù)是分配數(shù)組struct LSD d[301]，用來收集的指針數(shù)組in

53、t *c[10000]，關(guān)鍵字代表的學(xué)科在數(shù)組中的下標(biāo) */ double DCSort(struct LSD d[301],int *c[10000],int n) { double time; clock_t t_start; //時間記錄的開始 clock_t t_end; //時間記錄的結(jié)束 t_start=clock(); //獲取排序開始的時間 int j, temp; struct LSD *p,*p1; /*按關(guān)鍵字代表的學(xué)科成績將成績分配到d中*/ for(j

54、=0;j<10000;j++) { temp=c[j][n]; //學(xué)生的成績就是隊(duì)列號 if(d[temp].cur==NULL) //當(dāng)前隊(duì)列為空 { d[temp].cur=c[j]; //將c[j]代表的學(xué)生的成績添加到該隊(duì)列中 p=&d[temp]; p1=(struct LSD *)malloc(LENGTH); p1->cur=NULL; p1->next=NULL; p->next=p1; //初始化剛剛添加了學(xué)生記錄的隊(duì)列 }

55、 else //當(dāng)前隊(duì)列不為空 { p=&d[temp]; /*循環(huán)，一直到隊(duì)列的結(jié)尾*/ while(p->cur!=NULL) p=p->next; p->cur=c[j]; //將c[j]代表的學(xué)生的成績添加到該隊(duì)列中 p1=(struct LSD *)malloc(LENGTH); //新申請一個空間來存放學(xué)生成績 p1->cur=NULL; p1->next=NULL; p->next=p1; } } //分

56、配完畢 printf("\n分配完畢，下面開始進(jìn)行收集，請稍后…\n"); Collect(d,c); //將分配好的成績序列收集到c中 printf("收集完畢。\n"); InitDivide(d); //初始化分配數(shù)組 t_end = clock(); //獲取結(jié)束測試點(diǎn)的時間 time=(double)(t_end-t_start)/CLOCKS_PER_SEC; printf("本次分配和收集用時: %.3f s\n",time); return time; //

57、返回執(zhí)行時間 } /*冒泡法排序 *傳遞的參數(shù)是學(xué)生成績記錄int bubble[10000][5]，關(guān)鍵字所代表學(xué)科成績在數(shù)組中的下標(biāo) */ double BubbleSort(int bubble[10000][5],int n) { printf("\n下面開始用冒泡法進(jìn)行排序，請稍后…\n"); double time; clock_t t_start; clock_t t_end; t_start=clock(); int temp; for(int i=0;i<10000;i++)

58、 { for(int j=0;j<9999-i;j++) { if(bubble[j][n]

59、CKS_PER_SEC; printf("本次冒泡法排序用時: %.3f s\n\n",time); return time; //返回排序執(zhí)行的時間 } /*保存學(xué)生記錄的函數(shù) *參數(shù)為要保存的學(xué)生記錄和記錄條數(shù) *無返回值 */ void saveresults(int score[10000][5],int n) { int i; FILE *fp; //指向文件的指針 if((fp=fopen("D:\\recordresults.txt","wb"))==NULL) //只寫,打開或建立一個二進(jìn)制文

60、件，只允許寫數(shù)據(jù) { printf("文件打開失敗!\n"); exit(1); } fprintf(fp,"%d",n); //將記錄條數(shù)寫入文件 fprintf(fp,"\r\n"); //將換行符號寫入文件 for(i=0;i

61、 //將換行符號寫入文件 } fclose(fp); } /*從排序結(jié)果存放的文件recordresults.txt中讀取記錄輸出到屏幕上 */ void Print() { FILE *fp; if((fp=fopen("D:\\recordresults.txt","rb"))==NULL) printf("文件打開失敗!\n"); else printf("文件打開成功!\n"); char t; while(fscanf(fp,"%c",&t)&&!feof(fp))

62、 { if(t!=EOF) printf("%c",t); } //如果讀到結(jié)束符，循環(huán)結(jié)束，輸出結(jié)束 fclose(fp); //關(guān)閉文件 } 六 用戶手冊 本程序的運(yùn)行環(huán)境為DOS系統(tǒng)，執(zhí)行文件為“LSDSort.exe” 進(jìn)入程序后的界面如下： 用戶此時可以按路徑D:\\recordresources.txt文檔中查看模擬高考成績表 自動計算出分配收集法和冒泡法分別所需要的時間，綜合比較兩種方法 按照提示輸入自己要求的各個成績的優(yōu)先關(guān)系序列，然后程序自動進(jìn)入排序系統(tǒng)，最后程序就將分配和收集的過程以及冒泡法排序的過程分別輸出，

63、最后得到排序結(jié)果。 然后會到下面的界面： 即提示用戶輸入錄取的學(xué)生數(shù)目，由于把全部成績輸出對于高校錄取并沒有用，所以只要按一定的人數(shù)提取記錄就可以了 4.課程設(shè)計心得 這次課程設(shè)計收獲很大，從一開始的迷迷糊糊不明白題意，到現(xiàn)在很清楚該設(shè)計的各個方面，我在無數(shù)次的調(diào)試過程中學(xué)到了很多有用的東西 1、模塊化的思想。使程序模塊化之后，可以很方便的調(diào)用和對某個模塊的修改，我由于一開始對題目的要求不到位，在最后驗(yàn)收的時候發(fā)現(xiàn)一些功能未實(shí)現(xiàn)的問題，如果我的程序很亂，函數(shù)之間沒有清晰的調(diào)用關(guān)系，參數(shù)傳遞混亂的話，我就很難修改它，但是我用了模塊化的思想，在很短的時間之內(nèi)就將程序添加了文件流操

64、作的功能，使程序更加滿足實(shí)際要求，也更加清晰?，F(xiàn)在可以很容易添加一個不同的功能模塊。 2、調(diào)試技巧。在調(diào)試過程中同學(xué)們遇到了很多不同的錯誤，比如：錯誤提示如下 Cpp1.obj : error LNK2001: unresolved external symbol "void __cdecl CreatScore(int (* const)[5])" (?CreatScore@@YAXQAY04H@Z) Debug/Cpp1.exe : fatal error LNK1120: 1 unresolved externals。根據(jù)以前的經(jīng)驗(yàn)知道這是連接上出了錯，而且以前遇到類似的錯誤是因?yàn)?/p>

65、傳遞的參數(shù)不同而導(dǎo)致的，現(xiàn)在也想到估計是同樣的問題，但是看程序，參數(shù)傳遞正常。后來在找CreatScore時發(fā)現(xiàn)我不知道什么時候把它剪切了，這就好像是聲明了程序要用CreatScore，而且也用了，但是并沒有說明CreatScore是什么，它是怎樣實(shí)現(xiàn)的。 3、調(diào)試技巧。調(diào)試的時候我一般都是用F10和F20進(jìn)行調(diào)試，問老師的時候又學(xué)到了設(shè)置斷點(diǎn)的方法調(diào)試程序，這樣可以通過猜想，對某一段代碼進(jìn)行調(diào)試，省去了很多步驟。 4、分析問題的技巧。這個和設(shè)置斷點(diǎn)的方法類似，例如在判斷打開文件是否成功時，由于有三個函數(shù)要打開和關(guān)閉文件，而且從無提示都一樣：文件打開失敗。這樣在運(yùn)行程序時，如果文件

66、真的打開失敗了，就很難知道哪塊函數(shù)出問題了，所以可以設(shè)置不同的提示信息，來很清楚的追蹤到程序的運(yùn)行，還有就是發(fā)送錯誤報告，這種問題出現(xiàn)時總感覺不知道如何下手修改，因?yàn)楹茈y知道錯誤的發(fā)生點(diǎn)，這是我們就可以設(shè)置輸出提示信息：“程序已經(jīng)運(yùn)行到這里了”這樣我們就可以從它是否輸出該提示信息來了解程序是否正常運(yùn)行到某個位置。 5、在修改錯誤的時候也要有至頂向下的修改方法，因?yàn)楹竺娴腻e誤很可能就是勤勉的定義錯誤，從上到下改，我們可以發(fā)現(xiàn)有時候錯誤從80多個一下子就變成兩三個了，通過這個我們也可以看到不同的錯誤所影響的范圍，對我們變成中的側(cè)重點(diǎn)也有幫助 6、指針和地址的使用。在進(jìn)行文件操作時，我有一個功能就是從文件中讀取學(xué)生記錄到一個二維數(shù)組中，感覺寫的沒錯，可是輸出來的結(jié)果總是一個符合格式要求的地址結(jié)果，經(jīng)過老師的指導(dǎo)，我知道了在讀取的時候應(yīng)該把數(shù)據(jù)存放在數(shù)組的地址中，而我卻是按賦值的錯誤想法做的。 7、冒泡法排序。我認(rèn)為這個排序的算法很簡單，所以用到的時候沒有按照書上的算法，直接自己寫了一個冒泡排序，而且一直深信我的這個排序是正確的，可是結(jié)果總是出現(xiàn)錯誤，排序結(jié)果并不正確，后