创建与合并单链表的C++实现

"本文将介绍数据结构中的单链表，并提供创建和合并单链表的实例。单链表是一种线性数据结构，其中每个元素（节点）包含一个数据域和一个指向下一个元素的指针。在C++中，我们通常通过定义一个结构体来表示链表的节点。 首先，定义单链表的存储结构如下： ```cpp typedef struct LNode//单链表的存储结构 { ElemType data; struct LNode *next; }LNode,*LinkList; ``` 这里，`LNode`是结构体类型，它有两个成员：`data`用于存储元素的数据，`next`是一个指针，指向链表中的下一个节点。`LinkList`是`LNode`类型的指针，通常用来表示整个链表。 接着，我们来看如何创建一个单链表。以下是一个简单的示例函数`CreateList_L`，用于创建一个包含`n`个元素的链表： ```cpp void CreateList_L(LinkList& L, int n) { ElemType data; LinkList p; L = (LinkList)malloc(sizeof(LNode)); // 分配头节点 L->next = NULL; // 头节点的next设为NULL for (int i = n; i > 0; --i) { p = (LinkList)malloc(sizeof(LNode)); // 分配新节点 cout << "请输入元素：" << endl; cin >> data; p->next = L->next; L->next = p; // 将新节点添加到链表 } } ``` 这个函数会提示用户输入`n`个元素，然后创建一个新的链表，其中头节点`L`通过引用传递。每个新节点在链表中的插入位置是头节点之后。 另一个重要的操作是合并两个已排序的单链表。以下是一个函数`MergeList_L`，用于将两个有序链表`La`和`Lb`合并成一个有序链表`Lc`： ```cpp void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) { LinkList pa, pb, pc; pa = La->next; pb = Lb->next; Lc = pc = La; // 将La的头节点作为Lc的头节点 while (pa && pb) { if (pa->data <= pb->data) { pc->next = pa; // 将pa节点链接到pc pa = pa->next; } else { pc->next = pb; // 将pb节点链接到pc pb = pb->next; } pc = pc->next; // 移动pc到下一个位置 } if (pa == NULL) { pc->next = pb; // 如果La遍历完，将剩余的Lb链接到Lc } else { pc->next = pa; // 如果Lb遍历完，将剩余的La链接到Lc } } ``` 这个函数通过比较`La`和`Lb`中当前节点的值，选择较小的节点添加到`Lc`中，从而保持链表的排序。 在实际应用中，单链表常用于实现各种算法，如搜索、排序等。它的优点是插入和删除操作相对高效，因为只需要改变相邻节点的`next`指针。然而，由于没有内置的随机访问能力，访问中间或末尾的元素需要从头开始遍历链表，这在访问效率上不如数组。 单链表是数据结构基础中的重要概念，理解其基本操作和实现对于学习更复杂的算法和数据结构至关重要。通过上述的`CreateList_L`和`MergeList_L`函数，我们可以更好地理解和掌握单链表的基本操作。