数据结构—单向链表

转载自https://blog.csdn.net/weixin_43866583/article/details/127069907?spm=1001.2014.3001.5502

链表是什么

链表是编程语言中常见的一种数据结构，它可以实现动态的创建和删除，只要内存足够，链表的数量和长度是可以无限多和无限长的。

链表顾名思义是一种链式的数据结构，它由一个个节点组成，并通过节点之间的互相关联链接，形成了类似一条链式的结构。

链表的节点一般可以分为数据域和指针域。数据域中是存放节点数据的，往往链表的节点都是结构体类型的，可以方便定义多种不同的数据类型，便于使用。指针域是存放节点的指针的，是链表中每个节点能互相串联起来的关键，这个至关重要！

单向链表

单向链表根据使用情况还分为单向不循环链表、单向循环链表两种。

单向不循环链表

单向不循环链表是一种单向的链式结构，节点之间通过指针域互相关联，最后一个节点的指针域为空（NULL）

*先定义一个链表的节点*

// 定义一个链表节点的数据域。以记录一个苹果的信息为例，为方便说明，假设每个苹果的信息各不相同
typedef struct LinkData_struct
{
	int  weight; // 苹果的重量
	int  hight;  // 苹果的高度
	// ... 		 // 还可以定义更多的其他的数据
}LinkData_t;
 
/*** 定义一个链表节点 ******/
typedef struct LinkNode_Struct
{
	LinkData_t data;				// 链表节点的数据域
	struct LinkNode_Struct *Next; 	// 链表节点的指针域
}LinkNode_t;

*定义一个单向链表的头结点*

1 2	`/* 定义一个单向链表的头结点 */ LinkNode_t AppleInfo_head; //作为单向链表的一个头结点`

*初始化单向链表*

// 初始化单向链表的头结点
void Init_LinkNode(LinkNode_t * HeadNode)
{
	HeadNode->Next = NULL;
}

*创建链表节点并接入到链表中*

// 创建一个链表节点并接入到链表中
LinkNode_t * LinkNode_Create(LinkNode_t * HeadNode, LinkData_t *InsetData)
{
	LinkNode_t *Node,*pf;
	LinkNode_t *xReturn = NULL;
	Node = (LinkNode_t *)malloc(sizeof(LinkNode_t));
 
	if (Node == NULL)
	{
		printf("节点创建失败！！！\r\n");
		return NULL;
	}
 
	pf = HeadNode;
	while(pf->Next != NULL)
	{
		pf = pf->Next;
	}
	pf->Next = Node;
	Node->Next = NULL;
	Node->data.hight = InsetData->hight;
	Node->data.weight = InsetData->weight;
	xReturn = Node;
 
	printf("完成一个链表节点的创建，地址 = 0x%X\r\n",xReturn);
	return xReturn;
}

*删除链表中的节点*

// 删除链表中的某个节点,根据weight进行删除
void destroy_LinkNode(LinkNode_t * HeadNode, int weight)
{
	int deleteFlag = 0;
	LinkNode_t *pf,*preStre;
 
	pf = preStre = HeadNode;
 
	do
	{
		if (pf->data.weight == weight){
			deleteFlag = 1;
			break;
		}
		preStre = pf;
		pf = pf->Next;
	}while (pf->Next != NULL);
 
	if (!deleteFlag)
	{
		printf("找不到这个节点！！！\r\n");
	}
	else
	{
		if(pf->Next == NULL)	// 该点是尾节点
		{
			preStre->Next = NULL;
		}
		else
		{
			preStre->Next = pf->Next;
		}
		free(pf);
		printf("节点weight = %d 销毁成功！\r\n",weight);
	}
}

*输出整条链表的数据*

// 输出显示整条链表
void print_LinkNode_Info(LinkNode_t * HeadNode)
{
	int length = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		printf("weight = %d\r\n", (int)pf->data.weight);
		printf("height = %d\r\n", (int)pf->data.hight);
		printf("\r\n");
		length++;
	}while (pf->Next != NULL);
	printf("链表输出完成。长度为：%d\r\n",length);
}

*按条件查询链表中某个节点的数据*

// 按条件查询链表中某个节点的数据
void search_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("\r\n");
		}
		length++;
	}while (pf->Next != NULL);
 
	if(search_flag)
	{
		printf("链表查找结束。所在节点位置为：%d\r\n",length);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}

