c - 如何按字母顺序对字符串数组进行排序(区分大小写，非标准排序规则)

Question

我需要一个c语言代码来对一些字符串进行排序，它应该区分大小写并且对于大小写相同的字母，小写必须在前。例如以下字符串的排序结果:

eggs
bacon
cheese
Milk
spinach
potatoes
milk
spaghetti

应该是:

bacon
cheese
eggs
milk
Milk
potatoes
spaghetti
spinach

我写了一段代码，但得到的结果是:

Milk
bacon
cheese
eggs
milk
potatoes
spaghetti
spinach

我不知道如何改进这个，我已经搜索了很多。谁能帮我解决这个问题？

#include <stdio.h>
#include <string.h>

int main(){
    char c;
    char name[20][10], temp[10];
    int count_name = 0;
    int name_index = 0;
    int i, j;

    while ((c = getchar()) != EOF){
        if (c == 10){
            name[count_name][name_index] = '\0';
            count_name++;
            name_index = 0;
        } else {
            name[count_name][name_index] = c;
            name_index++;
        }
    }

    for(i=0; i < count_name-1 ; i++){
        for(j=i+1; j< count_name; j++)
        {
            if(strcmp(name[i],name[j]) > 0)
            {
                strcpy(temp,name[i]);
                strcpy(name[i],name[j]);
                strcpy(name[j],temp);
            }
        }
    }

    for (i = 0; i < count_name; i++){
        printf("%s\n", name[i]);
    }
}

Answer 1

将相似的词放在一起...

对于单词列表，将“相同”单词组合在一起通常更有用(即使它们的大小写不同)。例如:

Keeping things together:          Simple "M after m":
------------------------          -------------------
mars                              mars
mars bar                          mars bar
Mars bar                          milk
milk                              milk-duds
Milk                              milky-way
milk-duds                         Mars bar
milky-way                         Milk
Milky-way                         Milky-way

如果你想像第一列那样排列单词，我提供了三种方法:

• 使用 strcasecmp()结合strcmp() .
• 使用 isalpha() 跟踪字符类型的单 channel 实现, tolower() , 和 isupper() .
• 利用整理表的单 channel 实现。

最后我讨论了两种选择:

• 使用整理表建立任意排序。
• 设置语言环境以使用基于语言环境的整理。

使用可用的库函数

如果可能的话，避免重新发明轮子。在这种情况下，我们可以使用 POSIX 函数 strcasecmp() 来实现。通过不区分大小写的比较查看它们是否相等，然后返回 strcmp()什么时候。

int alphaBetize (const char *a, const char *b) {
    int r = strcasecmp(a, b);
    if (r) return r;
    /* if equal ignoring case, use opposite of strcmp() result to get
     * lower before upper */
    return -strcmp(a, b); /* aka: return strcmp(b, a); */
}

(在某些系统上，不区分大小写的比较函数称为 stricmp() 或 _stricmp()。如果您无法使用，下面提供了实现。)

#ifdef I_DONT_HAVE_STRCASECMP
int strcasecmp (const char *a, const char *b) {
    while (*a && *b) {
        if (tolower(*a) != tolower(*b)) {
            break;
        }
        ++a;
        ++b;
    }
    return tolower(*a) - tolower(*b);
}
#endif

避免两次传递字符串

有时，现有功能的性能不够好，您必须采取其他措施来加快速度。以下函数在一次传递中以大致相同的方式进行比较，并且不使用 strcasecmp() 中的任何一个。或 strcmp() .但是，它将所有非字母字符视为小于字母。

int alphaBetize (const char *a, const char *b) {
    int weight = 0;
    do {
        if (*a != *b) {
            if (!(isalpha(*a) && isalpha(*b))) {
                if (isalpha(*a) || isalpha(*b)) {
                    return isalpha(*a) - isalpha(*b);
                }
                return *a - *b;
            }
            if (tolower(*a) != tolower(*b)) {
                return tolower(*a) - tolower(*b);
            }
            /* treat as equal, but mark the weight if not set */
            if (weight == 0) {
                weight = isupper(*a) - isupper(*b);
            }
        }
        ++a;
        ++b;
    } while (*a && *b);
    /* if the words compared equal, use the weight as tie breaker */
    if (*a == *b) {
        return weight;
    }
    return !*b - !*a;
}

使用此比较进行排序将保留milk和 Milk彼此相邻，即使列表包含 milk-duds .

使用整理表

这是一种从“配置”动态创建整理表的方法。它用于说明改变字符串比较方式的对比技术。

您可以将字母表中的字母与一种简单的表格进行比较，该表格描述了您希望字母(或除 NUL 字节以外的任何字符)具有的相对顺序:

const char * alphaBetical =
    "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";

根据这个顺序，我们可以创建一个查找表来查看两个字母应该如何相互比较。如果尚未首先完成，则以下函数初始化表，否则执行表查找。

int alphaBeta_lookup (int c) {
    static int initialized;
    static char table[CHAR_MAX+1];
    if (!initialized) {
        /* leave all non-alphaBeticals in their relative order, but below
           alphaBeticals */
        int i, j;
        for (i = j = 1; i < CHAR_MAX+1; ++i) {
            if (strchr(alphaBetical, i)) continue;
            table[i] = j++;
        }
        /* now run through the alphaBeticals */
        for (i = 0; alphaBetical[i]; ++i) {
            table[(int)alphaBetical[i]] = j++;
        }
        initialized = 1;
    }
    /* return the computed ordinal of the provided character */
    if (c < 0 || c > CHAR_MAX) return c;
    return table[c];
}

有了这个查找表，我们现在可以简化 alphaBetize() 的循环体比较功能:

int alphaBetize (const char *a, const char *b) {
    int ax = alphaBeta_lookup(*a);
    int bx = alphaBeta_lookup(*b);
    int weight = 0;
    do {
        char al = tolower(*a);
        char bl = tolower(*b);
        if (ax != bx) {
            if (al != bl) {
                return alphaBeta_lookup(al) - alphaBeta_lookup(bl);
            }
            if (weight == 0) {
                weight = ax - bx;
            }
        }
        ax = alphaBeta_lookup(*++a);
        bx = alphaBeta_lookup(*++b);
    } while (ax && bx);
    /* if the words compared equal, use the weight as tie breaker */
    return (ax != bx) ? !bx - !ax : weight;
}

我们可以让事情变得更简单吗？

使用整理表，您可以使用简化的比较功能创建许多不同的排序，例如:

int simple_collating (const char *a, const char *b) {
    while (alphaBeta_lookup(*a) == alphaBeta_lookup(*b)) {
        if (*a == '\0') break;
        ++a, ++b;
    }
    return alphaBeta_lookup(*a) - alphaBeta_lookup(*b);
}

使用相同的函数并通过修改 alphaBetical字符串，您几乎可以实现任何您想要的排序(字母顺序、反向字母顺序、元音在辅音之前等)。然而，将相似的单词放在一起的安排需要将大写单词与小写单词穿插在一起，而这只能通过忽略大小写的比较来实现。

请注意 simple_collating()上面的函数和alphaBetical我提供的字符串，Bacon会在milk之前来，但是Mars会去 milk和之前 Milk .

如果你想根据你的地区排序。

如果您想使用已经为您的语言环境定义的整理序列，您可以设置语言环境并调用整理比较函数:

/*
 * To change the collating locale, use (for example):
       setlocale(LC_COLLATE, "en.US");
 */
int iso_collating (const char *a, const char *b) {
    return strcoll(a, b);
}

现在，通过更改语言环境，排序顺序将基于标准化的整理顺序。