开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构之单链表 -> 正文阅读

[数据结构与算法]数据结构之单链表

前言

上一章节,博主讲解完毕顺序表,并详细讲解了顺序表的各种增删查改方法.而这次我们需要讲解的是链表,而又主要讲解的是单链表

1. 为何需要链表?

问题: 为何需要链表?

在回答之前,我们回顾一下上一节我们怎样定义顺序表的结构的. 上一节的顺序表

逻辑结构: 线性 ; 物理结构 : 线性(即地址连续);
空间开辟是按照2的倍数开辟,顺序表中实际存储数量size小于等于线性表容量capacity

图示:

回顾完毕,大家有没有发现顺序表有一个致命的缺陷?? 对,那就是size数量常常小于等于capacity,导致空间浪费严重.

为了解决这个问题,我们的链表就诞生了,链表就是有一个内容就开辟一个空间.

这个时候有人会问,既然浪费严重,为何顺序表不一次只开辟一个空间? 嗯,问的好,但是反问,如果只开辟一个空间,物理结构连续吗?不连续.逻辑结构连续吗?不连续,因为连接不起来了. 后面会解释,请继续往下看

每次单独开辟的空间需要用某种方法把它们连接起来,而把它们连接起来也就是链表的功能

2. 清楚单链表结构

单链表类似于顺序表,也具有自己独立的 逻辑结构与物理结构,但是实际确有差别,请看下图解释:

顺序表:

单链表:

解释顺序表与单链表中的物理结构:

在顺序表中，我们回忆一下,空间是怎样开辟的?没错,直接一次性开辟一大块,当不够用时,再翻倍开辟.
- 请看之前写的顺序表空间开辟代码:
- 由于是利用realloc一次性动态调整出一大块空间,所以这一大块空间中的每个单元,地址都是连续的.

在单链表中,每一次都是用的malloc开辟的一个空间,那么每个空间的地址一定是不一样且不连续的,比如:

3. 定义单链表结构

在第2小节中大家看到,博主画链表时候是用的两个格子叠在一起表示链表的一个结点,那么为什么要这样呢? 博主现在就进行解释:

我们已经清楚的知道,链表结点与结点之间是必须要连接的,这样才符合链表的 逻辑结构,但是怎么进行连接呢? 答曰:指针

同时,链表是一种什么? 没错,是数据结构,那就是用来存储数据的,所以链表结点便进行了分层.

上层用于存储数据 ; 下层用于指向下一个结点,以达到连接目的,下面开始代码实现

代码实现

因为我们是自己在实现单链表,也就是相当于做一个小项目,那必然缺不了 头文件,源文件,测试文件,我们仍然按照顺序表文章风格叙述.

首先分别建立SList.h , SList.c , test.c文件,s的意思是single,单个,SList就是单链表(博主使用的编译器是VS2019)
如图:

还记得头文件是写什么的吗? 没错,写函数声明,结构定义,头文件引用和定义弘等

在SList.h中实现链表结点,需要存储的数据类型以int为例:

struct SListNode
{
    int data;
    struct SListNode* next;     
};

大家想一想,这样写会不会有什么麻烦? 没错,那就是如果我们以后不想存储int型后,就需要在后面的成千上万代码中一一修改,怎么解决呢? 按照上一节顺序表的思路,我们想到了typedef

修改后如下:

typedef int SLTDataType; //方便以后修改数据类型

struct SListNode
{
    SLTDatType data;
    struct SListNode* next;     
}SLTNode; //把结构体名改短一点

4.单链表的增删改查

4.1 单链表之尾插

我们学数据结构一定要养成一个好习惯,那就善于画图,这样才能理清逻辑,单链表也是这样,我们看看它的结构是什么样子 ?

即phead指向头结点(第一个结点),之后的每个结点的next指向下一个结点,其中尾结点的next为空.

所以我们想要实现尾插,步骤是什么??

