java 线性表数据表示形式(源代码)

1.import java.util.Arrays;   
2.   
3.public class SequenceList<T>   
4.{   
5.    private int DEFAULT_SIZE = 16;   
6.    //保存数组的长度。   
7.    private int capacity;   
8.    //定义一个数组用于保存顺序线性表的元素   
9.    private Object[] elementData;   
10.    //保存顺序表中元素的当前个数   
11.    private int size = 0;   
12.    //以默认数组长度创建空顺序线性表   
13.    public SequenceList()   
14.    {   
15.        capacity = DEFAULT_SIZE;   
16.        elementData = new Object[capacity];   
17.    }   
18.    //以一个初始化元素来创建顺序线性表   
19.    public SequenceList(T element)   
20.    {   
21.        this();   
22.        elementData[0] = element;   
23.        size++;   
24.    }   
25.    /**  
26.     * 以指定长度的数组来创建顺序线性表  
27.     * @param element 指定顺序线性表中第一个元素  
28.     * @param initSize 指定顺序线性表底层数组的长度  
29.     */   
30.    public SequenceList(T element , int initSize)   
31.    {   
32.        capacity = 1;   
33.        //把capacity设为大于initSize的最小的2的n次方   
34.        while (capacity < initSize)   
35.        {   
36.            capacity <<= 1;   
37.        }   
38.        elementData = new Object[capacity];   
39.        elementData[0] = element;   
40.        size++;   
41.    }   
42.    //获取顺序线性表的大小   
43.    public int length()   
44.    {   
45.        return size;   
46.    }   
47.    //获取顺序线性表中索引为i处的元素   
48.    public T get(int i)   
49.    {   
50.        if (i < 0 || i > size - 1)   
51.        {   
52.            throw new IndexOutOfBoundsException("线性表索引越界");   
53.        }   
54.        return (T)elementData[i];   
55.    }   
56.    //查找顺序线性表中指定元素的索引   
57.    public int locate(T element)   
58.    {   
59.        for (int i = 0 ; i < size ; i++)   
60.        {   
61.            if (elementData[i].equals(element))   
62.            {   
63.                return i;   
64.            }   
65.        }   
66.        return -1;   
67.    }   
68.    //向顺序线性表的指定位置插入一个元素。   
69.    public void insert(T element , int index)   
70.    {   
71.        if (index < 0 || index > size)   
72.        {   
73.            throw new IndexOutOfBoundsException("线性表索引越界");   
74.        }   
75.        ensureCapacity(size + 1);   
76.        //将index处以后所有元素向后移动一格。   
77.        System.arraycopy(elementData , index , elementData   
78.             , index + 1 , size - index);   
79.        elementData[index] = element;   
80.        size++;   
81.    }   
82.    //在线性顺序表的开始处添加一个元素。   
83.    public void add(T element)   
84.    {   
85.        insert(element , size);   
86.    }   
87.    //很麻烦，而且性能很差   
88.    private void ensureCapacity(int minCapacity)   
89.    {   
90.        //如果数组的原有长度小于目前所需的长度   
91.        if (minCapacity > capacity)   
92.        {   
93.            //不断地将capacity * 2，直到capacity大于minCapacity为止   
94.            while (capacity < minCapacity)   
95.            {   
96.                capacity <<= 1;   
97.            }   
98.            elementData = Arrays.copyOf(elementData , capacity);//此方法jdk1.6开始提供   
99.        }   
100.    }   
101.    //删除顺序线性表中指定索引处的元素   
102.    public T delete(int index)   
103.    {   
104.        if (index < 0 || index > size - 1)   
105.        {   
106.            throw new IndexOutOfBoundsException("线性表索引越界");   
107.        }   
108.        T oldValue = (T)elementData[index];   
109.        int numMoved = size - index - 1;   
110.        if (numMoved > 0)   
111.        {   
112.            System.arraycopy(elementData , index+1   
113.                , elementData, index ,  numMoved);   
114.        }   
115.        //清空最后一个元素   
116.        elementData[--size] = null;    
117.        return oldValue;   
118.    }   
119.    //删除顺序线性表中最后一个元素   
120.    public T remove()   
121.    {   
122.        return delete(size - 1);   
123.    }   
124.    //判断顺序线性表是否为空表   
125.    public boolean empty()   
126.    {   
127.        return size == 0;   
128.    }   
129.    //清空线性表   
130.    public void clear()   
131.    {   
132.        //将底层数组所有元素赋为null   
133.        Arrays.fill(elementData , null);   
134.        size = 0;   
135.    }   
136.    public String toString()   
137.    {   
138.        if (size == 0)   
139.        {   
140.            return "[]";   
141.        }   
142.        else   
143.        {   
144.            StringBuilder sb = new StringBuilder("[");   
145.            for (int i = 0 ; i < size ; i++ )   
146.            {   
147.                sb.append(elementData[i].toString() + ", ");   
148.            }   
149.            int len = sb.length();   
150.            return sb.delete(len - 2 , len).append("]").toString();   
151.        }   
152.    }   
153.       
154.    public static void main(String[] args)    
155.    {   
156.        SequenceList<String> list = new SequenceList<String>();   
157.        list.add("aaaa");   
158.        list.add("bbbb");   
159.        list.add("cccc");   
160.        //在索引为1处插入一个新元素   
161.        list.insert("dddd" , 1);   
162.        //输出顺序线性表的元素   
163.        System.out.println(list);   
164.        //删除索引为2处的元素   
165.        list.delete(2);   
166.        System.out.println(list);   
167.        //获取cccc字符串在顺序线性表中的位置   
168.        System.out.println("cccc在顺序线性表中的位置："    
169.            + list.locate("cccc"));   
170.    }   
171.}