在C语言中输入大字符串

Question

针对一个特定的问题，我需要从用户那里获取字符串输入，其大小可以在1和10^5之间。我使用了以下代码：

char *a;
a = malloc(100000*sizeof(char));

在循环内部（t代表测试用例的数量）

while( t-- )
{
  scanf( "%d", &n );
  scanf( "%s", a );
  .....
}

n是由用户在运行时输入的字符串的长度。问题是这给了我“超时”错误。

我对上面的代码进行了一些更改，

 while( t-- )
 {
   scanf( "%d", &n );
   char a[n];
   scanf( "%s", a );
   ....
 }

这段代码在没有使用"TLE"的情况下完美运行。但我不知道原因。使用第一种代码的原因是为了节省时间，因为只需要一次分配内存。我错了吗？ 请解释一下。

- akashrajkn

---

是谁在出现“超过时间限制”的错误？我认为这不是你的C代码出了问题，而是你使用的平台。 - Emanuele Paolini

如果第二段代码中读取为“a”的字符串确实是“n”个字符宽，那么您会低估一个（终止符）。其次，在第二种情况下没有“动态”运行时分配。它实际上是一个sub esp，n。如果我猜测，TLE的避免很可能与您的低分配直接相关，导致缓冲区溢出并覆盖了“t”，将其设置为终止符（即0），从而在单个迭代之后结束循环。 - WhozCraig

小问题：使用 a = malloc(100000 + 1); - chux - Reinstate Monica

在www.codechef.com上出现了“超时”的情况...第二段代码片段运行得非常完美。第一段代码片段则提示“时间限制已超过”... - akashrajkn

Answer 1

如果您使用malloc函数，内存空间将在堆上创建。

而在第二种实现中，内存位于栈上。

据我所知，栈比堆更快。

参考：What and where are the stack and heap? 此外，我认为在循环外声明char数组更加合理。

char a[100000] = {};

while( t-- )
 {
   scanf( "%d", &n );
   scanf( "%s", a );
   ....
 }

- Alfred Huang

---

如果循环中有"malloc"，这将是一个合理的论点。但实际情况并非如此，因此它...不是。这是一个单次分配，对整个算法的复杂度最多为O(1)。 - WhozCraig