数据结构考研复习之线性表逻辑结构
线性表的定义
线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系,数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的,或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的,如学生情况信息表是一个线性表:表中数据元素的类型为学生类型; 一个字符串也是一个线性表:表中数据元素的类型为字符型,等等。
综上所述,线性表定义如下:
线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,通常记为:
(a1,a2,… ai-1,ai,ai+1,…an)
其中n为表长, n=0 时称为空表。
表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋,ai+1 称为 ai 的直接后继。就是说:对于ai,当 i=2,...,n 时,有且仅有一个直接前趋 ai-1.,当i=1,2,...,n-1 时,有且仅有一个直接后继 ai+1,而 a1 是表中第一个元素,它没有前趋,an 是最后一个元素无后继。
需要说明的是:ai为序号为 i 的数据元素(i=1,2,…,n),通常我们将它的数据类型抽象为datatype,datatype根据具体问题而定,如在学生情况信息表中,它是用户自定义的学生类型; 在字符串中,它是字符型; 等等。
线性表的基本操作
在第一章中提到,数据结构的运算是定义在逻辑结构层次上的,而运算的具体实现是建立在存储结构上的,因此下面定义的线性表的基本运算作为逻辑结构的一部分,每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。
线性表上的基本操作有:
⑴ 线性表初始化:Init_List(L)
初始条件:表L不存在
操作结果:构造一个空的线性表
⑵ 求线性表的长度:Length_List(L)
初始条件:表L存在
操作结果:返回线性表中的所含元素的个数
⑶ 取表元:Get_List(L,i)
初始条件:表L存在且1<=i<=Length_List(L)
操作结果:返回线性表L中的第i个元素的值或地址
⑷ 按值查找:Locate_List(L,x),x是给定的一个数据元素。
初始条件:线性表L存在
操作结果:在表L中查找值为x的数据元素,其结果返回在L中首次出现的值为x的那个元素的序号或地址,称为查找成功; 否则,在L中未找到值为x的数据元素,返回一特殊值表示查找失败。
⑸ 插入操作:Insert_List(L,i,x)
初始条件:线性表L存在,插入位置正确 (1<=i<=n+1,n为插入前的表长)。
操作结果:在线性表L的第 i 个位置上插入一个值为 x 的新元素,这样使原序号为 i , i+1, ... , n 的数据元素的序号变为 i+1,i+2, ... , n+1,插入后表长=原表长+1。
⑹ 删除操作:Delete_List(L,i)
初始条件:线性表L存在,1<=i<=n。
操作结果:在线性表L中删除序号为i的数据元素,删除后使序号为 i+1, i+2,..., n 的元素变为序号为 i, i+1,...,n-1,新表长=原表长-1。
需要说明的是:
1. 某数据结构上的基本运算,不是它的全部运算,而是一些常用的基本的运算,而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。比如线性表的查找在链式存储结构中还会有按序号查找; 再如插入运算,也可能是将新元素x插入到适当位置上等等,不可能也没有必要全部定义出它的运算集,读者掌握了某一数据结构上的基本运算后,其它的运算可以通过基本运算来实现,也可以直接去实现。
2. 在上面各操作中定义的线性表L仅仅是一个抽象在逻辑结构层次的线性表,尚未涉及到它的存储结构,因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法,而算法的实现只有在存储结构确立之后。
2022考研初复试已经接近尾声,考研学子全面进入2023届备考,跨考为23考研的考生准备了10大课包全程准备、全年复习备考计划、目标院校专业辅导、全真复试模拟练习和全程针对性指导;2023考研的小伙伴针也已经开始择校和复习了,跨考考研畅学5.0版本全新升级,无论你在校在家都可以更自如的完成你的考研复习,暑假集训营带来了院校专业初步选择,明确方向;考研备考全年规划,核心知识点入门;个性化制定备考方案,助你赢在起跑线,早出发一点离成功就更近一点!
考研院校专业选择和考研复习计划 | |||
2023备考学习 | 2023线上线下随时学习 | 34所自划线院校考研复试分数线汇总 | |
2022考研复试最全信息整理 | 全国各招生院校考研复试分数线汇总 | ||
2023全日制封闭训练 | 全国各招生院校考研调剂信息汇总 | ||
2023考研先知 | 考研考试科目有哪些? | 如何正确看待考研分数线? | |
不同院校相同专业如何选择更适合自己的 | 从就业说考研如何择专业? | ||
手把手教你如何选专业? | 高校研究生教育各学科门类排行榜 |
相关推荐
跨考考研课程
班型 | 定向班型 | 开班时间 | 高定班 | 标准班 | 课程介绍 | 咨询 |
秋季集训 | 冲刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+专业课1对1+专业课定向辅导+协议加强课程(高定班)+专属规划答疑(高定班)+精细化答疑+复试资源(高定班)+复试课包(高定班)+复试指导(高定班)+复试班主任1v1服务(高定班)+复试面授密训(高定班)+复试1v1(高定班) | |
2023集训畅学 | 非定向(政英班/数政英班) | 每月20日 | 22800起(协议班) | 13800起 | 先行阶在线课程+基础阶在线课程+强化阶在线课程+真题阶在线课程+冲刺阶在线课程+专业课针对性一对一课程+班主任全程督学服务+全程规划体系+全程测试体系+全程精细化答疑+择校择专业能力定位体系+全年关键环节指导体系+初试加强课+初试专属服务+复试全科标准班服务 |