山东第一医科大学（泰山医学院）：《数据结构》课程教学资源（PPT课件）第2章 线性表

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

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

§2.1线性表的类型定义 ★定义：一个线性表是个数据元素的有限序列 如（a1,a2,..,ai, 例英文字母表（A,B,C,.…是一个线性表 例 学号 姓名 年龄 数据元素 001 张三 18 002 李四 19 ★特征： 必元素个数n一表长度，n=0空表 1<i<n时 ●a的直接前驱是a.1,a1无直接前驱 ●a的直接后继是a+1,an无直接后继 必元素同构，且不能出现缺项

§2.1 线性表的类型定义 定义：一个线性表是n个数据元素的有限序列 如 (a 1 , a 2 ,……, a i , ……a n ) 例 英文字母表（A,B,C,…..Z)是一个线性表 例 学号 姓名 年龄 001 张三 18 002 李四 19 …… …… …… 数据元素 特征： ❖元素个数n—表长度，n=0空表 ❖1<i<n时 ⚫ai的直接前驱是ai-1，a1无直接前驱 ⚫ai的直接后继是ai+1，an无直接后继 ❖元素同构，且不能出现缺项

抽象数据类型线性表的定义如下： ADT List{ 数据对象： D={a:la:∈ElemSet,i=l,2,,n,n≥0} {称n为线性表的表长； 称=0时的线性表为空表。}

抽象数据类型线性表的定义如下： ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长; 称 n=0 时的线性表为空表。}

数据关系： R1={la-1,a∈D,i=2,,n} {设线性表为(a1,a2, 称i为a在线性表中的位序}

数据关系： 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) GetElem(L,i,&e) 2 LocateElem(L,e,compare()) PriorElem(L,cur_e,&pre_e NextElem(L,cur e,&next e ListTraverse(L,visit())

ListEmpty( L ) ListLength( L ) PriorElem( L, cur_e, &pre_e ) NextElem( L, cur_e, &next_e ) ListTraverse(L, visit( )) 引用型操作: GetElem( L, i, &e ) LocateElem( L, e, compare( ) )

加工型操作 ClearList(&L) ListInsert(&L,i,e) ListDelete(&L,i,&e)

加工型操作 ClearList( &L ) ListInsert( &L, i, e ) ListDelete(&L, i, &e)

例2-1假设有两个集合A和B分别用两个线性 表LA和LB表示（即：线性表中的数据元素 即为集合中的成员)，现要求一个新的集合 A=AUBo 1·从线性表LB中依次取得每个数据元素； GetElem(LB,i)→e 2.依值在线性表LA中进行查访； LocateElem(LA,e,equal()) 3.若不存在，则插入之。 ListInsert(LA,n+1,e)

例2-1 假设有两个集合A和B分别用两个线性 表LA和LB表示（即：线性表中的数据元素 即为集合中的成员），现要求一个新的集合 A＝A∪B。 1．从线性表LB中依次取得每个数据元素; GetElem(LB, i)→e 2．依值在线性表LA中进行查访; LocateElem(LA, e, equal( )) 3．若不存在，则插入之。 ListInsert(LA, n+1, e)