【数据结构】纯c语言版单链表

发布于:2023-01-26 ⋅ 阅读:(23) ⋅ 点赞:(0) ⋅ 评论:(0)

目录

一、链表的定义

二、创建一个节点

三、对链表进行头插

四、对链表进行头插

五、对链表进行头删

六、对链表进行尾删

七、对链表的打印

八、对链表的销毁

九、对链表的查找 

十、对链表某个数据前插入

十一、对链表某个数据后插入

十二、对链表某个位置删除

十三、不遍历插入节点

十四、不遍历删除一个节点

十五、单向链表的头标兵


一、链表的定义

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

为了往后使用数据类型的变换,这里通过typedef 给int换了一个名字,后面我们要换其他的数据类型可以直接吧第一行的int换成你想要的类型。

结构体内data储存数据,next储存下一个节点的地址。

我们接下来创建一个节点。

二、创建一个节点

SLTNode* BuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)//当内存申请失败了需要报错并停止运行
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	return newnode;
}

 我们需要用到一个SLTNode *类型的函数,因为我们要返回创建节点的地址。

这样我们就可以创建一个链表并在里面插入数据了

int main()
{
	SLTNode* plist = NULL;
	phead = BuyNode(1);
}

 phead表示为头结点。

三、对链表进行头插

void PushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode *newnode=BuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

这里要注意的是,用到了二级指针,之所以要用二级指针是因为:我们需要改变phead的值,所以我们必须要把plist的地址传进来。

四、对链表进行头插

这里需要分情况讨论:1、链表非空。2、链表为空。

当链表非空的时候,我们只需要找到尾节点,然后接上新节点就可以了。

但当链表为空的时候,我们就要让头指针指向新节点(需要改变头指针phead),所以还是需要用到二级指针。

void SlistPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyNode(x);
	if (*pphead == NULL)
		*pphead = newnode;
	else
	{
		//找到尾节点
		SLTNode* tail=*pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

五、对链表进行头删

这里我们设置了一个del变量储存将要删除的节点,每次删除节点我们都要free掉这个节点,不然会有内存泄露的风险。

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

六、对链表进行尾删

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
		return;
	//一个节点
	//多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;

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

因为尾结点需要找到为节点的前一个节点,并将其next值设置为NULL,所以需要分情况讨论。

七、对链表的打印

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

八、对链表的销毁

与上面的删除同理,链表的节点都是malloc出来的,养成好习惯,把每个malloc的空间的返回给系统避免资源浪费。

void SLTistDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

最后记得把phead指向NULL(也就是*pphead),避免野指针的产生。

九、对链表的查找 

注意它的返回类型是节点的指针型,在没找到节点时返回NULL。

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

十、对链表某个数据前插入

我们需要通过上面的find函数,找到我们想在哪个元素前插入的位置(pos)。我们需要找到pos亲一个节点prev,然后再把新节点插入prev节点与pos节点之间。

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assrtt(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPopFront(x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
			prev = prev->next;
		SLTNode* newnode = BuyNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

十一、对链表某个数据后插入

因为单向链表只能从前往后查找,所以我们需要从头结点一个个往下找,才能找到插入的位置。

但是如果你想在某个元素后面插入数据的话,只需要往下找一个就行了。

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* next = pos->next;
	SLTNode* newnode = BuyNode(x);
	newnode->next = next;
	pos->next = newnode;

}

十二、对链表某个位置删除

需要分情况讨论,我这里用了两个指针,当链表只有一个元素的时候不需要两个指针,所以需要分情况讨论。

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

}

思路就是把要删除位置的前一个(prev)找到,然后吧prev的next改成pos的next,最后释放pos

  给你这样一个链表,你如何在3节点前插入一个节点并且不遍历这个链表。

你如何在把3节点删除不遍历这个链表。

十三、不遍历插入节点

给出思路,在3节点后面插入一个节点:

并将其赋予3节点的值:

 最后将三节点的值改为要插入的值:

大功告成,贴上代码:

void SListInsertBefore(SLTNode* pos,SLTDataType x)
{
	assert(pos);
	SLTNode *newnode=(SLTNode *)malloc(sizeof(SLTNode));
	newnode->data = pos->data;
	newnode->next = pos->next;
	pos->next = newnode;
}

十四、不遍历删除一个节点

上思路:先把4节点的值赋予3节点。

 然后将3节点的next指向4节点的下一个。

 最后再将4节点销毁。

上代码:

void SListErasePos(SLTNode* pos)
{
	assert(pos&&pos->next);
	SLTNode* next = pos->next;
	pos->data = next->data;
	pos->next = pos->next->next;
	free(next);
	next = NULL;//养成好习惯,吧malloc的空间释放掉
}

这个方法还是有一个缺陷,就是pos不能指向最后一个节点。而上一个方法就没有这个烦恼。

对于这些方法也不用太纠结,因为日常使用中双向链表才是最实用的。

十五、单向链表的头标兵

我们用纯c语言写链表在头删头插的地方经常会应用到二级指针,这里有一个更合理的处理方式:

加上一个头标兵头结点,且头节点不存放任何数据

这个有多舒服,就比如头插的时候直接在头结点后加一个节点就行了也不用判断是否为空节点,头删的时候直接让头结点指向2号节点。

 


网站公告

欢迎关注微信公众号

今日签到

点亮在社区的每一天
签到