Échange de nœuds dans une liste à double liaison - l'algorithme de tri lent fait tomber les nœuds

Question

Pour la pratique, j'ai travaillé sur un compresseur qui fait la chose find-repeat-parts, make-dictionary, compress-avec-huffman codes.

Ça ne marche pas vraiment. L'un des problèmes est, pour une raison quelconque, mon algorithme de tri supprime des mots-clés du dictionnaire. Je pense que le problème est dans la routine d'échange, mais je ne suis pas sûr. (cette routine échange des mots-clés adjacents, avec next next-> next).

J'ai un mot-clé statique * head;

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; 
} 

Vous ne trouvez pas ce produit:?

Answer 1

Vous ne définissez pas next->next->prev.

Il est notoirement difficile d'obtenir des implémentations de structure de données correctes. La façon de repérer ce genre de chose est de déterminer combien de pointeurs devraient être mis à jour (6). Vous ne mettez à jour que 5, donc il faut manquer!

Answer 2

J'ai vu beaucoup de questions liées à Listes liées, donc je décide de partager ma version Linked List, donc il peut être adapté et/ou amélioré. Cette version est écrite en C++, certaines méthodes ont été omises pour économiser l'espace:

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--; 
}