当前位置:首页 » 数据结构精品文章 » 正文

线性表相关定义和操作

1955 人参与  2018年09月03日 22:32  分类 : 数据结构精品文章  评论

1、线性表的定义?

n个数据元素的有限序列(a1,a2,.,an  

DS  = DR     LIST = DR), 

D={aiai∈数据对象集,i1..n n ³0 } 元素

R={<ai-1, ai >ai-1, aiDi2..n }关系

元素:是相同特性的数据对象

关系:是顺序排列的位置次序

2、线性表的特性有哪些?请举例说明。

线性关系 满足以下4点:

1)有一个头结点, 无前驱(a1);

2)有一个尾结点,无后继(an);

3ak1<k<n )在ak1之后,即akak1的后继;

4akak1之前,即akak1的前驱。

线性、有序——具线性序

例:项链、铁锁链,排队买火车票,单线联系

3、请详细叙述线性表的ADT定义。

ADT  List {

数据对象:D{ai | ai  ElemSet, i=1,2,...,n, n≥0 } 

数据关系:R={<ai-1, ai >ai-1, aiDi2..n }

4、线性表的基本操作有哪些?

{结构初始化} 

{销毁结构}

{引用型操作} 

{加工型操作}

} ADT  List

{结构初始化}

InitList( &L )

操作结果:构造一个空的线性表 L  

{销毁结构}

DestroyList( &L )

初始条件:线性表 L 已存在。

操作结果:销毁线性表 L

{引用型操作} 

v ListEmpty( L )

初始条件:线性表L已存在。

操作结果:若 L 为空表,则返回 TRUE,否则返回 FALSE 

v ListLength( L )

初始条件:线性表 L 已存在。

操作结果:返回 L 中元素个数。 

v PriorElem( L, cur_e, &pre_e )
初始条件:线性表 L 已存在。
操作结果:若 cur_e  L 中的数据元素,则用 pre_e 返回它的前驱,否则操作失败,pre_e 无定义。

v NextElem( L, cur_e, &next_e )
初始条件:线性表 L 已存在。操作结果:若 cur_e  L 中的数据元素,则用 next_e 返回它的后继,否则操作失败,next_e 无定义。 

vGetElem( L, i, &e )
初始条件:线性表 L 已存在,1≤i≤LengthList(L)
操作结果:用 e 返回 L 中第 i 个元素的值。

v LocateElem( L, e, compare( ) )
初始条件:线性表 L 已存在,compare( ) 是元素判定函数。

操作结果:返回 L 中第1个与 e 满足关系compare( )的元素的位序。若这样的元素不存在,则返回值为0

v ListTraverse(L, visit( ))
初始条件:线性表 L 已存在,visit( ) 为元素的访问函数。
操作结果:依次对 L 的每个元素调用函数visit( )。一旦 visit( ) 失败,则操作失败。

{加工型操作} 

v ClearList( &L )

初始条件:线性表 L 已存在。

操作结果:将 L 重置为空表。

v ListInsert( &L, i, e )
初始条件:线性表 L 已存在,1≤i≤LengthList(L)+1
操作结果:在 L 的第 i 个元素之前插入新的元素eL的长度增1

v ListDelete( &L, i, &e )

初始条件:线性表 L 已存在且非空,1≤i≤LengthList(L)

操作结果:删除 L 的第 i 个元素,并用 e 返回其值,L 的长度减1

5、关于线性表的基本操作,应注意哪些问题?

1某数据结构上的基本操作,不是它的全部操作,而是一些常用的基本的操作运算,而每一个基本操作在实现时也可能根据不同的存储结构派生出一系列相关的运算来。

如插入运算,也可能是将新元素x插入到适当位置上等等。

2)不可能也没有必要全部定义出它的运算集,读者掌握了某一数据结构上的基本运算后,其它的运算可以通过基本运算来实现,也可以直接去实现。

3)在上面各操作中定义的线性表L仅仅是一个抽象在逻辑结构层次的线性表,尚未涉及到它的存储结构,因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法,而算法的实现只有在存储结构确立之后。

6、将表中x元换成y元的操作顺序是怎样的

操作顺序

①找到x

②记住位置 

③删去x

④插入y于对应位

利用已知的ADT操作

d=LocateElem(L,x,compare( ))

ListDelete(&L,d,&e)

ListInsert(&L,d,y)

7、已知集合 A  B,求两个集合的并集,使 AAB 

从集合的观点看:只要对集合 B 中的所有元素一个一个地检查,看看在集合 A 中是否存在相同元素,若不存在,则将该元素插入到集合 A,否则舍弃之。 

假设,以线性表 LA  LB 分别表示集合 A  B

对线性表作如下操作:
扩大线性表 LA,将存在于线性表 LB 中而不存在于线性表LA 中的数据元素插入到线性表 LA 中去。

步骤:
 顺序取Lb表中元素 
 依值在La中进行查访;
 若不存在,则插入之。

GetElement( Lb, i, e );LocateElem( La, e, equal ) ListInsert( La, n+1,e ) 
void  union (List &La, List Lb)  {
La_len=ListLength (La) ; Lb_len=ListLength (Lb);
for ( i=1; i<=Lb_len; i++ ){
GetElement (Lb, i, e) ;
if (!LocateElem(La,e,equal)) ListInsert (La,++La_len,e); 
}
}//union


 

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=195

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!