c - 字符串插入排序程序

Question

刚开始学C，不是很了解。我们得到的程序告诉我们编写一个插入排序程序，该程序接受 20 个由空格分隔的字符串，然后按字母顺序排序并按顺序打印出来。这让我非常困惑，因为 C 没有 String 数据类型(至少据我所知)。字符串不就是字符数组吗？这是我得到的:

#include <stdio.h>
#include <string.h>
#define MAX_STRINGS 20

void InsertionSort(char list[]);

void main()
{
    int index;
    char strings[MAX_STRINGS];

    /* Get input */
    printf("Enter %s strings.\n", MAX_STRINGS);
    for (index = 0; index < MAX_STRINGS; index++)
    {
        char tempString[100];
        printf("Input string %d : ", index);
        scanf("%s", &tempString[0]);
        strings[index] = tempString;
    }

    InsertionSort(strings);

    printf("\nThe input set, in alphabetical order:\n");
    for (index = 0; index < MAX_STRINGS; index++)
    {
        printf("%s\n", strings[index]);
    }
}

void InsertionSort(char list[])
{
    int unsorted;
    int sorted;
    char unsortedItem;

    for(unsorted = 1; unsorted < MAX_STRINGS; unsorted++)
    {
        unsortedItem = list[unsorted];

        for (sorted = unsorted - 1; (sorted >= 0) && (list[sorted] >  unsortedItem); sorted--)
        {
            list[sorted + 1] = list[sorted];
        }
        list[sorted + 1] = unsortedItem;
    }
}

我对 C 和 C 语法完全陌生，我觉得它很困惑。该程序无法正常工作。它正在做的是它允许我输入 20 个字符串，但随后没有任何内容被排序并且它什么也没有打印出来。关于如何解决这个问题的任何想法？另外，是否知道如何将其输入到我键入单个句子并且每个字符串由空格分隔的位置？例如，如果我输入“我正在学习如何用 C 语言编程，但现在我不喜欢它”。那会给我 16 个字符串。 “我”、“我”、“学习”等。谢谢。

Answer 1

原代码的几个问题:

1) 不能使用=复制字符串；使用 strncpy为此(使用 = 仅分配指针)。

2) 字符串是字符数组；因此，字符串数组是字符数组的数组(因此您的 InsertionSort 签名是错误的)。请注意，C 字符串以 null 结尾，这仅意味着值为 0 的字节表示字符串的结尾(这非常重要，如果您忘记了其他所有内容，请记住这一点)。

3) %s 需要一个 char*；此行生成 UB:printf("Enter %s strings.\n", MAX_STRINGS);。您想要的是 %d(阅读 printf 格式说明符)。

4) 不能使用普通算术运算符比较字符串；那些比较指针。您需要使用 strcmp .

5) 你对插入排序算法的实现是错误的。

6) 标准允许main 声明的几个版本，char main 不是其中之一。在这种情况下，只需使用 int main。

这是您的代码的固定版本:

#include <stdio.h>
#include <string.h>
#define MAX_STRINGS 20
#define MAX_STRING_LEN 200

void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN]);

int main()
{
    int index;
    char strings[MAX_STRINGS][MAX_STRING_LEN];

    /* Get input */
    printf("Enter %d strings.\n", MAX_STRINGS);
    for (index = 0; index < MAX_STRINGS; index++)
    {
        printf("Input string %d : ", index);
        scanf("%199s", strings[index]);     // limit the width so we don't go past the buffer
        strings[index][sizeof(strings[index]) - 1] = '\0';
    }

    InsertionSort(strings);

    printf("\nThe input set, in alphabetical order:\n");
    for (index = 0; index < MAX_STRINGS; index++)
    {
        printf("%s\n", strings[index]);
    }
}

void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN])
{
    for (int i = 1; i < MAX_STRINGS; i++)
    {
        int j = i;

        while (j > 0 && strcmp(list[j - 1], list[j]) > 0)
        {
            char tmp[MAX_STRING_LEN];
            strncpy(tmp, list[j - 1], sizeof(tmp) - 1);
            tmp[sizeof(tmp) - 1] = '\0';

            strncpy(list[j - 1], list[j], sizeof(list[j - 1]) - 1);
            list[j - 1][sizeof(list[j - 1]) - 1] = '\0';

            strncpy(list[j], tmp, sizeof(list[j]));
            list[j][sizeof(list[j]) - 1] = '\0';

            --j;
        }
    }
}

一开始可能有点不知所措，但慢慢仔细阅读，你应该没有问题。

strncpy 或 scanf 之后的 = '\0' - 这些函数不会隐式以 null 终止字符串，因此我们有手动执行此操作 - 您可能会在不执行几次的情况下逃脱，但从长远来看，它最终会回到您身边。保持安全并养成习惯。

其他所有人:如果您发现任何错误，请告诉我 - 已经很晚了，我很累。

关于您在评论中的问题:

1) 为什么我在 for 循环中从 1 开始？
因为我稍后会引用 list[j - 1]，并且 j 设置为 i 的值(初始)，它可以不能小于 1 否则我们将使用负索引。参见 here算法的描述。

2) 如何读取整行字符串，包括空格？
最好的解决方案是使用 fgets .请注意，它有一个怪癖:它也在数组中存储了 \n 字符。如果您不想要它，则必须手动将其删除。

3) tmp 有什么用？
这只是一个临时的 char 缓冲区，因此我可以根据算法的要求交换这两个字符串。这并非特定于字符串，通常要交换两个变量，您需要第三个临时变量(除非您选择一些肮脏的 XOR hack)。