C语言之 - 双向链表

左手的ㄟ右手 2022-04-15 06:36 195阅读 0赞

## 一、前言 ##

之前，写过一篇[《C语言之 - 单向链表》][C_ -]的文章，有兴趣的朋友可以看一下。

双向链表再某些特定的场合结合着单向链表能够非常简便、快速的对数据进行操作，比如有锁队列等。

可以看一下双向链表的百科：[百科-双向链表][-]

## 二、实现过程 ##

我们结合着注释，一起来学习一下双向链表。文章底部有源码供大家下载。

首先我们定义一个结构体节点：

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

### 1.双向链表的创建 ###

/************************************************************************* 
    * Function:    void double_link_creat(s_msg_t **head, s_msg_t *new)
    * Description: 创建/插入双向链表
    * Input:   
    *              s_msg_t **head 链表头
    *              s_msg_t *new   链表节点
    * Return:      NULL
    * Others:      NULL
    **************************************************************************/
    void double_link_creat(s_msg_t **head, s_msg_t *pnew)
    {
    	s_msg_t *tmp = *head;
    	if (NULL == *head) // 头部为空，新来的节点就是第一个
    	{
    		*head = pnew;
    		pnew->prev = NULL;
    		pnew->next = NULL;
    	}
    	else // 第二次及以后追加节点
    	{
    		while (NULL != tmp->next)
    		{
    			tmp = tmp->next;// 循环找到最后一个节点
    		}
    		tmp->next  = pnew;  // 新申请的节点加入链表
    		pnew->prev = tmp;
    		pnew->next = NULL;
    	}
    }

### 2.双向链表的打印 ###

/************************************************************************* 
    * Function:    void double_link_print(s_msg_t * head)
    * Description: 打印链表节点
    * Input:   
    *              s_msg_t *head 链表头
    * Return:      NULL
    * Others:      NULL
    **************************************************************************/
    void double_link_print(s_msg_t * head)
    {
    	if (NULL == head)
    	{
    		LOGD("double link is null, return.");
    		return ;
    	}
    	
    	s_msg_t *tmp = head;
    	while (NULL != tmp)
    	{
    		LOGD("show link nodes: count = %d, str = %s\n", tmp->count, tmp->str);
    		tmp = tmp->next;
    	}
    }

### 3.双向链表删除节点 ###

/************************************************************************* 
    * Function:    void double_link_delete_nodes_for_num(s_msg_t **head, int num)
    * Description: 删除链表节点
    * Input:   
    *              s_msg_t *head 链表头
    *  int num     根据链表的数据删除的链表
    * Return:      NULL
    * Others:      NULL
    **************************************************************************/
    void double_link_delete_nodes_for_num(s_msg_t **head, int num)
    {
    	if (NULL == *head)
    	{
    		LOGD("double link is null, return.");
    		return ;
    	}
    	s_msg_t *tmp = *head, *pf;
    	while ((num != tmp->count) && (NULL != tmp->next))
    	{
    		tmp = tmp->next;
    	}
    	if (num == tmp->count)
    	{
    		if (tmp == (*head)) // 要删除的是头节点
    		{
    			if (NULL == (*head)->next)  // 如果只有头节点一个数据
    			{
    				(*head) = tmp->next;
    			}
    			else// 如果有两个以上的节点
    			{
    				(*head) = tmp->next;
    				(*head)->prev = NULL;
    			}
    		}
    		else // 要删除的是其它节点
    		{
    			if (NULL != tmp->next) // 删除的是中间节点
    			{
    				pf = tmp->prev;
    				pf->next = tmp->next;
    				(tmp->next)->prev = pf;
    			}
    			else // 删除尾节点
    			{
    				pf = tmp->prev;
    				pf->next = NULL;
    			}
    		}
    		free(tmp); // 释放节点
    	}
    	else
    	{
    		LOGD("not find the num, can't delete.");
    	}
    }

### 4.双向链表插入节点 ###

