链表(一) 单链表操作详解

川长思鸟来 2024-03-22 22:21 94阅读 0赞

#### 文章目录 ####

*  一、什么是链表
 *  二、链表的分类
 *   *  1、单向或者双向
     *  2、带头或不带头
     *  3、循环或不循环
 *  三、无头单向不循环链表的实现
 *   *  SList.h
     *  SList.c
     *   *  动态申请一个节点
         *  单链表打印
         *  单链表尾插
         *  单链表头插
         *  单链表的尾删
         *  单链表头删
         *  单链表查找
         *  在pos位置前插入
         *  单链表在pos位置之后插入x
         *  删除pos位置
         *  单链表删除pos位置之后的值

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

## 一、什么是链表 ##

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

逻辑结构：  
![在这里插入图片描述][346e4c1a6b4c40c7906352ac19e721ed.png]  
物理结构：

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

*  链式结构在逻辑上是连续的，但在物理上不一定连续
 *  节点是从堆上申请的空间，按策略分配的，可能连续也可能不连续

## 二、链表的分类 ##

按照单双链表，是否有头，是否循环，可以将链表分为八种

### 1、单向或者双向 ###

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

### 2、带头或不带头 ###

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

### 3、循环或不循环 ###

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

## 三、无头单向不循环链表的实现 ##

代码结构设计：

*  **SList.h:** 存放链表结构及需要用到的头文件，函数声明等
 *  **SList.c:** 各种操作函数的具体实现

### SList.h ###

#pragma once
    #include <stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    typedef int SLTDateType;
    typedef struct SListNode
    {
        
    	SLTDateType data;
    	struct SListNode* next;
    }SListNode;
    
    // 动态申请一个节点
    SListNode* BuySListNode(SLTDateType x);
    // 单链表打印
    void SListPrint(SListNode* plist);
    // 单链表尾插
    void SListPushBack(SListNode** pplist, SLTDateType x);
    // 单链表的头插
    void SListPushFront(SListNode** pplist, SLTDateType x);
    // 单链表的尾删
    void SListPopBack(SListNode** pplist);
    // 单链表头删
    void SListPopFront(SListNode** pplist);
    // 单链表查找
    SListNode* SListFind(SListNode* plist, SLTDateType x);
    // 单链表在pos位置之后插入x
    void SListInsertAfter(SListNode* pos, SLTDateType x);
    // 单链表删除pos位置之后的值
    void SListEraseAfter(SListNode* pos);

### SList.c ###

#include "SList.h"

#### 动态申请一个节点 ####

SListNode* BuySListNode(SLTDateType x)
    {
        
    	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    	if (newNode == NULL)
    	{
        
    		perror("malloc fail");
    		exit(-1);
    	}
    	newNode->data = x;
    	newNode->next = NULL;
    
    	return newNode;
    }

#### 单链表打印 ####

void SListPrint(SListNode* plist)
    {
        
    	SListNode* cur = plist;
    	while (cur != NULL)
    	{
        
    		printf("%d->", cur->data);
    		cur = cur->next;
    	}
    	printf("NULL\n");
    }

#### 单链表尾插 ####

void SListPushBack(SListNode** pplist, SLTDateType x)
    {
        
    	//pplist不能为空
    	assert(pplist);
    	//创建要插入的节点
    	SListNode* newNode = BuySListNode(x);
    	//链表没有节点时
    	if (*pplist == NULL)
    	{
        
    		*pplist = newNode;
    	}
    	//链表有节点时
    	else
    	{
        
    		SListNode* cur = *pplist;
    		//找到链表的最后一个节点
    		while (cur->next != NULL)
    		{
        
    			cur = cur->next;
    		}
    		cur->next = newNode;
    	}
    }

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

#### 单链表头插 ####

void SListPushFront(SListNode** pplist, SLTDateType x)
    {
        
    	//pplist不能为空
    	assert(pplist);
    	SListNode* newNode = BuySListNode(x);
    	newNode->next = *pplist;
    	*pplist = newNode;
    }

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

#### 单链表的尾删 ####

