1、前言

链表是数据结构中非常重要的一个知识点，比较经典的就是C语言的链表，在学校也有这门课程，非计算机专业的朋友可能没学到这一章就毕业了（呵呵），在这里可以和我一起学习。因为个人偏好对链表的知识也没有面面俱到，全面的链表知识请多方查证学习。这篇文章主要介绍一个通用双向链表，之所以叫通用因为链表本身不包含特定应用层的设计，只是将多个节点连接起来组成一条链的结构，每个节点挂载的"内容"是应用层的设计。同时这篇文章也是我下一篇文章《keil实现故障码系统及仿真测试(使用链表)》的基础。感兴趣的朋友可以继续留意我后续的文章。

2、概述

链表就是将若干个数据节点使用指针连接起来，分为单向链表与双向链表；链表的优点是：链表上的节点可以随时增加减小，即具有内存动态分配的优点，在内存资源比较少的系统是一个优势，比数组灵活，不必事先分配内存。比如某些信息是动态产生，保留一定时间，其信息处理后就不必保存的场景，使用链表就是最合适了。典型的链表如下图所示：

由上图可见此为一个双向链表，关键信息包含两个节点的指针（分别保存上一个节点与下一个节点的指针）、一个节点编号，一个负载指针。正是因为使用负载指针，而不是将应用层信息包含到节点中定义使得链表具有了通用的属性。这样节点与负载都可以通过动态申请内存得到，而且负载可以依据应用意图进行设计。直接给出链表管理器与节点数据结构的定义，如下图所示：

3、定义链表关键数据结构

//定义链表操作状态typedef enum{	listOpSuccess=0,					//链表操作成功	listOpListEmpty,					//链表为空	listOpListNotExist,					//链表不存在	listOpNodeNotExist,					//链表不存在此节点	listOpNodeNull,						//节点为空（节点地址非法）	listOpNewNodeNull,					//添加新节点时节点地址为空}listOpResult_t;//定义节点结构体typedef struct Node{	u16				num;				//节点编号	void*			pLoad;				//指向参数的指针	struct Node 	*pre;				//前一个节点		struct Node 	*next;				//后一个节点}Node_t;//定义链表结构体typedef struct listMgr{	u16 	count;						//节点数量	Node_t 	*pFirst;						//首节点		Node_t 	*pLast;						//末节点	Node_t 	*pNow;						//当前节点}List_t;

为了使用链表，有两个关键的操作：就是申请内存与释放内存；申请内存我们使用malloc()，释放内存使用free();我们需要两个关键的申请内存操作如下：

List_t *ListCreate(void)

链表关键的应用有：创建链表，创建一个节点（创建时自动增加到链表），从链表中移除节点（返回节点负载指针），查找指定编号的节点，遍历链表等

List_t *ListCreate(void)	//创建双向链表/********************************************************************函数功能：在链表尾部添加节点入口参数：list,链表指针 *pLoad加入链表的节点负载指针 nodeNum，节点编号返    回：无。备    注：创建节点之前需要先创建节点负载，节点本身的内存由本函数完成********************************************************************/listOpResult_t ListBackAddNode(List_t *list,void* pLoad,u16 nodeNum)/********************************************************************函数功能：从链表头部添加节点入口参数：list,链表指针 *pLoad加入链表的节点负载指针 nodeNum，节点编号返    回：无。备    注：无。创建节点之前需要先创建节点负载，节点本身的内存由本函数完成********************************************************************/listOpResult_t ListHeadAddNode(List_t *list,void* pLoad,u16 nodeNum)/********************************************************************函数功能：从尾部移除一个节点(自动释放这个节点的内存，添加节点时自动申请内存)入口参数：list目标链表返    回：对应节点的负载数据指针（移除节点后需要释放这个内存块）在外部free这个内存块备    注：释放节点对应的存储空间。********************************************************************/void* RemoveNodeFromBack(List_t* list)/********************************************************************函数功能：从头部移除一个节点(自动释放这个节点的内存，添加节点时自动申请内存)入口参数：无。返    回：对应节点的负载数据指针（移除节点后需要释放这个内存块）在外部free这个内存块备    注：释放节点对应的存储空间。********************************************************************/void* RemoveNodeFromHead(List_t* list)/********************************************************************函数功能：移除当前节点(自动释放这个节点的内存，添加节点时自动申请内存)入口参数：无。返    回：对应节点的负载数据指针（移除节点后需要释放这个内存块）在外部free这个内存块备    注：前提条件：先查找到某个节点（使得当前节点指向该节点），再进行删除操作。********************************************************************/void* RemoveCurrentNode(List_t* list)/********************************************************************函数功能：遍历整个链表查找指定节点编号的节点入口参数：list,链表 nodeNum节点编号,**pLoad目标节点负载数据的指针返    回：找到返回TRUE,找不到返回FALSE备    注：找到第一个节点即停止********************************************************************/bool listFindNodeFromBegin(List_t* list,u16 nodeNum,void **pLoad)/********************************************************************函数功能：遍历链表并返回节点编号及负载数据指针入口参数：list,链表 pNodeNum节点编号保存地址返    回：节点负载指针备    注：需先执行链表头部********************************************************************/void* listGetNodePayLoadAndMoveNext(List_t* list,u16 *pNodeNum)