/************************************************************************* 
    * Function:    void double_link_insert_for_num(s_msg_t **head, s_msg_t *pnew)
    * Description: 按数据大小插入链表节点
    * Input:   
    *              s_msg_t **head 链表头
    *              s_msg_t *pnew  要插入的节点
    * Return:      NULL
    * Others:      NULL
    **************************************************************************/
    void double_link_insert_for_num(s_msg_t **head, s_msg_t *pnew)
    {
    	s_msg_t *pf, *tmp = (*head);
    	if (NULL == tmp) // 链表为空，新来的就是头节点
    	{
    		(*head)= pnew;
    		pnew->prev = NULL;
    		pnew->next = NULL;
    		return ;
    	}
    	while ((pnew->count >= tmp->count) && (NULL != tmp->next))
    	{
    		tmp = tmp->next;
    	}
    	if (pnew->count < tmp->count) // 找到一个tmp的count比pnew的count大,插到tmp前面
    	{
    		if (tmp == (*head)) // 找到的是头节点,查到头节点前面
    		{
    			pnew->next = *head;
    			(*head)->prev = pnew;
    			pnew->prev = NULL;
    			(*head) = pnew;
    		}
    		else // 插到中间位置
    		{
    			pf = tmp->prev; // pf指向找到节点的前一个位置
    
    			pnew->next = tmp;
    			pnew->prev = pf;
    
    			pf->next   = pnew;
    			tmp->prev  = pnew;
    		}
    	}
    	else // tmp中的count都比pnew中的count小,插到最后面
    	{
    		tmp->next  = pnew;
    		pnew->prev = tmp;
    		pnew->next = NULL;
    	}
    }

### 5.双向链表查找节点 ###

/************************************************************************* 
    * Function:    s_msg_t *double_link_search_for_num(s_msg_t *head, int num)
    * Description: 查找链表节点
    * Input:   
    *              s_msg_t **head 链表头
    *              int num要搜寻的节点的num
    * Return:      NULL
    * Others:      NULL
    **************************************************************************/
    s_msg_t *double_link_search_for_num(s_msg_t *head, int num)
    {
    	if (NULL == head)
    	{
    		LOGD("double link is null, return.");
    		return ;
    	}
    
    	s_msg_t *tmp = head;
    	while (NULL != tmp)
    	{
    		if (num == tmp->count)
    		{
    			LOGD("find nodes: count = %d, str = %s", tmp->count, tmp->str);
    			//return NULL;
    		}
    		tmp = tmp->next;
    	}
    
    	return NULL;
    	
    }

### 6.双向链表的释放 ###

注：释放方式可能还不完善

/************************************************************************* 
    * Function:    s_msg_t *double_link_search_for_num(s_msg_t *head, int num)
    * Description: 双向链表释放
    * Input:   
    *              s_msg_t **head 链表头
    * Return:      NULL
    * Others:      NULL
    **************************************************************************/
    void double_link_free(s_msg_t **head)
    {
    	if (NULL == (*head)) // 若为空，直接返回
    	{
    		LOGD("double link is null, return.");
    		return ;
    	}
    	LOGD("free double link.");
    	s_msg_t *tmp = NULL;
    	while (NULL != (*head)) // 若头部不为空
    	{
    		tmp = (*head);  // 临时变量赋值
    		(*head) = tmp->next;// head后移一位
    		tmp->next = NULL;   // 临时变量下一个指向空
    		if (NULL != *head)  // 判断head是否为空
    		{
    			(*head)->prev = NULL; // 不为空则前一个指向空
    		}
    		free(tmp);
    		tmp = NULL;
    	}
    }

demo源码：[点击下载双向链表demo][demo] 提取码：vfer

下载源码放到linux系统下直接make编译即可。

## 三、结束语 ##

大家通过上面的例子灵活运用，根据自己的需求去修改代码。就介绍到这里吧，通过多写代码加深对链表的使用。

[C_ -]: https://blog.csdn.net/Amosstan/article/details/84301750
[-]: https://baike.baidu.com/item/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/2968731?fr=aladdin
[demo]: https://pan.baidu.com/s/1bTXB0Fs6wrs4NBz21vyLYw