程序员经验分享-hwhale

数据结构-线性表的链式存储（包含代码实现）

2023-05-16

线性表的链式表示和实现

链式存储结构

  • 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
  • 线性表的链式存储结构又称为非顺序映像或链式映像。
  • 用一组物理位置任意的存储单元来存放线性表的数据元素
  • 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
  • 链表中元素的逻辑次序和物理次序不一定相同

与链式存储结构相关的术语
1、结点：数据元素的存储映像。由数据域和指针域两部分组成

  • 数据域：存放元素数值数据
  • 指针域：存放直接后继结点的存储位置

2、链表：n个结点由指针链组成一个链表

  • 它是线性表的链式存储映像，称为线性表的链式存储结构

3、单链表、双链表、循环链表

  • 结点只有一个指针域的 链表，称为单链表或线性链表
  • 结点有两个指针域的链表，称为双链表
  • 首尾相接的链表称为循环链表

4、头指针、头结点和首元结点

  • 头指针：是指向链表中第一个结点的指针
    单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名
    若头指针名是L，则把链表称为表L
  • 首元结点：是指链表中存储第一个数据元素的结点
  • 头结点：是在链表的首元结点之前附设的一个结点

5、链表可分为带头结点和不带头结点

  • 无头结点时，头指针为空时表示空表
  • 有头结点时，当头指针的指针域为空时表示空表

在链表中设置头结点有什么好处？

  • 1、便于首元结点的处理
    首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置上一致，无须进行特殊处理；
  • 2、便于空表和非空表的统一处理
    无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

头结点的数据域内装的是什么？

  • 头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值

链表（链式存储结构）的特点

  • （1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
  • （2）访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，（这种存取元素的方法称为顺序存取法）所以寻找第一个结点和最后一个结点所花费的时间不等。

单链表的定义和表示

typedef struct LNode//声明结点的类型和指向结点的指针类型
{
	ElemType date;//结点的数据域
	struct LNode *next;//结点的指针域
}LNode,*LinkList;//LinkList为指向结构体LNode的指针类型
  • 定义链表L:LinkList L;
  • 定义结点指针p:LNode *p; 也可以LinkList p;
  • 重要操作
    p指向头结点： p=L;
    s指向首元结点： s=L->next;
    p指向下一个结点： p=p->next;

单链表基本操作的实现

单链表的初始化

  • 即构造一个空表
  • 算法步骤
    （1）生成新结点做头指针，用头指针L指向头结点。
    （2）将头结点的指针域置空

判断链表是否为空

  • 空表：链表中无元素称为空链表（头指针和头结点仍然存在）
  • 算法思路
    判断头结点的指针域是否为空

单链表的销毁

  • 链表销毁后不存在
  • 算法思路
    从头指针开始，依次释放所有结点

清空链表

  • 链表仍然存在，但链表中无元素，成为空链表（头指针和头结点仍然在）

  • 算法思路
    依次释放所有结点，并将头结点指针域设置为空

求单链表的表长

  • 算法思路
    从首元结点开始，依次计数所有结点

取值–取单链表中第i个元素的内容

  • 算法思路
    从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。

按值查找–根据指定数据获取该数据所在的位置（地址）

  • 算法步骤
    1、从第一个结点起，依次和e相比较
    2、如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址
    3、如果查遍整个链表都没有找到其值与e相等的元素，则返回0或者NULL；

插入–在第i个结点前插入值为e的新结点

  • 算法步骤
    1、首先找到i-1个元素的存储位置p
    2、生成一个数据域为e的新结点s
    3、插入新结点：
    ①新结点的指针域指向结点i s->next=p->next;
    ②结点i-1的指针域指向新结点 p->next=s;

删除–删除第i个结点

  • 算法步骤
    1、首先找到第i-1的存储位置p，保存要删除的第i个元素的值
    2、令p->next指向原本第i+1个元素
    3、释放原本第i个结点的空间

单链表的查找、插入、删除算法的时间效率分析

  • 1、查找：
    因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。
  • 2、插入和删除
    因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为为O(1)。
    但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。

