我使用以下代码的目标是让用户输入一些整数,将这些整数存储在 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;
}

最佳答案

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

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

  • 就是这样。你现在拥有的是不可行的,只会导致未定义的行为。您的列表基本上“由”生命周期已经结束的 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

    关于C - 堆栈分配的链表,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/45178196/

    10-11 22:59
    查看更多