大话数据结构一：线性表的顺序存储结构

大话数据结构一：线性表的顺序存储结构2014-12-281. 线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。

2. Java实现线性表的顺序存储结构：

// 顺序存储结构public class SequenceList {private static final int DEFAULT_SIZE = 10; // 默认初始化数组大小private int size; // 当前数组大小private static Object[] array;public SequenceList（） {init（DEFAULT_SIZE）;}public SequenceList（int size） {init（size）;}// 初始化数组大小public void init（int size） {this.size = 0;array = new Object[size];}public void add（int index, Object obj） {checkSize（index）;if （size == array.length） {// 判断size如果等于length, 说明原数组装满了Object[] newArray = new Object[array.length * 3 / 2 + 1];//创建一个更大的数组System.arraycopy（array, 0, newArray, 0, array.length）;//将原有数据复制到新数组array = newArray; // array指向新数组}for （int j = size; j > index; j--） {array[j] = array[j - 1]; // 将要插入位置后的数据元素往后移动一位}array[index] = obj;size++;}// 删除一个元素public void remove（int index） {if （size == 0） {throw new RuntimeException（"list已空"）;}checkSize（index）;for （int j = index; j < size - 1; j++） {array[j] = array[j + 1];}size--;}// 通过索引获取元素public Object get（int index） {checkSize（index）;return array[index];}// 显示所有元素public void display（） {for （int i = 0; i < size; i++） {System.out.print（" " + array[i]）;}}// 获取列表长度public int size（） {return size;}// 列表是否为空public boolean isEmpty（） {return size == 0;}private void checkSize（int index） {if （index < 0 || index > size） // 判断如果获取的index越界, 抛出异常throw new IndexOutOfBoundsException（"Index: " + index + ", Size: " + size）;}}

// 测试程序public class SequenceTest {public static void main（String[] args） {SequenceList seqList = new SequenceList（）;seqList.add（0, 1）;seqList.add（1, 2）;seqList.add（2, 3）;seqList.add（3, 4）;seqList.add（4, 5）;seqList.add（5, 6）;seqList.add（6, 7）;seqList.add（7, 8）;seqList.add（8, 9）;seqList.add（9, 10）;seqList.add（10, 11）;seqList.add（11, 12）;seqList.display（）;System.out.println（）;seqList.remove（1）;seqList.display（）;}}

3. 插入和删除的时间复杂度：

元素插入到第i个位置或者删除第i个元素，需要移动n-i个元素，根据概率原理，每个位置插入或删除元素的可能性是相同的，为（n-1）/ 2。平均的时间复杂度为O（n）

4. 线性表顺序存储的优缺点：

优点：无须为表中元素逻辑关系而增加额外的存储空间，同时可以快速存取表中任一位置的元素。

缺点：插入和删除操作需要移动大量的元素，当线性表长度变化较大时，难以确定存储空间的容量。

作者：csdn博客 zdp072