单链表的基本操作

对链表的基本操作有：

• 创建链表：从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继的关系。

• 检索操作：按给定的结点索引号或检索条件，查找某个结点。若找到指定的结点，则称之为检索成功；否则检索失败。

• 插入操作：在结点间插入一个新的结点，使线性表长度增一。

• 删除操作：删除结点 node，使线性表长度减一。

#include<iostream>
#include<string.h>
using namespace std;
#define LI_SUCCESS 0
#define LI_WRONG_LOC 1
#define LI_EMPTY 2

//单列表的类定义与实现
class CLinkList
{
public:
	CLinkList();
	~CLinkList();
	typedef struct _NODE {
		int Data;
		_NODE* pNext;
	}NODE, *PNODE;
	bool IsEmpty();//判断链表是否为空
	int Length();//返回链表长度
	void Clear();//清空链表
	bool GetEle(//获取索引处元素内容
		int Index, //索引值
		int &Data //获取值的变量
	);
	int GetLoc( //获取内容为Data的第一个元素的位置
		int Data//要获取的内容
	);
	bool ListInsert(//在链表的某一位置插入一个结点
		int nLoc,//要插入的位置
		int nData,//要插入的数据
		int &nError//用于获取一个错误码
	);
	bool ListDelete(//在链表的某一位置删除一个结点，并返回被删除的数据
		int nLoc,//要删除的位置
		int & nData,//要删除的数据
		int &nError//用于获取一个错误码
	);

private:
	PNODE m_pHead;//头结点指针
	int m_Length;//链表长度

};

//构造函数用于初始化头节点指针和链表长度
CLinkList::CLinkList() :m_pHead(nullptr), m_Length(0) {}

//析构函数用于清空链表
CLinkList::~CLinkList() { Clear(); }

//判断链表是否为空
bool CLinkList::IsEmpty() {
	return (m_Length == 0) ? true : false;
}

//返回链表长度
int CLinkList::Length() {
	return m_Length;
}


//************************************
// Method:    Clear
// FullName:  CLinkList::Clear
// Access:    public 
// Returns:   void
// Function: 清空链表
//************************************
void CLinkList::Clear() {
	//1.判断链表是否为空
	if ((m_pHead == nullptr) || m_Length == 0)
		return;
	//2.链表不为空则开始清空链表
	PNODE pTemp = m_pHead;
	while (pTemp->pNext) {//从头指针开始将结点删除
		m_pHead = pTemp->pNext;
		delete pTemp;
		pTemp = m_pHead->pNext;
	}
	//3.删除最后一个结点，并将链表长度置0
	delete m_pHead;
	m_pHead = nullptr;//否则为悬空指针
	m_Length = 0;
}


//************************************
// Method:    GetEle
// FullName:  CLinkList::GetEle
// Access:    public 
// Returns:   bool
// Function: 获取索引处的元素内容
// Parameter: int Index
// Parameter: int & Data
//************************************
bool CLinkList::GetEle(int Index, int &Data) {
	//1.判断链表是否为空
	if ((m_pHead == nullptr) || m_Length == 0) {
		return false;
	}
	//2.判断索引是否超出范围
	if ((Index == 0) || Index > m_Length) {
		return false;
	}
	//3.循环开始查找索引点的前一个结点
	PNODE pTemp = m_pHead;
	for (int i = 1; i < Index; i++) {
		pTemp = pTemp->pNext;
	}
	//4.将元素复制到传出元素
	memcpy_s(&Data, sizeof(int), &pTemp->Data, sizeof(int));
	return true;
}


//************************************
// Method:    GetLoc
// FullName:  CLinkList::GetLoc
// Access:    public 
// Returns:   int
// Function: 获取内容为Data的第一个元素的位置
// Parameter: int Data
//************************************
int CLinkList::GetLoc(int Data) {
	//1.判断链表是否为空
	if ((m_pHead == nullptr) || m_Length == 0) {
		return -1;
	}
	//2.循环匹配链表内容，匹配到则返回i值
	PNODE pTemp = m_pHead;
	for (int i = 1; i < m_Length; i++) {
		if (memcmp(&Data, &pTemp->Data, sizeof(int)) == 0)
			return i;
		pTemp = pTemp->pNext;
	}
	//3.没找到则返回-1
	return -1;
}


