HOWTO · C++
在 C++ 中对链表进行排序
本编程教程演示了在 C++ 中对链表数据结构的排序操作的实现。
本页内容
这个简单的编程教程演示了在 C++ 中对链表数据结构的排序操作的实现。
C++ 中的列表
列表或链表是一种线性数据结构，可以作为数据容器，将数据存储在内存中。与向量或数组不同，列表中的数据不需要连续的内存位置；相反，数据可以动态增长并分配到任意堆内存位置。
列表中的每个元素称为一个节点。列表中的每个节点都包含一个指向列表的下一个节点的指针。
在每个节点中包含指向下一个元素的指针可以促进线性链接，其中每个下一个元素都可以通过前一个节点访问。节点之间的这种线性链接是将此结构命名为链表的主要原因。
可以对链表执行多种 ADT（抽象数据类型）操作，例如插入、删除、搜索甚至排序。我们将从链表的基本结构实现开始，然后在该类中实现排序算法。
在 C++ 中实现链表
现在，我们将开始实现链表。为此，首先，我们需要为 Node 创建一个类，如下所示：
template <class T>
class Node {
public:
T data;
Node<T>* next;
Node() { next = 0; }
};
在这个类中，有两个成员，一个用于存储数据，即 info，另一个是该类的指针，用于存储下一个节点的地址。该类被模板化，以便可以创建任何数据类型的列表。
现在，我们将创建一个这样的链表类：
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = 0; }
void insertAtHead(T val) {
Node<T>* x = new Node<T>(val);
x->next = head;
head = x;
}
void displayAll() {
Node<T>* x = head;
{
while (x != 0) {
cout << x->info << endl;
x = x->next;
}
}
}
};
在这个类中，有一个构造函数和另外两个成员函数来插入和显示列表节点。
在 C++ 中对链表进行排序
我们将实现最简单的排序算法，冒泡排序，以升序对链表进行排序。如果以未排序的顺序放置，此排序算法会重复交换相邻元素。
重复执行此操作，直到所有元素都处于正确的排序位置。这将按如下方式实施：
-
创建一个新节点
temp供以后使用，并使head成为curr节点。 -
如果
head为 NULL，则返回。 -
否则，进行循环，直到到达
end节点（即 NULL）。 -
每次重复都应重复步骤 5-6。
-
在
temp中，存储curr节点的下一个节点。 -
检查
curr节点的数据是否大于下一个节点的数据。如果较大，则交换curr和temp。
void sortLinkedList() {
Node<T> *curr = head, *temp = NULL;
int t;
if (head == NULL) {
return;
} else {
while (curr != NULL) {
temp = curr->next;
while (temp != NULL) {
if (curr->info > temp->info) {
t = curr->info;
curr->info = temp->info;
temp->info = t;
}
temp = temp->next;
}
curr = curr->next;
}
}
}
驱动程序将是：
int main() {
LSLL<int> list;
list.insertAtHead(50);
list.insertAtHead(45);
list.insertAtHead(16);
cout << "Before sorting" << endl;
list.displayAll();
cout << "After Sorting: " << endl;
list.sortLinkedList();
list.displayAll();
return 0;
}
输出：
Before sorting
43
65
13
After Sorting:
13
43
65
