链表：
#include<iostream>
using namespace std;
template<class T>
struct Node{
Tdate;
Node<T> * next;
Node():date(T()),next(NULL){}
};
template<class T>
class LinkList
{
public:
LinkList()
{
Node<T> * p=new Node<T>;
head=p;
p->next=NULL;
}
Node<T> * push_front(const T &);
Node<T> * push_back(const T &);
Node<T> * insert(int pos,const T &);
Node<T> * pop_front();
Node<T> * pop_back();
const T& front();
const T& back();
const T& del(int pos);
void delelm(const T &);
void clear();
int size();
void display();
~LinkList()
{
this->clear();
}
private:
Node<T> * head;
};
/*
在链表的前边插入数据
返回类型：Node<T> * 返回插入数据的位置指针
const T &e ：插入的数据
*/
template<class T>
Node<T> *LinkList<T>::push_front(const T & e)
{
Node<T> * p=new Node<T>;
head->date=e;
Node<T> * q=head;
p->next=head;
head=p;
return q;
}
/*
在链表的最后一个位置插入数据
返回类型：Node<T> * 返回插入数据的位置指针
const T &e ：插入的数据
*/
template<class T>
Node<T> *LinkList<T>::push_back(const T & e)
{
Node<T> *p=new Node<T>;
p->date=e;
p->next=NULL;
Node<T> * q=head;
Node<T> * k=NULL;
while(q)
{
k=q;
q=q->next;
}
k->next=p;
return p;
}
/*
删除链表的第一个数据
返回类型：Node<T> * 返回删除数据的后一个位置指针
*/
template<class T>
Node<T> *LinkList<T>::pop_front()
{
if(!head->next)
{
cout<<"链表为空，pop_front失败！"<<endl;
return NULL;
}
else
{
Node<T> *p=head->next;
head->next=p->next;
delete p;
return head->next;
}
}
/*
删除链表的最后一个数据
返回类型：Node<T> * 返回删除数据的前一个位置指针
*/
template<class T>
Node<T> *LinkList<T>::pop_back()
{
if(!head->next)
{
cout<<"链表为空，pop_back失败！"<<endl;
return NULL;
}
else
{
Node<T> * p=head->next;
Node<T> * q=NULL;
while(p->next)
{
q=p;
p=p->next;
}
q->next=NULL;
delete p;
return q;
}
}
/*
返回链表的第一个数据
返回类型：const T & 返回链表的第一个数据的引用
*/
template<class T>
const T & LinkList<T>::front()
{
if(!head->next)
{
cout<<"链表为空，front失败!"<<endl;
return NULL;
}
else
{
return head->next->date;
}
}
/*
返回链表的最后一个数据
返回类型：const T & 返回链表的最后一个数据的引用
*/
template<class T>
const T & LinkList<T>::back()
{
if(!head->next)
{
cout<<"链表为空，back失败!"<<endl;
return NULL;
}
else
{
Node<T> * p=head->next;
Node<T> * q=NULL;
while(p)
{
q=p;
p=p->next;
}
return q->date;
}
}
/*
在链表的任意位置插入数据
返回类型：Node<T>* 返回插入的数据的指针位置
int pos ：插入的数据的位置
const T & e：插入的数据
*/
template<class T>
Node<T> *LinkList<T>::insert(int pos,const T &e)
{
if(!head->next)
{
cout<<"链表为空，insert失败！"<<endl;
return NULL;
}
else if(pos>this->size())
{
cout<<"pos位置超出链表长度，insert失败！"<<endl;
return NULL;
}
else if(pos<0)
{
cout<<"pos位置不存在，insert失败!"<<endl;
return NULL;
}
else
{
int i=1;
Node<T> * p=head->next;
Node<T> * q=NULL;
while(i<pos)
{
q=p;
p=p->next;
i++;
}
Node<T> * k =newNode<T>;
k->date=e;
q->next=k;
k->next=p;
return k;
}
}
/*
删除任意位置的数据
返回类型：const T & 返回链表被删除数据的引用
int pos ：要删除数据的位置
*/
template<class T>
const T & LinkList<T>::del(int pos)
{
if(!head->next)
{
cout<<"链表为空,del失败!"<<endl;
return NULL;
}
else if(pos<0|pos>this->size())
{
cout<<"pos位置不存在，del失败！"<<endl;
return NULL;
}
else
{
int i=1;
Node<T> * p=head->next;
Node<T> * q=NULL;
while(i<pos)
{
q=p;
p=p->next;
i++;
}
q->next=p->next;
T e=p->date;
delete p;
return e;
}
}
/*
删除与e相同的数据
*/
template<class T>
void LinkList<T>::delelm(const T&e)
{
if(!head->next)
{
cout<<"链表为空，del失败！"<<endl;
return NULL;
}
else
{
Node<T> * p=head->next;
Node<T> * q=NULL;
while(p->date!=e)
{
q=p;
p=p->next;
}
q->next=p->next;
delete p;
}
}
/*
返回链表的长度
*/
template<class T>
int LinkList<T>::size()
{
if(!head->next)
{
cout<<"链表为空！"<<endl;
return 0;
}
else
{
Node<T> * p=head->next;
int i=1;
while(p->next)
{
p=p->next;
i++;
}
return i;
}
}
/*
清空链表
*/
template<class T>
void LinkList<T>::clear()
{
Node<T> * p=head;
while(p)
{
head=p;
p=p->next;
deletehead;
}
}
/*
遍历输出链表中的数据
*/
template<class T>
void LinkList<T>::display()
{
if(!head->next)
{
cout<<"链表为空，display失败！"<<endl;
return ;
}
else
{
Node<T> * p=head->next;
while(p)
{
cout<<p->date<<",";
p=p->next;
}
cout<<endl;
}
}
int main()
{
LinkList<int> l;
l.push_back(10);
l.push_front(9);
l.push_back(8);
l.push_front(7);
l.display();
l.pop_back();
l.pop_front();
l.display();
cout<<"链表长度："<<l.size()<<endl;
l.push_back(3);
l.push_front(4);
l.insert(2,6);
l.display();
l.del(2);
l.delelm(9);
l.display();
l.clear();
return 0;
}