C++实现链表：动态内存分配与单向链表操作

"这篇资源是关于清华大学C++课程中第9章链表的讲解，主要涵盖了链表的基本概念、单向链表的定义与操作。通过动态内存分配和自引用结构来实现链表，允许在链表的任意位置进行元素的插入和删除。" 在编程领域，链表是一种非常重要的数据结构，它不同于数组，不需要预先定义固定的大小。在本章节中，首先介绍了链表的基本概念，强调了其优于结构数组的地方，即链表可以根据需要动态地分配和释放内存，避免了固定大小数组可能导致的空间浪费。 链表由一系列自引用结构组成，每个结构（也称为节点）包含数据以及一个指向下一个节点的指针。在C++中，我们可以定义一个结构体来表示链表的节点，例如： ```cpp struct node { int data; node* next; }; ``` 这里的`data`用于存储实际的数据，`next`是一个指向下一个`node`类型的指针，用于连接链表中的各个节点。当`next`为`NULL`时，表示链表的末尾。 单向链表是最基础的链表类型，每个节点只有一个指向下一个节点的指针。创建一个单向链表通常包括以下步骤： 1. 声明一个链首指针变量`head`并初始化为`NULL`，表示链表为空。 2. 通过`malloc`或`new`动态分配一个新的节点，并将其插入链尾。 3. 重复第二步，直到达到所需的节点数量。 例如，以下代码展示了如何创建一个读入n个整数的链表： ```cpp #include <iostream> struct node { int data; node* next; }; node* createList(int n) { node* temp, * tail = NULL, * head = NULL; int num; for (int i = 0; i < n; ++i) { std::cin >> num; temp = new node; temp->data = num; temp->next = NULL; if (head == NULL) { head = temp; tail = temp; } else { tail->next = temp; tail = temp; } } return head; } int main() { int n; std::cout << "Please enter the number of nodes: "; std::cin >> n; if (n > 0) { node* listHead = createList(n); // 进行其他操作... } return 0; } ``` 在这个例子中，`createList`函数接收一个整数n，然后读取n个整数，每个整数被用来创建一个新的节点并插入到链表的尾部。`main`函数则负责获取用户输入的节点数量，并调用`createList`函数来构建链表。 链表的插入和删除操作相比数组更加灵活，但访问速度较慢，因为需要通过指针逐个遍历。在处理动态数据集或需要频繁插入和删除元素的场景中，链表是很好的选择。理解链表的概念和操作对于深入学习数据结构和算法至关重要，也是C++程序员必备的基础知识。