C++链表讲解：动态内存与单双向链表操作

"这份资源是清华大学关于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. **双向链表**： - 虽然这个资源没有深入讨论双向链表，但双向链表是单向链表的扩展，每个节点除了有指向下一个节点的指针外，还有指向前一个节点的指针，这使得在链表中的前向和后向遍历都变得简单。 链表的这些概念和操作对于理解和实现复杂的数据结构，如队列、栈、图等，都至关重要。通过掌握链表，开发者能够有效地管理内存，实现灵活的数据存储和访问策略。在实际编程中，链表广泛应用于各种场景，如高效插入和删除操作，特别是在数据量不确定或者频繁变动的情况下。