单链表详解

ゞ浴缸里的玫瑰 2024-03-26 16:52 50阅读 0赞

#### 单链表 ####

*  一.概念
 *   *  二.一些类型的创建
     *  三.尾插
     *  四.头插
 *  五.头删尾删
 *  六.打印链表
 *  七.单链表查找,任意位置插入，任意位置删除
 *  八.源代码

![在这里插入图片描述][9185c03c2da240c085869433068ad075.png]

## 一.概念 ##

> **该篇链表博客是按照工程项目的格式来记录的，与平常的算法链表有些许不同，注意区分。**

![在这里插入图片描述][1b2e182d58174abdb0ef58777e4acc72.png]

![在这里插入图片描述][93cc5e1217004e8f8ba6781345f1421d.png]

### 二.一些类型的创建 ###

![在这里插入图片描述][343f6c0eae274c5686ceb2b2c9b9f1ac.png]

![在这里插入图片描述][dc9169f6672944bbb5ba1329ed73e41d.png]

### 三.尾插 ###

> **因为需要凭空插入一个数，所以我们肯定需要新开辟一个节点（newnode）来存放需要插入的数。之后我们需要找到原链表的尾部再将其插入就可以了。**

> **这里尤其需要注意的一个点是：我们增加操作如果链表为空时需要改变头节点（phead）,因为phead是一级指针，所以我们传参需要二级指针。**

*Test.c*

![在这里插入图片描述][f40c44057b10448fa39fae3116b59b1a.png]

*SList.h*  
![在这里插入图片描述][d853e6fed48348eaa81c72504772de20.png]

*SList.c*

![在这里插入图片描述][8dab8206e36644f8a822b45faf1c8a53.png]

### 四.头插 ###

> **因为头插必定会改变头节点所以同样需要使用二级指针。同时让插入的节点变为头节点。**

*Test.c*

![在这里插入图片描述][45f9fb2737484a9e96d675d2cf2e97c6.png]

*SLIst.h*

![在这里插入图片描述][6cd531e9be804815a7ccc04f2185b7c3.png]

*SList.c*

![在这里插入图片描述][0b6bcebdddf041d8823ee4d5ae2a8410.png]

## 五.头删尾删 ##

*SList.h*

![在这里插入图片描述][a256f84b030e4963892d571e3c467ebb.png]

*SList.c*

*尾删*  
![在这里插入图片描述][661623f4b7e74c65a06a1e0421f78838.png]

*头删*

![在这里插入图片描述][d6cd5b7d957c44adb2ac934565d59ed7.png]

## 六.打印链表 ##

*SList.h*

![在这里插入图片描述][5a9946c4bc194404b0fd5372addc4200.png]

*SList.c*

![在这里插入图片描述][f543002407804928bf9d39061f419887.png]

## 七.单链表查找,任意位置插入，任意位置删除 ##

*SList.h*

![在这里插入图片描述][83cebae1ad664a839443b2ec5648b4f4.png]

*SLiist.c*

*查找*

![在这里插入图片描述][66b3f1b38f7342a68177a8bd8b93893e.png]

*在pos位置前面插入*

![在这里插入图片描述][cf0d111315d74292b9a3ef0bcaee9987.png]

*将pos位置删除*

![在这里插入图片描述][3af05ebca19c444fbefe28f76cbaad33.png]

## 八.源代码 ##

*test.c*

#include"SList.h"
    
    void TestList()
    {
        
    	SListNode* phead = NULL;
    	
    	//测试部分
    
    }
    
    int main()
    {
        
    	TestList();
    	return 0;
    }

*SList.h*

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    #define SLTDataType int
    
    
    typedef struct {
        
    	SLTDataType data;//这里将int类型替换成链表类型以符合工程书写习惯
    	struct SListNode* next;
    }SListNode;
    
    
    void SLPushBack(SListNode** phead,SLTDataType x);//尾插
    
    void SLPushFront(SListNode** phead, SLTDataType x);//头插
    
    void SLPopBack(SListNode** phead);//尾删
    
    void SLPopFront(SListNode** phead);//头删
    
    void SLPrint(SListNode* phead);//打印
    
    //查找
    SListNode* SListFind(SListNode* phead, SLTDataType x);
    void SListInsert(SListNode**pphead,SListNode* pos, SLTDataType x);//在pos位置前位置插入(注意pos是节点的指针)
    void SListErase(SListNode**pphead,SListNode* pos);//删除pos位置

*SList.c*

