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

xumenger 发布于2021-10-11 10:58 / 3245人阅读

摘要：相对于顺序表的插入与删除数据，链表不用挪动数据，效率提高。如果感兴趣的话，可以给个关注，下期将发布与双向链表相关的基本操作文章。

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("NULL/n");}//为了测试接口

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 found/n");	}	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语言用链表实现队列c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/122138.html

【Redis基本数据结构】字典实现

摘要：字典又称为符号表关联数组或者映射是一种保存键值对的抽象数据结构字典作为一种常用数据结构被内置在许多程序语言中由于语言没有内置这种数据结构构建了自己的字典实现字典在中的应用相当广泛比如的数据库就是使用字典作为底层实现的对数据库的增删改查操作也字典, 又称为符号表关联数组或者映射,是一种保存键值对的抽象数据结构.字典作为一种常用数据结构被内置在许多程序语言中,由于 C 语言没有内置这种...

hqman 2019-07-24 14:39 评论0 收藏0
数据结构与算法JavaScript （不定时更新）

摘要：每个列表中的数据项称为元素。栈被称为一种后入先出，的数据结构。散列使用的数据结构叫做散列表。不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。因此二叉搜索树需要平衡，即左右子树高度要相近。楼楼非计算机专业，但是对计算机也还算喜欢。个人理解若有偏差，欢迎各位批评指正！对于数据结构和算法一直是我的薄弱环节，相信大多数前端工程师可能多少会有些这方面的弱点，加上数据结构和算法本...

levius 2019-08-26 11:40 评论0 收藏0
数据结构与算法JavaScript （不定时更新）

摘要：每个列表中的数据项称为元素。栈被称为一种后入先出，的数据结构。散列使用的数据结构叫做散列表。不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。因此二叉搜索树需要平衡，即左右子树高度要相近。楼楼非计算机专业，但是对计算机也还算喜欢。个人理解若有偏差，欢迎各位批评指正！对于数据结构和算法一直是我的薄弱环节，相信大多数前端工程师可能多少会有些这方面的弱点，加上数据结构和算法本...

mingde 2019-08-05 12:58 评论0 收藏0
MySQL InnoDB索引原理和算法

摘要：哈希索引学习哈希索引之前，我们先了解一些基础的知识哈希算法。最好能够避免碰撞或者达到最小碰撞。存储引擎中的哈希算法存储引擎使用哈希算法来查找字典，冲突机制采用链表，哈希函数采用除法散列。也许你经常用MySQL，也会经常用索引，但是对索引的原理和高级功能却并不知道，我们在这里一起学习下。 InnoDB存储索引在数据库中，如果索引太多，应用程序的性能可能会受到影响；如果索引太少，又会...

xiaokai 2019-08-01 13:57 评论0 收藏0
linux vfs系统基础

摘要：然而目录项不同，一旦目录项被读入内存，就把它转换成基于结构的一个目录项对象。总体架构图 showImg(https://segmentfault.com/img/bVN69I?w=782&h=442);showImg(https://segmentfault.com/img/bVN7av?w=772&h=703); fs_struct struct fs_struct { a...

MartinHan 2019-05-29 19:33 评论0 收藏0