单链表的基本实现(详细图解+解说)

  • Post author:
  • Post category:其他



目录


一.前言:


二.链表的结构实现:


三.单链表的功能实现-增删查…..


1.结点的申请


2.数据的头插


3.数据的打印


4.数据的尾插


5.数据的头删


6.数据的尾删


7.数据的查找


8.数据的指定插入和指定删除


9.链表的销毁


四.后言



一.前言:

我们都知道,顺序表是一块

连续

的可以存放数据的存储空间,其可以通过下标或指针解引用的方式快速访问某个位置的数据,但是由于空间的连续性,想要灵活的插入和删除数据便较为困难。

区别于顺序表,链表由一个个独立的可以存放数据的内存单元所构成,它们所拥有的空间在内存中一般是

不连续

的,每个独立的内存单元又称为

结点。

对于每个节点,其不仅存储了所需的数据,还存储了下一个节点的地址,因此可以由节点顺序寻址找到下一个节点。


二.链表的结构实现:

链表是由多个

结点

相互链接形成的一种数据结构,换言之,结点是基本单位,下面介绍节点的实现

代码(编程语言为C语言):

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

一个结点为简单定义的一个结构体,其结构成员包含:

1.SLDateType类型的结构体

变量data

,用来存放数据。

2.此结构体指针类型的结构体

变量next

,用来存放下一个结点的地址

由结点这一基本单位,假设我们创造n个节点,通过结构体成员next存放下一个节点的地址,从而将它们串连起来,便实现了一个可以存放数据的链表结构。在已知结点地址后,我们可以通过结构体指针p访问数据:p->data 及下一个结点的地址:p->next。

如图,每个方框代表一个结点,其内可以存放数据和地址。若用p1,p2,p3…..代表每个结点的地址,那么对于每一个结点而言,这个结点总是存放着下一个结点的地址。因此给定一个头节点地址,其总是能顺序访问至尾结点,即遍历链表。

链表是结构体指针来控制的

然而需要注意的是,对于一个空链表,其内部应该是没有数据的。也就是说,此时并没有创建任何结点,因此为了方便对链表进行管理,使用一个头指针slist指向头节点,若无结点,则slist指向NULL。此时链表便被我们很好的创建了。


三.单链表的功能实现-增删查…..


1.结点的申请

想要实现链表,对链表进行数据的增加,结点的创建是必不可少的,因此我们定义一个函数来创建结点。将数据传入函数,并返回新开辟空间的地址。

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
	if (tmp == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}
	tmp->data = x;
	tmp->next = NULL;
	return tmp;
}

对tmp进行判断,若开辟失败其值为空指针,则打印错误信息,程序中断。若开辟成功,则将数据复制给data,并将其next初始化为NULL。


2.数据的头插

对于数据的头插,首先我们肯定要

1.申请新结点

,那么接下来怎么进行链接呢?

如图,此时需要将新申请的tmp结点头插入链表之中,则只需要先

2.将tmp结点内的next指向结点p1

然后再

3.将slist指向新结点tmp

此时新结点插入完成,即完成了数据的头插,下面给出代码实现:

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);//判断是否为空指针

	SListNode* tmp = BuySListNode(x);//步1
	tmp->next = *pplist;//步2
	*pplist = tmp;//步3
}

注:此处形参为头指针的二级指针,是因为函数需要对外部定义的头指针变量进行修改,使其指向新节点。若传入二级指针时,必须assert断言其是否为空。而若为一级指针,则无需判断,因为若链表为空,则其值便是NULL。下文函数实现功能同理。


3.数据的打印

此处先介绍数据的打印,以便于对刚实现的头插功能进行测试,同时也便于对后文实现的增删功能进行测试。

那么数据如何进行打印呢?我们知道,我们可以通过头指针找到第一个结点,结点内的next又可以寻找下一个结点,因此我们可以轻易的对链表进行遍历。下图为代码实现:

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

由于不需要对头指针进行修改,与前文不同,此处形参为一级指针,是头指针的一份临时拷贝。首先定义变量cur表示当前结点位置,其初值为头指针的值。然后while循环进行遍历打印cur->data,直到cur为空指针时跳出。第一次循环cur为plist,即第一个结点的地址p1,然后打印data,cur被赋值为p2,继续循环……以下为循环图情况:

打印实现好之后,我们接下来完善剩余功能。


4.数据的尾插

1.申请新结点

2.遍历寻找当前尾结点p

3.插入新结点-将tmp赋值给p->next即可


如图操作即可,代码如下:

