结构体排序 - CSDN


结构体数组排序
由题引入
想法
qsort()函数
strcmp()函数
最终代码
奇妙错误

由题引入


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-- 用来比较两个元素的函数，即函数指针（回调函数）
回调函数：就是一个通过函数指针调用的函数。如果把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，就说这是回调函数。¹
compare函数:²

标准，qsort函数需要被告知一个规则，什么是大什么是小。

通过编写比较函数可以为函数qsort提供这些信息。

当给定两个指向数组元素的指针p和q时，比较函数必须返回一个整数。

如果* p小于* q,那么返回的数为负数;如果* p等于* q,那么返回0。如果* p大于* q,返回正数。
strcmp()函数
还有对字符串数组的排序，可使用strcmp函数。（之前有试过自己用字符串数组首元素地址所对应的空间中字母的ASC||值比较，未成功）
函数原型：

int strcmp(const char *s1,const char *s2);
规则：³

当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 0


Sample 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，看控制台输出错误数据看了半天没发现）




百度百科 ↩︎

【C/C++】qsort函数的使用方法和细节 ↩︎

百度百科 ↩︎
收起