数据结构PPT教学课件-第2章_线性表.ppt

第二章线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
一元多项式的表示及相加
线性表
线性结构是一个数据元素的有序(次序)集。
线性结构的特点:
存在唯一的一个被称做“第一个”的数据元素;
存在唯一的一个被称做“最后一个”的数据元素;
除第一个之外,集合中的每个数据元素均只有一个前驱;
除最后一个之外,集合中每个数据元素均只有一个后继。
线性表的类型定义
线性表(Liner List):n(  0)个数据元素的有限序列,记作(a1, …ai-1, ai, ai+1,…, an);其中ai是表中数据元素,n是表长度。
线性表的特点:
同一线性表中元素具有相同特性;
相邻数据元素之间存在序偶关系;
除第一个元素外,其他每一个元素有一个且仅有一个直接前驱;
除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。
线性表举例:
1. 数据元素只要是同性质就可以:
比如(A,B,……,Z),又如(6,17,28,50,92,188)
2. 一个数据元素可以由若干项目(数据项Item)组成,此时数据元素称为记录(Record),而含有大量记录的线性表又称文件(file)。
姓名
学号
性别
年龄
班级
健康状况
王小林
790631
男
18
计91
健康
陈红
790632
女
20
计91
一般
刘建平
790633
男
21
计91
健康
张立立
790634
男
17
计91
神经衰弱
……
……
……
……
……
……
线性表定义演示
结论:
线性表中的数据元素可以是各种各样的,但同一线性表(a1, …ai-1, ai, ai+1,…, an)中所有元素具有相同特性,即属同一数据对象。
任意两相邻元素ai-1和 ai之间存在序偶关系< ai-1, ai >;其中称ai-1为ai的直接前驱,而ai为ai-1的直接后继。当i=1,2,…,n-1时,ai有且仅有一个直接后继,当i=2,3,…,n时,ai有且仅有一个直接前驱。
线性表中元素的个数n定义为线性表的长度,n=0时称为空表。
在非空线性表中,任意一个元素ai是表的第i个元素,i称为数据元素在线性表中的位序。
线性表的抽象数据类型定义以及基本操作
数据的运算是定义在逻辑结构上的,而运算的具体实现则是在存储结构上进行的。
抽象数据类型线性表的定义如下:
ADT List {
数据对象:D={ ai|ai∈ElemSet,i=1,2,……,n, n≥0 }
数据关系:R1={ <ai-1,ai>| ai-1, ai ∈Di,i=2,……,n }
基本操作:
线性表的基本操作(一)
InitList(&L)
操作结果:构造一个空的线性表L。
DestroyList(&L)
初始条件:线性表L已存在。
操作结果:销毁线性表。
线性表的基本操作(二)
CleanList(&L)
初始条件:线性表L已存在。
操作结果:将L重置为空表。
ListEmpty(&L)
初始条件:线性表L已存在。
操作结果:若L为空表,则返回TRUE,否则返回FALSE。
线性表的基本操作(三)
ListLength(L)
初始条件:线性表L已存在。
操作结果:返回L中数据元素个数。
GetElem(L, i, &e)
初始条件:线性表L已存在,1≤i ≤ListLength(L)。
操作结果:用e返回L中第i个数据元素的值。