链表（一）

r囧r小猫 2022-06-12 02:12 125阅读 0赞

# 前言 #

*  数据链表无所不在，尤其是在大型项目中。对于C语言，链表有Linux内核链表及用户自建链表。在处理数据量较大，程序较复杂时，使用链表可使我们的程序更加高效，各节点之间互不影响。
 *  链表种类可分为以下几种：  
    ![这里写图片描述][SouthEast]
 *  而对链表的操作，主要有以下几种：  
    （1）建立链表结构体；  
    （2）创建头结点（初始化链表）；  
    （3）创建新节点；  
    （4）在链表前或链表后插入新节点；  
    （5）删除某一节点；  
    （6）移动某一节点；  
    （7）查找某一节点（或遍历链表）。
 *  链表总的来说，难点不在于以上几种方式。主要是要应用到链表的程序一般都较复杂，节点的信息量一般都很大。目前我所碰到一个较复杂的链表节点是：

typedef struct tag_task_mgr
    {
    	IPTASK task_pool[20];
    	PIPTASK task_free_list;  	//空闲任务链表
    	PIPTASK task_register_list;	//注册任务链表
    	
    	PIPTASK task_execute_list;	//执行任务链表
    	PIPTASK task_suspend_list;  //挂起任务链表
    }TASK_MSG_DATA;
    
    typedef struct tag_ip_task
    {
    	const char *task_name;			//任务名
    	const char *task_description;	//任务描述符
    	
    	PIPTASKINTERFACE interface;		//任务入口
    	uint32_t curstepnumber;			//当前任务执行的步数
    	struct tag_ip_task *next;		//链表指针
    }IPTASK,PIPTASK;
    
    typedef struct tag_task_interface
    {
    	PTASKINIT Inital;		//函数指针
    	PTASKPROCESS Process;	//函数指针
    }PIPTASKINTERFACE;

接下来，将根据链表的基本操作进行逐一的解释（以双向链表为例）。

# 一、链表的基本操作 #

## 1. 设计链表节点 ##

typedef struct node
    {
    	int data;
    	... ...
    	... ...
    	... ...
    	struct node *prev;  //链表指针，指向前一个节点
    	struct node *next;  //链表指针，指向下一个节点
    }listnode, *plistnode;

## 2.创建头结点（初始化空链表） ##

*  初始化空链表有两种形式，一是带有头结点的链表，另一种是不带头结点的链表。这两者的区别如下：  
    ![这里写图片描述][SouthEast 1]
 *  不带头结点：该类方法是直接使用节点指针指向NULL即可；  
    带头结点：创建一个头结点指针，该节点是不带数据的，其节点指针执行下一节点即可。
 *  一般而言，我们更倾向于带有头结点的链表，因为这样我们无需判断该链表是否为空，可直接对链表进行操作。
 *  初始化空链表的方法（以带节点的双向链表为例，下同）：  
    ![这里写图片描述][SouthEast 2]
 *  主要是步骤是：  
    （1）申请堆内存；  
    （2）初始化链表节点指向。

plistnode init_list(void)
    {
    	plistnode head = (plistnode)malloc(sizeof(struct node));//创建头节点
    	if (NULL != head)
    	{
    		head->prev = head->next = head;  //初始化头结点指针
    		return head;
    	}
    	else
    	{
    		return NULL;
    	}
    }

## 3.创建新节点 ##

*  创建新节点无外乎跟创建空链表一样，有一个较大的差别就是新节点的节点指针指向的是NULL，而不是自身。
 *  答：这主要是便于我们在使用链表的时候遍历节点，拿到头结点我们就可以直接遍历，而不用再去判断其是否为空，另一方面，是方便我们在遍历链表的时候，能够快速的退出当前链表，避免在此链表内出现死循环。
 *  具体的实现代码如下：

