删除链接列表中具有特定值的所有节点

标题相当自我解释。下面是我为这个目的编写的功能：删除链接列表中具有特定值的所有节点

void wipeLoneCells() 
{ 
    cell *tmp; 

    tail = head; 
    while (1) 
    { 
     if (head == tail && !tail->flag) 
     { 
      head = head->next; 
      free(tail); 
      tail = head; 
      continue; 
     } 

     tmp = tail->next; 

/***/ if (tmp->next == NULL && !tmp->flag) 
     { 
      tail->next = NULL; 
      free(tmp); 
      break; 
     } 
     else if (!tmp->flag) 
     { 
      tail->next = tmp->next; 
      free(tmp); 
      continue; 
     } 

     tail = tail->next;  
    } 
}

名单的头和尾是全球性的，而列表是通过这个函数被调用头指向第一个节点和尾指向时建最后（其下一个是NULL）。我几乎可以肯定，我的链接列表是正确构建的，因为我可以毫无错误地打印它们。有时候，这个函数完美地工作，有时它会在标有星号的行上导致访问冲突。我知道这并不是完全错误的，因为当我没有产生错误时，我得到了我想要的结果，尽管我经常得到错误，所以一定有一些我忽略的东西。预先感谢您的任何帮助。

编辑：这里是固定码：

void wipeLoneCells() 
{ 
    cell *tmp; 

    tail = head; 
    while (1) 
    { 
     if (head == tail && !tail->flag) 
     { 
      head = head->next; 
      free(tail); 
      tail = head; 
      continue; 
     } 

     tmp = tail->next; 

     if (tmp->next == NULL && !tmp->flag) 
     { 
      tail->next = NULL; 
      free(tmp); 
      break; 
     } 
     else if (tmp->next == NULL) 
     { 
      tail = tmp; 
      break; 
     } 
     else if (!tmp->flag) 
     { 
      tail->next = tmp->next; 
      free(tmp); 
      continue; 
     } 

     tail = tail->next;  
    } 
}

来源

2011-12-23 user1112789

你能告诉我们'细胞'的定义吗？ – fge 2011-12-23 12:12:25

提示：如果您使用笔和纸手写并在该基础上手动执行步骤和写入代码，则链接列表问题更容易解决。 – 2011-12-23 12:46:44

如果

tmp = tail->next;

是NULL？下一行尝试取消引用NULL指针，导致未定义的行为 - 可能导致崩溃。

你应该检查这个条件并采取适当的措施。

来源

2011-12-23 12:13:13

+1，我想实际上他只需要'tmp = tail'（或者根本不需要'tmp''''），否则他会跳过第二个元素。 – 2011-12-23 12:14:50

你让我意识到，当'tmp'指向最后一个节点并且节点不会被删除时，我没有条件。在这种情况下，'tail'移动到最后一个节点，'tmp'确实变为'NULL'，当我尝试读取'tmp-> next'时发生访问冲突。我在原来的帖子中添加了修复程序，感谢发人深省的评论。 – user1112789 2011-12-23 16:52:37

正确deleteitem()在单链表应该如下：

可以避开递归，并拿出一个迭代版本（给它一个尝试，但让我知道如果你需要帮助）。我不会在这种情况下使用while(1)！

typedef struct node { 
    int data; 
    struct node *next; 
}NODE; 


/* 

(1) deleting head 
    delete element and adjust head pointer 

(2) deleting tail 
    delete element and adjust tail pointer 

(3) one element list 
    if data is the data for the only element 
    then delete the list and set head and tail 
    pointers to NULL 

(4) all the other cases 
    traverse through the list and hold the 
    previous pointer. delete element and adjust 
    the next pointers. 

(5) if not the above cases, then element not 
    present.. do nothing.. 

*/ 
void deleteitem(int data) 
{ 
    printf("%s: %d - ", __FUNCTION__, data); 
    NODE *cur = head; 
    NODE *prev = cur; 
    NODE *temp = NULL; 

    if (head == NULL) { 
     assert (tail == NULL); 
     printf("Empty list \n"); 
     return; 
    } 

    if (head->data == data) { 
     temp = head; 

     // one element list 
     if (head == tail) 
      head = tail = NULL; 
     else 
      // list has more than one element 
      head = head->next; 

     printf("%d \n", temp->data); 
     free(temp); 
     deleteitem(data); 
     return; 
    } 

    while (cur != NULL) { 
     if (cur->data == data) { 
      if (cur == tail) { 
       tail = prev; 
      } 
      prev->next = cur->next; 
      printf(" %d deleted\n", cur->data); 
      free(cur); 
      assert(tail->next == NULL); 
      deleteitem(data); 
      return; 
     } 
     prev =cur; 
     cur = cur->next; 
    } 

    printf(" %d not found\n", data); 
    return; 
}

来源

2011-12-23 12:43:36

删除链接列表中具有特定值的所有节点

回答

相关问题