精华内容
下载资源
问答
  • 结构体排序

    2021-04-11 14:02:42
    结构体排序题目相关

    由题引入

    浙大复试 hdoj1862
    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 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,看控制台输出错误数据看了半天没发现)

    1. 百度百科 ↩︎

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

    3. 百度百科 ↩︎

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,578
精华内容 3,031
关键字:

结构体排序