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

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

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

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

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

目录页 Contents Page 线性表的类型定义 第二章线性表 线性表的顺序表示和实现 线性表的链式表示和实现 一元多项式的表示及相加 -3一 1945

— 3— — 3— Contents Page 目录页 线性表的顺序表示和实现 线性表的链式表示和实现 一元多项式的表示及相加 线性表的类型定义

2.1线性表的类型定义 ■线性表是个类型相同数据元素的有限序列 例126个英文字母组成的字母表 (A,B,C,,Z) 例2某校从1985年到1990年各种型号的计算机拥 有量的变化情况 (6,17,28,50,92,188) -4一 145

— 4— 2.1 线性表的类型定义  线性表是n个类型相同数据元素的有限序列 例1 26个英文字母组成的字母表 （A，B，C，…，Z） 例2 某校从1985年到1990年各种型号的计算机拥 有量的变化情况 （6，17，28，50，92，188）

2.1线性表的类型定义 ■线性表是个类型相同数据元素的有限序列 例3学生健康情况登记表如下 姓名 学号性别 年龄 健康情况 王小林 790631 男 18 健康 陈红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 see。ees0 ●。●●● ●。。●●。。 0 -5 1945

— 5— 2.1 线性表的类型定义 例3 学生健康情况登记表如下 …….. …….. ……. ……. ……. 张立立 790634 男 17 神经衰弱 刘建平 790633 男 21 健康 陈 红 790632 女 20 一般 王小林 790631 男 18 健康 姓 名 学 号 性 别 年龄 健康情况  线性表是n个类型相同数据元素的有限序列

2.1线性表的类型定义 ■线性表是个类型相同数据元素的有限序列 a1a23…a-1y aitI.. 数据元素 第一个元素 接前趋 a的直接卮 最后一个元素 下标，是元素的序号， 表示元素在表中的位置 n为元素总个数，即表长 n=0时，称为空表 -6 1945

— 6— 2.1 线性表的类型定义 ( a1, a2, … ai-1，ai , ai+1 ,…, an ) n=0时，称为空表 数据元素 第一个元素 ai的直接前趋 ai的直接后继 下标，是元素的序号， 表示元素在表中的位置 n为元素总个数，即表长 最后一个元素  线性表是n个类型相同数据元素的有限序列

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

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

2.1线性表的类型定义 结构操作 初始化操作 InitList(&L) 操作结果：构造一个空的线性表L。 结构销毁操作 DestroyList(&L 初始条件：线性表L已存在。 操作结果：销毁线性表L。 -8 145

— 8— 2.1 线性表的类型定义 结构操作 InitList( &L ) 操作结果：构造一个空的线性表L。 初始化操作 结构销毁操作 DestroyList( &L ) 初始条件：线性表L已存在。 操作结果：销毁线性表L

2.1线性表的类型定义 引用型操作： ListEmpty(L) ListLength(L) GetElem(L,i,&e LocateElem(L,e,compare()) -9 145

— 9— 2.1 线性表的类型定义 ListEmpty( L ) ListLength( L ) GetElem( L, i, &e ) 引用型操作: LocateElem( L, e, compare( ) )

2.1线性表的类型定义 ListEmpty(L) (线性表判空) 初始条件： 线性表L已存在。 操作结果： 若L为空表，则返回TRUE, 否则FALSE。 Q -10 145

— 10 — 2.1 线性表的类型定义 ListEmpty( L ) 初始条件： 操作结果： 线性表L已存在。 若L为空表，则返回TRUE， 否则FALSE。 （线性表判空）