//************************************
// Method:    ListInsert
// FullName:  CLinkList::ListInsert
// Access:    public 
// Returns:   bool
// Function: 在链表某一位置插入一个结点
// Parameter: int nLoc
// Parameter: int nData
// Parameter: int & nError
//************************************
bool CLinkList::ListInsert(int nLoc, int nData, int &nError) {
	//1.判断插入位置是否正确
	if (nLoc > m_Length) {
		nError = LI_WRONG_LOC;
		return false;
	}
	//2.判断头节点是否为空，若为空，直接在头结点插入元素
	if (m_pHead == nullptr) {
		m_pHead = new NODE;//新建一个要插入的结点指针
		m_pHead->pNext = nullptr;//否则为野指针
		m_pHead->Data = nData;
		nError = LI_SUCCESS;
		m_Length++;//链表长度增加
		return true;
	}
	//3.找到插入位置
	//3.1新建一个要插入的结点指针
	PNODE pPre = m_pHead;
	PNODE pTemp = new NODE;
	pTemp->Data = nData;
	pTemp->pNext = nullptr;
	//3.2判断是否向头结点之前插入，处理特殊情况
	if (nLoc == 0) {
		pTemp->pNext = m_pHead;
		m_pHead = pTemp;
		nError = LI_SUCCESS;
		m_Length++;
		return true;
	}
	//3.3正常情况,找到插入位置的前一结点
	for (int i = 0; i < nLoc - 1; i++) {
		pPre = pPre->pNext;
	}
	//4.执行插入操作
	pTemp->pNext = pPre->pNext;
	pPre->pNext = pTemp;
	//5.插入成功，长度自增并返回
	nError = LI_SUCCESS;
	m_Length++;
	return true;
}


//************************************
// Method:    ListDelete
// FullName:  CLinkList::ListDelete
// Access:    public 
// Returns:   bool
// Function: 在链表某一位置删除一个结点并返回被删除的数据
// Parameter: int nLoc
// Parameter: int & nData
// Parameter: int & nError
//************************************
bool CLinkList::ListDelete(int nLoc, int &nData, int &nError) {
	//1.判断链表是否为空
	if (m_pHead == nullptr || m_Length == 0) {
		nError = LI_EMPTY;
		return false;
	}
	//2.判断删除位置是否错误
	if (nLoc >= m_Length) {
		nError = LI_WRONG_LOC;
		return false;
	}
	//3.找到要删除的位置
	//3.1若要删除的是头结点
	if (nLoc == 0) {
		nData = m_pHead->Data;//给传出的数据复制
		PNODE pTemp = m_pHead;//用一个临时变量存储要被释放的头结点
		m_pHead = m_pHead->pNext;
		delete pTemp;
		pTemp = nullptr;
		m_Length--;
		nError = LI_SUCCESS;
		return true;
	}
	//3.2正常情况，循环查找要被删除结点的前一个结点
	PNODE pPre = m_pHead;
	PNODE pTemp = nullptr;
	for (int i = 0; i < nLoc - 1; i++) {
		pPre = pPre->pNext;
	}
	//4.执行删除操作
	pTemp = pPre->pNext;
	nData = pPre->Data;
	pPre->pNext = pPre->pNext->pNext;
	delete pTemp;
	pTemp = nullptr;
	m_Length--;
	nError = LI_SUCCESS;
	return true;
}
int main()
{
	CLinkList CList;
	int nError = 0;
	int a = 0;
	CList.ListInsert(0, 1, nError);
	CList.ListInsert(0, 2, nError);
	CList.ListInsert(0, 3, nError);
	CList.ListInsert(0, 4, nError);
	CList.ListInsert(0, 5, nError);
	CList.Length();
	CList.IsEmpty();
	CList.GetEle(1, a);
	CList.GetLoc(4);
	CList.ListDelete(0, a, nError);
	CList.ListDelete(3, a, nError);
	return 0;
}