如何使用交換功能爲雙向鏈表創建氣泡排序？

Question

我想弄清楚如何爲DNode編寫一個名爲DNode *DNode::bubble()的成員函數，其中 DNode *head可以對鏈表進行冒泡排序並返回新的頭部。 我想使用成員函數void swap(DNode *that) 交換兩個節點。

這裏是我迄今關於h和.cpp文件：

#ifndef DNODE_H 
#define DNODE_H 
class DNode { 

public: 

int key; 
DNode *next; 
DNode *prev; 

void add(int key); 
void print(); 
DNode(); 
DNode *bubble(); 
void swap(Dnode *that); 
}; 

#endif 

#include "DNode.h" 
#include <cstdlib> 
#include <iostream> 
using namespace std; 

void DNode::swap(DNode *that){ 
DNode *temp = this; 
DNode *R1, *L1, *R2, *L2; 

} 

Dnode *Dnode::bubble(){ 
DNode *temp = this; 
int count = 0; 
while(start != NULL){ 
count++; 
start = start->next; 
} 

for(int i = 0; i < count; i++){ 

} 
} 

我有一個問題，用什麼是交換函數只是一個參數來交換節點列表。

Answer 1

那麼所有你需要做的是從以前&未來這些元素調整兩者的next和prev成員，以及多達鏈接同步：

void DNode::swap(DNode *that) 
{ 
    // this->prev->next points back to 'this' should become 'that' 
    if(this->prev) { 
    this->prev->next = that; 
    } 
    // this->next->prev points back to 'this' should become 'that' 
    if(this->next) { 
    this->next->prev = that; 
    } 
    // that->prev->next points back to 'that' should become 'this' 
    if(that->prev) { 
    that->prev->next = this; 
    } 
    // that->next->prev points back to 'that' should become 'this' 
    if(that->next) { 
    that->next->prev = this; 
    } 
    // remember whatever 'this' ->next and ->prev point to 
    DNode * n1 = this->next, * p1 = this->prev; 
    // let 'this' take the position of 'that in the list 
    this->prev = that->prev; 
    this->next = that->next; 
    // let 'that' take the position of the original 'this' in the list. 
    that->prev = p1; 
    that->next = n1; 
} 

另外：如果你只是想換在列表中的特定邏輯位置值那麼你也可以簡單的交換價值：

void swap(DNode* that) 
{ 
    int old = this->key; 
    this->key = that->key; 
    that->key = old; 
}