【代码】线性表之链表--C++语言描述
插入、删除结点的代码有点多，但这样提高了代码的可读性，且不增加时间复杂度，不会影响程序性能
#include <iostream>using namespace std;template<typename T>class CList;template<class T>class Node{friend CList<T>;private:T m_data;Node *m_pNext;};template<class T>class CList{public:CList();~CList();bool IsEmpty();void Append(const T &data);void Delete(const int &pos);void Print();int GetLength();T Find(const int &pos);void Insert(const int &pos,const T &data);private:Node<T> *m_pHead;Node<T> *m_pEnd;int m_len;void Create();void Destroy();};//为头结点分配空间template<class T>void CList<T>::Create(){m_pHead = new Node<T>;m_pEnd = new Node<T>;m_pHead->m_pNext = NULL;m_pEnd->m_pNext = m_pHead->m_pNext;m_len = 0;}template<class T>CList<T>::CList(){Create();}//删除所有结点template<class T>void CList<T>::Destroy(){Node<T> *pF = m_pHead->m_pNext;Node<T> *pT;while(pF){pT = pF;pF = pF->m_pNext;delete pT;}}template<class T>CList<T>::~CList(){Destroy();}//判断是否为空template<class T>bool CList<T>::IsEmpty(){if(!m_pHead->m_pNext){return true;}else{return false;}}//从表的最后加入一个元素template<class T>void CList<T>::Append(const T &data){Node<T> *pT = new Node<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<class T>void CList<T>::Delete(const int &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;//目标结点int ix = -1;while(pT){++ix;if(ix == pos - 1 - 1){pPre = pT;}else if(ix == pos - 1){pBehind = pT->m_pNext;break;}pT = pT->m_pNext;}if(!pPre)//如果指针为空则说明pos是指第一个元素{delete pT;m_pHead->m_pNext = pBehind;--m_len;return;}if(!pBehind)//如果指针为空则说明pos是指最后一个元素{m_pEnd = pPre;delete pT;}pPre->m_pNext = pBehind;--m_len;}//输出所有数据template<class T>void CList<T>::Print(){Node<T> *pT = m_pHead->m_pNext;while(pT){cout<<pT->m_data<<",";pT = pT->m_pNext;}cout<<endl;}template<class T>int CList<T>::GetLength(){return m_len;}//查找数据template<class T>T CList<T>::Find(const int &pos){if(pos <= 0){cout<<"输入不合法"<<endl;return NULL;}if(pos > m_len){cout<<"超出表长"<<endl;return NULL;}int i = 0;Node<T> *pT = m_pHead->m_pNext;while(pT){++i;if(i == pos){return pT->m_data;}pT = pT->m_pNext;}return NULL;}template<class T>void CList<T>::Insert(const int &pos,const T &data){if(pos <= 0 || pos >m_len){cout<<"输入不合法"<<endl;return;}int i = 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 = new Node<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;}