第一步: 找到最后一个结点(即其next为空)
第二步: 开辟一个空间出来(使用malloc),存储数据,然后把新开辟的空间的next置为空.
第三步: 使用尾结点的next连接新开辟的空间

代码实现:

在SList.h中写尾插声明

//既然我们知道phead是指针,所以参数设置一定需要接收指针,同时还需要接收需要插入的元素
//而phead是一个结构体(链表结点)指针,所以设计如下.
void SListPushBack(SLTNode* phead,SLTDataType elem);

在SList.c中写函数定义

void SListPushBack(SLTNode* phead,SLTDataType elem)
{
    //第一步:找尾结点,  即cur->next 等于 NULL
    SLTNode* cur = phead;
    while(cur->next != NULL)
    {
        cur = cur->next;
    }
    
    //第二步:开辟新空间
    SLTNode* newnode = (SLTNode* )malloc(sizeof(SLTNode));//记得引头文件
    if(newnode == NULL)
    {
    	perror("错误原因:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->next = NULL;
    //第三步:连接
    cur->next = newnode;
}

大家看看,这样写完后看着是不是很憋屈? 憋屈的啥? 没错,那个开辟空间部分的代码,我们在以后的任何插入操作部分,都需要用到他.

所以,既然他这么频繁,我们为何不干脆把它搞成一个函数呢?

4.1.1 单链表之开辟空间

在SList.h文件中声明

SLTNode* ButSLTNode(SLTDatType elem);

在SList.c中写定义

SLTNode* ButSLTNode(SLTDatType elem)
{
	SLTNode* newnode = (SLTNode* )malloc(sizeof(SLTNode));//记得引头文件
    if(newnode == NULL)
    {
    	perror("错误原因:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->next = NULL;    
    return newnode;
}

修改后的尾插

void SListPushBack(SLTNode* phead,SLTDataType elem)
{

    //第一步:找尾结点,  即cur->next 等于 NULL
    SLTNode* cur = phead;
    while(cur->next != NULL) //cur用于迭代
    {
        cur = cur->next;
    }
    //第二步:开辟新空间
    SLTNode* newnode = BuySLTNode(elem);
    //第三步:连接
    cur->next = newnode;
}

写完以后,我们需要将进行测试了.就是尾插几个值进去,然后打印出来

既然需要打印,我们干脆把打印操作也进行实现吧,现在再看看这个图:

要打印所有的值,肯定需要一个循环,并且结束条件是该结点的next等于NULL

4.1.2 单链表之打印值

在SList.h文件中声明

void SListPrint(SLTNode* phead);

在SList.c文件中定义

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

测试单链表尾插

结果:

发现报错,怎么回事呢? 提示我们phead此时是一个空指针.

我们想想,什么时候,phead会是空指针?没错,链表为空的时候.

所以这段代码还需要修改一下下.就是特判一下链表为空

修改如下:

void SListPushBack(SLTNode* phead, SLTDataType elem)
{
	if (phead == NULL)
	{
		phead = BuySLTNode(elem);
	}
	else
	{
		//第一步:找尾结点,  即cur->next 等于 NULL
		SLTNode* cur = phead;
		while (cur->next != NULL) //cur用于迭代
		{
			cur = cur->next;
		}
		//第二步:开辟新空间
		SLTNode* newnode = BuySLTNode(elem);
		//第三步:连接
		cur->next = newnode;
	}
}

再次测试:

…艹,又出问题了. 怎么回事呢 ?, 竟然没有成功尾插进去值吗?

在仔细分析一波我们的代码,好像明白了为什么没有成功输入值.原来是我们的参数设置有问题.

还记得函数传参的值传递 与 址传递吗? plist的类型为SLTNode*,而我们形参类型也是SLTNode*,这属于值传递

值传递相当于形参是实参的一份临时拷贝,形参的改变并不会影响实参的值

怎么修改这个问题呢?没错,那就是用址传递,我们传plist的地址.形参用二级指针,修改如下:

void SListPushBack(SLTNode** pphead, SLTDataType elem)
{
	assert(pphead); //pphead不可以为空指针.
	if (*pphead == NULL)
	{
		*pphead = BuySLTNode(elem);
	}
	else
	{
		//第一步:找尾结点,  即cur->next 等于 NULL
		SLTNode* cur = *pphead;
		while (cur->next != NULL) //cur用于迭代
		{
			cur = cur->next;
		}
		//第二步:开辟新空间
		SLTNode* newnode = BuySLTNode(elem);
		//第三步:连接
		cur->next = newnode;
	}
}

测试:

成功!!!

总结: 涉及到需要修改的操作,我们最好用址传递

4.2单链表之头插

还是老规矩,写数据结构之前我们需要画图.既然是头插,那我们的步骤应该是什么?如图:

第一步: 创建新节点并存储数据
第二步: 让新节点连接原来的第一个结点
第三步: 让phead连接新节点

开始实现代码:

在SList.h文件中声明

//还记得上面的总结吗?这函数需要改变phead的值,所以我们的形参需要二级指针
void SListPushFront(SLTNode** pphead,SLTDataType elem);

在SList.c文件中定义

void SListPushFront(SLTNode** pphead,SLTDataType elem)
{
    assert(pphead);
    //第一步,创建
    SLTNode* newnode = BuySLTNode(elem);
    //第二步,新结点连接原来第一个结点
    newnode->next = *pphead;
    //第三步,phead指针指向新节点
    *pphead = newnode;
}

测试:

成功!!!

4.3单链表之尾删

还是老规矩,先画图,请看下面:

第一步: 找到倒数第二个结点
第二步: 释放最后一个结点
第三步: 将找的结点的next进行释放

代码实现:

在SList.h中声明

//由于涉及到修改,所以我们需要址传递,也就是形参需要变成二级指针
void SListPopBack(SLTNode** pphead);

在SList.c中定义

void SListPopBack(SLTNode** pphead)
{
	//第一步,找倒数第二个结点
	SLTNode* cur = *pphead;
	while (cur->next->next != NULL) //下一个结点(cur->next)的next等于NULL时候  就是尾巴
	{
		cur = cur->next;
	}
	//第二步,释放尾巴
	free(cur->next);
	//第三步,将现结点变NULL
	cur->next = NULL;
}

测试:

成功!!! 成功才怪让博主皮一下.

大家再执行想想,这样真的就执行完了吗? 其实没有, 比如链表只有一个数据时候和没有数据时候,如图:

执行!

会发现出问题了,所以我们需要改进,给它加个特判:

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead);  //如果没有结点,提示无法删除
    
    if((*pphead)->next == NULL)//如果只有一个结点
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }
    
	//第一步,找倒数第二个结点
	SLTNode* cur = *pphead;
	while (cur->next->next != NULL) //下一个结点(cur->next)的next等于NULL时候  就是尾巴
	{
		cur = cur->next;
	}
	//第二步,释放尾巴
	free(cur->next);
	//第三步,将现结点变NULL
	cur->next = NULL;
}

测试:

成功!!!,这才是真的成功

4.4 单链表之头删

老规矩,先画图,再讲解:

第一步,我们先把第二个结点的地址记下来
第二步, 释放第一个结点
第三步,将phead链接到原来的第二个结点

写代码:

在SList.h中写是声明

//还是同理,因为涉及修改,所以需要址传递
void SListPopFront(SLTNode** pphead);

在SList.c中写定义

还记得上面的尾删吗?我们考虑了3种情况:空链表,只有一个空间链表,多个结点链表

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	//0结点
	assert(*pphead);
	//1结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多结点
	//第一步,保留第二个结点地址
	SLTNode* next = (*pphead)->next;
	//第二步,释放第一个结点
	free(*pphead);
	//第三步,连接第二个
	*pphead = next;
}

