A2(线性表顺序存储).ppt

教学目标及要求 教学重点及难点 教学方法 复习 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一 个前驱 除最后一个外，集合中的每个数据元素均只有 一个后继 线性表 实例 线性表的操作 线性表的抽象数据类型 线性表的存储 线性表的顺序存储结构 顺序表： 定义：用一组地址连续的存储单元存放一个线性表叫~ 元素地址计算方法： LOC(ai)=LOC(a0)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 线性表的顺序存储结构 顺序表： 定义：用一组地址连续的存储单元存放一个线性表叫~ 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 特点： 逻辑顺序和物理顺序相同 实现随机存取 实现：可用C语言的一维数组实现 顺序表的实现的运算 插入 顺序表插入实现 删除 顺序表插入实现 查找 顺序存储结构的优缺点 线性表的动态分配顺序存储结构 删除算法 查找算法 小结 线性表的特点 线性表的定义 线性表的顺序存储 作业 作业 * * 线性表的顺序存储 顺序表的操作 线性表的顺序存储 线性表的插入操作 线性表的删除操作 多媒体演示 提问式 教学时数 2 数据类型 算法定义及特点 时间复杂度 ? 注意：线性表是最常用且最简单的一种线性数据结构 ? 线性表定义：由n（n=0）个数据元素组成的有限序 列。其中每个元素，除首元素和尾元素 外，有且仅有一个直接前趋和直接后继。 ? 表中的元素个数定义为线性表的长度。n=0,称为空表。例如：ai是第i个数据元素，i为数据元素ai在线性表中的位置,称i为ai在线性表中的位序 例 英文字母表（A,B,C,…..Z)是一个线性表 例 数据元素 例 英文字母表（A,B,C,…..Z)是一个线性表 插入：在下标为K的结点前（或后）插入一个新结点 删除：删除下标为K的结点。 查找：寻找下标为K的结点，或寻找域值的结点。 ADT List {　数据对象：D＝{ ai | ai ∈ ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ ai-1 ,ai | ai-1 , ai ∈D, i=2,...,n } 基本操作：　InitList( L ) 操作结果：构造一个空的线性表 L 。 　DestroyList( L )　　 初始条件：线性表 L 已存在。 操作结果：销毁线性表 L 。　ListEmpty( L )　　 初始条件：线性表L已存在。　 操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。 ListLength( L )　　初始条件：线性表 L 已存在。 操作结果：返回 L 中元素个数。 GetElem( L, i, e )　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)。　　操作结果：用 e 返回 L 中第 i 个元素的值。 } ADT List …… …… n-1 i …… 3 2 1 an-1 ...... …… ai ……. a3 a2 a1 …… …… 2004 2002 2000 A， B， C， D， E， E， F （ ） 线性表 typedef int DATATYPE; #define M 1000 DATATYPE data[M]; F E E D C B A 5 6 4 3 2 1 0 数组下标 5 6 4 3 2 1 0 元素序号 顺序表 20 男 张军 .. .. .. 18 女 李娟 年龄 性别 姓名 线性表 20 男 张军 18 女 李娟 1 0 数组下标 顺序表 typedef struct student { char name[20]; char sex; int age; }DATATYPE; DATATYPE su[M]; 插入 删除 查找 在顺序表（12,13,21,24,30,77）中，插入元素25。 …… 77 30 24 21 13 12 6 5 4 3 2 1 0 25 插入