C语言数据结构之链表的增删改查

本是古典何须时尚 2022-11-25 15:29 238阅读 0赞

## C语言数据结构之链表的增删改查 ##

tips:昨天学习了c语言结构体，今天来看看c语言数据结构之链表(单链表)的增删改查操作

--------------------

**首先我们创建一个简单的学生信息结构体，作为后面增删改查的主体**  
*student结构体包含  
数据域：学号，分数；  
指针域：一个指向后继结点的pNext指针；*

typedef struct student {
        
    	int num;
    	int score;
    	struct student *pNext;
    }stu, *pstu;

--------------------

链表测试输出函数

//链表打印
    void list_print(pstu phead)
    {
        
    	while (phead)//循环终止条件
    	{
        
    		printf("%d：%d分\n", phead->num,phead->score);
    		phead = phead->pNext;//打印下一个结点
    	}
    	printf("-------------------------------------\n");
    }

###### 一、链表的新增 ######

**链表的新增分为3种方式**  
***1、头插法：新增的结点作为原链表的头结点，原链表头结点顺序后移  
2、尾插法：新增的结点作为原链表的尾结点，原链表尾结点变为倒数第二个结点  
3、有序插入：新增的结点按照一定顺序，有序的插入链表中***

--------------------

***tips：在链表操作中用二级指针操作一级指针，并且为链表定义两个指针：phead头指针，ptail尾指针***

--------------------

**1.头插法**  
思路：  
***1.1创建新结点，并将其初始化  
1.2当原链表为空时，插入新结点后，原链表头指针和尾指针要同时指向新结点  
1.3当原链表不为空时，插入新结点后，原链表头指针指向新结点，新结点的pNext指针指向原头结点***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70]  
具体实现：

//头插法
    void list_head_insert(pstu *pphead, pstu *pptail, int i)
    {
        
    	pstu pnew = (pstu)malloc(sizeof(stu));//给新结点申请空间
    	
    	//给新结点初始化
    	pnew->num = i;
    	pnew->score = 90;//每个同学90分，保证公平！
    	pnew->pNext = NULL;
    
    	//初始化完成后就开始插入
    	if (*pphead == NULL)//判断链表为空（头指针为空，链表就为空）
    	{
        
    		//如果链表为空，头指针和尾指针都指向新结点
    		//头尾指针同时指向新结点
    		*pphead = pnew;
    		*pptail = pnew;
    	}
    	else
    	{
        
    		//不为空,往前插入新结点
    		pnew->pNext = *pphead;//将现有头结点放在新结点之后
    		*pphead = pnew;//pnew成为新的头结点,ptail不变，头指针指向新结点
    	}
    }//头插法，输出的是逆序

输出测试方法及结果：

//测试循环插入
    	pstu phead = NULL, ptail = NULL;
    	int i;
    	while (scanf("%d", &i) != EOF)
    	{
        
    		list_head_insert(&phead, &ptail, i);
    	}
    	list_print(phead);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 1]

--------------------

**2.尾插法**  
思路：  
***2.1创建新结点，并将其初始化  
2.2当原链表为空时，插入新结点后，原链表头指针和尾指针要同时指向新结点  
2.3当原链表不为空时，插入新结点后，原链表尾结点的pNext指向新结点，原链表的尾指针指向新结点***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 2]  
具体实现：

//尾插法
    void list_tail_insert(pstu *pphead, pstu *pptail, int i)
    {
        
    	pstu pnew = (pstu)malloc(sizeof(stu));//给新节点申请一个结构体大小的空间
    
    	//新节点初始化
    	pnew->num = i;
    	pnew->score = 90;//每个同学90分，保证公平！
    	pnew->pNext = NULL;
    
    	//开始插入
    	if (*pphead==NULL)//判断原有链表是否为空
    	{
        
    		//为空，新结点插入进来，头尾指针指向新结点
    		*pphead = pnew;
    		*pptail = pnew;
    	}
    	else
    	{
        
    		//不为空,往后插入新结点
    		(*pptail)->pNext = pnew;//将原结点的最后一个连接上新结点
    		*pptail = pnew;//新结点变成尾节点
    	}
    
    }//尾插法输出的是顺序

输出测试方法及结果：

//测试循环插入
    	pstu phead = NULL, ptail = NULL;
    	int i;
    	while (scanf("%d", &i) != EOF)
    	{
        
    		list_tail_insert(&phead, &ptail, i);
    	}
    	list_print(phead);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 3]

--------------------

