线性表之顺序表
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线性表的顺序表现和实现
<img src="http:https://img.haomeiwen.com/i2918620/bb96d3ac94bc4055.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/500">
1.线性表的顺序存储结构
线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱ai-1及后继ai+1的存储位置相邻。顺序存储的线性表也称为顺序表（sequential list）。
线性表的数据元素属于同一种数据类型，设a0的存储地址为Loc(a0)，每个元素占用c字节，则ai的存储地址为
<div align = "center">Loc(ai) = Loc(a0)+i*c</div>
<img src="http:https://img.haomeiwen.com/i2918620/8ebdaf65c4d32f0d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/400" >
顺序表元素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.顺序表的插入操作
<img src="http:https://img.haomeiwen.com/i2918620/f6e5532fa7c64287.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/400" />
<img src="http:https://img.haomeiwen.com/i2918620/1df50dcca4281c0f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/100">
如果数组已满，则不能插入，称为数据溢出。解决数据溢出的办法是，申请另一个更大容量的数组并复制全部数组元素，这样就扩充了顺序表的容量。代码如上SeqList类中的insert(int ,T)和append(T)。
<img src="http:https://img.haomeiwen.com/i2918620/1058430800136812.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/400">
4.顺序表的删除操作
删除顺序表元素ai,必须将元素ai+1，ai+2,...,an-1向前移动,移动过程如下图所示：
<img src="http:https://img.haomeiwen.com/i2918620/994f6961d74a285d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/400">
5.顺序表操作的效率分析
顺序表的静态特性很好，动态特性很差，具体说明如下。
① 顺序表元素的物理存储顺序直接反映线性表元素的逻辑顺序，顺序表是一种随机存取结构。get()、set()方法时间复杂度是 O(1)。
② 插入和删除操作效率很低。如果在各位置插入元素的概率相同，则有
<img src="http:https://img.haomeiwen.com/i2918620/e36b2525052c11f7.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/650">
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>
浅拷贝构造方法复制数组引用，使得两个对象的element变量只拥有一个数组，新对象没有申请自己的数组空间，如图a所示。两个对象拥有同一个数组，造成修改、插入、删除等操作结构互相影响，这是错误的。例如，当调用语句"lista.remove(4)";删除顺序表lista的一个元素时，实际上也删除了顺序表listb的元素，但listb的长度len没有改变，如图b所示，再调用语句“System.out.println("listb:"+listb.toString());”输出顺序表时，将产生运行错误。
<img src="http:https://img.haomeiwen.com/i2918620/691e5a5b3454ecae.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240">
因此，SeqList类的拷贝构造函数，不仅要复制对象的所有成员变量值，还要重新申请一个数组并复制所有数组元素，实现深度复制功能。
（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]; //对象引用，没有创建新对象
}
它的拷贝效果如图(a)和(b)所示，listb.element申请新的数组空间，使得lista.element和listb.element分别引用一个数组，进行插入、删除等操作，两者不会互相影响。但是， 由于对象赋值是引用赋值，导致lista.element和listb.element两个数组对应元素引用相同实例，修改其中某个实例，将同时改变另一个数组元素引用的该实例。
<img src="http:https://img.haomeiwen.com/i2918620/d6acbc26126cbe53.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/750">
所以，深拷贝应该是，复制每个引用类型成员变量所引用的数组或对象，这样对象可达的所有对象，如图(c)所示。但是，由于Java没有提供默认拷贝构造方法，所以不能实现类型参数为T的泛型类的深度拷贝功能。
与此类似，SeqList类提供以下深拷贝构造方法，由参数数组指定顺序表初值。
public SeqList(T[] element) //构造方法，参数数组指定顺序表初值，方法体省略
<img src="http:https://img.haomeiwen.com/i2918620/0d5e7f8a9ae5c668.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/750">
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;
}
