资源描述：
《数据结构课件 chapter02_线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表线性表是最简单和最常用的一种数据结构。本章讨论线性表的定义、顺序存储结构和链式存储结构。重点是线性表两种不同存储结构下的操作及其相应的算法。第二章线性表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
2、)第一个元素a1无直接前驱最后一个元素an无直接后继每个数据元素ai只有一个直接前驱和一个直接后继数据元素之间具有一对一的关系线性表的特点线性表的逻辑结构线性表的定义线性表的特点同一性：线性表由同类数据元素组成有穷性：线性表由有限个数据元素组成表长度：表中数据元素的个数有序性：线性表中相邻数据元素之间存在序偶关系线性表的抽象数据类型定义ADTList{数据元素：D={ai
3、ai∈D0,i=1,2,…n,n>=0,D0为某一数据对象}结构关系：R={
4、ai,ai+1∈D0,i=1,2,…n-1}}基本操作：(1)InitList(L)操作前提：L为
5、未初始化的线性表操作结果：将L初始化为空表(2)DestroyList(L)操作前提：线性表L已经存在操作结果：将L销毁(3)ClearList(L)操作前提：线性表L已经存在操作结果：将L置为空表线性表的抽象数据类型定义数据元素：D={ai
6、ai∈D0,i=1,2,…n,n>=0,D0为某一数据对象}结构关系：R={
7、ai,ai+1∈D0,i=1,2,…n-1}基本操作：(4)EmptyList(L)操作前提：线性表L已经存在操作结果：如果L为空表则返回TRUE，否则返回FALSE(5)ListLength(L)操作前提：线性表L已经存在操作结果：如果L为空表则
8、返回0，否则返回表中数据元素的个数(6)Locate(L,e)操作前提：线性表L已经存在，e为合法数据元素值操作结果：如果L中存在数据元素e，则将“当前指针”指向数据元素e所在位置并返回TRUE，否则返回FALSE线性表的抽象数据类型定义数据元素：D={ai
9、ai∈D0,i=1,2,…n,n>=0,D0为某一数据对象}结构关系：R={
10、ai,ai+1∈D0,i=1,2,…n-1}基本操作：(7)GetData(L,i)操作前提：线性表L已经存在，且i值合法操作结果：返回线性表L中第i个数据元素的值(8)InsList(L,i,e)操作前提：线性表L已经存在，e为合
11、法元素值且i值合法操作结果：在表中第i个位置之前插入新的数据元素e，L的长度加1(9)DelList(L,i,e)操作前提：线性表L已经存在，e为合法元素值且i值合法操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减12.2线性表的顺序存储线性表的顺序存储结构顺序表的定义地址映像的计算公式线性表顺序存储的表示线性表顺序存储结构上的基本操作查找操作插入操作删除操作线性表的顺序存储结构顺序表的定义演示线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个数据元素，采用顺序存储结构存放的线性表通常称为顺序表。顺序表归纳为：关系线性化、结点顺序存地址映像的计算公式线性
12、表顺序存储的表示一组连续的存储单元存放线性表的数据元素线性表的顺序存储结构顺序表的定义演示地址映像的计算公式假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则第i个元素地址loc(ai)的计算公式：loc(ai)=loc(a1)+(i-1)*k线性表顺序存储的表示线性表的顺序存储结构顺序表的定义演示地址映像的计算公式线性表顺序存储的表示说明#defineMaxSize100/*此处的宏定义变量表示线性表的最大长度*/typedefstructlist{DataTypedata[MaxSize];/*存放线性表的数组*/intlast;/*线性表最后一个
13、元素的下标，空表为-1*/}SeqList;思考：last和len有怎样的关系？线性表的顺序存储结构#defineMaxSize100typedefstruct{DataTypedata[MaxSize];intlast;}SeqList;#defineMaxSize100typedefstruct{DataTypedata[MaxSize];intlen;}SeqList;(1)结点类型DataType由线性表中的元素类型确定。(2)数组下标从0开始计数，即data
