如何对链表进行排序

Question

我有一个链表，我想按特殊顺序对它进行排序。我试着使用冒泡排序。由于我的结构(称为Node(中有许多数据类型，所以我无法交换这些值。

struct Node
{
int data;
Node *next;
Node(int x)
{
data = x;
next = NULL;
}
union
{
sold s;
apartment a;
villa v;
}u;
};

实际上，我不能在my_swap函数中交换并集值。我需要的是一个新的交换函数。这是我的密码。

#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct adderess {
char city[50];
char street[100];
char alley[100];
int code;
};
struct apartment {
float structure_s;
float price;
int floor;
bool elevator;
adderess adr;
};
struct villa {
float structure_s;
float yard_s;
float price;
int floor;
adderess adr;
};
struct sold {
int type;
float comission;
bool con;
};
struct Node
{
int data;
Node *next;
Node(int x)
{
data = x;
next = NULL;
}
union
{
sold s;
apartment a;
villa v;
}u;
};

void print_list(Node *head)
{
Node *start = head;
while (start)
{
cout << start->data << " -> ";
start = start->next;
}
cout << "nn";
}
void my_swap(Node *node_1, Node *node_2)
{
int temp = node_1->data;
node_1->data = node_2->data;
node_2->data = temp;
}
double total_price(Node **n) {
if ((*n)->data == 1)
return((*n)->data*(*n)->data);
else 
return((*n)->data*(*n)->data*(*n)->data);
}
void bubble_sort(Node *head)
{
int swapped;
Node *lPtr; // left pointer will always point to the start of the list
Node *rPrt = NULL; // right pointer will always point to the end of the list
do
{
swapped = 0;
lPtr = head;
while (lPtr->next != rPrt)
{
if (total_price(&lPtr) >total_price(& lPtr->next))
{
my_swap(lPtr, lPtr->next);
swapped = 1;
}
lPtr = lPtr->next;
}
//as the largest element is at the end of the list, assign that to rPtr as there is no need to
//check already sorted list
rPrt = lPtr;
} while (swapped);
}
int main()
{
Node *head = new Node(2);
head->next = new Node(1);
head->next->next = new Node(4);
head->next->next->next = new Node(3);
head->next->next->next->next = new Node(6);
head->next->next->next->next->next = new Node(5);
cout << "The original list = " << endl;
print_list(head);

bubble_sort(head);
cout << "The Sorted list = " << endl;
print_list(head);
return 0;
}

Answer 1

您可以交换它们在链表中的位置，而不是交换两个节点中的值。为此，您需要维护一个prev指针，该指针位于链表中lPtr之前。

void my_swap(Node*& head, Node*& prev, Node*& node_1, Node*& node_2)
{
if (prev == nullptr)
{
node_1->next = node_2->next;
node_2->next = node_1;
prev = node_2;
head = node_2;
}
else
{
node_1->next = node_2->next;
node_2->next = node_1;
prev->next = node_2;
prev = node_2;
}
}
void bubble_sort(Node *head)
{
bool swapped;
Node *prev, *lPtr, *rPtr; // left pointer will always point to the start of the list
rPtr = nullptr; // right pointer will always point to the end of the list
do
{
swapped = false;
prev = nullptr;
lPtr = head;
while (lPtr->next != rPtr)
{
if (total_price(&lPtr) > total_price(&lPtr->next))
{
my_swap(head, prev, lPtr, lPtr->next);
swapped = true;
}
else
lPtr = lPtr->next;
}
//as the largest element is at the end of the list, assign that to rPtr as there is no need to
//check already sorted list
rPtr = lPtr;
} while (swapped);
}

我还没有检查它是否正确运行，但希望你在看完代码后能明白。