如何使用相同的冒泡排序布局来处理双向链表

Question

下面的代码使用类函数对单链表进行排序。它将用户输入放入数组中，将该数组转换为链表，然后对其进行排序。我不确定应该进行哪些更改才能使其适用于双链接列表。我知道该结构需要一个新的 prev 指针，但我不知道如何将其放入气泡中 排序算法 这段代码的功能通常是冒最大的下降，我现在不太担心效率，而是看到排序的实用性。据我所知，转换为双链接应该只是一些新的 -> 链接，我想看看这些应该是什么，以更好地理解冒泡排序和双链表的基础知识。

#include <bits/stdc++.h>
using namespace std;

struct Node{
 int val;
 Node* prev;
 Node* next;
 Node(int x){
  val = x;
  prev = NULL;
  next = NULL;
 }
};

class DoubleLink{
 public:
  Node* head;

 void push(int x){
  Node* newnode = new Node(x);
  newnode->next = head;
  if(head != NULL){
   head->prev = newnode;
  }
  head = newnode;
 }

 void printList(Node* head){
  Node* current = head;
  cout<<endl;
  while(current != NULL){
   cout<<current->val<<" ";
   current = current->next;
  }
 }

 int getSize(Node* headref){
  int count =0;
  while(headref != NULL){
   count++;
   headref = headref->next;
  }
  return count;
 }

 void bubbleSort(Node* headref){
 Node* lswap = NULL;
 int sz = getSize(headref);
 while(sz--){
  Node* current = headref;
  Node* prv = NULL;
  Node* cswap = NULL;
  while(current->next != lswap){
   Node* after = current->next;
   if(current->val > after->val){
    current->next = after->next;
    after->next = current;
    if(prv == NULL)
     current=after;
    else
     prv->next=after;

    prv=after;
    cswap = current;
    }
    else{
     prv = current;
     current=current->next;
    }
   }
   if(cswap==NULL)
    break;
   else
    lswap = cswap;
  }
 }
};

int main(){
 DoubleLink list;
 int size;
 cout<<"How many numbers"<<endl;
 cin>>size;
 int numbers[size];
 cout<<"Enter numbers"<<endl;
 for(int i=0;i<size;i++){
  cin>>numbers[i];
 }
 for(int i=0;i<size;i++){
  list.push(numbers[i]);
 }
 cout<<"first"<<endl;
 list.printList(list.head);
 cout<<"second"<<endl;
 list.bubbleSort(list.head);
 list.printList(list.head);
 cout<<endl;
}

Answer 1

我也想知道！谢谢！