Поменять узлы в двойном связанном списке - алгоритм медленной сортировки отбрасывает узлы

Question

Для практики я работал над компрессором, который выполняет код поиска, повторяющихся частей, словаря компоновки, сжатия с Хаффманом.

Это на самом деле не работает.

Одна из проблем заключается в том, что по какой-то причине мой алгоритм сортировки удаляет ключевые слова из словаря.Я думаю, что проблема в процедуре обмена, но я не уверен.(эта процедура меняет местами смежные ключевые слова, а next - current-> next.

void swap(keyword * current, keyword * next) {
  keyword * prev = current->prev;
  if (prev){
    prev->next = next;
    next->prev = prev;
  } else { /* no prev - current is head */
    head = next;
    next->prev = 0;
  }
  current->prev = next;
  current->next = next->next;
  next->next = current;
}

Нашли что-нибудь не так с этим?

Answer 1

Вы не установили next->next->prev.

Получение правильных реализаций структуры данных общеизвестно сложно. Чтобы определить подобные вещи, нужно определить, сколько указателей нужно обновить (6). Вы обновляете только 5, так что один должен отсутствовать!

Answer 2

Я видел много вопросов, связанных с Связанными списками , поэтому я решил поделиться своей версией Связанного списка, чтобы ее можно было адаптировать и / или улучшить. Эта версия написана на C ++, некоторые методы для экономии места были опущены:

class Node {    
    friend class LinkedList;
public:
    Node();
    Node(const node& krNode);
    explicit Node(const int kiData);
    virtual ~Node();
    Node& operator=(const Node& krNode);
    int GetData(void) const {return _idata; }
private: int _iData; Node* _pNetxNode; 
}
Node::Node(): _iData(0), _pNextNode(0) {}
Node::Node(const Node& krnode): _iData(krNode._iData), _pNextNode(0) {}
Node::~Node() {}
Node& Node::operator=(const Node& krNode) {_iData = krNode._iData; return *this; }

class LinkedList {
public:
    LinkedList();
    virtual ~LinkedList();
    int GethLenght(void) {return _iSize;}
    void Append(Node* pNode);
    void Insert(const int kiIndex, node* pNode);
    Node* GetItem(const int kiIndex);
    int IndexOf(Node* pNode);
    void Remove(const int kiInde);  
    void Swap(constconst int kiIndexA, const int kiIndexB); 
    void Clear(void);
    void Print(void);
protected:
    LinkedList(const LinkedList& krLinkedList);
    LinkedList& operator=(const LinkedList& krLinkedList);
private:
    Node* Detach(const int kiIndex);
    Node* _pFirstNode;
    Node* _pLastNode;
    int _iSize;
}

LinkedList::LinkedList() : _pFirstNode(0), _pLastNode(0), _iSize(0) {}
LinkedList::~LinkedList() { Clear(); }
void LinkedList::Append(Node* pnode) { if(0==_iSize{_pFistrNode = pNode; } else { _pLastNode->_pNextNode = pnode; } _pLastNode = pNode; _iSize++; }
void LinkedList::Insert(const int kiIndex, node* pNode) {
    Node* pNext = 0; Node* pPrevious = 0;
    if(0==_iSize) { Append(pNode); }
    else {
        if(0==kiIndex){ pNode->_pNextNode = _pFirstNode; _pFirstNode = pNode; }
        else { pPrevious = Getitem(kiIndex-1); pNext=pPrevoius->_pNextnode; pNode->_pNextNode=pNext; pPrevious->_pNextnode=pNode;}
    } _iSize++;
}
Node* LinkedList::GetItem(const int kiIndex){
    Node* pNode = _pFirstNode; int iCounter = 0;
    while(icounter++ != kiIndex) { pNode = pNode->_pNextnode; }
    return pNode;
}

int LinkedList::IndexOf(Node* pSearchNode){
    node* pNode = _pFirstnode; int iIndex=0;
    while(o != pNode) { if(pnode==pSearchNode) { break;} iIdex++; pNode=pnode->_pnextnode; }
    if(iIndex ==_iSize) {iIndex = -1;}
    return iIndex;
}

void LinkedList::Remove(const int kiIndex){ delete Detach(kiIndex); }

void LinkedList::Swap(const int kiIndexA, const int kiIndexB){
    int iLowIndex = 0; int iHighIndex = 0;
    if(kiIndex>==kiIndexB) {return;}
    iLowIndex = (kiIndexA < kiIndexB) ? kiIndexA : kiIndexB;
    iHighIndex = (kiIndexA > kiIndexB) ? kiIndexA : kiIndexB;
    Insert(iHighIndex, Detach(iLowIndex));
    Insert(iLowIndex, Detach(iHighIndex-1));
}
void LinkedList::Clear(void) {
    Node* pNode=_pFirstNode; while(0!=pnode){delete pNode; pNode=pNode-_pNextNode;}
    _pFirstnode=0; _pLastnode=0;
}
void LinkedList::Print(void) {
    Node* pNode = _pFirstNode;
    while(0 != pnode) {printf("%d ", pNode_iData); pNode = pNode->_pNextNode;}
}
Node* LinkedList::Detach(const int kiindex){
    Node* pnode = _pFirstnode; Node* pToDetachNode = 0;
    if(kiIndex==0){
        pToDetachNode = _pFirstNode; _pFirstNode=pnode->_pNextNode; if(1==_iSize){_pLastNode=0;}
    }
    else{
        Node* pPreviousNode = GetItem(kiIndex-1);
        pToDetachNode = pPreviousNode->_pNextNode;
        if(kiIndex<_iSize){pPreviousNode->_pNextNode=pPreviousNode->_pNextnode; }
        else {pPreviousNode->_pNextnode=0; _pLastNode=pPrevoiusNode;}
    }_iSize--;
}