建立单链表：头插法–元素插入在链表头部，也叫前插法

  • 算法步骤
    1、从一个空表开始，重复读入数据
    2、生成新结点，将读入数据存放到新结点的数据域中
    3、从最后一个结点开始，依次将各结点插入到链表的前端

建立单链表：尾插法–元素插入在链表尾部，也叫后插法

  • 算法步骤
    1、从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
    2、初始时，r同L一起指向头结点，每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点
#include<iostream>
using namespace std;

typedef struct student {
	int id;
	struct student* next;
}LNode,*linklist;

int InitList(linklist& L)//初始化一个空链表-
{
	L = new LNode;//或L=(linklist)malloc(sizeof(LNode));
	L->next = NULL;
	return 0;
 }

int ListEmpty(linklist L)//判断是否为空
{
	if (L->next == NULL)//为空
		return 0;
	else
		return 1;
}

void DestroyList(linklist& L)//销毁链表
{
	LNode* p;
	
	while (L)
	{
		p = L;//将p指向头结点
		L = L->next;//指向下一个
		delete p;
	}
}

void ClearList(linklist& L) //清空链表
{
	LNode* p, * q;
	p = L->next;//p指向首元结点
	while (p)//没到表尾
	{
		q = p->next;//q指向p的下一个结点
		delete p;//释放p
		p = q;//p指向下一个结点
	}
	L->next = NULL;//将头结点的指针域置空
}

int ListLength(linklist L)//获取链表长度
{
	linklist p;
	p = L->next;//p指向第一个结点
	int i = 0;
	while (p)//遍历单链表，统计结点数
	{
		i++;
		p = p->next;
	}
	return i;//返回统计的个数i
}

int GetElem(linklist L, int i, int& e)//获取链表中某个位置的元素
{
	LNode* p;
	p = L->next;//p指向首元结点
	int j = 1;//初始化
	while (p && j < i)//向后扫描，直到p指向第i个元素或者p为空
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)//第i个元素不存在
		return -1;
	e = p->id;//取第i个元素的数据域的值
	return 1;
}

LNode* LocateElem(linklist L, int e)//查找某个元素的地址
{
	LNode* p;
	p = L->next;//p指向首元结点
	while (p && p->id != e)//没到尾部并且没找到值为e的结点
	{
		p = p->next;
	}
	return p;//返回找到的结点
}

int LocateELem(linklist L, int e)//根据指定数据查看该数据的位置序号
{
	LNode* p;
	p = L->next;//p指向首元结点
	int j = 1;//初始化计数变量
	while (p && p->id != e)//未到尾部且未找到值为e的结点
	{
		p = p->next;
		j++;
	}
	if (p)
		return j;//找到返回位置序号
	else
		return 0;//没找到返回0

}

int ListInsert(linklist& L, int i, int e)//在指定位置插入数据
{
	linklist p = L;//将p指向头结点
	int j = 0;//初始化计数参数
	while (p && j < i - 1)//寻找第i-1个结点，p指向i-1个结点
	{
		p = p->next;
		++j;
	}
	if (!p || j > i-1)//i大于表长+1或者小于1，插入位置非法
		return -1;
	else
	{
		linklist s;
		//InitList(s);
		s = new LNode;//生成新结点s
		s->id = e;//将结点s的数据域置为e
		s->next = p->next;
		p->next = s;
		return 1;
	}
	
}

int ListDelete(linklist& L, int i,int &e)//删除第i个位置的元素
{
	linklist p= L;
	//InitList(p);
	//p = L;
	int j = 0;//初始化计数变量
	while (p->next && j < i - 1)//寻找第i个结点，并使p指向其前驱，p指向第i-1个结点
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i - 1)//删除位置不合理
	{
		return -1;
	}
	linklist q;
	q = p->next;//q指向第i个结点，临时保存被删结点的地址以备释放

	p->next = q->next;//改变删除结点前驱结点的指针域
	e = q->id;//保存删除结点的数据域
	delete q;//释放删除结点的空间
	return 1;
}

void CreateListHead(linklist& L, int n)//头插
{
	InitList(L);//先建立一个带头结点的单链表
	for (int i = n; i > 0; i--)
	{
		linklist p;//生成新结点p
		p = new LNode;
		cin >> p->id;//输入元素值scanf(&p->id)
		p->next = L->next;//插入到表头
		L->next = p;
	}
}

