安徽理工大学：《数据结构》课程教学资源（PPT课件讲稿，C语言版，2018）第2章 线性表

第二章线性表 ■学习要点 ■了解线性表的逻辑结构是数据元素 之间存在着线性关系。 ■ 熟练掌握线性表的两种存储结构 即顺序存储结构和链式存储结构。 ■熟练掌握线性表的两种存储结构的 基本算法：查找、插入、删除等

第二章 线性表 ◼ 学习要点 ◼了解线性表的逻辑结构是数据元素 之间存在着线性关系。 ◼熟练掌握线性表的两种存储结构， 即顺序存储结构和链式存储结构。 ◼熟练掌握线性表的两种存储结构的 基本算法:查找、插入、删除等

线性表是一种最简单的线性结构 线性结构的基本特征为： 在数据元素的非空有限集中 1.存在唯一的一个“第一元素”： 2.存在唯一的一个 “最后元素 3.除最后元素在外，均有唯一的后继 4.除第一元素之外，均有唯一的前驱

线性表是一种最简单的线性结构 线性结构的基本特征为: 1．存在唯一的一个“第一元素”； 2．存在唯一的一个 “最后元素” ； 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。 在数据元素的非空有限集中

2.1线性表的类型定义 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4一元多项式的表示及相加

2.1 线性表的类型定义 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加 2.2 线性表的顺序表示和实现

2.1线性表的类型定义 ■线性表是n个类型相同数据元 素的有限序列 例如：英文字母表 学校计算机数量 学生健康情况登记表

2.1 线性表的类型定义 ◼线性表是n 个类型相同数据元 素的有限序列 例如：英文字母表 学校计算机数量 学生健康情况登记表

例1.26个英文字母组成的字母表 (A,B,C,·,Z) 例2.某校从1985年到1990年各种 型号的计算机拥有量的变化情况 (6,17,28,50,92,188)

例1. 26个英文字母组成的字母表 （A，B，C，…，Z） 例2. 某校从1985年到1990年各种 型号的计算机拥有量的变化情况 （6，17，28，50，92，188）

例3.学生健康情况登记表如下 姓名 学号 性别 年龄 健康情况 王小林 790631 男 18 健康 陈红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 17 神经衰弱

例3. 学生健康情况登记表如下 …….. …….. ……. ……. ……. 张立立 790634 男 17 神经衰弱 刘建平 790633 男 21 健康 陈 红 790632 女 20 一般 王小林 790631 男 18 健康 姓 名 学 号 性 别 年龄 健康情况

不同线性表中数据元素的类型可 以是各种各样的，但同一线性表中 的元素必须是同一类型的； 若将线性表记为 （a1,…,ai-l,a,a+1yan 1)在表中a.领先于a,,a领先于a+i 称a-是a的直接前驱，a+1是a的直 接后继；

不同线性表中数据元素的类型可 以是各种各样的，但同一线性表中 的元素必须是同一类型的； 若将线性表记为 （a1 , ... , ai -1 , ai , ai+1, …, an） 1) 在表中ai-1领先于ai ，ai领先于ai+1， 称ai-1是ai的直接前驱， ai+1是ai的直 接后继；

若将线性表记为 （a1,…,ai-lyai)ai+1…, 2)在线性表中，除第一个元素和最 后一个元素之外，其他元素都有且仅 有一个直接前驱，有且仅有一个直接 后继，这是所有线性结构的共同特征。 线性表是一种线性数据结构；

若将线性表记为 （a1 , ... , ai -1 , ai , ai+1, …, an） 2) 在线性表中，除第一个元素和最 后一个元素之外，其他元素都有且仅 有一个直接前驱，有且仅有一个直接 后继，这是所有线性结构的共同特征。 线性表是一种线性数据结构；

若将线性表记为 (a1,…,a-1,a1,at1,,a 3)线性表中元素的个数n称为线性表 的长度，n=0时称空表， 4)a是线性表的第i个元素，称为数 据元素a的位序，每一个元素在线性 表中的位置，仅取决于它的位序；

若将线性表记为 （a1 , ... , ai -1 , ai , ai+1, …, an） 3) 线性表中元素的个数n 称为线性表 的长度，n=0 时称空表； 4) ai是线性表的第i 个元素，称i为数 据元素ai 的位序，每一个元素在线性 表中的位置，仅取决于它的位序；

抽象数据类型线性表的定义如下： ADT List 数据对象： D={a;a;E ElemSet,i=1,2,...,n,n20 数据关系： R1={la-1,a∈D,i=2,,n} 基本操作： 结构操作 引用型操作 加工型操作 ADT List

抽象数据类型线性表的定义如下： ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ |ai-1 ,ai∈D, i=2,...,n } 基本操作： 结构操作 引用型操作 加工型操作 } ADT List