C语言链表讲解

发布于：2024-04-19 ⋅ 阅读:(22) ⋅ 点赞:(0)

链表的概念与结构 

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

 如图所示:

        链表通过指针域把一个一个节点链接起来,而最后一个节点的指针域指向NULL,表示到头了。

链表与顺序表的对比

链表是一种物理存储非连续，非顺序的存储结构

顺序表是一种物理存储连续，顺序的存储结构

 之前我们写过的通讯录,就是基于顺序表的实现的，而链表则不需要增容这个操作,需要节点时我们直接动态开辟一个通过指针域链接起来就可以了。

单链表的实现

创建一个工程,创建SList.c,Slist.h,test.c文件

函数的声明放到.h文件中,函数功能的定义放入SList.c文件中,test.c用来测试用的

创建链表

 这里我们测试用整形来测试,所以我们把SLDataType重定义为int,后面如果想要改变存储数据的类型时,方便修改。struct SListNode* next就是我们的指针域,用来存储下一个节点的地址。同时为了方便书写代码,我们把struct SListNode重定义为SListNode。

这里我们利用单链表实现以下功能:

  1. 在链表头部插入数据
  2. 在链表尾部插入数据
  3. 链表元素的打印
  4. 查找元素
  5. 在指定位置之前插入数据
  6. 在指定位置之后插入数据
  7. 删除指定位置之前的数据
  8. 删除指定位置之后的数据
  9. 销毁链表

在test.c中创建链表节点

 这里我们创建一个SLTNode* 的链表指针表示第一个节点,由于此时还没有值,我们先给它赋值为NULL。

头插与尾插

但是如何头插元素与尾插元素呢,函数的参数该怎么传呢？，由于我们此时plist为SLTNode*类型,所以此时我们如下设置函数

 先以头插为例子,如何头插呢?

在插入节点时,我们得 先创建一个节点,通过malloc创建一个节点之后,有两种情况  

  1. 链表还没有元素,此时为空
  2. 链表已有元素

第一种情况,我们创建完一个节点之后直接赋值给此时链表的第一个节点,也就时我们创建的phead

重点来分析第二种情况

 我们其实只需要把我们创建的那个节点的指针域指向此时的第一个节点(这里我称为头节点),然后把头节点指向的空间改为newhead不就相当于在链表头部插入数据了吗。

代码实现:

        首先先把需要的头文件在.h文件中引入

 同时,在SList.c文件中引入SList.h文件,再来写我们头插函数的定义

这里我们以pcur = pcur->next来遍历 链表

此时我们代码就写完了,由于此时还没有写打印函数,我们先来调试验证一下是否插入成功。

 此时我们看到,明明phead中已经成功放入数据,为什么plist调用完头插函数之后什么值都没有呢,我们分别取出两个的地址看看。

 可以看到此时phead和plist的地址不一样,这说明他们分别指向两块不一样的空间，这就说明了函数的形参只是实参的一份临时拷贝,改变形参实参不发生改变,如果想要实参改变,则应该传入的是plist的地址,那我此时我们的参数就应该使用SListNode** 这样的二级指针接受。

 此时我们把phead变为pphead，表示二级指针,同时添加assert.h库文件,断言pphead，不能为空,因为我们二级指针变量接受的是一级指针变量的地址,我们必须保证pphead接受的不是NULL,不然后面我们使用肯定会出问题的。

为了方便测试,我们把链表的打印写出来,链表的打印,就是遍历链表元素,不断打印它的data值,直到指向的为空之后就退出来

 此时我们运行之后,我们就把数据存入进去了。

 再来说尾插

尾插也分两种情况:

  1. 链表为空
  2. 链表不为空

第一种情况还是直接赋值就行了

第二种情况

 这种情况我们直接找到链表的最后一个节点,然后把他的next与newhead链接起来就可以了。

关键在于如何找到最后一个节点呢,前面的打印是验证pcur不等于空,而尾插我们不能使pcur==NULL，当pcur->next != NULL时我们继续查找,当pcur->next==NULL时,这时我们就找到了最后一个节点。此时把他的next指向newhead就可以了

代码实现:

这里发现无论头插还是尾插,我们都要创建一个新的节点,那我们直接封装一个创建节点函数吧,内容就是我们头插里面创建新节点的代码,我们直接把创建的节点返回就可以了。

由于头插也要使用,我们要把BuyNode写在前面 

 此时我们运行代码,测试尾插

 查找链表元素

 由于查找元素我们并不有需要修改链表,所以我们使用一级指针接受就可以了,找到了就返回这个节点,没找到返回NULL,所以我们只需要遍历整个链表就可以了。

代码实现:

此时我们运行

在指定位置之前插入元素

这里分为两种情况:

 首先我们如果想要在指定位置之前插入数据,那我们肯定要知道Pos这个想要插入数据的前面那个数据的地址,所以我们需要遍历判断Prev(记录前一个的地址)的next是否等于Pos,如果等于就退出,但是如果Pos等于我们的Phead(头一个节点)呢?,这样我们的Prev->next != Pos都执行不了,所以我们要单独执行这种情况

  1. 指定位置等于头节点
  2. 指定位置不等于头节点

代码实现:

由于这里我们需要处理Pos == phead这种情况,所以我们传二级指针,其实这种情况就是我们的头插,直接调用头插函数

 我们运行代码

 在指定位置之后插入元素

