3

我得到一个名为“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;

}

我的理解是，当我制作 head->next 新头时，应该摆脱原来的条目。

但是 0 值索引继续保留在列表中。结果是 (3,0) (6,200) (8,100)

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

4

2 回答 2

2

您的代码中有未定义的行为。

当你这样做

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

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

但这不是唯一的问题。另一个是您实际上并没有取消链接您正在释放的节点。先前的head->next（在重新分配head和随后的释放之前）指针仍然指向现在空闲的节点。

于 2013-10-22T18:35:03.200 回答
1

您的函数应该通过 return head 或 Node **head 作为参数返回新的 head

和

如果你根本没有头，head->index 就会崩溃

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;
}
于 2013-10-22T18:31:55.357 回答