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++程序设计有所帮助。