C++链表讲解：清华大学第九章链表教程

"这份资源是清华大学的一份关于C++链表的PPT，主要涵盖了链表的基本概念、动态内存分配、单向链表和双向链表的定义与操作。" 在计算机科学中，链表是一种重要的数据结构，它不同于数组，不连续存储数据。在C++中，链表的实现通常涉及指针和动态内存管理。本PPT讲解了以下几个关键知识点： 1. **链表的基本概念**：相对于固定大小的结构数组，链表允许动态地分配和释放内存，避免了浪费空间的问题。链表由一系列节点构成，每个节点包含数据和指向下一个节点的指针，最后一个节点的指针为NULL。 2. **自引用结构**：在C++中，链表节点通常是一个自引用的结构，即结构体中包含一个指向同类型结构的指针。例如，定义一个`node`结构体，它包含一个`int`类型的数据成员`data`和一个指向`node`类型的指针`next`。 ```cpp struct node { int data; node* next; }; ``` 3. **单向链表**：单向链表中的每个节点只含有一个指向下一个节点的指针。创建单向链表时，首先声明一个头指针`head`并初始化为`NULL`，然后通过动态分配内存（使用`malloc`或`new`）创建新节点，并将其链接到链尾。 4. **动态内存分配**：在C++中，`malloc`和`new`用于动态分配内存。例如，创建一个`student`类型的节点： ```cpp struct student { int num; char name[20]; char sex; float score; student* next; }; student* p = (student*)malloc(sizeof(student)); // 使用malloc // 或 student* p = new student; // 使用new ``` 5. **单向链表的操作**：主要包括链表的建立、插入和删除。例如，创建一个包含n个整数的链表，可以先读取用户输入的节点数量`n`，然后调用`createList`函数，通过循环动态创建节点并链接到链表尾部。 ```cpp node* createList(int n) { node* temp, * tail = NULL, * head = NULL; // 读取整数并创建节点，插入到链尾 ... } ``` 6. **双向链表**：双向链表每个节点除了包含数据外，还有两个指针，一个指向前一个节点，另一个指向后一个节点，这样可以从两个方向遍历链表。双向链表的操作比单向链表复杂，但提供了更多的灵活性，如双向插入和删除。 7. **链表的插入和删除操作**：在链表中插入节点需要修改前后节点的指针，删除节点则需要调整相邻节点的指针。这些操作都需要对链表结构有深入的理解和熟练的指针操作。 这份PPT详细介绍了链表的基础知识，包括其概念、内存管理以及在C++中的实现，对于学习数据结构和算法的初学者来说是一份宝贵的资料。