C++链表与标准模板库：从基础到应用

# C++ 链表与标准模板库：从基础到应用 ## 1. 链表基础操作 ### 1.1 创建新节点 在 C++ 中创建链表新节点时，使用动态内存分配。示例代码如下： ```cpp Entry* newEntry = new Entry; ``` 这里每次只分配一个 `Entry`，而非数组，所以不需要 `[]`。 ### 1.2 节点操作 对于新节点 `newEntry`，可以通过 `(*newEntry).name_` 访问其 `name_` 字段。不过，C++ 提供了更便捷的语法 `->`，例如 `newEntry->next_` 等同于 `(*newEntry).next_`。 ### 1.3 链表插入操作：`push_front` 向链表头部插入元素的代码如下： ```cpp template <typename T> void List<T>::push_front (const T& newElement) { Entry* newEntry = new Entry; newEntry->data_ = newElement; newEntry->next_ = start_; start_ = newEntry; } ``` 操作步骤如下： 1. 创建一个新的 `Entry` 节点。 2. 将新元素放入该节点的数据字段。 3. 将原 `start_` 的地址放入新节点的 `next_` 字段。 4. 更新 `start_` 为新节点的地址。 ### 1.4 链表删除操作：`pop_front` 最初尝试的代码如下： ```cpp template <typename T> void List<T>::pop_front() { if (empty()) throw Underflow(); delete start_; start_ = (*start_).next_; } ``` 但这样会导致程序崩溃，因为删除 `start_` 指向的节点后，再访问 `(*start_).next_` 会出错。正确的代码是： ```cpp template <typename T> void List<T>::pop_front() { if (empty()) throw Underflow(); Entry* temp = start_; start_ = (*start_).next_; delete temp; } ``` 操作步骤如下： 1. 检查链表是否为空，若为空则抛出异常。 2. 用临时指针 `temp` 保存 `start_` 的地址。 3. 更新 `start_` 为原 `start_` 的下一个节点。 4. 删除 `temp` 指向的节点。 ### 1.5 链表析构函数 链表的析构函数可以借助 `pop_front` 实现： ```cpp template <typename T> List<T>::~List () { while (!empty()) pop_front(); } ``` ### 1.6 指针作为条件 在编写代码时，常使用 `if (next_ != nullptr)` 或 `while (next_ != nullptr)`。由于 `nullptr` 类似于 0，代表“空”，所以可以简化为 `if (next_)`。 ### 1.7 链表模板 以下是完整的链表模板代码： ```cpp //class List: a linked list class #ifndef LIST_H #define LIST_H template <typename T> class List { public: class Underflow {}; List () { createEmptyList(); } List (const List <T>& other) : List () { copy(other); } ~List() { eraseAllElements(); } const List <T>& operator= (const List <T>& other) { eraseAllElements (); createEmptyList(); copy(other); return *this; } bool operator== (const List <T>& other) const; int size () const; bool empty () const { return size() == 0; } void push_front(const T& newElement); void pop_front (); const T& front () const; void print (std::ostream&) const; private: struct Entry { T data_; Entry* next_; }; Entry* start_; void copy(const List <T>& other); void eraseAllElements (); void createEmptyList () { start_ = nullptr; } }; template <typename T> inline std::ostream& operator<< (std::ostream& out, const List <T>& foo) { foo.print(out); return out; } template <typename T> void List<T>::eraseAllElements () { while (!empty()) pop_front(); } template <typename T> void List<T>::push_front (const T& newElement) { Entry* newEntry = new Entry; newEntry->data_ = newElement; newEntry->next_ = start_; start_ = newEntry; } template <typename T> void List<T>::pop_front() { if (empty()) throw Underflow(); Entry* temp = start_; start_ = start_->next_; delete temp; } template <typename T> void List<T>::copy(const List <T>& other) { Entry* lastEntry = nullptr; Entry* otherP = other.start_; while (otherP) { Entry* newEntry = new Entry; newEntry->data_ = otherP- ```