-
结构体排序
2021-04-11 14:02:42结构体排序题目相关由题引入
C=1,结构体一级排序,C=2,C=3对结构体二级排序。
AC代码详解博客站内很多,在此记录一下我遇到的问题。(没错,这是一篇伪题解博客)想法
看到题后,数据储存第一想法是单链表存储,排序时就有两种方法,交换结点指针,或者交换结点内容。这两种方法我都不熟练的情况下,还担心了自己写的排序模块会不会时间过长,想到了用C语言<stdlib.h>库函数qsort() 。
qsort函数对数组元素进行排序,于是数据存储就换成了结构体数组。(其实可以把链表元素遍历一遍,存入数组进行排序,输出排序后的数组。)qsort()函数
函数原型:
void qsort(void *base,size_t nitems,size_t size,int (*compare)(const void *,const void *))参数
base-- 指向要排序的数组的第一个元素的指针。
nitems-- 由 base 指向的数组中元素的个数。
size-- 数组中每个元素的大小,以字节为单位。
compare-- 用来比较两个元素的函数,即函数指针(回调函数)回调函数:就是一个通过函数指针调用的函数。如果把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,就说这是回调函数。1
compare函数:2
标准,qsort函数需要被告知一个规则,什么是大什么是小。
通过编写比较函数可以为函数qsort提供这些信息。
当给定两个指向数组元素的指针p和q时,比较函数必须返回一个整数。
如果* p小于* q,那么返回的数为负数;如果* p等于* q,那么返回0。如果* p大于* q,返回正数。strcmp()函数
还有对字符串数组的排序,可使用strcmp函数。(之前有试过自己用字符串数组首元素地址所对应的空间中字母的ASC||值比较,未成功)
函数原型:
int strcmp(const char *s1,const char *s2);规则:3
当s1<s2时,返回为负数;
当s1=s2时,返回值= 0;
当s1>s2时,返回正数。
即:两个字符串自左向右逐个字符相比(按ASCII值大小相比较),直到出现不同的字符或遇’\0’为止。如:
1.“A”<“B”
2.“A”<“AB”
3.“Apple”<“Banana”
4.“A”<“a”
5.“compare”<“computer”源码:
int strcmp(const char *str1,const char *str2) { while(*str1 == *str2) { assert((str1 != NULL) && (str2 != NULL)); if(*str1 == '\0') return 0; str1++; str2++; } return *str1 - *str2; }
模拟算法:
int strcmp(const char * src, const char * dst) { int ret = 0 ; while(!(ret=*src-*dst) && *dst) //相等且没有结束 ++src; ++dst; return( ret ); }
最终代码
没有AC,是TLE。在编译器上样例都对,但是超时。
Sample Input
3 1
000007 James 85
000010 Amy 90
000001 Zoe 60
4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98
4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90
0 0Sample Output
Case 1:
000001 Zoe 60
000007 James 85
000010 Amy 90
Case 2:
000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60
Case 3:
000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90#include <stdio.h> #include <stdlib.h> #include <string.h> struct stu { int id; char s[10]; int grade; }p[1000]; void sortid (stu* q,int n); void sorts (stu* q,int n); void sortgrade (stu* q,int n); int main() { int n,c; int cnt = 0; while (scanf("%d %d",&n,&c) && n) { int i=0; cnt++; for (i = 0 ; i<n ; i++) { scanf("%d %s %d",&p[i].id,p[i].s,&p[i].grade); } printf("Case %d:\n",cnt); switch(c) { case 1:{ sortid (p,n); break; } case 2:{ sorts (p,n); break; } case 3:{ sortgrade (p,n); break; } } } return 0; } int cmp(const void *a,const void *b) { return (*(stu *)a).id - (*(stu *)b).id; } int cmp2(const void *a,const void *b) { if(strcmp((*(stu *)a).s,(*(stu *)b).s)) { return strcmp((*(stu *)a).s,(*(stu *)b).s); } else return (*(stu *)a).id-(*(stu *)b).id; } int cmp3(const void *a,const void *b) { if((*(stu *)a).grade-(*(stu *)b).grade) { return (*(stu *)a).grade-(*(stu *)b).grade; } else return (*(stu *)a).id-(*(stu *)b).id; } void sortid (stu* q,int n) { qsort(q ,n ,sizeof(q[0]) ,cmp ); int i=0; for ( ; i<n ; i++) { printf("%06d %s %d\n",q[i].id,q[i].s,q[i].grade); } } void sorts (stu* q,int n) { qsort(q ,n ,sizeof(q[0]) ,cmp2 ); int i=0; for ( ; i<n ; i++) { printf("%06d %s %d\n",q[i].id,q[i].s,q[i].grade); } } void sortgrade (stu* q,int n) { qsort(q ,n ,sizeof(q[0]) ,cmp3 ); int i=0; for ( ; i<n ; i++) { printf("%06d %s %d\n",q[i].id,q[i].s,q[i].grade); } }
奇妙错误
- 一定理解题意再着手做题,case后是用例编号,不是排序编号
- 改代码时最好改了哪部分就把哪部分按代码顺序脑跑一遍,以防漏改漏增。(把while循环改成for循环后,控制循环的变量自增在for语句中出现了一次,在循环体里还有一次自增,改的时候没有删,导致一次循环,循环变量的循环步长是2,看控制台输出错误数据看了半天没发现)