敞开掘金成长之旅！这是我参加「掘金日新计划 2 月更文挑战」的第 1 天，点击检查活动概况

前语

回顾之前的顺序表，咱们发现就算是动态扩容，咱们也都是成倍的括，也或许存在空间糟蹋，并且顺序表的头插头删还十分麻烦，需求移动数据。而链表的存在就处理了头插头删以及空间糟蹋这一问题，说到链表，咱们脑海中就会浮现出一个链条把东西都链接起来。

链表

链表是一种物理存储结构上非接连、非顺序的存储结构，数据元素的逻辑顺序是经过链表中的指针链接次第完成的。这儿所谓的逻辑结构，其实就是为了便利了解，然后加上箭头用来表明关系的，但实际上并不存在箭头。

咱们发现，链式结构其实就是在该节点寄存下一个节点的地址，然后经过地址便能够访问到该节点的下一个节点。而上图中的箭头，仅仅为了便利了解，一个一个连接起来，但实际上是并不存在的。(逻辑结构)

因而，链式结构在逻辑上是接连的（如上图经过箭头链接起来），但在物理地址上却不必定接连。由于每一个节点都是在堆上拓荒空间，拓荒空间的地址有或许接连，又或许不接连。

链表种类

链表主要分为以下几类：单向与双向、带头与不带头、循环与非循环，而经过这三类的组合，又分为八种方式的链表：带头单向循环链表、带头单向不循环……

而咱们本次章节研讨的就是不带头单向非循环链表。把这一个连接后，后边的其它种类的链表就很好了解与完成了

接口完成

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//数据
	struct SListNode* next;//指向下一个结构体的指针
}SListNode;

动态请求节点

动态请求节点其实就是在堆上malloc出一块空间，并把数据data寄存在该节点中。由于后边的刺进操作都需求进行拓荒新空间，所以这儿单独给写了出来，后边用到的时分直接调用即可

//动态请求节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode*newnode=(SListNode*)malloc(sizeof(SListNode));//malloc空间
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;//将数据放在该节点的data
	newnode->next = NULL;//next置为空（防止野指针）
	return newnode;//回来新节点
}

尾插与尾删

尾插仍是需求进行画图，这样才干更好的了解

但是这儿假设传来的是个空指针，即假设是一个空的链表，那尾插时这个新节点就作为头节点来运用。（特殊情况）

//尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	//动态请求一个新节点
	SListNode* newnode = BuySListNode(x);
	//空表
	if (*pplist == NULL)
	{
		//这儿改动List，传址调用、形参是实参的临时复制，形参的修正不会影响实参，所以传List的地址，即用二级指针变量来接纳一级指针的地址，这时解引用后就会影响到List
		*pplist = newnode;
	}
	else
	{	//找尾巴
		SListNode* ptail = *pplist;
		//这儿修正的是结构体成员变量，所以不用二级指针
		while (ptail->next != NULL)
		{
			ptail = ptail->next;
		}
		//将节点接在尾巴上
		ptail->next = newnode;
	}
}

这儿需求留意的是，我是在外面定义的是一个结构体指针，要对此进行修正，有必要传址调用，由于传值调用形参的改动不会影响实参。而进行修正后（空表情况下进行尾插），后边的再次尾插其实改动的就不是该变量了，而是该变量的结构体成员next，以及next节点指向的data

尾删画图处理一切。

这儿需求留意的就是，假设只要一个节点的情况下，该节点的next就是空指针，然后再next就形成了空指针的解引用操作（NULL->next）这是错误的，所以咱们要考虑到只剩一个节点的特殊情况，另外，还要留意空表状况是不可删去的。

//尾删
void SListPopBack(SListNode** pplist)
{
	//空表不可进行删去，所以加个断言
	assert(*pplist);
	//只要一个数据时直接把该节点开释，然后置空即可
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* ptail = *pplist;//本意即SListNode*ptail=list
		//找到最终一个的前一个
		while (ptail->next->next!=NULL)
		{
			ptail = ptail->next;
		}
		//开释最终一个节点
		free(ptail->next);
		//并把指向最终一个节点的next置空（不置空就是野指针了，由于虽然开释了那块空间，但是它的前一个节点的next依然指向它）
		ptail->next = NULL;
	}
}

打印

这儿咱们写一个打印的接口，便利咱们调查。也很简单，遍历整个链表即可。

//单链表打印
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	//留意这儿是cur！=NULL，由于假设是cur->next ！=NULL的话，最终一个节点的数据不会被打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
}

这儿咱们来测验一下前面的尾插与尾删操作。

void SListTest2()
{
	SListNode* list = NULL;
	//传址调用，解引用后形参的修正会影响实参
	SListPushBack(&list, 0);
	//SListPrint(list);//0->NULL
	SListPushBack(&list, 1);
	SListPushBack(&list, 2);
	SListPushBack(&list, 3);
	SListPushBack(&list, 4);
	//打印
	//SListPrint(list);//0->1->2->3->4->NULL
	//尾删
	SListPopBack(&list);
	//SListPrint(list);//0->1->2->3->NULL
	SListPopBack(&list);
	SListPopBack(&list);
	SListPopBack(&list);
	SListPopBack(&list);
	SListPrint(list);//NULL
	//空表进行删去
	SListPopBack(&list);//报错 error
}

