"这份资源是清华大学关于C++链表的讲授内容，涵盖了自引用结构、链表的基本概念，以及单向链表和双向链表的定义与操作。通过PPT的形式进行了深入讲解，旨在帮助学习者理解动态内存分配和链式数据结构的运用。"
在计算机科学中，链表是一种基础且重要的数据结构，它与数组不同，不连续存储数据，而是通过指针链接一系列的节点。本讲座主要关注了以下几个核心知识点：
1. **链表的基本概念**：
- 链表克服了固定大小数组的限制，允许根据需要动态地分配和释放内存。在链表中，每个节点包含数据和一个指针，用于指向下一个节点，最后一个节点的指针为NULL，表示链表的结束。
2. **自引用结构**：
- 自引用结构是指结构体中包含了一个指向自身类型的指针。例如，定义一个单向链表节点时，节点结构包含一个整型数据和一个指向下一个同类型节点的指针。
3. **单向链表**：
- 单向链表的定义：每个节点除了存储数据外，还有一个指针指向下一个节点。链表的头部通常由一个指针变量（如`head`）来表示，初始时设为NULL，表示空链表。新节点通过动态内存分配（如`malloc`或`new`）创建，并附加到链尾。
4. **单向链表的操作**：
- 建立链表：首先声明链首指针，初始化为NULL，然后逐个读取数据，创建新的节点并添加到链尾。例如，可以编写一个函数`createList`，接收要创建的节点数，然后循环创建节点并链接。
```cpp
node* createList(int n) {
node* temp, *tail = NULL, *head = NULL;
int num;
// 读取数据，创建节点并链接
for (int i = 0; i < n; ++i) {
cin >> num;
temp = new node; // 动态创建节点
temp->data = num;
temp->next = NULL;
if (tail != NULL) tail->next = temp; // 将新节点链接到链尾
else head = temp; // 第一个节点，设置链首
tail = temp; // 更新尾部指针
}
return head;
}
```
5. **双向链表**：
- 虽然这个资源没有深入讨论双向链表，但双向链表是单向链表的扩展，每个节点除了有指向下一个节点的指针外，还有指向前一个节点的指针，这使得在链表中的前向和后向遍历都变得简单。
链表的这些概念和操作对于理解和实现复杂的数据结构，如队列、栈、图等，都至关重要。通过掌握链表，开发者能够有效地管理内存，实现灵活的数据存储和访问策略。在实际编程中，链表广泛应用于各种场景，如高效插入和删除操作，特别是在数据量不确定或者频繁变动的情况下。
我的内容管理
展开
