第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+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∈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
2.2线性表的顺序存储结构2.2.1线性表的顺序存储结构一顺序表长度为n的线性表存放在顺序表中capacity-17-1n-1数组下标6data数组aan-16/58
长度为n的线性表存放在顺序表中 data数组 a0 a1 . ai-1 ai . an-1 . 数组下标 0 1 . i-1 i . n-1 capacity-1 6/58
data数组存放线性表元素data数组的容量（存放最多的元素个数）为capacity。线性表中实际数据元素个数size//顺序表泛型类publicclassSqListclass//顺序表的初始容量（常量）final int initcapacity=io://存放顺序表中元素public E[] data;public int size;//存放顺序表的长度//存放顺序表的容量private int capacity;//构造方法，实现data和length的初始化public SqListclass()data=（E[])new Object[initcapacity]；//强制转换为E类型数组capacity=initcapacity;size=0;7//线性表的基本运算算法77/58
data数组存放线性表元素 data数组的容量（存放最多的元素个数）为capacity。 线性表中实际数据元素个数size public class SqListClass //顺序表泛型类 { final int initcapacity=10; //顺序表的初始容量(常量) public E[] data; //存放顺序表中元素 public int size; //存放顺序表的长度 private int capacity; //存放顺序表的容量 public SqListClass() //构造方法，实现data和length的初始化 { data = (E[])new Object[initcapacity]; //强制转换为E类型数组 capacity=initcapacity; size=0; } //线性表的基本运算算法 } 7/58
2.2.2线性表基本运算算法在顺序表中的实现在动态分配顺序表的空间时，初始容量设置为initcapacity，当添加或者插入元素可能需要扩大容量，在删除元素时可能需要减少容量。private void updatecapacity(int newcapacity)//改变顺序表的容量为newcapacity{E[]newdata =(E[])new Object[newcapacity];//复制原来的元素for (int i=; i<size; i++)newdata[i]=data[i];//设置新容量capacity=newcapacity;//仍由data标识数组data=newdata;子8/58
在动态分配顺序表的空间时，初始容量设置为initcapacity，当添加或 者插入元素可能需要扩大容量，在删除元素时可能需要减少容量。 private void updatecapacity(int newcapacity) //改变顺序表的容量为newcapacity { E[] newdata = (E[])new Object[newcapacity]; for (int i=0; i<size; i++) //复制原来的元素 newdata[i]=data[i]; capacity=newcapacity; //设置新容量 data=newdata; //仍由data标识数组 } 8/58
1.整体建立顺序表由含若干个元素的数组a的全部元素整体创建顺序表，即依次将a中的元素添加到data数组的末尾，当出现上溢出时按实际元素个数size的两倍扩大容量。//由a整体建立顺序表publicvoidCreateList(E[]a) int i,k=o;for(i=o;i<a.length;i++)1/出现上溢出时(if(size==capacity)//扩大容量updatecapacity(2*size);data[k]=a[i];k++;//添加的元素个数增加17size=k;1/设置长度79/58
1.整体建立顺序表 public void CreateList(E[] a) //由a整体建立顺序表 { int i,k=0; for (i=0;i<a.length;i++) { if (size==capacity) //出现上溢出时 updatecapacity(2*size); //扩大容量 data[k]=a[i]; k++; //添加的元素个数增加1 } size=k; //设置长度 } 由含若干个元素的数组a的全部元素整体创建顺序表，即依次将a中的元素 添加到data数组的末尾，当出现上溢出时按实际元素个数size的两倍扩大容量。 9/58
2.顺序表基本运算算法（1）将元素e添加到线性表末尾Add（e）//在线性表的末尾添加一个元素epublic void Add(E e)1/顺序表空间满时倍增容量{if(size==capacity)updatecapacity(2*size);data[size]=e;//长度增1size++;时间复杂度是多少？10/58
2.顺序表基本运算算法 public void Add(E e) //在线性表的末尾添加一个元素e { if (size==capacity) //顺序表空间满时倍增容量 updatecapacity(2*size); data[size]=e; size++; //长度增1 } 时间复杂度是多少？ 10/58