数据结构之单链表

2024-03-13 13:20:03

文章目录

前言
1. 为何需要链表?
2. 清楚单链表结构
3. 定义单链表结构
- 代码实现
4.单链表的增删改查
综合:

前言

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

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;
	}
}

码农公寓

文章目录

前言

1. 为何需要链表?

2. 清楚单链表结构

3. 定义单链表结构

代码实现

4.单链表的增删改查

4.1 单链表之尾插

4.1.1 单链表之开辟空间

4.1.2 单链表之打印值

4.2单链表之头插

4.3单链表之尾删

4.4 单链表之头删

4.5单链表之查链表长度

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

4.7单链表之查找某一个值

4.8单链表之 任意位置删除

4.9单链表之 任意位置插入

综合:

相关文章

4.8单链表之任意位置删除

4.9单链表之任意位置插入