注：以下所有代码均在VS2010环境下测试
C语言实现单链表： http://blog.csdn.net/snow_5288/article/details/52524830
C++实现动态顺序表： http://blog.csdn.net/snow_5288/article/details/52878083
C++模拟双向链表 http://blog.csdn.net/snow_5288/article/details/52882167
动态顺序表：以前我们为其起名为Seqlist,加入模板之后，我们称其为容器，取名vector
实现代码：
#include<iostream>
using namespace std;
#include<assert.h>
bool CheckPODType(const char* TypeName)
{
char* type[] = {"int","double","float","char","long"};
return false;
}
template<typename T>
class Vector
{
public:
Vector();
Vector(const T arr[], size_t size);
Vector(const Vector& v);
Vector& operator=(const Vector& s);
~Vector();
public:
void PrintVector();
void PushBack(const T& data);
void PopBack();
void Insert(size_t pos, const T& data);
void Erase(size_t pos);
const T& operator[](size_t index)const;
T& operator[](size_t index);
T& Front();
const T& Front()const;
T& Back();
const T& Back()const;
bool Empty()const;
size_t Size()const;
size_t Capacity()const;
void Clear();
void Resize(size_t size);
private:
void _CheckCapacity()
{
if(_size >= _capacity)//需要扩容
{
T* temp = new T[_capacity*2];
memcpy(temp,_pData,_size*sizeof(T));
for(size_t idx = 0; idx<_size; idx++)
{
temp[idx] = _pData[idx];
}
delete []_pData;//释放旧空间
_pData = temp;//指向新空间
_capacity *= 2;//改变容量
}
}
private:
T* _pData;
size_t _capacity;
size_t _size;
};
template<typename T>
Vector<T>::Vector()
:_pData(new T[3])
,_capacity(3)
,_size(0)
{}
template<typename T>
Vector<T>::Vector(const T arr[], size_t size)
:_pData(new T(size))
,_capacity(size)
,_size(size)
{
//memcpy(_pData,arr,size*sizeof(T));
for(size_t idx = 0; idx<size; idx++)
{
_pData[idx] = arr[idx];
}
}
//普通版的拷贝构造函数
template<typename T>
Vector<T>::Vector(const Vector& v)
:_pData(new T[v._capacity])
,_size(v._size)
,_capacity(v._capacity)
{
for(size_t idx = 0; idx<size; idx++)
{
_pData[idx] = v._pData[idx];
}
}
/*
//简洁版的拷贝构造函数
template<typename T>
Vector<T>::Vector(const Vector& v)
:_pData(NULL)
,_size(v._size)
,_capacity(v._capacity)
{
Vector<T> temp(v._pData);
std::swap(_pData,temp);
}
*/
//普通版的赋值运算符重载
template<typename T>
Vector<T>& Vector<T>::operator=(const Vector& s)
{
if(this != &s)
{
T* temp = new T[v._size];//开辟新空间
for(size_t idx = 0; idx<size; idx++)//给新空间赋值
{
temp[idx] = v._pData[idx];
}
delete []_pData;//释放旧空间
_pData = temp;//指向新空间
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
/*
//简洁版的赋值运算符重载
template<typename T>
Vector<T>& Vector<T>::operator=(Vector s)
{
std::swap(*this,s);
return *this;
}
*/
template<typename T>
Vector<T>::~Vector()
{
if(NULL != _pData)
{
delete []_pData;
_pData = NULL;
}
}
template<typename T>
void Vector<T>::PrintVector()
{
if(_size == 0)
{
cout<<"end"<<endl;
return;
}
for(size_t i=0; i<_size; i++)
{
cout<<_pData[i]<<"->";
}
cout<<"end"<<endl;
}
template<typename T>
void Vector<T>::PushBack(const T& data)
{
assert(_pData);
_CheckCapacity();
_pData[_size++] = data;
}
template<typename T>
void Vector<T>::PopBack()
{
if(_size == 0)
{
cout<<"顺序表已空"<<endl;
return;
}
else
{
_size--;
}
}
template<typename T>
void Vector<T>::Insert(size_t pos, const T& data)
{
assert(pos>=0 && pos<=_size);
_CheckCapacity();
for(size_t i=_size; i>pos; i--)
{
_pData[i] = _pData[i-1];
}
_pData[pos] = data;
_size++;
}
template<typename T>
void Vector<T>::Erase(size_t pos)
{
assert((pos>=0) && (pos<=_size));
if(_size == 0)
{
cout<<"顺序表已空"<<endl;
return;
}
else
{
size_t i = 0;
for(i=pos; i<_size-1; i++)
{
_pData[i] = _pData[i+1];
}
_size--;
}
}
template<typename T>
const T& Vector<T>::operator[](size_t index)const
{
assert(index>=0 && index<_size);
return _pData[index];
}
template<typename T>
T& Vector<T>::operator[](size_t index)
{
assert(index>=0 && index<_size);
return _pData[index];
}
template<typename T>
T& Vector<T>::Front()
{
assert(_pData);
return _pData[0];
}
template<typename T>
const T& Vector<T>::Front()const
{
assert(_pData);
return _pData[0];
}
template<typename T>
T& Vector<T>::Back()
{
assert(_pData);
return _pData[_size-1];
}
template<typename T>
const T& Vector<T>::Back()const
{
assert(_pData);
return _pData[_size-1];
}
template<typename T>
bool Vector<T>::Empty()const
{
if(0 == _size)
return true;
else
return false;
}
template<typename T>
size_t Vector<T>::Size()const
{
assert(_pData);
return _size;
}
template<typename T>
size_t Vector<T>::Capacity()const
{
assert(_pData);
return _capacity;
}
template<typename T>
void Vector<T>::Clear()
{
_size = 0;
_capacity = 0;
if(NULL != _pData)
{
delete []_pData;
_pData = NULL;
}
}
template<typename T>
void Vector<T>::Resize(size_t size)
{
if(size > _size)
{
size_t temp = _size;
_size = size;
_CheckCapacity();
for(size_t idx=temp; idx<size; idx++)//将新开辟的空间赋值为0
{
_pData[idx] = 0;
}
}
else
{
_size = size;
}
}
void Funtest()
{
Vector<int> v;
v.PushBack(1);
v.PushBack(2);
v.PushBack(3);
v.PushBack(4);
v.PrintVector();
v.PopBack();
v.PopBack();
v.PrintVector();
v.PopBack();
v.PopBack();
v.PopBack();
v.PrintVector();
cout<<endl<<endl;
Vector<int> v1;
v1.PushBack(1);
v1.PushBack(2);
v1.PushBack(3);
v1.PushBack(4);
v1.PrintVector();
v1.Insert(2,6);
v1.Insert(0,7);
int size = v1.Size();
v1.Insert(size,8);
v1.PrintVector();
v1.Erase(0);
v1.Erase(1);
v1.Erase(size-1);
v1.PrintVector();
cout<<endl<<endl;
Vector<int> v2;
v2.PushBack(1);
v2.PushBack(2);
v2.PushBack(3);
v2.PushBack(4);
v2.PrintVector();
v2[2] = 8;
v2.PrintVector();
cout<<"front:"<<v2.Front()<<endl;
cout<<"back:"<<v2.Back()<<endl;
int boo = v2.Empty();
cout<<boo<<endl;
cout<<"size:"<<v2.Size()<<endl;
cout<<"capacity:"<<v2.Capacity()<<endl;
v2.PrintVector();
v2.Resize(10);//增容
v2.PrintVector();
v2.Resize(2);//缩容
v2.PrintVector();
v2.Clear();
v2.PrintVector();
cout<<endl<<endl;
}
int main()
{
Funtest();
system("pause");
return 0;
}
运行结果：
双向链表：以前我们为其起名为Linklist,加入模板之后，我们也称其为容器，取名list
代码实现：
#include <iostream>
using namespace std;
#include <assert.h>
template<typename T>
struct Node
{
public:
friend ostream& operator<<(ostream& _cout, const Node<T>& n)
{
_cout<<n._data;
return _cout;
}
public:
Node<T>* _pNext;
Node<T>* _pPre;
T _data;
};
template<typename T>
class List
{
public:
template<typename T>
friend ostream& operator<<(ostream& _cout, const List<T>& l)
{
Node<T>* pCur = l._pHead;
while(pCur)
{
_cout<<pCur->_data<<"<-->";
pCur = pCur->_pNext;
}
_cout<<"end";
return _cout;
}
List()
:_size(0)
,_pHead(NULL)
,_pTail(NULL)
{}
List(T arr[], size_t size)
:_pHead(NULL)
,_pTail(NULL)
,_size(0)
{
size_t i = 0;
for(i=0; i<_size; i++)
{
PushBack(arr[i]);
}
}
List(const T& l)
:_size(0)
,_pHead(NULL)
,_pTail(NULL)
{
Node<T>* temp = _pHead;
_pHead->_pPre = NULL;
Node<T>* CurNode = l._pHead;
while(CurNode)
{
temp = CurNode;
CurNode = CurNode->_pNext;
temp = temp->_pNext;
_size++;
}
temp->_pNext = NULL;
}
T& operator=(const List& l)
{
if(this != &l)
{
Node<T>* temp = _pHead;
_pHead->_pPre = NULL;
Node<T>* CurNode = l._pHead;
while(CurNode)
{
temp = CurNode;
CurNode = CurNode->_pNext;
temp = temp->_pNext;
_size++;
}
temp->_pNext = NULL;
}
}
~List()
{
if(NULL != this)
{
Clear();
}
}
void PushBack(const T& data);
void PopBack();
void PushFront(const T& data);
void PopFront();
bool Empty()const;
Node<T>* Find(const T& data)const;
void Insert(Node<T>* pos, const T& data);
void Erase(Node<T>* pos);
void Remove(const T& data);
void RemoveAll(const T& data);
void Sort();
size_t Size()const;
void Clear();
Node<T>& Front();
const Node<T>& Front()const;
Node<T>& Back();
Node<T>& Back()const;
private:
Node<T>* BuyNode(const T& data)
{
Node<T>* NewNode = new Node<T>;
NewNode->_data = data;
return NewNode;
}
private:
size_t _size;
Node<T>* _pHead;
Node<T>* _pTail;
};
template<typename T>
void List<T>::PushBack(const T& data)
{
if(_size == 0)//链表为空
{
_pHead = _pTail = BuyNode(data);
_pHead->_pPre = NULL;
_pTail->_pNext = NULL;
}
else//链表不为空
{
Node<T>* temp = BuyNode(data);
Node<T>* CurNode = _pHead;
while(CurNode->_pNext)
{
CurNode = CurNode->_pNext;
}
temp->_pPre = CurNode;
CurNode->_pNext = temp;
temp->_pNext = NULL;
_pTail = temp;
}
_size++;
}
template<typename T>
void List<T>::PopBack()
{
if(_size == 0)//链表为空
{
cout<<"链表为空"<<endl;
return;
}
else if(_size == 1)//链表仅有一个节点
{
Node<T>* pDel = _pTail;
delete pDel;
_pHead = _pTail = NULL;
_size--;
}
else//有多个节点
{
Node<T>* pDel = _pTail;
_pTail = _pTail->_pPre;
_pTail->_pNext = NULL;
delete pDel;
_size--;
}
}
template<typename T>
void List<T>::PushFront(const T& data)
{
if(_size == 0)//链表为空
{
_pHead = BuyNode(data);
_pTail = _pHead;
_pHead->_pPre = NULL;
_pTail->_pNext = NULL;
}
else//链表不为空
{
Node<T>* temp = BuyNode(data);
temp->_pNext = _pHead;
_pHead->_pPre = temp;
_pHead = temp;
}
_size++;
}
template<typename T>
void List<T>::PopFront()
{
if(_size == 0)
{
cout<<"链表已空"<<endl;
return;
}
else if(_size == 1)
{
Node<T>* pDel = _pHead;
delete pDel;
_pHead = _pTail = NULL;
_size--;
}
else
{
Node<T>* pDel = _pHead;
_pHead = _pHead->_pNext;
_pHead->_pPre = NULL;
delete pDel;
_size--;
}
}
template<typename T>
bool List<T>::Empty()const
{
return _size==0;
}
template<typename T>
Node<T>* List<T>::Find(const T& data)const
{
Node<T>* pCur = _pHead;
while(pCur)
{
if(pCur->_data == data)
return pCur;
else
pCur = pCur->_pNext;
}
return pCur;
}
template<typename T>
void List<T>::Insert(Node<T>* pos, const T& data)//插入节点之前
{
if(pos == _pHead)
{
PushFront(data);
}
else
{
Node<T>* pCur = _pHead;
while(pCur->_pNext != pos)
{
pCur = pCur->_pNext;
}
Node<T>* temp = BuyNode(data);
pCur->_pNext = temp;
pos->_pPre = temp;
temp->_pPre = pCur;
temp->_pNext = pos;
}
_size++;
}
template<typename T>
void List<T>::Erase(Node<T>* pos)
{
if(pos == _pHead)
{
PopFront();
}
else if(pos == _pTail)
{
PopBack();
}
else
{
Node<T>* pDel = _pHead;
Node<T>* pPre = _pHead;
while((pDel != pos) && pDel->_pNext)
{
pPre = pDel;
pDel = pDel->_pNext;
}
pPre->_pNext = pDel->_pNext;
pos->_pNext->_pPre = pPre;
delete pDel;
}
_size--;
}
/*
//简洁版Remove
template<typename T>
void List<T>::Remove(const T& data)//删除第一个值为data的数据
{
Erase(Find(data));
}
*/
//普通版Remove
template<typename T>
void List<T>::Remove(const T& data)
{
Node<T> *pos=this->Find(data);
if(pos != 0)
{
if((!(pos->_pPre)) && pos->_pNext) //删除第一个结点
{
Node<T> *tmp = pos->_pNext;
tmp->_pPre = NULL;
_pHead = tmp;
}
else if(pos->_pPre && (!(pos->_pNext))) //删除最后一个结点
{
Node<T> *tmp = pos->_pPre;
tmp->_pNext = NULL;
_pTail = tmp;
}
else //删除中间节点
{
Node<T> *front = pos->_pPre;
Node<T> *next = pos->_pNext;
next->_pPre = front;
front->_pNext = next;
}
delete pos;
pos = 0;
}
}
template<typename T>
void List<T>::RemoveAll(const T& data)
{
Node<T> *cur = _pHead;
Node<T> *ret = this->Find(data);
if(ret != _pHead) //可删除第一个结点不是要删除的元素
{
while(cur->_pNext) //删除不了最后一个节点
{
Remove(data);
cur = cur->_pNext;
}
if(_pTail->_data == data)
PopBack();
}
}
template<typename T>
void List<T>::Sort()
{
int flag = 1;
Node<T> *cur = _pHead;
Node<T> *tail = NULL;
while(cur != tail)
{
while(cur->_pNext != tail)
{
if(cur->_data > cur->_pNext->_data)
{
T tmp = cur->_data;
cur->_data = cur->_pNext->_data;
cur->_pNext->_data =tmp;
flag = 0;
}
cur=cur->_pNext;
}
if(flag == 1)
break;
tail = cur;
cur = _pHead;
}
}
template<typename T>
size_t List<T>::Size()const
{
return _size;
}
template<typename T>
void List<T>::Clear()
{
if(_size == 0)
{
return;
}
else
{
Node<T>* pDel = _pHead;
Node<T>* pCur = _pHead->_pNext;
while(pCur->_pNext)
{
pCur = pCur->_pNext;
pDel = pCur->_pPre;
delete pDel;
}
delete pCur;
_pTail = NULL;
pDel = _pHead;
delete pDel;
_pHead = NULL;
_size = 0;
}
}
template<typename T>
Node<T>& List<T>::Front()
{
assert(Empty());
return *_pHead;
}
template<typename T>
const Node<T>& List<T>::Front()const
{
assert(Empty());
return *_pHead;
}
template<typename T>
Node<T>& List<T>::Back()
{
assert(Empty());
return *_pTail;
}
template<typename T>
Node<T>& List<T>::Back()const
{
assert(Empty());
return *_pTail;
}
int main()
{
List<int> l1;
l1.PushBack(1);
l1.PushBack(2);
l1.PushBack(3);
l1.PushBack(4);
cout<<l1<<endl;
l1.PopBack();
l1.PopBack();
l1.PopBack();
l1.PopBack();
cout<<l1<<endl;
l1.PushFront(4);
l1.PushFront(3);
l1.PushFront(2);
l1.PushFront(1);
cout<<l1<<endl;
l1.PopFront();
l1.PopFront();
l1.PopFront();
l1.PopFront();
cout<<l1<<endl;
size_t boo = l1.Empty();
cout<<boo<<endl;
cout<<endl<<endl;
List<int> l2;
l2.PushFront(5);
cout<<l2<<endl;
l2.PushBack(1);
l2.PushBack(2);
l2.PushBack(3);
cout<<l2<<endl;
l2.PushFront(4);
cout<<l2<<endl;
Node<int>* ret = l2.Find(4);
ret = l2.Find(2);
l2.Erase(ret);
cout<<l2<<endl;
l2.Insert(l2.Find(3),6);
cout<<l2<<endl;
l2.Sort();
cout<<l2<<endl;
ret = l2.Find(3);
ret = l2.Find(6);
l2.PopFront();
cout<<l2<<endl;
l2.PopFront();
l2.PopFront();
l2.PopFront();
cout<<l2<<endl;
l2.PopFront();
l2.Clear();
cout<<l2<<endl;
cout<<endl<<endl;
List<int> l3;
l3.PushBack(1);
l3.PushBack(2);
l3.PushBack(1);
l3.PushBack(1);
cout<<l3<<endl;
l3.Remove(1);
cout<<l3<<endl;
l3.RemoveAll(1);
cout<<l3<<endl;
system("pause");
return 0;
}
运行结果：