在指定位置之后插入数据就更简单了,由于每一个节点都是malloc出来的,所以节点实在堆区上存储的,所以我们甚至都不需要传入头节点,直接传入我们SListFind()找到的节点就可以了,只不过需要判断一下指定的位置不能为NULL,而之所以在指定位置之前需要传入二级指针接受头节点的地址,是因为有一个头插的情况,我们需要改变头节点的指向,而在指定位置之后插入则不需要,我们只需要保存下一个节点的地址,然后让newNode指向下一个节点的地址,然后把指定位置的下一个节点地址(pos->next)指向newNode就可以了。

这里我们无论在哪都是一样的操作

 代码实现:

此时我们运行

删除指定位置之前的元素

这里需要注意的是,我们不能删除第一个节点之前的位置,第一个节点之前都没有元素,所以我们还需要断言一下,pos != *pphead),同时pos也不能为空,但由于如果我们要删除第二个节点的前一个节点,那不就相当于把第一个节点删除了吗,那么第一个节点也需要改变指向,所以我们这次要传入二级指针。而且如果链表里面没有元素我们也不能删,所以还要要判断链表不为空

代码实现:

这里我们需要找到pos之前的那个节点,我们创建两个指针

prev: 指向删除节点的前一个位置

pcur: 指向想要删除的节点

 如上图,我们先把prev先赋值为NULL,每次循环的时候我们都让prev指向pcur的位置,然后pcur再指向下一个位置 ,直到为pos的前一个位置,这样我们就可以找到想要删除元素的前一个位置了,接下来只需要把prev的next指为pos就可以了,然后把pcur释放掉,同时置空。(因为是动态开辟的所以我们使用free)

 删除指定位置之后的元素

这个也简单,这里我们只需要知道pos->next->next(newnext)就可以了,把pos->next释放掉,同时pos->next指向下一个(newnext)就可以了,所以这里我们需要判断pos不能为空,同时pos->next也不能为空,如果pos->next是空,那不就相当于删除最后一个节点的下一个节点,NULL删他干嘛?

 

代码也比较简单:

 此时我们运行 

 销毁链表

 最后一步,我们的节点都是malloc出来的,所以最后都要free掉。怎么释放呢,其实按个遍历释放就可以了,但是我们要一个一个释放的 话,我们应该定义两个指针,一个指向要删除的节点,一个指向下一个节点,不然free点之后,我们是找不到下一个节点的。

 代码实现:

 注意: 这里要注意我标红的位置,我们的循环条件其实是prev,如果是pcur的话,当遍历到最后一个节点,此时pcur指向NULL了,就退出循环了,那么此时prev指向的最后一个节点没有被free掉,我们直接*pphead = NULL，就会造成内存泄露了,所以我们给pcur加一个条件,当他不是NULL的时候才指向下一个节点。这样就能保证每一个节点都被释放了

总代码

SList.c

#define _CRT_SECURE_NO_WARNINGS

#include "SList.h"


SLTNode* BuyNode(SLTDataType x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newNode == NULL)
	{
		perror("malloc fail!\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newNode = BuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newNode;
	}
	else
	{
		newNode->next = *pphead;
		*pphead = newNode;
	}
}
//链表的打印
void SListPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newNode = BuyNode(x);

	if (*pphead == NULL)
	{
		*pphead = newNode;
	}
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newNode;
	}
}

//查找链表元素
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
			return pcur;
		pcur = pcur->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SListInsertFront(SLTNode** pphead,SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	SLTNode* newNode = BuyNode(x);
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newNode->next = pos;
		prev->next = newNode;
	}

}

//在指定位置之后插入数据
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newNode = BuyNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

//删除指定位置之前的数据
void SListEarseFront(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead && pos && pos != *pphead);
	if (pos == (*pphead)->next)
	{
		free(*pphead);
		*pphead = pos;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* pcur = *pphead;

		while (pcur->next != pos)
		{
			prev = pcur;
			pcur = pcur->next;
		}
		prev->next = pos;
		free(pcur);
		pcur = NULL;
	}
}

//删除指定位置之后的数据
void SListEarseAfter(SLTNode* pos)
{
	assert(pos && pos->next != NULL);
	SLTNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}

//销毁链表
void SListDestory(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* pcur = (*pphead)->next;
		while (prev)
		{
			free(prev);
			prev = pcur;
			if (pcur)
				pcur = pcur->next;
		}
		*pphead = NULL;
	}
}

SList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//
//链表的打印
void SListPrint(SLTNode* phead);
//查找链表元素
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SListInsertFront(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除指定位置之前的数据
void SListEarseFront(SLTNode** pphead, SLTNode* pos);
//删除指定位置之后的数据
void SListEarseAfter(SLTNode* pos);
//销毁链表
void SListDestory(SLTNode** pphead);

链表的种类

 其实我们实现的只是链表的其中一种

链表可分为如下八种, 2*2*2,每一种都可以排列起来,我们演示的只是单向不带头不循环链表,

还有一种是双向循环带头链表,这两种比较常见,后期有时间我把双链表写出来

结言

本篇文章讲解了链表的基础功能,其实还有头删和尾删两个功能没有写出来,但在删除指定位置之前与后的功能里面中的特殊情况就是头删和尾删,兄弟们可以自己下去实现一下。

本篇文章到此就结束了,如果有什么问题欢迎在评论区留言~

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布