当前位置： 首页 > news >正文

【数据结构：链表】——无头单向非循环链表的实现（C语言）

news 来源：原创 2024/4/29 4:51:55
1、什么是链表？

链表：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
详细了解： 链表的详解
在这里插入图片描述
注： 实际上链表的结构是多样的，总共有8种链表结构。
1.单项、双向
2.带头、不带头
3.循环、不循环
在这里插入图片描述
在这里插入图片描述 在这里插入图片描述
虽然有八种数据结构但是生活中我们常用的结构也就是这两种链表结构：无头单向非循环链表、带头双向循环链表。
在这里插入图片描述

  1. 无头单向非循环链表： 结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结
    构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表： 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向
    循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而
    简单了，后面我们代码实现了就知道了。
2、链表的实现

1、无头单向非循环链表无头单向非循环链表

3、代码实现

从上面图片中我们就可以看出来该链表该链表的一个节点由指针域和数据域各一个构成，在通过指针域相互连接。
链表节点数据结构定义：

typedef int SlistNodeDate;

//节点结构体
typedef struct SlistNode
{
	SlistNodeDate _date;
	struct SlistNode* _next;
}SlistNode;

//编写操作 防止直接传结构体出现二级指针
typedef struct Slist
{
	SlistNode* _head;
}Slist;

解释一下在节点结构声明完成后为什么还要再声明一个结构；因为方便在对链表进行操作，防止二级指针操作失误。链表的操作都是用指针来完成的当传入链表的头结点就要传该节点的地址就要用二级指针，而声明结构体后就完美的解决了传二级指针的问题了。
【注意】：这里不给出头文件，读者自己加上
Slist.h文件

typedef int SlistNodeDate;

//节点结构体
typedef struct SlistNode
{
	SlistNodeDate _date;
	struct SlistNode* _next;
}SlistNode;

//编写操作 防止直接传结构体出现二级指针
typedef struct Slist
{
	SlistNode* _head;
}Slist;

void SlistInit(Slist *plt);//链表初始化
void SlistPushBack(Slist *plt, SlistNodeDate x);//尾部插入
void SlistPushFront(Slist *plt, SlistNodeDate x);//头部插入
SlistNode* SlistFind(Slist *plt, SlistNodeDate x);//查找某个节点在链表中的位置
void SlistInsertAfter(SlistNode *pos, SlistNodeDate x);//在某个节点的后一位插入一个节点
void SListEraseAfter(SlistNode *pos);//删除某个节点的后一位
void SlistRemove(Slist *plt, SlistNodeDate x);//删除指定的节点
void SlistReverse_1(Slist *plt);//翻转链表 三指针原链表翻转
void SlistPopBack(Slist *plt);//尾部删除
void SlistPopFront(Slist *plt);//头部删除
void SlistDestory(Slist *plt);//删除链表
void SlistPrint(Slist *plt);//输出链表

Slist.c文件

void SlistInit(Slist *plt)//链表初始化
{
	assert(plt);

	plt->_head = NULL;
}

void SlistPushBack(Slist *plt, SlistNodeDate x)//尾部插入
{
	assert(plt);

	SlistNode *newnode = (SlistNode*)malloc(sizeof(SlistNode));
	newnode->_date = x;
	newnode->_next = NULL;

	if (plt->_head == NULL)//链表为空
	{
		plt->_head = newnode;
	}
	else//链表不为空
	{
		SlistNode *cur = plt->_head;
		while (cur->_next != NULL)
		{
			cur = cur->_next;
		}
		cur->_next = newnode;
	}
}

void SlistPushFront(Slist *plt, SlistNodeDate x)//头部插入
{
	assert(plt);

	SlistNode  *newnode =(SlistNode*)malloc(sizeof(SlistNode));
	newnode->_date = x;
	newnode->_next = NULL;

	if (plt->_head == NULL)//链表为空
	{
		plt->_head = newnode;
	}
	else//链表不为空
	{
		newnode->_next = plt->_head;
		plt->_head = newnode;
	}
}

