塔里木大学：《数据结构》课程教学课件（PPT讲稿）第二章 线性表

第二章线性表2.1 丝线性表的类型定义2.2线性表的顺序表示和实现2.3 丝线性表的链式表示和实现

2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 第二章 线性表

主要内容：1.线性表的类型定义2.线性表的顺序表示和实现3.线性表的链式表示和实现学习提要：1.了解线性表的逻辑结构和物理结构2.掌握两种存储结构的描述方法以及在每种存诸结构上的基本操作的实现3.理解两种存储结构的特点及其使用场合重难点内容：顺序表、链表及其操作实现

主要内容： 1.线性表的类型定义 2.线性表的顺序表示和实现 3.线性表的链式表示和实现 学习提要： 1.了解线性表的逻辑结构和物理结构 2.掌握两种存储结构的描述方法以及在每种存 储结构上的基本操作的实现 3.理解两种存储结构的特点及其使用场合 重难点内容： 顺序表、链表及其操作实现

线性结构是一个数据元素的有序（次序）集。线性结构的基本特征（1）存在唯一的一个被称作“第一个”的数据元素（2）存在唯一的一个被称作“最后一个的数据元素（3）除第一个外，集合中的每个数据元素均只有一个前驱（4）除最后一个外，集合中的每个数据元素均只有一个后继

线性结构是一个数据元素的有序（次序） 集 。 线性结构的基本特征: （1）存在唯一的一个被称作“第一个”的 数据元素 （2）存在唯一的一个被称作“最后一个” 的数据元素 （3）除第一个外，集合中的每个数据元素 均只有 一个前驱 （4）除最后一个外，集合中的每个数据元 素均只有一个后继

8 2.1线性表的类型定义★线性表：n个数据元素组成的有限序列。表示为（a1，a2...，aiai+1 - ... , an)例：英文字母表（A,B,C......Z)是一个线性表例;学号姓名年龄数据元素18001张三19002李四

线性表：n个数据元素组成的有限序 列。表示为（a1，a2，.，ai， ai+1，.，an ) 例：英文字母表（A,B,C,.Z)是一个 线性表 例： 学号 姓名 年龄 001 张三 18 002 李四 19 . . . 数据元素 §2.1 线性表的类型定义

8 2.1线性表的类型定义★逻辑特征：*1=0)，n=0空表★位序：元素a：在表中的位置数i

§2.1 线性表的类型定义 线性表的长度：表中元素的个数 n(n>=0)，n=0 空表。 位序：元素ai在表中的位置数i 。 逻辑特征： ❖1<i<n时 ⚫ai的直接前驱是ai-1，a1无直接前驱 ⚫ai的直接后继是ai+1，an无直接后继 ❖元素同构，且不能出现缺项

抽象数据类型线性表的定义如下：ADT List {数据对象：D= a; | a; EElemSet , i-1,2,...,n,n≥0 }数据关系：R1 = ( lai-1 ,a; ED,i-2,..,n 基本操作：(&L)InitList(操作结果：构造一个空的线性表L

抽象数据类型线性表的定义如下： ADT List { 数据对象： D＝{ ai | ai ∈ElemSet，i=1,2,.,n, n≥0 } 数据关系： R1＝{ |ai-1 ,ai∈D, i=2,.,n } 基本操作： InitList( &L ) 操作结果：构造一个空的线性表L

DestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在操作结果：返回L中元素个数

DestroyList( &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,compareO)初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第i个与e满足关系compare(）的元素的位序。若这样的元素不存在，则返回值为0

GetElem( L, i, &e ) 初始条件：线性表L已存在，1≤i≤ListLength (L) 操作结果：用e返回L中第i个元素的值。 LocateElem( L, e, compare( ) ) 初始条件：线性表L已存在，compare( )是 元素判定函数。 操作结果：返回L中第i个与e满足关系 compare( )的元素的位序。若这样的元素不存 在，则返回值为0

PriorElem(L,cur e,&pre e)初始条件：线性表L已存在操作结果：若cure是L的元素，但不是第一个，则用pree返回它的前驱，否则操作失败，pree无定义NextElem(L, cur e, &next e)引用型操作初始条件：线性表L已存操作结果：若cure是L的元素，但不是最后一个，则用nexte返回它的后继，否则操作失败，nexte无定义

PriorElem( L, cur_e, &pre_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是第 一个，则用pre_e 返回它的前驱，否则操作失 败，pre_e无定义。 NextElem( L, cur_e, &next_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是最 后一个，则用next_e返回它的后继，否则操 作失败，next_e无定义。 引用型操作

ListTraverse(Lvisit())初始条件：线性表L已存在。加工型操作操作结果：依次对L的每个元系训用函数visit()。一旦visit()失败，则操作失败ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表PutElem(L,i, &e)初始条件：线性表L已存在，1≤i<ListLength (L)操作结果：L中第i个元素赋值同e的值

ListTraverse(L, visit( )) 初始条件：线性表L已存在。 操作结果：依次对L的每个元素调用函数 visit( )。一旦visit( )失败，则操作失败。 ClearList( &L ) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 PutElem( L, i, &e ) 初 始 条 件 ： 线 性 表 L 已存在 ， 1≤i≤ ListLength (L) 操作结果：L中第i个元素赋值同e的值。 加工型操作