1.1线性表定义
线性表是具有相同数据类型的 n(n >= 0) 个数据元素的有限序列，通常记为：（a1,a2,…,ai,ai+1,…,an）,特征如下：
- 表中的元素个数n称为表的长度， n = 0 时称为空表。
- 当 1 < i < n时，第i个元素ai的直接前驱是ai-1,a1无直接前驱；第i个元素ai的直接后继是ai+1,an无直接后继。
- 所有的元素类型相同，且不能出现缺项。
每个数据元素可以是简单的数据类型，也可以是任意复杂的数据类型。
1.2线性表抽象数据类型（ADT）
在这个接口 MList 的基础上，顺序表和链表直接实现这个接口，并可以定义各自的特殊方法。
public interface MList {
//数据元素：(a1,a2,...,an)
//部分基本操作
//判断线性表是否为空
boolean isEmpty();
//线性表元素个数
int length();
//取第i个位置的数据元素，返回数据元素的值
T get(int i);
//将第i个位置的数据元素设置为值x
void set(int i, T x);
//将位置i及其后的元素依次后移一个位置， 将x插入到第i位置
void add(int i, T x);
//删除第i个位置的数据元素，位置 i+1 及其后的元素一次迁移一个位置
T remove(int i);
//返回数据元素x的表List中的位置
int indexOf(T x);
} 在java中，抽象数据类型的描述可以采用两种方式：第一种是抽象类；第二种是接口。下面用抽象类描述线性表。
1.3线性表抽象类定义
public abstract class MAbsList implements Iterable, MList{
protected int length;
//返回第 i(i >= 0) 个元素
abstract public T get(int i);
//设置第i个元素为x
abstract public void set(int i, T x);
// 查找，返回首次出现的关键字为key的元素
abstract public int indexOf(int begin, int end, T key);
//插入x作为第i个元素
abstract public void add(int i, T x);
abstract public void clear();
//删除第i个元素并返回被删除对象
abstract public T remove(int i);
//返回一个迭代器
abstract public Iterator iterator();
//判断线性表是否为空
public boolean isEmpty(){
return length == 0;
}
//返回线性表长度
public int length(){
return length;
}
//在线性表最后插入x
public void add(T x){
add(length, x);
}
public void append(T x){
add(length, x);
}
public int indexOf(T o){
return indexOf(0, length, o);
}
public int indexOf(int begin, T o){
return indexOf(begin, length, o);
}
public T remove(T o){
return remove(indexOf(o));
}
} 2.1顺序表
定义：把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表简称为顺序表。java中数组就是一种典型的顺序表，但数组有一个缺点即数组长度一旦确定，并为数组分配了数组存储空间，则数组就不能再增加长度。
特点：存储结构直接反映了逻辑结构。
2.2顺序表类定义
- 由于线性表中的元素类型是任意的，所以使用泛型，但java不支持泛型数组，所以在MSeqList中，保存实际数据的数组声明为Object类型。
- 顺序表容量管理由4个函数来实现：setCapacity(),getCapacity(),setIncr()和grow()。
- 顺序表实质上是数组，能够实现随机存取，由get(),set()方法实现。
- 向顺序表插入元素，数据存储空间不够时进行扩容，时间复杂度是O(n)。删除的时候也是O(n).
- 查找，因为允许顺序表元素为空，所以要对这种情况处理。
- 插入与排序
顺序表转换为数组或字符串
public class MSeqListextends MAbsList implements Iterable { //顺序表增量长度 private int incrementSize; //保存顺序表数据的数组 protected Object[] data; //默认构造函数 public MSeqList() { this(16); } //构造函数，capacity是顺序表容量 public MSeqList(int capacity) { if (capacity <= 0="" 0)="" capacity="16;" length="0;" incrementsize="0;" data="new" object[capacity];="" }="" 构造函数，用数组elem初始化顺序表="" public="" mseqlist(t[]="" elem)="" {="" length);="" 设置新的容量="" void="" setcapacity(int="" newsize){="" newsize);="" 取得顺序表容量="" int="" getcapacity(){="" return="" data.length;="" 设置顺序表每次容量增加时增量大小，默认值是16="" setincr(int="" inc){="" 内部使用，自动增加顺序表容量="" private="" grow(){="" newsize="data.length" +="" incrementsize;="" 取得顺序表长度，同length()="" size(){="" length;="" compare(t="" a,="" t="" b){="" if="" (a="" instanceof="" comparable="" &&="" b="" comparable){="" ((comparable)="" a).compareto((comparable)b);="" }else="" ((string)a).compareto((string)="" b);="" @override="" get(int="" i)="" (i="" <="" ||="" i=""> length - 1) return null; return (T) data[i]; } @Override public boolean set(int i, T x) { if (i < 0 || i > length - 1) return false; else { data[i] = x; return true; } } @Override public int indexOf(int begin, int end, T key) { //顺序查找 if (key == null){ //查找null值 for (int i = 0; i < length; i++){ if (data[i] == null) return i; } }else { //查找有效值 for (int i = 0; i < length; i++){ if (compare(key, (T) data[i]) == 0){ return i; } } } return -1; } @Override public void add(int i, T x) { //顺序表容量满，自动增蓉 if (length == data.length) grow(); if (i < 0) i = 0; if (i > length) i = length; for (int j = length - 1; j >= i; j--){ data[j + 1] = data[j]; } data[i] = x; length++; } @Override public void add(T x) { if (length == data.length) grow(); data[length] = x; length++; } @Override public void append(T x) { add(x); } //以有序方式向顺序表增加数据元素x public void addSort(T x){ insertOrder(length, x); length++; } //对顺序表排序 public void sort(){ for (int i = 0; i <= length-1;="" i++){="" insertorder(i,="" (t)="" data[i]);="" }="" 内部使用，以有序方式向顺序表增加数据元素x="" protected="" void="" insertorder(int="" end,="" t="" x){="" if="" (length="=" data.length)="" grow();="" int="" k;="" for="" (k="end" -="" 1;="" k="">= 0; k--){ if (compare(x, (T) data[k]) < 0) data[k+1] = data[k]; else break; } data[k+1] = x; } @Override public void clear() { for (int i = 0; i < length; i++){ data[i] = null; //java虚拟机的垃圾收集器自动处理 } length = 0; } @Override public T remove(int i) { if (i < 0 || i > length - 1) throw new IndexOutOfBoundsException("下标越界 i=" + i); T olddata = (T) data[i]; for (int j = i; j < length - 1; j++){ data[j] = data[j + 1]; } data[--length] = null; return olddata; } @Override public T remove(T o) { int i = indexOf(o); return remove(i); } @Override public Iterator iterator() { return null; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder = builder.append("("); for (int i = 0; i < length - 1; i++){ builder = builder.append(data[i].toString() + ","); } builder = builder.append(data[length-1] + ")"); String s = new String(builder); return s; } //将顺序表转换为Object数组 public Object[] toArray(){ return Arrays.copyOf(this.data, this.length); } /** * 将顺序表转换为类型为E的数组 * a的长度可以是0，a的主要作用是告诉系统将顺序表转换为类型为E[]的数组 * @param a * @return */ public E[] toArray(E[] a){ if (a.length < length){ //创建一个与数组a的运行时类型相同的新数组， a的长度可以为0 return (E[]) Arrays.copyOf(this.data, this.length, a.getClass()); } System.arraycopy(this.data, 0, a, 0, this.length); if (a.length > this.length){ a[length] = null; } return a; } //内部类，迭代器实现原理与链表迭代器相同 class MyIterator implements Iterator { private int index = 0; @Override public boolean hasNext() { //在调用next()后，index自增，确保index不等于length return index != length(); } @Override public T next() { return get(index++); } @Override public void remove() { } } }