数据结构 线性表.ppt

第二章线性表
线性结构的基本特征为:
线性结构是
一个数据元素的有序(次序)集
线性表是一种最简单的线性结构
“第一元素”;
“最后元素”;
,均有唯一的后继;
,均有唯一的前驱。
元素之间是一对一的关系
线性表的类型定义
线性表类型的实现
链式映象
一元多项式的表示
线性表类型的实现
顺序映象

线性表的类型定义
线性表的类型定义
线性表举例:
字母表(A,B,C,…,X,Y,Z)
数据序列(6,17,28,50,92,188)
n个元素的线性表:(相邻元素之间存在序偶关系)
(a1, a2 ,…, ai, ai+1, …, an)
第一个元素
(没有前驱)
第i个元素
(有唯一的前驱
和唯一的后继)
最后一个元素
(没有后继)
抽象数据类型线性表的定义如下:
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
InitList( &L )
操作结果:
构造一个空的线性表L。
初始化操作
结构销毁操作
DestroyList( &L )
初始条件:
操作结果:
线性表 L 已存在。
销毁线性表 L。
ListEmpty( L )
ListLength( L )
PriorElem( L, cur_e, &pre_e )
NextElem( L, cur_e, &next_e )
GetElem( L, i, &e )
LocateElem( L, e, compare( ) )
ListTraverse(L, visit( ))
引用型操作: