C ++ Удаление из списка с начальной позицией и концом - PullRequest
Новая
       73

C ++ Удаление из списка с начальной позицией и концом

2 голосов
/ 08 января 2020

Как я могу удалить из списка, например, с позиций с 1 по 4?

Я только что решил это удаление с 1 элементом из списка: 

void delPos(int iPos) {
  ListElem *pElemToDelete = mpHead;
  for (int i = 0; i < iPos; ++i) {
    pElemToDelete = pElemToDelete->mpNext;
  }
  if (pElemToDelete != nullptr) {
    if (mpHead == pElemToDelete) {
      mpHead = pElemToDelete->mpNext;
      delete pElemToDelete;
    } else {
      for (ListElem *pTmp = mpHead; pTmp != nullptr; pTmp = pTmp->mpNext) {
        if (pTmp->mpNext == pElemToDelete) {
          pTmp->mpNext = pElemToDelete->mpNext;
          delete pElemToDelete;
          return;
        }
      }
    }
  }

И для удаления позиции (от начала до конца) я получил это: 

void deleteElem(int start, int end) {
  ListElem *pTmp1 = m_pHead;
  ListElem *pTmp2 = m_pHead;
  for (int i = 0; i < end; ++i) {
    if (i < start - 1) {
      if (pTmp1->m_pNext != nullptr) {
        pTmp1 = pTmp1->m_pNext;
      }
    }
    if (pTmp2->m_pNext != nullptr) {
      pTmp2 = pTmp2->m_pNext;
    }
  }
  if (start == 0) {
    m_pHead = pTmp2->m_pNext;
  } else {
    pTmp1->m_pNext = pTmp2->m_pNext;
  }
}

но это действительно не удаляется верно? Он просто показывает следующий указатель на нужный элемент. Я пробую это как выше с 1 элементом, но это не работает.

Может быть, вы, ребята, можете дать мне несколько советов?

1 Ответ

0 голосов
/ 08 января 2020

Для начала эта функция 

void delPos(int iPos) {
  ListElem *pElemToDelete = mpHead;
  for (int i = 0; i < iPos; ++i) {
    pElemToDelete = pElemToDelete->mpNext;
  }
  //..

может вызывать неопределенное поведение, когда iPos больше или равно количеству узлов в списке.

Функция может быть реализована следующим образом 

bool delPos( size_t iPos ) 
{
    ListElem **pElemToDelete = &mpHead;

    for ( ; pElemToDelete != nullptr && iPos != 0; --iPos )
    {
         pElemToDelete = &( *pElemToDelete )->mpNext;
    }

    bool success = pElemToDelete != nullptr;

    if ( success )
    {
        ListElem *tmp  = *pElemToDelete;
        *pElemToDelete = ( *pElemToDelete )->mpNext;
        delete tmp;
    }

    return success;
}

Теперь реализовать вторую функцию несложно. Я предполагаю, что конечная позиция не входит в диапазон удаленных узлов. 

bool delPos( size_t iStart, size_t iEnd ) 
{
    bool success = iStart < iEnd;

    if ( success )
    {
        ListElem **pElemToDelete = &mpHead;

        size_t i = 0;

        for ( ; pElemToDelete != nullptr && i != iStart; ++i )
        {
            pElemToDelete = &( *pElemToDelete )->mpNext;
        }

        success = pElemToDelete != nullptr;

        if ( success )
        {
            for ( ; pElemToDelete != nullptr && i != iEnd; i++ )
            {
                ListElem *tmp  = *pElemToDelete;
                *pElemToDelete = ( *pElemToDelete )->mpNext;
                delete tmp;
            }
        }
    }

    return success;
}

Вот демонстрационная программа. 

#include <iostream>

class List
{
private:
    struct ListElem
    {
        int data;
        ListElem *mpNext;
    } *mpHead = nullptr;
public: 
    List() = default;

    void pushFront( int );

    bool delPos( size_t );
    bool delPos( size_t, size_t );

    std::ostream & printList( std::ostream & = std::cout ) const;
};


void List::pushFront( int data )
{
    mpHead = new ListElem { data, mpHead };
}

bool List::delPos( size_t iPos ) 
{
    ListElem **pElemToDelete = &mpHead;

    for ( ; pElemToDelete != nullptr && iPos != 0; --iPos )
    {
         pElemToDelete = &( *pElemToDelete )->mpNext;
    }

    bool success = pElemToDelete != nullptr;

    if ( success )
    {
        ListElem *tmp  = *pElemToDelete;
        *pElemToDelete = ( *pElemToDelete )->mpNext;
        delete tmp;
    }

    return success;
}

bool List::delPos( size_t iStart, size_t iEnd ) 
{
    bool success = iStart < iEnd;

    if ( success )
    {
        ListElem **pElemToDelete = &mpHead;

        size_t i = 0;

        for ( ; pElemToDelete != nullptr && i != iStart; ++i )
        {
            pElemToDelete = &( *pElemToDelete )->mpNext;
        }

        success = pElemToDelete != nullptr;

        if ( success )
        {
            for ( ; pElemToDelete != nullptr && i != iEnd; i++ )
            {
                ListElem *tmp  = *pElemToDelete;
                *pElemToDelete = ( *pElemToDelete )->mpNext;
                delete tmp;
            }
        }
    }

    return success;
}

std::ostream & List::printList( std::ostream &os ) const
{
    for ( ListElem *current = mpHead; current != nullptr; current = current->mpNext )
    {
        os << current->data << ' ';
    }

    return os << "nullptr";
}

int main() 
{
    List lst;

    const int N = 10;

    for ( int i = 0; i < N; i++ ) lst.pushFront( i );

    lst.printList() << '\n';

    lst.delPos( 0 );

    lst.printList() << '\n';

    lst.delPos( 8 );

    lst.printList() << '\n';

    lst.delPos( 3, 5 );

    lst.printList() << '\n';

lst.delPos( 0, 6 );

lst.printList() << '\n';
}

Ее вывод 

9 8 7 6 5 4 3 2 1 0 nullptr
8 7 6 5 4 3 2 1 0 nullptr
8 7 6 5 4 3 2 1 nullptr
8 7 6 3 2 1 nullptr
nullptr
...