155 lines
5.3 KiB
C++
155 lines
5.3 KiB
C++
// 设计一个模板类 LinkedList，实现基本的链表功能，包括插入节点（insert）、删除节点（remove）、查找节点（search）等操作， 通过全局友元函数，实现列表的打印功能。
|
||
#include <iostream>
|
||
|
||
using namespace std;
|
||
|
||
template <typename T>
|
||
class LinkedList
|
||
{
|
||
// // 使用友元函数模版的方式，可以避免重复声明
|
||
template <typename U>
|
||
friend ostream &operator<<(ostream &out, const LinkedList<U> &list);
|
||
|
||
private:
|
||
// 只能在类内部使用的私有结构体
|
||
struct Node // 节点结构体，定义数据结构，包括数据和指针
|
||
{
|
||
T val; // 节点的值
|
||
Node *next; // 指向下一个节点的指针
|
||
Node(T val) // 构造函数，用于初始化节点
|
||
{
|
||
this->val = val;
|
||
this->next = nullptr;
|
||
}
|
||
};
|
||
Node *head;
|
||
int size;
|
||
|
||
public:
|
||
LinkedList()
|
||
{
|
||
this->head = nullptr;
|
||
this->size = 0;
|
||
}
|
||
LinkedList(const LinkedList<T> &other)
|
||
{
|
||
this->head = nullptr;
|
||
this->size = 0;
|
||
Node *p = other.head;
|
||
while (p != nullptr)
|
||
{
|
||
this->insert(p->val);
|
||
p = p->next;
|
||
}
|
||
size = other.size; // 计数器赋值
|
||
}
|
||
~LinkedList()
|
||
{
|
||
Node *p = head; // 从头节点开始
|
||
while (p != nullptr) // 当前节点不为空时，循环
|
||
{
|
||
Node *q = p->next; // 保存下一个节点的指针
|
||
delete p; // 删除当前节点
|
||
p = q; // p 重新指向保存的下一个节点 q
|
||
}
|
||
|
||
size = 0; // 计数器清零
|
||
}
|
||
|
||
public:
|
||
LinkedList &insert(T val)
|
||
{
|
||
Node *node = new Node(val); // 创建新节点
|
||
if (head == nullptr)
|
||
{
|
||
head = node; // 如果头节点为空，直接将新节点赋值给头节点
|
||
return *this; // 如果头节点为空，直接返回
|
||
}
|
||
Node *p = head;
|
||
while (p->next != nullptr)
|
||
{
|
||
p = p->next; // 找到最后一个节点
|
||
}
|
||
p->next = node; // 将新节点插入到最后一个节点的后面
|
||
size++; // 计数器加一
|
||
return *this; // 返回当前对象
|
||
}
|
||
LinkedList &remove(T val)
|
||
{
|
||
if (head == nullptr)
|
||
{
|
||
cout << "链表为空，无法删除" << endl;
|
||
return *this; // 如果头节点为空，直接返回
|
||
}
|
||
Node *p = head;
|
||
if (p->val == val) // 如果头节点的值等于要删除的值
|
||
{
|
||
head = p->next; // 将头节点的下一个节点赋值给头节点
|
||
delete p; // 删除头节点
|
||
size--; // 计数器减一
|
||
return *this; // 返回当前对象
|
||
}
|
||
while (p->next != nullptr && p->next->val != val)
|
||
{
|
||
p = p->next; // 找到要删除的节点的前一个节点
|
||
}
|
||
if (p->next == nullptr) // 找到最后也没有找到要删除的节点
|
||
{
|
||
cout << "未找到要删除的节点" << endl;
|
||
return *this; // 如果未找到要删除的节点，直接返回
|
||
}
|
||
Node *q = p->next; // 保存要删除的节点
|
||
p->next = q->next; // 将要删除的节点的下一个节点赋值给要删除的节点的前一个节点的下一个节点
|
||
delete q; // 删除要删除的节点
|
||
size--; // 计数器减一
|
||
return *this; // 返回当前对象
|
||
}
|
||
void search(T val)
|
||
{
|
||
Node *p = head;
|
||
while (p != nullptr && p->val != val)
|
||
{
|
||
p = p->next; // 找到要删除的节点的前一个节点
|
||
}
|
||
if (p == nullptr) // 找到最后也没有找到要查找的节点
|
||
{
|
||
cout << val << " 未找到" << endl;
|
||
return;
|
||
}
|
||
cout << val << " 已找到" << endl;
|
||
return;
|
||
}
|
||
};
|
||
|
||
template <typename U>
|
||
ostream &operator<<(ostream &out, const LinkedList<U> &list)
|
||
{
|
||
/*
|
||
typename 关键字告诉编译器 LinkedList<U>::Node 是一个类型名，而不是一个成员变量
|
||
LinkedList<U>::Node 表示 LinkedList<U> 类的嵌套类型 Node
|
||
*p 指向 Node 类型的对象
|
||
list.head 是链表的头节点指针
|
||
*/
|
||
// 注意，由于 Node 是一个内部嵌套结构体，所以在使用时需要使用 typename 关键字来指示其是一个类型名
|
||
typename LinkedList<U>::Node *p = list.head; // 从头节点开始
|
||
while (p != nullptr) // 遍历链表
|
||
{
|
||
out << p->val << " "; // 输出节点的值
|
||
p = p->next; // 指向下一个节点
|
||
}
|
||
out << endl; // 最后输出换行
|
||
return out; // 返回输出流对象
|
||
}
|
||
|
||
int main()
|
||
{
|
||
LinkedList<double> list; // 创建一个链表
|
||
list.insert(1.1).insert(2.2).insert(3.3).insert(4.4).insert(5.5); // 插入节点
|
||
cout << list; // 输出链表
|
||
list.search(3.9); // 查找节点
|
||
list.search(4.4); // 查找节点
|
||
list.remove(3.3); // 删除节点
|
||
cout << list; // 输出链表
|
||
return 0;
|
||
}
|