plistnode new_node(int data)   //此处可增加节点的参数
    {
    	plistnode new = (plistnode)malloc(sizeof(struct node));
    	if (NULL != new)   //为啥NULL要在前面呢？？？这是一种防止漏写等号右边的数值的编程经验
    	{
    		new->data = data;    //节点参数处理
    		new->prev = new->next = NULL;
    	}
    	
    	return new;
    }

## 4.插入节点 ##

*  对于插入节点来说又有两种方式：一种是节点前插入，另一种是节点后插入。何为前后呢？这是将当前节点插入时所选取参考节点的前后位置而已。
 *  后插入（将新节点插入到当前节点的下一个位置）  
    假设当前节点为：anchor，新节点为：new下同。  
    第1步：将新节点的prev指针指向anchor节点：new->prev = anchor;  
    ![这里写图片描述][SouthEast 3]  
    第2步：将新节点的next指向anchor的next：new->next = anchor->next;  
    ![这里写图片描述][SouthEast 4]  
    第3步：将当前节点anchor的next执行new：anchor->next = new;  
    ![这里写图片描述][SouthEast 5]  
    第4步：将当前节点anchor原来的下一个节点的prev指向新节点new：new->next->prev = new;  
    ![这里写图片描述][SouthEast 6]
 *  具体的实现代码如下：

void insert_next(plistnode new, plistnode anchor)
    {
    	if (NULL == new || NULL == anchor)
    		return;
    	new->next = anchor->next;  	//第1步
    	new->prev = anchor;			//第2步
    	
    	anchor->next = new;			//第3步
    	new->next->prev = new;		//第4步
    }

*  前插入（将新节点new插入到当前节点anchor的前一个位置）  
    第1步：将新节点的next指针指向anchor节点：new->next = anchor;  
    ![这里写图片描述][SouthEast 7]  
    第2步：将新节点的prev指向anchor的prev：new->prev = anchor->prev;  
    ![这里写图片描述][SouthEast 8]  
    第3步：将当前节点anchor的prev执行new：anchor->prev = new;  
    ![这里写图片描述][SouthEast 9]  
    第4步：将当前节点anchor原来的前一个节点的next指向新节点new：new->prev->next = new;  
    ![这里写图片描述][SouthEast 10]

void insert_prev(plistnode new, plistnode anchor)
    {
    	if (NULL == new || NULL == anchor)
    		return;
    	
    	new->prev = anchor->prev;	//第1步
    	new->next = anchor;			//第2步
    	
    	anchor->prev = new;			//第3步
    	new->prev->next = new;		//第4步
    }

## 5.删除节点 ##

*  删除一个节点的不做很简单，无外乎移动几个指针即可。主要是将其前趋节点的指向其后续节点，其后续节点指向前趋节点。在删除节点是需要注意处理指针的顺序，否则将会导致无法找到相关的节点。
 *  首先：调整带删除节点的前后节点的next和prev指针  
    ![这里写图片描述][SouthEast 11]
 *  其次：将待删除节点的next和prev指针置空  
    ![这里写图片描述][SouthEast 12]
 *  具体的实现代码如下：

void remove_node(plistnode delete)
    {
    	if (NULL == delete)
    		return;
    	
    	delete->prev->next = delete->next;	//第1步
    	delete->next->prev = delete->prev;	//第2步
    	
    	delete->prev = NULL;				//第3步
    	delete->next = NULL;				//第4步
    }

## 6.移动节点 ##

*  移动节点同样有两种形式：一是移动到某节点anchor的后面，二是移动到某节点anchor的前面。
 *  （1）移到节点anchor的后面  
    ![这里写图片描述][SouthEast 13]

具体实现代码：

void move_next(plistnode p, plistnode anchor)
    {
    	if (NULL == p || NULL == anchor)
    		return;
    	
    	remove_node(p);
    	insert_next(p, anchor);
    }

*  （2）移到节点anchor前面  
    ![这里写图片描述][SouthEast 14]

具体实现代码：

