devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言之 - 单向链表_c 语言 单向链表定义

作者：我家小花儿 | 2024-08-08 00:16:18

赞

踩

c 语言 单向链表定义

一、前言

做项目的时候，经常会遇到这么一个场景： 需要在具有相同属性的数据(例如:学生的学号、名字组成的一串数据)里面查找或者追加或者删除一些数据。 那么，简单的数组远远不能达到目的，因为数组必须实现确定大小，不能动态申请和释放。然而使用malloc动态分配也不能实现，不能够实现局部申请和释放。

那么，链表应运而生。我们这篇文章主要介绍单向链表。

二、链表定义

定义: 链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一中线性存储结构。

特点： 链表由一系列节点(链表中每个元素称为节点)组成，节点在运行时动态生成，每个节点包括两部分：

一个是存储数据元素的数据域。

另一个是存储下一个节点地址的指针域。

更详细的解析详见链表-百度百科

三、实现过程

接下来就进入正题，看看链表是怎么实现的。
我们将会分10个部分用注释的方式来讲解链表的使用。

文章底部有完整的代码链接。

首先我们定义一个链表的数据结构。

typedef struct s_msg
{
	int  count;              // 数据域：整型 count
	char str[20];            // 数据域：字符串数组，分配20个字节
	struct s_msg *next;      // 指针域：链接下一个节点
}s_msg_t;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

1. 创建/追加链表

