数据结构考研复习之线性表逻辑结构

最后更新时间:2012-04-13 13:07:05
辅导课程:暑期集训 在线咨询
复习紧张,焦头烂额?逆风轻袭,来跨考秋季集训营,帮你寻方法,定方案! 了解一下>>

  线性表的定义

  线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系,数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的,或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的,如学生情况信息表是一个线性表:表中数据元素的类型为学生类型; 一个字符串也是一个线性表:表中数据元素的类型为字符型,等等。

  综上所述,线性表定义如下:

  线性表是具有相同数据类型的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仅仅是一个抽象在逻辑结构层次的线性表,尚未涉及到它的存储结构,因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法,而算法的实现只有在存储结构确立之后。

跨考考研课程

班型 定向班型 开班时间 高定班 标准班 课程介绍 咨询
秋季集训 冲刺班 9.10-12.20 168000 24800起 小班面授+专业课1对1+专业课定向辅导+协议加强课程(高定班)+专属规划答疑(高定班)+精细化答疑+复试资源(高定班)+复试课包(高定班)+复试指导(高定班)+复试班主任1v1服务(高定班)+复试面授密训(高定班)+复试1v1(高定班)
2023集训畅学 非定向(政英班/数政英班) 每月20日 22800起(协议班) 13800起 先行阶在线课程+基础阶在线课程+强化阶在线课程+真题阶在线课程+冲刺阶在线课程+专业课针对性一对一课程+班主任全程督学服务+全程规划体系+全程测试体系+全程精细化答疑+择校择专业能力定位体系+全年关键环节指导体系+初试加强课+初试专属服务+复试全科标准班服务

①凡本网注明“稿件来源:跨考网”的所有文字、图片和音视频稿件,版权均属北京尚学硕博教育咨询有限公司(含本网和跨考网)所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转帖或以其他任何方式复制、发表。已经本网协议授权的媒体、网站,在下载使用时必须注明“稿件来源,跨考网”,违者本网将依法追究法律责任。

②本网未注明“稿件来源:跨考网”的文/图等稿件均为转载稿,本网转载仅基于传递更多信息之目的,并不意味着再通转载稿的观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的“稿件来源”,并自负版权等法律责任。如擅自篡改为“稿件来源:跨考网”,本网将依法追究法律责任。

③如本网转载稿涉及版权等问题,请作者见稿后在两周内速来电与跨考网联系,电话:400-883-2220