第2章线性表 2.1线性表的定义 2.2线性表的顺序存储结构 提纲 2.3线性表的链式存储结构 CONTENTS 2.4顺序表和链表的比较 2.5线性表的应用 作业 上机实验题 1/58
CONTENTS 提纲 1/58
2.1线性表的定义2.1.1什么是线性表线性表是具有相同特性的数据元素的一个有限序列。所有数据元素类型相同。线性表是有限个数据元素构成的。线性表中数据元素与位置相关，即每个数据元素有唯一的序号。2/58
线性表是具有相同特性的数据元素的一个有限序列。 所有数据元素类型相同。 线性表是有限个数据元素构成的。 线性表中数据元素与位置相关，即每个数据元素有唯一的序号。 2/58
线性结构的基本特征是：①有而且只有一个“第一元素”；②有而且只有一个“最后元素”；③除第一元素之外，其他元素都有唯一的直接前趋④除最后元素之外，其他元素都有唯一的直接后继
✎ 线性结构的基本特征是： ①有而且只有一个“第一元素” ； ②有而且只有一个“最后元素” ； ③除第一元素之外，其他元素都有唯一的直接前趋； ④除最后元素之外，其他元素都有唯一的直接后继
线性表的逻辑结构表示(ag, ai,", ai, ai+1,..,an-1)用图形表示的逻辑结构：doadi+1dn-1线性表中每个元素a的唯一位置通过序号或者索引表示，为了说明算法设计方便，将逻辑序号和存储序号统一，均假设从0开始，这样含n个元素的线性表的元素序号i满足0≤i≤n-1。4/58
线性表的逻辑结构表示 （a0，a1，.，ai，ai+1，.，an-1） 用图形表示的逻辑结构： a0 a1 . ai ai+1 . an-1 线性表中每个元素ai的唯一位置通过序号或者索引i表示，为了 算法设计方便，将逻辑序号和存储序号统一，均假设从0开始， 这样含n个元素的线性表的元素序号i满足0≤i≤n-1。 说明 4/58
2.1.23线性表的抽象数据类型描述ADT Listt数据对象：D={ai|0≤i≤n-1，n≥0，a为E类型}//E是用户指定的类型数据关系：r={<ai, ai+1> [ ai, ai+iED, i=0, ., n-2]基本运算（11个）：void CreateList(E[]a)：由a数组建立线性表的相应存储结构。voidAdd(Ee)：将元素e添加到线性表末尾。int size()：求线性表的长度。voidSetsize（int nlen)：设置线性表的长度为nlen。EGetElem（inti）：求线性表中序号为i的元素。voidSetElem（int i，Ee）：设置线性表中序号i的元素为e。int GetNo(E e)：求线性表中第一个值为e的元素的序号。voidswap（inti，intj)：交换线性表中序号i和序号j的元素。voidInsert（inti，Ee）：在线性表中插入数据元素e作为第i个元素。voidDelete（inti）：在线性表中删除第i个数据元素。Stringtostring()：将线性表转换为字符串。5/58
ADT List { 数据对象： D={ai | 0≤i≤n-1，n≥0，ai为E类型} //E是用户指定的类型 数据关系： r={<ai，ai+1> | ai，ai+1∈D，i=0，.，n-2} 基本运算（11个）： void CreateList(E [] a)：由a数组建立线性表的相应存储结构。 void Add(E e)：将元素e添加到线性表末尾。 int size()：求线性表的长度。 void Setsize(int nlen)：设置线性表的长度为nlen。 E GetElem(int i)：求线性表中序号为i的元素。 void SetElem(int i，E e)：设置线性表中序号i的元素为e。 int GetNo(E e)：求线性表中第一个值为e的元素的序号。 void swap(int i，int j)：交换线性表中序号i和序号j的元素。 void Insert(int i，E e)：在线性表中插入数据元素e作为第i个元素。 void Delete(int i)：在线性表中删除第i个数据元素。 String toString()：将线性表转换为字符串。 } 5/58