数据结构之单链表及其实现!

这篇具有很好参考价值的文章主要介绍了数据结构之单链表及其实现!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

​编辑

1.  顺序表的问题及思考

2.链表的概念结构和分类

2.1 概念及结构

2.2 分类

3. 单链表的实现

3.1 新节点的创建

3.2 打印单链表

3.3 头插

3.4 头删

3.5 尾插

3.6 尾删

3.7 查找元素X

3.8 在pos位置修改

3.9 在任意位置之前插入

3.10 在任意位置删除

3.11 单链表的销毁

4. 完整代码

5. 完结散花


数据结构之单链表及其实现!,数据结构与算法,数据结构

                                            悟已往之不谏,知来者犹可追  

创作不易,宝子们!如果这篇文章对你们有帮助的话,别忘了给个免费的赞哟

1.  顺序表的问题及思考

问题:

1. 中间/头部的插入删除,时间复杂度为O(N)

2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

思考:如何解决以上问题呢?下面给出了链表的结构来看看。

2.链表的概念结构和分类

2.1 概念及结构

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

数据结构之单链表及其实现!,数据结构与算法,数据结构

2.2 分类

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

1. 单项或者双向

数据结构之单链表及其实现!,数据结构与算法,数据结构

 2. 带头或者不带头

数据结构之单链表及其实现!,数据结构与算法,数据结构

 3. 循环或者非循环

数据结构之单链表及其实现!,数据结构与算法,数据结构

虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:

数据结构之单链表及其实现!,数据结构与算法,数据结构

 1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带 来很多优势,实现反而简单了,后面我们代码实现了就知道了。

下面我就来实现一下无头单向非循环链表~

3. 单链表的实现

这里我就具体实现一下接口~(SList.h)

#define _CRT_SECURE_NO_WARNINGS
#pragma once//避免头文件被多次引用
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SListDataType;//便于改变数据类型

//定义一个结构体类型的节点
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;//存储下一个节点的地址
}SListNode;

//1. 新节点的创建
SListNode* SListCreatNode(SListDataType x);

//2. 打印单链表
void PrintSList(SListNode* phead);

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x);

//4. 头删
void  SListPopFront(SListNode** phead);

//5. 尾差
void SListPushBack(SListNode** phead, SListDataType x);

//6. 尾删
void  SListPopBack(SListNode** phead);

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x);

//8. 在pos位置修改
void SListModify(SListNode* pos, SListDataType x);

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x);

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos);

//11. 销毁单链表
void SListDestroy(SListNode** phead);

3.1 新节点的创建

(1)代码实现

//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{
	SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
	if (NewNode == NULL)//判断空间是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	NewNode->data = x;//赋值
	NewNode->next = NULL;//置空
	return NewNode;
}

3.2 打印单链表

(1)代码实现

//2. 打印单链表
void PrintSList(SListNode* phead)
{
	if (phead == NULL)
	{
		printf("NULL");//如果链表没有元素就打印NULL
		return;
	}
	SListNode* cur = phead;
	//循环单链表打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

(2) 复杂度分析

  • 时间复杂度:因为需要遍历整个链表,显然时间复杂度为O(N)。
  • 空间复杂度:打印链表不需要格外的空间,所以空间复杂度为O(1).

3.3 头插

(1)代码实现

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
	assert(phead);
	SListNode* newnode =SListCreatNode(x);//创建一个新节点
	newnode->next =*phead;
	*phead = newnode;
}

(2) 复杂度分析

  • 时间复杂度:不需要额外时间的消耗,时间复杂度为O(1)。
  • 空间复杂度:固定创造一个节点,空间复杂度为O(1)。

3.4 头删

(1)代码实现

//4. 头删
void  SListPopFront(SListNode** phead)
{
	assert(phead);
	assert(*phead);//如果没有数据就不用头删,并报错
	SListNode* cur = (*phead)->next;
	free(*phead);
	*phead = cur;
}

(2) 复杂度分析

  • 时间复杂度:不需要额外时间的消耗,时间复杂度为O(1)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

3.5 尾插

(1)代码实现

