《数据结构与算法分析》课程教学课件（PPT讲稿）第二章 线性表

第2章 线性表 本章主要介绍下列内容 ●线性表的类型定义 。线性表的顺序存储结构 ·线性表的链式存储结构 。线性表的应用举例

第2章 线性表 本章主要介绍下列内容 ⚫ 线性表的类型定义 ⚫ 线性表的顺序存储结构 ⚫ 线性表的链式存储结构 ⚫ 线性表的应用举例

2.1 线性表的类型定义 1、线性表的定义 线性表是由n(n>0)个类型相同的数据元素组成 的有限序列。通常表示成下列形式： L=(a1,a2,.,ai-1,ai,ai+i,.,an) 其中：L为线性表名称，习惯用大写书写； i为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度 当=0时，线性表为空，又称为空线性表。表中相 邻元素之间存在着前后次序关系，将ai-l称为ai的直接 前驱，将ai+l,称为ai的直接后继

2.1 线性表的类型定义 1、线性表的定义 线性表是由n（n≥0）个类型相同的数据元素组成 的有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度 当n=0时，线性表为空，又称为空线性表。表中相 邻元素之间存在着前后次序关系．将ai-1称为ai的直接 前驱，将ai＋1,称为ai的直接后继

线性表举例： La=(34,89,765,12,90,-34,22)//数据元素类型为int。 Ls=("H","W","C) //数据元素类型为字符型。 Lb=(booki,book2.,book1o) //数据元素类型为下列所示的结构类型： class bookinfo int No; /*图书编号*/ String name; /*图书名称*/ String auther;/*作者名称*/ . };

线性表举例： La=(34,89,765,12,90,-34,22)//数据元素类型为int。 Ls=(H , W , C) //数据元素类型为字符型。 Lb=(book1,book2,.,book100) //数据元素类型为下列所示的结构类型： class bookinfo { int No; /*图书编号*/ String name; /*图书名称*/ String auther; /*作者名称*/ .; };

L=（a1,a2,.,a-1,ai,ait1,.,an） 2、线性表的四个特点： 1)存在唯一的一个被称作“第一个”的数据 元素。 2)存在唯一的一个被称作“最后一个”的数 据元素。 3)除第一个之外，集合中的每个数据元素均 只有一个前驱。 4)除最后一个外，集合中的每个数据元素均 只有一个后继

L=( a1, a2,.,ai-1,ai,ai+1,.,an) 2、线性表的四个特点： 1）存在唯一的一个被称作“第一个”的数据 元素。 2）存在唯一的一个被称作“最后一个”的数 据元素。 3）除第一个之外，集合中的每个数据元素均 只有一个前驱。 4）除最后一个外，集合中的每个数据元素均 只有一个后继

3、线性表的抽象数据类型定义 ADT LIST! n个数据元素的集合。数据元素可以是整型、 字符型、结构类型。 数据对象·一 D={a|a;∈ElemSet,i=1,2,n,n≥0} 数据关系： R={|a-1,a∈D,i=2,n} a和a之间存在一个有序关系，二者不能互 基本操作： 换

3、线性表的抽象数据类型定义 ADT LIST{ 数据对象： D＝{ai | ai∈ElemSet, i=1,2,.,n, n≥0} 数据关系： R＝{ | ai-1 , ai ∈D, i=2,.,n} 基本操作： } 栈的n个数据元素的集合。数据元素可以是整型、 字符型、结构类型。 栈a i-1和ai之间存在一个有序关系，二者不能互 换

。关于基本操作的几点说明： 1、基本操作是定义于逻辑结构上的基本操作， 向外界提供一个与其通讯的接口。还没有用具 体的某种程序语言写出具体的算法，而算法的 实现只有在存储结构确立之后。对应于不同的 存储结构，线性表的基本操作的实现也不相同。 2、基本操作的种类可随实际需要的不同而不 同。 ·3、针对不同的需要，基本操作的参数和返回 值可以有所变化

