【数据结构】单链表完整代码实现

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

单链表

前置文章:顺序表的代码实现

1、链表的定义

每个结点除了存放数据元素外,还要存储指向下一个结点的指针。

2、链表的特点

  • 不要求大片连续空间
  • 改变容量方便
  • 不可随机存取
  • 要耗费一定空间存放指针

3、链式存储结构

//单链表的存储结构
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

4、完整实现代码

代码结构:

  • 定义单链表结构
  • 初始化单链表
  • 单链表的取值方法
  • 单链表的查找方法
  • 单链表的插入方法
  • 单链表的删除方法
  • 主函数用以测试

代码详情:

#include<iostream>
#include<string>

using namespace std;

/*
	单链表(带头结点)
*/

typedef int ElemType;
typedef int Status;

typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

//初始化 有头结点
Status InitList(LinkList &L)
{
	L = new LNode;
	L->next = NULL;
	return 1;
}

/*
	单链表的取值(按位序取值): 时间复杂度O(n)
	参数一:要取值的单链表
	参数二:要取值的位置
	参数三:待保存的对象
	注意:成功:返回1;失败:返回0。
*/
Status GetElem(LinkList L,int i,ElemType &e)
{
	LNode *p = L->next;
	int j = 1;
	while (p && j<i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i) 
	{
		return 0;
	}
	e = p->data;
	return p->data;
}

/*
	单链表的查找(按位序查找): 时间复杂度O(n)
	参数一:要查找的单链表
	参数二:要查找的数据
	注意:成功:返回下标地址;失败:返回NULL。
*/
LNode* LocateElem(LinkList L, ElemType e)//使用Book类型的外号ElemType作为传入参数e的类型,使用int类型的外号Status作为函数的返回值类型
{
	LNode* p = L->next;//创建新结点,并指向第一块数据
	while (p && p->data!=e)//如果p不为空且data == e,返回p的地址
	{
		p = p->next;
	}
	return p;
}

/*
	单链表的插入(按位序插入(后插法)):  时间复杂度O(n)
	参数一:要插入的单链表
	参数二:要插入的位置
	参数三:要插入的数据
	注意:成功:返回1;失败:返回0。
*/
Status ListInsert(LinkList& L, int i, ElemType e)
{
	if (i<1)
	{
		return 0;
	}
	LNode* p = L;//创建临时结点指向头结点,头结点不存数据
	int j = 0;//记录p指向的是第几个结点,第0个结点为头结点,头结点不存数据,只存地址
	while (p && (j<i-1))//循环找到第i-1个结点
	{
		p = p->next;
		j++;
	}
	if (!p || j>i-1)//如果地址p为NULL就退出,头结点的地址也不为空
	{
		return 0;
	}
	LNode* s = new LNode; //创建新结点
	s->data = e;//新结点存放新数据e
	s->next = p->next;//将p的指针指向的下一个数据地址赋值给新结点s的指针
	p->next = s;//p的指针指向新节点s

	return 1;
}

/*
	单链表的删除(按位序删除): 时间复杂度O(n)
	参数一:要删除的单链表
	参数二:要删除的位置
	注意:成功:返回1;失败:返回0。
*/
Status ListDelete(LinkList& L, int i)
{
	LNode* p = L;//创建临时结点指向头结点,头结点不存数据
	int j = 0;//记录p指向的是第几个结点,第0个结点为头结点,头结点不存数据,只存地址
	while (p->next&&(j<i-1))//循环找到第i-1个结点的前一个结点
	{
		p = p->next;
		j++;
	}
	if (!(p->next)||(j>i-1))
	{
		return 0;
	}
	LNode* q = p->next;//创建新结点q,指向要删除的数据内存地址
	p->next = q->next;//p的指针指向q的指针指向的下一个数据地址
	delete q;//释放q结点

	return 1;
}

int main()
{
	LinkList L;
	//创建单链表
	//CreateList_H(L,5);
	//初始化单链表
	InitList(L);
	//插入单链表
	for (int i = 1; i < 6; i++)
	{
		ListInsert(L, 1, i);
	}
	//取值
	int e;
	for (int i = 1; i <= 5; i++)
	{
		cout << GetElem(L, i, e) << endl;
	}
	
	//查找
	cout << "5的地址为:" << LocateElem(L, 5) << endl;
	//删除
	ListDelete(L, 1);
	cout << "删除第一个元素5:" << endl;
	for (int i = 1; i < 5; i++)
	{
		cout << GetElem(L, i, e) << endl;
	}
	
	return 1;
}

5、知识补充

补充创建单链表的两种方法:前插法和尾插法。还有单链表插入的两种方法:前插法和尾插法。

注:此段知识补充内容,未经本人实践验证,只是遇到了,总结到此处,仅供参考。

相关代码:

/*
	前插法创建单链表
*/
//void CreateList_H(LinkList& L, int n)
//{
//	L = new LNode;
//	L->next = NULL;
//	for (int i = 0; i < n; i++)
//	{
//		LNode* p = new LNode;
//		cin >> p->data;
//		p->next = L->next;
//		L->next = p;
//	}
//}
/*
	尾插法创建单链表
*/
//void CreateList_R(LinkList& L, int n)
//{
//	L = new LNode;
//	L->next = NULL;
//	LNode* r = L;
//	for (int i = 0; i < n; i++)
//	{
//		LNode* p = new LNode;
//		cin >> p->data;
//		p->next = NULL;
//		r->next = p;
//		r = p;
//	}
//}