void SListPopBack(SListNode** pplist)
    {
        
    	assert(pplist);
    	//检查链表是否为空
    	assert(*pplist);
    
    	//链表只有一个节点
    	if ((*pplist)->next == NULL)
    	{
        
    		free(*pplist);
    		*pplist = NULL;
    	}
    	else
    	{
        
    		SListNode* cur = *pplist;
    		//找到倒数第二个节点
    		while (cur->next->next != NULL)
    		{
        
    			cur = cur->next;
    		}
    		free(cur->next);
    		cur->next = NULL;
    	}
    }

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

#### 单链表头删 ####

void SListPopFront(SListNode** pplist)
    {
        
    	assert(pplist);
    	//检查链表是否为空
    	assert(*pplist);
    
    	SListNode* cur = *pplist;
    	*pplist = cur->next;
    	free(cur);
    }

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

#### 单链表查找 ####

SListNode* SListFind(SListNode* plist, SLTDateType x)
    {
        
    	SListNode* cur = plist;
    
    	while (cur != NULL)
    	{
        
    		if (cur->data == x)
    		{
        
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return cur;
    }

#### 在pos位置前插入 ####

void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
    {
        
    	assert(pplist);
    	assert(pos);
    
    	if (pos == *pplist)
    	{
        
    		//在第一个节点前插入即头插
    		SLTPushFront(pplist, x);
    	}
    	else
    	{
        
    		SListNode* prev = *pplist;
    		while (prev->next != pos)
    		{
        
    			prev = prev->next;
    		}
    
    		SListNode* newnode = BuySListNode(x);
    		prev->next = newnode;
    		newnode->next = pos;
    	}
    }
    }

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

#### 单链表在pos位置之后插入x ####

void SListInsertAfter(SListNode* pos, SLTDateType x)
    {
        
    	assert(pos);
    
    	SListNode* newNode = BuySListNode(x);
    	newNode->next = pos->next;
    	pos->next = newNode;
    }

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

#### 删除pos位置 ####

void SLTErase(SListNode** pplist, SListNode* pos)
    {
        
    	assert(pplist);
    	assert(pos);
    
    	if (pos == *pplist)
    	{
        
    		//删除第一个节点即头删
    		SLTPopFront(pplist);
    	}
    	else
    	{
        
    		SListNode* prev = *pplist;
    		while (prev->next != pos)
    		{
        
    			prev = prev->next;
    		}
    
    		prev->next = pos->next;
    		free(pos);
    	}
    }

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

#### 单链表删除pos位置之后的值 ####

void SListEraseAfter(SListNode* pos)
    {
        
    	assert(pos);
    	assert(pos->next);
    	
    	SListNode* cur = pos->next->next;
    	free(pos->next);
    	pos->next = cur;
    }

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

[f96284886ccd4617b2f614312da78dea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a159283708224a7f8ce6d9a841f9a0e4.png
[346e4c1a6b4c40c7906352ac19e721ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/99ecaec30dba4a1e923efed47aba20f7.png
[a220e2354da24ed4afe4283651f003f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/864c95934a8949a8b7373baaf20be4f1.png
[c4de8818f5f045a986998ff0e8eb8c27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/659f4f40e400479c8e92f941f9558388.png
[fdb611e6225341bfb1ac5cf3f576c5b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/82f3c720440e4613aa490803d3445ec3.png
[e3d3fa12b57d4971a08db9fea44bee77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/1bd22db285e640cd8eccef8cae3ac7a8.png
[4d3cbd1781fe426cbcfdae8e5b62beea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d70794c90eaa400987281710643987d6.png
[6407dfb73ff641048c31b7e71a93f8bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c774b61bd5554b349fcfffa6267fbfb5.png
[7381884ea2954ec4bedcdbd8619ff04c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/977140b5fd174bb785a0488fe9e3156c.png
[e1c60714dfe7407e9cae9d1045cccedb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7e0e3bbb97db4a38a5dae2ea8c1b9867.png
[981eeeea98dc445a906ee0d2631d4ae7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/add441c66e824ce49fe28f8f733770a0.png
[04be89de52fa4c95bbccda850660986e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/845353e86cae451cacf2cc46076e2791.png
[8d7b33413a084ce2bc10cf219f8619b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d130bf0453fd49ab930529a8c0b0fec8.png
[469ed4881b154d518520910d29efe37c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/837b5998dfe04ecaa8d7aab20d78f208.png