第2章 线性表.ppt

第2章线性表
主要内容:





11/10/2017
1
计算机教研室
线性表是一种最简单的线性结构
线性结构的基本特征为:
线性结构是一个数据元素的有序(次序)集
“第一元素”;
“最后元素”;
,均有唯一的后继;
,均有唯一的前驱。
11/10/2017
2
计算机教研室
线形表的类型定义
11/10/2017
3
计算机教研室
抽象数据类型线性表的定义
ADT List {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
{称 n 为线性表的表长; 称 n=0 时的线性表为空表。}
数据关系:
R1={ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n }
{设线性表为(a1,a2, . . . ,ai,. . . ,an), 称
i 为 ai 在线性表中的位序。}
基本操作:
结构初始化操作
结构销毁操作
引用型操作
加工型操作
} ADT List
11/10/2017
4
计算机教研室
初始化操作
InitList( &L )
操作结果:构造一个空的线性表L。
结构销毁操作
DestroyList( &L )
初始条件:线性表 L 已存在。
操作结果:销毁线性表 L。
引用型操作
ListEmpty( L )
初始条件:线性表L已存在。
操作结果:若L为空表,则返回TRUE, 否则FALSE。
11/10/2017
5
计算机教研室
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无定义。
引用型操作
11/10/2017
6
计算机教研室
GetElem( L, cur_e, &next_e )
初始条件:线性表L已存在, 1≤i≤LengthList(L)
操作结果:用e返回L中第i个元素的值。
LocateElem( L, e, compare( ) )
初始条件:pare( )是元素判定函数。
操作结果:pare( )的元素的位序。
若这样的元素不存在,则返回值为0。
ListTraverse(L, visit( ))
初始条件:线性表L已存在。
操作结果:依次对L的每个元素调用函数visit( )。一旦visit( )失败,则操作失败。
11/10/2017
7
计算机教研室
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。
加工型操作
11/10/2017
8
计算机教研室
例2-1 假设有两个集合A和B分别用两个线性表LA和LB表示(即:线性表中的数据元素即为集合中的成员),现要求一个新的集合
A=A∪B。
上述问题可演绎为,要求对线性表作如下操作:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。
; GetElem(LB, i, e)
; LocateElem(LA, e, equal( ))
,则插入之。 ListInsert(LA, n+1, e)
11/10/2017
9
计算机教研室

void union(List &La, List Lb) {
// 将所有在线性表Lb中但不在La中的数据元素插入到La中
La_len