[数据结构与算法]【数据结构基础_双向链表（有[*pHead]和[*pEnd]）_(C++)】

此文为上一篇文章改为C++格式实现（多文件形式）

头文件

#pragma once
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct Node
{
	int iData;
	struct Node* pNext;		//记录后一个节点地址
	struct Node* pPre;		//记录前一个节点的地址
};

class SX
{
private:
	struct Node* g_pHead = NULL;
	struct Node* g_pEnd = NULL;
	int g_iNodeCount = 0;

private:
	//释放链表
	void FreeList();
public:
	SX();
	~SX();
public:
	//尾添加
	void AddToEnd(int iData);
	
	//遍历链表 1.正向 2.反向
	void LookZheng();
	void LookFan();
	//头添加
	void AddToHead(int iData);
	//指定的下标位置添加
	void InsertNodeByIndex(int iIndex, int iCount, int iData);
	//指定数据位置添加节点
	void InsertNodeByData(int iValue, int iData);
	//根据下标查询
	struct Node* GetByIndex(int iIndex);
	//根据数据查询
	struct Node* GetByData(int iData);
	//修改
	void ChangeByIndex(int iIndex, int iValue);
	void ChangeByData(int iData, int iValue);
	//根据下标删除节点
	void DeleteByIndex(int iIndex);
	//删除节点
	void DeleteNode(struct Node* pTemp);
	//根据数据删除所有与之相同的节点
	void DeleteByData(int iValue);
};

函数实现

#include"sx.h"

SX::SX()
{

}
SX::~SX()
{
	FreeList();
}

