学生的记录由学号和成绩组成,N名学生的数据已放入主函数中的结构体数组s中,请编写函数fun,其功能是:按分数降序排列学生的记录,高分在前,低分在后。注意:部分源程序在文件PROG1.C中。请勿改动主函...
注意:部分源程序在文件PROG1.C中。
请勿改动主函数main和其它函数中的任何内容,仅在函数fun的花括号中填入你编写的若干语句。
参考解析: 【参考答案】
void fun(STREC a[])
{
int i,j;
STREC t;
for(i=1;i<N;i++) /*用冒泡法进行排序,进行N-1次比较*/
for(j=0;j<N-1;j++) /*在每一次比较中要进行N-1次两两比较*/
if(a[j].s<a[j+1].s)
{t=a[j];a[j]=a[j+1];a[j+1]=t;} /*按分数的高低排列学生的记录,高分在前*/
}
【考点分析】
本题考查:排序算法;结构体类型。
【解题思路】
对N个数进行排序的算法很多,其中最简单的排序算法是冒泡算法。利用双层for循环嵌套和一个if判断语句来实现,外层循环用来控制需比较的轮数,内层循环用来控制两两比较。
【解题宝典】
冒泡法算法思路:如果有N个数,则要进行N-1次比较,在每一次比较中要进行N-1次两两比较(这种算法较好理解但不是最好的)。所谓两两比较就是从头到尾依次将相邻两个数进行比较,并将其中较大的数放在前或在后(若要求从小到大排序,则大的数要放在后面,反之对调),即两两比较后这两个数要形成题中所要求的顺序。由于总是从头到尾进行比较,第1轮比较结束后,最大(或最小)数肯定在最后,第2轮比较结束后,次最大(或次最小)数肯定在倒数第2个,依次类推,所以进行第1轮比较时必须比较到最后一个数,而进行第2轮比较时只要比较到倒数第2个数,进行第i轮比较时只需比较到第N-i-1个数即可(这种算法较难理解,但它是最好的)。
选择法算法思路:如果有N个数,则从头到倒数的第2个数逐个向后移动,每移动1个数总是对其后面的所有数进行搜索,并找出它们的最大(或最小)数,然后与该数进行比较,若大于(或小于)该数则进行交换,交换后再移动到下一个数,依次交换到结束。此外,选择法还可用如下思路:如果有N个数,则从头到倒数第2个数逐个移动,每移动一个数总是将这个数与其后的所有数进行两两比较,在比较时按顺序将进行比较的这两个数排序(即交换)。
插入法算法思路:先对前两个数进行排序。然后把第3个数插入到前两个数中,插入后前3个数依然有序;再把第4个数插入到前3个数中,插入后前4个数依然有序;依次插完所有的数。具体执行方式(假设从小到大排序):从第2个数开始往后逐个走动直到最后,每走到1个数总是将该数(先将其存到1个临时变量中)与前面的数进行比较(比较的顺序总是从后往前进行),在比较时只要发现该数比被比较的数小,就将被比较的数往后移1位,然后再与前1个数进行比较,直到发现该数比被比较的数大或已比较到头(即第1个数的前面),并将该数存入当前被比较数的后1位(存储空间)。
例如,整型一维数组a中有N个元素,要求将其按从小到大排序。注意元素下标是从0开始的。
冒泡法:
for(i=1;i<N;i++)
for(j=0;j<N-1;j++)
if(a[j]>a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
选择法:
for(i=0;i<N-1;i++)
{
p=i;
for(j=i+1;j<N;j++)
if(a[p]>a[j]) p=j;
if(p!=i)
{t=a[i];a[i]=a[p];a[p]=t;}
}
插入法:
for(i=1;i<N;i++)
{
t=a[i];
for(j=i-1;a[j]>t&&j>=0;j--)
a[j+1]=a[j];
a[j+1]=t;
}