双向链表的C语言实现与基本操作（二）

左手的ㄟ右手 2022-06-17 06:13 150阅读 0赞

**本文的主要内容目录：**

一、链表结点元素的添加

二、链表结点元素的删除

三、链表结点元素的更改

四、链表结点元素的查询

在上一篇博文中已经对双向链表的实现做了比较详细地阐述，在一篇文章来说一说双向链表的四个基本操作：增、删、改、查。在讲基本操作之前，再来看看链表结点元素的结构体的实现，它是整个数据结构的核心。

/* 定义一个表示链表的结构体指针 */
    struct list {
    	int id;			/* 标识这个元素方便查找 */
    	char data[20];		/* 链表中包含的元素 */
    	struct list *next;	/* 指向下一个结点的指针 */
    	struct list *prev;	/* 指向前一个结点的指针 */
    };

**一、链表结点元素的添加**

本文所实现的链表结点元素的添加是在链表尾部来添加结点元素的，当然读者也可以根据对我实现的这个函数进行修改，使其可以在任何指定的位置添加元素。

算法的具体实现函数如下：

/**	将指定元素插入到聊表尾部
      * 	head	: 表示要插入元素的链表的头部的地址
      *	list    : 表示要插入到链表中的元素
      */
    static void list_add(struct list **head, struct list *list)
    {
    	struct list *temp;
    
    	/* 判断链表是否为空 */
    	if(NULL == *head)
    	{
    		/* 为空 */
    		*head = list;
    		(*head)->next = NULL;
    		(*head)->prev = NULL;
    	}
    	else
    	{
    		/* 不为空 */
    		temp = *head;
    		while(temp)
    		{
    			/* 将新结点插入到链表尾部 */
    			if(NULL == temp->next)
    			{
    				temp->next = list;
    				list->next = NULL;
    				list->prev = temp;
    				return;
    			}
    			temp = temp->next;
    		}
    	}
    }

先判断链表是否为空，如果为空直接返回NULL，否者对链表进行遍历找到链表的尾部，然后将要插入的结点元素插入到链表尾部，具体实现参考上面这个函数。

进行结点元素的添加测试，在main函数中添加如下代码：

/* 定义一个临时的链表结点元素 */
    	struct list temp_list;
    
    /* 对临时定义的结点元素进行赋值并加入到链表当中 */
    temp_list.id = list_id++;
    sprintf(temp_list.data, "temp_list node!");
    list_add(&list_head, &temp_list);
    
    /* 从头部遍历链表，把链表中每个元素的信息都打印出来 */
    list_print_head(&list_head);

编译运行结果如下：

![Center][]

**二、链表结点元素的删除**

对链表结点元素的删除，主要是根据链表结点的id进行的，id是一个整形值，是一个静态全局变量，每次赋值时都让其自增加1，这样可以保证加入到链表的结点元素拥有唯一的id号。这个全局的id定义如下：

static int list_id = 0;

结点元素删除的算法实现如下：

/**	将指定元素从链表尾部删除
      * 	head	: 表示要删除元素的链表的头部的地址
      *		id      : 表示要删除元素的标识
      *		返回值  : 0-成功，-1-失败
      */
    static int list_del(struct list **head, int id)
    {
    	struct list *temp, *p;
    	temp = *head;
    
    	if(NULL == temp)
    	{
    		/* 链表为空 */
    		printf("链表为空!\n");
    		return -1;
    	}
    	else
    	{
    		/* 判断匹配的元素是否为链表头部的元素 */
    		if(id == temp->id)		/* 是链表头部 */
    		{
    			*head = temp->next;
    			if(NULL != *head)
    				(*head)->prev = NULL;
    			return 0;
    		}
    		else					/* 不是链表头部 */
    		{
    			while(temp->next)
    			{
    				p = temp;
    				temp = temp->next;
    
    				if(id == temp->id)
    				{
    					p->next = temp->next;
    					if(NULL != temp->next)
    						temp->next->prev = p;
    					return 0;
    				}
    			}	
    			return -1;
    		}
    	}
    
    	return -1;
    }

先判断链表是否为空，为空直接返回-1，表示删除失败。如果不为空，判断是否为链表头部，如果是直接将链表结点的下一个元素赋值给链表头部；如果不是链表头部，这对链表进行遍历，根据id找到要删除的元素并将其从链表中移除。具体细节见上面函数的实现。

对删除操作进行测试，在main函数中添加如下代码：

/* 删除链表中开始位置、中间位置、尾部的元素 */
    list_del(&list_head, 0);
    list_del(&list_head, 5);
    list_del(&list_head, 10);
    
    /* 从头部遍历链表，把链表中每个元素的信息都打印出来 */
    list_print_head(&list_head);

编译运行结果如下所示：  
![Center 1][]

**三、链表结点元素的更改**

对链表结点元素的更改也是根据id号进行的，通过遍历链表找到匹配的id号然后对其的数据进行修改，实现相对容易，实现函数如下所示：