void SlistPopBack(Slist *plt)//尾部删除
{
	assert(plt);
    SlistNode *cur = plt->_head;

	if (plt->_head == NULL)
	{
		return;
	}
	else if (cur->_next == NULL)
	{
		free(cur);
		plt->_head = NULL;
	}
	else
	{
		while (cur->_next->_next != NULL)
		{
			cur = cur->_next;
		}
		free(cur->_next);
		cur->_next = NULL;
	}
}

void SlistPopFront(Slist *plt)//头部删除
{
	assert(plt);
	SlistNode  *cur = plt->_head;

	if (plt->_head == NULL)
	{
		return;
	}
	else if (cur->_next == NULL)
	{
		free(cur);
		plt->_head = NULL;
	}
	else
	{
		plt->_head = cur->_next;
		free(cur);
	}
}

SlistNode* SlistFind(Slist *plt, SlistNodeDate x)//查找某个节点在链表中的位置
{
	assert(plt);

	SlistNode *cur = plt->_head;

	while (cur != NULL)
	{
		if (cur->_date == x)
		{
			return cur;
		}
		else
		{
			cur = cur->_next;
		}
	}
	return NULL;
}

void SlistInsertAfter(SlistNode *pos, SlistNodeDate x)//在某个节点的后一位插入一个节点
{
	assert(pos);
	SlistNode *newnode = (SlistNode*)malloc(sizeof(SlistNode));
	newnode->_date = x;
	newnode->_next = NULL;

	//先连接节点的后面，在连接节点的前面
	newnode->_next = pos->_next;
	pos->_next = newnode;
}

void SListEraseAfter(SlistNode *pos)//删除某个节点的后一位
{
	assert(pos);
	
	if (pos->_next == NULL)
	{
		return;
	}
	else
	{
		SlistNode *next = pos->_next;
		pos->_next = next->_next;
		free(next);
		next = NULL;
	}
}

