第2章线性表
第2章 线性表
线性结构 线性结构是一个数据元素的有序(次序)集合。 它有四个基本特征: 集合中必存在唯一的一个"第一元素 集合中必存在唯一的一个最后元素 3.除最后元素之外,其它数据元素均有唯一的 "后继"; 4.除第一元素之外,其它数据元素均有唯一的 前驱
线性结构 • 线性结构是一个数据元素的有序（次序）集合。 • 它有四个基本特征： 1．集合中必存在唯一的一个"第一元素" ； 2．集合中必存在唯一的一个"最后元素" ； 3．除最后元素之外，其它数据元素均有唯一的 "后继" ； 4．除第一元素之外，其它数据元素均有唯一的 "前驱"
第一节线性表的类型定义 21.1抽象数据类型线性表的定义 ·通常可以下列n个数据元素的序列表示线性 表( Linear_list)(a 25·9i15=i5=i+15 序列中数据元素的个数n定义为线性表的表长 ·n=0时的线性表被称为空表 ·称i为a在线性表中的位序
第一节 线性表的类型定义 2.1.1 抽象数据类型线性表的定义 • 通常可以下列" n 个数据元素的序列"表示线性 表 (Linear_List) ( a1 , a2 ,...,ai-1 ,ai ,ai+1,...,an ) • 序列中数据元素的个数 n 定义为线性表的表长 • n=0 时的线性表被称为空表 • 称 i 为ai在线性表中的位序
线性表的抽象数据类型的定义 ADT List t 数据对象:D={a1a1∈ Elem Set=1,2…,n,n0} 数据关系:R1={<a1,a1叫a1a1∈D,i=2,,n} 基本操作: {结构初始化} InitList( &L 操作结果:构造一个空的线性表L。 销毁结构} Destroy List(&L 初始条件:线性表L已存在。 操作结果:销毁线性表L
线性表的抽象数据类型的定义 • ADT List { 数据对象：D＝{ai | ai ∈ ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ | ai-1 ,ai∈D, i=2,...,n } 基本操作： {结构初始化} InitList( &L ) 操作结果：构造一个空的线性表 L 。 {销毁结构} DestroyList( &L ) 初始条件：线性表 L 已存在。 操作结果：销毁线性表 L
{引用型操作} ListEmpty( L 初始条件:线性表L已存在。 操作结果:若L为空表,则返回TRUE,否则 返回 FALSE。 ListLength( L 初始条件:线性表L已存在。 操作结果:返回L中元素个数 PriorElem(L, cur 操作结果:若cu已是的数据元素,则用 pree返回它的前驱,否则操作失败,pee无定义。 NextElem( L, cur e, &next e) 初始条件:线性表L已存在。 cu 中的数据元素,则用 next e返回它的后继,否则操作失败, next e无定义
• {引用型操作} ListEmpty( L ) 初始条件：线性表L已存在。 操作结果：若 L 为空表，则返回 TRUE，否则 返回 FALSE。 ListLength( L ) 初始条件：线性表 L 已存在。 操作结果：返回 L 中元素个数。 PriorElem( L, cur_e, &pre_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义。 NextElem( L, cur_e, &next_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义
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 中的元素相比较