吉林大学：《数据结构》课程电子教案（PPT课件）第三章 线性表

第三章 线 性 表

第三章 线 性 表

3.1 线性表的突义和操作 3.1.1线性表的定义 [例1]英文字母表 (A,B,C,…,Z） [例2]某班学生健康情况登记表。 学号 姓名 性别 年龄 健康情况 01 张军 男 18 一般 02 陈红 女 17 良好 03 陈军 男 19 神经衰弱 … …

3.1 线性表的定义和操作 3.1.1 线性表的定义 [例1] 英文字母表 （ A,B,C,……,Z ) [例2] 某班学生健康情况登记表。 学号 姓名 性别 年龄 健康情况 01 张军 男 18 一般 02 陈红 女 17 良好 03 陈军 男 19 神经衰弱 … … … … …

●线性表定义： 线性表是n>=0个数据元素al,a2,, an的有限序列，表中每个元素，除首元素和 尾元素外，有且仅有一个直接前趋和直接后继。 表中的元素个数定义为线性表的长度。 线性表记为 (al,a2,,an)n<>0 1（) n=0 ●线性表的逻辑结构：是线性结构

● 线性表定义： 线性表是 n>=0 个数据元素 a1，a2，…， an 的有限序列，表中每个元素，除首元素和 尾元素外，有且仅有一个直接前趋和直接后继。 表中的元素个数定义为线性表的长度。 ● 线性表的逻辑结构：是线性结构。 线性表记为 (a1, a2, …, an) n0 ( ) n = 0

3.1.2线性表的操作 (1)随机存取：存取下标为k的结点，返回该结 点的元素值。 (2)插入：在下标为k的结点前（或后）插入一 个新结点 (3)删除：删除下标为k的结点。 (4)查找：寻觅具有特定域值的结点。 (5)归并、分拆、复制、计数、排序

3.1.2 线性表的操作 （1）随机存取：存取下标为k的结点，返回该结 点的元素值。 （2）插入：在下标为k的结点前（或后）插入一 个新结点 （3）删除：删除下标为k的结点。 （4）查找：寻觅具有特定域值的结点。 （5）归并、分拆、复制、计数、排序

3.2 幾性表的顺序表示和实现 3.2.1顺序表 线性表 顺序存储 存储结构 非顺序存储—链表 。顺序表：用顺序存储方法存储的线性表叫顺 序表

3.2 线性表的顺序表示和实现 3.2.1 顺序表 ● 顺序表：用顺序存储方法存储的线性表叫顺 序表。 线性表 存储结构 顺序存储 非顺序存储——链表

●顺序存储：用一组连续的存储空间依次存储 线性表的元素。 。特点：其逻辑顺序与物理顺序相同。 ●注意：顺序表是顺序存储，随机存取。 实现顺序存储的最有效方法是使用一维数组。 [例]：线性表(ao,a1,…,an-1)

● 顺序存储：用一组连续的存储空间依次存储 线性表的元素。 ● 特点：其逻辑顺序与物理顺序相同。 ● 注意：顺序表是顺序存储，随机存取。 实现顺序存储的最有效方法是使用一维数组 。 [例] ：线性表（a0，a1 ，… , an-1 )

b ao 0 b+c a 1 b+i*c a i b+(n-1)*c an-1 n-1 空闲区 Loc(a[i])=Loc (a[O])+i*c

Loc(a[i])= Loc (a[0]) + i*c a0 a1 an-1 ai b+c b+i*c b b+(n-1)*c … … 0 1 n-1 i 空闲区

3.2.2 顺序表上实现的基本运 1、插入 [例]在顺序表(12,13,21,24,28,30,42,77) 中，插入元素25

3.2.2 顺序表上实现的基本运算 1、插入 [例] 在顺序表（12,13,21,24,28,30,42,77） 中，插入元素 25

序号 元素 序号 元素 1 12 1 12 2 13 2 13 3 21 3 21 插入25 4 24 4 24 5 28 5 25 6 30 6 28 7 42 7 30 8 77 8 42 9 77

序号 元素 3 4 1 5 2 7 8 6 12 13 21 24 28 30 42 77 插入25 序号 元素 3 4 1 5 2 7 8 6 12 13 25 21 24 28 30 42 9 77

2、删除 [例]在顺序表(12,13,21,24,28,30,42,77) 中，删除元素24

2、删除 [例] 在顺序表（12,13,21,24,28,30,42,77） 中，删除元素 24