void CreateListTail(linklist& L, int n)//尾插
{
	InitList(L);
	LNode* r;//新建一个尾指针r
	r = L;//将其指向头结点
	for (int i = 0; i < n; ++i)
	{
		LNode* p;
		p = new LNode;//生成新结点
		cin >> p->id;//输入元素值
		p->next = NULL;//将新插入的结点的指针域置空
		r->next = p;//插入到末尾
		r = p;//r指向新的尾结点
	}
}

void DeleteLinkList(LinkList& L, int e)//删除单链表中某个元素为e的所有结点
{
    Lnode* p, * q;//定义一前一后两个指针
    p = new Lnode;
    q = new Lnode;
    p = L->next;//p指向首元结点
    q = L;//q指向头结点
    while (p)//未到末尾
    {
        if (p->date == e)//查看是否为e
        {
            q->next = p->next;//用q暂存p的下一个结点的地址
            free(p);//释放
            p = q->next;//将p从删除结点的前一个结点指向后面一个
        }
        q = p;//让q指向p
        p = p->next;//p后移一个
    }
}

void PrintLinkList(LinkList L)//输出单链表中的值
{
    Lnode* p;
    p = new Lnode;
    p = L->next;//将p指向首元结点
    while (p)//非空
    {
        cout << p->date << " ";
        p = p->next;
    }
}

int main()
{
	linklist L;
	InitList(L);
	int i=ListLength(L);
	cout <<"插入前元素个数为：" << i << endl;

	CreateListHead(L, 6);
	i = ListLength(L);
	cout << "头插后元素个数为：" << i << endl;

	cout << "头插后元素遍历：" << " ";
	for (int j = 1; j < 7; j++)
	{
		int e_id;
		GetElem(L, j,e_id);
		cout << e_id << " ";
	}
	cout << endl;

	ClearList(L);

	CreateListTail(L, 5);
	i = ListLength(L);
	cout << "尾插后元素个数为：" << i << endl;

	cout << "尾插后元素遍历：" << " ";
	for (int j = 1; j < 6; j++)
	{
		int e_id;
		GetElem(L, j, e_id);
		cout << e_id << " ";
	}
	cout << endl;

	ListInsert(L, 3, 89);

	for (int j = 1; j < 7; j++)
	{
		int e_id;
		GetElem(L, j, e_id);
		cout << e_id << " ";
	}
	cout << endl;

	int e_IDD;
	int result=ListDelete(L, 2, e_IDD);

	cout << "result=" << result << endl;
	for (int j = 1; j < 7; j++)
	{
		int e_id;
		GetElem(L, j, e_id);
		cout << e_id << " ";
	}
	cout << endl;

	return 0;
}

其它链表

循环链表

  • 是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）。
  • 优点：从表中任一结点出发均可找到表中其它结点。
  • 注意：
    由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或者p->next是否为空，而是判断它们是否等于头指针。
    循环条件 p!=L 或 p->next!=L
  • 注意：表的操作常常是在表的首尾位置上进行。

带尾指针的循环链表合并（将Tb合并在Ta之后）

  • 步骤：
    1、p存表头节点 p=Ta->next;
    2、Tb表头连接到Ta表尾 Ta->next=Tb->next->next;
    3、释放Tb表头结点 delete Tb->next;
    4、修改指针 Tb->next=p;
//带尾指针的循环链表合并（将Tb合并在Ta之后）
linklist Connect(linklist Ta, linklist Tb)//假设Ta,Tb都是非空的单循环链表
{
	LNode* p;
	p = Ta->next;//p存表头节点
	Ta->next = Tb->next->next;//Tb表头连接到Ta表尾
	delete Tb->next;//释放Tb表头结点 
	Tb->next = p;//修改指针
	return Tb;
}

双向链表

  • 在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表
  • 定义
typedef struct DulNode
{
	Elemtype date;//Elemtype是数据类型
	struct DulNode* prior, * next;
}DulNode,*DuLinkList;

双向循环链表

  • 和单链的循环链表类似，双向链表也可以有循环表
    （1）让头结点的前驱指针指向链表最后一个结点
    （2）让最后一个结点的后继指针指向头结点