**3.有序插入**  
思路：  
***3.1创建新结点，并将其初始化  
3.2当原链表为空时，插入新结点后，原链表头指针和尾指针要同时指向新结点  
3.3当原链表不为空时，根据插入结点学号i的大小确定新结点插入的位置：  
· 如果新结点学号小于头结点学号，则插入头部；  
· 如果新结点学号大于头结点学号则插入位置时中间或者尾部；  
循环遍历整个链表，为新结点找位置，当前指针指向的结点的i>新结点时，那么也可以说明前一个结点的i小于新结点，则说明新结点找到中间位置插入。（这里需要定义一个指针pcur指向循环遍历当前结点，还需定义一个指针ppre指向当前结点的前一个结点，说白了就是两个工具人！）找到位置后，当前结点的前一个结点的pNext指向新结点，新结点的pNext指向当前结点；  
如果遍历完整个链表都没有找到位置插入，则插入尾部；***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 4]  
具体实现：

//有序插入链表
    void list_sort_insert(pstu *pphead, pstu *pptail, int i)
    {
        
    	pstu pcur;//保存当前结点信息；
    	pstu ppre;//保留pcur前一个结点信息；
    
    	//新建一个结点
    	pstu pnew = (pstu)malloc(sizeof(stu));
    
    	//对新结点初始化
    	pnew->num = i;
    	pnew->score = 90;//每个同学90分，保证公平！
    	pnew->pNext = NULL;
    
    	pcur = *pphead;//当前结点指针,初始化等于头指针
    	ppre = *pphead;
    
    	if (pcur == NULL)//判断链表是否为空
    	{
        
    		//链表为空,插入后头指针尾指针指向插入的结点
    		*pphead = pnew;
    		*pptail = pnew;
    	}
    	else if (i < pcur->num)//是否插入头部.当插入的结点小于头结点时候插入头部
    	{
        
    		//新结点变成头结点
    		pnew->pNext = *pphead;
    		*pphead = pnew;
    	}
    	else {
        
    		//插入中间和尾部
    		while (pcur)//遍历整个链表，找中间位置插入
    		{
        
    			if (pcur->num > i)//链表当前结点值大于要插入结点的值
    			{
        
    				//新结点插入两个结点之间
    				pnew->pNext = pcur;
    				ppre->pNext = pnew;
    
    				break;//插入后跳出循环
    			}
    			ppre = pcur;//将当前位置信息赋给ppre
    
    			pcur=pcur->pNext;
    
    		}
    		if (pcur==NULL)//中间没有位置插入，往最后插入
    		{
        
    			//新结点变成最后一个结点，原来尾指针新结点
    			(*pptail)->pNext = pnew;
    			//尾指针重新指向新结点	
    			*pptail = pnew;
    		}
    	}
    }

输出测试方法及结果：

//测试循环插入
    	pstu phead = NULL, ptail = NULL;
    	int i;
    	while (scanf("%d", &i) != EOF)
    	{
        
    		list_sort_insert(&phead, &ptail, i);
    	}
    	list_print(phead);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 5]

--------------------

###### 二、链表的删除 ######

思路  
***1.当链表为空时，输出链表为空  
2.当链表不为空时  
2.1删除的是头结点：头指针指向头结点的下一个结点，释放原头结点空间，还需判断删完后，原链表是否为空，若为空，则尾指针要置位NULL；  
2.2删除的是中间结点或者尾结点：循环遍历整个链表，找到要删除结点的位置，当前指针指向的结点的i==新结点时，则说明位置找到。（这里需要定义一个指针pcur指向循环遍历当前结点，还需定义一个指针ppre指向当前结点的前一个结点，说白了就是两个工具人！！）找到位置后，当前结点的前一个结点的pNext指向当前结点的pNext，释放当前结点空间；当遍历到达尾结点找到位置，则删除尾结点，将尾指针指向当前结点的前一个结点；当遍历完链表没有找到删除位置，则链表中没有符合条件的结点；***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 6]  
具体实现：

