有趣的地方

有趣的地方

【数据结构】单链表

文章目录


前言

在笔者之前的文章中提到过顺序表,但是顺序表存在许多缺陷,比如说在中间或头部插入低下(要进行循环,将后面元素后移),一旦增容会降低运行效率、增容造成空间浪费等,因此,链表应运而生,可以刚好填补上上述三个缺点。

链表的概念和结构

在笔者之前的文章中提到过顺序表,但是顺序表存在许多缺陷,比如说在中间或头部插入低下(要进行循环,将后面元素后移),一旦增容会降低运行效率、增容造成空间浪费等,因此,链表应运而生

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

链表也是线性表的一种,线性表在物理结构上 不一定 是线性的,但在逻辑结构上 一定 是线性的

链表在物理结构上 不是 线性的
在这里插入图片描述

链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其他车厢,每节车厢都是独立存在的。

车相是独立存在的,且每节车厢都有车门,假设每节车厢的车门都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带一把钥匙的情况下如何从车头走到车尾?最简单的做法:每节车厢里都放一把下一节车厢的钥匙。

那么,在链表中车厢是什么样的呢?
在这里插入图片描述
与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为“结点/节点”(一个意思),链表就是由一个一个节点组成的

节点的组成主要有两个部分:当前节点要保存的数据和保存下一个节点的地址(指针变量)。

图中指针变量 plist保存的是第一个节点的地址,我们称plist此时“指向”第一个节点,
如果我们希望plist“指向”第二个节点时,只需要修改plist保存的内容为0x0012FFA0。

下面这是一个基本的链表结构

struct SListNode
{
	int data;
	struct SListNode* next;//指向下一个节点的指针
};

用C语言实现单链表

接下来我们以方法的实现来对链表进行更加深入的了解
注意看代码里的注释
我们先创建如下一个头文件和两个源文件
在这里插入图片描述
我们在头文件 "List.h" 中写入如下代码

#pragma once
#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义节点的结构
//数据+指向下一个节点的指针
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;//存储的数据
	struct SListNode* next;//指向下一个节点的指针
}SLTNode;//重命名简化为SLTNOde

接下来我们在测试文件 ”test.c“ 创建如下几个变量,使其存储数字,和下一个节点的地址

在这里插入图片描述

#include"List.h"

void SListTest01()
{
	//链表是由一个一个的节点组成的
	//创建几个节点
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将4个节点联系起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

}

int main()
{
	SListTest01();
	return 0;
}

了解链表运行 - 以链表的打印为例

为了使我们理解这里的链表运用,我们自定义一个打印的功能。

#include"List.h"

void SLTprint(SLTNode* phead)//传入头节点地址
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

打印如下
在这里插入图片描述

这个的本质就是没打印出当前节点的内容后,就将这个指针 pcur 变成下一个节点的地址,方便打印下一个节点的内容,还是比较好理解的。
这与数组的区别就是,链表使没有索引的,没法像数组一样一个一个往下打印,而是需要不断获得下一个节点的指针

实现链表数据改变 - 以尾插为例

在知晓了链表的基本运行方式后,我们着手尾插方式的实现,基本原理就是找到尾巴,然后把新创建的节点接上

但是很快我们会遇到第一个问题就是如果这个链表为空,直接去寻找链表的尾巴,必然要对空指针进行解引用,这就会直接导致报错,所以我们必须进行分类,于是就写出了如下代码

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = SLTBuyNode(x);

	//空链表和非空链表
	if (phead == NULL)//如果对空链表找尾巴,会解引用空指针导致报错
	{
		phead = newnode;
	}
	else
	{
		//找尾巴
		SLTNode* ptail = phead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail此时指向的是尾节点
		ptail->next = newnode;
	}
}

可是我们一运行,发现上面都没有改变,于是我们通过调试知道,这里我们只改变了形参,那么想要改变链表的各个节点我们就需要运用二级指针,使链表的值也能跟着改变,这也是为什么打印只需值,但改变数据需要地址

如果大家对这种二级指针的概念还不是很熟悉,欢迎看看笔者C语言专栏里的指针详解 link

//尾插
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);//给上一个非0的退出码表示错误
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//防止节点传空
	SLTNode* newnode = SLTBuyNode(x);
	

	//空链表和非空链表
	if (*pphead == NULL)//如果对空链表找尾巴,会解引用空指针导致报错
	{
		*pphead = newnode;
	}
	else
	{
		//找尾巴
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail此时指向的是尾节点
		ptail->next = newnode;
	}
}

其他还有一些代码的实现,大差不大,笔者将部分可能会用到的代码放在下面了,有需要的小伙伴自己看看哈

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;//重新确定链表的开头
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//不能传空,链表也不能为空

	//链表只有一个节点
	if ((*pphead)->next == NULL)//-> 的优先级高于 *
	{
		free(*pphead);
		*pphead = NULL;
	}
	//链表有多个节点
	else 
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
	
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	//养成好习惯,创建临时变量来遍历
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//pos不用传地址的原因是我们只需要获得它内部下一个节点的地址,即next就行了,不需要获得这个节点的地址
{
	assert(pphead && *pphead);
	SLTNode* newnode = SLTBuyNode(x);
	SLTNode* prev = *pphead;

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = newnode;
		newnode->next = pos;

	}
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);
	
	newnode->next = pos->next;
	pos->next = newnode;
}

//删除指定节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//删除指定节点的后一个节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

//销毁链表
void SLTDestory(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

发表评论:

Powered By Z-BlogPHP 1.7.3

© 2018-2020 有趣的地方 粤ICP备18140861号-1 网站地图