/*************************************************************************
* Function:    void create_link(s_msg_t **head, s_msg_t *p_new)
* Description: 创建/追加链表
* Input:
*              s_msg_t **head 链表头部
*              s_msg_t *p_new 链表新节点
* Return:      NULL
* Others:      NULL
**************************************************************************/
void create_link(s_msg_t **head, s_msg_t *p_new)
{
	if(NULL == (*head)) // head为空，新来的节点p_new就是head
	{
		LOGD("The current link is NULL, p_new is link head.");
		(*head) = p_new;
		(*head)->next = NULL;
	}
	else
	{
		LOGD("The current link has data, add nodes to last one.");
		s_msg_t *p_tmp = (*head);
		while(NULL != p_tmp->next) // head不为空，循环查找到链表尾部
		{
			p_tmp = p_tmp->next;
		}

		p_tmp->next = p_new; // 新来的节点p_new链接到链表尾部
		p_new->next = NULL;  // 将新节点p_new的尾部指向空
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

2.释放链表

/*************************************************************************
* Function:    void free_link(s_msg_t **head)
* Description: 释放链表
* Input:
*              s_msg_t **head 链表头部
* Return:      NULL
* Others:      NULL
**************************************************************************/
void free_link(s_msg_t **head)
{
	if(NULL == (*head))        // 头部为空直接返回
	{
		LOGD("The current link is NULL, return.");
		return ;
	}
	LOGD("Free link...");
	s_msg_t *p_tmp = NULL;
	while(NULL != (*head))     // 循环释放
	{
		p_tmp = (*head);       // 临时链表指向头部
		(*head) = p_tmp->next; // 链表的头部后移一个位置
		free(p_tmp);           // 释放临时指向的链表
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

3.打印链表节点

/*************************************************************************
* Function:    void show_link_nodes(s_msg_t *head)
* Description: 打印链表节点
* Input:
*              s_msg_t **head 链表头部
* Return:      NULL
* Others:      NULL
**************************************************************************/
void show_link_nodes(s_msg_t *head)
{
	if(NULL == head)        // 头部为空直接返回
	{
		LOGD("The current link is NULL, return.");
		return ;		
	}

	s_msg_t *p_tmp = head;   // 创建一个临时变量指向链表头部
	while(NULL != p_tmp)     // 循环查找链表并打印
	{
		LOGD("count: %d, str: %s", p_tmp->count, p_tmp->str);
		p_tmp = p_tmp->next; // 每打印一个节点，临时变量后移一位
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

4.查找节点 按count

/*************************************************************************
* Function:    s_msg_t *serach_node_for_link_as_count(s_msg_t *head,
*                                                              int count)
* Description: 按Count查找节点，并打印
* Input:
*              s_msg_t **head 链表头部
*              int count  查找的内容
* Return:      NULL
* Others:      NULL
**************************************************************************/
s_msg_t *serach_node_for_link_as_count(s_msg_t *head, int count)
{
	if(NULL == head)                  // 头部为空直接返回
	{
		LOGD("The current link is NULL, return.");
		return NULL;		
	}
	else
	{
		s_msg_t *p_tmp = head;        // 创建一个临时变量指向链表头部
		while(NULL != p_tmp)          // 循环查找
		{
			if(count == p_tmp->count) // 数据相等便打印
			{
				LOGD("Find node: Count: %d, Buffer: %s", p_tmp->count, p_tmp->str);
			}
			p_tmp = p_tmp->next;      // 临时变量后移一位
		}
	}
	return NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

5.查找节点 按Buffer

/*************************************************************************
* Function:    s_msg_t *serach_node_for_link_as_count(s_msg_t *head,
*                                                           char *buffer)
* Description: 按Buffer查找节点，并打印
* Input:
*              s_msg_t **head 链表头部
*              char *buffer   查找的内容
* Return:      NULL
* Others:      NULL
**************************************************************************/
s_msg_t *serach_node_for_link_as_buffer(s_msg_t *head, char *buffer)
{
	if(NULL == head)              // 头部为空直接返回
	{
		LOGD("The current link is NULL, return.");
		return NULL;		
	}
	else
	{
		s_msg_t *p_tmp = head;    // 创建一个临时变量指向链表头部
		while(NULL != p_tmp)      // 循环查找，数据相等便打印
		{
			if(0 == strncmp(p_tmp->str, buffer, strlen(buffer)))
			{
				LOGD("Find node: Count: %d, Buffer: %s", p_tmp->count, p_tmp->str);
			}
			p_tmp = p_tmp->next;  // 临时变量后移一位
		}
	}
	return NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

6.删除节点 按Count

/*************************************************************************
* Function:    delete_nodes_for_link_as_count(s_msg_t **head, int count)
* Description: 按Count删除节点
* Input:
*              s_msg_t **head 链表头部
*              int count  需要删除节点的数据
* Return:      NULL
* Others:      NULL
**************************************************************************/
void delete_nodes_for_link_as_count(s_msg_t **head, int count)
{
	if(NULL == (*head))               // 头部为空直接返回
	{
		LOGD("The current link is NULL, return.");
		return ;		
	}
	else
	{
		s_msg_t *p_f = NULL;          // 定义临时指针
		s_msg_t *p_n = NULL;
		p_f = p_n = (*head);

		while((count != p_n->count) && (NULL != p_n->next)) // 条件不等后移
		{
			p_f = p_n;
			p_n = p_n->next;          // 始终保持p_f在前p_n在后
		}

		if(count == p_n->count)       // 找到count
		{
			if(p_n == (*head))        // 若为头部
			{
				LOGD("Delete head, the head->next is new head.");
				(*head) = p_n->next;  // 链表head后移一位
			}
			else
			{
				LOGD("Delete link body.");
				p_f->next = p_n->next; // 其它部分p_f指向p_n的下一个
			}
			free(p_n);                 // 释放p_n
		}
		else
		{
			LOGD("Not find the Count is %d nodes.", count);
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

7.删除节点 按Buffer

此部分原理跟按count删除相同，这儿就不在对代码进行注释。

/*************************************************************************
* Function: delete_nodes_for_link_as_count(s_msg_t **head, char *buffer)
* Description:  按Buffer删除节点
* Input:
*   s_msg_t **head 链表头部
*   char *buffer   需要删除节点的数据
* Return:   NULL
* Others:   NULL
**************************************************************************/
void delete_nodes_for_link_as_buffer(s_msg_t **head, char *buffer)
{
	if(NULL == (*head))
	{
		LOGD("The current link is NULL, return.");
		return ;		
	}
	else
	{
		s_msg_t *p_f = NULL;
		s_msg_t *p_n = NULL;
		p_f = p_n = (*head);

		while((0 != strcmp(p_n->str, buffer)) && (NULL != p_n->next))
		{
			p_f = p_n;
			p_n = p_n->next;
		}

		if(0 == strcmp(p_n->str, buffer))
		{
			if(p_n == (*head))
			{
				LOGD("Delete head, the head->next is new head.");
				(*head) = p_n->next;
			}
			else
			{
				LOGD("Delete link body.");
				p_f->next = p_n->next;
			}
			free(p_n);
		}
		else
		{
			LOGD("Not find the Buffer is %s nodes.", buffer);
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

8. 插入链表###

/*************************************************************************
* Function:    insert_nodes_for_link_as_count(s_msg_t **head, s_msg_t *p_new)
* Description: 根据count的大小插入链表
* Input:
*              s_msg_t **head 链表头部
*              s_msg_t *p_new 链表新节点
* Return:      NULL
* Others:      NULL
**************************************************************************/
void insert_nodes_for_link_as_count(s_msg_t **head, s_msg_t *p_new)
{
	if(NULL == (*head)) // 头部为空，新来的节点p_new就是第一个节点
	{
		LOGD("The current link is NULL, new node is link head.");
		(*head) = p_new;
		p_new->next = NULL;
	}
	else
	{
		s_msg_t *p_f = NULL;            // 定义临时变量
		s_msg_t *p_n = NULL;
		p_f = p_n = (*head);

		while((p_new->count >= p_n->count) && (NULL != p_n->next)) // 条件不满足后移
		{
			p_f = p_n;
			p_n = p_n->next;
		}

		if(p_new->count < p_n->count)   // 条件满足
		{
			if(p_n == (*head))          // 若为头部
			{
				LOGD("Insert beyound head.");
				p_new->next = (*head);  // p_new就是head
				*(head) = p_new;        // 让head指向p_new
			}
			else
			{
				LOGD("Insert body.");
				p_f->next = p_new;      // p_new插在p_f和p_n的中间
				p_new->next = p_n;
			}
		}
		else
		{
			LOGD("Insert last one.");
			p_n->next = p_new;          // 插在链表尾部
			p_new->next = NULL;
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

9. 链表排序

/*************************************************************************
* Function:    void order_link(s_msg_t **head)
* Description: 链表由小到大排序
* Input:
*              s_msg_t **head 链表头部
* Return:      NULL
* Others:      NULL
**************************************************************************/
void order_link(s_msg_t **head)
{
	if(NULL == (*head))                 // 头部为空返回
	{
		LOGD("The node is NULL, return.");
		return ;	
	}
	if(NULL == (*head)->next)           // 仅有一个节点返回
	{
		LOGD("The node is only one, return.");
		return ;
	}

	s_msg_t *p_f   = NULL;              // 定义临时变量
	s_msg_t *p_n   = NULL;
	s_msg_t p_tmp;
	p_f = p_n = *head;
	while(NULL != p_f->next)            // 两层循环判断
	{
		p_n = p_f->next;                // p_f在前p_n在后
		while(NULL != p_n)              // p_n不为空
		{
			if(p_f->count > p_n->count) // 若p_f比p_n大，交换数据
			{
				p_tmp = *p_f;
				*p_f  = *p_n;
				*p_n  = p_tmp;

				p_tmp.next = p_f->next; // 注意next也要交换
				p_f->next  = p_n->next;
				p_n->next  = p_tmp.next;
			}
			p_n = p_n->next;            // p_n指向下一个
		}
		p_f = p_f->next;                // p_f指向下一个
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

10. 链表反转

/*************************************************************************
* Function:    void reverse_link(s_msg_t **head)
* Description: 链表反转
* Input:
*              s_msg_t **head 链表头部
* Return:      NULL
* Others:      NULL
**************************************************************************/
void reverse_link(s_msg_t **head)
{
	if(NULL == (*head))                 // 头部为空返回
	{
		LOGD("The node is NULL, return.");
		return ;		
	}
	if(NULL == (*head)->next)           // 仅有一个节点返回
	{
		LOGD("The node is only one, return.");
		return ;	
	}
	
	s_msg_t *p_f = NULL;                // 定义三个临时变量
	s_msg_t *p_n = NULL;
	s_msg_t *p_r = NULL;
	p_f = *head;                        // 保证p_n是p_f的下一个
	p_n = p_f->next;
	while(NULL != p_n)
	{
		p_r = p_n->next;                // p_r保证p_n的下一个能找到
		p_n->next = p_f;                // p_n的下一个指向p_f
		p_f = p_n;                      // p_f指向p_n
		p_n = p_r;                      // p_n指向p_r
	}
	(*head)->next = NULL;               // 最后head->next指向空
	*head = p_f;                        // p_f为新的头部
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

完整demo链接:点击下载 提取码：rgnz

以上就是链表的基本操作，我们将demo下载下来，放到linux系统下直接make编译，运行后结果如下图：运行图
大家可以根据代码去理解、学习单项链表的使用，通过运行起来的demo查看链表的操作。

四、结束语

链表解决了一些场合下数据存储的问题，它可以延伸到很多地方去使用，如工作队列等。掌握好它的基本操作，最好通过画图的方式去理解它。我所写出的链表结构有些浅显，可能还有很多没有注意到的地方，还请大家多多指正，共同探讨，共同成长。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/945145
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号