单向循环链表

单向循环链表是一种单向的可回头的链表，节点之间通过指针域互相关联，最后一个节点的指针域为头结点的地址。

*先定义一个链表的节点*

// 定义一个链表节点的数据域。以记录一个苹果的信息为例，为方便说明，假设每个苹果的信息各不相同
typedef struct LinkData_struct
{
	int  weight; // 苹果的重量
	int  hight;  // 苹果的高度
	// ... 		 // 还可以定义更多的其他的数据
}LinkData_t;
 
/*** 定义一个链表节点 ******/
typedef struct LinkNode_Struct
{
	LinkData_t data;				// 链表节点的数据域
	struct LinkNode_Struct *Next; 	// 链表节点的指针域
}LinkNode_t;

*定义一个单向链表的头结点*

1 2	`/* 定义一个单向链表的头结点 */ LinkNode_t AppleInfo_head; //作为单向链表的一个头结点`

*初始化单向链表*

// 初始化单向循环链表的头结点
void Init_LinkNode(LinkNode_t * HeadNode)
{
	HeadNode->Next = HeadNode;
}

*创建链表节点并接入到链表中*

// 创建一个链表节点并接入到单向循环链表中
LinkNode_t * LinkNode_Create(LinkNode_t * HeadNode, LinkData_t *InsetData)
{
	LinkNode_t *Node,*pf;
	LinkNode_t *xReturn = NULL;
	Node = (LinkNode_t *)malloc(sizeof(LinkNode_t));
 
	if (Node == NULL)
	{
		printf("节点创建失败！！！\r\n");
		return NULL;
	}
 
	pf = HeadNode;
	while(pf->Next != HeadNode)
	{
		pf = pf->Next;
	}
	pf->Next = Node;
	Node->Next = HeadNode;
	Node->data.hight = InsetData->hight;
	Node->data.weight = InsetData->weight;
	xReturn = Node;
 
	printf("完成一个链表节点的创建，地址 = 0x%X\r\n",xReturn);
	return xReturn;
}

*删除链表中的节点*

// 删除链表中的某个节点,根据weight进行删除
void destroy_LinkNode(LinkNode_t * HeadNode, int weight)
{
	int deleteFlag = 0;
	LinkNode_t *pf,*preStre;
 
	pf = preStre = HeadNode;
 
	do
	{
		preStre = pf;
		pf = pf->Next;
		if (pf->data.weight == weight){
			deleteFlag = 1;
			break;
		}
	}while (pf->Next != HeadNode);
 
	if (!deleteFlag)
	{
		printf("找不到这个节点！！！\r\n");
	}
	else
	{
		if(pf->Next == HeadNode)	// 该点是尾节点
		{
			preStre->Next = HeadNode;
		}
		else
		{
			preStre->Next = pf->Next;
		}
		free(pf);
		printf("节点weight = %d 销毁成功！\r\n",weight);
	}
}

*输出整条链表的数据*

// 输出显示整条链表
void print_LinkNode_Info(LinkNode_t * HeadNode)
{
	int length = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == HeadNode)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		printf("weight = %d\r\n", (int)pf->data.weight);
		printf("height = %d\r\n", (int)pf->data.hight);
		printf("\r\n");
		length++;
	}while (pf->Next != HeadNode);
	printf("链表输出完成。长度为：%d\r\n",length);
}

*按条件查询链表中某个节点的数据*

// 按条件查询链表中某个节点的数据
void search_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;
 
	if (pf->Next == HeadNode)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}
 
	do	
	{
		pf = pf->Next;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("\r\n");
		}
		length++;
	}while (pf->Next != HeadNode);
 
	if(search_flag)
	{
		printf("链表查找结束。所在节点位置为：%d\r\n",length);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}

单向不循环链表和单向循环链表基本是相同的，不同之处主要在于尾节点的指针域不同。单向不循环链表的尾节点的指针域为空，到尾节点的位置链表就结束了；单向循环链表的尾节点保存的是头节点的地址，从尾节点可以知道首节点的位置，形成一种循环的链式结构。

DATA_STRUCT

#linked

数据结构—双向链表上一篇

CAN协议下一篇