链表初探：单链表的设计和实现

### 单链表及其实现 #### 知识点概览 1. **单链表的概念** 2. **单链表的基本操作** - 插入 - 删除 - 查找 - 遍历 3. **单链表节点结构** 4. **单链表类的设计** #### 单链表的概念 单链表是一种线性数据结构，其中每个元素都存储在称为节点的结构中。每个节点包含两个部分：数据字段和一个指向下一个节点的指针。单链表的特点是只能从前一个节点访问到后一个节点，而不能反向访问。 #### 单链表的基本操作 单链表提供了一系列基本的操作来管理和操作链表中的元素。 ##### 插入操作 - **插入头结点**：将新节点插入到链表的头部。 - **插入尾结点**：将新节点添加到链表的末尾。 - **插入指定位置**：在链表的指定位置插入一个新节点。 ##### 删除操作 - **删除头结点**：移除链表的第一个元素。 - **删除尾结点**：移除链表的最后一个元素。 - **删除指定值**：移除链表中值为特定值的所有节点。 ##### 查找操作 - **查找指定位置的节点**：返回链表中指定位置的节点。 - **查找特定值**：查找链表中具有特定值的节点。 ##### 遍历操作 遍历整个链表，访问每个节点的数据。 #### 单链表节点结构 ```cpp template<class T> struct SLNode { T data; // 存储数据 SLNode<T>* next; // 指向下一个节点的指针 SLNode(SLNode* nextnode = NULL) : next(nextnode) {} SLNode(const T& item, SLNode* nextnode = NULL) : data(item), next(nextnode) {} }; ``` 每个节点包含一个数据成员`data`用于存储数据，以及一个指向下一个节点的指针`next`。构造函数提供了创建新节点的两种方式：一种是默认构造函数，另一种接受初始数据和下一个节点的指针。 #### 单链表类的设计 ```cpp template<class T> class SLList { private: SLNode<T>* head, *cur, *tail; // 头结点、当前节点、尾节点 int size; // 链表大小 public: SLList(); // 默认构造函数 SLList(T& item); // 带初始数据的构造函数 ~SLList(); // 析构函数 bool IsEmpty() const; // 判断是否为空 void Insert(const T item); // 在当前节点后插入 void InsertHead(const T item); // 在头部插入 void InsertTail(const T item); // 在尾部插入 void Delete(T& item); // 删除指定节点 void DeleteHead(T& item); // 删除头结点 void DeleteTail(T& item); // 删除尾结点 void FindK(int k, T& item) const; // 查找第k个节点 void FindCur(T& item) const; // 查找当前节点 int Search(const T& item) const; // 搜索特定值 void print(); // 打印链表 }; ``` ##### 构造与析构 - **构造函数**： - 默认构造函数初始化空链表。 - 带参数的构造函数创建一个带有初始数据的链表。 - **析构函数**：释放所有节点分配的内存。 ##### 插入操作实现 - **插入头结点**：如果链表为空，则同时更新头结点和尾结点；否则仅更新头结点。 - **插入当前节点后**：创建新节点，并将其插入到当前节点之后。如果当前节点是尾节点，则更新尾节点。 - **插入尾结点**：在尾节点后面插入新节点，并更新尾节点。 ##### 删除操作实现 - **删除节点**：首先检查链表是否为空或要删除的节点是否存在，然后删除该节点并更新指针。 - **删除头结点**：删除头结点并更新头结点。 - **删除尾结点**：找到前一个节点，并使其指针指向空。 #### 总结 本篇内容详细介绍了单链表的数据结构及其基本操作，包括插入、删除、查找等。通过模板化的设计，使得该链表可以存储任何类型的数据。此外，还实现了链表的基本管理功能，如判断链表是否为空、获取链表大小等。这些基础知识对于理解更复杂的链表操作非常有帮助。