【数据结构】线性表之链表--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;

}