例2.1.假设有两个集合A和B分别用两个线 性表LA和LB表示，即线性表中的数据元素即 为集合中的成员。编写一个算法求一个新的集合 A=AUB,即将两个集合的并集放在线性表LC中。 解：算法思想是：扩大线性表LA,将存在于线 性表LB中而不存在于线性表LA中的数据元素插入 到线性表LA中去。只要从线性交LB中依次取得每 个数据元素，并依值在线性表LA中进行查访，若 不存在，则插入到表中。 算法如下：
例2.1 假设有两个集合 A 和 B 分别用两个线 性表 LA 和 LB 表示,即线性表中的数据元素即 为集合中的成员。编写一个算法求一个新的集合 A=A∪B,即将两个集合的并集放在线性表LC中。 解:算法思想是:扩大线性表LA，将存在于线 性表LB中而不存在于线性表LA中的数据元素插入 到线性表LA中去。只要从线性交LB中依次取得每 个数据元素，并依值在线性表LA中进行查访，若 不存在，则插入到表中。 算法如下:
void Union(List&La,List Lb){∥算法2.1 ∥将所有在线性表Lb中但不在La中的数据元素插入到La中 int La len,Lb len,i; ElemType e; La len ListLength(La); ∥求线性表的长度 Lb len ListLength(Lb); for (i=1;i<=Lb len;i++){ GetElem(Lb,i,e); ∥取Lb中第i个数据元素赋给e if(LocateElem(La,e,equal)∥La中不存在和e相同的数据 元素 ListInsert(La,++La len,e)；∥插入 }/∥union 由于LocateElem(LA,c)运算的时间复杂度为 O(ListLength(LA),所以本算法的时间复杂度为： O(ListLength(LA)*ListLength(LB))
void Union(List &La, List Lb) { // 算法2.1 // 将所有在线性表Lb中但不在La中的数据元素插入到La中 int La_len,Lb_len,i; ElemType e; La_len = ListLength(La); // 求线性表的长度 Lb_len = ListLength(Lb); for (i=1; i<=Lb_len; i++) { GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal)) // La中不存在和e相同的数据 元素 ListInsert(La, ++La_len, e); // 插入 } } // union 由 于 LocateElem(LA,e) 运算的时间复杂度为 O(ListLength(LA)), 所以本算法的时间复杂度为: O(ListLength(LA)*ListLength(LB))
2.2线性表的顺序表示和实现 2.2.1线性表的顺序存储结构 顺序存储：把线性表的结点按逻辑顺序依次存放 在一组地址连续的存储单元里。用这种方法存储的 线性表简称顺序表。 顺序存储的线性表的特点： ◆线性表的逻辑顺序与物理顺序一致； ◆数据元素之间的关系是以元素在计算机内“物理位置 相邻”来体现
2.2 线性表的顺序表示和实现 顺序存储 ：把线性表的结点按逻辑顺序依次存放 在一组地址连续的存储单元里。用这种方法存储的 线性表简称顺序表。 顺序存储的线性表的特点： ◆ 线性表的逻辑顺序与物理顺序一致; ◆ 数据元素之间的关系是以元素在计算机内“物理位置 相邻”来体现。 2.2.1 线性表的顺序存储结构
设有非空的线性表：(a1,a2,…an)。顺序存储如图所示。 Loc(a)Loc(a)+(i-1)* a a 在具体的机器环境下：设线性表的每个元素需占用个存储 单元，以所占的第一个单元的存储地址作为数据元素的存 储位置。则线性表中第+1个数据元素的存储位置LOC(a+1) 和第i个数据元素的存储位置LOC(a)之间满足下列关系： LOC(ai+D)=LOC(ai)+l 线性表的第i个数据元素a的存储位置为： LOC(ai)=LOC(a)+(i-1)*
设有非空的线性表：(a1，a2，…an ) 。顺序存储如图所示。 … a1 a2 … ai … an … Loc(a1 ) Loc(a1 )+(i-1)* l 在具体的机器环境下：设线性表的每个元素需占用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的存储 位置，通常称做线性表的起始位置或基地址。 ◆元素在计算机内物理位置相邻来表示线性表中 数据元素之间的逻辑关系。 ◆只要确定了存储线性表的起始位置，线性表中 任一数据元素都可以随机可取，所以线性表的顺 序存储结构是一种随机存取的存储结构
◆LOC(a1 )是线性表的第一个数据元素a1的存储 位置，通常称做线性表的起始位置或基地址。 ◆元素在计算机内物理位置相邻来表示线性表中 数据元素之间的逻辑关系。 ◆只要确定了存储线性表的起始位置，线性表中 任一数据元素都可以随机可取，所以线性表的顺 序存储结构是一种随机存取的存储结构