线性表的基本操作举例 例2-1求A=A∪BP2O算法2.1 时间复杂度: LocateElemo执行次数 OCListLength()ListLength(B)) 例2-2合并LA和LB到LC中 P20-21算法22 ◆时间复杂度: ListInsert0执行次数 O(ListLength (LA)+ListLength(LB)
线性表的基本操作举例 ◼ 例2-1 求A = A ∪ B P20算法2.1 ◆时间复杂度：LocateElem()执行次数 O(ListLength(A)*ListLength(B)) ◼ 例2-2 合并LA 和 LB 到LC中 P20-21算法2.2 ◆时间复杂度：ListInsert()执行次数 O(ListLength(LA)+ListLength(LB))
2.2线性表的顺序表示和实现 1.顺序表一线性表的顺序存储结构 1)在计算机内存中用一组地址连续的存储单元依次 存储线性表中的各个数据元素 2)假设线性表的每个元素需占用L个存储单元,并以 衢点的第则线性单倍数入乙款存柔蓄始存 Loc(a-l)和第i个数据元素的存储位置Loc(a)之间满足 下列关系: Loc(ai+1) )=Loc(ai)+L 般来说,线性表的第个元素a的存储位置为: Loc(ai)= loc(a,1+(i-1*L 其中Loc(a1)是线性表的第一个数据元素a1的存储位置, 通常称作线性表的起始位置或基地址
2.2 线性表的顺序表示和实现 1.顺序表—线性表的顺序存储结构 1）在计算机内存中用一组地址连续的存储单元依次 存储线性表中的各个数据元素。 2）假设线性表的每个元素需占用L个存储单元，并以 所占的第一个单元的存储地址作为数据元素的起始存 储位置，则线性表中第i+1个数据元素的存储位置 Loc(ai+1)和第i个数据元素的存储位置Loc(ai )之间满足 下列关系： Loc(ai+1) = Loc(ai ) + L 一般来说，线性表的第i个元素ai的存储位置为： Loc(ai ) = Loc(a1 ) + (i-1)*L 其中Loc(a1 )是线性表的第一个数据元素a1的存储位置， 通常称作线性表的起始位置或基地址
1.顺序表一线性表的顺序存储结构 3)线性表的顺序存储结构示意图一一p22图2 ■用“物理位置”相邻来表示线性表中数据元素之间 的逻辑关系。 根据线性表的顺序存储结构的特点,只要确定了存 储线性表的起始位置,线性表中任一数据元素都可 随机存取,所以,线性表的顺序存储结构是一种随 机存取的存储结构
1.顺序表—线性表的顺序存储结构 3）线性表的顺序存储结构示意图——p22图2.2 ◼ 用“物理位置”相邻来表示线性表中数据元素之间 的逻辑关系。 ◼ 根据线性表的顺序存储结构的特点，只要确定了存 储线性表的起始位置，线性表中任一数据元素都可 随机存取，所以，线性表的顺序存储结构是一种随 机存取的存储结构
2.顺序存储线性表的描述 令C语言中静态分配描述p22 # define LIST MAX LENTH100/或者N/或者是一个 数 typedef struct Elem Type int *elem int length ng 3 SqList Sqlist L
#define LIST_MAX_LENTH 100/或者N/或者是一 个 常数 typedef struct ElemType { int *elem; int length; } SqList; SqList L; 2.顺序存储线性表的描述 ❖ C语言中静态分配描述 p22
2.顺序存储线性表的描述 冷C语言中静态分配描述p22 >求置空表 Status ClearList (&L) L length=0 return OK
➢求置空表 Status ClearList( &L ) { L. length=0; return OK; } 2.顺序存储线性表的描述 ❖ C语言中静态分配描述 p22