【数据结构基础_双向链表（有[*pHead]和[*pEnd]）_(C语言实现)】_c语言g_phead_千北@的博客-程序员宅基地

【数据结构基础_双向链表（有[pHead]和[pEnd]）_(C语言实现)】_c语言g_phead_千北@的博客-程序员宅基地

双向链表（含头尾指针）

双向链表呢，顾名思义，就是比单向多一个向前指向节点的一个指针

本文主要是针对（含头尾指针）双向链表进行增、删、改、查操作

创建一个结构体当做节点

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

前面我用的是局部定义头尾指针（每次调用都需要传参），这次咱们使用全局的
定义头尾指针

struct Node* g_pHead = NULL;
struct Node* g_pEnd = NULL;
int g_iNodeCount = 0;

g_iNodeCount是记录节点数的

增加：1.尾添加

//尾添加
void AddToEnd(int iData)
{
    
	//参数合法性检测
	if (g_iNodeCount < 0)
		return;
	//申请节点
	struct Node* pTemp = (struct Node*)malloc(sizeof(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++;
}

增加：2.头添加

void AddToHead(int iData)
{
    
	//创建节点
	struct Node* pTemp = (struct Node*)malloc(sizeof(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 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 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 FreeList()
{
    
	//参数合法性检测
	if (NULL == g_pHead)
		return;
	//申请中间变量
	struct Node* pTemp = g_pHead;
	while (pTemp != NULL)
	{
    
		//记录要被释放的节点
		struct Node* pT = pTemp;
		//指向下一个节点
		pTemp = pTemp->pNext;
		//释放当前节点
		free(pT);
	}
	g_pHead = NULL;
	g_pEnd = NULL;
	g_iNodeCount = 0;
}

释放链表记得指针要置空哈
并且计数器置零

查找：1.根据下标查询

struct Node* 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;
}

查找：2.根据数值查询

struct Node* 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;
}

升级版添加：1.指定的下标位置添加

void 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 = (struct Node*)malloc(sizeof(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;
	}
}

升级版添加：2.指定数据位置添加节点

void 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 = (struct Node*)malloc(sizeof(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;
		}
	}
}

修改：1.根据数值改变此节点数据

void 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;
	}
}

修改：2.根据下标改变此节点数据

void 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;
	}
}

删除：1.根据下标删除节点

void DeleteByIndex(int iIndex)
{
    
	//查找节点
	struct Node* pTemp = GetByIndex(iIndex);
	//判断是否找到
	if (pTemp != NULL)
	{
    
		//找到了删除节点
		DeleteNode(pTemp);
	}
}

删除：2.删除结点

