第02章 节 线性表 数据结构 （第二版）.ppt

第二章线性表
线性表及其基本运算
线性表的顺序存储结构
线性表的链式存储结构
线性表的逻辑结构、物理结构,以及它们之间的相互关系;
定义与之相适应的运算;
设计相应的算法;
分析算法的效率。
一、线性表(linear_list)
线性表是n个数据元素的有限序列,记为:
L=(a1,a2, …,an)
线性表及其基本运算
数据元素之间的关系是:
ai-1领先于ai,ai领先于ai+1。
称ai-1是ai的直接前驱元素;ai+1是ai的直接后继元素。
除a1外,每个元素有且仅有一个直接前驱元素,
除an外,每个元素有且仅有一个直接后继元素。
线性表中数据元素的个数n(n>=0)称为线性表的长度,
当n=0时,称为空表。
线性表及其基本运算
线性表是最常用且最简单的一种数据结构,
它的形式化定义为: linear_list=(D,R)
其中,D={ai| ai ∈DO,i=1,2,...,n,n>=0}
R={N},N={<ai-1, ai>|ai-1, ai∈D0,i=2,3,...,n}
D0为某个数据对象,
N是一个序偶的集合,它表示线性表中数据元素之间的相邻关系。
线性表及其基本运算
二. 基本运算
INITIATE(L) 初始化操作设定一个空的线性表L
LENGTH(L) 求长度函数值为L中数据元素的个数
GET(L,i) 取元素函数 1<=i<=LENGTH(L)时返回L中第i个数据元素,否则为空元素NULL。 i称为该数据元素在L中的位序
PRIOR(L,elm) 求前驱函数 elm为L中的一个数据元素,若它的位序大于1,则函数值为elm前驱,否则为NULL
NEXT(L,elm) 求后继函数 若elm的位序小于表长, 则函数值为elm的后继,否则为NULL
线性表及其基本运算
LOCATE(L,x) 定位函数给定值x,若x不在表中,
则返回0,否则,返回x在表中第一次出现时的位序
INSERTE(L, i , b)前插操作在第i个元素之前插入新元素b,i 的取值范围为:1<=i<=n+1;i =n+1表示在表尾插入, n为表长
DELETE(L,i) 删除操作删除线性表L中的第i个元素, 1<=i<=n
EMPTY(L) 判空表函数 若L为空表,则返回布尔值“true”,否则返回布尔值“false”
CLEAR(L) 表置空操作将L置为空表
线性表的顺序存储结构
一、顺序存储结构
用一组地址连续的存储单元依次存储线性表的元素。设线性表的每个元素占用k个存储单元,则第i个元素ai 的存储位置为:Loc(ai)=Loc(a1)+(i-1)*k 其中,Loc(ai)为线性表的起址。
a1
a2
ai
an
b
b+k
b+(i-1)k
b+(n-1)k
线性表的顺序存储结构
线性表顺序存储结构的定义为:
CONST maxlen=线性表可能达到的最大长度;
TYPE sqlisttp=RECORD
elem:ARRAY[1..maxlen] OF elemtp;
last:0..maxlen
END
在上述描述中,线性表的顺序存储结构是一个记录型的结构。
其中,数据域 elem描述了线性表中的DE占用的数组空间,
数组的第i个分量为线性表中第i 个DE的存储映象;
数据域 last指示最后一个DE在数组空间中的位置,也是表长。
线性表的顺序存储结构
二. 插入和删除操作
1. 插入运算 INSERT(L, i, b)
插入前:L=(a1, ... , ai-1, ai, ... ,an)
插入后:L=(a1, ... , ai-1, b, ai, ... ,an )
算法思想:
①进行合法性检查,1<=i<=n+1;
②判断线性表是否已满;
③将第n个至第i个元素逐一后移一个单元;
④在第i个位置处插入新元素;
⑤将表的长度加1。