//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
	assert(phead);
	if (*phead == NULL)
	{
		*phead = SListCreatNode(x);//创建新节点并插入
	}
	else
	{
		SListNode* tail = *phead;
		while (tail->next != NULL)//找到尾节点
		{
			tail = tail->next;
		}
		tail->next = SListCreatNode(x);//创建新节点并插入
	}
}

(2) 复杂度分析

  • 时间复杂度:需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:固定创造一个节点,空间复杂度为O(1)。

3.6 尾删

(1)代码实现

//6. 尾删
void  SListPopBack(SListNode** phead)
{
	assert(phead);
	assert(*phead);//链表为空就不进行尾删
	SListNode* tail = *phead;
	if (tail->next == NULL)//如果链表就只有一个元素就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

(2) 复杂度分析

  • 时间复杂度:需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

3.7 查找元素X

(1)代码实现

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	assert(phead);
	while (phead->next!=NULL)//注意最后一个节点是没有查找的
	{
		if (phead->data == x)
			return phead;
			phead = phead->next;
	}
	if (phead->data == x)
		return phead;//最后一个节点没有查找
	else
	return NULL;//没找到
}

(2) 时间复杂度

  • 时间复杂度:可能需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

3.8 在pos位置修改

(1)代码实现


//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
	assert(pos);
	pos->data = x;
}

(2) 时间复杂度

  • 时间复杂度:可能需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

3.9 在任意位置之前插入

(1)代码实现

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
	assert(phead);
	assert(*phead);
	if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
	{
		SListPushFront( phead,x);
	}
	else
	{
		SListNode* newnode = SListCreatNode(x);
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next  = pos;
	}
}

(2) 复杂度分析

  • 时间复杂度:可能需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

3.10 在任意位置删除

(1)代码实现

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
	assert(phead && *phead && pos);
	if (pos==*phead)//如果pos位置就是第一个节点就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

(2) 复杂度分析

  • 时间复杂度:可能需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

3.11 单链表的销毁

(1)代码实现

//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
	assert(*phead && phead);
	SListNode* cur = *phead;
	while (cur!= NULL)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*phead = NULL;
}

(2) 复杂度分析

  • 时间复杂度:可能需要遍历整个链表,时间复杂度为O(N)。
  • 空间复杂度:不需要格外的空间消耗,空间复杂度为O(1)。

4. 完整代码

SList.c

#define _CRT_SECURE_NO_WARNINGS

#include"SList.h"

//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{
	SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
	if (NewNode == NULL)//判断空间是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	NewNode->data = x;//赋值
	NewNode->next = NULL;//置空
	return NewNode;
}

//2. 打印单链表
void PrintSList(SListNode* phead)
{
	if (phead == NULL)
	{
		printf("NULL");//如果链表没有元素就打印NULL
		return;
	}
	SListNode* cur = phead;
	//循环单链表打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
	assert(phead);
	SListNode* newnode =SListCreatNode(x);//创建一个新节点
	newnode->next =*phead;
	*phead = newnode;
}

//4. 头删
void  SListPopFront(SListNode** phead)
{
	assert(phead);
	assert(*phead);//如果没有数据就不用头删,并报错
	SListNode* cur = (*phead)->next;
	free(*phead);
	*phead = cur;
}

//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
	assert(phead);
	if (*phead == NULL)
	{
		*phead = SListCreatNode(x);//创建新节点并插入
	}
	else
	{
		SListNode* tail = *phead;
		while (tail->next != NULL)//找到尾节点
		{
			tail = tail->next;
		}
		tail->next = SListCreatNode(x);//创建新节点并插入
	}
}

//6. 尾删
void  SListPopBack(SListNode** phead)
{
	assert(phead);
	assert(*phead);//链表为空就不进行尾删
	SListNode* tail = *phead;
	if (tail->next == NULL)//如果链表就只有一个元素就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	assert(phead);
	while (phead->next!=NULL)//注意最后一个节点是没有查找的
	{
		if (phead->data == x)
			return phead;
			phead = phead->next;
	}
	if (phead->data == x)
		return phead;//最后一个节点没有查找
	else
	return NULL;//没找到
}

