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