C++语言实现线性表之链表实例
本文实例讲述了C++语言实现线性表之链表实现方法。分享给大家供大家参考。具体分析如下：
插入、删除结点的代码有点多，但这样提高了代码的可读性，且不增加时间复杂度，不会影响程序性能
#include<iostream>
usingnamespacestd;
template<typenameT>
classCList;
template<classT>
classNode
{
friendCList<T>;
private:
Tm_data;
Node*m_pNext;
};
template<classT>
classCList
{
public:
CList();
~CList();
boolIsEmpty();
voidAppend(constT&data);
voidDelete(constint&pos);
voidPrint();
intGetLength();
TFind(constint&pos);
voidInsert(constint&pos,constT&data);
private:
Node<T>*m_pHead;
Node<T>*m_pEnd;
intm_len;
voidCreate();
voidDestroy();
};
//为头结点分配空间
template<classT>
voidCList<T>::Create()
{
m_pHead=newNode<T>;
m_pEnd=newNode<T>;
m_pHead->m_pNext=NULL;
m_pEnd->m_pNext=m_pHead->m_pNext;
m_len=0;
}
template<classT>
CList<T>::CList()
{
Create();
}
//删除所有结点
template<classT>
voidCList<T>::Destroy()
{
Node<T>*pF=m_pHead->m_pNext;
Node<T>*pT;
while(pF)
{
pT=pF;
pF=pF->m_pNext;
deletepT;
}
}
template<classT>
CList<T>::~CList()
{
Destroy();
}
//判断是否为空
template<classT>
boolCList<T>::IsEmpty()
{
if(!m_pHead->m_pNext)
{
returntrue;
}
else
{
returnfalse;
}
}
//从表的最后加入一个元素
template<classT>
voidCList<T>::Append(constT&data)
{
Node<T>*pT=newNode<T>;
pT->m_data=data;
pT->m_pNext=NULL;
if(!m_pHead->m_pNext)
{
m_pHead->m_pNext=pT;
}
else
{
(m_pEnd->m_pNext)->m_pNext=pT;
}
m_pEnd->m_pNext=pT;
++m_len;
}
//删除一个元素
template<classT>
voidCList<T>::Delete(constint&pos)
{
if(pos<0||pos<m_len)
{
cout<<"位置不合法"<<endl;
return;
}
Node<T>*pPre=NULL;//存放前一个结点
Node<T>*pBehind=NULL;//存放后一个结点
Node<T>*pT=m_pHead->m_pNext;//目标结点
intix=-1;
while(pT)
{
++ix;
if(ix==pos-1-1)
{
pPre=pT;
}
elseif(ix==pos-1)
{
pBehind=pT->m_pNext;
break;
}
pT=pT->m_pNext;
}
if(!pPre)//如果指针为空则说明pos是指第一个元素
{
deletepT;
m_pHead->m_pNext=pBehind;
--m_len;
return;
}
if(!pBehind)//如果指针为空则说明pos是指最后一个元素
{
m_pEnd=pPre;
deletepT;
}
pPre->m_pNext=pBehind;
--m_len;
}
//输出所有数据
template<classT>
voidCList<T>::Print()
{
Node<T>*pT=m_pHead->m_pNext;
while(pT)
{
cout<<pT->m_data<<",";
pT=pT->m_pNext;
}
cout<<endl;
}
template<classT>
intCList<T>::GetLength()
{
returnm_len;
}
//查找数据
template<classT>
TCList<T>::Find(constint&pos)
{
if(pos<=0)
{
cout<<"输入不合法"<<endl;
returnNULL;
}
if(pos>m_len)
{
cout<<"超出表长"<<endl;
returnNULL;
}
inti=0;
Node<T>*pT=m_pHead->m_pNext;
while(pT)
{
++i;
if(i==pos)
{
returnpT->m_data;
}
pT=pT->m_pNext;
}
returnNULL;
}
template<classT>
voidCList<T>::Insert(constint&pos,constT&data)
{
if(pos<=0||pos>m_len)
{
cout<<"输入不合法"<<endl;
return;
}
inti=0;
Node<T>*pT=m_pHead->m_pNext;
Node<T>*pPre=NULL;
Node<T>*pBehind=NULL;
while(pT)
{
++i;
if(i==pos-1)
{
pPre=pT;
}
if(i==pos)
{
pBehind=pT->m_pNext;
break;
}
pT=pT->m_pNext;
}
Node<T>*pNew=newNode<T>;
pNew->m_data=data;
if(!pPre)//如果指针为空则说明pos是指第一个元素
{
pNew->m_pNext=m_pHead->m_pNext;
m_pHead->m_pNext=pNew;
++m_len;
return;
}
if(!pBehind)//如果指针为空则说明pos是指最后一个元素
{
m_pEnd->m_pNext=pNew;
}
pPre->m_pNext=pNew;
pNew->m_pNext=pT;
++m_len;
}
希望本文所述对大家的C++程序设计有所帮助。