双向链表结构的对称性

  • 设p指向某一结点p->prior->next=p=p->next->peior
  • 在双向链表中有些操作，因为仅涉及一个方向的指针，故他们的算法和线性链表的相同。但在插入、删除时，则需要修改两个方向上的指针，两者的操作时间复杂度均为O(n)。

双向链表的插入
在这里插入图片描述

int ListInsertDul(DuLinkList& L, int i, Elemtype e)//在带头结点的双向链表L中第i个位置之前插入元素e
{
	DuLinkList p;
	if (!(p = GetElemDul(L, i)))//找到第i个元素，将p指向它，若没找到，返回-1
		return -1;
	
	DuLinkList s;
	s = new DulNode;//新建一个结点
	s->date = e;//给新结点数据域赋值
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;
	return 1;
}

双向链表的删除
在这里插入图片描述

int ListDeleteDul(DuLinkList& L, int i, Elemtype& e)//删除带头结点的双向循环链表L的第i个元素，并用e返回
{
	DuLinkList p;
	if (!(p = GetElemDul(L, i)))//找到第i个元素，将p指向它，若没找到，返回-1
		return -1;
	e = p->date;//将要删除的结点的数据域保存到e中
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);//释放结点
	return 1;
}

总结

链式存储结构的优点

  • 结点空间可以动态申请和释放
  • 数据元素的逻辑次序靠结点的指针来显示，插入和删除时不需要移动数据元素

链式存储结构的缺点

  • 存储密度小，每个结点的指针域需要额外占用内存空间，当每个结点的数据域所占字节不多时，指针域所占用的存储空间的比重显得很大。
  • 链式存储结构是非随机存储结构。对于任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度

存储密度

  • 是指结点数据本身所占的存储量和整个结点结构中所占存储量之比，即
    存储密度=结点数据本身占用的空间/结点占用的空间总量
  • 一般的，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1（100%），而链表的存储密度小于1

单链表、循环链表和双向链表的时间效率比较
在这里插入图片描述

顺序表和链表的比较
在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构-线性表的链式存储（包含代码实现） 的相关文章

