c - 将新节点添加到列表时出现段错误

Question

我在搜索列表并尝试添加新节点时遇到问题。 代码如下所示

struct sizelist{
    int currentsize, origsize;
    struct sizelist * next;
};
typedef struct sizelist item;

这里是内容的大小，items是连接的节点数量，next是下一个节点。

void firstfit(item tosort){
  int junksize = tosort.currentsize;
  int paired;
  item* current;
  for(int i=0;i<containeramount;i++){
    if(containers[i].currentsize - junksize >=0){
      paired = i;
      break;
    }
  }
  current = &containers[paired];
  while(current->next!=NULL){
    current = current->next;
  }
  containers[paired].currentsize = containers[paired].currentsize - junksize;
  current->next = &tosort;
 }

containers 是 item 的数组。

这似乎现在有效。但是现在我的输出有问题:

void writeout(){
  item* current;
  for(int i=0;i<containeramount;i++){
    current = &containers[i];
    for(int j=0;; j++){
      printf("%d ",current->currentsize);
      if(current->next!=NULL){
        current = current->next;
      }
      else{
        break;
      }
    }
    printf("\n");
  }
}

现在你也对程序有了全部的了解。 例如，我给它 3 个大小为 10 的容器和大小为 6、8、1、5 的东西。看起来 firstfit 成功了，但 writeout 方法却不行。 这里正确的输出应该是:

10 6 1

10 8

10 5

这里 origsize 的输出是:

10 3

10 3

10 3

对于当前大小，它是:

3 134515941

2 134515941

5 134515941

Answer 1

看起来最新版本的代码改进了很多， 但是 tosort 按值传递给 firstfit(item tosort)。 这意味着在函数 firstfit(item tosort) 中，tosort 是一个临时的 在函数结束时销毁的变量。 (这也出现在程序的早期版本中，但我们查看了 先解决其他问题。)

现在该函数正在对实际内容进行处理 containers[paired] 而不是临时副本， 正在设置列表中的最终 next 指针(根据需要)， 但它指向临时对象 tosort。 当函数结束时，tosort 超出范围。 据推测，其他东西被写入同一个虚拟 block 打印出来时的内存。

如果函数改为 firstfit(item* tosort)，即传递一个指针而不是一个副本 结构。 这将表现得更像你期望调用一个函数 在 Java 中运行。

---

注意:以下备注引用revision 2 of the question. 问题中的代码已被修改，以便遵循 这些建议。

---

我发现代码中有很多明显的错误，很难跟踪 所有这些，但我怀疑段错误在这里:

    current = containers[paired];
    for(int i=0;i<containers[paired].items;i++){
        current = *current.next;
    }

代码中的一个错误是您将 item 声明为当前；。 这意味着 current 始终是一个临时数据结构，从不 实际上“在”containers[paired] 中。当你执行 current.next = &tosort; 时，唯一改变的是这个临时数据结构的一个字段，它在下一行超出范围并被销毁。所以实际上那条线什么都不做。它绝对不在containers[paired] 中插入任何数据。

另一方面，containers[paired].items++;确实增加了containers[paired]中的计数器。所以现在 containers[paired].items 大于链表中实际的项目数。这意味着当你在其他时间进入这个函数并使用相同的 containers[paired] 执行上面的循环时，你也会执行 current = *current.next;多次;您最终尝试访问列表中最后一个节点的 next 节点，然后出现段错误。

在C中实现简单链表的标准方法是设置 next 指针指向 0(或 NULL，如果它被定义为 0)每当 列表中没有实际的“下一个”东西；列表中的最后一件事 总是 next 等于 0。为了找到列表中的最后一个东西， 您不会计算跟随next 指针的次数； 您只需跟随 next 指针，直到到达其所在的节点 next 指针为 0，然后你停止。

我强烈建议摆脱 items。您始终可以通过跟踪列表到最后并计算遇到的节点数来找出容器中有多少项。当然，这比只读取 items 的值要花更长的时间，但它会给你正确的答案，而且不会导致段错误 .让你的程序无错误地运行，然后你可以考虑在需要时让它更快(例如通过将 items 放回你的结构中并使其实际具有正确的值)。