首页 > 代码库 > 数据结构之线性表-顺序存储
数据结构之线性表-顺序存储
本人文笔较差，语文从来不及格，基础不好，写此类文章仅供自己学习，理解队列及其他知识，高手大神请略过。参考书籍 《数据结构与算法分析-Java语言描述》
1.1 线性表简介
线性表是0个或多个元素的有限序列。即元素之间有顺序且有限。假设表中有元素A1，A2，A3，....，AN，若存在1<i<N,则 Ai 是 Ai-1的直接后继，Ai-1 是Ai的直接前驱。作为线性表，必须满足A1没有前驱，AN没有后继（有限性）。N是线性表的长度。当N=0时，即表中没有任何元素也即空表。
1.2 线性表的顺序存储
在内存中用一段地址连续的存储单元依次存储线性表的数据元素。如每天上下班挤地铁排成一条长队，有时候几个要好的同事接连的站在一起。其他人就占据不了这几个位置了。转换成计算机语言就是在内存中找了一块地儿，把这段内存空间给占了，然后把相同数据类型的元素（暂且理解成通用Object类型）放在这块儿地儿。用数组实现，第一个人就存储在下标是0的那个位置，线性表的长度就是人数。此时在等地铁的时候又遇到一个同事，我们让他(她)跟我们一起，于是线性表的长度就加了1，但是事先已经定义了数组的长度，即内存中只占了我们几个人空间，这时有个同事看向左侧一排发现没人，就带着我们过去排队，然后我们都能排在一起了。即重新定义了数组，内存中多占了块儿地儿。另一种情况是，突然有个同事内急去上厕所，我们就多余占了一个位置。即线性表的长度是不断变化的，而数组要预先占好足够多的空间。所以线性表的长度总是小于或等于数组的长度。
存储器中的每个存储单元都有自己的编号，当在没有重写toString方法时，打印一个实例得到的结果，即内存地址。确定任何一个元素位置了，就可以通过编号计算其他任意元素的位置了。即它获取元素的时间复杂度是O(1)。
假设之前那个同事占据了好几十个人的空间，我们只有m个人现在考虑前面的插入问题即突然又来了一位同事，若插在最后一个同事位置后面（这里假设它站过来需要t时间，t是个固定常数），这时其他同事都不用动，时间复杂度即是常数O(1),若插在中间的某个位置k(0<k<m)，则k之前的同事也不用动，但是k之后的m-k个同事每一个都要向后挪一位，用时(m-k)*t的时间，最费时情况的是他（她）若插到最前面的那个同事前面，我们每一个人都将向后挪动一个位置将耗时m*t，所以平均耗时m*t/2, 平均时间复杂度即O(N)，N是规模，这里是同事的人数m。当然移除元素即每个元素向前挪，和插入一样，平均时间复杂度都是O(N)。
至此，就明白了，基本的线性表顺序存储(其实其他结构的存储也是)就包括插入，删除，获取元素及获取表的长度的几个操作。Java代码的简单实现：
/** * Created with IntelliJ IDEA. * CreateUser: blentle * Email: renhuan@milipp.com * CreateTime: 2014/11/6 12:40 * ModifyUser: blentle * ModifyTime: 2014/11/6 12:40 * Class Description: * To change this template use File | Settings | File Templates. */public class SequenceList<T> { //不指定存储空间时的默认存储，操作时越界暂时将抛出异常 private static final int DEFAULT_CAPACITY = 10; //线性表的最大长度（数组的长度） private int capacity; //线性表元素的个数 private int size; //存储线性表元素的数组 private Object[] elementData; /** * 使用默认的最大存储空间，超过最大存储空间将抛出异常 */ public SequenceList() { this(DEFAULT_CAPACITY); } /** * * @param initialCapacity 最大存储空间初始化 */ public SequenceList(int initialCapacity) { this.capacity = initialCapacity; this.elementData = http://www.mamicode.com/new Object[capacity]; } /** * * @return 线性表的长度 */ public int size() { return this.size; } /** * * @return 线性表是否是空表 */ public boolean isEmpty() { return this.size == 0; } /** * 获取元素 * @param index * @return T */ public T get(int index) { //检查序号是否越界,注意inde是从0开始 if(index >= size) { throw new IndexOutOfBoundsException("index is :"+ index + "but size is:" + this.size); } return elementData(index); } public boolean add(int index,T element) { //检查序号是否越界,注意inde是从0开始,最大值是size-1 if(index > size || index < 0) { throw new IndexOutOfBoundsException("index is :"+ index + ",but size is:" + this.size); } //若链表已满(元素个数等于数组初始化最大容量，一般ArrayList继续扩展容量，这里抛出异常) if(size == capacity) { throw new IndexOutOfBoundsException("list is full..."); } if(index == size) { //插在表尾 elementData[size] = element; } else { //插在其他地方，index后面的的每一个元素向后挪一位 for(int i = size + 1 ; i > index ; i--) { elementData[i] = elementData[i-1]; } } //index位置被替换成element elementData[index] = element; size++; return true; } /** * 不指定插入位置，插入表尾 * @param t 链表元素 * @return */ public boolean add(T t) { return add(size,t); } /** * 从表中移除元素 * @param index 元素序号 * @return */ public boolean remove(int index) { if(index >= size || index < 0) { throw new IndexOutOfBoundsException("index is :"+ index + ",but size is:" + this.size); } for(int k = index ; k < size - 1 ; k++) { elementData[k] = elementData[k + 1]; } elementData[size - 1] = null; size--; return true; } /** * 清空线性表 */ public void clear() { if(size > 0) { for(int i = 0 ; i < size ; i ++) { elementData[i] = null; } size = 0; } } @Override public String toString() { String a = ""; for(int i = 0 ; i < size() ; i ++) { a += (T)elementData[i] + " "; } return a; } /** * 获取元素并强制转换的封装（参考ArrayList源码） * @param index * @return */ private T elementData(int index) { return (T) elementData[index]; }}
1.3 从代码可以看出线性表的特点
- 快速地从表中获取任意位置的元素。
- 插入和删除操作需要移动大量的元素。
- 当表的长度变化比较大时，不太好确定存储空间的容量（数组的初始化大小）
数据结构之线性表-顺序存储