《课程设计报告-多关键字排序2.docx》由会员分享，可在线阅读，更多相关《课程设计报告-多关键字排序2.docx（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、合肥学院计算机科学与技术系课程设计报告20122013学年第二学期2013 年 6 月Cppl. obj : error LNK2001: unresolved external symbol void _cdecl CreatScore(int (* const)5) (?CreatScoreYAXQAY04HZ)Debug/Cppl. exe : fatal error LNK1120: 1 unresolved externalso 根据以前 的经验知道这是连接上出了错，而且以前遇到类似的错误是因为传递的参数不同 而导致的，现在也想到估计是同样的问题，但是看程序，参数传递正常。后来在 找
2、CreatScore时发现我不知道什么时候把它剪切了，这就好像是声明了程序要 用CreatScore,而且也用了，但是并没有说明CreatScore是什么，它是怎样实 现的。还有在定义struct LSD d301时,刚开始是用d101的，后来才程序中无法将 总成绩的信息放进去，导致了无法访问。五、测试结果及其分析C:UsBrsAdministQtorDesktop课程 i2iflDebugTextl.exe程序正在模拟创立工0000条高考成绩记录并保存到文件D： XrecoiTesoiwces.txt中,3r圃建曲铸成功？txt进行查看。您可以,通过路住D： 7、e cords ounces
3、 .y序系统开始运行首至港从数以高孝感透源文件reco犬dsoiwces.txt中读取数据？盅功篇舞盘新0000条记录到排序系统中9知耆输Xs ncegp4H的央交昔子母序列9知耆输Xs ncegp4H的央交昔子母序列:比方(总分，数学，语文，英语)图三C:UsersAd ministratorDesktopiSiflDebugTextl.exe,、士 1IB、士 1IBnee婀各 召：艮 八在下正，按面口 。不隹级螃指好或绩进行排序：比方（总分，数学，语文，英语） 勺央文首子母序列S me e罄 弋戈 年开XI己 酉： 分请稍后嬲骤髓喝财后嬲骤髓喝财后正：和 岳工十配 程完士火刀 在现八正：
4、和 岳工十配 程完士火刀 在现八请稍后下面开凿用量泡法进行排序，请稍后 本次冒洵法排序用时：1.241 s下面开凿用量泡法进行排序，请稍后 本次冒洵法排序用时：1.241 s图四C:UsersAd ministratorDesktopiziitlDebugTextl.exe,rrrr-1 ， OTrr 岳工十配 程完士穴刀 在现八按面集后 稍 请（耨罐勰髓即吸F稍后（耨罐勰髓即吸F稍后窿胃鬻牖稳置虐翳配 保袋3都而收集用时=0.萌9 s帽罐非赢牌财后,耀麟航鬻氟魏骋那为:0-044 请问您要提取多少条学生的成绩信息（0T0000）：图五C:UsersAd ministratorDesktopi
5、TflDebugTextl.exe, 汉图六六、用户使用说明进入程序后的界面如下:C:UsBrsAdministQtorDesktop课程 i2iflDebugTextl.exe程序正在模拟创立10000条ri考成绩记录并保存到文件D： 5ecoiTesoiwces.txt中, 请稍尸.W牛创立型建成功？“f工也可以通过路住D： 7、ecoi*dsou犬ces.txt进仃查看。排序系统开始运行从取源 日强从 功 首正成从取源 日强从 功 首正成我以高翥球绩源文件re c o rds o urc e s廨苗覆取力0 ，一二二二二二-txt中读取数据?10000条记录到排序系统中然薪鬻鬻翱罐嫖辍绩
6、进行排序：比方（总分数学，语文，英语）图七用户此时可以按路径D:recordresources.txt文档中查看模拟高考成绩表自动计算出分配收集法和冒泡法分别所需要的时间，综合比拟两种方法C:UsersAd ministratorDesktopizSvtlDebugTextl.exe就请输入smee即各科的英就请输入smee即各科的英nee:比方（总分，数学，语文，英语）矍蠹嘴甯翻颦懦鹘请稍后 收集完毕。冷茨羯己输收集用时：0.010 s下面开箱唐郭&法造行排序，请稍后本次冒阖出排序用舟：1.215 s跟在建庄正在按c仿雌I学型行通能分配，请稍后 除鸵窕生,下面开始进存收集.谙稍后 收建为隼。
7、本次分配和收集用时：0013 s下面开凿用量退法进行排序，请稍后 本次冒泡法知序用时：1.241 s图八图九按照提示输入自己要求的各个成绩的优先关系序列，然后程序自动进入排序系统，最 后程序就将分配和提供的过程以及冒泡法排序的过程分别输出，最后得到排序结果。然后会到下面的界面:C:UsersAd ministratorDesktopiTflDebugTextl.exe,鳏奔髓臀少条学生的成绩信息-3030456596100992953447999599293263310097942915829979499290407499999028865049499952886489798932883354
8、959598288978899919728753449699912861589969892286201594921002866591100932842615889997284752893969528428209499902837800939892283848586100962824187969590281361393909828188581008794281371998892279图十七、参考文献1王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月。2其它。八、附录#include#include#include#includestruct LSD抽象类型定义，队列的结构类型，
9、由于是按LSD法进行的排序，所以命名为LSD (int *cur;当前位置struct LSD *next;)；#define LENGTH sizeof(struct LSD)void CreatScore(int score100005);/随机创立学生记录表 scoreo 正常高考中该表是的，不必创立void savesources(int score100005,int n);将模拟创立的高考学生信息记录存放到文件中从学生高考记录源文件中读void load(int score100005);取记录到该二维数组中void Collect(struct LSD d3Ol,int *c 1
10、0000);/LSD 法排序中的收集函数，即将分配好的记录收集到c指针数组保存void InitDivide(struct LSD d301);/用于初始化临时分配数组，在每一次收集后必须做的工作double DCSort(struct LSD d301,int *c 10000,int n);分配(Divide)和收集(Collect)排序 的方法double BubbleSort(int scorefl00005,int n);冒泡法排序void saveresults(int score100005,int n);按照用户的要求(总成绩在前多少名的学生记录)，将这n条学生的记录存放到新的
11、文件中void Print();/将排序结果文件中的记录数据输出到屏幕上int main() (int i,j,n;按第一个关键字代表的学科成绩用冒泡法排序执行的时间/冒泡法排序的总时间按第一个关键字代表的学科成绩用分配和提供的方法执double BubTimel,BubTime2, BubTime3, BubTime4, BubTimeSum, DCTimel, 行的时间DCTime2,DCTime3,DCTime4,DCTimeSum;分配和收集法排序的总时间int score100005,随机创立的模拟学生记录源数组bubble100005, /进行冒泡法排序时用来存放学生记录源数组，并
12、且随排序进行 数组中的记录发生交换copy100005;/从模拟的学生记录源txt文件中读取学生记录到该数组struct LSDd301; 分配数组，该处考虑到把总分(0-300)也列入优先级序列中， 因此建立了 301个队列int *c10000;用来存放收集到的学生记录char x5;存放有优先关系的学科代号序列/*初始化c,使其与score函数同步”*/for(i=0;i10000;i+) ci=scorci;InitDivide(d);初始化队列/*在实际中全部学生的高考记录是存放在一个文件中的，程序运行时是从该文件中读取 的源记录数据。*本程序要求随机模拟创立该文件，所以下面要创立每
13、个学生的记录(CreatScore。)并 保存到一个文件中(save()*调用这两个函数后就生成了全部学生的记录*/CreatScore(score);在score数组中savesources(score, 10000);件在程序运行的时候是不变的 load(copy);数组copy中CreatScore(score);在score数组中savesources(score, 10000);件在程序运行的时候是不变的 load(copy);数组copy中随机生成各科成绩，并将考号和总成绩一并生成将随机生成的记录信息保存在record.txt中，该文从源记录文件record.txt中读取学生记录到
14、printf(nnn现在程序正在按。代表的学科进行成绩分配,请稍后/Chinese按语文这个关键字用分配和收集/按语文这个关键字用冒泡法排序/Math/English/Sum输入代号错误提示/*为了防止改变源记录，在进行冒泡法排序的时候用bubble这个数组*/ for(i=0;i10000;i+)for(j=0;j=0;i)switch(xij)case c:DCTimel=DCSort(d,c,0);法排序，并返回时间BubTime 1 =BubbleSort(bubble,0);break;casem:DCTime2=DCSort(d,c, 1);BubTime2=BubbleSort(
15、bubble, 1);break;case e:DCTime3=DCSort(d,c,2);BubTime3=BubbleSort(bubble,2); break;case C:DCTime4=DCSort(d,c,3)；BubTime4=BubbleSort(bubble,3)； break;default:printf(您输入的科目代号错误n)break;)DCTimeSum=DCTime 1 +DCTime2+DCTime3+DCTime4; /分配排序法的总 时间等于按 照各个关键字进行排序的分时间的和BubTimeSum=BubTime 1 +BubTime2+BubTime3+B
16、ubTime4;printf(”n用分配和提供的方法排序，执行的总时间为：%.3fnn,DCTimeSum);printf(”用冒泡法排序，执行的总时间为：.3An”,BubTimeSum);printf(”n请问您要提取多少条学生的成绩信息(0-10000)： ”)；scanf(n%dn,&n);saveresults(bubble,n);/将前n名学生的记录保存在结果文件recordresults.txt 中Print();从结果文件recordresults.txt中读取记录到屏幕上return 0;)/*创立一个含有10000名学生成绩记录的score,包含语文、数学、英语、总分和学号
17、，随机生 成语文、数学、英语的成绩。*传递的参数是成绩数组score,无返回值*/void CreatScore(int score100005) (int ij;srand(time(NULL);利用时间设置随机种子产生随机数/*伪随机生成语文、数学、英语的成绩*/for(i=0;i10000;i+)(for(j=0;j3;j+)(scoreij=rand()%101;成绩的范围是 0-100)/*总分成绩初始化*/for(i=0;i10000;i+)scorei 3=scorei 0+scorei 1 +scorei 2;总成绩为各科成绩之和/*学号的初始化*/for(i=0;i10000
18、;iH-+)scorei4=i+1;学号是按从前到后的顺序依次赋值的/*保存学生记录的函数* 参数为要保存的学生记录和记录条数无返回值* /void savesources(int scorefl00005,int n)(int i;FILE *fp;指向文件的指针printf(nn程序正在模拟创立10000条高考成绩记录并保存到文件D:recordresources.txt 中，n请稍后n)输出提示信息if(fp=fopen(D:recordsources.txtn/wbn)=NULL) 只写，翻开或建立一个二进制 文件，只允许写数据(printff文件翻开失败!n”);exit(l);)f
19、printf(fp；1%dn,n);将记录条数写入文件fprintf(fpjrn)；将换行符号写入文件for(i=0;in;i+)fprintf(fp；,%-10d%-10d%-10d%-10d%-10dn,scorei4,scorei0,scoreil,scorei2,sc ore皿3);/格式写入记录fprintf(fp/rnn);将换行符号写入文件)fclose(fp);printf(文件创立并保存成功!n您可以通过路径D:recordsources.txt进行查看。nnn”); )/*读入函数，把文件中的记录读入到二维数组中* 参数为结构体数组/void load(int score
20、100005)int i,n;FILE *fp;if(fp=fopen(D:recordsources.txt，Vrtn)=NULL) (printf(文件翻开失败!n”)；exit(l);)fscanf(fp,n%dM,&n);for(i=0;in;i+)fscanf(fp,n%d %d %d %d %d&scorei4,&scorei0,&scoreil,&scorei2,&scorei3);fclose(fp);if(fp=fopen(D:recordsources.txt，Vrtn)=NULL) (printf(文件翻开失败!n”)；exit(l);)fscanf(fp,n%dM,&n
21、);for(i=0;in;i+)fscanf(fp,n%d %d %d %d %d&scorei4,&scorei0,&scoreil,&scorei2,&scorei3);fclose(fp);翻开文件读入记录数按格式读入记录printf(”* 排 序 系 统 开 始 运 行*1* *1*1* =0; i-)以共分配的队列为0-300(if(di.cur!=NULL) 该队列P=&di;while(p-cur!=NULL)void Collect(struct LSD d301,int *c 10000) (int i,j=0;struct LSD *p;for(i=300; i=0; i-
22、)以共分配的队列为0-300(if(di.cur!=NULL) 该队列P=&di;while(p-cur!=NULL)因为包含总成绩（0-300）的优先级，所当前队列不空，即有学生的成绩分配到当前位置有学生的成绩题目：多关键字的排序有其一定的实用范围。例如：在进行高考分数处理时，除了需对总 分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户 提出的单科分数的次序要求排出考生录取的次序。一、问题分析和任务定义1、对高考分数按照总分和不同学科的分数按照优先级顺序排出考生录取的次序，以满 足不同专业对单科分数的要求。2、对不同排序策略进行综合比拟。二、数据结构的选择和概
23、要设计2.1自动随机产生成绩进行操作1、2、3、4、5、伪随机生成的数据包含语文、数学、英语三科成绩。总成绩为语文、数学、英 语三科成绩的和。学号按成绩数组的下标赋值，生成学生成绩记录，将该记录 保存到txt文档中。从上面的txt文档中读取数据到一个二维数组中，以便对学生信息进行处理。 给出排序的优先关系，根据优先关系由低位向高位逐个关键字进行排序。对单科成绩进行排序的时候，单科成绩虽然是0-100,但总成绩是0-300,所以 要建301个队列进行排序，先按“分配”和“”的方法进行一趟“基数排 序”；然后再按照稳定的内部排序法（冒泡法）进行排序。将好的或排序好 的序列存储，以进行对次优先级的关
24、键字进行再排序。将排序好的学生成绩按照用户提出的提取人数的要求,保存到另一个txt文档中, 并输出到屏幕。2. 2存储结构设计struct LSDdouble BubTimel, 间抽象类型定义，队列的结构类型，由于是按LSD 法进行的排序，所以命名为LSD当前位置int *cur;struct LSD *next;按第一个关键字代表的学科成绩用冒泡法排序执行的时BubTime2, BubTime3, BubTime4, BubTimeSum,冒泡法排序的总时间DCTimel,按第一个关键字代表的学科成绩用分配和提供的方法执行的时间DCTime2, DCTime3, DCTime4, DCTi
25、meSum;分配和收集法排序的总时间 int score10000 5,随机创立的模拟学生记录源数组bubble10000 5,进行冒泡法排序时用来存放学生记录源数组，并且随排序进行数组中的记录发生交换copy 10000 5;从模拟的学生记录源txt文件中读取学生记录到该数组struct LSD d301; 分配数组，该处考虑到把总分（0-300）也列入 优先级序列中，因此建立了 301个队列int *c10000;用来存放收集到的学生记录char x 5;存放有优先关系的学科代号序列2.3 LSD排序与冒泡排序cj=p-cur;收集到c指针数组中j+；p=p-next;指针p指向该队列的下
26、一个位置)/*初始化d数组即置空，在每一次收集后必须做的工作* 传递的参数是struct LSD d301/void InitDivide(struct LSD d301)(int i;for(i=0;i301;i+)(di.cur=NULL;di.next=NULL;)/*”分配，和，收集“方法排序分配数组为d,收集数组为c* 进行排序的关键字所代表的学科成绩n在分配数组中的位置就是n传递的参数是分配数组struct LSD d|301,用来提供的指针数组int *c 100001，关键字代表 的学科在数组中的下标* /double DCSort(struct LSD d301,int *c
27、 10000,int n) (int j,temp;double time;struct LSD *p,*pl;clock_t t_start;时间记录的开始clock_t t_end;时间记录的结束t_start=clock();获取排序开始的时间/*按关键字代表的学科成绩将成绩分配到d中*/for(j=0;jcur=NULL;pl-next=NULL;p-next=p 1;的队列else(p=&dtemp;/*循环，一直到队列的结尾*/while(p-cur!=NULL)p=p-next;p-cur=cj;队列中pInstruct LSD *)malloc(LENGTH);pl-cur=N
28、ULL;pl-next=NULL;p-next=p 1;)printf(”n分配完毕，下面开始进行收集，请稍后n)；Collect(d,c);将分配好的成绩序列收集到c中printf(收集完毕。n)；InitDivide(d);初始化分配数组t_end = clock();获取结束测试点的时间time=(double)(t_end-t_start)/CLOCKS_PER_SEC; printf(”本次分配和收集用时:%.3f snM,time);return time;/返回执行时间/*冒泡法排序*传递的参数是学生成绩记录intbubble100005,关键字所代表学科成绩在数组中的下标dou
29、ble BubbleSort(int bubble 100005,int n)int ij,m;double time;clock_t t_start;clock_t t_end;int temp;t_start=clock();printf(nn下面开始用冒泡法进行排序，请稍后n);for(i=0;i10000;i4-+)(for(j=0;j9999-i;j+)(if(bubblej nbubblej+1 n)(/*交换学生的各科成绩*/for(m=0;m5 ;m+)(temp=bubblej m;bubblej m=bubblej+ lm;bubblej+l |m|=temp;)t_end
30、 = clock();time=(double)(t_end-t_start)/CLOCKS_PER_SEC;printf(本次冒泡法排序用时：%.3fsnnn,time);return time;返回排序执行的H寸间)/*保存学生记录的函数*参数为要保存的学生记录和记录条数*无返回值*/void saveresults(int score100005,int n)(int i;指向文件的指针FILE *fp;if(fp=fopen(,D:recordresults.txt，V，wbn)=NULL) 只写，翻开或建立一个二进制 文件，只允许写数据(printf(文件翻开失败!n”);exit(
31、l); )fprintf(fp；,%d,;n);将记录条数写入文件fprintf(fp；rnn);将换行符号写入文件for(i=0;in;i+)fprintf(fp,n%-10d%-10d%-10d%-10d%-10dn,scorei4,scorei0,scoreil,scorei2,sc orei3);格式写入记录fprintf(fpJNT);将换行符号写入文件)fclose(fp);)/*从排序结果存放的文件recordresults.txt中读取记录输出到屏幕上*/void Print()(char t;FILE *fp;if(fp=fopen(D:recordresults.txtn；
32、,rbn)=NULL)printf(文件翻开失败!n)；elseprintf(文件翻开成功!n“);while(fscanf(fp,n %cn, &t)&! feof(fp)if(t!=EOF)printf(n%c;t);)如果读到结束符，循环结束，输出结束fclose(fp);关闭文件1) LSD算法：这是一种“低位优先”的排序方法，借助一趟基数排序的方法，先按最低位的值 对记录进行初步排序，在此基础上再按次低位的值进行进一步排序。以此类推，有 低位到高位，每一趟都是在前一趟的基础上，根据关键字的某一位对所有的记录进 行排序，直至最高位，这样就完成了基数排序的全过程。2)冒泡法排序：该排序是
33、比拟简单的交换类排序方法，通过相邻数据元素的交换，逐步将带排序列 变成有序序列的过程。子程序及功能设计(1) CreatScore(int scoreRecordNumberKeyNumber)(2)收集函数 Collect (struct LSD dQueueNumber, int *cRecordNumber)(3)初始化分配数组 InitDivide(struct LSD dQueueNumber)(4) 分配和收集方法排序 double DCSort (struct LSD dQueueNumber, int*cRecordNumber,int n)(5)冒泡法排序 double Bu
34、bbleSort (int bubbleRecordNumber QueueNumber)(6) savesources (int scoreRecordNumber KeyNumber, int n) 保存随机产生的 成绩saveresults(int scoreRecordNumberKeyNumber,int n)保存排序过后的成(7) load(int scoreRecordNumberKeyNumber)/加载文本中的成绩Print ()函数(8) Void main();主函数函数与主函数的调用关系图一三、详细设计和编码sitart图二1 .抽象数据类型struct LSDstru
35、ct LSD/队列的结构类型，链表存储结构类型 (int *cur;当前位置struct LSD *next;队列中下一个位置)；2 . CreatScore(int score RecordNumber KeyNumber)函数/*创立一个含有RecordNumber名学生成绩记录的score,包含语文、数学、英语、总分和学号, 随机生成语文、数学、英语的成绩。*传递的参数是成绩数组score,无返回值*/void CreatScore(int score| RecordNumber KeyNumber) (/*伪随机生成语文、数学、英语的成绩*/for(i=0;i RecordNumber
36、;i+)(for(j=0;j3;j+)(scoreij=rand()%101;成绩的范围是 0-100)/*总分成绩初始化*/for(i=0;i RecordNumber;i+)scorei 3=scorei 0+scorei 1 +scorei 2; 总成绩为各科成绩之和/*学号的初始化*/学号是按从前到后的顺学号是按从前到后的顺for(i=0;i=0; i-) (if(di.cur!=NULL)该队列(p=&di;while(p-cur!=NULL) (cj=p-cur;J+；p=p-next;)当前队列不空，即有学生的成绩分配到当前位置有学生的成绩收集到C指针数组中指针P指向该队列的下一
37、个位置4 .初始化分配数组 InitDivide(struct LSD d QueueNumber)/*初始化d数组即置空，在每一次收集后必须做g勺工作*传递的参数是struct LSD dQueueNumber,无返回值*/void InitDivide(struct LSD dQueueNumber)(for(int i=O;iQueueNumber;i+)(di.cur=NULL;di.next=NULL;)5 .分配和收集方法排序 double DCSort (struct LSD d QueueNumber, int *cRecordNumber, int n)/*“分配“和“收集“
38、方法排序* 分配数组为d,收集数组为c进行排序的关键字所代表的学科成绩n在分配数组中的位置就是n* 传递的参数是分配数组struct LSD dQueueNumber,用来提供的指针数组intcRecordNumber,关键字代表的学科在数组中的下标* /double DCSort(struct LSD dQueueNumber,int *cRecordNumber,int n) (/*按关键字代表的学科成绩将成绩分配到d中*/for(j=0;jcur=NULL;pl-next=NULL;p-next=pl;的队列else(p=&dtemp;/*循环，一直到队列的结尾*/while(p-cur
39、!=NULL)p=p-next;p-cur=cj;队列中plstruct LSD *)malloc(LENGTH); pl-cur=NULL;p l-next=NULL;p-next=pl;)Collect(d,c);InitDivide(d);初始化刚刚添加了学生记录当前队列不为空将cj代表的学生的成绩添加到该/新申请一个空间来存放学生成绩分配完毕将分配好的成绩序列收集到C中初始化分配数组return time;返回执行时间)6.冒泡法排序 double BubbleSort (int bubble RecordNumber EQueueNumber)/*冒泡法排序*传递的参数是学生成绩记录int bubbleRecordNumberKeyN