C语言字符数组与字符型指针

Question

给字符型变量赋初值时，可以正常运行。输入一个字符给字符型变量时，没有运行结果。
代码如下：

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

int main()
{
    char str[] ="I like playing basketball!";
    printf("%s\n",str);
    char c;
    printf("请输入想删除的字符：");
    scanf("%s",&c);
    //c=getchar();
    printf("%s\n",c);
    for(int i=0;i<strlen(str);i++)
    {
        if(str[i]==c)
        {
            for(int j=i;j<strlen(str);j++)
            {
                str[j]=str[j+1];
            }
        }
    }
    printf("%s\n",str);
    return 0;
}

运行结果截图：

两种输入方式都是上图的结果。如果使用字符型指针，代码该如何修改？该算法的时间复杂度为O(mn),如何提高算法的时间复杂度？

Answer 1

该回答引用ChatGPT

在您的代码中，使用 scanf 函数读取一个字符时，需要使用 %c 格式字符串，而不是 %s，因为 %s 用于读取字符串。此外，您可以使用字符指针来代替字符数组，这样可以节省空间。修改后的代码如下：

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

int main()
{
    char *str = "I like playing basketball!";
    printf("%s\n", str);

    char c;
    printf("请输入想删除的字符：");
    scanf("%c", &c);

    for (int i = 0; i < strlen(str); i++)
    {
        if (str[i] == c)
        {
            for (int j = i; j < strlen(str); j++)
            {
                str[j] = str[j + 1];
            }
        }
    }

    printf("%s\n", str);

    return 0;
}

在这个实现中，使用了字符指针来代替字符数组，因为字符串是常量，无需在运行时修改。因此，使用字符指针可以节省空间。

对于时间复杂度的问题，您的算法的时间复杂度是 O(mn)，其中 m 是字符串长度，n 是要删除的字符的数量。在每次删除时，您需要将剩余部分的字符串向左移动一个位置。因此，您需要在最坏情况下移动 m 次，因此总时间复杂度为 O(mn)。

为了提高时间复杂度，您可以考虑使用双指针，遍历字符串并在原地修改字符串。这样，您只需要遍历一次字符串，并在必要时删除字符，时间复杂度将降至 O(m)。具体实现方式如下：

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

int main()
{
    char str[] = "I like playing basketball!";
    printf("%s\n", str);

    char c;
    printf("请输入想删除的字符：");
    scanf("%c", &c);

    char *p = str;
    char *q = str;
    while (*q)
    {
        if (*q != c)
        {
            *p++ = *q;
        }
        q++;
    }
    *p = '\0';

    printf("%s\n", str);

    return 0;
}

在这个实现中，使用双指针，一个指针用于遍历字符串，另一个指针用于指向当前的有效字符。当遍历到不需要删除的字符时，将其复制到有效字符的位置，并将有效字符指针向前移动。这样，在遍历结束时，有效字符指针将指向新字符串的结尾。这个算法的时间复杂度是 O(m)，其中 m 是字符串长度。