| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2619 人关注过本帖
标题:堆排序(多关键字)
只看楼主 加入收藏
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
结帖率:79.37%
收藏
已结贴  问题点数:20 回复次数:25 
堆排序(多关键字)
题目描述
某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学 排在前面,这样,每个学生的排序是唯一确定的。
任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前五名名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分) 是:
7 279

5 279
这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ,但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279

7 279
则按输出错误处理,不能得分。

输入格式
输入包含n+1行:

第1行为一个正整数n,表示该校参加评选的学生人数。

第2到n+1行,每行有3个用空格隔开的数字,每个数字都在O到100之间z第1行的3个数 字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为l~n (恰好是输入数据的行号减1)。

所给的数据都是正确的,不必检验。

输出格式
输出共有5行,每行是两个用空格隔开的正整数,依次表示前5名学生的学号和总分。

样例输入
【输入样例1】
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
【输入样例2】
8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
样例输出
【输出样例1】
6 265
4 264
3 258
2 244
1 237
【输出样例2】
8 265
2 264
6 264
1 258
5 258

我使用堆排序做这题,但是发生了一些问题:
#include <stdio.h>
#include <stdlib.h>
int chinese[10]={0},english[10]={0},math[10]={0},num[10]={0},total[10]={0},n;
void sift(int startPos,int endPos)
{
    int k=2*startPos;
    int temp_num=num[startPos];
    int temp_total=total[startPos];
    int temp_chinese=chinese[startPos];
    while(k<=endPos)
    {
        if(k<endPos)
        {
        if(total[k]<total[k+1])
        k++;
        else if(total[k]==total[k+1]&&chinese[k]<chinese[k+1])
        k++;
        else if(total[k]==total[k+1]&&chinese[k]==chinese[k+1]&&num[k]<num[k+1])
        k++;
        }
        if(temp_total>total[k])
        {
        total[startPos]=total[k];
        startPos=k;
        k=2*startPos;
        }
        else if(temp_total==total[k]&&temp_chinese>chinese[k])
        {
        total[startPos]=total[k];
        startPos=k;
        k=2*startPos;
        }
        else if(temp_total==total[k]&&temp_chinese==chinese[k]&&temp_num<num[k])
        {
        total[startPos]=total[k];
        startPos=k;
        k=2*startPos;
        }
        else break;
    }
    num[startPos]=temp_num;
    total[startPos]=temp_total;
    chinese[startPos]=temp_chinese;
}
void heap_sort(int n)
{
    int i,temp;
    for(i=n/2;i>=0;i--)
    sift(i,n);
    for(i=n-1;i>=0;i--)
    {
    temp=total[i]; total[i]=total[0]; total[0]=temp;
    temp=chinese[i];chinese[i]=chinese[0];chinese[0]=temp;
    temp=math[i];math[i]=math[0];math[0]=temp;
    temp=english[i];english[i]=english[0];english[0]=temp;
    temp=num[i];num[i]=num[0];num[0]=temp;
    sift(0,i-1);
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    scanf("%d %d %d",&chinese[i],&math[i],&english[i]);
    num[i]=i+1;
    total[i]=chinese[i]+math[i]+english[i];
    }
    heap_sort(n);
    for(i=4;i>=0;i--)
    printf("%d %d\n",num[i],total[i]);
    system("pause");
    return 0;
}
搜索更多相关主题的帖子: 关键字 奖学金 英语 
2011-01-28 10:39
刘定邦
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:687
专家分:1570
注 册:2010-9-21
收藏
得分:1 
学习学习....
2011-01-28 13:02
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
#include <stdio.h>
#include <stdlib.h>
int chinese[10]={0},english[10]={0},math[10]={0},num[10]={0},total[10]={0},n;
void sift(int startPos,int endPos)
{
    int k=2*startPos+1;
    int temp_num=num[startPos];
    int temp_total=total[startPos];
    int temp_chinese=chinese[startPos];
    while(k<endPos)
    {
        if(k<endPos)
        {
        if(total[k]<total[k+1])
        k++;
        else if(total[k]==total[k+1]&&chinese[k]<chinese[k+1])
        k++;
        else if(total[k]==total[k+1]&&chinese[k]==chinese[k+1]&&num[k]<num[k+1])
        k++;
        }
        if(temp_total>total[k])
        {
        total[startPos]=total[k];
        startPos=k;
        k=2*startPos+1;
        }
        else if(temp_total==total[k]&&temp_chinese>chinese[k])
        {
        total[startPos]=total[k];
        startPos=k;
        k=2*startPos+1;
        }
        else if(temp_total==total[k]&&temp_chinese==chinese[k]&&temp_num<num[k])
        {
        total[startPos]=total[k];
        startPos=k;
        k=2*startPos+1;
        }
        else break;
    }
    num[startPos]=temp_num;
    total[startPos]=temp_total;
    chinese[startPos]=temp_chinese;
}
void heap_sort(int n)
{
    int i,temp;
    for(i=n/2;i>=0;i--)
    sift(i,n);
    for(i=n-1;i>=0;i--)
    {
    temp=total[i]; total[i]=total[0]; total[0]=temp;
    temp=chinese[i];chinese[i]=chinese[0];chinese[0]=temp;
    temp=math[i];math[i]=math[0];math[0]=temp;
    temp=english[i];english[i]=english[0];english[0]=temp;
    temp=num[i];num[i]=num[0];num[0]=temp;
    sift(0,i);
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    scanf("%d %d %d",&chinese[i],&math[i],&english[i]);
    num[i]=i+1;
    total[i]=chinese[i]+math[i]+english[i];
    }
    heap_sort(n);
    for(i=0;i<5;i++)
    printf("%d %d\n",num[i],total[i]);
    system("pause");
    return 0;
}

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 11:04
点线面
Rank: 8Rank: 8
来 自:NO.-1
等 级:蝙蝠侠
帖 子:525
专家分:980
注 册:2011-1-3
收藏
得分:15 
#define M  //总人数
定义一个
struct student
{
  float chinese;
  float english;
  float math;
}score[M];

 . . .这样是不是清晰

