数据结构与算法之桶排序
2017-07-17 本文已影响0人
LiChangBao
问题:现在分别有 5 个人的名字和分数:huhu 5 分、haha 3分、xixi 5 分、hengheng 2 分和 gaoshou 8 分。请按照分数从高到低,输出他们的名字。
上面的问题不适合使用桶排序,适合使用冒泡排序来解决。看完桶排序后,经过一番YY,总算给实现,不过实现的实在是有些.....
代码如下:
#include<stdio.h>
#include<string.h>
struct student{
char name[15];
int score;
};
int main()
{
int i,j,k=0;
int score;
int n;
char name[15];
struct student stu1[11];
struct student stu2[11];
int a[10];
//对结构体数组初始化
for(i=0;i<=10;i++)
{
strcpy(stu1[i].name,"null");
stu1[i].score = -1;//用于存储实际成绩
strcpy(stu2[i].name,"null");//其实对于结构体数组stu2来说,name部分对其并没有实际的用途!
stu2[i].score = 0;//用于存储某一成绩出现的次数
a[i] = -2;
}
printf("请输入参与排序的学生人数:");
scanf("%d",&n);
printf("请分别输入待排序学生的姓名和成绩:\n");
for(i=0;i<n;i++)
{
scanf("%s %d",&name,&score);
strcpy(stu1[i].name,name);
stu1[i].score = score;
stu2[score].score++;//这条代码很关键哦(桶排序从这里开始)
}
//桶排序核心算法
for(i=0;i<=10;i++)
{
for(j=1;j<=stu2[i].score;j++)
{
a[k] = i;//把排好序的成绩存放在a数组中
k++;
}
}
printf("使用桶排序之后:\n");
for(i=0;i<=10;i++)
{
for(j=0;j<=10;j++)
{
if(a[i]==stu1[j].score)//因为结构体数组stu1中的学生姓名和成绩是一一对应的,故此处找到对应成绩就等于找到其对应的学生姓名了。
{
printf("%s %d\n",stu1[j].name,a[i]);
strcpy(stu1[j].name,"null");
stu1[j].score = -1;
}
}
}
return 0;
}