|
|
#ifndef LIST_HPP
|
|
|
#define LIST_HPP
|
|
|
|
|
|
#include <iostream>
|
|
|
#include "Node.hpp"
|
|
|
|
|
|
// 这里列举了链表类模板的最基本功能，对原教材当中的写法进行了修订
|
|
|
// 更多功能改进，见对应的实战练习
|
|
|
|
|
|
template <typename T>
|
|
|
class List
|
|
|
{
|
|
|
Node<T> *head, *tail; // 链表头指针和尾指针
|
|
|
public:
|
|
|
List(); // 只生成头结点
|
|
|
~List(); // 删除整个链表
|
|
|
void clear(); // 清空链表，只余表头结点
|
|
|
Node<T> *find(const T &data) const; // 返回数值为data的节点
|
|
|
int length() const; // 计算单链表长度
|
|
|
void print() const; // 打印链表的数据域
|
|
|
void insert_front(Node<T> *p); // 表头插入
|
|
|
void insert_rear(Node<T> *p); // 表尾插入
|
|
|
Node<T> *delete_node(Node<T> *p); // 删除并返回地址为p的节点
|
|
|
};
|
|
|
|
|
|
template <typename T>
|
|
|
List<T>::List()
|
|
|
{
|
|
|
// 当链表为空时，tail指向头节点，否则指向链表最后一个节点
|
|
|
head = tail = new Node<T>{};
|
|
|
}
|
|
|
|
|
|
template <typename T>
|
|
|
List<T>::~List()
|
|
|
{
|
|
|
clear();
|
|
|
delete head;
|
|
|
}
|
|
|
|
|
|
template <typename T>
|
|
|
void List<T>::clear()
|
|
|
{
|
|
|
while (head->link)
|
|
|
delete head->remove_after();
|
|
|
tail = head; // 务必注意本类当中的操作是否会影响tail
|
|
|
}
|
|
|
|
|
|
template <typename T>
|
|
|
Node<T> *List<T>::find(const T &data) const
|
|
|
{
|
|
|
Node<T> *tempP{head->link};
|
|
|
while (tempP && tempP->info != data)
|
|
|
tempP = tempP->link;
|
|
|
return tempP; // 搜索成功返回指点节点的指针，不成功返回nullptr
|
|
|
}
|
|
|
|
|
|
template <typename T>
|
|
|
int List<T>::length() const
|
|
|
{
|
|
|
int count{0};
|
|
|
Node<T> *tempP{head->link};
|
|
|
while (tempP)
|
|
|
{
|
|
|
tempP = tempP->link;
|
|
|
++count;
|
|
|
}
|
|
|
return count;
|
|
|
}
|
|
|
|
|
|
template <typename T>
|
|
|
void List<T>::print() const
|
|
|
{
|
|
|
Node<T> *tempP{head->link};
|
|
|
while (tempP)
|
|
|
{
|
|
|
//tempP->print();
|
|
|
std::cout << tempP->get_info() << '\t';
|
|
|
tempP = tempP->link;
|
|
|
}
|
|
|
std::cout << '\n';
|
|
|
}
|
|
|
|
|
|
template <typename T>
|
|
|
void List<T>::insert_front(Node<T> *p)
|
|
|
{
|
|
|
head->insert_after(p);
|
|
|
if (tail == head)
|
|
|
tail = p; // 注意可能修正tail
|
|
|
}
|
|
|
|
|
|
template <typename T>
|
|
|
void List<T>::insert_rear(Node<T> *p)
|
|
|
{
|
|
|
tail->insert_after(p);
|
|
|
tail = p;
|
|
|
}
|
|
|
|
|
|
template <typename T>
|
|
|
Node<T> *List<T>::delete_node(Node<T> *p)
|
|
|
{
|
|
|
Node<T> *tempP{head}; // 注意与之前的不同
|
|
|
while (tempP->link && tempP->link != p) // 找到p的位置
|
|
|
tempP = tempP->link;
|
|
|
if (p == tail)
|
|
|
tail = tempP; // 修正tail
|
|
|
return tempP->remove_after();
|
|
|
}
|
|
|
|
|
|
#endif |
