河池学院：《数据结构》课程电子教案（PPT教学课件）第2章 线性表 2.1 线性表的定义 2.2 线性表的顺序存储结构

第2章线性表 2.1线性表的定义 2.2线性表的顺序存储结构 提纲 2.3线性表的链式存储结构 CONTENTS 2.4顺序表和链表的比较 2.5线性表的应用 作业 上机实验题 1/58

CONTENTS 提纲 1/58

线性表是具有相同特性的数据元素的一个有限序列。 所有数据元素类型相同。 线性表是有限个数据元素构成的。 线性表中数据元素与位置相关，即每个数据元素有唯一的序号。 2/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

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

长度为n的线性表存放在顺序表中 data数组 a0 a1 . ai-1 ai . an-1 . 数组下标 0 1 . i-1 i . n-1 capacity-1 6/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

在动态分配顺序表的空间时，初始容量设置为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.整体建立顺序表 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.顺序表基本运算算法 public void Add(E e) //在线性表的末尾添加一个元素e { if (size==capacity) //顺序表空间满时倍增容量 updatecapacity(2*size); data[size]=e; size++; //长度增1 } 时间复杂度是多少？ 10/58