GetElem(L, i, &e 初始条件:线性表L已存在,1≤ LengthList(L 操作结果:用e返回L中第i个元素的值 LocateElem(L, e, compare)) 初始条件:线性表L已存在, compare()是元素判定函 数。 操作结果:返回L中第1个与e满足关系 compare() 的元素的位序。若这样的元素不存在,则返回值为0。 ListTraverse(L, visit()) 初始条件:线性表L已存在,vsi()为元素的访问函 数。 操作结果:依次对L的每个元素调用函数vsi()。 旦vist()失败,则操作失败
• GetElem( L, i, &e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)。 操作结果：用 e 返回 L 中第 i 个元素的值。 LocateElem( L, e, compare( ) ) 初始条件：线性表 L 已存在,compare( ) 是元素判定函 数。 操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在，则返回值为0。 ListTraverse(L, visit( )) 初始条件：线性表 L 已存在，visit( ) 为元素的访问函 数。 操作结果：依次对 L 的每个元素调用函数 visit( )。 一旦 visit( ) 失败，则操作失败
加工型操作} ClearList( &L 初始条件:线性表L已存在 操作结果:将L重置为空表。 PutElem(&L.i. &e 初始条件:线性表已存在,1 LengthList(L) 操作结果:L中第i个元素赋值同e的值 ListInsert(&L,i,e 推结集:性第素X期的21 L的长度增1。 ListDelete( &L,i, &e 初始条件:线性表L已存在且非空 1≤ sLengthList(L) 操作结果:删除L的第i个元素,并用e返回其值, L的长度减1。 3 ADT List
• {加工型操作} ClearList( &L ) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 PutElem( &L, i, &e ) 初始条件：线性表L已存在，1≤i≤LengthList(L)。 操作结果：L 中第 i 个元素赋值同 e 的值。 ListInsert( &L, i, e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。 操作结果：在 L 的第 i 个元素之前插入新的元素 e， L 的长度增1。 ListDelete( &L, i, &e ) 初始条件：线性表 L 已存在且非空， 1≤i≤LengthList(L)。 操作结果：删除 L 的第 i 个元素，并用 e 返回其值， L 的长度减1。 } ADT List
212线性表类型的应用 例1已知集合A和B,求两个集合的并集,使A =AUB,且B不再单独存在。 分析以线性表LA和LB分别表示集合A和B, 对集合B中的所有元素一个一个地检查,将存 在于线性表LB中而不存在于线性表LA中的数 据元素插入到线性表LA中去。 具体操作步骤为: 1.从线性表LB中取出一个数据元素 2.依值在线性表LA中进行查询; 3.若不存在,则将它插入到LA中 重复上述三步直至LB为空表止
2.1.2 线性表类型的应用 • 例1 已知集合A 和 B，求两个集合的并集，使A ＝A∪B，且 B 不再单独存在。 • 分析:以线性表 LA 和 LB 分别表示集合 A 和 B， 对集合 B 中的所有元素一个一个地检查，将存 在于线性表 LB 中而不存在于线性表 LA 中的数 据元素插入到线性表 LA 中去。 • 具体操作步骤为： 1．从线性表 LB 中取出一个数据元素； 2．依值在线性表 LA 中进行查询； 3．若不存在，则将它插入到 LA 中。 重复上述三步直至 LB 为空表止
对应的线性表基本操作 1. ListDelete LB,1,e; 2. LocateElem(LA, e, equal); 3. Listinsert( LA, n+, e) void union (List &LA, List &LB) La_|en= ListLength(LA);∥求得线性表LA的长度 whle( ListEmpty(LB))∥依次处理LB中元素直至 LB为空表止 ∥从LB中删除第1个数据元素并赋给e ListDelete (LB, 1, e); ∥当LA中不存在和e值相同的数据元素时进行插入 if ! Elem (LA, e, equal()) ListInsert(LA, ++La len, e); Destroy List(LB) ∥销毁线性表LB }∥ union
• 对应的线性表基本操作： 1. ListDelete( LB, 1, e ); 2. LocateElem( LA, e, equal() ); 3. ListInsert( LA, n+1,e ) • void union(List &LA, List &LB) { La_len = ListLength(LA);// 求得线性表 LA 的长度 while (!ListEmpty(LB)) // 依次处理 LB 中元素直至 LB 为空表止 { // 从 LB 中删除第1个数据元素并赋给 e ListDelete(LB,1,e); // 当LA中不存在和 e 值相同的数据元素时进行插入 if (!LocateElem(LA,e,equal( )) ListInsert(LA,++La_len,e); } DestroyList(LB); // 销毁线性表 LB } // union
例2已知一个“非纯集合”B,试构造一个 集合A,使A中只包含B中所有值各不相 同的数据元素。 分析:将每个从B中取出的元素和已经加入 到集合A中的元素相比较
• 例2 已知一个“非纯集合” B，试构造一个 集合 A，使 A 中只包含 B 中所有值各不相 同的数据元素。 • 分析:将每个从 B 中取出的元素和已经加入 到集合 A 中的元素相比较