【c++模板】模拟实现有模板的双向链表(List)（声明和定义分离）

时间：2021-08-10 23:17:24

List.h

#pragma once
/* 环境：  win7  64位  vs2012 */
#include <iostream>
using namespace std;

template<typename T>
struct Node
{
Node(const T& value)
:_value(value)
,_pPre(nullptr)
,_pNext(nullptr)
{}
T _value;
Node<T>* _pPre;
Node<T>* _pNext;
};

template<typename T>
class List
{
private:
size_t _size;
Node<T>* _pHead;
Node<T>* _pTail;
private:
// 清除所有元素
void _Destroy()
{
if (_pHead != nullptr)
{
Node<T>* pCur = _pHead;
while (pCur->_pNext)
{
pCur = pCur->_pNext;
delete pCur->_pPre;
}
delete pCur;
_pHead = _pTail = nullptr;
_size = 0;
}

}
// 返回一个新节点
Node<T>* _BuyNode(const T&value)
{
return new Node<T>(value);
}
public:
// 构造函数
List()
:_size(0)
,_pHead(nullptr)
,_pTail(nullptr)
{}

// 拷贝构造函数
List(const List<T>& list);

// 构造函数重载
List(size_t n, const T& value = T());

// 赋值操作符重载
List<T>& operator =(const List<T>& list);

// 输出运算符重载
template<typename T>
friend ostream& operator<<(ostream &_cout, const List<T>&list);

// 析构函数
~List();

// 尾插
void PushBack(const T& value);

// 尾删
void PopBack();

// 头插
void PushFront(const T& value);

// 头删
void PopFront();

// 查找
Node<T>* Find(const T& value);

// 插入
void Insert( Node<T>* pos, const T&value);

// 删除
void Erase(Node<T>* pos);

// 首元素
T& Front();
const T& Front()const;

// 尾元素
T& Back();
const T& Back()const;

// 判空
bool Empty()const;

// 元素个数
size_t Size()const;

};
List,cpp 

#pragma once
#include "List.h"
// 拷贝构造函数
template<typename T>
List<T>::List(const List<T>& list)
:_size(0)
,_pHead(nullptr)
,_pTail(nullptr)
{
Node<T>* pTemp = list._pHead;
while (pTemp)
{
PushBack(pTemp->_value);
pTemp = pTemp->_pNext;
}
}

// 构造函数重载
template<typename T>
List<T>::List(size_t n, const T& value = T())
:_size(0)
,_pHead(nullptr)
,_pTail(nullptr)
{
for (int idx = 0; idx < (int)n; idx++)
{
PushBack(value);
}
}

// 赋值操作符重载
template<typename T>
List<T>& List<T>::operator =(const List<T>& list)
{
if (this != &list)
{
_Destroy();
Node<T>* pTemp =list._pHead;
while (pTemp)
{
PushBack(pTemp->_value);
pTemp = pTemp->_pNext;
}
}
return *this;
}

// 输出运算符重载
template<class T>
ostream& operator<<(ostream &_cout, const List<T>&list)
{
if (list._pHead == nullptr)
{
cout << "链表以空。" << endl;
}
Node<T>* pCur = list._pHead;
while (pCur)
{
_cout<< "  " <<pCur->_value;
pCur = pCur->_pNext;
}
return _cout;
}

// 析构函数
template<typename T>
List<T>::~List()
{
_Destroy();
}

// 尾插
template<typename T>
void List<T>::PushBack(const T& value)
{
if (nullptr == _pHead)
{
_pHead = _pTail = _BuyNode(value);
}
else
{
_pTail->_pNext = _BuyNode(value);
_pTail->_pNext->_pPre = _pTail;
_pTail = _pTail->_pNext;
}
++_size;
}

// 尾删
template<typename T>
void List<T>::PopBack()
{
if (nullptr == _pHead)
{
cout <<" 删除失败，链表以空。"<<endl;
return;
}
else if(1 == _size)
{
delete _pHead;
_pHead = _pTail = nullptr;
--_size;
}
else
{
_pTail = _pTail->_pPre;
delete _pTail->_pNext;
_pTail->_pNext = nullptr;
--_size;
}
}

// 头插
template<typename T>
void List<T>::PushFront(const T& value)
{
if ( nullptr == _pHead)
{
_pHead = _pTail = _BuyNode(value);
}
else
{
_pHead->_pPre = _BuyNode(value);
_pHead->_pPre->_pNext = _pHead;
_pHead = _pHead->_pPre;
}
++_size;
}

