单向链表的C语言实现与基本操作

Dear 丶 2022-06-17 04:29 179阅读 0赞

本文的主要内容目录：

一、单向链表的C语言实现

二、单向链表的基本操作

一、单向链表的C语言实现

链表作为一种基本的数据结构在程序开发过程当中经常会使用到。对C语言来说链表的实现主要依靠结构体和指针，所以本文相关内容和程序需要有C语言当中指针和结构体的基础。

链表是一种线性存储数据的结构，存储内容在逻辑上连续的，在物理上却不一定连续。单向链表的组成包括一个链表头（head）和若干链表元素（node），对链表的基本操作其实就是增、删、改、查。

首先说说单向链表的C语言实现方法。为了实现一个单向链表，首先定义一个结构体：

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

下面来编写程序实现一个链表的基本操作。该程序的功能是首先分配若干个链表元素（node），然后对这些链表元素进行赋初值，赋完初值之后将这些链表元素依次加入到链表当中，最后把这些元素的data字段依次打印出来。（注意 ：本程序实现的链表头结点（head）当中是存放数据的；为了保证每一个元素的id字段都不相同，所以定义了一个全局静态数据成员list\_id；使用linux下的gcc进行编译）。程序如下：

/* 包含的头文件 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义一个表示链表的结构体指针 */
    struct list {
    	int id;			/* 标识这个元素方便查找 */
    	char data[20];		/* 链表中包含的元素 */
    	struct list *next;	/* 指向下一个链表的指针 */
    };
    
    /* 定义一个链表头部 */
    static struct list *list_head = 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;
    	}
    	else
    	{
    		/* 不为空 */
    		temp = *head;
    		while(temp)
    		{
    			if(NULL == temp->next)
    			{
    				temp->next = list;
    				list->next = NULL;
    			}
    			temp = temp->next;
    		}
    	}
    }
    
    /** 遍历一个链表，打印链表中每个元素所包含的数据
      * head : 表示要遍历的链表的头部的指针
      */
    static void list_print(struct list **head)
    {	
    	struct list *temp;
    
    	temp = *head;
    
    	printf("list information :\n");
    	while(temp)
    	{
    		printf("\tlist %d : %s\n", temp->id, temp->data);
    		temp = temp->next;
    	}
    }
    
    /* 主函数，程序的入口 */
    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_print(&list_head);
    
    	return 0;
    }

程序的运行结果如下所示：  
![Center][]

二、单向链表的基本操作

链表的基本操作其实就是对链表中元素的操作。链表的基本操作包括链表中结点元素的添加、删除、修改和查看，简单来说就是增、删、改、查。

2.1 单向链表中元素添加

在链表中添加元素时首先判断链表是否为空，为空时直接把要添加的元素赋值给链表头部，否者就要对链表进行遍历找到下一个为空的结点，然后把元素插入到链表尾部。

实现链表插入的程序代码：

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

在main函数中田间如下代码：

struct list temp_list;
    
    /* 填充这个结构体并加入链表当中 */
    	temp_list.id = list_id++;
    	sprintf(temp_list.data, "temp_list");
    	list_add(&list_head, &temp_list);

对程序进行编译，结果如下：

![Center 1][]

2.2 在单向链表中删除元素

在链表删除一个元素结点是链表基本操作中相对复杂的。首先需要判断链表是否为空，当链表不为空时，要再次判断要删除的元素是否是头结点（head），如果是直接将下一个元素赋值给头结点，不过不是就需要遍历整个链表找到要删除的结点元素。（注：本算法实现的删除是通过对元素结点的id字段进行的）。

删除链表结点的程序代码：

/**	将指定元素从链表尾部删除
      * 	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;
    			return 0;
    		}
    		else					/* 不是链表头部 */
    		{
    			while(temp->next)
    			{
    				p = temp;
    				temp = temp->next;
    
    				if(id == temp->id)
    				{
    					p->next = temp->next;
    					return 0;
    				}
    			}	
    			return -1;
    		}
    	}
    
    	return -1;
    }

在main函数中添加如下代码：

/* 删除链表中开始位置、中间位置、尾部的元素 */
    	list_del(&list_head, 0);
    	list_del(&list_head, 5);
    	list_del(&list_head, 10);

对程序进行编译结果如下所示，第0、5、10号元素都被删除：

![Center 2][]

2.3 在单向链表中修改指定的元素

在链表中修改元素，通过对链表中元素进行遍历，找到要修改的元素对其内容分进行修改即可，实现链表元素的修改是相对容易的。（注 ：对要修改的元素的定位是通过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!!!");

编译程序，运行结果如下所示：

![Center 3][]

2.4 对单向链表的元素进行查询操作

在链表中查询一个元素，根据链表头部对链表进行遍历即可。

链表中查询的程序代码：

/**	将指定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;
    }

程序运行结果：

![Center 4][]

**附录：单向链表的基本操作已经说完，附上一个完整的程序。**

/* 包含的头文件 */
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    /* 定义一个表示链表的结构体指针 */
    struct list {
    	int id;				/* 标识这个元素方便查找 */
    	char data[20];		/* 链表中包含的元素 */
    	struct list *next;	/* 指向下一个链表的指针 */
    };
    
    /* 定义一个链表头部 */
    static struct list *list_head = 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;
    	}
    	else
    	{
    		/* 不为空 */
    		temp = *head;
    		while(temp)
    		{
    			if(NULL == temp->next)
    			{
    				temp->next = list;
    				list->next = NULL;
    			}
    			temp = temp->next;
    		}
    	}
    }
    
    /** 遍历一个链表，打印链表中每个元素所包含的数据
      * head : 表示要遍历的链表的头部的指针
      */
    static void list_print(struct list **head)
    {	
    	struct list *temp;
    
    	temp = *head;
    
    	printf("list information :\n");
    	while(temp)
    	{
    		printf("\tlist %d : %s\n", temp->id, temp->data);
    		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;
    			return 0;
    		}
    		else					/* 不是链表头部 */
    		{
    			while(temp->next)
    			{
    				p = temp;
    				temp = temp->next;
    
    				if(id == temp->id)
    				{
    					p->next = temp->next;
    					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;
    }
    
    
    /* 主函数，程序的入口 */
    int main(int argc, char *argv[])
    {
    	int i = 0;
    	struct list *lists = NULL;
    
    	struct list temp_list;
    
    	/* 分配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]);
    	}
    
    	/* 填充这个结构体并加入链表当中 */
    	temp_list.id = list_id++;
    	sprintf(temp_list.data, "temp_list");
    	list_add(&list_head, &temp_list);
    
    	/* 删除链表中开始位置、中间位置、尾部的元素 */
    	list_del(&list_head, 0);
    	list_del(&list_head, 5);
    	list_del(&list_head, 10);
    
    	/* 改变id为4的元素所对应的值为 "change!!!" */
    	list_chg(&list_head, 4, "change!!!");
    
    	/* 查询链表中id为4的元素结点的内容 */
    	list_query(&list_head, 4);
    
    	return 0;
    }

[Center]: /images/20220617/2a58a6f29fc144fca32a5e4ce85c132f.png
[Center 1]: /images/20220617/606284a395dc48c6bab029d3d01d84e5.png
[Center 2]: /images/20220617/0903f7f20c4f4d6d8c4bb8166d8701c2.png
[Center 3]: /images/20220617/78af194db81c4f61b9f3bc7ac5859caa.png
[Center 4]: /images/20220617/9d26b7d07d4648ab8c96743ee0c3383b.png