数据结构（2.1）-线性表的顺序表示

顺序表使用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。线性表中元素的位序是从1开始的。

特点：
1. 具有随机访问的特性，即通过首地址和元素序号可以在O(1)时间内找到指定元素。
2. 元素存储密度高，每个节点只存储数据元素。
3. 逻辑上相邻的元素物理上也相邻，因此，插入和删除操作需要移动大量元素。

时间复杂度：

1. 插入操作：
   最好情况–在表尾插入O(1)
   最坏情况–在表头插入O(n)
   平均情况–O(n)
2. 删除操作：
   最好情况–在表尾删除O(1)
   最坏情况–删除表头元素O(n)
   平均情况–O(n)
3. 查找操作：
   索引查找–O(1)
   按值查找–最好情况，查找元素就在表头O(1)
   最坏情况，查找元素在表尾O(n)
   平均情况O(n)

顺序表的Java实现：
接口部分：

/**
 * @author zfr
 *
 */
public interface ISeqList<T> {
    /**
     * 判断线性表是否为空
     * @return
     */
    boolean isEmpty();
    /**
     * 返回线性表的长度
     * @return
     */
    int length();
    /**
     * 返回第i（i>=0）个元素
     * @param i
     * @return
     */
    T get(int i);
    /**
     * 设置第i个元素的值
     * @param i
     * @param x
     */
    void set(int i,T x);
    /**
     * 插入x作为第i个元素
     * @param i
     * @param x
     */
    void insert(int i,T x);
    /**
     * 在线性表尾部添加元素x
     * @param x
     */
    void append(T x);
    /**
     * 删除第i个元素，并返回该元素的值
     * @param i
     * @return
     */
    T remove(int i);
    /**
     * 删除所有元素
     */
    void removeAll();
    /**
     * 查找并返回首次出现元素key的位置
     * @param key
     * @return
     */
    int search(T key);
    /**
     * 打印线性表
     */
    void print();
}

实现部分：

package 线性表;

public class SeqList<T> implements ISeqList<T> {
    /**
     * 成员变量 表示表的长度
     */
    protected int length;
    /**
     * 成员变量，对象数组
     */
    protected Object[] data;
    /**
     * 默认构造函数，创建默认容量的空表
     */
    public SeqList() {
        // TODO Auto-generated constructor stub
        this(20);
    }
    /**
     * 构造方法，创建容量为size的表
     * @param size
     */
    public SeqList(int size) {
        // TODO Auto-generated constructor stub
        this.data=new Object[size];//创建长度为size的数组
        this.length = 0;//初始长度为0
    }
    /**
     * 判断是否为空表
     */
    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return this.length==0;
    }
    /**
     * 返回表的长度
     */
    @Override
    public int length() {
        // TODO Auto-generated method stub
        return length;
    }
    /**
     * 返回表中第i个元素的值
     */
    @SuppressWarnings("unchecked")
    @Override
    public T get(int i) {
        // TODO Auto-generated method stub
        if(i>=0 && i<length)
            return (T) data[i];
        return null;
    }
    /**
     * 设置第i个元素的值为x
     */
    @Override
    public void set(int i, T x) {
        // TODO Auto-generated method stub
        if(x==null)
            return ;
        if(i>=0 && i<length)
            data[i] = x;
        else
            throw new IndexOutOfBoundsException(i+"");//抛出越界异常
    }
    /**
     * 在第i个位置插入元素x
     */
    @Override
    public void insert(int i, T x) {
        // TODO Auto-generated method stub
        if(x==null)
            return;
        //数组已满 需要扩容
        if(data.length==length){
              Object[] temp = this.data;
              this.data=new Object[length*20];
              for(int j=0;j<length;j++){
                  this.data[j]=temp[j];
              }
        }
        //下标容错
        if(i<0)
            i=0;
        if(i>this.length)
            i=this.length;
        //元素后移
        for(int j=this.length;j>i;j--){
            this.data[j]=this.data[j-1];
        }
        //为第i个位置赋值
        this.data[i]=x;
        length++;
    }
    /**
     * 在末尾加入元素x
     */
    @Override
    public void append(T x) {
        // TODO Auto-generated method stub
        insert(this.length,x);
    }
    /**
     * 删除第i个位置的元素
     */
    @Override
    public T remove(int i) {
        // TODO Auto-generated method stub
        if(this.length==0||i<0||i>=this.length)
            return null;
        //记录该位置为元素
        T old = (T) this.data[i];
        for(int j=i;j<length-1;j++){
            this.data[j]=this.data[j+1];
        }
        this.length--;
        return old;
    }
    /**
     * 删除所有元素
     */
    @Override
    public void removeAll() {
        // TODO Auto-generated method stub
        this.length=0;
    }
    /**
     * 查找元素key第一次出现的位置
     */
    @Override
    public int search(T key) {
        // TODO Auto-generated method stub
        for(int i=0;i<length;i++)
        {
            if(this.data[i].equals(key))
                return i;
        }
        return -1;
    }
    /**
     * 打印顺序表
     */
    @Override
    public void print() {
        // TODO Auto-generated method stub
        for(int i=0;i<length;i++){
            System.out.print(this.data[i]+" ");
        }
        System.out.println();
    }
    /**
     * 比较两个顺序表是否相等
     */
    @Override
    public boolean equals(Object obj) {
        // TODO Auto-generated method stub
        return super.equals(obj);
    }
    /**
     * 将顺序表转换为字符串
     */
    @Override
    public String toString() {
        // TODO Auto-generated method stub
        String str="";
        if(this.length>0)
            str+=this.data[0].toString();
        for(int i=1;i<this.length;i++)
            str+=","+this.data[i].toString();
        return str;
    }

}