Удаление m узлов в одиночных списках

Напишите код функции bool DeleteMNodes (int x, int m). Функция удаляет первые m узлы со значением x. Если есть хотя бы один узел со значением 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 == 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; 
     } 
    } 
    else { 
     break; 
    } 
}

Я бы предпочел, чтобы последний из них избегал ненужных итераций.

источник

2014-01-25 23:45:41 Pedrom

Удаление m узлов в одиночных списках

ответ

Смежные вопросы