单链表之C++封装

前面的顺序表是用一组地址连续的存储单元来保存数据的，所以它具有随机存取的特点。即查找快速，但是做插入或删除动作是，需要移动大量元素，效率较低。

链表

链表是线性表的链式存储结构，它相比于顺序表，在插入和删除元素时，效率要高很多。

链表，是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

每个数据单元有两部分组成，一个是数据域，存储数据值；另一个是指针域，指向下一个数据单元，这样的数据单元叫做结点。当多个结点通过指针指向，关联起来，就形成了一个链，即链表。

单链表就是沿着单方向的链表。例如：A->B->C->D->... 只能顺序的连下去，即可以从A往下找其他元素，但是反之则不行。

单链表的封装：

.h文件：

#pragma once

class Node//定义链表中的一个节点
{
public:
	int Data;
	Node* pNext;
	void PrintNode();
};

//链表中除去头结点，第一个节点的位置是0，第二个节点的位置是1，依次2、3...

class CZzcSingleList
{
public:
	CZzcSingleList();//创建链表
	~CZzcSingleList();//销毁链表
	void ClearList();//清空链表
	bool IsListEmpty();//判断列表是否为空
	int GetListLenth();//返回链表的长度
	bool GetItemByPos(int n,Node* pNode);//获取链表中第i个节点的值
	int GetPosOfItem(Node* pNode);//获取节点的位置
	bool GetPreOfItem(Node* pCurNode,Node* pPreNode);//获取当前节点的前驱节点
	bool GetNextOfItem(Node* pCurNode,Node* pNextNode);//获取当前节点的后继节点
	void ListTraverse();//遍历链表
	bool InsertItemByPos(int n,Node* pNode);//将节点插入到链表的第i个位置
	bool TalkOutItemByPos(int n,Node* pNode);//将链表中第i个节点取出
	bool InsertItemBehindHead(Node* pNode);//将节点插入到头结点后面
	bool InsertItemBehindTail(Node* pNode);//将节点插入到尾节点的后面
private:
	Node* m_pList;
	int m_nLength;
};

#include "StdAfx.h"
#include "ZzcSingleList.h"
#include <iostream>
using namespace std;


void Node::PrintNode()
{
	cout<<Data<<endl;
}

CZzcSingleList::CZzcSingleList()
{
	m_pList = new Node;//定义一个链表的头结点
	m_pList->Data = 0;
	m_pList->pNext = NULL;
	m_nLength = 0;
}

CZzcSingleList::~CZzcSingleList()
{
	ClearList();
	delete m_pList;
}

bool CZzcSingleList::IsListEmpty()
{
	return m_nLength == 0?true:false;
}

int CZzcSingleList::GetListLenth()
{
	return m_nLength;
}

void CZzcSingleList::ClearList()
{
	Node* pCurNode = m_pList->pNext;

	while (pCurNode != NULL)
	{
		Node* pTemp = pCurNode->pNext;
		delete pCurNode;
		pCurNode = pTemp;
	}

	m_nLength = 0;

	m_pList->pNext = NULL;
}

bool CZzcSingleList::InsertItemBehindHead(Node* pNode)
{
	Node* pTempNdoe = m_pList->pNext;

	Node* pNewNode = new Node;
	if(!pNewNode) return false;

	pNewNode->Data = pNode->Data;

	m_pList->pNext = pNewNode;
	pNewNode->pNext = pTempNdoe;

	m_nLength++;

	return true;
}

bool CZzcSingleList::InsertItemBehindTail(Node* pNode)
{
	Node* pTempNode = m_pList;
	while (pTempNode->pNext)
	{
		pTempNode = pTempNode->pNext;
	}

	Node* pNewNode = new Node;
	if(!pNewNode) return false;
	pNewNode->Data = pNode->Data;

	pTempNode->pNext = pNewNode;
	pNewNode->pNext = NULL;

	m_nLength++;

	return true;
}

bool CZzcSingleList::InsertItemByPos(int n,Node* pNode)
{
	if(n < 0||n > m_nLength) return false;

	Node* pCurNode = m_pList;
	for (int i = 0;i < n;i++)
	{
		pCurNode = pCurNode->pNext;
	}

	Node* pNewNode = new Node;
	if(!pNewNode) return false;
	pNewNode->Data = pNode->Data;

	pNewNode->pNext = pCurNode->pNext;
	pCurNode->pNext = pNewNode;

	m_nLength++;

	return true;
}

bool CZzcSingleList::TalkOutItemByPos(int n,Node* pNode)
{
	if(n < 0||n >= m_nLength) return false;

	Node* pCurNode = m_pList;
	Node* pCurNodePre = NULL;
	for (int i = 0;i <= n;i++)
	{
		pCurNodePre = pCurNode;
		pCurNode = pCurNode->pNext;
	}

	pCurNodePre->pNext = pCurNode->pNext;

	pNode->Data = pCurNode->Data;

	delete pCurNode;
	pCurNode = NULL;

	m_nLength--;

	return true;
}

bool CZzcSingleList::GetItemByPos(int n,Node* pNode)
{
	if(n < 0||n >= m_nLength) return false;

	Node* pCurNode = m_pList;
	for (int i = 0;i <= n;i++)
	{
		pCurNode = pCurNode->pNext;
	}

	pNode->Data = pCurNode->Data;

	return true;
}

int CZzcSingleList::GetPosOfItem(Node* pNode)//第一次出现的位置
{
	Node* pCurNode = m_pList;
	int nPos = 0;
	while (pCurNode->pNext != NULL)
	{
		pCurNode = pCurNode->pNext;

		if (pCurNode->Data == pNode->Data)
		{
			return nPos;
		}
		nPos++;
	}

	return -1;
}

bool CZzcSingleList::GetPreOfItem(Node* pCurNode,Node* pPreNode)
{
	Node* pTempNode = m_pList->pNext;
	Node* pTempNodePre = NULL;

	while (pTempNode->pNext != NULL)
	{
		pTempNodePre = pTempNode;
		pTempNode = pTempNode->pNext;
		if (pTempNode->Data == pCurNode->Data)
		{
			pPreNode->Data = pTempNodePre->Data;

			return true;
		}
	}

	return false;
}

bool CZzcSingleList::GetNextOfItem(Node* pCurNode,Node* pNextNode)
{
	Node* pTempNode = m_pList->pNext;
	Node* pTempNodeNext = NULL;
	while (pTempNode->pNext != NULL)
	{
		pTempNodeNext = pTempNode->pNext;

		if (pTempNode->Data == pCurNode->Data)
		{
			pNextNode->Data = pTempNodeNext->Data;

			return true;
		}

		pTempNode = pTempNode->pNext;
	}

	return false;
}

void CZzcSingleList::ListTraverse()
{
	Node* pCurNode = m_pList->pNext;
	while (pCurNode)
	{
		pCurNode->PrintNode();
		pCurNode = pCurNode->pNext;
	}
}