#include"SList.h"
    
    
    void SLPushBack(SListNode** pphead, SLTDataType x)//尾插
    {
        
        SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//开辟新节点来存放插入的数
    	if (newnode == NULL)//如果开辟失败则返回错误
    	{
        
    		perror("malloc fail");
    		return;
    	}
    
    	newnode->data = x;
    	newnode->next = NULL;//初始化新节点
    
    	if (*pphead == NULL)//注意*pphead就是phead
    	{
        
    		*pphead = newnode;
    	}//如果链表里没有数直接插入数
    	else
    	{
        
    		SListNode* tail = *pphead;
    		while (tail->next != NULL)
    		{
        
    			tail = tail->next;
    		}//找到原链表尾部
    
    		tail->next = newnode;//插入新节点
    	}
    	
    }
    
    void SLPushFront(SListNode** pphead, SLTDataType x)//头插
    {
        
    	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//开辟一个新节点
    	if (newnode == NULL)//判断是否开辟成功
    	{
        
    		perror("malloc fail");
    	}
    	
    	newnode->data = x;
    	newnode->next = *pphead;//让新的节点指向原本的头节点
    	*pphead = newnode;//让新节点成为头节点
    }
    
    
    void SLPopBack(SListNode** pphead)//尾删
    {
        
    	assert(*pphead!=NULL);//断言链表不能为空
    
    	//找尾
    	if ((*pphead)->next == NULL)//如果链表只有一个数
    	{
        
    		free(*pphead);//直接释放头节点
    		*pphead = NULL;
    	}
    	else
    	{
        
    		SListNode* tail = *pphead;
    		SListNode* prev = NULL;
    		while (tail->next != NULL)
    		{
        
    			prev = tail;
    			tail = tail->next;
    		}
    		free(tail);//直接删掉tail节点
    		tail = NULL;
    
    		prev->next = NULL;
    	}
    
    
    }
    
    
    void SLPopFront(SListNode** pphead)//头删
    {
        
    	assert(*pphead != NULL);//链表不能为空
    
    	SListNode* first = *pphead;
    	*pphead = first->next;//直接让头节点变为第二个数
    	free(first);
    	first = NULL;
    }
    
    
    void SLPrint(SListNode* phead)//打印
    {
        
    	SListNode* start = phead;
    	while (start != NULL)
    	{
        
    		printf("%d ", start->data);
    		start = start->next;
    	}
    	printf("NULL");
    }
    
    SListNode* SListFind(SListNode* phead, SLTDataType x)//查找
    {
        
    	SListNode* cur = phead;
    	while (cur->data != x&&cur!=NULL)
    	{
        
    		cur = cur->next;
    	}
    	return cur;
    }
    
    void SListInsert(SListNode**pphead,SListNode* pos, SLTDataType x)//任意位置插入
    {
        
    	if (pos == *pphead)
    	{
        
    		SLPushFront(pphead,x);//头插
    	}
    	else
    	{
        
    		SListNode* pre = *pphead;
    		while (pre->next != pos)//找到pos前面的位置
    		{
        
    			pre = pre->next;
    		}
    		SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//开辟新节点
    		newnode->data = x;
    		newnode->next = pos;//初始化新节点
    		pre->next = newnode;//将pos前一个位置连接到新节点上
    	}
    }
    
    
    void SListErase(SListNode** pphead, SListNode* pos)//任意位置删除
    {
        
    	if (pos == *pphead)
    	{
        
    		SLPopFront(pphead);//头删 
    	}
    	else
    	{
        
    		SListNode* pre = *pphead;
    		while (pre->next != pos)//找到pos前面的位置
    		{
        
    			pre = pre->next;
    		}
    		pre->next = pos->next;//删除
    		free(pos);
    	}
    }

![在这里插入图片描述][7f76dc9373f440f08e54e86cac9e342e.png]

[9185c03c2da240c085869433068ad075.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6abb1a7aaa464358aeaaba10303e0e53.png
[1b2e182d58174abdb0ef58777e4acc72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4f5b0cfb0de44170aa76e9fb8b66e1c6.png
[93cc5e1217004e8f8ba6781345f1421d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/920cd77500664df188626b4cdf863956.png
[343f6c0eae274c5686ceb2b2c9b9f1ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ecf1ada899d545bf9b2720144ffc2fd0.png
[dc9169f6672944bbb5ba1329ed73e41d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f147672966d844fe91cc49655501a626.png
[f40c44057b10448fa39fae3116b59b1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/729801b52f624146904cbf588119d1af.png
[d853e6fed48348eaa81c72504772de20.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7b0f484b752344bda3c0fc77cb2e06a6.png
[8dab8206e36644f8a822b45faf1c8a53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/da82e38a59904ababd634f56ff4b0caf.png
[45f9fb2737484a9e96d675d2cf2e97c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/268132a8ef9e4a17936859fa513fe8d9.png
[6cd531e9be804815a7ccc04f2185b7c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/bc0c117a1f8f4a73990e5ba4ae236276.png
[0b6bcebdddf041d8823ee4d5ae2a8410.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/9d2c8a5f90b64d68bf719ac647eae5e9.png
[a256f84b030e4963892d571e3c467ebb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ffea011a43ee4670b223d400001a123a.png
[661623f4b7e74c65a06a1e0421f78838.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fe4ed1a5241942d8b29fe9f2e48f6a0f.png
[d6cd5b7d957c44adb2ac934565d59ed7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/93343de6da5e49b687429521ab8c71e6.png
[5a9946c4bc194404b0fd5372addc4200.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/17136066cd4141cb90a4fc415fe9d669.png
[f543002407804928bf9d39061f419887.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/212e7a0bc356419bb9fb16a44c276d75.png
[83cebae1ad664a839443b2ec5648b4f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ae4f159a754d488b8d221617c38c0437.png
[66b3f1b38f7342a68177a8bd8b93893e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/86e0a2e49bfb44f68427631f06949104.png
[cf0d111315d74292b9a3ef0bcaee9987.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6e9d8a74a8744222990dd15908f0217f.png
[3af05ebca19c444fbefe28f76cbaad33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4b6fb398810e4054b226c807253c1d30.png
[7f76dc9373f440f08e54e86cac9e342e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7d1dcc3d241a4278bb224ecb3ac7e466.png