题解 第三章排序与查找| #小白鼠排队#

法1:

使用常规的qsort方法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static const int CharNum=10;

typedef struct Rat
{
    int W;
    char C[CharNum];
}Rat;

int cmp(const void *a,const void *b)
{
    return (*(Rat*)a).W<(*(Rat*)b).W;
}

int main()
{
    int Num;
    scanf("%d",&Num);
    Rat R[Num];
    for(int i=0;i<Num;i++)
        scanf("%d%s",&R[i].W,R[i].C);
    
    qsort(R,Num,sizeof(Rat),cmp);
    
    for(int i=0;i<Num;i++)
        printf("%s\n",R[i].C);
    
    return 0;
}

法2:

一种巧妙的解法

将为整数的重量,看做二维数组的行数

将对应的重量,存入对应的行中

只需要从大行,遍历到小行,输出不为空的行即可

但是缺点就是,不能有两个同样重量的,也不能有过于巨大的重量存在

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static const int CharNum=10;

typedef struct Rat
{
    int W;
    char C[CharNum];
}Rat;

int cmp(const void *a,const void *b)
{
    return (*(Rat*)a).W<(*(Rat*)b).W;
}

int main()
{
    int Num;
    scanf("%d",&Num);
    Rat R[Num];
    for(int i=0;i<Num;i++)
        scanf("%d%s",&R[i].W,R[i].C);
    
    qsort(R,Num,sizeof(Rat),cmp);
    
    for(int i=0;i<Num;i++)
        printf("%s\n",R[i].C);
    
    return 0;
}