C语言 如何按升序创建链表

Question

我得到了一个名为"head"的稀疏数组，它是二维的，有一个索引和一个值。所以像这样：（3， 100） （6，200） （8，100）

1. 我必须按升序将一个节点（值、索引）插入到这个稀疏数组中。因此，如果我得到 （2，100），列表应如下所示：(2, 100)（3，100） （6，200） （8，100）

同样，如果我得到 （4，200），它应该返回（3，100） （4，200） （6，200） （8，100）

条件 1：如果索引相同，那么我必须添加值

所以如果我得到（3，100），那么我应该返回（3，200） （6，200） （8，100）

条件 2：如果索引相同，并且值为零，则应删除该值。所以如果数组是 （3，-100），我必须返回

（6，200） （8，100）

Node * List_insert_ascend(Node * head, int value, int index)
{
  Node * node = List_create(value, index); //this creates an empty node, "node"
  if (index < (head->index)) //node's index is less, e.g. (1,100)
    {node -> next = head;} //this inserts "node" before "head"
  if (index == (head->index))
  {
    node = head;
    head->value = head->value + value; //Condition 1
    while ((head->value)==0)  //Condition 2
    {
      Node *p = head->next;
      head = p;
        
    }
  }
  return node;
}

我的理解是，当我将头>下一个新头时，应该去掉原来的条目。

但0值指数继续保留在列表中。结果是（3，0） （6，200） （8，100）

如果有人能帮助我弄清楚我做错了什么（甚至可能是为什么），我将不胜感激。

Answer 1

代码中有未定义的行为。

当你这样做时

Node *p = head->next;
head = p;
free(p);

您实际上是在释放head和p都指向的节点。然后取消引用head会导致未定义的行为。

但这不是唯一的问题。另一个是你实际上并没有取消链接你释放的节点。前一个head->next（从重新分配head及其后续释放之前）指针仍然指向现在可用的节点。

Answer 2

你的函数应该通过返回头或节点返回新头 **头作为参数

和

头部>指数是你根本没有头部的崩溃

Node * list_insert_update_remove(Node **head, int value, int index) 
{
  Node *node = List_create(...);
  if (*head == NULL) 
    *head = node;
  else {
    Node *prev = NULL;
    Node *list = head;
    while (list) {
      if (index < list->index) { //prepend
        if (prev == NULL) // before head
          *head = node; 
        else {
          prev->next = node; // into the middle/end
          node->next = list;
        }
        break;
      } else if (index == list->index) {
        //update or remove (execercise)
        break;
      } else if (list->next == NULL) { // append at end
        list->next = node;
        break;
      }
      prev = list;
      list = list->next;
    }
  }
  return *head;
}