亲宝软件园·资讯

展开

C语言链表

平凡的人1 人气:1

前言

关于线性表的一些相关介绍,大家可以看看我们之前写的点我-链表

点我-顺序表,里面有一些相关的知识介绍,都是比较基础的,一些比较常见的操作里面也有具体的介绍与实现到,然后呢,今天我们学习的是链表,相比于之前的操作实现更加具有深度,对于一些比较简单的操作这里就不加说明了。而且涉及到之前未说到的一些知识,对此我们可以强化对其认识,这就是写这篇博客的目的。

编译工具:vs2019,小伙伴们可以一起跟着来敲敲代码。

开始之前:很有必要提醒大家注意二级指针的使用,为什么会用到二级指针,我的博客也有一些相关介绍,简单来说,传值参数并不改变实参,传址参数改变形参。

一、链表的介绍

1.什么是链表

简单来说,就是一条链子连接成的表,上面的链接也有比较正式规矩的介绍。

与顺序表相比,链表的最大特点就是不要求物理空间连续,插入不需要移动大量的数据

 怎么去联系各个结点呢?

从上图其实不难发现,搞个指针连接起来就行了。既要有数据域和指针域,注意一点:最后一个元素的指针域为NULL。上面的箭头实际并不存在,只是为了看起来比较直接,形象化起来。那要怎么去表示出来了?可以用结构体的自引用。

2.链表的分类

之前并没说到链表的类型有哪些,根据类型的不同,我们实际上可以对其进行分类,由于都是基于单链表实现操作,因此需要学好单链表,进行深化学习。

2.1.根据方向

单向/双向链表

2.2.头结点

带头结点/不带头结点

2.3.循环/非循环

 二、链表的实现

链表的实现当然离不开我们自己动手去敲代码了,这首先需要准备好我们的编译环境,vs2019,同时,每次写完一块模板,我们要去测试一下有没有bug,方便我们去找错误,进行调试,这样会大大减少我们的工作量。

1.结构体

链表我们该如何去表示呢?其实,通过上面的例子,我们大致已经知道,需要一个地方来存放数据,另一个地方存放下一个结点的地址。我们可以通过结构体来定义,具体代码如下:

#include <stdio.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

2.开辟结点

后续操作会频繁动态开辟一个头结点,我们不妨把它封装成一个函数,便于后面方便使用。当然,你如果觉得自己每次都可以自己写的话,也不必写成一个函数。

//创建新结点
SLTNode* BuySListNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

注意点:新结点的指针域置为空!

3.打印

先别急,我们先来试试水,先尝试自己动手写一下打印的函数。

这里为了比较更加形象起来,每次打印的时候都会用->来连接,同时,最后用NULL结尾

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

4.尾插

什么是尾插?根据字面意思,就是将新结点插入到到链表的尾部。

为了让大家更好理解,特地上网找了一张图片,一起来看看把

 每一次插入一个数都放在最后一个位置,同时,最后一个结点的指针域置为空,关键的就是,我们如何找到当前链表的尾结点呢?前面已经说了,最后一个结点的指针域为空,我们可以以此为突破点。注意:当链表为空时,你会怎么处理?想想。这里先不说了,直接看看我们的代码。

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else {
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

细心的你应该注意到了,这里我们使用的都是二级指针pphead

因为假设我们使用一级指针,直接传入头指针phead时,头指针本身就是一级指针的了,当我们需要更改该指针指向的地址时,改动只会在函数内部生效,main函数中的phead指针并没有被改变。要想改变的话,就需要二级指针来进行操作了

5.头插

有尾插自然就会有头插,相比较与尾插而言,头插显得更加简单了,直接把新的结点放在头结点前不就ok了?

//头插 
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

6.测试

好了,到这里,我们已经有一些函数了,不急,我们先来测试测试效果如何

void TestSList1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 0);
	SListPrint(plist);
}
int main()
{
TestSList1();
}

运行结果如下:

 我们必须养成边写代码边测试的习惯,这有利于我们及时发现自己的错误,不易导致后面出现一大堆bug而自己却不知道错在哪。当然,除此之外,我们还可以通过调试的方法,快速准确发现自己的bug,这也是我们需要养成的。这些都是需要我们去关注的点。

好啦,下面我不会在像上面那么详细的说明了,我们直接来个头删尾删

7.头删/尾删

有头插尾插,自然有头删尾删,其实,不知道你们发现,不管是插还是删,关于头部的操作都是比较简单了,我们先来个开胃菜,头删:可不能直接删哦,我们要记录头结点的下一个位置,如何直接删了头结点的话,那就麻烦,会造成野指针的,自己好好捋捋。

//头删
void SListpopFront(SLTNode**pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

尾删:说起尾删,就要多注意点了,要看具体情况而言了,直接来看代码把

//尾删
void SListPopBack(SLTNode** pphead)
{
	//链表为空
	if (*pphead == NULL)
	{
		return;
	}
	//只有一个结点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有一个以上的结点
	else {
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

尾删的关键点在于找到最后一个结点,最后一个结点的指针域为空。

1.链表为空时,不需要删,

2.链表只有一个结点,那它自己就是最后一个结点了,

3.多个结点就按常规处理就ok了,该说清楚的还是要说清楚的。 

8.查找

查找这个操作其实是比较简单的,在这里说是为了后面的使用,想要找到摸个元素,直接去调用函数即可,不用自己一次次去遍历。

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

9.在pos的前面插入x

除了基本的头尾增加,我们还可能还需要在某一个特定节点前后进行插入,这就需要我们玩转起来了,变得更加灵活。

两个核心点:

1.pos 的位置

2.插入的操作(这里可能有的同学会有一些疑惑,其实只要知道一点,插入的位置是已经知道的了)

//在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos == *pphead) {
		SListPushFront(pphead,x);
	}
	else {
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

10.删除pos位置的值

关键的一点,如何找到pos,找到之后链表跳过它,然后删除即可。

//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		SListpopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

三、主函数Test

这个没啥好说的,自己可以去试试

这只是单纯的试试函数能不能调用起来,自己可以动气手来试一试

结束语

好啦,这次想说的主要都讲完了,其实学数据结构除了实现之外,我们还需要及时去刷一些OJ题,提高我们的能力,使自己的知识融会贯通起来

加载全部内容

相关教程
猜你喜欢
用户评论