文档介绍：第二章线性表
线性结构是一个数据元素的有序(次序)集
线性结构的基本特征:
“第一元素”;
“最后元素”;
,均有唯一的后继;
,均有唯一的前驱。
线性表的类型定义
抽象数据类型线性表的定义如下:
ADT List {
数据对象:D={ ai | ai ∈ElemSet, i=1,2,...,n,
n≥0 }
数据关系:R1={ <ai-1 ,ai >|ai-1 ,ai∈D,
i=2,...,n }
基本操作:
{ 初始化}
InitList( &L )
操作结果:构造一个空的线性表L。
{ 结构销毁}
DestroyList( &L )
初始条件:线性表L已存在。
操作结果:销毁线性表L。
{ 引用型操作}
ListEmpty( L )
初始条件:线性表L已存在。
操作结果:若L为空表,则返回TRUE,
否则FALSE。
ListLength( L )
初始条件:线性表L已存在。
操作结果:返回L中元素个数。
GetElem( L, i, &e )
初始条件:线性表L已存在,
1≤i≤LengthList(L)
操作结果:用e返回L中第i个元素的值。
LocateElem( L, e, compare( ) )
初始条件:pare( )
是元素判定函数。
操作结果:返回L中第1个与e满足关系
compare( )的元素的位序。若这样的元
素不存在,则返回值为0。
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无定义。
ListTraverse(L, visit( ))
初始条件:线性表L已存在。
操作结果:依次对L的每个元素调用函数
visit( )。一旦visit( )失败,则操作失败。
{ 加工型操作}
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
例2-1 假设利用两个线性表LA和LB分别表示两个集合A和B(即:线性表中的数据元素即为集合中的成员),现要求一个新的集合A=A∪B。
上述问题等价于:要求对线性表作如下操作:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。
分下列三步进行:
;
;
,则插入之。
用C语言描述得如下算法:
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
算法
例 2-2 已知一个非纯集合 B,试构造集合A,要求集合A中只包含集合B中所有值不相同的数据元素。
解法一:同上例,分别以线性表