按字母顺序对字符串数组进行快速排序

Question

我正在尝试使用qsort函数对从文件中读取的字符串数组进行按字母顺序排序。以下是我的代码：

#include<stdio.h>
#include<stdlib.h>
#include<io.h>

#define MAXCHAR 256


int main(int argc, char **argv){
    char tempList[MAXCHAR][MAXCHAR];
    char reader[MAXCHAR];
    FILE* fp;
    int i;
    char *n;
    int index = 0;
    if(argc != 2){
        printf("too few arguments\n");
        exit(-1);
    }

    fp=fopen(argv[1], "r");
    if(fp == NULL){
        printf("failed to open file\n");
        exit(-1);
    }
    while(!feof(fp)){
        fgets(reader, MAXCHAR, fp);
        n = strchr(reader, '\n');
        if(n != NULL){
            *n = '\0';
        }
        strcpy(tempList[index], reader);
        index++;
    }
    index--;
    for(i=0; i<index; i++){
        printf("%s\n", tempList[i]);

    }
    qsort(tempList, index, sizeof(char *), strcmp);

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

当我运行程序时，列表根本没有被排序。我也尝试了在这个网站上发布的方法来解决类似的问题，但它们都给了我分段错误。代码有什么问题吗？

以下是txt文件内容的一部分。它是一个包含40个名称的列表：

Liam
Alexander
Mia
Noah
Emma
William
Charlotte
Charlotte
Mason
William
Ethan
Ethan
Liam
Alexander
Liam
Sophia
Emily
Mason
Alexander

- NewbieProgrammer

---

可能与问题无关，但是为什么“while ( !feof (file) )”总是错误的呢？ - Eugene Sh.

你得到了什么输出？ - Eugene Sh.

我建议使用while(fgets(reader, MAXCHAR, fp) != NULL)代替feof。 - Weather Vane

同时在名称长度空间和名称数量上使用MAXCHAR是非常不好的做法 - 这可能会在使用MAXCHAR时导致混淆。 - Weather Vane

Answer 1

你有一个真正的数组，而不是一个char*类型的数组。数组不是指针。qsort函数预期对正在排序的序列中元素的步长进行排序。因为你声明的序列是：

char tempList[MAXCHAR][MAXCHAR];

适当的元素大小是较小元素大小。在这种情况下，您有一个大小为MAXCHAR的char数组大小为MAXCHAR（数组的数组）。

因此，以下内容是错误的：

qsort(tempList, index, sizeof(char *), strcmp);
// wrong size ==============^^^^

每个元素的大小应为：

qsort(tempList, index, sizeof tempList[0], strcmp);
// correct size ==============^^^^

您的程序中还有其他问题最终会让您感到沮丧，在您的问题下方有一般性的评论，但这是导致排序无法正确工作的根本问题。下面是一个重新设计过的程序版本，解决了大部分问题：

更新的源代码

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

#define MAXCHAR 256

/* properly declared for compatibility with qsort */
static int cmp_str(const void *lhs, const void *rhs)
{
    return strcmp(lhs, rhs);
}

/* main entrypoint */
int main(int argc, char **argv)
{
    char tempList[MAXCHAR][MAXCHAR];
    FILE* fp;
    size_t i, index = 0;

    if(argc != 2)
    {
        printf("too few arguments\n");
        return EXIT_FAILURE;
    }

    fp=fopen(argv[1], "r");
    if(fp == NULL)
    {
        perror(argv[1]);
        return EXIT_FAILURE;
    }

    while(index < MAXCHAR && fgets(tempList[index], sizeof(*tempList), fp) != NULL)
    {
        char *n = strchr(tempList[index], '\n');
        if(n != NULL)
            *n = 0;
        if (*(tempList[index])) /* don't insert blank lines */
            ++index;
    }

    for(i=0; i<index; i++)
        printf("%s\n", tempList[i]);
    fputc('\n', stdout);


    qsort(tempList, index, sizeof tempList[0], cmp_str);

    for(i=0; i<index; i++)
        printf("%s\n", tempList[i]);

    return EXIT_SUCCESS;
}

未经测试，但应该非常接近。

祝你好运。

- WhozCraig

---

谢谢！它有效！不过有几个问题：1）我听说在if（），for（），while（）等语句后不加大括号是一种不好的做法，但你（和许多其他程序员）似乎仍在使用它。当我听到这是一种不好的做法时，我是被误导了吗？2）EXIT_FAILURE和EXIT_SUCCESS是否与exit（-1），exit（0）相同？这些关键字是否属于< stdlib.h >的一部分？3）我需要<io.h>（我认为在Mac上是<unistd.h>）来进行文件读写吗？4）size_t是int的另一种写法吗？ - NewbieProgrammer

1. 这是一个极具个人观点的问题，在两个阵营中都有利弊。但你应该注意适当的间距和缩进也很重要。
2. 它们被标准定义为适合您的平台。这就是我使用它们的原因。
3. 此程序使用所有标准库函数，无需使用特定于Unix或Mac的头文件。
4. size_t 也被标准定义为与 sizeof 等兼容的无符号类型。请在此处了解更多关于它及其典型用法的信息。

- WhozCraig

Answer 2

qsort(tempList, index, sizeof(char *), strcmp);中的 size 值是错误的。 应该是 qsort(tempList, index, sizeof(*tempList), strcmp);。

- Robert Jacobs

---

在这种情况下，字符串的数量与字符串长度MAXCHAR相同。最好按照@itsnotmyrealname的回答，将sizeof(*tempList)传递给qsort。然后，如果您更改其中一个数组大小，这将避免任何混淆。 - Weather Vane

由于您已经编辑了答案，我想指出sizeof(*tempList)与@WhozCraig发布的sizeof tempList[0]是相同的。 - Weather Vane

Answer 3

我已经尝试修复你的代码。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<io.h>    it's not standart


#define MAXCHAR 256

//  I implement the function because the warning is that
//  Incompatible pointer types passing 'int
//  (const char *, const char *)' to parameter of type
//  'int (*)(const void *, const void *)'

//  Already qsort() prototype is

// void qsort(void* ptr, size_t count, size_t size,
// int (*comp)(const void*, const void*));

// I think that the warning can be ignored strcmp also can be used

int myCompare(const void* a, const void* b)
{
    const char* aa = (const char*)a;
    const char* bb = (const char*)b;
    return strcmp(aa, bb);
}

int main(int argc, char **argv){
    char tempList[MAXCHAR][MAXCHAR];
    char reader[MAXCHAR];
    FILE* fp;
    int i;
    char *n;
    int index = 0;
    if(argc != 2){
        printf("too few arguments\n");
        exit(-1);
    }

    fp=fopen(argv[1], "r");
    if(fp == NULL){
        printf("failed to open file\n");
        exit(-1);
    }
    while(fgets(reader, MAXCHAR, fp) != NULL){ // !feof is not recommended search why

        n = strchr(reader, '\n');
        if(n != NULL){
            *n = '\0';
        }
        strcpy(tempList[index], reader);
        index++;
    }

    /*
    printf("%lu\n",sizeof(reader));     //256
    printf("%lu\n",sizeof(*reader));    //1
    printf("%lu\n",sizeof(*tempList));  //256
    printf("%lu\n",sizeof(**tempList)); //1
    */

    for(i=0; i<index; i++){
        printf("%s\n", tempList[i]);

    }
    qsort(tempList, index, sizeof(*tempList), myCompare);
    printf("\n\nAfter sorting\n\n");
    for(i=0; i<index; i++){
        printf("%s\n", tempList[i]);
    }
}

- Soner from The Ottoman Empire

---

谢谢您的建议，我已经添加为注释 @WeatherVane - Soner from The Ottoman Empire

MSVC没有关于传递给qsort函数的参数发出警告。 - Weather Vane

WhozCraig的回答更好。它解释了实际问题（二维字符数组与字符指针数组之间的区别）。这个答案对qsort的参数做出了正确的更改，但没有在任何地方提到这个更改。 - Peter Cordes

通过查看我编辑后的代码中的注释，可以推断出实际问题的逻辑。@PeterCordes - Soner from The Ottoman Empire

一个需要修复代码的人不应该直接复制粘贴正确的代码。我认为这个人应该仔细查看代码（注释等），而不是直接复制。我这样做是有原因的。否则，我也可以直接写出来。@PeterCordes - Soner from The Ottoman Empire