SListNode* tmp = BuySListNode(x);
SListNode* tail = *pplist;
while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = tmp;

尾结点特点便是p->next=NULL,因此如上代码,利用tail->next的条件判断,循环遍历寻找尾结点,再将tmp与尾结点进行链接。

然而我们需要考虑到,这只是一般情况。还有一种特殊情况没有考虑到-

不存在尾结点

,也即当前链表为空,此时则相当于头插,需要修改头指针,因此形参必须为二级指针。对于此特殊情况,*pplist==NULL,若执行上述程序,则条件判断时对空指针进行访问,显然是行不通的,因此需要与上述情况区别开,再复用头插函数进行插入,完整代码如下:

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* tmp = BuySListNode(x);
	SListNode* tail = *pplist;
	if (tail == NULL)
	{
		*pplist = tmp;
	}
	else
	{
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = tmp;
	}
}


5.数据的头删

较为简单,只需

1.首先令头指针指向结点2



2.再将结点1结构体申请的空间释放

即可。 当然考虑特殊情况,若链表为空,无可删除的结点,此时则需要另行处理。最后给出代码如下:

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)//若为空指针,打印错误信息
	{
		printf("no valid data: %d\n",__LINE__);
		return;
	}
	SListNode* tmp = *pplist;//步1
	*pplist = tmp->next;
	free(tmp);//步2
}

此处临时变量tmp的作用是保存结点1的地址p1,否则执行步1后找不到结点1的地址,也就无法释放内存,造成内存泄漏。


6.数据的尾删



以上图为例,基本思路是先找到尾结点p2,将p2结构体空间释放,然后将其前一个结点的next值改为NULL。但是要注意,目前我们实现的

单链表只能向后访问,无法向前访问

,因此我们的目的应该是尾结点前一个结点。代码实现如下:

        SListNode* tail = *pplist;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;

当tail->next->next==NULL时,即找到了p1处结点。然后将尾结点tail->next释放,再将p1的next赋值为NULL,即完成尾删。

然而还需要考虑两种特殊情况,

1.链表为空  2.链表只有一个结点。

对于这两种情况,显然上述代码是无法处理的,因此分开考虑,最终代码如下:

void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)
	{
		printf("no valid data: %d\n", __LINE__);
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

1.如果为空指针,打印错误信息然后返回。  2.如果其值的next为空,即只有一个结点,此时释放此结点,头指针置空  3便为一般情况,上文已经解释过。


7.数据的查找

-传入查找值,返回此值所在结点的地址,若没找到,返回NULL

简单的链表遍历,此处不过详细介绍,直接上代码:

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

以cur为变量进行遍历,如果cur->data为查找值,则返回cur。否则遍历直到cur==NULL,函数返回NULL。


8.数据的指定插入和指定删除

-此处插入为向前插入

前文说过,链表是由结构体指针控制的,指定插入或删除需要以结点的地址为位置向前插入或直接删除,因此我们需要调用前文的SListFind函数来找到指定值的结点地址。

思路与前文的增删基本一致,下面给出代码:


指定插入:

void SListInsert(SListNode** pplist,SListNode* pos, SLTDateType x)
{
	assert(pplist);
	assert(pos);
	SListNode* tmp = BuySListNode(x);
	if (*pplist == pos)
	{
		SListPushFront(pplist, x);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		tmp->next = prev->next;
		prev->next = tmp;
	}
}

分三种情况:

1.首先断言,若为空链表或目标位置为NULL则无法插入。

2.if-若头结点为目标位置,则调用头插函数。

3.else-寻找目标结点的

前一个结点

,然后将目标节点及其之前,之后的结点进行链接。


指定删除:

void SListErase(SListNode** pplist,SListNode* pos)
{
	assert(pplist);
	assert(pos);//.....
	if (*pplist == pos)
	{
		SListPopFront(pplist);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

同样三种情况:

1.首先断言,若为空链表或目标位置为NULL则无法插入。

2.if-若头结点为目标位置,则调用头删函数。

3.寻找目标结点的

前一个结点

,然后与目标结点下一个结点进行链接,并释放目标结点的空间。


9.链表的销毁

-注意需要将头指针置空

遍历释放空间即可

void SListDestory(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;
}

先保存此结点下一个空间的地址,然后再释放此结点(若先释放则找不到下个结点),利用循环遍历实现,最后头指针*pplist置空。

四.后言

单链表部分就介绍到此,如有错误,欢迎指正。这篇博客花了博主挺长时间(哭),路过的小伙伴也不妨点个关注呀,感谢支持



版权声明:本文为Eliauk_U原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。