pepole

数据结构课程设计报告

题目：多关键字排序

多关键字排序

【问题描述】

多关键字的排序有一定的实用范围。例如：在进行高考分数处理时，除了需对总分进行排序外，不同的专

业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录

取的次序。

【基本要求】

（1）假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100.。

按用户给定的进行排序的关键字的优先关系，输出排序结果。

（2）约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略：其一是利用稳定的

内部排序法，其二是利用“分配”和“收集”的方法。并综合比较这两种策略。

【测试数据】

由随机数产生器生成。

C语言源程序

#include

#include

#include

#include

#defineN200

typedefstruct

{intkey[5];

}score;

scoresr[N];

voidMerge(scoreR[],intlow,intm,inthigh,intkeynum)

{//将两个有序的R[low..m)和R[m+1..high]归并成一个有序的R[low..high]

inti,j,k;

i=low,j=m+1,k=0;

score*R1;

R1=(score*)malloc((high-low+1)*sizeof(score));

//临时申请空间

if(!R1)

return;

//申请空间失败

while(i<=m&&j<=high)

//两子文件非空时取较大者复制到R1[k]上

{if(R[i].key[keynum]>=R[j].key[keynum])

R1[k++]=R[i++];

elR1[k++]=R[j++];

}

while(i<=m)

//若第1个数组非空，则复制剩余记录到R1中

R1[k++]=R[i++];

while(j<=high)

//若第2个数组非空，则复制剩余记录到R1中

R1[k++]=R[j++];

for(k=0,i=low;i<=high;k++,i++)

R[i]=R1[k];

//归并完成后将结果复制回R[low..high]

}

voidMergeSort(scoreR[],intlow,inthigh,intkeynumber)

{//对R[low..high]进行二路归并排序

intmid;

if(low

{//区间长度大于1

mid=(low+high)/2;//分解

MergeSort(R,low,mid,keynumber);//递归地对R[low..mid]排序

MergeSort(R,mid+1,high,keynumber);//递归地对R[mid+1..high]排序

Merge(R,low,mid,high,keynumber);//组合，将两个有序区归并为一个有序区

}

}

intmain()

{inti,j,n,pepole;

printf("请输入总记录条数，和关键字的个数，并且以空格作为间隔符n");

scanf("%d%d",&pepole,&n);

printf("按记录顺序：以关键字优先次序从低到高产生随机关键字，最后一个关键字是总分由系统自动计算

n");

srand((unsigned)time(NULL));

for(i=0;i

{sr[i].key[n-1]=0;

for(j=0;j

{

sr[i].key[j]=rand()%100;

sr[i].key[n-1]=sr[i].key[n-1]+sr[i].key[j];

printf("%4d",sr[i].key[j]);

}

printf("%4d",sr[i].key[n-1]);

printf("n");

}

for(i=0;i

MergeSort(sr,0,pepole-1,i);

printf("n排序结果为：n");

for(i=0;i

{for(j=0;j

printf("%3d",sr[i].key[j]);

printf("n");

}

system("pau");

return0;

}