C++支持泛型的单向链表
前言
该项目可以作为学习过程中实验性质的练习，涉及到的知识比较基础，可以作为检验C++掌握情况的考试。对于程序中不懂或忘记的名词和关键词，应该回顾并掌握。
编写或读懂该程序需要对C++有基本全面的了解。另外该程序也有可改进的地方，在后续会提出一些改进思路，有兴趣的同学可以继续思考并尝试。
代码量在200行左右。
功能
如果有兴趣可以自己根据需求编写，然后再来比较谁的版本更好。
支持泛型数据的单向链表。
实现功能：插入、删除、遍历、链接、多种初始化方式、支持拷贝和移动。
技术细节：
- 拷贝控制成员：构造、拷贝构造、移动构造、拷贝赋值、移动赋值、析构
- 类模板、嵌套类
- 动态内存管理
- 考虑异常安全
测试用例
这里测试内容比较长，需要大家耐心看完，如果你写了自己的程序，可以调用我的测试用例，看看程序会不会出现异常。
测试的方式比较原始和简陋，具体看代码中的注释即可。
另外，本程序拷贝控制成员较多，对于拷贝可能有多种情况，如果想要具体分析，可以在拷贝控制成员中输出相关的调试信息，看看与预期是否相符。
void print(List<int>& list, string s = "") {
cout << s << " ";
for (int i = 0; i < list.size(); ++i) {
cout << list[i] << " ";
}
cout << endl;
}
//测试越界访问
//在产生越界异常后，不应该对原对象产生影响
void errorTest(List<int>& list1) {
try {
cout << list1[5] << endl;
}
catch (out_of_range e) {
cout << e.what() << endl;
}
}
//测试越界删除
//在越界删除后，不应该对原对象产生影响
void errorTest2(List<int>& list1) {
try {
list1.del(0);
}
catch (out_of_range e) {
cout << e.what() << endl;
}
}
//测试移动操作
List<int> moveTest() {
List<int> list1 = { 1,2,3,4,5 };
List<int> list2 = { 6,7,8,9,10 };
List<int> list3 = list1 + list1;//调用移动构造
list3 = list1 + list2;//调用移动赋值
return list3;//返回调用移动构造
}
void test() {
List<int> list1;
errorTest2(list1);//list1无元素，删除抛出异常
List<int> list2({ 1,2,3,4,5 });//调用列表初始化
list1 = list2;//调用赋值运算符
errorTest(list1);//越界访问list1，抛出异常
print(list1, "list1:");
print(list2, "list2:");
list2.add(6);
List<int> list3 = list2;//调用拷贝构造
list2.del(0);
list2.del(list2.size() - 1);
print(list2, "after list2:");
print(list3, "list3:");
List<int> list4(5);
print(list4, "list4:");
list4.clear();
for (int i = 0; i < 5; ++i) {
list4.add(i, 0);
}
print(list4, "after list4:");
List<int> list5 = moveTest();//调用移动构造
print(list5, "list5:");
}
int main(){
test();
return 0;
}
输出结果：
invalid index
invalid index
list1: 1 2 3 4 5
list2: 1 2 3 4 5
after list2: 2 3 4 5
list3: 1 2 3 4 5 6
list4: 5
after list4: 4 3 2 1 0
list5: 1 2 3 4 5 6 7 8 9 10
内存泄露检测：对于内存泄漏的检测方法也比较原始，通过不断循环创建和销毁，看看内存是否有增长。如果在任务管理器中看到程序内存不断增长，说明有内存泄露问题。
int main(){
while(true)
test();
return 0;
}
类结构
template <typename T>
class List{
struct ListNode;//前置声明
public:
List() : m_count(0), m_head(nullptr) {};//默认构造函数，无头节点
List(T val) : m_count(1), m_head(new ListNode(val)) {}//生成头节点的构造函数
List(std::initializer_list<T>);//列表初始化的构造函数
List(List&);//拷贝构造函数
List(List&&) noexcept;//移动构造函数
~List() { clear(); };
T& operator[](int index);//重载下标运算符
List& operator=(List&);//重载赋值运算符
List& operator=(List&&) noexcept;//移动赋值
List operator+(List&);//链接两个链表
void clear();//清空链表
void add(T, int index = INT_MAX);//添加元素，默认添加到尾后
void del(int);//删除元素
int size() { return m_count; }//返回链表长度
private:
struct ListNode {//嵌套类定义
ListNode() = delete;
ListNode(T val) : value(val), next(nullptr) {}
T value;
ListNode* next;
};
ListNode* getByIndex(int);
int m_count;
ListNode* m_head;
};
功能实现
初始化
//列表初始化的构造函数，遍历列表il用到了迭代器
template<typename T>
List<T>::List(std::initializer_list<T> il){
ListNode* headNode = new ListNode(*il.begin()), *temp = headNode;
for (auto beg = il.begin() + 1; beg != il.end(); ++beg) {
temp->next = new ListNode(*beg);
temp = temp->next;
}
m_head = headNode;
m_count = static_cast<int>(il.end() - il.begin());
}
//拷贝初始化的构造函数
template <typename T>
List<T>::List(List& val) {
m_count = 0;
m_head = nullptr;
for (int i = 0; i < val.m_count; ++i) {
add(val[i], i);//调用添加元素的函数
}
}
//移动构造函数，当传入值是一个右值时调用
template <typename T> inline
List<T>::List(List&& val) noexcept : m_count(val.m_count), m_head(val.m_head){
val.m_head = nullptr;
val.m_count = 0;
}
获取元素
//获得第index个节点
//这里必须通过typename声明ListNode*是一个类型
template <typename T> typename
List<T>::ListNode* List<T>::getByIndex(int index) {
//异常安全，产生异常并不会对原对象产生影响
if (index >= m_count || index < 0)
throw std::out_of_range("invalid index");
ListNode* curNode = m_head;
for (int i = 0; i < index; ++i) {
curNode = curNode->next;
}
return curNode;
}
//获取第index个元素
template <typename T> inline
T& List<T>::operator[](int index) {
return getByIndex(index)->value;
}
添加元素
这里因为无法用数据成员作为默认实参，所以用了个并不正规的方法，将默认实参设置为int的最大值，并在函数内进行判断。
要想使用数据成员作为实参，可以参考这篇文章
这里有个关于动态内存管理和异常的注意细节，由于getByIndex函数可能抛出越界的异常，所以我们不能在getByIndex函数前进行new操作，这样会导致内存泄露。
//添加元素至第index个元素的前面
//输入0插入到头节点前，输入size插入到尾节点后
template <typename T>
void List<T>::add(T val, int index) {
if (index == INT_MAX)
index = m_count;
if (index == 0) {
ListNode* temp = m_head;
ListNode* newVal = new ListNode(val);
++m_count;
m_head = newVal;
m_head->next = temp;
return;
}
ListNode* curNode = getByIndex(index - 1);
ListNode* newVal = new ListNode(val);//防止内存泄露
++m_count;
if (curNode == nullptr) {
//如果链表中没有节点，创建一个头节点
m_head = newVal;
}else if (curNode->next == nullptr) {
//如果是尾节点，直接插入
curNode->next = newVal;
}else {
//节点位于中间
ListNode* temp = curNode->next;
curNode->next = newVal;
curNode->next->next = temp;
}
}
删除元素
//删除第index个节点
template <typename T>
void List<T>::del(int index) {
//异常安全，产生异常并不会对原对象产生影响
if(index >= m_count || index < 0)
throw std::out_of_range("invalid index");
--m_count;
if (index == 0) {
//如果是头节点
ListNode* temp = m_head->next;
delete m_head;
m_head = temp;
return;
}
ListNode* curNode = getByIndex(index - 1);
if(curNode->next->next == nullptr) {
//如果是尾节点，直接删除
delete curNode->next;
curNode->next = nullptr;
}else {
ListNode* temp = curNode->next;
curNode->next = curNode->next->next;
delete temp;
}
}
//清空链表
template <typename T>
void List<T>::clear() {
if (m_count == 0)
return;
ListNode* curNode = m_head;
ListNode* temp = curNode->next;
for (int i = 0; i < m_count; ++i) {
delete curNode;
curNode = temp;
if(temp != nullptr)
temp = temp->next;
}
m_head = nullptr;
m_count = 0;
}
赋值运算
//重载赋值运算符，复制等号右边的链表给左边
template <typename T>
List<T>& List<T>::operator=(List& val) {
if (&val == this)
return *this;
clear();
for (int i = 0; i < val.m_count; ++i) {
add(val[i], i);
}
return *this;
}
//移动赋值运算符
template <typename T>
List<T>& List<T>::operator=(List&& val) noexcept {
if (&val == this)
return *this;
clear();
m_count = val.m_count;
m_head = val.m_head;
val.m_count = 0;
val.m_head = nullptr;
return *this;
}
链接链表
//链接两个链表
template <typename T>
List<T> List<T>::operator+(List<T>& rhs) {
List<T> newList = *this;//需要先复制内容，执行拷贝构造
List<T> rList = rhs;//需要先复制内容，执行拷贝构造
newList.getByIndex(m_count - 1)->next = rList.m_head;
newList.m_count += rhs.m_count;
rList.m_head = nullptr;
rList.m_count = 0;
return newList;
}
扩展思考
本程序在异常安全中并没有考虑到内存空间不足的问题。当new一个对象时，如果内存空间不足，有可能返回一个空指针而不抛异常，这和编译器有关系。
当new出一个空指针而不抛出异常，程序继续执行会产生严重的错误。
但查阅资料，目前主流的编译器对C++标准都支持较好，当内存空间不足时new一个对象会直接抛出异常，而不会返回空指针，所以本程序并没有考虑内存空间不足的异常安全问题。
另外，你如果自己编写了一遍程序，可能也会感觉到动态内存管理的困难，即使只有200+行的程序，一不小心仍然会导致内存泄露。
本程序的另一个改进思路是引入智能指针，将动态内存的管理交托给智能指针，从而实现内存安全。但我仍然建议编写一遍传统指针的程序，这样才能对智能指针有更深的理解。
评论 |
0条评论