/*
	单链表的插入(前插法): 时间复杂度O(1)
	参数一:要插入的结点
	参数二:要插入的数据
	注意:成功:返回1;失败:返回0。
	原理:前插法即开辟新结点s,复制p结点的值,然后将数据e存给p结点,再将s的指针指向p的指针指向,p的指针指向s。可谓是偷天换日、原地TP。
*/
Status ListPriorInsert(LNode *p, ElemType e)
{
	if (p == NULL)
	{
		return 0;
	}
	LNode* s = new LNode;//创建新结点
	if (s == NULL)
	{
		return 0;
	}
	s->data = p->data;//复制插入的前一个数据到新开辟的空间
	p->data = e;  //前一个数据存放新数据e
	s->next = p->next;//将p的指针指向的下一个数据地址赋值给新结点s的指针
	p->next = s;//p的指针指向新节点s

	return 1;
}

/*
	单链表的插入(后插法): 时间复杂度O(1)
	参数一:要插入的结点
	参数二:要插入的数据
	注意:成功:返回1;失败:返回0。
*/
Status ListNextInsert(LNode* p, ElemType e)
{
	if (p == NULL)
	{
		return 0;
	}
	LNode* s = new LNode;//创建新结点
	if (s == NULL)
	{
		return 0;
	}
	s->data = e;//新结点存放新数据e
	s->next = p->next;//将p的指针指向的下一个数据地址赋值给新结点s的指针
	p->next = s;//p的指针指向新节点s

	return 1;
}

6、最后

以上为个人实践总结,如有错误和疏漏的地方,欢迎大佬评论区指正和补充…
觉得写还不错的话,还请点赞、收藏、评论和分享,非常感谢~


参考文献文章来源地址https://www.toymoban.com/news/detail-723168.html

  1. 《数据结构》C 语言版,严为敏 吴伟民编,清华大学出版社,2009.

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

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

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

相关文章

  • 【数据结构】认识链表和模拟实现单链表

    即使骑的小电驴,也要奋力前进 目录 1.链表 1.1 链表的概念  1.2 链表的逻辑结构图和物理结构图 1.2.1 链表的逻辑结构图  1.2.2 链表的物理结构图  1.3链表结构的分类 1.3.1 链表通过什么进行结构的分类  1.3.2 不同链表结构的逻辑图 2.模拟实现一个单向链表  2.1 MyLinkedList类的

    2024年02月14日
    浏览(58)
  • 【数据结构】链表(单链表与双链表实现+原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月24日
    浏览(143)
  • [C语言][数据结构][链表] 单链表的从零实现!

    目录 零.必备知识 1.一级指针 二级指针 2. 节点的成员列表     a.数据     b.指向下一个节点的指针. 3. 动态内存空间的开辟 (malloc-calloc-realloc) 一.单链表的实现与销毁          1.1 节点的定义         1.2 单链表的尾插         1.3 单链表的头插         1.4 单链表的尾删  

    2024年04月11日
    浏览(76)
  • 链表的总体涵盖以及无哨兵位单链表实现——【数据结构】

     😊W…Y:个人主页 在学习之前看一下美丽的夕阳,也是很不错的。 如果觉得博主的美景不错,博客也不错的话,关注一下博主吧💕 在上一期中,我们说完了顺序表,并且提出顺序表中的问题 1. 中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释

    2024年02月14日
    浏览(68)
  • 数据结构:队列的链表结构(含完整代码,可复制)

    1.输出队列 2.入队一个元素 3.出队一个元素 5.建立链表队列 6.完整代码

    2024年01月16日
    浏览(48)
  • 一起学数据结构(3)——万字解析:链表的概念及单链表的实现

    上篇文章介绍了数据结构的一些基本概念,以及顺序表的概念和实现,本文来介绍链表的概念和单链表的实现,在此之前,首先来回顾以下顺序表的特点: 1. 顺序表是一组地址连续的存储单元依次存储的线性表的数据结构,逻辑上:顺序表中相邻的数据元素,其物理次序也是

    2024年02月13日
    浏览(54)
  • 数据结构-链表-单链表(3)

    目录 1. 顺序表的缺陷 2. 单链表 2.1 单链表的基本结构与接口函数 2.2 重要接口 创建新节点的函数: 2.2.1 尾插 2.2.2 头插 2.2.3 尾删 2.2.4 头删 2.2.5 查找 2.2.6 插入 2.2.7 删除 2.2.8 从pos后面插入 2.2.9 从pos后面删除 3. 链表的缺陷与优势: 4. 链表与顺序表比较 写在最后: 为什么

    2024年01月17日
    浏览(110)
  • [数据结构]链表之单链表(详解)

    在学习 链表 之前,我们已经学习了 顺序表 了 根据 顺序表 的特点,我们可以发现 顺序表 有优点,也有一些缺陷。 所以根据 顺序表 的缺点,链表就横空出世啦~ **概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次

    2023年04月08日
    浏览(56)
  • 【数据结构】- 链表之单链表(下)

    未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散 本章是关于数据结构中的链表之单链表(下) 提示:以下是本篇文章正文内容,下面案例可供参考 1.2.1 在pos位置插入(也就是pos位置之前) 流程图 多个节点 一个节点 1.2.2 在pos位置之后插入 流程图: 注意: 下面这种写

    2023年04月23日
    浏览(63)
  • 【算法基础】数据结构| 单链表+双链表 代码实现+图解+原理

    博主简介: 努力学习的预备程序媛一枚~ 博主主页: @是瑶瑶子啦 所属专栏: Java岛冒险记【从小白到大佬之路】 因为瑶瑶子正在备战蓝桥杯和校内ACM选拔赛,最近在学习算法相关的知识。我是借助 AcWing网站 来学习的,这篇文章是我学习就我学习内容的一个笔记,其中的一些

    2024年02月01日
    浏览(61)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包