小代码,大智慧
2011-01-29 11:17
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
但是我这个写得有什么问题呢?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 11:19
点线面
Rank: 8Rank: 8
来 自:NO.-1
等 级:蝙蝠侠
帖 子:525
专家分:980
注 册:2011-1-3
收藏
得分:0 
就是将你的int chinese[10]={0},english[10]={0},math[10]={0},num[10]={0},total[10]={0},n;
归成一个类,有助分析

小代码,大智慧
2011-01-29 11:24
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 6楼 点线面
为了避免元素太多以至于混乱,所以我先做一个小例子:
输入学号与成绩,成绩大的排到前面。如果将要交换的两个成绩相同,则学号小的排在前面。
输入:
6
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88
输出:
7231 84
3239 88
1001 88
1000 90
2390 95
1005 95


我将代码写出来了,但是有很多问题,一个是成绩不能成为有序排列,而且学号还会“张冠李戴”:

#include <stdio.h>
#include <stdlib.h>
void sift(int startPos,int endPos,int score[],int number[])
{
    int k=startPos*2+1,temp1,temp2;
    temp1=score[startPos];
    temp2=number[startPos];
    while(k<endPos)
    {
    if(k+1<endPos&&score[k]<score[k+1])k++;
    else if(k+1<endPos&&number[k]==number[k+1]&&number[k]>number[k+1])k++;
    if(temp1>score[k])
    {
    score[startPos]=score[k];
    startPos=k;
    k=startPos*2+1;
    }
    else if(score[k]==temp1&&number[k]>number[k+1])
    {
    score[startPos]=score[k];
    startPos=k;
    k=startPos*2+1;
    }
    else break;
    }
    score[startPos]=temp1;
    number[startPos]=temp2;
}
void heap_sort(int number[],int score[],int n)
{
    int i,temp;
    for(i=n/2;i>=0;i--)
    sift(i,n,score,number);
    for(i=n-1;i>=0;i--)
    {
    temp=number[i];number[i]=number[0];number[0]=temp;
    temp=score[i];score[i]=score[0];score[0]=temp;
    sift(0,i,score,number);
    }
}
int main()
{
    int number[10]={0},score[10]={0},n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d %d",&number[i],&score[i]);
    heap_sort(number,score,n);
    printf("\n");
    for(i=0;i<n;i++)
    printf("%d %d\n",number[i],score[i]);
    system("pause");
    return 0;
}

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 15:35
犬虫门心
Rank: 8Rank: 8
来 自:西安
等 级:蝙蝠侠
帖 子:209
专家分:753
注 册:2011-1-25
收藏
得分:0 
呵呵,这个问题有一个一揽子解决方案。我先去给我家女女打预防针,回来我跟你讨论!
提示:排序的本质是交换,那么交换的前提是什么呢?能不能一次性表述清楚呢?

当一名对得起学生学费的老师,一直是我的目标!我会更努力的!
2011-01-29 15:40
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 8楼 犬虫门心
您先把我写得堆排序单关键字看看吧,我现在还不知道自己写的对不对:https://bbs.bccn.net/thread-331587-2-1.html

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 15:45
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 8楼 犬虫门心
那当然有许多排序方法,但是现在我主要研究的是堆排序,所以才问这个问题的。

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-29 15:47
快速回复:堆排序(多关键字)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.101467 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved