在 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
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布，任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站。本站所有源码与软件均为原作者提供，仅供学习和研究使用。如您对本站的相关版权有任何异议，或者认为侵犯了您的合法权益，请及时通知我们处理。
