第二章线性表 线性结构的特点是,在数据元素的非空有限集中, )存在唯一的一个被称作“第一个”的数据元素; 2)存在唯一的一个被称作“最后一个”的数据元素; 3)除第一个数据元素之外,集合中的每个数据元素均只有一个直 接前趋数据元素; 4)除最后一个数据元素之外,集合中的每个数据元素均只有一个 直接后继数据元素 2线性表及其基本操作 线性表属线性结构,是最常用且最简单的一种数据结构, 个线性表是n>=0个数据元素a1,a2,…,n的有限序列,表中 每个数据元素,除第一个和最后一个外,有且仅有一个直接前 趋和一个直接后继
第 二 章 线 性 表 线性结构的特点是, 在数据元素的非空有限集中, 1) 存在唯一的一个被称作“第一个”的数据元素; 2) 存在唯一的一个被称作“最后一个”的数据元素; 3) 除第一个数据元素之外, 集合中的每个数据元素均只有一个直 接前趋数据元素; 4) 除最后一个数据元素之外, 集合中的每个数据元素均只有一个 直接后继数据元素. 2 .1 线性表及其基本操作 线性表属线性结构, 是最常用且最简单的一种数据结构, 一 个线性表是n>=0个数据元素 a a a n , , , 1 2 的有限序列, 表中 每个数据元素, 除第一个和最后一个外, 有且仅有一个直接前 趋和一个直接后继
线性表的形式化定义:含有n个数据元素的线性表是一个 数据结构 Liner list=(DR),其中: Di=1 R 23. D为某个数据对象 解读线性表的形式化定义,可得如下注意点 1)同一个线性表中的数据元素必定具有相同特性,即应属于 同一数据对象; 2)关系N是一个序偶的集合,表示线性表中数据元素之间的 相邻关系,即a领先于a,4领先41+1,依此类推.称a1-1 是a的直接前趋元素,a1是a的直接后继元素 3)线性表中数据元素的个数n(n≥0)定义为线性表的长度,当 n=0时称为空表,n>0时,线性表通常记为
线性表的形式化定义: 含有n个数据元素的线性表是一个 数据结构 Liner _list = (D,R) , 其中: R N N a a a a D i n D a a D i n n i i i i i i , , , , 2,3, , , 1,2, , , 0 1 1 0 0 = = = = = − − D0 为某个数据对象. 解读线性表的形式化定义, 可得如下注意点: 1)同一个线性表中的数据元素必定具有相同特性, 即应属于 同一数据对象; 2)关系N是一个序偶的集合,表示线性表中数据元素之间的 相邻关系, 即 ai−1 领先于 ai ai , 领先 ai+1 ,依此类推. 称 ai−1 是 ai 的直接前趋元素, ai+1 是 ai 的直接后继元素. 3)线性表中数据元素的个数 n(n 0) 定义为线性表的长度,当 n = 0 时称为空表, n 0 时,线性表通常记为: ( , , , , , ) a1 a2 ai a n
4线性表中的每一个数据元素,视不同情况,可以是一个 数、一个符号,也可以是一页书,甚至为其它更复杂的 信息.当一个数据元素由若干项数据项组成时,可把数 据元素称为记录 (record)或结点(node),含有大量记录的 线性表又叫文件(file) 对线性表的常用操作可见教材P11,本章主要讨论插入和 删除这两种基本操作.为对线性表的操作而编制的具体程 序,随线性表存储结构的不同而不同 2.2线性表的顺序存储结构 221顺序存储结构 定义:用一组地址连续的存储单元对线性表中的数 据元素按照其逻辑次序依次存放的存储结构 叫顺序存储结构,此时的线性表叫顺序表
4)线性表中的每一个数据元素, 视不同情况, 可以是一个 数﹑一个符号, 也可以是一页书, 甚至为其它更复杂的 信息. 当一个数据元素由若干项数据项组成时, 可把数 据元素称为记录(record)或结点(node), 含有大量记录的 线性表又叫文件(file). 对线性表的常用操作可见教材P.11, 本章主要讨论插入和 删除这两种基本操作. 为对线性表的操作而编制的具体程 序, 随线性表存储结构的不同而不同. 2 .2 线性表的顺序存储结构 2.2.1顺序存储结构 定义: 用一组地址连续的存储单元对线性表中的数 据元素按照其逻辑次序依次存放的存储结构 叫顺序存储结构, 此时的线性表叫顺序表
如果线性表中各数据元素只占用一个存储单元,则顺序表 的存储形式可用下图表示,从下图可知,线性表的第i 存储地址内容结点序号个数据元素即结点)的存储地 址为: L+1 LOC(a)=lOC(a+(i-1) 上式中LOC(a1)为第一个数 L+(i-1) 据元素的存储地址,推广到 般情况,如每个数据元素 L+n-1 占用c个存储单元,则第i 个数据元素的存储地址为:OC(a1)=DOC(a1)+(t-1)×C 上式中LOC(a1)第一个数据元素所占用的C个存储单元 的第一个单元的存储地址.称上两式中的LOC(a1)为线性 表的基地址.如用C语言中的数组表示线性表 100 并假设表中所有元素均为整形,则在主程序中可作如下说明
如果线性表中各数据元素只占用一个存储单元, 则顺序表 的存储形式可用下图表示, 存储地址 1 ( 1) 1 + − + − + L n L i L L 结点序号 n i 2 1 n i a a a a 2 1 内容 从下图可知, 线性表的第 i 个数据元素(即结点) 的存储地 址为: ( ) ( ) ( 1) LOC ai = LOC a1 + i − 上式中 ( ) LOC a1 为第一个数 据元素的存储地址, 推广到 一般情况, 如每个数据元素 占用 c 个存储单元, 则第 i 个数据元素的存储地址为: LOC(ai ) = LOC(a1 ) + (i −1) c 上式中 ( ) LOC a1 为第一个数据元素所占用的 c 个存储单元 的第一个单元的存储地址. 称上两式中的 ( ) LOC a1 为线性 表的基地址. 如用C语言中的数组表示线性表 ( , , , , , ) a1 a2 ai a100 并假设表中所有元素均为整形, 则在主程序中可作如下说明:
#define maXsize 101 int VIMAXSIZEI; 因为C语言中数组下标的下界是0,有时为讨论问题方便起 见,下标为0的单元空置不用,数组长度为线性表实际长度 加1,故有上述说明 由前面给出的地址公式,一旦基地址和一个数据元素 占用存储单元的大小确定,就可求出任一个数据元素的起 始地址,因此,顺序表便于进行随机访问,是一种随机存 取结构 222顺序表的插入和删除 插入和删除是对顺序表的基本操作(运算) 顺序表的插入 线性表的插入运算是指在第i个数据元素和第i-1个数据 元素之间插入一个新的数据元素x,它的结果使线性表的长 度由n变为n+1,而根据线性表在顺序存储结构下的特点,在 插入一个新数据元素之后,线性表的逻辑关系发生了变化
#define MAXSIZE 101 int v[MAXSIZE]; 因为C语言中数组下标的下界是0, 有时为讨论问题方便起 见, 下标为0的单元空置不用, 数组长度为线性表实际长度 加1, 故有上述说明. 由前面给出的地址公式, 一旦基地址和一个数据元素 占用存储单元的大小确定, 就可求出任一个数据元素的起 始地址, 因此, 顺序表便于进行随机访问, 是一种随机存 取结构. 2.2.2 顺序表的插入和删除 插入和删除是对顺序表的基本操作(运算). 一﹑ 顺序表的插入 线性表的插入运算是指在第i个数据元素和第i -1个数据 元素之间插入一个新的数据元素x, 它的结果使线性表的长 度由n变为n+1, 而根据线性表在顺序存储结构下的特点,在 插入一个新数据元素之后, 线性表的逻辑关系发生了变化