void SX::DeleteByData(int iValue)
{
	//while (1)
	//{
	//	//找
	//	struct Node* pTemp = GetByData(iValue);
	//	if (pTemp == NULL)
	//		break;
	//	DeleteNode(pTemp);
	//}
	struct Node* pTemp = NULL;
	while (NULL != (pTemp = GetByData(iValue)))
		DeleteNode(pTemp);
}
void SX::DeleteNode(struct Node* pTemp)
{
	//是否为头结点
	if (pTemp == g_pHead)
	{
		if (g_pHead == g_pEnd)
		{
			delete g_pHead;
			g_pHead = NULL;
			g_pEnd = NULL;
		}
		else
		{
			//1.
			//记录头
			//struct Node* pT = g_pHead;
			头指向下一个
			//g_pHead = g_pHead->pNext;
			头前设置为NULL
			//g_pHead->pPre = NULL;
			释放
			//free(pT)
			2.记录头
			头指向下一个
			//g_pHead = g_pHead->pNext;
			头前设置为NULL
			//g_pHead->pPre = NULL;
			释放
			//free(pTemp);

			//3.头指向下一个
			g_pHead = g_pHead->pNext;
			//释放头的前一个节点
			delete (g_pHead->pPre);
			//头前置NULL
			g_pHead->pPre = NULL;
		}
	}
	//尾节点
	else if (pTemp == g_pEnd)
	{
		g_pEnd = g_pEnd->pPre;
		delete(g_pEnd->pNext);
		g_pEnd->pNext = NULL;
	}
	//中间节点
	else
	{
		//让其前一个节点的pNext 指针指向其后一个节点
		pTemp->pPre->pNext = pTemp->pNext;
		//让其后一个节点的pPre 指针指向其前一个节点
		pTemp->pNext->pPre = pTemp->pPre;
		//释放此节点
		delete (pTemp);
	}
	g_iNodeCount--;
}
void SX::DeleteByIndex(int iIndex)
{
	//查找节点
	struct Node* pTemp = GetByIndex(iIndex);
	//判断是否找到
	if (pTemp != NULL)
	{
		//找到了删除节点
		DeleteNode(pTemp);
	}
}
void SX::ChangeByData(int iData, int iValue)
{
	//参数合法性检测
	if (NULL == g_pHead)
		return;
	//循环遍历
	struct Node* pTemp = g_pHead;
	while (pTemp != NULL)
	{
		if (pTemp->iData == iData)
			pTemp->iData = iValue;
		pTemp = pTemp->pNext;
	}
}
void SX::ChangeByIndex(int iIndex, int iValue)
{
	//参数合法性检测
	if (NULL == g_pHead || iIndex < 0 || iIndex >= g_iNodeCount)
		return;
	struct Node* pTemp = GetByIndex(iIndex);
	if (pTemp != NULL)
	{
		pTemp->iData = iValue;
	}
}
Node* SX::GetByData(int iData)
{
	//参数合法性检测
	if (NULL == g_pHead)
		return NULL;
	//循环遍历
	struct Node* pTemp = g_pHead;
	while (pTemp != NULL)
	{
		if (pTemp->iData == iData)
			break;//return pTemp;
		pTemp = pTemp->pNext;
	}
	//return NULL;
	return pTemp;
}
Node* SX::GetByIndex(int iIndex)
{
	//参数合法性检测
	if (NULL == g_pHead || iIndex < 0 || iIndex >= g_iNodeCount)
		return NULL;
	//循环遍历
	struct Node* pTemp = g_pHead;
	for (int i = 0; i < iIndex; i++)
		pTemp = pTemp->pNext;
	//返回
	return pTemp;
}
void SX::InsertNodeByData(int iValue, int iData)
{
	//参数合法性检测
	if (NULL == g_pHead)
		return;
	//找节点
	struct Node* pTemp = g_pHead;
	while (pTemp != NULL)
	{
		if (pTemp->iData == iValue)
			break;
		pTemp = pTemp->pNext;
	}
	//判断是否找到
	if (pTemp != NULL)
	{
		if (pTemp == g_pHead)
			AddToHead(iData);
		else
		{
			//申请节点
			struct Node* pNew = new struct Node;
			if (NULL == pNew)
				return;
			//节点成员赋值
			pNew->iData = iData;
			pNew->pNext = NULL;
			pNew->pPre = NULL;
			//链接
			//指定位置前一个节点与新节点相连
			pTemp->pPre->pNext = pNew;
			pNew->pPre = pTemp->pPre;
			//指定位置节点与新节点相连
			pNew->pNext = pTemp;
			pTemp->pPre = pNew;
			//节点数量++
			g_iNodeCount += 1;
		}
	}
}
void SX::InsertNodeByIndex(int iIndex, int iCount, int iData)
{
	//参数合法性检测
	if (iIndex < 0 || iIndex>g_iNodeCount || iCount <= 0)
		return;
	//分类判断
	if (0 == iIndex)					//头添加
	{
		for (int i = 0; i < iCount; i++)
			AddToHead(iData);
	}
	else if (iIndex == g_iNodeCount)	//尾添加
	{
		for (int i = 0; i < iCount; i++)
			AddToEnd(iData);
	}
	else								//中间添加
	{
		//找位置
		struct Node* pTemp = g_pHead;
		for (int i = 0; i < iIndex; i++)
			pTemp = pTemp->pNext;
		//循环
		for (int i = 0; i < iCount; i++)
		{
			//申请节点
			struct Node* pNew = new struct Node;
			if (pNew == NULL)
				return;
			//节点赋值
			pNew->iData = iData;
			pNew->pNext = NULL;
			pNew->pPre = NULL;
			//链接
			//指定位置前一个节点与新节点相连
			pTemp->pPre->pNext = pNew;
			pNew->pPre = pTemp->pPre;
			//指定位置节点与新节点相连
			pNew->pNext = pTemp;
			pTemp->pPre = pNew;
		}
		//节点数量++
		g_iNodeCount += iCount;
	}
}
void SX::AddToHead(int iData)
{
	//创建节点
	struct Node* pTemp = new struct Node;
	if (pTemp == NULL)
		return;
	//节点赋值
	pTemp->iData = iData;
	pTemp->pNext = NULL;
	pTemp->pPre = NULL;
	//连接到链表上
	if (NULL == g_pHead)
	{
		//g_pHead = pTemp;
		g_pEnd = pTemp;
	}
	else
	{
		pTemp->pNext = g_pHead;
		g_pHead->pPre = pTemp;
		//g_pHead = pTemp;
	}
	g_pHead = pTemp;
	g_iNodeCount++;
}
void SX::LookFan()
{
	if (NULL == g_pEnd)
		return;
	//循环遍历
	printf("共有 %d 个节点： ", g_iNodeCount);
	struct Node* pTemp = g_pEnd;
	while (pTemp != NULL)
	{
		printf("%d  ", pTemp->iData);
		pTemp = pTemp->pPre;
	}
	putchar('\n');
}
void SX::LookZheng()
{
	if (NULL == g_pHead)
		return;
	//循环遍历
	printf("共有 %d 个节点： ", g_iNodeCount);
	struct Node* pTemp = g_pHead;
	while (pTemp != NULL)
	{
		printf("%d  ", pTemp->iData);
		pTemp = pTemp->pNext;
	}
	putchar('\n');
}
void SX::FreeList()
{
	//参数合法性检测
	if (NULL == g_pHead)
		return;
	//申请中间变量
	Node* pTemp = g_pHead;
	if (pTemp == NULL)
		return;
	while (pTemp != NULL)
	{
		//记录要被释放的节点
		struct Node* pT = pTemp;
		//指向下一个节点
		pTemp = pTemp->pNext;
		//释放当前节点
		delete pT;
	}
	g_pHead = NULL;
	g_pEnd = NULL;
	g_iNodeCount = 0;
}
void SX::AddToEnd(int iData)
{
	//参数合法性检测
	if (g_iNodeCount < 0)
		return;
	//申请节点
	struct Node* pTemp = new struct Node;
	if (NULL == pTemp)
		return;
	//节点成员赋值
	pTemp->iData = iData;
	pTemp->pNext = NULL;
	pTemp->pPre = NULL;
	//连接链表
	if (NULL == g_pHead)	//无节点
	{
		g_pHead = pTemp;
		//g_pEnd = pTemp;
	}
	else
	{
		g_pEnd->pNext = pTemp;
		pTemp->pPre = g_pEnd;
		//g_pEnd = pTemp;
	}
	g_pEnd = pTemp;
	//节点数量++
	g_iNodeCount++;
}

主函数

#include"sx.h"

int main()
{
	SX s;
	s.AddToEnd(1);
	s.AddToEnd(2);
	s.AddToEnd(3);
	s.LookZheng();


	return 0;
}