C语言之 - 单向链表

约定不等于承诺〃 2022-04-15 02:25 220阅读 0赞

## 一、前言 ##

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

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

## 二、链表定义 ##

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

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

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

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

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

## 三、实现过程 ##

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

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

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

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

### 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的尾部指向空
    	}
    }

### 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);           // 释放临时指向的链表
    	}
    }

### 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; // 每打印一个节点，临时变量后移一位
    	}
    }

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

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

### 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);
    		}
    	}
    }

### 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);
    		}
    	}
    }

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

### 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指向下一个
    	}
    }

### 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为新的头部
    }

完整demo链接:[点击下载][Link 1] 提取码：rgnz

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

## 四、结束语 ##

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

[-]: https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8/9794473?fr=aladdin
[Link 1]: https://pan.baidu.com/s/1-4wmu5JS6tI4OeEjWzhzvg
[gvkBITW.png]: https://i.imgur.com/gvkBITW.png