双向链表的类模板的实现
全部代码加详细注释 List.hpp写法1----将迭代器类，节点类和链表类分开写，变量不统一，书写较麻烦
/***************Node结点的定义************/
template<class T>
struct Node
{
T data;
Node<T>* prev, * next;
Node(T d = 0, Node<T>* p = NULL, Node<T>* n = NULL) :data(d), prev(p), next(n) {}
};
/***************迭代器的定义************/
//类做友元，要声明
template<class T> class List;
template<class T>
class const_iterator
{
protected:
Node<T>* current;
T& retrive()const { return current->data; }//常函数不能更改成员变量的值，这里不能更改指针指向，但是可以更改指针指向地址上存储的值
//转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
const_iterator(Node<T>* p) :current(p) {}
friend class List<T>;
public:
//默认迭代器指向内容为空
const_iterator() :current(NULL) {}
//const迭代器解引用得到的值不能进行修改，这里是常迭代器
//这里前置const规定了返回值不能修改，这里返回的值是指针指向的地址的值，因此这里不能修改指针的指向和指向的值
const T& operator*()const { return retrive(); }
//前置++
const_iterator& operator++()
{
current = current->next;
return *this;
}
//后置++
const_iterator operator++(int)
{
//保留旧值
const_iterator old = *this;
//新值后移
++(*this);
return old;
}
//前置--
const_iterator& operator--()
{
current = current->prev;
return *this;
}
//后置--
const_iterator operator--(int)
{
//保留旧值
const_iterator old = *this;
//新值前移
--(*this);
return old;
}
//==
bool operator==(const const_iterator& rhs)const
{
return current == rhs.current;
}
//!=
bool operator!=(const const_iterator& rhs)const
{
return current != rhs.current;
}
};
//List类模板做友元函数要在前面添加类模板声明
template<class T> class List;
template<class T>
class iterator : public const_iterator<T>
{
protected:
//转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
iterator(Node<T>* p) :const_iterator<T>(p) {}
friend class List<T>;
public:
iterator() {};
//用普通迭代器可以修改当前迭代器指向位置的值
T& operator*()
{
return const_iterator<T>::retrive();
}
//常对象调用----前置const不能作为重载条件，后置const可以
const T& operator*()const
{
return const_iterator<T>::operator*();
}
//************************************************************************
//前++
iterator& operator++()
{
const_iterator<T>::current = const_iterator<T>::current->next;
return *this;
}
//后置++
iterator operator++(int)
{
//保留旧值
iterator old = (*this);
//新值后移
++(*this);
return old;
}
//前置--
iterator& operator--()
{
const_iterator<T>::current = const_iterator<T>::current->prev;
return *this;
}
//后置--
iterator operator--(int)
{
//保留旧值
iterator old = *this;
--(*this);
return old;
}
//*******************************************************************
};
/***************链表类模板的定义************/
template<class T>
class List//有头链表
{
private:
Node<T>* head;// 头节点指针
Node<T>* tail;//尾节点指针
int size;//节点个数
//初始化函数
void init()
{
head = new Node<T>;//自动调用Node类的默认构造函数
tail = new Node<T>;
size = 0;
//头和尾都需要创建一个节点，用来维护指针域，而不是数据域
head->next = tail;
tail->prev = head;
}
public:
//默认构造函数
List() { init(); }
//复制构造函数
List(const List<T>& l)
{
//先初始化
init();
//再调用赋值运算符重载
operator=(l);
}
//赋值运算符重载
const List& operator=(const List& L);
//迭代器中的转换构造是在begin和end函数里面使用的
//开始迭代器---返回的迭代器已经可以间接操作head->next即第一个有效节点的位置
//注意这里返回的都是临时匿名迭代器对象
iterator<T> Begin() { return iterator<T>(head->next); }
const_iterator<T> Begin()const { return const_iterator<T>(head->next); }
//结束迭代器---返回的迭代器已经可以间接操作tail即最后一个有效节点的后一个位置
iterator<T> End() { return iterator<T>(tail); }
const_iterator<T> End()const { return const_iterator<T>(tail); }
//返回首元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
T& front() { return *Begin(); }
const T& front() const { return *Begin(); }
//返回尾元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
//但注意返回的应该是end迭代器前一个，即最后一个位置的有效元素
//这里迭代器重载了--运算符，因此迭代器--,就等于current指针前移
T& back() { return *(--End()); }
const T& back()const { return *(--End()); }
//头插---begin迭代器指向的是第一个有效位置，因此这里插入到第一个有效元素前
void push_front(const T& item)
{
Insert(Begin(), item);
}
//尾插函数---end迭代器指向最后一个有效元素后面一个位置，因此这里插入end迭代器之前，相当于插入的新元素成为了最后一个有效的元素
void push_back(const T& item)
{
Insert(End(), item);
}
//删除首节点---删除begin迭代器指向的第一个有效节点
void pop_front()
{
Erase(Begin());
}
//删除尾节点--删除end迭代器前面一个节点，因此end迭代器指向最后一个有效元素后面一个位置
void pop_back()
{
Erase(--End());//这里--end相当于current指针前移一位
}
//删除指定位置的函数
iterator<T> Erase(iterator<T> itr);
//插入节点的函数
iterator<T> Insert(iterator<T> itr, const T& item);
//获取节点个数
int Size()const { return size; }
//判空函数
bool empty()const { return size == 0; }
//清空----如果不为空，就一直进行头删操作
void clear() { while (!empty()) { pop_front(); } }
};
//插入节点的函数---插入指定迭代器位置之前
template<class T>
iterator<T> List<T>::Insert(iterator<T> itr, const T& item)
{
//这里需要用p指向当前迭代器的current指针
Node<T>* p = itr.current;
p->prev->next = new Node<T>(item, p->prev, p);
p->prev = p->prev->next;
size++;
//插入到当前节点之前---返回已经指向当前新插入值位置的迭代器
return iterator<T>(p->prev);
}
//删除指定位置的函数--返回删除当前迭代器的下一个位置
template<class T>
iterator<T> List<T>::Erase(iterator<T> itr)
{
//p用来临时保存，方便一会delete
Node<T>* p = itr.current;
iterator<T> re(p->next);//当前迭代器的下一个位置的迭代器
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
size--;
return re;
}
//赋值运算符重载
template<class T>
const List<T>& List<T>::operator=(const List<T>& L)
{
//清表
clear();
//逐个节点进行复制操作
for (const_iterator<T> itr = L.Begin(); itr != L.End(); ++itr)
{
push_back(*itr);
}
return *this;
}List.hpp第二种写法—迭代器类和节点类都嵌套到list类中，模板变量参数统一化，便于书写
#pragma once
#include<cstdlib>
#include<iostream>
using namespace std;
/***************链表类模板的定义************/
template<class T>
class List//有头链表
{
private:
struct Node
{
T data;
Node* prev, * next;
Node(T d = 0, Node* p = NULL, Node* n = NULL) :data(d), prev(p), next(n) {}
};
Node* head;// 头节点指针
Node* tail;//尾节点指针
int size;//节点个数
//初始化函数
void init()
{
head = new Node;
tail = new Node;
size = 0;
//头和尾都需要创建一个节点，用来维护指针域，而不是数据域
head->next = tail;
tail->prev = head;
}
public:
class const_iterator
{
protected:
Node* current;
T& retrive()const { return current->data; }
//转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
explicit const_iterator(Node* p) :current(p) {}
friend class List<T>;
public:
//默认迭代器指向内容为空
explicit const_iterator() :current(NULL) {}
//const迭代器解引用得到的值不能进行修改，这里是常迭代器
const T& operator*()const { return retrive(); }
//前置++
const_iterator& operator++()
{
current = current->next;
return *this;
}
//后置++
const_iterator operator++(int)
{
//保留旧值
const_iterator old = *this;
//新值后移
++(*this);
return old;
}
//前置--
const_iterator& operator--()
{
current = current->prev;
return *this;
}
//后置--
const_iterator operator--(int)
{
//保留旧值
const_iterator old = *this;
//新值前移
--(*this);
return old;
}
//==
bool operator==(const const_iterator& rhs)const
{
return current == rhs.current;
}
//!=
bool operator!=(const const_iterator& rhs)const
{
return current != rhs.current;
}
};
class iterator : public const_iterator
{
protected:
//转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
explicit iterator(Node* p) :const_iterator(p) {}
friend class List<T>;
public:
explicit iterator() {};
//用普通迭代器可以修改当前迭代器指向位置的值
T& operator*()
{
return const_iterator::retrive();
}
//常对象调用----前置const不能作为重载条件，后置const可以
const T& operator*()const
{
return const_iterator::operator*();
}
//前++
iterator& operator++()
{
const_iterator::current = const_iterator::current->next;
return *this;
}
// 后置++
iterator operator++(int)
{
//保留旧值
iterator old = (*this);
//新值后移
++(*this);
return old;
}
// 前置--
iterator& operator--()
{
const_iterator::current = const_iterator::current->prev;
return *this;
}
// 后置--
iterator operator--(int)
{
//保留旧值
iterator old = *this;
--(*this);
return old;
}
//*******************************************************************
};
//默认构造函数
List() { init(); }
//复制构造函数
List(const List<T>& l)
{
//先初始化
init();
//再调用赋值运算符重载
operator=(l);
}
//赋值运算符重载
const List& operator=(const List& L);
//迭代器中的转换构造是在begin和end函数里面使用的
//开始迭代器---返回的迭代器已经可以间接操作head->next即第一个有效节点的位置
//注意这里返回的都是临时匿名迭代器对象
iterator Begin() { return iterator(head->next); }
const_iterator Begin()const { return const_iterator(head->next); }
//结束迭代器---返回的迭代器已经可以间接操作tail即最后一个有效节点的后一个位置
iterator End() { return iterator(tail); }
const_iterator End()const { return const_iterator(tail); }
//返回首元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
T& front() { return *Begin(); }
const T& front() const { return *Begin(); }
//返回尾元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
//但注意返回的应该是end迭代器前一个，即最后一个位置的有效元素
//这里迭代器重载了--运算符，因此迭代器--,就等于current指针前移
T& back() { return *(--End()); }
const T& back()const { return *(--End()); }
//头插---begin迭代器指向的是第一个有效位置，因此这里插入到第一个有效元素前
void push_front(const T& item)
{
Insert(Begin(), item);
}
//尾插函数---end迭代器指向最后一个有效元素后面一个位置，因此这里插入end迭代器之前，相当于插入的新元素成为了最后一个有效的元素
void push_back(const T& item)
{
Insert(End(), item);
}
//删除首节点---删除begin迭代器指向的第一个有效节点
void pop_front()
{
Erase(Begin());
}
//删除尾节点--删除end迭代器前面一个节点，因此end迭代器指向最后一个有效元素后面一个位置
void pop_back()
{
Erase(--End());//这里--end相当于current指针前移一位
}
//删除指定位置的函数
iterator Erase(iterator itr);
//插入节点的函数
iterator Insert(iterator itr, const T& item);
//获取节点个数
int Size()const { return size; }
//判空函数
bool empty()const { return size == 0; }
//清空----如果不为空，就一直进行头删操作
void clear() { while (!empty()) { pop_front(); } }
};
//插入节点的函数---插入指定迭代器位置之前
template<class T>
typename List<T>::iterator List<T>::Insert(iterator itr, const T& item)
{
//这里需要用p指向当前迭代器的current指针
Node* p = itr.current;
p->prev->next = new Node(item, p->prev, p);
p->prev = p->prev->next;
size++;
//插入到当前节点之前---返回已经指向当前新插入值位置的迭代器
return iterator(p->prev);
}
//删除指定位置的函数--返回删除当前迭代器的下一个位置
template<class T>
typename List<T>::iterator List<T>::Erase(iterator itr)
{
//p用来临时保存，方便一会delete
Node* p = itr.current;
iterator re(p->next);//当前迭代器的下一个位置的迭代器
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
size--;
return re;
}
//赋值运算符重载
template<class T>
const List<T>& List<T>::operator=(const List<T>& L)
{
//清表
clear();
//逐个节点进行复制操作
for (const_iterator itr = L.Begin(); itr != L.End(); ++itr)
{
push_back(*itr);
}
return *this;
}main.cpp
#include <iostream>
#include"List.hpp" //用户头文件
using namespace std;
template<class Iterator> //在指定范围内输出元素
void display(Iterator first, Iterator last)
{
for (; first != last; ++first)
cout << *first << ' ';
cout << endl;
}
//交换两个节点的值
template<class Iterator,class T>
void swap(Iterator L1, Iterator L2,T temp)
{
temp = *L1;
*L1 = *L2;
*L2 = temp;
}
//选择排序
template<class Iterator>
void select_sort(Iterator first, Iterator last)
{
Iterator i, j, min;
for (i = first; i != last; ++i)
{
min = i;
//注意这里不能直接写j=i+1---->因为iterator我们没有重载+运算符
for (j =i,++j; j != last; ++j)
{
if ((*j) < (*min))//解引用迭代器得到的就是当前迭代器的指针域指向的data
min = j;
}
//交换节点存储的data值，而非改变指针指向，完成交换
if (i != min)
{
swap(i, min, *i);
}
//错误写法---因此temp=i,相当于temp的current指针和i的current指针指向同一块内存,当这块内存的值发生变化的时候，temp的指针指向的内容随之改变
//我们要的是用temp来保留一份i的current指向的data数据域的值
//if (i != min)
//{
// Iterator temp = i;
// *i = *min;
// *min = *temp;
//}
}
}
int main()
{
List<int> L;
for (int i = 0; i < 10; i++)
{
L.Insert(L.Begin(), i + 100);
}
display(L.Begin(), L.End());
L.Erase(L.Begin());
display(L.Begin(), L.End());
List<int> L2;
L2 = L;
display(L2.Begin(), L2.End());
for (int i = 0; i < 20; i++)
{
L2.Insert(L2.Begin(), i * 2);
}
display(L2.Begin(), L2.End());
L.Erase(L2.Begin());
display(L2.Begin(), L2.End());
const List<int> L3(L2);
display(L2.Begin(), L2.End());
cout << "未排序前: " << endl;
List<int> L5;
L5.push_back(2);
L5.push_back(5);
L5.push_back(3);
L5.push_back(6);
L5.push_back(8);
L5.push_back(10);
display(L5.Begin(), L5.End());
cout << "选择排序后:" << endl;
select_sort(L5.Begin(), L5.End());
display(L5.Begin(), L5.End());
List<int> L6 = L5;
cout << "L6= " << endl;
display(L6.Begin(), L6.End());
return 0;
}
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
总结:
- 如果类型是依赖于模板参数的限定名，那么在它之前必须加typename(除非是基类列表，或者在类的初始化成员列表中)
- 上面部分讲解有误，详细typename用法详情，可以参考下面这篇大佬写的文章 typename详细用法
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/04/26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
