第二章线性表 线性表 顺序表 链表 顺序表与链表的比较
◼ 线性表 ◼ 顺序表 ◼ 链表 ◼ 顺序表与链表的比较
线性表( Linear list) 线性表的定义和特点 ◆定义n(≥0)个数据元素的有限 序列,记作 1929·。·9un a;是表中数据元素,n是表长度 遍历逐项访问: 从前向后从后向前
线性表 (Linear List) ◼ 线性表的定义和特点 ◆ 定义 n（ 0）个数据元素的有限 序列，记作 （a1 , a2 , …, an） ai 是表中数据元素，n 是表长度。 ◆ 遍历 逐项访问： 从前向后 从后向前
线性表的特点 除第一个元素外,其他每一个元素 有一个且仅有一个直接前驱。 除最后一个元素外,其他每一个元 素有一个且仅有一个直接后继
线性表的特点 ◼ 除第一个元素外，其他每一个元素 有一个且仅有一个直接前驱。 ◼ 除最后一个元素外，其他每一个元 素有一个且仅有一个直接后继。 a1 a2 a3 a4 a5 a6
顺序表( Sequential List 顺序表的定义和特点 ◆定义将线性表中的元素相继存放 在一个连续的存储空间中。 ◆可利用一维数组描述存储结构 ◆特点线性表的顺序存储方式 ◆遍历顺序访问,可以随机存取 012345 data253457164809
顺序表 (Sequential List) ◼ 顺序表的定义和特点 ◆ 定义 将线性表中的元素相继存放 在一个连续的存储空间中。 ◆ 可利用一维数组描述存储结构 ◆ 特点 线性表的顺序存储方式 ◆ 遍历 顺序访问, 可以随机存取 25 34 57 16 48 09 0 1 2 3 4 5 data
顺序表的连续存储方式 LOC(= LOC(i-1)+l=a+il 0123456789 a3527 49 18605477834102 a+i i=0 LOC( LOC(i-1)+=a+i*L,i>0
顺序表的连续存储方式 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 l l l l l l l l l l LOC(i) = LOC(i-1)+l = a+i*l LOC(i) = LOC(i-1)+l = a+i*l, i > 0 a, i = 0 a+i*l a