教案 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 回它的后继，否则操作失败，next e无定义 ListInsert(&L,i,e) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1 操作结果：在L中第ⅰ个位置之前插入新的数据元素e,L的长度加1 ListDelete(&L.i.&e) 初始条件：线性表L己存在，I≤i≤ListLength(L) 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 ListTraverse(L.visit()) 初始条件：线性表L己存在 操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败， 则操作失败 ADT List 2.1.2基于ADT List的算法设计 1、例2-1 假设利用两个线性表La和Lb分别表示两个集合A和B(即：线性表中的数据元素即为集 合中的成员)，现要求一个新的集合A=AUB。 【设计思路】 输入：线性表La、线性表Lb 输出：变化了的La →union(&LaLb) 处理方法：上述问题相当于：扩大线性表L,将存在于线性表b中而不存在于线性表La 中的数据元素插入到线性表La中去。 步骤： 1.从线性表LB中依次取得每个数据元素； 2.依值在线性表LA中进行查访： 3.若不存在，则插入之。 【算法2.1】 void union(List &La,List Lb){ ∥将所有在线性表Lb中但不在La中的数据元素插入到La中 La len=ListLength(La); Lb len ListLength(Lb); ∥求线性表的长度 for(i=1;i<=Lb len;i+){ GetElem(Lb,i,e); ∥取b中第i个数据元素赋给e if(!LocateElem(La,e,equal)) ListInsert(La,+La len,e;∥La中不存在和e相同的数据元素，则插入之 }/∥union 【性能分析】 时间复杂度：O(ListLength(La)×ListLength(Lb)(视GetElem和在表尾的插入操作为单位时 间) 【思考】 1、算法设计：已知集合B,试构造集合A,要求集合A中只包含B中所有值不相同的数 据元素。 方法1：InitList(&La,union(&La,Lb): 时间复杂度：O2(ListLength(Lb) 方法2：排序，删除 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第2页程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 2 页 第 2 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 回它的后继，否则操作失败，next_e 无定义 ListInsert(&L, i, e) 初始条件：线性表 L 已存在，1≤i≤ListLength(L)+1 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 ListDelete(&L, i, &e) 初始条件：线性表 L 已存在，1≤i≤ListLength(L) 操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 ListTraverse(L, visit( )) 初始条件：线性表 L 已存在 操作结果：依次对 L 的每个数据元素调用函数 visit( )。一旦 visit( )失败， 则操作失败 }ADT List 2.1.2 基于 ADT List 的算法设计 1、例 2-1 假设利用两个线性表 La 和 Lb 分别表示两个集合 A 和 B（即：线性表中的数据元素即为集 合中的成员），现要求一个新的集合 A＝A∪B。 【设计思路】 输入：线性表 La、线性表 Lb 输出：变化了的 La ➔union(&La, Lb) 处理方法：上述问题相当于：扩大线性表 La，将存在于线性表 Lb 中而不存在于线性表 La 中的数据元素插入到线性表 La 中去。 步骤： 1．从线性表 LB 中依次取得每个数据元素; 2．依值在线性表 LA 中进行查访; 3．若不存在，则插入之。 【算法 2.1】 void union(List &La, List Lb) { // 将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 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)) ListInsert(La, ++La_len, e); // La 中不存在和 e 相同的数据元素，则插入之 } } // union 【性能分析】 时间复杂度：O(ListLength(La)×ListLength(Lb)) (视 GetElem 和在表尾的插入操作为单位时 间) 【思考】 1、算法设计：已知集合 B，试构造集合 A，要求集合 A 中只包含 B 中所有值不相同的数 据元素。 方法 1：InitList(&La); union(&La, Lb); 时间复杂度：O2 (ListLength(Lb) 方法 2：排序，删除