/**	将指定id的元素所定义的内容进行修改
      * 	head	: 表示要改变元素的链表的头部的地址
      *	id      : 表示要改变元素的标识
      *	content : 表示要改变的内容
      *	返回值  : 0-成功，-1-失败
      */
    static int list_chg(struct list **head, int id, char *content)
    {
    	struct list *temp;
    
    	temp = *head;	/* 将链表的头部赋值给临时聊表变量 */
    
    	while(temp)		/* 对链表进行轮询 */
    	{
    		if(id == temp->id)
    		{
    			memset(temp->data, 0, sizeof(temp->data));
    			sprintf(temp->data, "%s", content);
    			temp->data[strlen(content)] = '\0';
    			return 0;
    		}
    		temp = temp->next;
    	}
    	return -1;
    }

对更改结点元素的函数进行测试，在main函数中添加如下代码：

/* 改变id为4的元素所对应的值为 "change!!!" */
    list_chg(&list_head, 4, "change!!!");
    
    /* 从头部遍历链表，把链表中每个元素的信息都打印出来 */
    list_print_head(&list_head);

编译运行结果如下所示：  
![Center 2][]

**四、链表结点元素的查看**  
结点元素的查询也是根据id号进行的，查询相对容易实现，通过对链表进行遍历即可实现，具体实现函数如下所示：

/**	将指定id的元素所定义的内容进行查找
      * 	head	: 表示要查询元素的链表的头部的地址
      *	id      : 表示要查询元素的标识
      *	返回值  : 0-成功，-1-失败
      */
    static int list_query(struct list **head, int id)
    {
    	struct list *temp;
    
    	temp = *head;	/* 将链表的头部赋值给临时聊表变量 */
    
    	while(temp)		/* 对链表进行轮询 */
    	{
    		if(id == temp->id)
    		{
    			printf("list %d : %s\n", temp->id, temp->data);
    			return 0;
    		}
    		temp = temp->next;
    	}
    
    	/* 没有找到元素 */
    	printf("not finding!\n");
    	
    	return -1;
    }

对查询函数进行测试，在main函数中添加如下代码：

/* 查询链表中id为4的元素结点的内容 */
    list_query(&list_head, 4);

编译运行结果如下所示：

![Center 3][]

至此，双向链表的基本操作增、删、该、查都说完了，不过实现的较为简单，希望看到我博文的人多多指教，谢谢。

**附录：本文所涉及的双向链表的实现与基本操作的完整代码如下所示。**