因为此链表设计为通用类型，为测试方便下面定义一个节点负载数据结构（此为假设的一个负载数据结构，当然也可以定义成其他类型）

//链表负载数据结构typedef struct{	u8 Voltage;			//电压	u8 Currnet;			//电流	u8 Freq;			//频率}sPowerInfo_t;//负载数据初始化void PowerInfoInit(sPowerInfo_t *PowerInfo,u8 Voltage,u8 Currnet,u8 Freq){	PowerInfo->Voltage=Voltage;	PowerInfo->Currnet=Currnet;	PowerInfo->Freq=Freq;}//打印负载信息void printPowerInfo(sPowerInfo_t *PowerInfo,u8 NodeNum){	printf("NodeNum=%d Voltage=%dV Currnet=%dA Freq=%dHz \r\n",NodeNum,PowerInfo->Voltage,PowerInfo->Currnet,PowerInfo->Freq);}

写一个专门的函数测试链表，测试添加节点（5个），查找节点，遍历链表，输出相关测试信息。

static List_t *list;		//定义链表指针void ListTest(void){	bool findNodeFlag=FALSE;	int i;	u8 Voltage=100;			//电压	u8 Currnet=5;			//电流	u8 Freq=50;				//频率	u16 NodeNum=1,FindNodeNum;	sPowerInfo_t *PowerInfo;	list = ListCreate();	#if 1																	//添加节点		printf("------------------链表添加节点------------------------\r\n");		for(i=0; i<5; i++)		{			PowerInfo = (sPowerInfo_t *)malloc(sizeof(sPowerInfo_t));		//申请节点内存			PowerInfoInit(PowerInfo,Voltage,Currnet,Freq);					//初始化节点数据			printPowerInfo(PowerInfo,NodeNum);								//打印节点负载信息				ListBackAddNode(list, PowerInfo,NodeNum);						//将节点添加到链表末尾			NodeNum++;														//节点编号			Voltage+=10;													//电压			Currnet++;														//电流			Freq++;															//频率		}		PrintListFromHead(list);											//打印节点负载内存地址	#endif	#if 1																	//查找节点			FindNodeNum=4;		printf("------------------查找节点%d------------------------\r\n",FindNodeNum);		findNodeFlag=listFindNodeFromBegin(list,FindNodeNum,(void*)&PowerInfo);		if(findNodeFlag==FALSE)		{			printf("----listCount=%d 链表无编号=%d的节点\r\n",listCount(list),FindNodeNum);		}		else		{			printf("----listCount=%d pLoad=0x%X\r\n",listCount(list),(u32)PowerInfo);			printPowerInfo(PowerInfo,FindNodeNum);		}		FindNodeNum=8;		printf("------------------查找节点%d------------------------\r\n",FindNodeNum);		findNodeFlag=listFindNodeFromBegin(list,FindNodeNum,(void*)&PowerInfo);		if(findNodeFlag==FALSE)		{			printf("-1--listCount=%d 链表无编号=%d的节点\r\n",listCount(list),FindNodeNum);		}		else		{			printf("-2--listCount=%d pLoad=0x%X\r\n",listCount(list),(u32)PowerInfo);			printPowerInfo(PowerInfo,FindNodeNum);		}	#endif	#if 1																	//遍历节点	printf("------------------遍历链表节点------------------------\r\n");	listBegin(list);		while(listHasNext(list))	{		PowerInfo=listGetNodePayLoadAndMoveNext(list,&FindNodeNum);		printPowerInfo(PowerInfo,FindNodeNum);	}	#endif	#if 1				//移除部分节点		printf("------------------移除部分节点------------------------\r\n");		//listSetBegin(list);		findNodeFlag=listFindNodeFromBegin(list,1,(void*)&PowerInfo);		//查找节点		PowerInfo=RemoveCurrentNode(list);free(PowerInfo);					//移除节点并释放节点负载内存		printf("findNode:%d 移除节点0x%X \n",findNodeFlag,(u32)PowerInfo);	//打印该节点内存地址				findNodeFlag=listFindNodeFromBegin(list,3,(void*)&PowerInfo);		//查找节点		PowerInfo=RemoveCurrentNode(list);free(PowerInfo);					//移除节点并释放节点负载内存		printf("findNode:%d 移除节点0x%X \n",findNodeFlag,(u32)PowerInfo);	//打印该节点内存地址		printf("----剩余节点数量=%d \r\n",listCount(list));			#endif	#if 1																	//遍历节点	printf("----------------移除部分节点--遍历链表节点------------------------\r\n");	listBegin(list);		while(listHasNext(list))	{		PowerInfo=listGetNodePayLoadAndMoveNext(list,&FindNodeNum);		printPowerInfo(PowerInfo,FindNodeNum);	}	#endif}

下面使用KEIL仿真一下链表的效果

链表仿真参数打印效果

链表仿真节点链效果

总结：链表的使用关键点是内存管理及指针操作。链表也是数据数据结构一个关键知识点。