在 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
Husnain is a professional Software Engineer and a researcher who loves to learn, build, write, and teach. Having worked various jobs in the IT industry, he especially enjoys finding ways to express complex ideas in simple ways through his content. In his free time, Husnain unwinds by thinking about tech fiction to solve problems around him.
LinkedIn