void move_prev(plistnode p, plistnode anchor)
    {
    	if (NULL == p || NULL == anchor)
    		return;
    	
    	remove_node(p);
    	insert_prev(p, anchor);
    }

*  移动某一节点，主要有两步，一是将该节点从链表中提取（删除）出来，然后再将该节点插入到新节点的位置即可。

## 7.查找节点 ##

*  查找节点就是对链表进行遍历，从头开始，直到找到所需要的节点或者遍历完整个链表。具体的代码如下：

plistnode find_node(int data, listnode listhead)
    {
    	if (is_empty(listhead))
    		return NULL;
    	
    	plistnode tmp = listhead->next; 	//从头结点的下一节点开始遍历
    	
    	while (listhead != tmp)
    	{
    		if (data == tmp->data)			//比较数据，是否为自己想要的节点
    			return tmp;
    		
    		tmp = tmp->next;				//继续遍历下面的节点
    	}
    	
    	return NULL;
    }

# 二、以上所有代码的整体实现代码如下： #

#include <stdio.h>
    
    #define SIZE 20
    
    typedef enum
    {
    	err = -1;
    	 ok = 0;
    };
    
    enum {insert, delete, move_p, move_n, quit};
    
    typedef struct node
    {
    	int data;
    	struct node *prev;
    	struct node *next;
    }listnode, *plistnode;
    
    plistnode init_list(void)
    {
    	plistnode head = (plistnode)malloc(sizeof(struct node));
    	if (NULL != head)
    	{
    		head->prev = head->next = head;
    		return head;
    	}
    	else
    	{
    		return NULL;
    	}
    }
    
    plistnode new_node(int data)
    {
    	plistnode new = (plistnode)malloc(sizeof(struct node));
    	if (NULL != new)
    	{
    		new->data = data;
    		new->prev = new->next = NULL;
    	}
    	
    	return new;
    }
    
    bool is_empty(plistnode mylist)
    {
    	return mylist->prev == mylist->next;
    }
    
    void insert_prev(plistnode new, plistnode anchor)
    {
    	if (NULL == new || NULL == anchor)
    		return;
    	
    	new->prev = anchor->prev;	//第1步
    	new->next = anchor;			//第2步
    	
    	anchor->prev = new;			//第3步
    	new->prev->next = new;		//第4步
    }
    
    void insert_next(plistnode new, plistnode anchor)
    {
    	if (NULL == new || NULL == anchor)
    		return;
    	
    	new->next = anchor->next;  	//第1步
    	new->prev = anchor;			//第2步
    	
    	anchor->next = new;			//第3步
    	new->next->prev = new;		//第4步
    }
    
    void remove_node(plistnode delete)
    {
    	if (NULL == delete)
    		return;
    	
    	delete->prev->next = delete->next;	//第1步
    	delete->next->prev = delete->prev;	//第2步
    	
    	delete->prev = NULL;				//第3步
    	delete->next = NULL;				//第4步
    }
    
    void move_prev(plistnode p, plistnode anchor)
    {
    	if (NULL == p || NULL == anchor)
    		return;
    	
    	remove_node(p);
    	insert_prev(p, anchor);
    }
    
    void move_next(plistnode p, plistnode anchor)
    {
    	if (NULL == p || NULL == anchor)
    		return;
    	
    	remove_node(p);
    	insert_next(p, anchor);
    }
    
    void show_list(plistnode head)
    {
    	plistnode tmp = head->next;
    	
    	int flag = 0;
    	while( mylist != tmp)
    	{
    		printf("%s", flag == 0 ? "" : "->");
    		printf("%d", tmp->data);
    		tmp = tmp->next;
    		flag = 1;
    	}
    	
    	printf("\n");
    }
    
    int parse(char *buf, int *num)
    {
    	if (NULL == buf || NULL == num || (!(strcmp(buf, "\n")) ) )
    		return err;
    	
    	char *p, delim[] = ",";
    	
    	p = strtok(buf, delim);	//获取数据
    	num[0] =  atoi(p);		//将数据转化为整型数
    	if (0 == num[0])
    		return quit;
    	
    	if (NULL != p)
    	{	
    		if ('p' == p[0])	//往前移动节点
    		{
    			num[1] = atoi(p + 1);
    			return move_p;
    		}
    		else if ('n' == p[0])
    		{
    			num[1] = atoi(p + 1);	//往后移动节点
    			return move_n;
    		}
    		else 
    			return (num[0] > 0 ? insert : delete);
    	}
    }
    
    plistnode find_node(int data, listnode listhead)
    {
    	if (is_empty(listhead))
    		return NULL;
    	
    	plistnode tmp = listhead->next; 	//从头结点的下一节点开始遍历
    	
    	while (listhead != tmp)
    	{
    		if (data == tmp->data)			//比较数据，是否为自己想要的节点
    			return tmp;
    		
    		tmp = tmp->next;				//继续遍历下面的节点
    	}
    	
    	return NULL;
    }
    
    int main(void)
    {
    	char buf[SIZE];
    	int number[2], ret;
    	
    	plistnode listhead = NULL;
    	listhead = init_list();
    	if (NULL == listhead)
    	{
    		printf("init list failed\n");
    		return err;
    	}
    	
    	while (1)
    	{
    		bzero(buf, SIZE);
    		bzero(number, 2);
    		
    		fgets(buf, SIZE, stdin);  //输入一行数据，以回车结束输入
    		ret = parse(buf, number); //转换所输入的数据
    		
    		plistnode new, tmp, p1, p2;
    		switch (ret)
    		{
    			case insert:
    				new = new_node(numbre[0]);
    				insert_prev(new, listhead);
    				break;
    			
    			case delete:
    				tmp = find_node(-numbre[0], listhead);
    				remove_node(tmp);
    				free(tmp);
    				break;
    				
    			case move_p:
    				p1 = find_node(number[0], listhead);
    				p2 = find_node(numbre[1], listhead);
    				move_prev(p1, p2);
    				break;
    				
    			case move_n:
    				p1 = find_node(numbre[0], listhead);
    				p2 = find_node(number[1], listhead);
    				move_next(p1, p2);
    				break;
    			
    			case quit:
    				exit(0);
    		}
    		
    		show_list(listhead);
    	}
    	
    	return 0;
    }