经过测验咱们发现一切都在掌控之中，并没有什么问题。接下来完成头插与头删。

头插与头删

头插

单链表的头插最为简单，时刻复杂度达到了O（1）,仍是经过画图然后更好的了解。这儿只需求将新节点的next指向目前的头指针，然后头指针再更新为新节点即可。

//头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
    //留意这儿形参是二级指针，由于这儿改动的是list，并不是改动list指向的结构体成员，所以传地址，而一级指针的地址，就要用二级指针pplist接纳
	SListNode* newnode = BuySListNode(x);
		newnode->next =*pplist;
		*pplist = newnode;
}

咱们假定是个空链表，咱们发现头插也是适用的。因而就以上代码就够了。头删

这儿咱们需求留意的就是，空表不可进行删去，然后其他的画个图就一目了然，需求留意的是，这儿依然是改动的list，所以仍是用二级指针。

//头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	//先保存
	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}

测验

//头插头删
void SListTest3()
{
	//头插
	SListNode* list = NULL;
	SListPushFront(&list,1);
	//SListPrint(list);//1->NULL
	SListPushFront(&list, 2);
	SListPushFront(&list, 3);
	SListPushFront(&list, 4);
	//SListPrint(list);//4->3->2->1->NULL
	//头删
	SListPopFront(&list);
	//SListPrint(list);//3->2->1->NULL
	SListPopFront(&list);
	SListPopFront(&list);
	SListPopFront(&list);
	SListPrint(list);//NULL
	//SListPopFront(&list);//error(空表不可删去)
}

这儿咱们经过测验，进行调查发现没有什么问题，接下来是单链表的查找。

查找

查找操作也很简单，无非就是遍历整个链表，然后找到data时回来该节点指针即可，找不到就回来空指针。其实也能够这样来完成：

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	//while (cur)
	//{
	//	if (cur->data == x)
	//	{
	//		return cur;
	//	}
	//	cur = cur->next;
	//}
	//return NULL;
	//简化版本
	while (cur && cur->data != x)
	{
		cur = cur->next;
	}
	//完毕循环的条件，要么就是cur== NULL，说明找不到，或者就是cur->data==x,找到了，这儿直接回来cur就行。
	return cur;
}

恣意方位刺进与删去

pos方位进行刺进 思路都在图纸当中，画图会愈加简单了解！

//在pos方位刺进
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	if (*pplist == pos)
	{
		//头插
		SListPushFront(pplist, x);
	}
	else
	{
		SListNode* cur = *pplist;
		//找到pos节点之前的一个
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		//将新节点刺进在此
		SListNode* newnode = BuySListNode(x);
		//找到了pos方位之前的了
		cur->next = newnode;
		newnode->next = pos;
	}
}

pos方位进行删去

//删去pos方位
void SListErase(SListNode** pplist, SListNode* pos)
{
	assert(pos);
	//假设pos指向list
	if (pos == *pplist)
	{
		SListPopFront(pplist);
	}
	else
	{
		SListNode* cur = *pplist;
		//找到pos方位之前的
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

销毁

最终就是单链表的销毁，由于咱们知道，malloc、realloc、calloc这几个函数都是与free成对呈现的。不然会造成内存走漏。这儿咱们也是需求进行遍历每一个节点，然后进行删去，不过需求留意的是在删去该节点之前。要先记住下一个节点。

//单链表销毁
void SListDestroy(SListNode** pplist)
{
	SListNode* cur = *pplist;
	while(cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;//必定要置空，不然后边打印就是野指针的访问
}

总结

在这儿，必定要多画图，根据图形来理清思路，然后再进行写代码，一起必定要考虑考虑特殊情况，比方空表状况下能不能删去，比方free的时分会不会存在野指针，并且还主张大家边写边调试，不要一口气从尾插写完，要逐渐进行，慢便是快！

end 日子本来烦闷，但跑起来就会有风！❤

【线性表】—不带头单向非循环链表的增删查改

前语

接口完成

动态请求节点

尾插与尾删

打印

头插与头删

查找

恣意方位刺进与删去

销毁

总结

作者信息

【线性表】—不带头单向非循环链表的增删查改

前语

接口完成

动态请求节点

尾插与尾删

打印

头插与头删

查找

恣意方位刺进与删去

销毁

总结

相关文章

真没必要再对 axios 进行过度的封装

Qt入门系列教程——02

用这4招 优雅的实现Spring Boot 异步线程间数据传递

如何用CSS将DIV盒子呈现卡片翻转效果

作者信息

用这4招优雅的实现Spring Boot 异步线程间数据传递