数据结构——单链表(不带头节点)

这篇具有很好参考价值的文章主要介绍了数据结构——单链表(不带头节点)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链表的概念

链表是一种物理存储结构上非联系,非顺序的存储结构,但数据元素的逻辑顺序是通过链表中的指针链接实现的

逻辑结构:
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法
实际物理结构:
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法

每个链表节点都有自己的地址,链表的物理结构实际上是前一个结点保存着下一个结点的地址

所以从上面图中可以看出:
1.链表在逻辑上是连续的,但在物理上不是连续的
2.现实中,每个结点都是从堆中申请的
3.在堆中申请空间,按照一定规则进行分配,所以两次连续的开辟空间可以连续,可能不连续


链表的分类

实际中的链表有多种结构
分别为:

  • 带头节点或不带头结点
  • 单向或双向
  • 循环或不循环

所以链表一共有8种结构

但是常用的只有:不带头节点非循环单链表 和 带头循环双向链表两种


单链表的实现

这里我们介绍的是不带头节点非循环单链表

单链表的结构

一个节点即存放了元素的值,也存放了下一个节点的地址,所以在结构体中,定义一个SLTDataType类型的data,以及结构体的自引用:struct SListNode* next作为指向下一个节点的指针

所以结构体如下:

typedef int SLTDataType;

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

到这里,我们知道了可以通过一个节点找到下一个节点,但是我们如何找到头节点呢?

解决办法就是用一个结构体类型的指针去指向头节点,也解释存放头节点的地址。
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法
所以在接下来的函数中,传这个头指针就可以了


单链表的接口函数

创建节点函数

因为每个节点都需要在堆中开辟,所以可以封装成一个函数,需要调用malloc去开辟空间

同时,在这个函数中,将data的值存放到节点中,因为不知道当前下一个节点的地址,所以next指针赋为NULL,最后返回这个节点的地址

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* new = (SLTNode*)malloc(sizeof(SLTNode));
	if (new == NULL)
	{
		perror("malloc fail");
		return;
	}
	new->next = NULL;
	new->data = x;
	return new;
}

打印函数

从头节点开始,直到NULL,遍历链表,并且打印出来

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

尾插函数

在实现尾插函数前,如果此时头指针指向的为NULL,在尾插函数中便会改变头指针的指向,也就是改变头指针的值,如果这个函数是传的一级指针的话,虽然在尾插函数中改变了头指针的指向,但在主函数中,头指针的改变并没有改变

传一级指针的情况图如下
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法

不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法

所以这样的情况下,就需要传二级指针,将头节点的二级指针pphead传过去,让后通过解引用*pphead去改变头指针的指向
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法
所以在后面的会改变头指针指向的函数中,都需要传二级指针

接下来,实现尾插函数

我们应先创建节点,调用SLTBuyNode函数
接下来还有一点要注意的:
如果此时头指针是空,就说明它后面没有任何节点,所以需要把newnode的节点地址赋值给头指针
如果不为空,找到尾节点,在尾节点的后面插入新节点

这里还需要注意的一个点是:二级指针是头指针的地址,这个地址一定不能为空,如果为空就出问题了,所以在函数开始应用assert断言判断一下pphead是否为空

头节点的值可能为NULL,所以不用断言判断*pphead

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

	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
	

}

头插函数

头插函数在头部插入,所以一点会改变头指针的指向,所以仍需传二级指针

然后灵newnode->next等于*pphead,然会再将newnode的值赋给头指针

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

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

头删函数

头删函数一定会改变头指针指向,所以需要传二级指针

头删,一定必须是链表中有节点,如果没有节点,则头删没有意义,如果链表为空,那么头指针的值就为null,所以我们可以通过断言判断*pphead是否为空,同时仍需判断pphead,所以这个函数的开头需要断言2次

因为节点都是动态开辟出来的,所以要用free函数释放,如果直接直接free*pphead,那么后面的节点都找不到了,因为也free掉了next的值

所以可以定义一个head变量指向第一个节点,然后先将head->next赋给*pphead,接下来再free掉head就可以了

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

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

尾删函数

和头删同样,需要传二级指针,以及断言2次

尾删,找到尾节点很简单,但是删除尾节点后还需要把尾节点前一个结点的next指针赋为NULL,但是如何找到这个倒数第二个结点是个问题

这里我们有2种放法:

1.利用tail->next->next找,当tail->next->next==NULL时,就找到了新的尾结点
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法

2.定义一个prev指针,让prev一直在tail指针的前面,当tail到达尾时,prev也自然是倒数第二个结点了
起始时:
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法
逐渐向后移动:
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法
最后:
不带头结点的单链表,# C\C++数据结构,数据结构,链表,算法

这里我们使用第一种方法,接着我们还会发现一个问题:当只有一个节点时,cur->next已经为空了。cur->next->next就错了
所以还需分类运算当只有一个节点的情况

void SLTPophBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

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

查找函数

遍历链表,如果找到则返回这个节点的地址,否则返回NULL

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pos = phead;
	while (pos != NULL)
	{
		if (pos->data == x)
		{
			return pos;
		}
		else
		{
			pos = pos->next;
		}
	}
	return NULL;
}

pos位置前插入

这个pos是通过SLTFind寻找返回的节点地址,这个地址不会为空,所以可以断言判断一下

如果想在pos位置前插入,就需要直到pos前一个位置,所以这里就需要遍历寻找pos的前一个结点prev,然后将prevnewndoepos链接在一起

如果这个pos等于*pphead,就是在头节点前插入,也就是头插

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

	if (pos==*pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)//想要插入pos前,就要知道pos前的节点,就需要遍历,所以单链表不适合在前面插入
		{
			prev = prev->next;
		}
		SLTNode* newnode = SLTBuyNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

因为在pos前插入,所以这个函数是不会做到尾插功能的

下面考虑一个问题:如果只给pos,不给头指针,怎么在pos前插入?

在pos后面插入,再交换pos和pos后面节点中的data值就做到了在pos前面插入


删除pos位置节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);

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

只给pos,不给头指针,也可以删除pos位置节点:交换pos和pos->next的data值,保存pos->next->next的值为nex,然后删除pos->next,最后链接pos和nex
但是这种方法不适用尾删


pos位置后面插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

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

因为在pos后面插入,所以不需要传头指针,同时还需要assert断言判断pos是否为空
在pos后面插入,所以这个函数实现不了头插


pos位置后面删除

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

pos后面删除,不仅到断言pos还需要断言pos->next

其余逻辑很简单


销毁函数

void SLTDestroy(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* del = *pphead;
	SLTNode* next = NULL;
	while (del != NULL)
	{
		next = del->next;
		free(del);
		del = next;
	}
	*pphead = NULL;
}

因为销毁会改变头指针的指向,所以需要传二级指针

如果链表为空,就不必销毁了,所以需要断言*pphead

销毁链表,是一个一个结点得释放,在释放当前节点前,需要保存下一个节点的地址,然后再销毁当前节点,再删除下一个节点

最后还需要把*pphead也就是头节点赋值为空*pphead = NULL


单链表的问题

从上面的代码中可以看出,对于单链表想要尾插,就需要找尾,想要尾删就需要找到尾和尾的前一个结点
并且在某个位置插入删除,需要找到这个位置的前一个结点
这些操作都需要遍历链表,效率低

这也正是单链表的问题,而这些问题放到带头循环双向链表就是小菜一碟了文章来源地址https://www.toymoban.com/news/detail-738824.html

到了这里,关于数据结构——单链表(不带头节点)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包