c - 无法从链表中删除最低值

Question

我在 C 中创建了一个链表。我正在尝试创建一个函数，该函数查看链表中的最低值(即头部)并删除该值的“最右边”实例列表。

假设链表如下所示:

2 -> 2 -> 2 -> 4 -> 5 -> 6

此列表中的头是 2。但它不是我要删除的头。我想删除 4 之前的 2(它是头部最右边的实例)。

这是我为实现此目的而创建的函数:

double removeLowestValue() {
  struct node *temp;
  struct node *ptr = head;
  double val = ptr->value;
  if(head == tail)
  {
      free(head);
      head = NULL;
      tail = NULL;
  }
  else
  {
      while(ptr->value == ptr->next->value)
      {
          temp = ptr;
          ptr = ptr->next;
          val = ptr->value
      }
      temp->next = NULL;
      temp->next = ptr->next;
      free(ptr);

      return val;
  }
}

然后我尝试测试该功能是否有效:

int main() {
  insertNode(18.0);
  insertNode(13.0);
  insertNode(11.0);
  insertNode(11.0);
  insertNode(22.0);

  printf("%d", removeLowestValue());

  return 0;
}

不幸的是，程序没有按预期打印出“11”。事实上，它根本不打印任何东西。这是怎么回事？

编辑:

下面是我如何实现 insertNode 函数:

void insertNode(double value) {
  struct node *new_node = create_new_node(value);
  struct node *temp = head;
  struct node *prev;

  if (head == NULL) {
    head = new_node;
    tail = new_node;
  } else {
    while (value > temp->value && temp->next != NULL) {
      prev = temp;
      temp = temp->next;
    }

    if(value < temp->value || value == temp->value)
    {
        /*If the value of the new node equals to the value of temp
         OR if the value of the new node is less than the value of temp,
         then insert the new node right before temp*/

        new_node->next = temp;
        prev->next = new_node;
    }
    else if(value > temp->value)
    {
        temp->next = new_node;
        tail = new_node;
    }
  }
}

Answer 1

您的函数已更正，当然假设列表已排序:

double removeLowestValue() {
  if (head == NULL)
    return 0; /* ???? */
  else {
    node * ptr = head;
    node * previous = 0; /* the cell before the cell to remove */

    while ((ptr->next != NULL) && (ptr->value == ptr->next->value)) {
      previous = ptr;
      ptr = ptr->next;
    }

    /* ptr is now the cell to remove */

    double val = ptr->value;

    if (ptr == head) {
      /* remove the first cell */
      ptr = head->next;
      free(head);
      head = ptr;
      if (head == NULL)
        /* the list is empty */
        tail = NULL;
    }
    else if (ptr->next == NULL) {
      /* all the values are the same in the list
         ptr is the last cell */
      free(ptr);
      /* previous is now the last cell */
      previous->next = NULL;
      tail = previous;
    }
    else {
      /* ptr is not the first nor the last cell */
      previous->next = ptr->next;
      free(ptr);
    }

    return val;
  }
}

---

关于 insertNode :

• 最好把变量temp和prev的声明移到有用的地方，如果head就没用了null so 在定义的顶部

• (value < temp->value || value == temp->value)可以只是(value <= temp->value)和 else if (...) after 可以只是一个 else

• 当 (value <= temp->value) prev 仍可取消设置但用于 prev->next = new_node ，当您在 main 中的 18 之后插入 13 时，它会追加。当(temp == head)你必须更新 head 并将其设置为 new_node

所以更正后的版本可以是:

void insertNode(double value) {
  struct node *new_node = create_new_node(value);

  if (head == NULL) {
    head = new_node;
    tail = new_node;
  } else {
    struct node *temp = head;
    struct node *prev = 0; /* = 0 to be sure to have a crash if something wrong */

    while ((value > temp->value) && (temp->next != NULL)) {
      prev = temp;
      temp = temp->next;
    }

    if (value <= temp->value)
    {
        /* insert the new node right before temp*/
        new_node->next = temp;
        if (temp == head)
          head = new_node;
        else
          /* prev was set */
          prev->next = new_node;
    } else {
        /* insert the new node at end */
        temp->next = new_node;
        tail = new_node;
    }
  }
}

---

使用附加定义

typedef struct node {
  double value;
  struct node * next;
} node;

node * create_new_node(double value)
{
  node * r = (node *) malloc(sizeof(node));

  r->value = value;
  r->next = 0;

  return r;
}

int main() {
  insertNode(18.0);
  insertNode(13.0);
  insertNode(11.0);
  insertNode(11.0);
  insertNode(22.0);

  printf("%g\n", removeLowestValue());
  printf("%g\n", removeLowestValue());
  printf("%g\n", removeLowestValue());
  printf("%g\n", removeLowestValue());
  printf("%g\n", removeLowestValue());
  printf("%g\n", removeLowestValue());

  return 0;
}

执行写入(最后0表示列表为空)

11
11
13
18
22
0