c - 从 C 中的两个参数字符串中删除重复字符

Question

我正在尝试优化一个问题，我必须以相同的速度优化使其更具可读性。我的问题在于:

Allowed function: write.c, nothing else.

Write a program that takes two strings and displays, without doubles, the characters that appear in either one of the strings.

The display will be in the order characters appear in the command line, and will be followed by a \n.

如您所见，在 main 中，它将把两个参数字符串(argv[1] 和 argv[2])带入我们的函数(void remove_dup(char *str, char *str2) 使用 GCC 编译后。该临时数组将在检测到重复字符后保存该字符的 ASCII 值。例如，str1 = "hello " 和 str2 = "laoblc"。使用 write 函数，预期输出将是“heloabc”。

但是，GCC 正在提示，因为我有一个数组下标，其中的临时字符数组填充了字符串索引中的零。为了停止编译器提示，我必须将字符串索引转换为 int 以将 ASCII 值保存在临时数组中。这将是我们的检查器，它将根据字符的值确定字符串中是否存在重复项。再次重新编译，但这次使用警告标志:gcc -Wextra -Werror -Wall remove_dup.c。这是我得到的错误:

remove_dup:11 error: array subscript is of type 'char' [-Werror,-Wchar-subscripts]

           if (temp[str[i]] == 0)
                     ^~~~~~~

remove_dup:13 error: array subscript is of type 'char' [-Werror,-Wchar-subscripts]

                   temp[str[i]] = 1;
                        ^~~~~~~

remove_dup:21 error: array subscript is of type 'char' [-Werror,-Wchar-subscripts]

           if (temp[str2[i]]  == 0)
                   ^~~~~~~~

remove_dup.c:23 error: array subscript is of type 'char' [-Werror,-Wchar-subscripts]

                  temp[str2[i]] = 1;
                      ^~~~~~~~

现在我真正的问题是，如何才能拥有相同的时间效率，但不使用任何类型的转换到我的数组中？该程序以 O(m + n) 运行，其中 m 是我们的第一个字符串，n 是我们的第二个字符串。

这是代码:

void    remove_dup(char *str, char *str2)
{
    int temp[10000] = {0};
    int i;

    i = 0;
    while (str[i])
    {
        if (temp[(int)str[i]] == 0)
        {
            temp[(int)str[i]] = 1;
            write(1, &str[i], 1);
        }
        i++;
    }
    i = 0;
    while (str2[i])
    {
        if (temp[(int)str2[i]]  == 0)
        {
            temp[(int)str2[i]] = 1;
            write(1, &str2[i], 1);
        }
        i++;
    }
}

int main(int argc, char *argv[])
{
    if (argc == 3)
        remove_dup(argv[1], argv[2]);
    write(1, "\n", 1);
    return (0);
}

我希望我解释的逻辑结构足够清楚。我可能有语法错误，所以请耐心等待:)。

Answer 1

此处转换不会造成性能损失。

但是，根据经验，通常最好尽可能避免显式强制转换。例如，您可以通过更改来做到这一点:

   temp[(int)str[i]]

至:

   temp[+str[i]]

这将通过通常的算术转换来实现。

但是，您的代码还有另一个问题。您可能会问:为什么 gcc 会费心发出这样一个烦人警告消息？

一个答案是他们只是喜欢惹人厌。更好的猜测是，在大多数平台上 char 都是 signed - 请参阅 Is char signed or unsigned by default? --因此，如果您的字符串碰巧有一个大于 127(即小于零)的 ASCII 字符，则会出现错误。

解决此问题的一种方法是替换:

   temp[(int)str[i]]

与:

   temp[str[i] + 128]

(并将 int temp[10000] = {0} 更改为 int temp[256 + 128] = {0})。无论 char 的默认符号如何，这都将起作用。