刪除鏈接列表中具有特定值的所有節點

標題相當自我解釋。下面是我爲這個目的編寫的功能：刪除鏈接列表中具有特定值的所有節點

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

刪除鏈接列表中具有特定值的所有節點

回答

相關問題