C - 堆栈分配的链表

Question

我使用以下代码的目标是让用户输入一些整数，将这些整数存储在类型为INT_NODE的堆栈分配节点中，然后将所有这些节点链接在一起。 最后，我想遍历列表并打印出每个节点上的元素(只有以下代码中的前 5 个(。 但是，当我输入一些数字时，程序会打印出我输入的第一个数字，然后我输入的最后一个数字重复了 4 次。 例如，如果我输入84 5 12 7 1 22 31[Enter]然后在下一行的开头按Ctrl+D来模拟这台 Mac 上的 EOF，我会得到以下输出;84 31 31 31 31. 我不知道它为什么要这样做。

我知道我可以使用malloc()分配堆上的节点，并且我已经编写了一个函数来执行此操作。 我只是想知道是否可以使用运行时堆栈来做到这一点。

在下面的代码中，INT_NODE类型在"SortingAlgs.h"标头中定义如下;

typedef struct INT_NODE {
int element;
struct INT_NODE *next;
} INT_NODE;

---

#include <stdio.h>
#include <stdlib.h>
#include "SortingAlgs.h"
int main(void) {
INT_NODE head = {-999999999};
int num;
INT_NODE *pCurrentNode = &head;
if (scanf("%d", &num) != EOF) {
head.element = num;
while (scanf("%d", &num) != EOF) {
INT_NODE newNode;
newNode.element = num;
newNode.next = NULL;
pCurrentNode->next = &newNode;
pCurrentNode = pCurrentNode->next;
}
} 
int i;
for (pCurrentNode = &head, i = 0; i < 5;
pCurrentNode = pCurrentNode->next, i++)
printf("%d  ", pCurrentNode->element);
printf("n");
return 0; 
}

Answer 1

要使用运行时堆栈执行此操作，您可以使用以下方法之一：

1. 通过alloca进行运行时分配。这很简单：基本上只需将malloc替换为alloca(并且不要尝试将alloca包装到另一个函数中(。但是，alloca不是标准功能。
2. 递归函数，其中每个递归级别将托管单个列表节点(或固定数量的列表节点(。这有一些严重的限制，但从技术上讲，它满足了您在堆栈上分配所有节点的要求。
3. 预先分配固定数量的节点作为本地数组，并希望它足以满足您的列表...但我敢肯定这不是你的意思。

仅此而已。你现在拥有的东西是不可行的，只会导致未定义的行为。您的列表基本上"包含"INT_NODE生命周期已经结束的对象。在实践中，您通常最终会一次又一次地重用相同的内存位置，有效地将单个节点链接到自身。

下面是一个示例，如果一个实现按照递归方法将整个列表"保留在堆栈上"。当然，该列表仅在所有递归调用都处于"活动"状态时才存在。这限制了这种技术的适用性，但它有它的用途

#include <stdlib.h>
#include <stdio.h>
typedef struct INT_NODE 
{
int element;
struct INT_NODE *next;
} INT_NODE;
void print_list(const INT_NODE *head)
{
for (const INT_NODE *current = head; current != NULL; current = current->next)
printf("%d  ", current->element);
printf("n");
}
void build_list(INT_NODE *head, INT_NODE *last)
{
INT_NODE new = { 0 };
if (scanf("%d", &new.element) != 1)
{
print_list(head);
return;
}
if (head == NULL)
head = &new;
else
last->next = &new;
build_list(head, &new);
}
int main(void) 
{
build_list(NULL, NULL);
}

http://coliru.stacked-crooked.com/a/5a4f15a82c66d992

Answer 2

我认为原因是变量的范围。 输入 5，程序在堆栈上分配内存，但它将被返回。 输入 12，分配相同的内存，返回它。 所以最后，头下一个指针是相同的内存，同一个内存下一个指针是它自己。

您可以输出 5 个以上。 也许你会得到 84

31 31 31 31 31 31 .....