随机推荐

  • 安装PCL1.9.1其它版本号Python3.6+PCL1.9.1+VS2017+gtkbundle_3.6.4版本

    下载 python pcl文件 地址 xff1a https github com strawlab python pcl 安装 VS2017 安装PLC1 91 首先在自己电脑上安装PCL xff08 点击这里 xff09 xff0c 这

  • ROS--机器人小车仿真rviz

    URDF练习 需求描述 创建一个四轮圆柱状机器人模型 xff0c 机器人参数如下 底盘为圆柱状 xff0c 半径 10cm xff0c 高 8cm xff0c 四轮由两个驱动轮和两个万向支撑轮组成 xff0c 两个驱动轮半径为 3 25cm

  • ROS--URDF集成Gazebo仿真小车和rviz结合

    ROS URDF集成Gazebo仿真小车 实现流程 需要编写封装惯性矩阵算法的 xacro 文件 为机器人模型中的每一个 link 添加 collision 和 inertial 标签 xff0c 并且重置颜色属性 在 launch 文件中

  • 使用D435i深度相机运行ORB-SLAM3

    下载安装链接 下载ORB SLAM3地址 xff1a git clone https github com UZ SLAMLab ORB SLAM3 git eigen3多版本安装 xff1a https blog csdn net wei

  • keil5使用一个父工程打开多个子工程文件

    1 首先工程文件需要在同样的文件夹里 2 打开keil5 xff0c 选择Project New Multi Project Workspace 3 将工程文件建立在刚刚的总文件夹里面 xff0c 命名保存 4 弹出此页面 xff08 Cr

  • ​Android动态加载so！这一篇就够了！

    作者 xff1a Pika 链接 xff1a https juejin cn post 7107958280097366030 对于一个普通的android应用来说 xff0c so库的占比通常都是巨高不下的 xff0c 因为我们无可避免的

  • HTTP是什么

    HTTP是什么 HTTP是什么 HTTP协议是Hyper Text Transfer Protocol xff08 超文本传输协议 xff09 的缩写 是用于从万维网 xff08 WWW World Wide Web xff09 服务器传输

  • error: array has incomplete element type ‘char []‘

    原代码 xff1a void explain input char int char a 报错 xff1a error array has incomplete element type 39 char 39 原因 xff1a 可以用二维数

  • STM32串口接收十六进制数转为十进制数（包含负数）

    外部设备传输给STM32单片机十六进制数 例如0x09c4 代表2500 0xff38 代表 200 xff08 并不是65336 xff0c 因为这是有符号的 xff09 串口接收处理函数 接收到 5A A5 06 83 55 00 01

  • 无人机-3无人机ROS应用与开发

    一 ROS是什么 二 为什么要学习ROS 三 怎么学习ROS https www cnblogs com masbay p 10745170 html TF坐标系指机器人在现实世界会有坐标的变换 xff0c ROS已经将其算成固定的程序 x

  • ROS入门-4.安装ROS系统(ubuntu20.04版本安装ros的noetic版本)

    ubuntu20 04版本安装ros的noetic版本 1 添加软件源2 添加密钥3 更新4 安装ROS5 初始化rosdep6 设置环境变量7 测试ROS安装是否成功 1 添加软件源 2 添加密钥 3 更新 4 安装ROS 5 初始化ro

  • 数学建模-12.预测模型

    灰色预测 灰色系统 GM 1 1 模型 xff1a Grey Model GM 1 1 原理介绍 呢么 xff0c 准指数规律的检验 xff1f 发展系数 a 与预测情形的探究 发展系数越小预测的越精确 GM 1 1 模型的评价 在使用GM

  • 数学建模-数学规划模型

    数学规划模型 一 概述 1 什么是数学规划 xff1f 运筹学的一个分支 xff0c 用来研究在给定条件下 即约束条件 xff0c 如何按照某一衡量指标 xff08 目标函数 xff09 来寻求计划 管理工作中的最优方案 即求目标函数在一定

  • 机器学习西瓜书学习记录-第四章 决策树

    第4章 决策树 4 1基本流程 决策树 xff0c 一类常见机器学习方法 xff0c 希望从给定训练集学得一个模型用以对新示例进行分类 一般 xff0c 一棵决策树包含一个根结点 若干个内部结点和若干个叶结点 xff1b 叶结点对应于决策结

  • 机器学习西瓜书学习记录-第五章 神经网络

    第5章 神经网络 5 1神经元模型 神经网络中最基本的成分是神经元模型 M P神经元模型 xff0c 又称 阈值逻辑单元 在模型中 xff0c 神经元接收到来自n个其他神经元传递过来的输入信号 xff0c 这些输入信号通过带权重的连接进行传

  • 机器学习西瓜书学习记录-第六章 支持向量机

    第6章 支持向量机 移步b站学习 学习贴

  • SurfaceFlinger模块

    SurfaceFlinger是一个系统服务 xff0c 作用就是接受不同layer的buffer数据进行合成 xff0c 然后发送到显示设备进行显示 SurfaceFlinger进程是什么时候起来的 xff1f 在之前的Android低版本

  • STM32-串口通信实验

    一 通信接口背景知识 1 通信的两种方式 xff1a 并行通信 传输原理 数据各个位同时传输 优点 速度快缺点 占用引脚资源多 串行通信 传输原理 数据按位顺序传输 优点 占用引脚资源少缺点 速度相对较慢 2 串行通信 按照数据传送的方向

  • UDP介绍,编程流程

    介绍 xff1a 面向无连接的用户数据报协议 xff0c 不需要建立任何连接 xff0c 目的主机接收后不需要确认 UDP特点 xff1a 相比TCP速度快一些简单的应用程序直接使用 不需要加密对于海量数据不采用UDP广播和多播必须采用UD

  • 数据结构-线性表的链式存储（包含代码实现）

    线性表的链式表示和实现 链式存储结构 结点在存储器中的位置是任意的 xff0c 即逻辑上相邻的数据元素在物理上不一定相邻线性表的链式存储结构又称为非顺序映像或链式映像 用一组物理位置任意的存储单元来存放线性表的数据元素这组存储单元既可以是连

热门标签