排序算法更新了不应该的变量

Question

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

int get_index(char c);
string selectionSort(string arr, int n);

int main(int argc, string argv[])
{
    string key = argv[1];
    int str_len = strlen(key);
    string sorted = selectionSort(key, str_len);
}

string selectionSort(string arr, int n)
{

    int i, j, min_idx;
    for (i = 0; i < n - 1; i++)
    {
        min_idx = i;
        for (j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min_idx])
            {
                min_idx = j;
            }
        }
        char x = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = x;
    }
    return (string) arr;
}

我已经有了这个c代码，并且selectionSort函数正在更新关键变量，我该怎么做才能使关键变量保持不变？

我尝试复制密钥，但即使我将其设置为常量，它也会发生变化。

Answer 1

弦乐

请记住，在 C 中，字符串只是一个字符数组。

<cs50.h>

会用

typedef char * string;

向您隐藏这一点，并且它会自动为您提供

free()

的字符串。虽然方便，但恕我直言，这对您的理解有点损害。

如果将代码中

string

的所有实例更改为

char *

，您将立即开始看到一些可能出错的地方。

数组

数组不是 C 中的一等公民。如果将数组传递给函数，它实际上会作为指针传递到数组中的第一个元素 - 不会创建数组的副本。然后该函数可以对数组数据执行任何它想要的操作。

用额外变量命名事物

就可读性而言，为更复杂的事物提供更简单的名称可能很有用。拥有这样的别名会很有用。但要小心，这样做很可能会掩盖你应该知道的事情。

这会发生在

char * key = argv[1]

上。如前所述，您实际上并没有在任何地方获得

argv[1]

字符串（数组）的副本，而只是指向它的指针。 （您将获得指向 argv[1] 指针所指向的字符串数组的第一个元素的

pointer

的副本。清晰如泥，对吧？）

同样，收集变量中的数组长度以简单地在其他地方使用它也是多余的，并且会让像未来的自己这样的人怀疑该变量中是否有 modified 值而不是 actual 数组的当前长度。

因此，当值别名不能显着阐明代码时，请避免使用值别名。

选择排序

排序算法通常会修改其参数列表——它们通常不会返回新列表。

最好假设您的选择排序也是如此。据我们所知——字符串是数组，数组作为指向元素的指针传递给函数，不创建数组的副本并且函数修改参数数组——我们可以看到排序实际上修改了

argv[1][]

数组！

原型 > 主要 > 函数 == Evil

我一直不明白，甚至在 1998 年 C 标准化之前，为什么人们喜欢列出函数原型，然后

main()

，然后是函数。这是一种“古老”的布局，只会引发问题并增加精神压力。 更喜欢简单地按顺序定义您的函数，并将

main()

最后。这将使您的生活变得更加轻松。

块顶部的局部变量

这

曾经

是一项要求，再次，古代。现代 C 不要求您在词法块中的任何语句之前声明变量。 更愿意在尽可能靠近使用变量的地方声明变量。例如，在

for

语句中，在初始化部分声明它。将其移出循环的唯一原因是如果在循环终止后

使用它。

应用知识！

让我们把它们放在一起：

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

void selectionSort(char * arr, int n)
{
    for (int i = 0;  i < n - 1;  i++)
    {
        int min_idx = i;
        for (int j = i + 1;  j < n;  j++)
        {
            if (arr[j] < arr[min_idx])
            {
                min_idx = j;
            }
        }
        char x = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = x;
    }
}

int main(int argc, char * argv[])
{
    // The string to sort is passed as first argument to the program
    if (argc != 2) return 1;

    printf("given:  \"%s\"\n", argv[1]);
    selectionSort(argv[1], strlen(argv[1]));
    printf("sorted: \"%s\"\n", argv[1]);

    return 0;
}

田田！您的代码有效！可能值得您花时间查看该选择排序以了解它的实际工作原理。提示：

i

计算数组中已排序元素的数量。

• 'j' 只是对数组中未排序的元素进行计数。

• min_idx
的命名不明确 — 它是数组的
• unsorted

   部分中最小元素值的索引。

  继续前进！它变得更容易！答应我！