//根据i删除链表结点
    void list_delete(pstu *pphead, pstu *pptail, int i) 
    {
        
    	//首先判断链表是否为空
    	pstu pcur = *pphead;//用来当工具人
    	pstu ppre = *pphead;//工具人，用来保存当前结点前一个结点的信息
    	if (pcur == NULL)
    	{
        
    		printf("当前链表为空！\n");
    	}
    	else if(pcur->num==i)//删除的是头结点
    	{
        
    		(*pphead)->pNext = pcur->pNext;
    		//释放结点空间
    		free(pcur);
    		//删完后判断链表是否为空，如果链表为空*pptail=NULL
    		if ((*pphead) == NULL)
    		{
        
    			*pptail = NULL;
    		}
    	}
    	else//删除中间或尾结点
    	{
        
    		//删除的是中间结点，循环遍历
    		while (pcur)//循环遍历找到结点值为i的
    		{
        
    			if (pcur->num == i)
    			{
        
    				//找到符合条件的结点就删除该结点
    				ppre->pNext = pcur->pNext;
    				free(pcur);//释放掉当前被删除结点的空间
    				break;
    			}
    			ppre = pcur;//先将此结点信息保存到ppre，pcur再往后移
    			pcur = pcur->pNext;
    
    		}
    		//删除的是尾结点
    		if (pcur == *pptail)
    		{
        
    			*pptail = ppre;//尾指针前移
    		}
    		if (pcur == NULL)//删除的结点不在链表中
    		{
        
    			printf("该链表中没有结点值为%d的结点!\n", i);
    		}
    	}
    
    }

输出测试及结果：

pstu phead = NULL, ptail = NULL;//定义头尾指针，描述链表
    	int i；
    	while (printf("请输入要删除结点的值（num）:"), scanf("%d", &i) != EOF)
    	{
        
    		list_delete(&phead, &ptail, i);
    		list_print(phead);
    	}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 7]

###### 三、链表的修改 ######

思路：  
***1.当链表为空时，输出链表为空。  
2.当链表不为空时，循环遍历链表找到符合条件的结点，修改值。若找不到符合条件的结点，则输出该结点不在链表。***

具体实现：

void list_modify(pstu phead, int i, int score)
    {
        
    	//判断链表是否为空
    	if (phead == NULL)
    	{
        
    		printf("当前链表为空！\n");
    	}
    	else
    	{
        
    		//遍历寻找符合条件的结点
    		while (phead)
    		{
        
    			if (phead->num == i)
    			{
        
    				phead->score = score;
    				break;
    			}
    			phead=phead->pNext;
    		}
    		if(phead==NULL)
    		{
        
    			printf("该链表中没有结点值为%d的结点!\n", i);
    		}
    
    	}
    }

输出测试及结果：

pstu phead = NULL, ptail = NULL;//定义头尾指针，描述链表
    	int i,score;
    	while (printf("请输入要改变结点的值（num score）:"), scanf("%d %d", &i,&score) != EOF)
    	{
        
    		list_modify(phead,i,score);
    		list_print(phead);
    	}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 8]

###### 四、链表的查找 ######

思路：  
***1.当链表为空时，输出链表为空。  
2.当链表不为空时，循环遍历链表找到符合条件的结点，输出值。若找不到符合条件的结点，则输出该结点不在链表。***

具体实现：

//查找对应结点i的信息
    void list_search(pstu phead, int i)
    {
        
    	//判断链表是否为空
    	if (phead == NULL)
    	{
        
    		printf("当前链表为空！\n");
    	}
    	else
    	{
        
    		//遍历寻找符合条件的结点
    		while (phead)
    		{
        
    			if (phead->num == i)
    			{
        
    				printf("%d：%d分\n", phead->num, phead->score);
    				break;
    			}
    			phead = phead->pNext;
    		}
    		if (phead == NULL)
    		{
        
    			printf("该链表中没有结点值为%d的结点!\n", i);
    		}
    
    	}
    }

输出测试及结果：

pstu phead = NULL, ptail = NULL;//定义头尾指针，描述链表
    	int i;
    	while (printf("请输入要查询结点的值（num）:"), scanf("%d", &i) != EOF)
    	{
        
    		list_search(phead,i);
    	}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 9]

--------------------

链表的增删改成至此已经完成了，希望大家看了能有收获！

--------------------

tips：在这个世界上取得成就的人，都努力去寻找他们想要的机会，如果找不到机会，他们便自己创造机会。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70]: /images/20221124/79fac3e4883f4646b00020854640f88b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 1]: /images/20221124/b852e7f345a44a158f3a066829ed5e0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 2]: /images/20221124/60c5836608d7480ba514a278eaed7dcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 3]: /images/20221124/0f7716829db34929869879050280e176.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 4]: /images/20221124/55996a1d70d0449d950422355e69d8a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 5]: /images/20221124/faac736707ea47a8a954bc44d6ab8d90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 6]: /images/20221124/51992ea5eaac4db6b4f7da4a6f47d8be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 7]: /images/20221124/549b15f2bd6f4c5c88167253a44e407e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 8]: /images/20221124/337fdba9d43f43e99e0a05fa540e0818.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 9]: /images/20221124/2da19422caa846988f2458eb2117bc4f.png