数据结构第二章线性表.ppt

第二章线性表
线性结构的特点:
在数据元素的有限集合中:
存在唯一的一个被称作“第一个”的数据元素
存在唯一的一个被称作“最后一个”的数据元素
除第一个外,集合中的每个数据元素均只有一个前驱
除最后一个外,集合中的每个数据元素均只有一个后继
线性表的类型定义
线性表类型的实现
链式存储
一元多项式的表示
线性表类型的实现
顺序存储
小结及****题

定义:一个线性表是n个数据元素的有限序列
例1 英文字母表(A,B,C,……,Z)是一个线性表
例2
数据元素
特征:
元素个数n(n≥0) 称为表长度,n=0空表
1<i<n时
ai的直接前驱是ai-1,a1无直接前驱
ai的直接后继是ai+1,an无直接后继
元素同构(属于同一数据对象),且不能出现缺项
↓
记录→文件
抽象数据类型线性表的定义如下:
ADT List {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
{ 其中n 为线性表的表长; }
数据关系:
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( ))
引用型操作: