将节点添加到链表

Question

这段代码在将节点插入到NULL单元格时工作正常。我尝试将其实现为将单元格发送到开头，但自那以后，display_list函数只显示最后一个单元格。我已经试图找出原因一段时间了，有什么建议吗？

我会补充说明，这应该是一个模仿Linux中的dc函数的函数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct CELL {
  int val;
  struct CELL *next;
};

void append_node(struct CELL *llist, int num);
void display_list(struct CELL *llist);

主要看起来很好

int main(void)
{

  int num = 0;
  int first = 0;
  int input = 0;
  char quit = 'n';
  char inputchar = ' ';

  struct CELL *llist;

  llist = (struct CELL *)malloc(sizeof(struct CELL));
  llist->next = NULL;

  while (quit == 'n'){

    if (scanf("%d", &input) == 1){

      if ( first == 1 )
        append_node(llist, input);


      if ( first == 0){
        llist->val = input;
        first = 1;
      }
    }

    else{
      inputchar = getchar();

      if (llist->next == NULL && first == 0)
        printf("List is empty.\n");

      if (inputchar == 'f')
        display_list(llist);

      if (inputchar == 'q')
        quit = 'y';
      else if (llist->next != NULL){
        switch (inputchar){

        case 'q':
        quit = 'y';
        break;
    }
      }
    }


  }
  free(llist);
  return 0;
}

这段被注释的代码是正常工作的！但是我发现我应该将单元格添加到另一端，而我很难想出如何实现。我在这里错过了什么？

void append_node(struct CELL *llist, int num) {
  /* while(llist->next != NULL)
     llist = llist->next;
  llist->next = (struct CELL *)malloc(sizeof(struct CELL));
  llist->next->val = num;
  llist->next->next = NULL;*/

  struct CELL *temp;
  temp = (struct CELL *)malloc(sizeof(struct CELL));
  temp->val = num;
  temp->next = llist;
  llist = temp;
}

void display_list(struct CELL *llist)
{
  while(llist->next != NULL) {
    printf("%d\n", llist->val);
    llist = llist->next;
  }
  printf("%d\n", llist->val);
}

我承认我不太清楚何时应该使用指针，我怀疑可能有地方遗漏了。希望能得到帮助。

- Blake Howard

Answer 1

请看您代码的这一部分：

void append_node(struct CELL *llist, int num) {
  struct CELL *temp;
  temp = (struct CELL *)malloc(sizeof(struct CELL));
  temp->val = num;
  temp->next = llist;
  llist = temp;   // Line1
}

注意事项1: 当你将 llist 指向新节点时，你正在改变 llist 的本地副本，而 main 函数中的 llist 仍然保留着旧值。

如何解决？

这是链表设计上的缺陷。客户端程序（main 函数）不应该访问 CELL 结构。你应该有另一个结构来表示链表，并且拥有指向第一个单元格的指针。

类似于这样：

struct LinkedList {
  struct CELL *head;
};

您的main应该使用这种结构，而不是CELL。

---

在您的代码中，我看到了其他一些事情，

1）如果向display_list函数传递NULL，它将失败。最好像这样处理：

void display_list(struct CELL *llist)
{
  while(llist != NULL) {
    printf("%d\n", llist->val);
    llist = llist->next;
  }
}

2) 在你的main函数最后看到这一行：

free(llist);

你只释放了链表中的第一个单元格。你没有释放添加到列表中的其他单元格，这将导致程序中的内存泄漏。

我该如何解决？不能由客户（主）代码来释放链接列表。你应该提供另一个函数，递归释放所有已分配的单元格。同样，如果你遵循上面建议的用结构表示链接列表的设计，这将更加容易。

---

编辑：根据评论部分的要求添加了一个示例。

如果你按照我建议的设计更改，你的显示将类似于以下内容：

void display_list(struct LinkedList *llist)
{
  struct CELL * head = llist->head;
  while(head != NULL) {
    printf("%d\n", head->val);
    head = head->next;
  }
}

- Ghazanfar

---

谢谢你的所有帮助。我理解你在“我在你的代码中看到的其他几件事”部分所说的内容。我不太确定如何实现这个新结构，它会替换我在开头声明的*llist吗？ - Blake Howard

@BlakeHoward 很高兴能帮助你。这不会取代cell结构，而是取代客户端将要访问的内容。客户端不应该知道cell结构的存在。 - Ghazanfar

@BlakeHoward 创建如上所示的 LinkedList 结构。现在，主函数将创建该结构的实例，而不是 cell 的实例。现在，您所有的 add、delete 和 display 函数都将接受这个 LinkedList 结构，而不是 cell。 - Ghazanfar

@BlakeHoward 我添加了一个示例来展示函数将如何更改。 - Ghazanfar

嘿！我的代码已经运行了，看起来更加简洁，并且根据你们的建议全部正常运行。再次感谢！ - Blake Howard

Answer 2

@Mohammad Ghazanfar的观点是正确的，人们应该注意这些要点。 另一方面，您可以更改以下函数以使您的代码正常工作。

将void append_node(struct CELL *llist, int num);的函数签名更改为 void append_node(struct CELL **llist, int num); 函数定义如下：

void append_node(struct CELL **llist, int num) {
  /* while(llist->next != NULL)
     llist = llist->next;
  llist->next = (struct CELL *)malloc(sizeof(struct CELL));
  llist->next->val = num;
  llist->next->next = NULL;*/

  struct CELL *temp;
  temp = (struct CELL *)malloc(sizeof(struct CELL));
  temp->val = num;
  temp->next = (*llist);
  (*llist) = temp;
  return;
}

将调用 append_node(llist, input); 替换为 append_node(&llist, input);

注意：我只是让你的代码能够工作。这可能不是完美的解决方案。您应该考虑 @Mohammad Ghazanfar 提到的要点。

希望这有所帮助 :)

- Nakul

---

谢谢你的贡献！根据你提供的快速更正，显示函数只返回一个随机的8位数字..... - Blake Howard

我刚刚检查了一下，它显示了正确的输出。我使用了Mohammad Ghazanfar先生答案中的display函数。 - Nakul

没问题，我按照上面的建议重新编写了代码，现在它更加简洁、清晰，并且运行良好！谢谢大家。 - Blake Howard