// 头删
template<typename T>
void List<T>::PopFront()
{
if (nullptr == _pHead)
{
cout <<" 删除失败，链表以空。"<<endl;
return;
}
else if(1 == _size)
{
delete _pTail;
_pHead = _pTail = nullptr;
--_size;
}
else
{
_pHead = _pHead->_pNext;
delete _pHead->_pPre;
_pHead->_pPre = nullptr;
--_size;
}
}

// 查找
template <typename T>
Node<T>* List<T>::Find(const T&value)
{
Node<T>* temp = _pHead;
while (temp)
{
if (temp->_value == value)
{
return temp;
}
temp = temp->_pNext;
}
cout << "此元素不存在。" << endl;
return nullptr;
}

// 插入
template<typename T>
void List<T>::Insert( Node<T>* pos, const T&value)
{
if (pos == nullptr)
{
cout << "插入位置为空" << endl;
}
else
{
// 插入到后面
Node<T>* temp = _BuyNode(value);
pos->_pPre->_pNext = temp;
temp->_pPre = pos->_pPre;
temp->_pNext = pos;
pos->_pPre = temp;

/*  // 插入到后面
temp->_pNext = pos->_pNext;
pos->_pNext->_pPre = temp;
pos->_pNext = temp;
temp->_pPre = pos;*/
++_size;
}
}

// 删除
template<typename T>
void List<T>::Erase(Node<T>* pos)
{
if (pos == nullptr)
{
cout << "删除失败，位置为空" << endl;
}
else
{
pos->_pPre->_pNext = pos->_pNext;
pos->_pNext->_pPre = pos->_pPre;
--_size;
}
}

// 首元素 
template<typename T>
T& List<T>::Front()
{
return _pHead->_value;
};

template<typename T>
const T& List<T>::Front()const
{
return _pHead->_value;
};

// 尾元素 
template<typename T>
T& List<T>::Back()
{
return _pTail->_value;
};

template<typename T>
const T& List<T>::Back()const
{
return _pTail->_value;
};


// 判空
template<typename T>
bool List<T>::Empty()const
{
return 0 == _size;
}

// 元素个数
template<typename T>
size_t List<T>::Size()const
{
return _size;
}


Test.cpp 

#pragma once
#include "List.cpp"
#include <iostream>
#include <string>
using namespace std;

int  main()
{

//  测试 构造拷贝构造 输出 赋值 尾插运算符
// List<string> l1;
// l1.PushBack("aa");
// l1.PushBack("bb");
// l1.PushBack("cc");
// l1.PushBack("dd");
// 
// cout <<l1 << endl;
// List<string> l2(l1);
// cout <<l2 << endl;
// List<int> l3(5,1);
// cout << l3 << endl;
// List<string> l4;
// l4 = l1;
// cout << "l4::" << l4<<endl;
// l4.PushBack("xx");
// cout << "l4::" << l4<<endl;

//  测试尾删  头删
//List<string> l2;
// l2.PushBack("heiheihei");
// l2.PushBack("hahaha");
// l2.PushBack("xixixi");
// l2.PushFront("aaa");
// cout << "删前：" << l2<<endl;
//l2.PopFront();
// l2.PopFront();
// l2.PopFront();
// l2.PopFront();
// l2.PopBack();
// l2.PopBack();
// l2.PopBack();
// l2.PopBack();
//cout << "删后：" << l2<<endl;

// 测试 查找
// List<string> list1;
// list1.PushBack("1");
// list1.PushBack("2");
// list1.PushBack("3");
// list1.PushBack("4");
// cout << list1.Find("2") << endl;
// cout << list1.Find("2qqq") << endl;

//  测试 插入
// List<string> list1;
// list1.PushBack("1");
// list1.PushBack("2");
// list1.PushBack("3");
// list1.PushBack("4");
// cout<< "插入前：" << list1 << endl;
// list1.Insert(list1.Find("2"), "0");
// cout<< "插入后：" << list1 << endl;

//测试 删除
// List<string> list1;
// list1.PushBack("1");
// list1.PushBack("2");
// list1.PushBack("3");
// list1.PushBack("4");
// cout<< "删前：" << list1 << endl;
// list1.Erase(list1.Find("2"));
// cout<< "删后：" << list1 << endl;
// list1.Erase(list1.Find("2222"));


// List<string> l1;
// l1.PushBack("111");
// l1.PushBack("222");
// l1.PushBack("333");
// cout << "l1:" <<l1 << endl;
// cout<< "Front---" << l1.Front() <<endl;
// cout << " Back ---" << l1.Back() << endl;
// cout << "Empty:" << l1.Empty() << endl;
// cout << " Size: ---" << l1.Size() << endl;

return 0;
}


标签：

相关文章