C链表删除功能

Question

大家好，我必须用C语言写一个程序，我不能用deleteByPrice - function来删除所有价格大于我必须在控制台上输入的结构这就是我的结构

 typedef struct  
    {
       char name[20];
       char id[20];
       float price;
    }Type;
typedef struct Details {
    Type data;
    struct Details *next;
}Node;

，这就是我的代码，但不工作:

Node *deleteByPrice(Node *start) {
    Node *cur =start;
    Node *next=start;
    float price;
    printf("Insert the price here : ");
    scanf("%f",&price);
    while(cur){
      if (price < cur->data.price){
            next=cur->next;
            free(cur);
            cur = next;
            start=cur;
            } 
       else {           
            next = cur->next->next;
            free(cur->next);
            cur->next = next;
            }
       }
   return cur;
 }

Answer 1

那么，while循环中的两个分支都是不正确的。首先，当价格低于您在控制台上给出的价格时，您应该使用cur = cur->next直接跳转到下一个元素;不需要乱搞链表中的任何项。其次，当价格大于您给出的价格并且您必须删除该项目时，必须按如下方式删除:

1. 您必须将上一个项的next指针链接到当前项(即cur->next)之后的项。因为你只允许在你的链接中移动"前进"，这意味着你必须跟踪上一个项目以及当前项目;使用一个名为prev的额外指针，它从空指针开始，在while循环的每次迭代中将cur步进到下一项之前将其设置为cur。一旦有了prev，就可以使用prev->next = cur->next从列表中删除要删除的项目。(注意，这不会释放项目)。

2. 一旦你从列表中删除了要删除的项目，你可以使用free(cur)安全地释放它，并转移到列表中的下一个项目。然而，由于cur现在是free之后的一个无效指针，您必须首先在释放cur之前的变量中记录cur->next，然后将cur设置为该记录的值以继续遍历列表。

整个解决方案归结为:

prev = 0; cur = start;
while (cur) {
    if (cur->data.price < price) {
        /* keep the item and move to the next one */
        prev = cur;
        cur = cur->next;
    } else {
         /* remember the item after the item being removed */
         next = cur->next;
         /* unlink the item from the list */
         if (prev) {
             prev->next = next;
         }
         /* free the unlinked item */
         free(cur);
         /* move to the next item */
         cur = next;
         /* note that prev does not have to be modified here */
     }
 }

同样，这里还有一个问题。如果你碰巧从列表中删除了第一项，这意味着调用deleteByPrice的函数持有的访问列表第一项的指针不再有效，所以当你删除列表的第一项时，必须相应地更新start，并且必须在函数结束时返回start，以便调用者将知道列表的"新"头在哪里。我故意从上面的代码中省略了这一点——如果您理解我的代码，那么添加这一点应该不会太难。

Answer 2

在删除节点时，您总是修改start，我认为它应该指向列表头(第一个元素)。这似乎不对。

只有当你要修改的元素是第一个元素时，你才应该修改start。

此外，当您发现要删除的元素时，似乎需要跟踪前一个元素，以便更改的 next指针。

Answer 3

Node *deleteByPrice(Node *start, float price) {
  Node *cur;
  Node **ptr;
  for (ptr = &start; cur = *ptr; ){
    if (cur->data.price < price){
        ptr = &cur->next;
        continue;
        }
    *ptr = cur->next; 
    free(cur);
   }
   return start;
 }