南京航空航天大学：《数据结构》课程教学资源（PPT课件讲稿）第二章 线性表

教育部—微软精品课程建设项目 第二章线性表 南京航空航天大学数据结构课题组版权所有

第二章 线性表

教育部—微软精品课程建设项 线性表是一种最简单的线性结构 线性结构的基本特征为 线性结构是 个数据元素的有序(次序)集 1.集合中必存在唯一的一个“第一元素”; 2.集合中必存在唯一的一个“最后元素” 3.除最后元素在外,均有唯一的后继 4.除第一元素之外,均有唯一的前驱。 南京航空航天大学数据结构课题组版权所有

线性结构的基本特征为: 1．集合中必存在唯一的一个“第一元素”； 2．集合中必存在唯一的一个 “最后元素” ； 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。 线性结构 是 一个数据元素的有序（次序）集 线性表是一种最简单的线性结构

教育部—微软精品课程建设项目 21线性表的类型定义 2.2线性表类型的实现 顺序映象 23线性表类型的实现 链式映象 24一元多项式的表示 南京航空航天大学数据结构课题组版权所有

2.1 线性表的类型定义 2.3 线性表类型的实现 ⎯ 链式映象 2.4 一元多项式的表示 2.2 线性表类型的实现 ⎯ 顺序映象

教育部—微软精品课程建设项目 2.1 线性表的类型定义 南京航空航天大学数据结构课题组版权所有

2.1 线性表的类型定义

教育部—微软精品课程建设项目 抽象数据类型线性表的定义如下 ADT List i 数据对象 D={a1|a1∈ Elem set,i=1,2,…,n,n>0 {称n为线性表的表长; 称n=0时的线性表为空表。 数据关系 R1={a1,21∈D,i2,…,n 设线性表为a1,a2 n/2 称为a在线性表中的位序。 南京航空航天大学数据结构课题组版权所有

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

教育部—微软精品课程建设项目 基本操作 结构初始化操作 结构销毁操作 引用型操作 加工型操作 3 ADT List 扇京航航天大学数握题组视有

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

教育部—微软精品课程建设项目 初始化操作 Initlist( &l) 操作结果 构造一个空的线性表L。 南京航空航天大学数据结构课题组版权所有

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

教育部—微软精品课程建设项目 结构销毁操作 DestroyList( &L) 初始条件:线性表L已存在 操作结果:销毁线性表L。 南京航空航天大学数据结构课题组版权所有

结构销毁操作 DestroyList( &L ) 初始条件： 操作结果： 线性表 L 已存在。 销毁线性表 L

教育部—微软精品课程建设项目 引用型操作 ListEmpty(L) ListLength(L) Prior Elem( L, cur e, &pre e) NextElem( l, cur e, &next e) GetElem( L, i, &e) LocateElem( L, e, compare() ListTraverse (l, visito) 扇京航航天大学数握常题组版

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) (线性表判空) 初始条件:线性表L已存在 操作结果:若L为空表,则返回 TRUE,否则 FALSE 南京航空航天大学数据结构课题组版权所有

ListEmpty( L ) 初始条件： 操作结果： 线性表L已存在。 若L为空表，则返回 TRUE，否则FALSE。 （线性表判空）