• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

数据结构-单项链表基本操作(c语言实现)

互联网 diligentman 14分钟前 2次浏览

1.申请空间并初始化

SLNode* BuySLNode(DateType x)
{
	SLNode*node = (SLNode*)malloc(sizeof(SLNode) * 1);
	if (node == NULL)
	{
		printf("failed to open up capacity");
	}
	node->date = x;
	node->next = NULL;
	return node;
}

相对于顺序表,按需求去申请空间,不存在空间浪费问题 

2.头插(头插多个节点以便于其他接口的测试)

void SListPushFront(SLNode**plist,DateType x)
{
	assert(plist);
	SLNode*newnode = BuySLNode(x);
	newnode->date = x;
	newnode->next = *plist;
	*plist = newnode;
}

3.查找数据

SLNode* SListFind(SLNode**plist, DateType x)
{
	assert(plist);
	SLNode*cur = *plist;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		else
			cur = cur->next;
	}
	return NULL;
}

函数最后返回SLNode*的指类型的好处(可以修改当前数据 有利于后面接口的测试) 。

4.修改数据

void SListModify(SLNode*pos, DateType x)
{
	assert(pos);
	pos->date = x;
}

5.在pos的下一个位置插入一个节点

void SListInsertAfter(SLNode*pos, DateType x)//在pos的下一个节点插入一个节点
{
	assert(pos);//防止传的是空指针
	SLNode*next = pos->next;
	SLNode*newnode = BuySLNode(x);
	pos->next = newnode;
	newnode->next = next;
}

6.在pos的上一个位置插入一个节点

void SListInsertBefore(SLNode**plist, SLNode*pos, DateType x)//在pos的前一个节点插入一个节点
{
	assert(pos);
	assert(plist);
	SLNode*newnode = BuySLNode(x);
	if (pos == *plist)
	{
		newnode->next = *plist;
		*plist = newnode;
	}//考虑pos的位置在第一个节点,即头插
	else
	{
		SLNode*prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}//多个节点的时候
	
}

这里需要考虑pos在第一个节点与在其它节点的时候。

7.将pos的下一个节点 删除

void SListEraseAfter(SLNode*pos)//将pos的下一个节点删除
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLNode*next = pos->next;
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

这里需要考虑pos在第一个节点与在其它节点的时候。

8.将pos所在的当前节点删除

void SListEraseCur(SLNode**plist,SLNode*pos)//删除当前节点
{
	assert(pos);
	if (pos == *plist)
	{
		SLNode*next = (*plist)->next;
		free(pos);
		pos = NULL;
		*plist = next;
	}//考虑的是pos的位置在第一个节点处
	else
	{
		SLNode*next = pos->next;
		SLNode*prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;

		}
		free(pos);
		pos = NULL;
		prev->next = next;
	}

}

这里需要考虑pos在第一个节点与在其它节点的时候。相对于顺序表的插入与删除数据 ,链表不用挪动数据,效率提高。

9.释放空间

void SListDestory(SLNode**plist)
{
	assert(plist);
	SLNode*cur = *plist;
	while (cur)
	{
		SLNode*next = cur->next;
		free(cur);
		cur = next;
	}
    *plist = NULL;//防止*plist成为野指针
}

因为申请了空间,所以一定要释放空间,不然会导致内存泄漏的问题。这里传一级指针的话,主函数里的SLNode*phead会成为野指针。如果传了一级指针的话,还需要在主函数里将SLNode*phead制空

10.打印(为了测试各个接口)

void Print(SLNode**plist)
{
	assert(plist);
	SLNode*cur = *plist;
	while (cur)
	{
		printf("%d->", cur->date);
		cur = cur->next;
	}
	printf("NULLn");
}//为了测试接口

11.测试

void test()
{
	SLNode*phead = BuySLNode(4);
	SListPushFront(&phead, 2);
	SListPushFront(&phead, 3);
	Print(&phead);
	SLNode*pos = SListFind(&phead, 3);
	if (pos)
	{
		/*pos->date = 20;*///如果查找数据成功,也可以改变当前数据
		printf("date foundn");
	}
	else
	{
		printf("date not found");
	}
	SListModify(pos,20);
	Print(&phead);
	SListInsertAfter( pos, 4);//pos的下一个位置插入一个节点
	Print(&phead);
	SListInsertBefore(&phead, pos, 5);//pos的前一个位置插入一个节点
	Print(&phead);
	SListEraseAfter(pos);//消除pos的下一个节点
	Print(&phead);
	SListEraseCur(&phead, pos);//消除当前pos的位置的节点
	Print(&phead);
	SListDestory(&phead);
}

11.测试结果 :

 数据结构-单项链表基本操作(c语言实现)

链表的增删查改就分享到这里了,感谢你的浏览。如果感兴趣的话,可以给个关注,数据结构-单项链表基本操作(c语言实现)

下期将发布与双向链表相关的基本操作文章。 

 

 

 

 

 

 


程序员灯塔
转载请注明原文链接:数据结构-单项链表基本操作(c语言实现)
喜欢 (0)