成功!!!

其实上面的代码还可以优化些~~~,就是只有一个结点的代码可以删除,大家下来画图想想

4.5单链表之查链表长度

这个实在过于简单,博主就不画图了,直接码代码

在SList.h中写声明

//这个函数的功能只是求长度,并没有修改,所以 值传递
int SListSize(SLTNode* phead);

在SList.c中写定义

int SListSize(SLTNode* phead)
{
    SLTNode* cur = phead;
    int size = 0;
    while(cur->next != NULL)
    {
        size++;
        cur = cur->next;
    };
    return size;
}

测试

成功!!

4.6单链表之判断链表是否为空

过于简单,直接上代码

在SList.h中写声明

bool SListEmpty(SLTNode* phead);  //注意哦~,C语言里面没有布尔值,写bool需要引入<stdbool.h>

在SList.c中写定义

bool SListEmpty(SLTNode* phead)
{
	return phead == NULL;
}

测试:

成功!!

4.7单链表之查找某一个值

这里博主要解释下,很多书籍上写这个函数时,返回值是一个索引,代表在哪个位置,博主不建议这样写.为什么呢? 大家继续往后阅读就会明白,博主是要搭配任意位置插入和任意位置删除函数一起使用

在SList.h中写声明

// 博主对于这个函数的要求是,如果可以找到,就返回那个结点,如果找不到,返回空指针
SLTNode* SListFind(SLTNode* phead, SLTDataType elem);

