指向链表的指针混乱

Question

我正在写一个简单的C程序来管理一个链表，定义如下:

typedef struct node {
    int value;
    struct node *next;
} *List;

我检查了代码，看起来还可以，但是当打印结果时，有些东西工作得不好。

我的主目录，注释有问题:

int main(void) {
    List n = list_create(1);
    insert(n, 2);
    insert(n, 3);
    insert(n, 5);
    insert(n, 4);
    //something here does not work properly. It produces the following output:
    //Value: 1
    //Value: 2
    //Value: 3
    //Value: 4
    //where is value 5?
    print_list(n);
    delete(n, 3);
    print_list(n);
    return 0;
}

我不知道我在哪里破坏了表结构。这些是我的函数，如果你太仁慈的话，可以调试。

List list_create(int value) {
    List new = malloc(sizeof(struct node));
    new->value = value;
    new->next = NULL;
    return new;
}
List new_node(int value, List next_node) {
    List new = malloc(sizeof(struct node));
    new->value = value;
    new->next = next_node;
    return new;
}
void print_list(List l) {
    List *aux;
    for (aux = &l; (*aux) != NULL; aux = &((*aux)->next))
        printf("Valor: %dn", (*aux)->value);
}
void insert(List l, int value) {
    List *p;
    for (p = &l; (*p) != NULL; p = &((*p)->next))
        if ((*p)->value > value) {
            List tmp = *p;
            List new = new_node(value, tmp);
            *p = new;
            break;
        }
    *p = new_node(value, NULL);
}
void delete(List l, int value) {
    List *p;
    for (p = &l; (*p) != NULL; p = &((*p)->next))
        if ((*p)->value == value) {
            List del = (*p);
            (*p) = ((*p)->next);
            free(del);
            break;
        }
}

Answer 1

这段代码(至少)有两个bug:

1. 行

   if ((*p)->value>value){

意味着如果你以1作为列表的第一个值，然后尝试插入2,3,4…， if语句体永远不会运行，因此不会插入任何内容。

如果你在起始值下面插入一个值，你必须修改列表指针本身。然而，正如@EOF所暗示的那样，您试图通过获取其地址来修改传递给函数的值。这行不通。&l不给你传递的List的地址，它给你insert()堆栈上的本地副本的地址。您最好修改列表的第一个元素的值"到位"。如果你真的想让List参数可变，你需要将其作为List *传递，并使用列表的地址调用函数(例如insert(&n,2);)你的delete()函数也遇到了同样的问题——尝试删除列表的第一个元素。

为你的插入函数试试这个:

void insert(List l, int value)
{
  List p;
  // Find end of list or highest item less than value
  for(p = l; p->next != NULL && p->next->value < value; p = p->next);
  if (p->value >= value) {
    // Over-write p with new value, and insert p as a new one after.
    // This saves having to modify l itself.
    int tmpval = p->value;
    p->value = value;
    p->next = new_node(tmpval, p->next);
  } else {
    // Insert new item after p
    p->next = new_node(value, p->next);
  }
}

注释:你使用指针的方式可能对调试过程没有帮助。

例如，print_list()可以这样重写:

void print_list(List l){
  List aux;
  for(aux = l; aux != NULL; aux = aux->next)
    printf("Valor: %dn", aux->value);
}

仍然表现相同。不要通过在typedef中包含"*"来"隐藏"指针类似指针的性质，这通常是一种良好的做法。例如，如果您这样定义列表:

typedef struct node{
  int value;
  struct node *next;
} List

并传递给如下函数:

my_func(List *l, ...)

则会使这些问题更加明显。

Answer 2

你的代码有很多问题:

• 将指针隐藏在typedef后面是一个坏主意，它会导致程序员和读者的混淆。

• 您必须决定初始节点是虚拟节点还是空列表只是一个NULL指针。后者处理起来要简单得多，但你必须将头节点的地址传递给insert和delete，以便他们可以更改头节点。

• printlist不需要间接指针，特别是从作为参数传递的指针的地址开始。

• 在insert中，您正确地在下一个更高的节点之前插入新节点，但您应该然后从函数返回。相反，您将中断切换并执行追加代码，将插入的节点替换为具有相同值和NULL next指针的新节点。这就是5在插入4时被删除和丢失的原因。此外，您应该传递头节点的地址，以便在第一个节点之前插入一个节点。

• delete从参数的地址开始。它不能删除头节点，因为调用方空间中的指针没有得到更新。您应该传递头节点的地址

• 您应该避免在C代码中使用new和delete等c++关键字:虽然不是非法的，但它会混淆习惯c++的读者，混淆语法高亮，并阻止c++编译器编译。

这里是一个简化和更正的版本:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int value;
    struct Node *next;
} Node;
Node *new_node(int value, Node *next_node) {
    Node *node = malloc(sizeof(*node));
    if (node != NULL) {
        node->value = value;
        node->next = next_node;
    }
    return node;
}
void print_list(Node *list) {
    for (; list != NULL; list = list->next)
        printf("Valor: %dn", list->value);
}
void insert_node(Node **p, int value) {
    while ((*p) != NULL && (*p)->value < value)
        p = &(*p)->next;
    *p = new_node(value, *p);
}
void delete_node(Node **p, int value) {
    while (*p != NULL) {
        if ((*p)->value == value) {
            Node *found = *p;
            *p = (*p)->next;
            free(found);
            // return unless delete() is supposed to remove all occurrences
            return;
        } else {
            p = &(*p)->next;
        }
    }
}
int main(void) {
    Node *n = NULL;
    insert_node(&n, 2);
    insert_node(&n, 3);
    insert_node(&n, 5);
    insert_node(&n, 4);
    insert_node(&n, 1);
    print_list(n);
    delete_node(&n, 3);
    print_list(n);
    delete_node(&n, 1);
    print_list(n);
    return 0;
}