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<E>//顺序表的初始容量（常量）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<E> //顺序表泛型类 { 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