如何使用交换功能为双向链表创建气泡排序？

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