第2章线性表 主要内容: 1.线形表的类型定义 2.线形表的顺序表示和实现 3.线形表的链式表示和实现 4.有序表 5.顺序表和链表的综合比较 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第2章线性表 胡建华 2021/2/19 计算机教研室 第 1 页 第 2 章 线性表 主要内容： 1．线形表的类型定义 2．线形表的顺序表示和实现 3．线形表的链式表示和实现 4．有序表 5．顺序表和链表的综合比较
@线性表是一种最简单的线性结构 ·线性结构的基本特征为: ·线性结构是一个数据元素的有序(次序)集 集合中必存在唯一的一个“第一元素” 2.集合中必存在唯一的一个“最后元素 3.除最后元素在外,均有唯一的后继; 4.除第一元素之外,均有唯一的前驱。 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第2页 线性表是一种最简单的线性结构 • 线性结构的基本特征为: • 线性结构是一个数据元素的有序（次序）集 1．集合中必存在唯一的一个“第一元素” ； 2．集合中必存在唯一的一个 “最后元素” ； 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱
21线形表的类型定义 计算机教研宦 第3页 2021/2/19
Data Structure 数据结构—— 第2章线性表 胡建华 2021/2/19 计算机教研室 第 3 页 2.1 线形表的类型定义
抽象数据类型线性表的定义 ADT List 数据对象: D={a1|a1∈ ElemNet,i=1,2,,n,n≥0} 称n为线性表的表长;称n=0时的线性表为空表。} 数据关系: R1={<a i-1,ai a i-1 a:∈D n 设线性表为(a1,a2, a 称 i为a1在线性表中的位序。} 基本操作: 结构初始化操作 结构销毁操作 引用型操作 加工型操作 AdT List 计算机教研室 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第4页 抽象数据类型线性表的定义 ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长; 称 n=0 时的线性表为空表。} 数据关系： R1＝{ |ai-1 ,ai∈D, i=2,...,n } {设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。} 基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 } ADT List
初始化操作 InitList(& 操作结果:构造一个空的线性表L。 结构销毁操作 DestroyList(&L 初始条件:线性表L已存在。 操作结果:销毁线性表L。 引用型操作 ListEmpty(L) 初始条件:线性表L已存在。 操作结果:若L为空表,则返回TRUE, 否则 fAlse。 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第5页 初始化操作 InitList( &L ) 操作结果：构造一个空的线性表L。 结构销毁操作 DestroyList( &L ) 初始条件：线性表 L 已存在。 操作结果：销毁线性表 L。 引用型操作 ListEmpty( L ) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE， 否则FALSE
@引用型操作 ListLength (L) 初始条件:线性表L已存在 操作结果:返回L中元素个数。 PriorElem(L, cur e, &pre e) 初始条件:线性表L已存在 的操作结果:若ure是L的元素,但不是第一个,则用ree返回它 的前驱,否则操作失败,pree无定义。 NextElem l, cur e, &next e) 意初始条件:线性表L已存在。 操作结果:若cure是L的元素,但不是最后一个,则用 next e返回 表它的后继,否则操作失败, next e无定义。 计算机教研宦 第6页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第6页 •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, cur e, &next e) 初始条件:线性表L已存在,1≤i≤ LengthList(L 操作结果:用e返回L中第个元素的值 .LocateElem( L, e, compare()) 初始条件:线性表已存在, compare()是元素判定函数 操作结果:返回中第1个与e满足关系 compare()的元素的位序。 若这样的元素不存在,则返回值为0。 Listtraverse l, visito) 意初始条件:线性表L已存在。 线操作结果:依次对L的每个元素调用函数 visit()。一且 visit()失败,则操作失败。 计算机教研宦 第7页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第7页 •GetElem( L, cur_e, &next_e ) 初始条件：线性表L已存在， 1≤i≤LengthList(L) 操作结果：用e返回L中第i个元素的值。 •LocateElem( L, e, compare( ) ) 初始条件：线性表L已存在，compare( )是元素判定函数。 操作结果：返回L中第1个与e满足关系compare( )的元素的位序。 若这样的元素不存在，则返回值为0。 •ListTraverse(L, visit( )) 初始条件：线性表L已存在。 操作结果：依次对L的每个元素调用函数visit( )。一旦 visit( )失败，则操作失败
⑨加工型操作 ClearList(&L) 初始条件:线性表L已存在 操作结果:将L重置为空表 PutElem( L, i, &e) 初始条件:线性表已存在,1≤i≤ LengthList(L) 操作结果:L中第i个元素赋值同e的值。 ListInsert(&L 初始条件:线性表L已存在,1≤i≤ LengthList〔L)+1 操作结果:在的第个元素之前插入新的元素e,L的长度增1 意· ListDelete(&L,i,&e) 初始条件:线性表L已存在且非空,1≤i≤ LengthList①L) 操作结果:删除L的第i个元素,并用e返回其值,L的长度减1 计算机教研宦 第8页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第8页 • 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。 加工型操作
8例2-1假设有两个集合A和B分别用两个线性表LA和B表示(即:线 性表中的数据元素即为集合中的成员),现要求一个新的集合 A=A∪B 上述问题可演绎为,要求对线性表作如下操作:扩大线性表LA,将 存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表 LA中去。 宫1.从线性表LB中依次取得每个数据元素; GetElem(LB,i,e) 意2·依值在线性表LA中进行查访; LocateElem(LA,e, equal() 3.若不存在,则插入之。 ListInsert(LA,n+1,e) 计算机教研宦 第9页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第9页 例2-1 假设有两个集合A和B分别用两个线性表LA和LB表示（即：线 性表中的数据元素即为集合中的成员），现要求一个新的集合 A＝A∪B。 上述问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将 存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表 LA中去。 1．从线性表LB中依次取得每个数据元素; GetElem(LB, i, e) 2．依值在线性表LA中进行查访; LocateElem(LA, e, equal( )) 3．若不存在，则插入之。 ListInsert(LA, n+1, e)
◎算法2.①③④③②④⑤ void union List &La, List Lb)i //将所有在线性表Lb中但不在La中的数据元素插入到La中 La len ListLength (La) Lb1en= ListLength (Lb);//求线性表的长度 for (i= 1: i<= Lb len; i++)i GetElem(Lb, i, e) //取Lb中第i个数据元素赋给e if(! LocateElem(La, e, equal()) ListInsert(La, ++La len, e) //La中不存在和e相同的数据元素,则插入之 / union 计算机教研宦 第10页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第10页 算法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 1 3 4 8 2 4 5 La Lb