void SlistRemove(Slist *plt, SlistNodeDate x)//删除指定节点
{
	    assert(plt);

		SlistNode *prev = NULL;
		SlistNode *cur = plt->_head;
		if (plt == NULL)
		{
			return;
		}
		else
		{
			while (cur != NULL)
			{
				if (cur->_date == x)
				{
					if (prev == NULL)//该节点没有前驱
					{
						plt->_head = cur->_next;
				    	free(cur);
					    cur = NULL;
						cur = plt->_head;
					}
					else//该节点有前驱
					{
						prev->_next = cur->_next;
						free(cur);
						cur = NULL;
						cur = prev->_next;
					}
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
				
			}
	}
}

void SlistDestory(Slist *plt)//删除链表
{
	assert(plt);
	SlistNode *cur = plt->_head;

	if (plt->_head == NULL)
	{
		printf("空链表\n");
	}
	else
	{
		while (plt->_head != NULL)
		{
			SlistNode *cur = plt->_head;
			plt->_head = cur->_next;
			free(cur);
		}
		printf("删除成功！\n");
	}
}

void SlistPrint(Slist *plt)//输出链表
{
	SlistNode *cur = plt->_head;
	if (plt->_head == NULL)
	{
		printf("链表为空！\n");
	}
	else
	{
		while (cur != NULL)
		{
			printf("%d->", cur->_date);
			cur = cur->_next;
		}
		printf("NULL\n");
	}
}

void SlistReverse_1(Slist *plt)//翻转链表 三指针原链表进行逆转
{
	assert(plt);

	SlistNode *prev = NULL;
	SlistNode *cur = plt->_head;
	SlistNode *next = NULL;
    
	if (cur == NULL)
	{
		return NULL;
	}
	else if (cur->_next == NULL)
	{
		return ;
	}
	else
	{
		while (cur != NULL)
		{
			next = cur->_next;
			cur->_next = prev;
			prev = cur;
			cur = next;
		}
		plt->_head = prev;
	}
}

main.c文件

int main()
{
	//测试函数
void Test_Slist_1()//w
{
	Slist pl;

	SlistInit(&pl);

	SlistPushBack(&pl, 1);
	SlistPushBack(&pl, 2);
	SlistPushBack(&pl, 3);
	SlistPushBack(&pl, 4);
	SlistPushFront(&pl, 0);
	SlistPrint(&pl);

	//SlistPopBack(&pl);
	//SlistPopBack(&pl);
	//SlistPopBack(&pl);
	//SlistPopBack(&pl);
	SlistPopFront(&pl);
	SlistPrint(&pl);
	//SlistPopFront(&pl);
	//SlistPopFront(&pl);
	//SlistPopFront(&pl);
	//SlistPopFront(&pl);
	SlistReverse_1(&pl);
	SlistPrint(&pl);
	SlistReverse_1(&pl);
	SlistPrint(&pl);

	//SlistDestory(&pl);
}
	system("pause");
	return 0;
}

运行截图：
在这里插入图片描述

带头双向循环链表在下一篇中实现

相关文章：

  • 【数据结构：链表】——带头双向循环链表的实现（C语言）
  • 【数据结构：堆】——堆及堆的相关操作（C语言）
  • c++入门——基础知识点（1）
  • c/c++内存管理
  • 函数模板、类模板初识
  • 【Linux】进程地址空间了解
  • 【Linux】入门基础命令（1）
  • c++入门——基础知识点（2）
  • 【Linux】基础文件的I/O操作（1）
  • 【Linux】进程信号
  • 【Linux】网络编程套接字（1）
  • 【Linux】UDP网络套接字编程
  • 【数据结构：树】——搜索二叉树-K模型(非递归和递归)
  • 【C++】——STL关联式容器认识以及使用
  • TCP三次握手和四次挥手详解
  • 2019.2.20 c++ 知识梳理
  • 3.7、@ResponseBody 和 @RestController
  • ES2017异步函数现已正式可用
  • gf框架之分页模块(五) - 自定义分页
  • IP路由与转发
  • Java 网络编程（2）：UDP 的使用
  • java取消线程实例
  • oldjun 检测网站的经验
  • Service Worker
  • VUE es6技巧写法（持续更新中~~~）
  • webpack项目中使用grunt监听文件变动自动打包编译
  • XML已死 ？
  • 阿里研究院入选中国企业智库系统影响力榜
  • 分享自己折腾多时的一套 vue 组件 --we-vue
  • 简单实现一个textarea自适应高度
  • 看域名解析域名安全对SEO的影响
  • 可能是历史上最全的CC0版权可以免费商用的图片网站
  • 利用DataURL技术在网页上显示图片
  • 聊聊flink的BlobWriter
  • 码农张的Bug人生 - 见面之礼
  • 使用Swoole加速Laravel(正式环境中)
  • 学习笔记TF060:图像语音结合，看图说话
  • 验证码识别技术——15分钟带你突破各种复杂不定长验证码
  • 原生Ajax
  • shell使用lftp连接ftp和sftp,并可以指定私钥
  • ​低代码平台的核心价值与优势
  • ​力扣解法汇总1802. 有界数组中指定下标处的最大值
  • ​直流电和交流电有什么区别为什么这个时候又要变成直流电呢？交流转换到直流（整流器）直流变交流（逆变器）​
  • #LLM入门|Prompt#2.3_对查询任务进行分类|意图分析_Classification
  • #pragma pack(1)
  • #Z0458. 树的中心2
  • ${ }的特别功能
  • $分析了六十多年间100万字的政府工作报告，我看到了这样的变迁
  • （13）：Silverlight 2 数据与通信之WebRequest
  • (4) PIVOT 和 UPIVOT 的使用
  • （Redis使用系列） Springboot 使用Redis+Session实现Session共享 ，简单的单点登录 五
  • （八）Docker网络跨主机通讯vxlan和vlan
  • （附源码）springboot高校宿舍交电费系统 毕业设计031552
  • （亲测成功）在centos7.5上安装kvm,通过VNC远程连接并创建多台ubuntu虚拟机（ubuntu server版本）...
  • （十八）SpringBoot之发送QQ邮件