一、线性表

　　1，什么是线性表

　　线性表就是零个或多个数据元素的有限序列。线性表中的每个元素只能有零个或一个前驱元素，零个或一个后继元素。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。比如牵手排队的小朋友，可以有学号、姓名、性别、出生日期等数据项。

　　2，线性表的抽象数据类型

　　线性表的抽象数据类型定义如下。

复制代码
ADT List Data     线性表的数据对象集合为{a1,a2,...,a3},每个元素的类型均为DataType Operation     InitList (L) : 初始化操作，建立一个空的线性表L     ListEmpty (L) : 若线性表为空，则返回true，否则返回false     ClearList(L）: 清空线性表     GetElem(L,i,e): 将线性表L中的第i个位置元素值返回给e     LocateElem(L,e): 在L中查找与给定值e相等的元素，若查找成功，返回位                                        序；若查找失败，返回0     ListInsert(L,i,e): 在L中的第i个位置插入新元素e     ListDelete(L,i,e): 删除线性表L中的第i个未知元素，并通过e返回其值     ListLength(L): 返回L中的元素个数 endADT
复制代码

　　上述操作是最基本的，对于实际中涉及的线性表有更复杂的操作，但一般可以用上述简单操作的组合来完成，例如我们来思考将线性表A和B组合，实现并集操作，只要循环B中的元素，判断该元素是否在A中，若不存在，插入A即可，实现如下。

复制代码
public class ListDemo {     public static void main(String[] args){         List<String> ListA = new ArrayList<String>();         List<String> ListB = new ArrayList<String>();          ListA.add("zhang");         ListA.add("li");         ListA.add("wang");          ListB.add("zhang");         ListB.add("li");         ListB.add("liu");          for (String name: ListB              ) {             if (!ListA.contains(name)){                 ListA.add(name);             }         }         System.out.println(ListA.toString());     } }
复制代码

二、线性表的顺序存储结构

　　1，顺序存储结构的实现

　　可以用一维数组来实现顺序存储结构。描述顺序存储结构需要三个属性：

　　　　1，存储空间的起始位置：即数组的存储位置

　　　　2，线性表的最大存储容量：数组初始化的长度

　　　　3，线性表的当前长度

　　

 

 

 　　2，顺序存储结构的泛型实现

 

　　

复制代码
package List;

import java.util.Iterator;
import java.util.List;

public class ArrayListDemo<T> {
    //初始化后可存放的数量，从1开始计数
    private int capacity;
    //private T[] data; 不能构造泛型数组，我们用Object[]
    private Object[] data;
    //已存的数量，从0开始计数。 当size == capacity 时，满。 size = index + 1.
    private int size;
    private static int DEFAULT_CAPACITY = 10;

    /**
     * 自定义顺序存储线性表的构造函数
     * @param capacity 数组的初始化长度
     */
    public ArrayListDemo(int capacity) {
        //下面写法会报错。因为Java中不能使用泛型数组，有隐含的ClassCastException
        //date = new T[length];
        //那么JDK中的ArrayList是怎么实现的？
        //JDK中使用Object[]来初始化了表
        if (capacity > 0){
            this.capacity = capacity;
            this.data = new Object[capacity];
            size = 0;
        }else {
            throw new IndexOutOfBoundsException("长度不合法");
        }