山东理工大学：《数据结构》课程教学课件（数学）CH2 线性表

第二章线性表

线性结构的特点： 在数据元素的有限集合中： 。存在唯一的一个被称作“第一个”的数据元素 。存在唯一的一个被称作“最后一个”的数据元素 。除第一个外，集合中的每个数据元素均只有一个前驱 。除最后一个外，集合中的每个数据元素均只有个后继

线性结构的特点： 在数据元素的有限集合中： l 存在 的一个被称作“ ”的数据元素 l 存在 的一个被称作“ ”的数据元素 l 除第一个外，集合中的每个数据元素均 l 除最后一个外，集合中的每个数据元素均

2.1线性表的类型定义 2.2线性表类型的实现 一顺序映象 2.3线性表类型的实现 一链式映象 2.4一元多项式的表示 2.5小结及习题

2.1 线性表的类型定义 2.3 线性表类型的实现  链式映象 2.4 一元多项式的表示 2.2 线性表类型的实现  顺序映象 2.5 小结及习题

2.1 线性表的奏型定义

●定义：一个线性表是n个数据元素的有限序列 如(a1,a2.,a,.an) 例1英文字母表（A,B,C,.,Z)是一个线性表 例2 学号 姓名 年龄 数据元素 001 张三 18 002 李四 19 记录→文件 ●特征： ◆元素个数n(n≥0)称为表长度，n=0空表 ◆1<i<n时 ◆a的直接前驱是a,a无直接前驱 ◆a的直接后继是a,a无直接后继 ◆元素同构（属于同一数据对象），且不能出现缺项

l 定义：一个线性表是n个数据元素的有限序列   i n a , a   , a ,   a 如 1 2 , 例1 英文字母表（A,B,C,.,Z)是一个线性表 例2 学号 姓名 年龄 001 张三 18 002 李四 19 . . . 数据元素 l特征： u元素个数n(n≥0) 称为表长度，n=0空表 u 1<i<n时 u ai的直接前驱是ai-1，a1无直接前驱 u ai的直接后继是ai+1，an无直接后继 u元素同构（属于同一数据对象），且不能出现缺项 ↓ 记录→文件

抽象数据类型线性表的定义如下： ADT List{ 数据对象： D={a|a∈ElemSet,.i=l,2,.,n,n≥0} {其中n为线性表的表长；} 数据关系： R1={la-1,a∈D,i=2,n} {设线性表为(a1,a2,··,a,.,an, 称i为a,在线性表中的位序。}

抽象数据类型线性表的定义如下： ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,.,n, n≥0 } { 其中n 为线性表的表长; } 数据关系： R1＝{ |ai-1 ,ai∈D, i=2,.,n } { 设线性表为 (a1，a2 , . . . ，ai，. . . ，an ), 称 i 为 ai在线性表中的位序。}

基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 ADT List

基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 } ADT List

初给化操作 InitList(&L) 操作结果： 构造一个空的线性表L。 回

InitList( &L ) 操作结果： 构造一个空的线性表L。 初始化操作

结构销毀操作 DestroyList(&L) 初始条件：线性表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())

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( )) 引用型操作: