在雙鏈表中交換節點 - 緩慢的排序算法丟棄節點

Question

實踐中，我一直致力於尋找重複部分，生成字典，壓縮與哈夫曼編碼的壓縮器。

這不是真的有用。

其中一個問題是，由於某種原因，我的排序算法從字典中刪除關鍵字。我認爲問題出現在交換例程中，但我不確定。 （這個例程交換相鄰的關鍵字，下一個是當前 - >下一個）。

我確實有一個static關鍵字* 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; 
} 

發現這有什麼不對嗎？

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