• 关于基本操作的几点说明： • 1、基本操作是定义于逻辑结构上的基本操作， 向外界提供一个与其通讯的接口。还没有用具 体的某种程序语言写出具体的算法，而算法的 实现只有在存储结构确立之后。对应于不同的 存储结构，线性表的基本操作的实现也不相同。 • 2、基本操作的种类可随实际需要的不同而不 同。 • 3、针对不同的需要，基本操作的参数和返回 值可以有所变化

1、 求长度：count() 初始条件：线性表存在； ■操作结果：返回线性表中所有数据元素的个数。 2、清空操作：Clear(0 初始条件：线性表存在且有数据元素； 操作结果：从线性表中清除所有数据元素，线 性表为空。 ■3、判断线性表是否为空：IsEmpty0 ■初始条件：线性表存在； ■操作结果：如果线性表为空返回true,否则返回 false

1、求长度：count() ◼ 初始条件：线性表存在； ◼ 操作结果：返回线性表中所有数据元素的个数。 ◼ 2、清空操作：Clear() ◼ 初始条件：线性表存在且有数据元素； ◼ 操作结果：从线性表中清除所有数据元素，线 性表为空。 ◼ 3、判断线性表是否为空：IsEmpty() ◼ 初始条件：线性表存在； ◼ 操作结果：如果线性表为空返回true，否则返回 false

4、附加操作：Append(T item) ■初始条件：线性表存在且未满； ·操作结果：将值为item的新元素添加到表的末尾。 a5、插入操作：Insert(T item,inti) ·初始条件：线性表存在，插入位置正确(1≤isn+1,n为插 入前的表长)。 ■操作结果：在线性表的第i个位置上插入一个值为item 的新元素，这样使得原序号为i,i+1,n的数据元素的序 号变为i+1,i+2,.,n+1,插入后表长=原表长+1

◼ 4、附加操作：Append(T item) ◼ 初始条件：线性表存在且未满； ◼ 操作结果：将值为item的新元素添加到表的末尾。 ◼ 5、插入操作：Insert(T item, int i) ◼ 初始条件：线性表存在，插入位置正确(1≤i≤n+1,n为插 入前的表长)。 ◼ 操作结果：在线性表的第i个位置上插入一个值为item 的新元素，这样使得原序号为i,i+1,.,n的数据元素的序 号变为i+1,i+2,.,n+1，插入后表长=原表长+1

6、删除操作：Delete(inti) 初始条件：线性表存在且不为空，删除位置正确 (1≤isn,n为删除前的表长)。 ■操作结果：在线性表中删除序号为的数据元素， 返回删除后的数据元素。删除后使原序号为 i+1,i+2,n的数据元素的序号变为1，i+1,.,n-1, 删除后表长=原表长1。 ■ 7、取表元：GetElem(inti) ■初始条件：线性表存在，所取数据元素位置正确 (1sisn,n为线性表的表长)； ■操作结果：返回线性表中第个数据元素

◼ 6、删除操作：Delete(int i) ◼ 初始条件：线性表存在且不为空，删除位置正确 (1≤i≤n,n为删除前的表长)。 ◼ 操作结果：在线性表中删除序号为i的数据元素， 返回删除后的数据元素。删除后使原序号为 i+1,i+2,.,n的数据元素的序号变为i,i+1,.,n-1， 删除后表长=原表长-1。 ◼ 7、取表元：GetElem(int i) ◼ 初始条件：线性表存在，所取数据元素位置正确 （1≤i≤n，n为线性表的表长）； ◼ 操作结果：返回线性表中第i个数据元素

8、按值查找：Locate(T value) ■初始条件：线性表存在。 ■操作结果：在线性表中查找值为vaue的数据元 素，其结果返回在线性表中首次出现的值为 vaue的数据元素的序号，称为查找成功；否则， 在线性表中未找到值为value的数据元素，返回 一个特殊值表示查找失败

8、按值查找：Locate(T value) ◼ 初始条件：线性表存在。 ◼ 操作结果：在线性表中查找值为value的数据元 素，其结果返回在线性表中首次出现的值为 value的数据元素的序号，称为查找成功；否则， 在线性表中未找到值为value的数据元素，返回 一个特殊值表示查找失败