C f 给出了意想不到的结果

Question

我正在做“Advent of Code 2022”，我在第一天遇到了一个奇怪的错误 (https://adventofcode.com/2022/day/1)，我需要帮助。

当前，我正在尝试解析一个包含数字组的文本文件（https://adventofcode.com/2022/day/1/input）并将结果输出到屏幕。代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define IN_FILE "input.txt"
#define MAX_LINE_LEN 20480

int main(int argc, char *argv[])
{
    // Variable declaration
    char line[MAX_LINE_LEN];
    int counter = 0;
    int elfno = 0;
    FILE *fd;

    // Create "Key Value pair" struct. Use ints for both vars as we need to perform arithmetic on the values.
    struct kv_store
    {
        int key;
        int value;
    };

    struct kv_store kv[counter];
    //struct kv_store kv_total;

    // Open file

    fd = fopen(IN_FILE, "r");
    if (fd == NULL)
    {
        // File does not exist. Exit
        fprintf(stdout, "\n[*]%s not found in current working directory.", IN_FILE);
        return -1;
    }

    // Iterate through file line by line. Place lines into kv[n].value with kv[n].key as the elf number (elfno). Increment elfno once a blank line is found.
    while(fgets(line, MAX_LINE_LEN, fd) != NULL)
    {
        if(strlen(line) == 1)
        {
            elfno ++;
            continue;
        }
        else
        {
            kv[counter].key = elfno;
            sscanf(line, "%d", &kv[counter].value);
            //kv[counter].value = strtol(line, NULL, 0);
            counter ++;
            continue;
        }
    }

    for(int i=0;i < counter;i++)
    {
        fprintf(stdout, "Iteration: %d - Elf: %d holds: %d \n", i, kv[i].key, kv[i].value);
    }

    // TODO: Upon EOF, we can iterate through kv. If elfno for next value in kv hasn't changed, add value to kv_total[elfno].value. If it does change, move on to the next efls values.

    // TODO: Once complete, iterate through kv_total and find the largest number, print to screen.
    return 0;
}

一切似乎都工作正常，但是在 while 循环的第四次迭代（从输入中读取值 6086）中，我得到了垃圾结果。我应该看到 Elf: 1 成立：6086。剩余的迭代给出了正确的输出（下面的示例屏幕截图）。

使用我对 gdb 和调试非常有限的知识，我在运行时查看了 line 变量，并且可以看到仅当 line 在迭代过程中包含值 6086 时才修改该变量（下面的屏幕截图).

目前已进行的检查：

• 使用十六进制编辑器确认输入文件中没有恶意编码
• 尝试使用

  strtol

  而不是

  sscanf

• 尝试使用

  malloc()

  和

  free()

  在每次迭代结束时清除 line 变量

任何对此的帮助将不胜感激。

Answer 1

正如评论中提到的，你有一个零长度数组：

// ...
    int counter = 0;
    // ...
    struct kv_store kv[counter];
// ...

访问此内容将导致未定义的行为。 Valgrind 可能是检测此问题的有用工具：

$ gcc aoc.c -ggdb3 -Wall && valgrind ./a.out
==58338== Memcheck, a memory error detector
==58338== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==58338== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==58338== Command: ./a.out
==58338== 
==58338== Invalid write of size 4
==58338==    at 0x109390: main (aoc.c:45)
==58338==  Address 0x1fff002a48 is not stack'd, malloc'd or (recently) free'd

其中

aoc.c:45

（第 45 行）是第一个写入

kv

：

kv[counter].key = elfno;

。

退一步来说，你还需要数组吗？该问题要求所有精灵负载的最大。贪心算法应该起作用——每当发现更大的负载时，这就是全局的新的最佳结果。无需存储历史记录，因为任何其他先前结果都不可能篡夺当前最佳结果。

如果这还不清楚，经典的问题解决策略是简化问题并从更简单问题的解决方案推断回更大的问题。这个问题可以简化为寻找数组中最大的元素。

在现实生活中，你会如何在头脑中解决这个问题？您可能会在记忆中保留一个“迄今为止最大的”数字，然后在发现更大的数字时替换它。无需记住已被替换的数字，因为它们肯定不是最佳的。从时间复杂度的角度来看，这需要 O(1) 空间而不是 O(n)（存储结果与输入大小成正比）。

#include <stdio.h>

int main() {
    int nums_len = 5;
    int nums[] = {3, 5, 6, 1, 3};
    int largest = nums[0];

    for (int i = 0; i < nums_len; i++) {
        if (nums[i] > largest) {
            largest = nums[i];
        }
    }

    printf("%d\n", largest); // => 6
}

您正在解决的问题是类似的，除了需要在构建当前块时保留当前块的总数，该总数可以累积在单个整数上。一旦将当前块总数与总体最大块大小进行比较，就可以将其丢弃，就像在更简单的问题中一样。

伪代码：

largest = -infinity
current_chunk = 0

for (line in file) {
   if line is empty {
       largest = max(largest, current_chunk)
       current_chunk = 0 // prepare for the next chunk
   }
   else { // accumulate the size of the current chunk
       current_chunk += parse_integer(line)
   }
}

// current_chunk may still hold a value from the last
// chunk in the file, if the file doesn't end in a blank
// line, so consider it as a possible result one more time
largest = max(largest, current_chunk)

print largest

尝试用 C 语言编写代码。