刪除單鏈表中的m個節點

編寫函數bool DeleteMNodes (int x, int m)的代碼。該函數刪除值爲x的第一個m節點。如果至少有一個值爲x的節點，則返回true;否則，它返回false。如果值爲x的節點數小於m，則刪除值爲x的所有節點。該功能應在O(n)中運行。刪除單鏈表中的m個節點

這裏是班裏的SSL節點：

class IntSLLNode 
{ 
public: 
    int val; 
    IntSLLNode* next; 

    IntSLLNode(int val,IntSLLNode* next); 
    ~IntSLLNode(); 
};

這是SSL類：

class IntSLList 
{ 
public: 
    IntSLList(); 
    ~IntSLList(); 

    bool IsEmpty(void); 
    void AddToHead(int val); 
    void AddToTail(int val); 
    void DeleteFromHead(void); 
    void DeleteFromTail(void); 
    bool DeleteNode(int val); 
    bool IsInList(int val); 
    bool DeleteMNodes (int x, int m); //My function 
    void Print(); 

private: 
    IntSLLNode *head, *tail; 
};

這是我實現DeleteMNodes(int x, int m)功能：

bool IntSLList::DeleteMNodes(int x, int m) 
{ 
    IntSLLNode *pred, *tmp, *delNode; 
    int count=0; 
    if (IsEmpty()) 
     return false; 

    if (count <= m) { 
     if (head->val == x) { 
      DeleteFromHead(); 
      count++; 
     } 
    } 

    for (pred=head, tmp=head->next; tmp!=NULL;) 
    {  
     if (count <= m) 
     { 
      if (tmp->val == x) 
      { 
       delNode = tmp; 
       pred->next = tmp->next; 
       tmp = tmp->next; 
       delete delNode; 
       count++; 
      } 
      else { 
       pred = pred->next; 
       tmp = tmp->next; 
      } 

     } 
    } 
    if (count>=1) 
     return true; 
    else 
     return false; 
    } 
}

但它不工作！什麼是錯的？

來源

2014-01-25 ammarx

你有什麼錯誤？ –

我認爲它進入了一個無限循環。當我將'count <= m'更改爲'count ammarx

我需要查看何時調用'DeleteMNodes'。另外，請注意您的計數器初始化爲0，因此如果您希望刪除'm'節點，則應該是'count

計數達到m後，指針並未前進。你有幾個這樣的選項，例如：

for (pred=head, tmp=head->next; tmp!=NULL;) 
{  
    bool didDelete = false; 
    if (count <= m) 
    { 
     if (tmp->val == x) 
     { 
      delNode = tmp; 
      pred->next = tmp->next; 
      tmp = tmp->next; 
      delete delNode; 
      count++; 
      didDelete = true; 
     } 
    } 

    if(!didDelete) 
    { 
     pred = pred->next; 
     tmp = tmp->next; 
    } 
}

或者你可以只打破一次m ==計數。

for (pred=head, tmp=head->next; tmp!=NULL;) 
{  
    if (count <= m) 
    { 
     if (tmp->val == x) 
     { 
      delNode = tmp; 
      pred->next = tmp->next; 
      tmp = tmp->next; 
      delete delNode; 
      count++; 
     } 
     else { 
      pred = pred->next; 
      tmp = tmp->next; 
     } 
    } 
    else { 
     break; 
    } 
}

我可能會更喜歡最後一個，因爲避免不必要的迭代。

來源

2014-01-25 23:45:41 Pedrom

刪除單鏈表中的m個節點

回答

相關問題