手把手教你实现链表—单链表(数据结构C语言实现3)

举报
bug郭 发表于 2022/07/31 12:50:10 2022/07/31
【摘要】 写在前面博主教你用最简单的方式,让你彻底理解链表,实现链表。 学习链表,要多调试,多画图,自己多实现几遍,拿下链表不在话下!@TOC 本节目标1.链表表示和实现(单链表+双向链表)2.链表的常见OJ题3.顺序表和链表的区别和联系 链表表示和实现(单链表+双向链表)顺序表的问题及思考问题:中间/头部的插入删除,时间复杂度为O(N)增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗增容一...

写在前面

博主教你用最简单的方式,让你彻底理解链表,实现链表。 学习链表,要多调试,多画图,自己多实现几遍,拿下链表不在话下!
@TOC

本节目标

1.链表表示和实现(单链表+双向链表)
2.链表的常见OJ题
3.顺序表和链表的区别和联系

链表表示和实现(单链表+双向链表)

顺序表的问题及思考问题:

  1. 中间/头部的插入删除,时间复杂度为O(N)
  2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗
  3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
  4. 思考:如何解决以上问题呢?下面给出了链表的结构来看看。

链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

逻辑结构

在这里插入图片描述想必大家看的都是链表的逻辑结构,其实真实并不存在连接两个链表的箭头,为了更好理解罢了。箭头代表前面的节点存了,后面节点的指针。
物理结构
物理结构就是真正的结构,便于初学者学习!
在这里插入图片描述是不是突然对链表有了更深刻的理解!

单链表的实现

// 1、无头+单向+非循环链表增删查改实现
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos);

链表节点创建
链表的创建也是用结构体创建。

  //类型创建
  typedef int SLDataType;
  typedef struct SListNode
  {
      SLDataType date;   //存值
      struct SListNode* next; //存下一节点的指针
  }SLNode;
// 动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
   SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
   newnode->date = x;
   newnode->next = NULL;
   return newnode;
}
// 打印
void SListPrint(SLTNode* phead)
{
   while (phead != NULL)
   {
   	printf("%d ", phead->date);
   	phead = phead->next;
   }
   printf("NULL\n");
}
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
   if (*pphead == NULL)
   {
   	*pphead = BuySListNode(x);
   }
   else
   {
   	SLTNode* tail = *pphead;
   	while (tail->next)
   	{
   		tail = tail->next;
   	}
   	tail->next = BuySListNode(x);
   }
}
//头插接口测试
void TestSList2()
{
   SLTNode* plist = NULL;
   SListPushFront(&plist, 1);
   SListPushFront(&plist, 2);
   SListPushFront(&plist, 3);
   SListPushFront(&plist, 4);
   SListPushFront(&plist, 5);
   SListPushFront(&plist, 6);
   SListPrint(plist);
}

在这里插入图片描述

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
   if (!*pphead)
   {
   	*pphead= BuySListNode(x);
   }
   else
   {
   	SLTNode* first = BuySListNode(x);
   	first->next = *pphead;
   	*pphead = first;
   }
}
//头插接口测试
void TestSList2()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
}

在这里插入图片描述

//头删
void SListPopFront(SLTNode** pphead)
{
	if (!*pphead)
	{
		return;
	}	
	else
	{
		*pphead = (*pphead)->next;
	}
}
//头删接口测试
void TestSList3()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
}

在这里插入图片描述

//尾删
void SListPopBack(SLTNode** pphead)
{
	//1头结点为空
	//2只有一个节点
	//3多个节点
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next ==NULL)
	{
		*pphead = NULL;
		free(*pphead);
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* ret = *pphead;
		while (tail->next)
		{
			ret = tail;
			tail = tail->next;
		}
		tail = NULL;
		ret->next = NULL;
		free(tail);
	}
}
//尾删接口测试
void TestSList4()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPrint(plist);
}

在这里插入图片描述

//查找节点x位置并返回节点位置
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	if (phead == NULL)  //节点为空
	{
		return NULL;
	}
	else
	{
		SLTNode *ret= phead;
		while (ret) 
		{
			if (ret->date == x)    //找到了
			{
				return ret;
			}
			ret = ret->next;
		}
		return NULL;           //找不到
		
	}
}

// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		return;
	}
	else if(*pphead==pos)
	{
		*pphead = newnode;
		newnode->next = pos;
	}
	else
	{
		SLTNode* ret = *pphead;
		while (ret->next != pos)
		{
			ret = ret->next;
		}
		ret->next = newnode;
		newnode->next = pos;
	}
	
}
//任意位置查找插入测试

void TestSList5()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SLTNode* pos = SListFind(plist,3);
	if (pos)
	{
		SListInsert(&plist,pos,0);
	}
	SListPrint(plist);
}

在这里插入图片描述

//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead==NULL)
	{
		return;
	}
	else if (*pphead == pos)
	{
		*pphead = NULL;
	}
	else
	{
		SLTNode* ret = *pphead;
		while (ret->next != pos)
		{
			ret = ret->next;
		}
		ret->next = pos->next;
		pos = NULL;
		free(pos);
	}
}


//任意位置修改接口测试
void TestList6()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPushBack(&plist, 6);
	SListPrint(plist);
	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}

在这里插入图片描述
单链表的实现就学习到这里,还有很多接口,等以后我们再学习吧,单链表结构简单但是实现复杂,我们下期博客学习双链表的实现!结构复杂,实现简单…未完待续····

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。