C++链表操作：单向与双向

本文主要介绍了C++中单向链表和双向链表的基本操作，包括链表的创建、计算长度、查找元素、打印链表、清空链表以及链表的逆序。以下是对这些操作的详细说明： 1. 链表创建：在C++中，链表是由一系列节点组成的数据结构，每个节点包含一个数据部分和一个指向下一个节点的指针。在`Create()`函数中，首先创建一个临时节点`p1`，然后从用户输入接收数值并不断创建新节点，直到遇到数值为0时停止。新节点插入链表末尾，并通过`p2`指针更新链表的链接。最后返回链表头节点。 ```cpp Node* Create() { int n = 0; Node* p1, * p2, * head; // ... (省略部分代码) } ``` 2. 计算链表长度：`ListLength()`函数通过遍历链表计算节点数量。从头节点开始，逐个移动`p`指针直到到达链表尾部，每次移动都增加计数器`count`。 ```cpp int ListLength(Node* L) { Node* p = L; int count = 0; while (p->next) { count++; p = p->next; } return count; } ``` 3. 查找链表元素：`Search()`函数用于在链表中查找特定值的节点。它从头节点开始遍历，比较每个节点的数值，若找到匹配的值则返回对应的索引，否则返回0。 ```cpp int Search(Node& L, int value) { Node* p = L; int index = 0; while (p) { if (p->num == value) return index; p = p->next; index++; } return 0; } ``` 4. 打印链表：`Print()`函数遍历链表并将每个节点的数值输出。从头节点开始，逐个打印节点直到链表尾部。 ```cpp void Print(Node* head) { Node* p = head; while (p) { cout << p->num << ""; p = p->next; } cout << endl; } ``` 5. 清空链表：`Destruct()`函数通过遍历链表并删除每个节点来释放链表所占的内存。同时维护一个临时指针`temp`来存储当前节点，以便在删除`current`后释放内存。 ```cpp void Destruct(Node* head) { Node* current = head, * temp = NULL; while (current) { temp = current; current = current->next; delete temp; } } ``` 6. 链表逆序：`ReverseList()`函数采用循环方法实现链表的逆序。初始时，`p`指向头节点，`q`指向下一个节点，`r`存储`q`的下一个节点。然后将`q`的`next`指针指向`p`，再移动`p`、`q`和`r`，直到`q`为空，完成链表逆序。 ```cpp Node* ReverseList(Node* head) { Node* p, * q, * r; p = head; while (q != NULL) { r = q->next; q->next = p; p = q; q = r; } return p; } ``` 以上就是C++中单向链表和双向链表的基本操作，它们构成了链表操作的基础，为更复杂的链表算法提供了可能。注意，这里的示例仅涉及单向链表，双向链表的操作会有额外的前向指针，但基本操作思路相似。