//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
	assert(pos);
	pos->data = x;
}

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
	assert(phead);
	assert(*phead);
	if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
	{
		SListPushFront( phead,x);
	}
	else
	{
		SListNode* newnode = SListCreatNode(x);
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next  = pos;
	}
}

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
	assert(phead && *phead && pos);
	if (pos==*phead)//如果pos位置就是第一个节点就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
	assert(*phead && phead);
	SListNode* cur = *phead;
	while (cur!= NULL)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*phead = NULL;
}

5. 完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

数据结构之单链表及其实现!,数据结构与算法,数据结构数据结构之单链表及其实现!,数据结构与算法,数据结构文章来源地址https://www.toymoban.com/news/detail-838863.html

到了这里,关于数据结构之单链表及其实现!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】之顺序表及其实现!

    目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6  顺序表的头删 2.7 顺序表在pos位置插入 2.8  顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺序表的销毁 2.1

    2024年04月28日
    浏览(35)
  • 【数据结构与算法】之双向链表及其实现!

    ​                                                                                 个人主页:秋风起,再归来~                                                                                             数据结构与

    2024年04月23日
    浏览(42)
  • 单链表——“数据结构与算法”

    各位CSDN的uu们你们好呀,今天,小雅兰的内容终于是我们心心念念的单链表啦,这一块呢,是一个很重要的部分,也是一个对目前的我来说,比较困难的部分,下面,就让我们进入单链表的世界吧 之前小雅兰写过顺序表的内容: 顺序表(更新版)——“数据结构与算法”_认

    2023年04月26日
    浏览(45)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现,含注释

      头文件和源文件分开有很多好处:可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性,同时也可以使代码结构更清晰,方便代码的管理和维护。 LinkList.h test.cpp                  (下面所有函数都默认在类中实现)   我们以

    2024年02月07日
    浏览(58)
  • 【算法基础】(二)数据结构 --- 单链表

    ✨个人主页:bit me ✨当前专栏:算法基础 🔥专栏简介:该专栏主要更新一些基础算法题,有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下,互相监督打卡学习 🌹 🌹 🌹 实现一个单链表,链表初始为空,支持三种操作: 向链表头插入一个数; 删除第 k 个插

    2023年04月17日
    浏览(98)
  • 【数据结构与算法】单链表的排序算法(选择,冒泡,递归)

    目录 选择排序 冒泡排序 快速排序 合并两条链表并排序 选择排序 链表的选择排序思想与数组的排序类似,但是链表需要先找到里面最小或者最大的值,然后将这个值用改链语句进行操作 我们先看这个改链语句的操作(min是笔者打错了应该是max,但是图已经画好了就没有改)

    2024年02月04日
    浏览(56)
  • 【数据结构与算法】单链表的插入和删除

    🔥 本文由 程序喵正在路上 原创,CSDN首发! 💖 系列专栏: 数据结构与算法 🌠 首发时间:2022年9月21日 🦋 欢迎关注🖱点赞👍收藏🌟留言🐾 🌟 一以贯之的努力 不得懈怠的人生 众所周知,顺序表中的每个结点中只存放数据元素,其优缺点为: 优点:可随机存取,存储

    2024年02月07日
    浏览(43)
  • 【数据结构】单链表经典算法题的巧妙解题思路

    目录 题目 1.移除链表元素 2.反转链表 3.链表的中间节点 4.合并两个有序链表 5.环形链表的约瑟夫问题 解析 题目1:创建新链表 题目2:巧用三个指针 题目3:快慢指针 题目4:哨兵位节点 题目5:环形链表   介绍完了单链表,我们这次来说几个经典的题目,本篇的题目衔接下一

    2024年04月28日
    浏览(63)
  • 【数据结构与算法】单链表的增删查改(附源码)

      这么可爱的猫猫不值得点个赞吗 😽😻 目录 一.链表的概念和结构 二.单链表的逻辑结构和物理结构 1.逻辑结构  2.物理结构 三.结构体的定义 四.增加 1.尾插   SListpushback 2.头插  SListpushfront 五.删除 1.尾删  SListpopback 2.头删  SListpopfront 六.查找  插入  释放   打印 1.查找

    2024年02月02日
    浏览(75)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包