数据结构课件 chapter02_线性表.ppt

第二章 线性表 线性表是最简单和最常用的一种数据结构。 本章讨论线性表的定义、顺序存储结构和链式存储结构。 重点是线性表两种不同存储结构下的操作及其相应的算法。 第二章 线性表 2.1 线性表的概念及其抽象数据类型 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的应用——一元多项式的表示及相加 2.5 顺序表与链表的综合比较（自学） 2.6 总结与提高（复习作业） 2.1 线性表的概念及其抽象数据类型 线性表的逻辑结构 线性表的定义 线性表的特点 线性表的抽象数据类型定义 线性表的逻辑结构 线性表的定义 线性表是由n（n=0）个类型相同的数据元素组成的有限序列，记做 (a1,a2,…ai-1,ai,ai+1,…an) 第一个元素a1无直接前驱 最后一个元素an无直接后继 每个数据元素ai只有一个直接前驱和一个直接后继 数据元素之间具有一对一的关系 线性表的特点 线性表的逻辑结构 线性表的定义 线性表的特点 同一性：线性表由同类数据元素组成 有穷性：线性表由有限个数据元素组成 表长度：表中数据元素的个数 有序性：线性表中相邻数据元素之间存在序偶关系ai,ai+1 线性表的抽象数据类型定义 ADT List{ 数据元素：D={ai|ai∈D0,i=1,2,…n,n=0,D0为某一数据对象} 结构关系：R={ai,ai+1|ai,ai+1∈D0,i=1,2,…n-1}} 基本操作： (1) InitList(L) 操作前提：L为未初始化的线性表 操作结果：将L初始化为空表 (2) DestroyList(L) 操作前提：线性表L已经存在 操作结果：将L销毁 (3) ClearList(L) 操作前提：线性表L已经存在 操作结果：将L置为空表 线性表的抽象数据类型定义 数据元素：D={ai|ai∈D0,i=1,2,…n,n=0,D0为某一数据对象} 结构关系：R={ai,ai+1|ai,ai+1∈D0,i=1,2,…n-1} 基本操作： (4) EmptyList(L) 操作前提：线性表L已经存在 操作结果：如果L为空表则返回TRUE，否则返回FALSE (5) ListLength(L) 操作前提：线性表L已经存在 操作结果：如果L为空表则返回0，否则返回表中数据元素的个数 (6) Locate(L,e) 操作前提：线性表L已经存在，e为合法数据元素值 操作结果：如果L中存在数据元素e，则将“当前指针”指向数据元素e所在位置并返回TRUE，否则返回FALSE 线性表的抽象数据类型定义 数据元素：D={ai|ai∈D0,i=1,2,…n,n=0,D0为某一数据对象} 结构关系：R={ai,ai+1|ai,ai+1∈D0,i=1,2,…n-1} 基本操作： (7) GetData(L,i) 操作前提：线性表L已经存在，且i值合法 操作结果：返回线性表L中第i个数据元素的值 (8) InsList(L,i,e) 操作前提：线性表L已经存在，e为合法元素值且i值合法 操作结果：在表中第i个位置之前插入新的数据元素e，L的长度加1 (9) DelList(L,i,e) 操作前提：线性表L已经存在，e为合法元素值且i值合法 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 2.2 线性表的顺序存储 线性表的顺序存储结构 顺序表的定义 地址映像的计算公式 线性表顺序存储的表示 线性表顺序存储结构上的基本操作 查找操作 插入操作 删除操作 线性表的顺序存储结构 顺序表的定义 演示 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个数据元素，采用顺序存储结构存放的线性表通常称为顺序表。 顺序表归纳为：关系线性化、结点顺序存 地址映像的计算公式 线性表顺序存储的表示 线性表的顺序存储结构 顺序表的定义 演示 地址映像的计算公式 假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则第i个元素地址loc(ai)的计算公式： loc(ai)=loc(a1)+(i-1)*k 线性表顺序存储的表示 线性表的顺序存储结构 顺序表的定义 演示 地址映像的计算公式 线性表顺序存储的表示 说明 #define MaxSize 100 /*此处的宏定义变量表示线性表的最大长度*/ typedef struct list{ DataType data[MaxSize]; /*存放线性表的数组*/ int last; /*线性表最后一个元素的下标，空表为-1*/ }SeqList; 线性表的顺序存储结构 #define MaxSize 100 typedef struct{ DataType da