在SList.c中写定义

SLTNode* SListFind(SLTNode* phead, SLTDataType elem)
{
    SLTNode* cur = phead;
    while(cur->data != elem)
    {
        cur = cur->next;
    }
    if(cur->data==elem)
    {
        return cur;
    }
    return NULL;
}

测试

4.8单链表之任意位置删除

还记得博主开始设计查找值函数时候吗,它的返回值是什么?没错就是如果找到就返回结点,否则返回NULL

而现在我们就需要用它的返回值,也就是说,我们这个函数设置的形参之一就是目标结点.

老规矩,先画图:

第一步: 就是找到目标结点之前位置
第二步: 就是保存目标结点后位置
第三步:就是销毁目标空间
第四步,连接

在SList.h中声明:

//由于需要修改,所以 址传递,pos是目标结点地址.
void SListErase(SLTNode** pphead,SLTNode* pos);

在SList.c中定义

void SListErase(SLTNode** pphead,SLTNode* pos)
{
    assert(pphead);
    //0结点情况
    assert(*pphead);
    //一个结点情况.也就是只删除一个,其实就相当于头删,所以直接调用头删.
    if((*pphead)->next == NULL)
    {
        SListPopFront(pphead);
    }
    else
    {
        SLTNode* cur = *pphead;
        while(cur->next != pos)
        {
            cur = cur->next;
        }
        SLTNode* two_next = pos->next;
        free(pos);
        cur->next = two_next;
    }
}

测试

成功!!

4.9单链表之任意位置插入

老规矩,先画图

第一步,先找目标结点之前结点
第二步,新建结点保存数据
第三步,新结点连接目标结点
第四步,当前结点连接新结点

在SList.h中声明

void SListInsert(SLTNode** pphead,SLTNode* pos,SLTDataType* elem);

在SList.h中定义

void SListInsert(SLTNode** pphead,SLTNode* pos,SLTDataType elem)
{
	assert(pphead);
	assert(pos);
	if (*pphead== pos)
	{
		SListPushFront(pphead,elem);
	}
	else
	{
		SLTNode* pre = *pphead;
		while (pre->next  != pos)
		{
			pre = pre->next;
		}
		SLTNode* next = BuySLTNode(elem);
		next->next = pos;
		pre->next = next;
	}
}

测试

成功

综合:

SList.h文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


//只是读则只需要一级指针
void SListPrint(SLTNode* Phead);
int SListSize(SLTNode* phead);
SLTNode* SListFind(SLTNode* phead, SLTDataType elem);
bool SListEmpty(SLTNode* phead);
SLTNode* BuySLTNode(SLTDataType elem);


