1,第二章线性表,信息科学与工程学院网络工程系卫文学,2,知识回顾,3,线性结构的基本特征为:,3.除最后元素在外，均有唯一的后继；,4.除第一元素之外，均有唯一的前驱。,在数据元素的非空有限集中,线性表是一种最简单的线性结构。（a1,a2,a3,ai,an）,1.集合中必存在唯一的一个“第一元素”；,2.集合中必存在唯一的一个“最后元素”；,线性表,4,2.1线性表的类型定义,5,抽象数据类型线性表的定义如下：,ADTList,数据对象：,Dai|aiElemSet,i=1,2,.,n,n0称n为线性表的表长;称n=0时的线性表为空表。,数据关系：,R1|ai-1,aiD,i=2,.,n,设线性表为(a1，a2,.，ai，.，an),称i为ai在线性表中的位序。,6,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADTList,7,2.2线性表类型的实现-顺序映象,8,最简单的一种顺序映象方法是：令y的存储位置和x的存储位置相邻。,顺序映象,以x的存储位置和y的存储位置之间某种关系表示逻辑关系。,9
