1.1线性表抽象数据类型
线性表是由n(n>=0)个类型相同的数据元素a0,a1,...,an-1组成的有限序列，记为：
<div align = "center">LinearList = (a0,a1,...,an-1)</div>
线性表接口LList声明如下，表示线性表抽象数据类型，描述线性表的获取元素值、设置元素值、插入、删除等基本操作。文件名为LList.java。
public interface LList<T> {
/**
* 判断线性表是否为空
* @return
*/
boolean isEmpty();
/**
* 返回线性表长度
* @return
*/
int lenght();
/**
* 返回第i(i>=0)个元素
* @param i
* @return
*/
T get(int i);
/**
* 设置第i个元素值为x
* @param i
* @param x
*/
void set(int i,T x);
/**
* 插入x作为第i个元素
* @param i
* @param x
*/
void insert(int i,T x);
/**
* 在线性表最后插入x元素
* @param i
* @param x
*/
void append(T x);
/**
* 删除第i个元素并返回被删除对象
* @param i
* @return
*/
T remove(int i);
/**
* 删除线性表所有元素
* @return
*/
T removeAll();
/**
* 查找
* @param key
* @return 返回首次出现的关键字为key元素
*/
T search(T key);
}
1.2线性表的顺序表现和实现
1.线性表的顺序存储结构
线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱ai-1及后继ai+1的存储位置相邻。顺序存储的线性表也称为顺序表（sequential list）。
线性表的数据元素属于同一种数据类型，设a0的存储地址为Loc(a0)，每个元素占用c字节，则ai的存储地址为
<div align = "center">Loc(ai) = Loc(a0)+i*c</div>
顺序表元素ai的存储地址是它在线性表中位置i的线性函数，如上图所示，与线性表长度n无关；而计算一个元素地址所需时间是一个常量，与元素位置i无关。因此，存取任何一个元素的时间复杂度是O(1).换言之，顺序表是一种随机存储结构。
顺序表通常采用数组存储数据元素。数组是顺序存储的随机存取结构。
2.顺序表类(SeqList.java)
SeqList类有两个私有成员变量element和len。element是一个存放线性表元素的一维数组，元素类型为T；len表示顺序表长度，len<= element.length.
import com.zxj.sequential.LList;
public class SeqList<T> implements LList<T> {
/**
* 对象数组，私有成员
*/
private Object[] element;
/**
* 顺序表长度，记载元素个数
*/
private int len;
/**
* 构造方法，创建容量为size的空表
*
* @param size
*/
public SeqList(int size) {
this.element = new Object[size];
this.len = 0;
}
/**
* 默认构造方法，创建默认容量的空表
*/
public SeqList() {
this(64);
}
@Override
public boolean isEmpty() {
return this.len == 0;
}
@Override
public int lenght() {
return this.len;
}
/**
* 返回第i(i>=0)个元素，若i制定序号无效则返回null
*/
@Override
public T get(int i) {
if (i >= 0 && i < this.len)
return (T) this.element[i];
return null;
}
@Override
public void set(int i, T x) {
if (x == null)
return;
if (i >= 0 && i < this.len)
this.element[i] = x;
else
throw new IndexOutOfBoundsException(i + "");
}
@Override
public void insert(int i, T x) {
if(x == null)
return;
if(this.len == element.length){//若数组满，则扩充顺序表容量
Object[] temp = this.element;//temp也引用element数组
this.element = new Object[temp.length * 2];//重新申请一个容量更大的数组
for(int j=0;j<temp.length;j++)//复制数组元素,O(n)
this.element[j] =temp[j];
}
if(i<0)
i=0;//下标容错
if(i>this.len)
i = this.len;
for(int j = this.len -1;j>=i;j--)//元素后移，平均移动len/2
this.element[j + 1] = this.element[j];
this.element[i] = x;
this.len ++;
}
/**
* 在顺序表最后插入x对象
*/
@Override
public void append(T x) {
insert(this.len, x);
}
/**
* 删除第i个元素，若操作成功返回被删除对象，否则返回null
*/
@Override
public T remove(int i) {
if(this.len == 0 || i<0 ||i > this.len)
return null;
T old = (T) this.element[i];
for(int j = i;j<this.len - 1;j++)//元素前移，平均移动len/2
this.element[j] = this.element[j+1];
this.element[this.len -1] = null;//尾位置设置为空
this.len --;
return old;
}
@Override
public T removeAll() {
// TODO Auto-generated method stub
return null;
}
@Override
public T search(T key) {
// TODO Auto-generated method stub
return null;
}
public String toString() {
String str = "(";
if (this.len > 0)
str += this.element[0].toString();
for (int i = 1; i < this.len; i++)
str += "," + this.element[i].toString();
return str + ")";
}
}
3.顺序表的插入操作
4.顺序表的删除操作
5.顺序表操作的效率分析
6. 顺序表的浅拷贝与深拷贝
一个类的构造方法，如果其参数是该类对象，称为拷贝构造方法
一个类的拷贝构造方法声明格式如下：
类(类 对象)
类(类 对象) { //拷贝构造方法
this.成员变量 = 参数对象.成员变量; //逐域赋值，以参数的实例值初始化当前实例
}
（1）顺序表的浅拷贝
如果一个类将拷贝构造方法实现为逐域拷贝，即将当前对象的各成员变量值赋值为实际参数对应各成员变量值，称为浅拷贝。
public SeqList(SeqList<T> list) { //浅拷贝构造方法
this.n = list.n; //int整数赋值，复制了整数值
this.element = list.element;
//数组引用赋值，两个变量共用一个数组，错误
}
当成员变量的数据类型是基本数据类型时，浅拷贝能够实现对象复制功能。由于Java的数组和类是引用数据类型，两个数组/对象之间的赋值是引用赋值，数组赋值过程中没有申请新的存储空间，对象赋值过程中没有创建新的实例。因此，当成员变量的数据类型是引用类型时，浅拷贝只复制了对象引用（类似C++语音的指针变量），并没有真正实现对象复制功能。例如，设已有顺序表对象lista，以下语句执行拷贝构造方法创建顺序表对象listb
<div align = "center">SeqList<String> listb = new SeqList<String>(lista);</div>
（2）顺序表的深拷贝
当一个类包含引用类型的成员变量时，该类声明的拷贝构造函数，不仅要复制对象的所有基本类型成员变量值，还要重新申请引用类型变量占用的动态存储空间，并复制其中所有对象，这种复制方式称为深拷贝
public SeqList(SeqList<T> list){ //深拷贝构造方法
this.len = list.len; //若lsit == null，抛出空对象异常
this.element = new Object[list.element.length]; //申请一个数组
for(int i=0;i<list.element.length;i++) //复制数组元素，O(n)
this.element[i] = list.element[i]; //对象引用，没有创建新对象
}
public SeqList(T[] element) //构造方法，参数数组指定顺序表初值，方法体省略
7.线性表比较相等
两个线性表相等是指，它们各对应元素相等并且长度相同。
public boolean equals(Object obj)
{
if (this==obj) //引用同一个实例
return true;
if (obj instanceof SeqList<?>) //若obj引用顺序表实例。
//SeqList<?>是所有SeqList<T>的父类
{
SeqList<T> list = (SeqList<T>)obj;
if (this.length()==list.length()) //比较长度
{
for (int i=0; i<this.length(); i++) //比较所有元素
if (!(this.get(i).equals(list.get(i)))) //运行时多态
return false;
return true;
}
}
return false;
}