第二章线性表 线性结构的特点:在数据元素中的非空有限集中 ●(1)存在唯一的一个被称作“第一”的数据元素; (2)存在唯一的一个被称作“最后一个”的数据元 素 (3)除第一个外,集合中的每一个数据元素均只有 一个前驱; (4)除最后一个外,集合中的每一个数据元素均只 有一个后继。 北京邮电大学自动化学院
北京邮电大学自动化学院 1 ⚫ 线性结构的特点：在数据元素中的非空有限集中 ⚫ （1）存在唯一的一个被称作“第一”的数据元素； ⚫ （2）存在唯一的一个被称作“最后一个”的数据元 素； ⚫ （3）除第一个外，集合中的每一个数据元素均只有 一个前驱； ⚫ （4）除最后一个外，集合中的每一个数据元素均只 有一个后继。 第二章 线性表
21线性表的类型定义 1、线性表 ●线性表 Linear list):一个线性表是n个数据元素的 有限序列。例如: 例1、26个英文字母组成的字母表 (A,B,C、∴、Z) 例2、某校从1999年到2003年各种型号的计算机拥 有量的变化情况。 ●(6,17,28,50,92,188) 北京邮电大学自动化学院
北京邮电大学自动化学院 2 ⚫ 1、线性表 ⚫ 线性表(Linear List) ：一个线性表是n个数据元素的 有限序列。例如： ⚫ 例1、26个英文字母组成的字母表 ⚫（A，B，C、…、Z） ⚫ 例2、某校从1999年到2003年各种型号的计算机拥 有量的变化情况。 ⚫（6，17，28，50，92，188） 2.1 线性表的类型定义
1、线性表 ●在稍复杂的线性表中,一个数据元素可以由若干个数据项组 成。在这种情况下,常把数据元素称为记录,含有大量记录的 线性表又称为文件。 ●例3、学生健康情况登记表如下: 姓名 学号 性别 年龄 健康情况 王小林 790631 18 健康 陈红 790632 20 一般 刘建平 790633 男女男男 21 健康 张立立 790634 神经衰弱 北京邮电大学自动化学院
北京邮电大学自动化学院 3 ⚫ 在稍复杂的线性表中，一个数据元素可以由若干个数据项组 成。在这种情况下，常把数据元素称为记录，含有大量记录的 线性表又称为文件。 ⚫ 例3、学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 …….. …….. ……. ……. ……. 1、线性表
1、线性表 综合上述三个例子可见,线性表中的数据元素可以是各种各样 的,但同一线性表中的元素必定具有相同特征,即属同一数据 对象,相邻数据元素之间存在着序偶关系。若将线性表记为: i+myan ·则表中a领先于a,a领先于a H19 称a1是a的直接前驱元 素,a1是a1的直接后继元素 当i=1,2,,n-时,a有且仅有一个直接后继,当i2,3,…,n 时,a有且仅有一个直接前驱。 线性表中的元素的个数n(n≥0)定义为线性表的长度,n=0时 称为空表。 北京邮电大学自动化学院 4
北京邮电大学自动化学院 4 ⚫ 综合上述三个例子可见，线性表中的数据元素可以是各种各样 的，但同一线性表中的元素必定具有相同特征，即属同一数据 对象，相邻数据元素之间存在着序偶关系。若将线性表记为： ⚫ (a1，…,a i-1，ai，a i+1…,an ) ⚫ 则表中ai-1领先于ai，ai领先于ai+1 ，称ai-1是ai的直接前驱元 素，ai+1是ai的直接后继元素。 ⚫ 当i=1,2,…,n-1时，ai有且仅有一个直接后继，当i=2,3,…,n 时， ai有且仅有一个直接前驱。 ⚫ 线性表中的元素的个数n(n 0)定义为线性表的长度，n=0时 称为空表。 1、线性表
2、抽象数据类型线性表 ADT Listi 数据对象:={a|an∈ Elem Set,i=1,2,,n,n0} 数据关系:R1={a11a|a1ap∈D,i=2,,n ●基本操作: ● netList(&L) ●操作结果:构造一个空的线性表L。 Destroy List(&L) 初始条件:线性表L已经存在。 ●操作结果:销毁线性表L。 北京邮电大学自动化学院
北京邮电大学自动化学院 5 ⚫ ADT List{ ⚫ 数据对象：={ai |aiElemSet，i=1,2,…,n,n0} ⚫ 数据关系：R1={<ai-1 ,ai>| ai-1 ,ai , D,i=2,…,n} ⚫ 基本操作： ⚫ InitList(&L) ⚫ 操作结果：构造一个空的线性表L。 2、抽象数据类型线性表 ⚫ DestroyList(&L) ⚫ 初始条件：线性表L已经存在。 ⚫ 操作结果：销毁线性表L