数据结构——单链表

code-child

发布于 2023-05-30 14:14:05

1180

发布于 2023-05-30 14:14:05

文章被收录于专栏：codechildcodechild

单链表描述

链表在物理储存结构上是非连续的，它主要是通过指针指向下一个数据的。

节点都是动态开辟出来的。

我们把数据和指向下一个节点地址的指针叫做一个节点。

代码实现

注：本代码的实现的是动态的

创建节点

ctypedef int SLTypeDate;

typedef struct SListNode
{
	SLTypeDate date;
	struct SListNode* next;
}SListNode;

增加节点

cSListNode* BuySListNode(SLTypeDate x)
{
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
	if (NewNode == NULL)
		exit(-1);
	NewNode->date = x;
	NewNode->next = NULL;
	return NewNode;
}

链表数据的打印

cvoid SListPrint(SListNode* phead)
{
	while (phead)
	{
		printf("%d->", phead->date);
		phead = phead->next;
	}
	printf("NULL\n");
}

单链表的销毁

从头节点一个一个进行销毁

cvoid SListDestory(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur =*pphead;
	while (cur)
	{
		cur = (*pphead)->next;
		free(*pphead);
		*pphead = cur;
	}
}

头插

cvoid SListPushFront(SListNode** pphead, SLTypeDate x)
{
	assert(pphead);
	SListNode* NewNode=BuySListNode(x);
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
	if (NewNode == NULL)
		exit(-1);
	NewNode->date = x;
	NewNode->next = *pphead;
	*pphead = NewNode;
}

尾插

尾插的时候也要注意没有节点的情况。

cvoid SListPushBack(SListNode** pphead, SLTypeDate x)
{
	assert(pphead);
	SListNode* NewNode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		SListNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = NewNode;
	}
}

尾删

需要判断节点为1，还有多个的情况

cvoid SListPopBack(SListNode** pphead)
{
	assert(*pphead);

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

头删

先用临时变量储存起来头节点后面的节点

cvoid SListPopFront(SListNode** pphead)
{
	assert(*pphead);
	SListNode* cur = (*pphead)->next;
	free(*pphead);
	*pphead = cur;
}

查找数据的位置

查找到返回改节点的地址，查找不到返回空指针

cSListNode* SListFind(SListNode* phead, SLTypeDate x)
{
	assert(phead);
	while (phead->date!=x)
	{
		phead = phead->next;
		if (phead == NULL)
			return NULL;
	}
	return phead;
}

在查找位置之前插入

1.pos不能为空指针 2.注意在第一个节点前插的情况

cvoid SListInsertPre(SListNode** pphead, SListNode* pos, SLTypeDate x)
{
	assert(pphead);
	assert(pos);
	SListNode* NewNode = BuySListNode(x);
	
	if (pos==*pphead)
	{
		//NewNode->next = *pphead;
		//*pphead = NewNode;
		SListPushFront(pphead,x);
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		NewNode->next = pos;
		cur->next = NewNode;
	}
	
}

在查找位置之后插入

cvoid SListInsertAfter(SListNode* pos, SLTypeDate x)
{
	assert(pos);
	SListNode* NewNode = BuySListNode(x);
	NewNode->next = pos->next;
	pos->next = NewNode;
}

删除查找位置的节点

cvoid SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		//*pphead = (*pphead)->next;
		//free(pos);
		//pos = NULL;
		SListPopFront(pphead);
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
		pos = NULL;
	}
	
}

删除查找位置之后的节点

注意为最后一个节点的时候，不能进行删除

cvoid SListEraseAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	SListNode* cur = pos->next->next;
	free(pos->next);
	pos->next = cur;
	
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-26，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构