[SouthEast]: /images/20220612/41b99cda9519418ba8091cceb1c5ded6.png
[SouthEast 1]: /images/20220612/ee7ee4d7eb1b4ebf88f5523cb7fb1798.png
[SouthEast 2]: /images/20220612/bb76a37bd1234f77aa314fda511379e7.png
[SouthEast 3]: /images/20220612/4d70840d5a424894b132fd452e3ad9db.png
[SouthEast 4]: /images/20220612/d0e25a591292459f90c493881843d412.png
[SouthEast 5]: /images/20220612/7299b5b206d7439f9f337ef5641d6863.png
[SouthEast 6]: /images/20220612/bcd13775de3f44f1987c8bd383e1ff44.png
[SouthEast 7]: /images/20220612/8f10d9c27f1741c49341b005f16dac69.png
[SouthEast 8]: /images/20220612/8da2c615a1344f298cfa47834b5a4ecb.png
[SouthEast 9]: /images/20220612/cc20f31a66244e1298732c34fe1d8c7f.png
[SouthEast 10]: /images/20220612/ca34e092db8c48b1bb7a5743edc47912.png
[SouthEast 11]: /images/20220612/8670cf4574eb457099d64eca3603eee5.png
[SouthEast 12]: /images/20220612/81741d8d9d7c4898a792b5d04c98005b.png
[SouthEast 13]: /images/20220612/a0dbd2a90daa4350ab23f58488605188.png
[SouthEast 14]: /images/20220612/02b37c146ea0466e96704dd594551418.png