混合串排序

喜欢ヅ旅行 2022-05-17 07:04 113阅读 0赞

两个字符串（字符串1、字符串2）的大小比较，字符串可能既含有字符（a～z）又含有数字（0～9）。比较规则：  
(1)从左到右分离单纯的子字符串（全字符）和子数字串（全数字）进行比较。  
(2)如果被比较的都是子字符串，则可以调用strcmp比较子字符串大小。  
(3)如果被比较的都是子数字串，则根据值比较大小，如果值相等，则子数字串短的一方大（前面的0少）。  
(4)如果被比较的一边是子数字串，一边是子字符串，则子字符串大。  
不能用递归 测试例子，对字符串组B1，B01，B2，B11进行递增排序：输出应该是B01，B1，B2，B11。  
\#define MAX\_Length 50  
void SortString(char str\[\]\[MAX\_Length\],  size\_t numberOfString)

### 代码示例 ###

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <string.h>
    
    #define MAX_Length 50
    
    int isNum(char c)
    {
        if( (c>='0') && (c<='9') )
            return 1;
        return 0;
    }
    int getNum(char c)
    {
        if(isNum(c))
            return (c-'0');
        return -1;
    }
    int getAdd(const char * s, int * index)
    {
        int n=0;
        int total=0;
        n=getNum(s[*index]);
        while(n>=0)
        {
            total*=10;
            total+=n;
            (*index)++;
            n=getNum(s[*index]);
        }
        return total;
    }
    int cmpNum(const char * s1, const char * s2, int * p1, int * p2)
    {
        int index1=*p1,index2=*p2;
        int sum1=0,sum2=0;
        int len1=0,len2=0;
    
        sum1=getAdd(s1,p1);
        sum2=getAdd(s2,p2);
        
        //printf("%d\t%d\n",sum1,sum2);
    
        if(sum1==sum2)
        {
            len1=*p1-index1;
            len2=*p2-index2;
            return len2-len1;//length follows descending order
        }
        return sum1-sum2;//number follows ascending order
    }
    int cmp(const void * a, const void * b)
    {
        int i=0,j=0;
        int isNum1=0,isNum2=0;
        const char * s1=(const char * )a;
        const char * s2=(const char * )b;
        int ans=0;
        
        while(s1[i]!='\0' && s2[j]!='\0')
        {
            isNum1=isNum(s1[i]);
            isNum2=isNum(s2[j]);
            //printf("%s:i=%d\t%s:j=%d\n",s1,i,s2,j);
            //getchar();
    
            if(!isNum1 && isNum2)
                return 1;
            if(isNum1 && !isNum2)
                return -1;
            if(!isNum1 && !isNum2)
                if(s1[i]!=s2[i])
                    return s1[i]-s2[j];
            if(isNum1 && isNum2)
            {
                ans=cmpNum(s1,s2,&i,&j);
                if(ans!=0)
                    return ans;
                continue;
            }
            i++;
            j++;
        }
    
        if(s1[i]!='\0')
            return 1;
    
        if(s2[j]!='\0')
            return -1;
    
        return 0;
    }
    void SortString(char str[][MAX_Length], int numberOfString)
    {
        qsort(str, numberOfString, sizeof(char[MAX_Length]), cmp);
    }
    
    int main()
    {
        int i=0,END=15;
        char str[256][MAX_Length];
        
        FILE * fp=fopen("2.txt","r");
        //FILE * fout=fopen("out.txt","w");
        if(!fp)
            return -1;
    
        for(i=0;i<END;i++)
        {
            fgets(str[i], 1024, fp);
            //printf("%s\t%d\n",str[i],strlen(str[i]));
            str[i][strlen(str[i])-1]='\0';
        }
    
        SortString(str, END);
        for(i=0;i<END;i++)
            printf("%s\n",str[i]);
    
        return 0;
    
    }

1.  使用 qsort 将问题简化为两个字符串的对比  
2. 使用strpbrk将字符串分离  
3.  数字字符串的对比（如不考虑越界或用atoi）  
尽量使用C库API和现成的代码  
考虑字符串的越界问题

#include <stdio.h>
    #include <string.h>
    #include <assert.h>
    
    #define MAX_Length 50
    
    void SplitString(const char* p, char strPart[MAX_Length], char numPart[MAX_Length])
    {
    	const char * pNumPart = strpbrk(p, "0123456789");
    
    	assert(p != NULL);
    	if(pNumPart != NULL)
    		strcpy(numPart, pNumPart);
    	
    	strncpy(strPart, p, strlen(p) - strlen(numPart));
    }
    /*防止数字越界，如果用atoi也可以*/
    int CompareNumer(const char numPart1[MAX_Length], const char numPart2[MAX_Length])
    {
    	const char * p1 = numPart1;
    	const char * p2 = numPart2;
    
    	while(*p1 == '0')
    	{
    		++p1;
    	}
    
    	while(*p2 == '0')
    	{
    		++p2;
    	}
    
    	if(strlen(p1) != strlen(p2))
    	{
    		return strlen(p1) - strlen(p2);
    	}
    
    	while(*p1)
    	{
    		if(*p1 != *p2)
    			return *p1 - *p2;
    		++p1;
    		++p2;
    	}
    	
    	return strlen(numPart2) - strlen(numPart1);
    }
    
    int Compare(const char* p1, const char*p2)
    {
    	char strPart1[MAX_Length] = {0};	
    	char numPart1[MAX_Length] = {0};
    
    	char strPart2[MAX_Length] = {0};
    	char numPart2[MAX_Length] = {0};
    
    	int result = 0;
    	SplitString(p1, strPart1, numPart1);
    	SplitString(p2, strPart2, numPart2);
    
    	result = strcmp(strPart1, strPart2);
    
    	if(result == 0)
    	{
    		result = CompareNumer(numPart1, numPart2);
    	}	
    	return result;
    }
    
    void SortString(char str[][MAX_Length],  size_t numberOfString)
    {     
    	qsort(str, numberOfString, MAX_Length, Compare);
    }
    
    void Test_Compare()
    {
    	assert(Compare("B", "A") > 0 );
    
    	assert(Compare("A2", "013") > 0 );
    
    	assert(Compare("A2", "B1") < 0 );
    	assert(Compare("A2", "Bcd1") < 0 );
      
    
    	assert(Compare("B1", "B01") > 0 );
    	assert(Compare("B1", "B2") < 0 );
    	
    	assert(Compare("B2", "B11") < 0 );
    }
    
    void PrintfStr(const char str[][MAX_Length],  size_t numberOfString)
    {
    	size_t i = 0;
    	for (i = 0; i < numberOfString; ++i)
    		printf("%s\n", str[i]);
    }
    
    int main ()
    {
    	
    	char str[10][MAX_Length] = {0};
    	strcpy(str[0], "1234");
    	strcpy(str[1], "dfsdf");
    
    	strcpy(str[2], "^&*(()");
    
    	SortString(str,3);
    	PrintfStr(str,3);
    
    	strcpy(str[0], "B2");
    	strcpy(str[1], "B11");
    
    	strcpy(str[2], "B01");
    	strcpy(str[3], "B1");
    	strcpy(str[4], "1234567890123456789012345678901234567890123456789");
    
    	SortString(str,5);
    	PrintfStr(str,5);
    	
        return 0;
    }