DS知识点总结--线性表定义及顺序表示

数据结构知识点汇总(考研C++版)

文章目录

  • 数据结构知识点汇总(考研C++版)
    • 二、线性表
      • 2.1 线性表的定义和操作
        • 2.1.1 线性表的定义
        • 2.1.2 线性表的基本操作
      • 2.2 线性表的顺序表示
        • 2.2.1 顺序表的定义
        • 2.2.2 顺序表上的基本操作的实现

二、线性表

2.1 线性表的定义和操作

2.1.1 线性表的定义

线性表是具有相线性表是具有相同数据类型的n(n>0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。若用工命名线性表,则其一般表示为同数据类型的n(n>0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。若用工命名线性表,则其一般表示为
L = ( a 1 , a 2 , ⋯ , a i , a i + 1 , ⋯ , a n ) L=(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n) L=(a1,a2,,ai,ai+1,,an)
式中,a是唯一的“第一个”数据元素,又称表头元素;a,是唯一的“最后一个”数据元素,又称表尾元素。除第一个元素外,每个元素有且仅有一个直接前驱。除最后一个元素外,每个元素有且仅有一个直接后继(“直接前驱”和“前驱”、“直接后继”和“后继”通常被视为同义词)。
线性表的特点:

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性,表中元素有其先后次序。
  • 表中元素都是数据元素,每个元素都是单个元素。
  • 表中元素的数据类型都相同,这意味着每个元素占有相同大小的存储空间。
  • 表中元素具有抽象性,即仅讨论元素间的逻辑关系,而不考虑元素究竟表示什么内容

线性表是一种逻辑结构,表示元素之间一对一的相邻关系。顺序表和链表是指存储结构两者属于不同层面的概念,因此不要将其混淆。

2.1.2 线性表的基本操作
InitList(&):初始化表。构造一个空的线性表。
Length():求表长。返回线性表工的长度,即1中数据元素的个数。
LocateElem(L,e):按值査找操作。在表中査找具有给定关键字值的元素。
Getelem(L,i):按位査找操作。获取表工中第i个位置的元素的值。
ListInsert(&,i,e):插入操作。在表工中的第i个位置上插入指定元素e 。ListDelete(&L,i,&e):删除操作。删除表工中第i个位置的元素,并用e返回删除元素的值 。Printzist():输出操作。按前后顺序输出线性表工的所有元素值。
Empty(L):判空操作。若为空表,则返回true,否则返回 falseDestroyList(&L):销毁操作。销毁线性表,并释放线性表工所占用的内存空间。

2.2 线性表的顺序表示

2.2.1 顺序表的定义

​ 线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在顺序表的起始位置,第i个元素的存储位置后面紧接着存储的是第i+1个元素,称i为元素a在顺序表中的位序。因此,顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。
假设顺序表工存储的起始位置为LOC(A)sizeof(ElemType)是每个数据元素所占用存储空间的大小,则表所对应的顺序存储如图所示。

image-20240621164241419

​ 线性表的元素类型为 ElemType,则静态分配的顺序表存储结构描述为:

#define MaxSize 50
typedef struct{
ElemType data[MaxSize]; //顺序表的元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义

​ 一维数组可以是静态分配的,也可以是动态分配的。对数组进行静态分配时,因为数组的大小和空间事先已经固定,所以一旦空间占满,再加入新数据就会产生溢出,进而导致程序崩溃。而在动态分配时,存储数组的空间是在程序执行过程中通过动态存储分配语句分配的,一旦数据空间占满,就另外开辟一块更大的存储空间,将原表中的元素全部拷贝到新空间,从而达到扩充数组存储空间的目的,而不需要为线性表一次性地划分所有空间。动态分配的顺序表存储结构描述为:

#define InitSize 100   //表长度的初始定义
typedef struct{  ElemType *data;   //指示动态分配数组的指针int MaxSize,length; //数组的最大容量和当前个数
}SeqList; //动态分配数组顺序表的类型定义

C的初始动态分配语句为

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

C++的初始动态分配语句为,

L.data=new ElemType[InitSize];

顺序表的主要优点:

  1. 可进行随机访问,即可通过首地址和元素序号可以在 0(1)时间内找到指定的元素
  2. 存储密度高,每个结点只存储数据元素。顺序表的缺点也很明显
  3. 元素的插入和删除需要移动大量的元素,插入操作平均需要移动 n/2 个元素,删除操作平均需要移动(n-1)/2个元素;
  4. 顺序存储分配需要一段连续的存储空间,不够灵活。
2.2.2 顺序表上的基本操作的实现

1、顺序表的初始化
静态分配和动态分配的顺序表的初始化操作是不同的。静态分配在声明一个顺序表时,就已为其分配了数组空间,因此初始化时只需将顺序表的当前长度设为0。

//sqList L; //声明一个顺序表
void Initlist(SqList &l){L.length=0; //顺序表初始长度为0
}

动态分配的初始化为顺序表分配一个预定义大小的数组空间,并将顺序表的当前长度设为 0。Maxsize指示顺序表当前分配的存储空间大小,一旦因插入元素而空间不足,就进行再分配。

void Initlist(Seqlist &){
L.data=(ElemType *)malloc(MaxSize*sizeof(ElemType)); //分配存储空间
L.length=0;   //顺序表初始长度为0
L.MaxSize=InitSize;//初始存储容量
}

2、插入操作
在顺序表工 的第i(1<=i<=.length+1)个位置插入新元素 e。若i的输入不合法,则返回 false,表示插入失败;否则,将第i个元素及其后的所有元素依次往后移动一个位置,腾出一个空位置插入新元素 e,顺序表长度增加 1,插入成功,返回 true。

bool ListInsert(SqList &l,int i,ElemType e){if(i<1||i>.length+1)return false; //判断i的范围是否有效if(1.length>=MaxSize)return false; //当前存储空间己满,不能插入for(int j=.length;j>=i;j--) //将第i个元素及之后的元素后移L.data[j]=L.data[j-1]; L.data[i-1]=e;L.length++;   //在位置i处放入e//线性表长度加1return true;
}

3、删除操作
删除顺序表1 中第i(1<=i<=L.length)个位置的元素,用引用变量e返回。若i的输入不合法,则返回 false;否则,将被删元素赋给引用变量 e,并将第 i+1 个元素及其后的所有元素依次往前移动一个位置,返回true。

bool ListDelete(SqList &l,int i,ElemType &e){if(i<1||i>.length)
//判断i的范围是否有效
return false;
e=L.data[i-1];  //将被删除的元素赋值给e
for(int j=i;j<L.length;j++)
L.data[j-1]=L.data[j];
L.length--;  //线性表长度减1
return true;

4、按值查找(顺序查找)
在顺序表工中查找第一个元素值等于e的元素,并返回其位序。

int LocateElem(SqListl,ElemType e){int i;for(i=0;i<L.length;i++)if(L.data[i]==e)//下标为i的元素值等于e,返回其位序i+1return i+1;
return 0; //退出循环,说明查找失败  

最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为(1)。

最坏情况:查找的元素在表尾(或不存在)时,需要比较n次,时间复杂度为(n)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/355772.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

python通过selenium实现自动登录及轻松过滑块验证、点选验证码(2024-06-14)

一、chromedriver配置环境搭建 请确保下载的驱动程序与你的Chrome浏览器版本匹配&#xff0c;以确保正常运行。 1、Chrome版本号 chrome的地址栏输入chrome://version&#xff0c;自然就得到125.0.6422.142 版本 125.0.6422.142&#xff08;正式版本&#xff09; &#xff08;…

V4和V6双栈处理

现进行双栈 对R1 对R2 对R3 对R4 路由地址配完&#xff0c;起协议 然后起ripng&#xff0c;在R2&#xff0c;R3&#xff0c;R4上都宣告一下 然后在PC1和PC2上都手动配置一下就可以了

Kafka第一篇——内部组件概念架构启动服务器zookeeper选举以及底层原理

目录 引入 ——为什么分布式系统需要用第三方软件&#xff1f; JMS 对比 组件 架构推演——备份实现安全可靠 &#xff0c; Zookeeper controller的选举 controller和broker底层通信原理 BROKER内部组件 ​编辑 topic创建 引入 ——为什么分布式系统需要用第三方软件&#…

游戏开发丨基于Tkinter的五子棋小游戏

文章目录 写在前面Tkinter五子棋系列文章写在后面 写在前面 本期内容&#xff1a;基于tkinter的五子棋小游戏 下载地址&#xff1a;https://download.csdn.net/download/m0_68111267/88700190 实验环境 python3.11及以上pycharmtkinter Tkinter Tkinter是Python的一个标准…

刷题记录(240613)

aliyun0512 1. 小红定义一个数组是好数组&#xff0c;当且仅当所有奇数出现了奇数次&#xff0c;所有偶数出现了偶数次。现在小红拿到了一个数组&#xff0c;她希望取一个该数组的非空子序列(可以不连续)&#xff0c;使得子序列是好数组。你能帮小红求出子序列的方案数吗?由于…

C# Winform Datagridview控件使用和详解

DataGridView 是一种以表格形式显示数据的控件&#xff0c;由Rows(行)&#xff0c;Columns(列)&#xff0c;Cells(单元格)构成。本实例将综合利用DataGridView的属性和事件&#xff0c;展示不同的表格风格数据和操作。包含&#xff1a; 添加Datagridview行&#xff0c;列数据设…

APP IOS

APP IOS苹果源生应用程序 APP Android-CSDN博客

【Python/Pytorch 】-- K-means聚类算法

文章目录 文章目录 00 写在前面01 基于Python版本的K-means代码02 X-means方法03 最小二乘法简单理解04 贝叶斯信息准则 00 写在前面 时间演变聚类算法&#xff1a;将时间演变聚类算法用在去噪上&#xff0c;基本思想是&#xff0c;具有相似信号演化的体素具有相似的模型参数…

【开源项目】智慧北京案例~超经典实景三维数字孪生智慧城市CIM/BIM数字孪生可视化项目——开源工程及源码!

飞渡科技数字孪生北京管理平台&#xff0c; 依托实景数字孪生底座&#xff0c;以城市感知网络为硬件基础&#xff0c;以城市大数据为核心资源&#xff0c;以数字孪生、云计算、人工智能为关键技术&#xff0c;实现城市产业规划、资产安全管理、城市能耗监控等一体化空间融合。 …

实现锚点链接点击tab跳转到指定位置 并且滚动鼠标顶部锚点的样式也跟随变化

实现效果如下 不管是点击还是 滚动鼠标 顶部的样式也会跟随变化 点击会跳转到指定的位置 通过IntersectionObserver 监听是否可见 下面代码可以直接执行到vue的文件 <template><div><ul class"nav"><li v-for"tab in tabs" :key…

Java——访问修饰符

一、访问修饰符是什么 Java中的访问修饰符用于控制类、接口、构造函数、方法和数据成员&#xff08;字段&#xff09;的可见性和访问级别。 Java提供了四种访问修饰符&#xff1a; 访问修饰符同一类内同一包内不同包的子类不同包的非子类适用对象public可见可见可见可见类、…

第 7 章: 对象关系映射

在第 6 章中&#xff0c;我们大概了解了如何通过 JDBC 来进行简单的数据库操作。通过 SQL 来执行操作虽然不算复杂&#xff0c;但在面向对象的语言中&#xff0c;这类操作多少显得有些格格不入&#xff0c;毕竟我们都是在与“对象”打交道。把对象与关系型数据库关联起来&#…

【目标检测】图解 DETR 系统框图

简略版本 Backbone&#xff1a;CNN backbone 学习图像的 2D 特征Positional Encoding&#xff1a;将 2D 特征展平&#xff0c;并对其使用位置编码&#xff08;positional encoding&#xff09;Encoder&#xff1a;经过 Transformer 的 encoderDecoder&#xff1a;encoder 的输出…

光纤中的数值 2.405 是怎么一回事?

在光纤通信中,光线的传播依赖于纤芯和包层之间的折射率差异。 即,当光线从纤芯入射到界面上时,如果入射角大于临界角 θ0,将发生全反射,没有光能量透射至包层而泄漏出去,此即光纤导光原理。 反映到光纤的端面,在光纤端面的光线,当入射角必须小于光纤的孔径角 α0 ,此时…

laravel中如何向字段标签添加工具提示

首先&#xff0c;您可以使用 轻松自定义字段标签->label()。我相信您知道这一点。但您知道吗……标签输出未转义&#xff1f;这意味着您也可以在标签中包含 HTML。 为了尽快实现上述目标&#xff0c;我只是采取了一个快速而粗糙的解决方案&#xff1a; CRUD::field(nickna…

Python 修炼|人人编程手册|001 计算思维

在微信中阅读,关注公众号:CodeFit。 > 创作不易,如果你觉得这篇文章对您有帮助,请不要忘了 点赞、分享 和 关注,为我的 持续创作 提供 动力! 1. 计算思维 在我们正式开启 Python 修炼之旅前,先来了解一个关键的概念 —— 计算思维。 计算思维,其核心本质在于 抽象 …

学生护眼大路灯应该怎么选?五款护眼大路灯对比推荐

我们都知道光线无处不在&#xff0c;想要减少近视隐患&#xff0c;就不得不提一下护眼灯了&#xff0c;特别是经常坐在电脑前码字的上班族以及深夜还在学习的学生党这一类人群&#xff0c;经常用眼光线不好不仅影响视力健康&#xff0c;还会影响效率。而一款护眼灯能够提供柔和…

阐述一下Golang中defer的原理

基本用法 在Go语言中&#xff0c;defer关键字用于在函数返回前执行一段代码或调用一个清理函数。这对于处理文件关闭、解锁或者返回一些资源到资源池等操作非常有用。 其基本用法如下所示&#xff1a; package mainimport "fmt"func main() {example() }func exam…

AI穿戴设备是未来手机的终结者?中国AI商业化的未来预测

AI技术的发展正处于商业化应用的关键阶段&#xff0c;而中国在互联网时代已凭借商业化应用逆袭。AI算法大模型虽强大&#xff0c;但真正普惠民众需与设备深度结合。穿戴式智能设备就成为了新战场&#xff0c;AI算法与穿戴设备结合能释放更大工作效率。私人助理AI将成趋势&#…

AI口语练习APP的开发流程

开发AI口语练习APP是一个持续的过程&#xff0c;需要多学科团队的紧密合作&#xff0c;包括产品经理、UI/UX设计师、前后端开发者、机器学习工程师、测试工程师和市场运营人员等。随着技术的发展和用户需求的变化&#xff0c;开发流程可能需要相应地进行调整和优化。AI口语练习…