在 C 中的链表的前面添加一个条目

Question

Welp 好久不见终于得到指点。我知道我的程序会变得优雅和强大。可悲的是，我的理解似乎缺乏。我正在使用 Kochan 的 C 第 4 版编程，这是练习 10.3。我要在链表的开头添加一个条目，但是我认为应该起作用的却不起作用。

#include <stdbool.h>

struct entry
  {
      int      value;
      struct entry *next;
  };
                        //n0_1              list_pointer
void insertEntry(struct entry *what, struct entry *where)
{
    what->next = where->next;
    where->next = what;
}

int main (void)
{

struct entry n1, n2, n3, n4, n5,n0_1, n2_3, n3_4, n4_5;

struct entry *list_pointer = &n1;

  n1.value = 100;
  n2.value = 200;
  n3.value = 300;
  n4.value = 400;
  n5.value = 500;

  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n4;
  n4.next = &n5;
  n5.next = (struct entry*)0;

  n0_1.value = 50;
  n2_3.value = 250;
  n3_4.value = 350;
  n4_5.value = 450;

  insertEntry(&n0_1, list_pointer);
  insertEntry(&n3_4, &n3);
  insertEntry(&n4_5, &n4);


  while (list_pointer != (struct entry *)0){
    printf("%i\n", list_pointer->value);
    list_pointer = list_pointer->next;

  }


  return 0;
}

所以我将发生的事情分解如下-

n0_1.next = List_pointer.next    //ok n0_1.next points to whatever the list pointer was.  
list_pointer.next = n0_1     //doesn't that make list pointer point to n0_1?

任何指导将不胜感激，在此先感谢。看到自己做错了自然会觉得自己是个白痴。

Answer 1

让我们退一步。

所以我们将 n1 作为第一个节点，list_pointer 指向第一个节点。

当您在列表的开头插入节点 X 时，您希望 X.next 指向 list_pointer 指向的内容。所以

X.next = list_pointer

而且，这个节点 X 现在成为您的起始节点。

list_pointer = X

Answer 2

你不能使用这样的调用

insertEntry(&n3_4, &n3);

在节点n3之前插入一个节点，因为在这种情况下你需要更改指向节点n3的节点n2的数据成员next ].但是该函数没有关于节点的信息 n2 因为你有一个单链表。

甚至为了通话

insertEntry(&n0_1, list_pointer);

指针list_pointer指向的节点没有前导节点函数写错了。至少应该定义成

struct entry * insertEntry(struct entry *what, struct entry *where)
{
    what->next = where;
    where = what;

    return where;
}

并称赞

list_pointer = insertEntry(&n0_1, list_pointer);

您可以编写一个函数，在给定节点之后插入一个新节点。例如

struct entry * insertEntry(struct entry *what, struct entry *where)
{
    if ( where == NULL )
    {
        what->next = where;
        where = what;
    }
    else
    {
        what->next = where->next;
        where->next = what;
    }

    return where;
}

Answer 3

显示函数insertEntry，您不能在原始列表指针之前插入任何内容。在这种情况下，指向列表头部的指针必须改变，即 list_pointer 本身的值需要改变，而不是 list_pointer.next 的值；您可以采用两种方法：

(1) 让列表的头部始终相同（并忽略它的 value）；第一个实际项目将是 head.next 指向的项目。

(2) 更改插入条目，这样它可能会更改 where 的值（通过传递指向该指针的指针）。

方法(1)：

struct entry n1, n2, n3, n4, n5,n0_1, n2_3, n3_4, n4_5;
n1.value = 100;
...
struct entry list_pointer;
list_pointer.next = &n1;
...
struct entry* iterator = list_pointer.next;
while (iterator != NULL){
    printf("%i\n", iterator->value);
    iterator = iterator->next;
}

方法(2)

void insertBefore(struct entry *what, struct entry **head)
{
    what->next = (*head);  // let what.next point to the former head
    *head = &what;  // let the head-pointer point to the new head
}

insertEntry(&n0_1, &list_pointer);
...
struct entry* iterator = list_pointer;
while (iterator != NULL){
    printf("%i\n", iterator->value);
    iterator = iterator->next;
}

Answer 4

太棒了，我已经和这该死的东西搏斗了一段时间了。这是我所拥有的，对我来说看起来不错。我迷路的地方是这与上面的答案不冲突？ list_ptr 像我最初认为的那样工作。

#include <stdio.h>
#include <stdbool.h>


struct entry
  {
      int      value;
      struct entry *next;
  };

void insertEntry(struct entry *what, struct entry *where)
{
    what->next = where->next;
    where->next = what;
}

void printEntries(struct entry initial)
{
     while (initial.next != NULL){
        printf("%i   \n", initial.next->value);
        initial.next = initial.next->next;
}
printf("\n");
}

int main (void)
{
  struct entry nx2, n0, n1, n2, n3, nx;

  struct entry *list_ptr;

  list_ptr = &n0;

  n1.value = 100;
  n2.value = 200;
  n3.value = 300;

  nx.value = 77;
  nx2.value = 15;

  n0.next = &n1;
  n1.next = &n2;
  n2.next = &n3;
  n3.next = NULL;

    printEntries(*list_ptr);
    insertEntry(&nx, list_ptr);
    printEntries(*list_ptr);
    insertEntry(&nx2, &n2);
    printEntries(n0);



  return 0;
}

在 C 中的链表的前面添加一个条目

Adding an entry at the front of a linked list in C

c

struct

linked-list

singly-linked-list