线性表的顺序表示和实现.ppt

线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
一元多项式的表示及相加
第二章 线性表
线性表的顺序表示和实现
线性表是最简单常用的数据结构，顺序存储结构链式存储结构也是应用中最常用的存储方法。这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容：如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构的存储结构和操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常重要，应很好地学****理解和掌握。
线性表的顺序表示和实现
线性表的类型定义
具有相同特性的数据元素的有限序列。
( a1 , …, ai –1 , ai , ai +1 ,…, an )
线性表中的元素个数n称为线性表的长度。
线性表的记号
第i个元素
ai在表中的位序
线性表的顺序表示和实现
线性表的特点
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
线性表的顺序表示和实现
ADT List {
数据对象: D = {ai | ai ElemSet , i=1,2,…,n , n ≥0}
数据关系: R1 = {<ai-1 , ai > | ai-1 , ai D , i=2,…,n}
ADT线性表的定义
基本操作:
InitList ( &L ) //初始化
操作结果:构造一个空的线性表L 。
DestroyList ( &L ) //撤销
初始条件: 线性表L 已存在。
操作结果:销毁线性表L 。
线性表的顺序表示和实现
ClearList ( &L ) //置空
初始条件:线性表L 已存在。
操作结果:将L重置为空表。
ListEmpty ( L ) //判空
初始条件:线性表L 已存在。
操作结果:若L为空表 , 则返回TRUE ,
否则返回FALSE。
ListLength ( L ) //求长
初始条件:线性表L 已存在。
操作结果:返回L中数据元素的个数。
线性表的顺序表示和实现
GetElem( L , i , &e ) //读元素
初始条件: 线性表L 已存在 ,
1≤ i ≤ListLength ( L ) 。
操作结果: 用 e 返回 L 中第 i 个元素的值。
LocateElem ( L , e , compare( ) ) //查找 ( 定位 )
初始条件: 线性表L 已存在, compare( ) 是数据
元素判定函数。
操作结果: 返回 L 中第 1 个与 e 满足关系
compare( )的数据元素的位序, 若这
样的数据元素不存在,则返回值为0 。
线性表的顺序表示和实现
NextElem ( L , cur_ e , &next_e ) //求后继
初始条件: 线性表L 已存在。
操作结果: 若cur_ e 是L的数据元素, 且不是最
后一 个, 则用 next_e返回它的后继,
否则操作失败, next_e无定义。
PriorElem ( L , cur_ e , & pre _e ) //求前驱
初始条件: 线性表L 已存在。
操作结果: 若cur_ e 是L的数据元素, 且不是第
一 个, 则用 pre _e返回它的前驱,
否则操作失败, pre _e无定义。
线性表的顺序表示和实现
ListDelete( &L , i , &e ) //删除
初始条件: 线性表L 已存在且非空 ,
1≤ i ≤ListLength( L ) 。
操作结果: 删除L 的第 i 个数据元素 , 并
用e 返回其值, L的长度减1 。
ListInsert( &L , i , e ) //前插(入)
初始条件: 线