/* 包含的头文件 */
    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <string.h>
    
    /* 定义一个表示链表的结构体指针 */
    struct list {
    	int id;			/* 标识这个元素方便查找 */
    	char data[20];		/* 链表中包含的元素 */
    	struct list *next;	/* 指向下一个结点的指针 */
    	struct list *prev;	/* 指向前一个结点的指针 */
    };
    
    /* 定义一个链表头部 */
    static struct list *list_head = NULL;
    
    /* 定义一个链表尾部 */
    static struct list *list_tail = NULL;
    
    /* 为了保证每一个链表元素的id不同，特意把id定义成一个全局静态变量 */
    static int list_id = 0;
    
    /**	将指定元素插入到聊表尾部
      * 	head	: 表示要插入元素的链表的头部的地址
      *	list    : 表示要插入到链表中的元素
      */
    static void list_add(struct list **head, struct list *list)
    {
    	struct list *temp;
    
    	/* 判断链表是否为空 */
    	if(NULL == *head)
    	{
    		/* 为空 */
    		*head = list;
    		(*head)->next = NULL;
    		(*head)->prev = NULL;
    	}
    	else
    	{
    		/* 不为空 */
    		temp = *head;
    		while(temp)
    		{
    			/* 将新结点插入到链表尾部 */
    			if(NULL == temp->next)
    			{
    				temp->next = list;
    				list->next = NULL;
    				list->prev = temp;
    				return;
    			}
    			temp = temp->next;
    		}
    	}
    }
    
    /**	将指定元素从链表尾部删除
      * 	head	: 表示要删除元素的链表的头部的地址
      *	id      : 表示要删除元素的标识
      *	返回值  : 0-成功，-1-失败
      */
    static int list_del(struct list **head, int id)
    {
    	struct list *temp, *p;
    	temp = *head;
    
    	if(NULL == temp)
    	{
    		/* 链表为空 */
    		printf("链表为空!\n");
    		return -1;
    	}
    	else
    	{
    		/* 判断匹配的元素是否为链表头部的元素 */
    		if(id == temp->id)		/* 是链表头部 */
    		{
    			*head = temp->next;
    			if(NULL != *head)
    				(*head)->prev = NULL;
    			return 0;
    		}
    		else					/* 不是链表头部 */
    		{
    			while(temp->next)
    			{
    				p = temp;
    				temp = temp->next;
    
    				if(id == temp->id)
    				{
    					p->next = temp->next;
    					if(NULL != temp->next)
    						temp->next->prev = p;
    					return 0;
    				}
    			}	
    			return -1;
    		}
    	}
    
    	return -1;
    }
    
    /**	将指定id的元素所定义的内容进行修改
      * 	head	: 表示要改变元素的链表的头部的地址
      *	id      : 表示要改变元素的标识
      *	content : 表示要改变的内容
      *	返回值  : 0-成功，-1-失败
      */
    static int list_chg(struct list **head, int id, char *content)
    {
    	struct list *temp;
    
    	temp = *head;	/* 将链表的头部赋值给临时聊表变量 */
    
    	while(temp)		/* 对链表进行轮询 */
    	{
    		if(id == temp->id)
    		{
    			memset(temp->data, 0, sizeof(temp->data));
    			sprintf(temp->data, "%s", content);
    			temp->data[strlen(content)] = '\0';
    			return 0;
    		}
    		temp = temp->next;
    	}
    	return -1;
    }
    
    /**	将指定id的元素所定义的内容进行查找
      * 	head	: 表示要查询元素的链表的头部的地址
      *	id      : 表示要查询元素的标识
      *	返回值  : 0-成功，-1-失败
      */
    static int list_query(struct list **head, int id)
    {
    	struct list *temp;
    
    	temp = *head;	/* 将链表的头部赋值给临时聊表变量 */
    
    	while(temp)		/* 对链表进行轮询 */
    	{
    		if(id == temp->id)
    		{
    			printf("list %d : %s\n", temp->id, temp->data);
    			return 0;
    		}
    		temp = temp->next;
    	}
    
    	/* 没有找到元素 */
    	printf("not finding!\n");
    	
    	return -1;
    }
    
    
    /**	通过链表的头部找到链表的尾部
      *	head	:	链表的头部的地址
      *	返回值	:	返回链表尾部的地址
      */
    static struct list *find_list_tail(struct list **head)
    {
    	struct list *temp = *head;
    	struct list *p = NULL;
    
    	/* 判断链表是否为空 */
    	if(NULL == temp)		/* 为空 */
    	{
    		return NULL;
    	}
    	else					/* 不为空 */
    	{
    		while(temp)
    		{
    			p = temp;
    			temp = temp->next;
    			if(NULL == temp) return p;
    		}
    	}
    
    	return NULL;
    }
    
    /** 遍历一个链表，打印链表中每个元素所包含的数据
      * head : 表示要遍历的链表的头部的指针
      */
    static void list_print_head(struct list **head)
    {	
    	struct list *temp;
    
    	temp = *head;
    
    	printf("list information form head:\n");
    	while(temp)
    	{
    		printf("\tlist %d : %s\n", temp->id, temp->data);
    		temp = temp->next;
    	}
    }
    
    /** 遍历一个链表，打印链表中每个元素所包含的数据
      * tail : 表示要遍历的链表的尾部的指针
      */
    static void list_print_tail(struct list **tail)
    {	
    	struct list *temp;
    
    	temp = *tail;
    
    	printf("list information form tail:\n");
    	while(temp)
    	{
    		printf("\tlist %d : %s\n", temp->id, temp->data);
    		temp = temp->prev;
    	}
    }
    
    
    /* 主函数，程序的入口 */
    int main(int argc, char *argv[])
    {
    	int i = 0;
    	struct list *lists = NULL;
    
    	/* 分配10个元素 */
    	lists = malloc(sizeof(struct list) * 10);
    	if(NULL == lists)
    	{
    		printf("malloc error!\n");
    		return -1;
    	}
    
    	/* 将分配的10个元素依次填充数据并加入到链表当中 */
    	for(i = 0; i < 10; i++)
    	{
    		lists[i].id = list_id++;
    		sprintf(lists[i].data, "TECH-PRO - %d", i);
    
    		list_add(&list_head, &lists[i]);
    	}
    
    	/* 找到链表尾部 */
    	list_tail = find_list_tail(&list_head);
    
    	/* 删除链表中开始位置、中间位置、尾部的元素 */
    	list_del(&list_head, 0);
    	list_del(&list_head, 5);
    	list_del(&list_head, 10);
    
    	/* 改变id为4的元素所对应的值为 "change!!!" */
    	list_chg(&list_head, 4, "change!!!");
    
    	/* 从头部遍历链表，把链表中每个元素的信息都打印出来 */
    	list_print_head(&list_head);
    
    	/* 查询链表中id为4的元素结点的内容 */
    	list_query(&list_head, 4);
    	
    	return 0;
    }

[Center]: /images/20220617/049664bfd1fc425fb59997ee6d8409bd.png
[Center 1]: /images/20220617/c28d15d7a08649d293e8448cd9129446.png
[Center 2]: /images/20220617/c4b6ddf60d5c440482a243ffec23fd8a.png
[Center 3]: /images/20220617/6a1ea4d8dbca4c5f8b7520f40cbd0e8c.png