//设计读写和修改就要二级指针
void SListPushBack(SLTNode** phead,SLTDataType elem);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
void SListInsert(SLTNode** pphead, SLTNode* pos,SLTDataType elem);
void SListErease(SLTNode** pphead, SLTNode* pos);

SList.c文件

#include "SList.h"

void SListPrint(SLTNode* phead)
{
	SLTNode* CUR = phead;
	while (CUR != NULL)
	{
		printf("%d-->", CUR->data);
		CUR = CUR->next;
	}
	printf("NULL\n");
}

SLTNode* BuySLTNode(SLTDataType elem)
{
	SLTNode* ptail =  (SLTNode*)malloc(sizeof(SLTNode));
	if (ptail == NULL)
	{
		perror("错误原因:");
		exit(-1);
	}
	ptail->data = elem;
	ptail->next = NULL;
	return ptail;
}


void SListPushBack(SLTNode** pphead, SLTDataType elem)
{
	assert(pphead); //pphead不可以为空指针.
	if (*pphead == NULL)
	{
		*pphead = BuySLTNode(elem);
	}
	else
	{
		//第一步:找尾结点,  即cur->next 等于 NULL
		SLTNode* cur = *pphead;
		while (cur->next != NULL) //cur用于迭代
		{
			cur = cur->next;
		}
		//第二步:开辟新空间
		SLTNode* newnode = BuySLTNode(elem);
		//第三步:连接
		cur->next = newnode;
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType elem)
{
	assert(pphead);
	//第一步,创建
	SLTNode* newnode = BuySLTNode(elem);
	//第二步,新结点连接原来第一个结点
	newnode->next = *pphead;
	//第三步,phead指针指向新节点
	*pphead = newnode;
}

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);  //如果没有结点,提示无法删除

	if ((*pphead)->next == NULL)//如果只有一个结点
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//第一步,找倒数第二个结点
	SLTNode* cur = *pphead;
	while (cur->next->next != NULL) //下一个结点(cur->next)的next等于NULL时候  就是尾巴
	{
		cur = cur->next;
	}
	//第二步,释放尾巴
	free(cur->next);
	//第三步,将现结点变NULL
	cur->next = NULL;
}

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	//0结点
	assert(*pphead);
	//1结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}

	//多结点
	//第一步,保留第二个结点地址
	SLTNode* next = (*pphead)->next;
	//第二步,释放第一个结点
	free(*pphead);
	//第三步,连接第二个
	*pphead = next;
}

a
int SListSize(SLTNode* phead)
{
	SLTNode* CUR = phead;
	int size = 0;
	while (CUR)
	{
		size++;
		CUR = CUR->next;
	}
	return size;
}

bool SListEmpty(SLTNode* phead)
{
	return phead == NULL;
}

SLTNode* SListFind(SLTNode* phead, SLTDataType elem)
{
	SLTNode* cur = phead;
	while (cur->data != elem)
	{
		cur = cur->next;
	}
	if (cur->data == elem)
	{
		return cur;
	}
	return NULL;
}



void SListInsert(SLTNode** pphead,SLTNode* pos,SLTDataType elem)
{
	assert(pphead);
	assert(pos);
	if (*pphead== pos)
	{
		SListPushFront(pphead,elem);
	}
	else
	{
		SLTNode* pre = *pphead;
		while (pre->next  != pos)
		{
			pre = pre->next;
		}
		SLTNode* next = BuySLTNode(elem);
		next->next = pos;
		pre->next = next;
	}
}



void SListErease(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	//0结点情况
	assert(*pphead);
	//一个结点情况.也就是只删除一个,其实就相当于头删,所以直接调用头删.
	if ((*pphead)->next == NULL)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SLTNode* two_next = pos->next;
		free(pos);
		cur->next = two_next;
	}
}