如何使用swap函数为双重链表创建冒泡排序

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