如何用指针数组实现单字符串字符排序与字符串列表排序？

问题描述 #

需要编写C程序实现两个功能：

• 对单个字符串内的字符按顺序排序
• 对字符串列表按字母顺序排序

目前已完成字符串列表排序，但单个字符串的字符排序功能缺失。当前代码如下：

#include<stdio.h>    
#include<string.h>   
#include<ctype.h>   
#include<stdlib.h> 
 
#define MAX_STRING_LENGTH 20  
#define TOTAL_STRING 10  

int main()    
{    
    int wordNum,i,j;  
    char *pointer[MAX_STRING_LENGTH];   
    char p, *strlist;  

    printf("How many words will you enter (must be at most 21):");  
    scanf("%d", &wordNum);  
    getchar();  
    printf("You will print %d words\n", wordNum);  
     
    if(wordNum<=MAX_STRING_LENGTH){  
        for(i=0;i<wordNum;i++){  
            j=0;  
            strlist=malloc(TOTAL_STRING*sizeof(char));  
            p=getchar();  
            while(p!='\n'){  
                *(strlist+j)=p;  
                j++;  
                p=getchar();  
            }  
            if(p=='\n'){  
                strlist[j]='\0';  
            }  
            pointer[i]=strlist;  
        }  
    }  
     
    for(i=0;i<wordNum-1;i++){  
        for(j=i+1;j<wordNum;j++){  
            if(strcmp(pointer[i], pointer[j])>0){  
                char *temp = pointer[i];  
                pointer[i] = pointer[j];  
                pointer[j] = temp;  
            }  
        }  
    }  
     
    printf("Words now sorted:\n");
 
    for(i=0;i<wordNum;i++){  
        printf("%s\n", pointer[i]);  
    }  
     
    printf("Bye!");  
       
    return 0;    
} 

输入示例：geeksforgeeks，预期输出：eeeefggkkorss

解决方案 #

1. 实现单个字符串字符排序函数 #

添加基于qsort的字符排序函数（比手动实现冒泡排序更高效）：

// qsort所需的字符比较函数，按ASCII值排序
int compareChars(const void *a, const void *b) {
    return *(const char *)a - *(const char *)b;
}

// 对单个字符串内的字符排序
void sortStringChars(char *str) {
    qsort(str, strlen(str), sizeof(char), compareChars);
}

2. 在程序中调用排序函数 #

在输入每个字符串后立即调用字符排序函数，同时添加长度检查避免内存越界：

if(wordNum<=MAX_STRING_LENGTH){  
    for(i=0;i<wordNum;i++){  
        j=0;  
        strlist=malloc(TOTAL_STRING*sizeof(char));  
        p=getchar();  
        while(p!='\n'){  
            *(strlist+j)=p;  
            j++;  
            // 防止超出单个字符串的内存范围
            if(j >= TOTAL_STRING - 1) break;
            p=getchar();  
        }  
        strlist[j]='\0';  
        // 对当前字符串的字符排序
        sortStringChars(strlist);
        pointer[i]=strlist;  
    }  
}  

3. 修正原代码潜在问题 #

• 宏定义命名优化：将MAX_STRING_LENGTH改为MAX_STRINGS（表示最多输入的字符串数量），TOTAL_STRING改为MAX_STRING_LEN（表示单个字符串的最大长度），避免混淆。
• 添加内存释放代码，避免内存泄漏。

修改后的完整代码 #

#include<stdio.h>    
#include<string.h>   
#include<ctype.h>   
#include<stdlib.h> 
 
#define MAX_STRINGS 20  
#define MAX_STRING_LEN 10  

// 字符比较函数，供qsort使用
int compareChars(const void *a, const void *b) {
    return *(const char *)a - *(const char *)b;
}

// 排序单个字符串内的字符
void sortStringChars(char *str) {
    qsort(str, strlen(str), sizeof(char), compareChars);
}

int main()    
{    
    int wordNum,i,j;  
    char *pointer[MAX_STRINGS];   
    char p, *strlist;  

    printf("How many words will you enter (must be at most 21):");  
    scanf("%d", &wordNum);  
    getchar();  
    printf("You will enter %d words\n", wordNum);  
     
    if(wordNum<=MAX_STRINGS){  
        for(i=0;i<wordNum;i++){  
            j=0;  
            strlist=malloc(MAX_STRING_LEN*sizeof(char));  
            p=getchar();  
            while(p!='\n'){  
                *(strlist+j)=p;  
                j++;  
                // 防止超出单个字符串的内存范围
                if(j >= MAX_STRING_LEN - 1) {
                    break;
                }
                p=getchar();  
            }  
            strlist[j]='\0';  
            // 对当前字符串的字符排序
            sortStringChars(strlist);
            pointer[i]=strlist;  
        }  
    }  
     
    // 对字符串列表按字母顺序排序
    for(i=0;i<wordNum-1;i++){  
        for(j=i+1;j<wordNum;j++){  
            if(strcmp(pointer[i], pointer[j])>0){  
                char *temp = pointer[i];  
                pointer[i] = pointer[j];  
                pointer[j] = temp;  
            }  
        }  
    }  
     
    printf("Words now sorted:\n");
 
    for(i=0;i<wordNum;i++){  
        printf("%s\n", pointer[i]);  
    }  

    // 释放malloc的内存，避免内存泄漏
    for(i=0;i<wordNum;i++){
        free(pointer[i]);
    }
     
    printf("Bye!");  
       
    return 0;    
} 

补充说明 #

• 若需要支持更长的单个字符串，修改MAX_STRING_LEN的值即可。
• 如果需要不区分大小写的字符排序，修改compareChars函数：

  int compareChars(const void *a, const void *b) {
      char c1 = tolower(*(const char *)a);
      char c2 = tolower(*(const char *)b);
      return c1 - c2;
  }
  

内容的提问来源于stack exchange，提问作者Aaron