void DeleteNode(struct Node* pTemp)
{
    
	//是否为头结点
	if (pTemp == g_pHead)
	{
    
		if (g_pHead == g_pEnd)
		{
    
			free(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;
			//释放头的前一个节点
			free(g_pHead->pPre);
			//头前置NULL
			g_pHead->pPre = NULL;
		}
	}
	//尾节点
	else if (pTemp == g_pEnd)
	{
    
		g_pEnd = g_pEnd->pPre;
		free(g_pEnd->pNext);
		g_pEnd->pNext = NULL;
	}
	//中间节点
	else
	{
    
		//让其前一个节点的pNext 指针指向其后一个节点
		pTemp->pPre->pNext = pTemp->pNext;
		//让其后一个节点的pPre 指针指向其前一个节点
		pTemp->pNext->pPre = pTemp->pPre;
		//释放此节点
		free(pTemp);
	}
	g_iNodeCount--;
}

删除：3.根据数据删除所有与之相同的节点

void 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 HeBing(struct Node** pHA, struct Node** pEA, int* pCA, struct Node** pHB, struct Node** pEB, int* pCB)
{
    
	//参数合法性检测
	if (NULL == pHA || NULL == *pHA || NULL == pHB || NULL == *pHB)
		return;
	//循环
	while(1)
	{
    
		//获取头
		struct Node* pTemp = GetHead(pHA, pEA, pCA);
		if (pTemp == NULL)
			return;
		//比头小
		if (pTemp->iData <= (*pHB)->iData)
		{
    
			//新节点下一个指向头
			pTemp->pNext = (*pHB);
			// 头前一个指向新节点
			(*pHB)->pPre = pTemp;
			// 头向前移
			(*pHB) = pTemp;
			//数量++
			(*pCB)++;
		}
		// 比尾大
		else if (pTemp->iData >= (*pEB)->iData)
		{
    
			//尾巴的pNext指向新节点
			(*pEB)->pNext = pTemp;
			//新节点的pre指向尾巴
			pTemp->pPre = (*pEB);
			//尾后移
			(*pEB) = pTemp;
			//尾巴的pNext置NULL
			(*pEB)->pNext = NULL;
			//数量++
			(*pCB)++;
		}
		else  // 中间
		{
    
			//在链表B中找到合适的位置
			struct Node* pT = *pHB;
			if (pT == NULL)
				return;
			while (pT->pNext != NULL)
			{
    
				if (pTemp->iData >= pT->iData && pTemp->iData <= pT->pNext->iData)
					break;
				pT = pT->pNext;
			}
			//中间添加
			if (NULL == pT->pNext)
				return;
			//新节点的pNext 指向pT的下一个
			pTemp->pNext = pT->pNext;
			//pT的下一个的pPre指向新节点
			pT->pNext->pPre = pTemp;
			//pT和新节点相连
			pT->pNext = pTemp;
			pTemp->pPre = pT;
			//数量++
			(*pCB)++;
		}
	}
}

实现合并链表的完整代码

#include<stdio.h>
#include<stdlib.h>

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

//尾添加
void AddToEnd(struct Node** pHead, struct Node** pEnd, int* pCount, int iData);
//释放链表
void FreeList(struct Node** pHead, struct Node** pEnd, int* pCount);
//遍历链表 1.正向 2.反向
void LookZheng(struct Node* pHead, int* pCount);
//得到链表头
struct Node* GetHead(struct Node** pHead, struct Node** pEnd, int* pCount);
//合并函数
void HeBing(struct Node** pHA, struct Node** pEA, int* pCA, struct Node** pHB, struct Node** pEB, int* pCB);


int main()
{
    
	struct Node* g_pAH = NULL;
	struct Node* g_pAE = NULL;
	int g_iA = 0;
	struct Node* g_pBH = NULL;
	struct Node* g_pBE = NULL;
	int g_iB = 0;
	AddToEnd(&g_pAH, &g_pAE, &g_iA, 1);
	AddToEnd(&g_pAH, &g_pAE, &g_iA, 5);
	AddToEnd(&g_pAH, &g_pAE, &g_iA, 2);
	AddToEnd(&g_pAH, &g_pAE, &g_iA, 8);
	AddToEnd(&g_pAH, &g_pAE, &g_iA, 10);
	
	AddToEnd(&g_pBH, &g_pBE, &g_iB, 2);
	AddToEnd(&g_pBH, &g_pBE, &g_iB, 6);
	AddToEnd(&g_pBH, &g_pBE, &g_iB, 9);

	LookZheng(g_pAH, &g_iA);
	LookZheng(g_pBH, &g_iB);
	
	HeBing(&g_pAH, &g_pAE, &g_iA, &g_pBH, &g_pBE, &g_iB);
	LookZheng(g_pBH, &g_iB);
	
	FreeList(&g_pAH, &g_pAE, &g_iA);
	FreeList(&g_pBH, &g_pBE, &g_iB);
	return 0;
}
void HeBing(struct Node** pHA, struct Node** pEA, int* pCA, struct Node** pHB, struct Node** pEB, int* pCB)
{
    
	//参数合法性检测
	if (NULL == pHA || NULL == *pHA || NULL == pHB || NULL == *pHB)
		return;
	//循环
	while(1)
	{
    
		//获取头
		struct Node* pTemp = GetHead(pHA, pEA, pCA);
		if (pTemp == NULL)
			return;
		//比头小
		if (pTemp->iData <= (*pHB)->iData)
		{
    
			//新节点下一个指向头
			pTemp->pNext = (*pHB);
			// 头前一个指向新节点
			(*pHB)->pPre = pTemp;
			// 头向前移
			(*pHB) = pTemp;
			//数量++
			(*pCB)++;
		}
		// 比尾大
		else if (pTemp->iData >= (*pEB)->iData)
		{
    
			//尾巴的pNext指向新节点
			(*pEB)->pNext = pTemp;
			//新节点的pre指向尾巴
			pTemp->pPre = (*pEB);
			//尾后移
			(*pEB) = pTemp;
			//尾巴的pNext置NULL
			(*pEB)->pNext = NULL;
			//数量++
			(*pCB)++;
		}
		else  // 中间
		{
    
			//在链表B中找到合适的位置
			struct Node* pT = *pHB;
			if (pT == NULL)
				return;
			while (pT->pNext != NULL)
			{
    
				if (pTemp->iData >= pT->iData && pTemp->iData <= pT->pNext->iData)
					break;
				pT = pT->pNext;
			}
			//中间添加
			if (NULL == pT->pNext)
				return;
			//新节点的pNext 指向pT的下一个
			pTemp->pNext = pT->pNext;
			//pT的下一个的pPre指向新节点
			pT->pNext->pPre = pTemp;
			//pT和新节点相连
			pT->pNext = pTemp;
			pTemp->pPre = pT;
			//数量++
			(*pCB)++;
		}
	}
}
struct Node* GetHead(struct Node** pHead, struct Node** pEnd, int* pCount)
{
    
	//参数合法性检测
	if (NULL == pHead || NULL == *pHead)
		return NULL;
	//摘头
	struct Node* pT = *pHead;		//记录头
	if (*pHead == *pEnd)			//只有一个节点
	{
    
		*pHead = NULL;
		*pEnd = NULL;
	}
	else
	{
    
		*pHead = (*pHead)->pNext;	//头往后走
		(*pHead)->pPre = NULL;
	}
	(*pCount)--;
	return pT;
}
void LookZheng(struct Node* pHead,int* pCount)
{
    
	if (NULL == pHead)
		return;
	//循环遍历
	printf("共有 %d 个节点： ", *pCount);
	struct Node* pTemp = pHead;
	while (pTemp != NULL)
	{
    
		printf("%d  ", pTemp->iData);
		pTemp = pTemp->pNext;
	}
	putchar('\n');
}
void FreeList(struct Node** pHead, struct Node** pEnd, int* pCount)
{
    
	//参数合法性检测
	if (NULL == *pHead)
		return;
	//申请中间变量
	struct Node* pTemp = *pHead;
	while (pTemp != NULL)
	{
    
		//记录要被释放的节点
		struct Node* pT = pTemp;
		//指向下一个节点
		pTemp = pTemp->pNext;
		//释放当前节点
		free(pT);
	}
	*pHead = NULL;
	*pEnd = NULL;
	*pCount = 0;
}
void AddToEnd(struct Node** pHead, struct Node** pEnd, int* pCount, int iData)
{
    
	//参数合法性检测
	if (*pCount < 0)
		return;
	//申请节点
	struct Node* pTemp = (struct Node*)malloc(sizeof(struct Node));
	if (NULL == pTemp)
		return;
	//节点成员赋值
	pTemp->iData = iData;
	pTemp->pNext = NULL;
	pTemp->pPre = NULL;
	//连接链表
	if (NULL == *pHead)	//无节点
	{
    
		*pHead = pTemp;
	}
	else
	{
    
		(*pEnd)->pNext = pTemp;
		pTemp->pPre = *pEnd;
	}
	*pEnd = pTemp;
	//节点数量++
	(*pCount)++;
}

本文链接：https://blog.csdn.net/Sugar_wolf/article/details/121619454

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Java面试题-springboot_spring boot java面试题-程序员宅基地

目录@、什么是springboot@、Spring Boot有哪些优点？@、如何重新加载Spring Boot上的更改，而无需重新启动服务器？springboot注解@、Spring Boot中的监视器是什么？@、什么是YAML？@、如何集成Spring Boot和ActiveMQ？@、springboot常用的starter有哪些？@、spri..._spring boot java面试题

每个人都应该学习一门编程语言-程序员宅基地

关键词：编程入门，编程语言基本要素作者：码匠信龙在纪录片《乔布斯：遗失的访谈》中，乔布斯谈到他20岁左右学习编程的经历：当时编程可以帮助我们完成工作，但没有明确的实用性，重要的是我们把它看作思考的镜子，学习如何思考。我觉得每个人都应该学习一门编程语言。学习编程教你如何思考，就像学法律一样。学法律并不一定要为了做律师，但法律教你一种思考方式。学习编程也是一样，我把计算机科学看成是基础教..._如果一定要学习一门编程语言

Android Monkey源码解析_monkey软件架构图-程序员宅基地

这两天在读Android Monkey的源代码.代码不多,放出分享.我现说一下,Monkey是干什么的:简单的说就是,模拟用户的touch screen和keyboard的输入.其实这个功能就已经很恐怖了. Google自己说的下面:// Only bind this to local host. This means that you can only// talk to th_monkey软件架构图

使用display:inline-block；属性转化的行内块的缺点及解决方法_flydrem的博客-程序员宅基地

使用display:inline-block;属性转化的行内块的缺点及解决方法缺点多个相邻行内块之间有间隙（空隙产生的原因：当元素有行内元素的特性时，元素间的空白符都会被解析，回车换行会被解析成一个空白符，如果字体不为零那么就会占一定的宽度，并且这些间距会随字体的大小而变化）里面的文本行数不一致时会出现盒子塌陷取消盒子间隙的方法删除标签之间的空白（有效果但是不建议使用，代码看起来不太规范，一般不使用）给转化显示模式为行内块的盒子添加margin-left: -10px;，取负值，可以把间隙

C++读书列表 (V3.0)-程序员宅基地

时隔半年，“C++读书列表”再次更新。所列图书均是Ada已经阅读过的书记。目录格式为：作品分类、英文书名、作者、译者、中文版出版社、简介。排名虽然不分先后，但是Ada用红色标出推荐读物（推荐角度各有不同，无需照单全收）。参考手册1. The C++ Programming Language (Special Edition), Bjarne Stroustrup 裘宗燕(译), 机械工业出版

AsyncTask用法详解_asynctask publishprogress-程序员宅基地

本文从http://blog.csdn.net/iispring/article/details/50639090转载在Android中我们可以通过Thread+Handler实现多线程通信，一种经典的使用场景是：在新线程中进行耗时操作，当任务完成后通过Handler向主线程发送Message，这样主线程的Handler在收到该Message之后就可以进行更新UI的操作。上述场景中需要分别在T_asynctask publishprogress

随便推点

python实验（1）_写一个程序,能接收用户输入的实部和虚部-程序员宅基地

请编写一个程序，能接收用户输入的一个复数的实部和虚部，输出其复数表示形式，并求其模。import math if __name__ == '__main__': real=int(input("请输入实数部分：")) imaginary=int(input("请输入虚数部分:")) Module_length=math.sqrt(real*real+imaginary*imaginary) print("实数部分"+str(real)+"______"+"虚数部分._写一个程序,能接收用户输入的实部和虚部

swagger 报错 Ambiguous handler methods mapped for ‘/v3/api-docs/‘_ambiguous handler methods mapped for '/v3/api-docs-程序员宅基地

在启动项目A时, 调用/v3/api-docs 接口发现报错返回值{"errorCode":"Unknown","code":500,"path":"/v3/api-docs/","stack":"","errorMsg":"Ambiguous handler methods mapped for '/v3/api-docs/': {public java.lang.String org.springdoc.api.OpenApiResource.openapiJson(javax.servlet._ambiguous handler methods mapped for '/v3/api-docs