线性表的顺序存储结构,也称为顺序表,指用一段连续的存储单元依次存储线性表中的数据元素。
根据顺序表的特性,我们用数组来实现顺序表,下面是我通过数组实现的Java版本的顺序表。
package com.phn.datestructure; /** * @author 潘海南 * @Email 1016593477@qq.com * @TODO 顺序表 * @date 2015年7月16日 */ public class FOArrayList<E> { // 顺序表长度 private int size; // 顺序表默认数组为null private Object[] data = null; // 顺序表中数组的初始化长度 private int capacity; // 顺序表默认初始化长度 private static final int DEFUALT_INITIAL_SIZE = 0; /** * 默认无参构造函数 */ public FOArrayList() { this(DEFUALT_INITIAL_SIZE); } /** * @TODO 带参构造函数 * @param initialSize 初始化顺序表长度 */ public FOArrayList(int initialSize) { if (initialSize < 0) { throw new RuntimeException("数组大小错误:" + initialSize); } this.data = new Object[initialSize]; this.capacity = initialSize; this.setSize(); } /** * @TODO 设置顺序表的长度 */ private void setSize() { this.size = 0; } /** * @TODO 获取顺序表的长度 * @return size 顺序表的长度 */ public int size() { return this.size; } /** * @TODO 顺序表添加元素 * @param e 数据元素类型 * @return true */ public boolean add(E e) { ensureSize(size); this.data[size] = e; this.size++; return true; } /** * @TODO 顺序表插入元素 * @param index 插入位置 * @param e 数据元素类型 * @return true */ public boolean insert(int index, E e) { if (index >= 0 && index <= size) { ensureSize(size); E temp = (E) this.data[index - 1]; this.data[index - 1] = e; this.size++; for (int i = index; i <= size; i++) { E temp2 = (E) this.data[i]; this.data[i] = temp; temp = temp2; } } else { throw new RuntimeException("数组下标错误:" + index); } return true; } /** * @TODO 顺序表删除元素 * @param index 将要删除的元素的索引位置 * @return E 删除的元素 */ public E remove(int index) { validateIndex(index); E e = (E) this.data[index]; for (int i = index; i < size - 1; i++) { this.data[i] = this.data[i + 1]; } this.size--; return e; } /** * @TODO 根据元素索引位置获取元素 * @param index 元素的索引位置 * @return E 元素e */ public E get(int index) { validateIndex(index); return (E) this.data[index]; } /** * @TODO 将顺序表中索引位置为i的元素修改为元素e * @param index 元素的索引位置 * @param e 需要修改成的元素 * @return true 修改成功标志 */ public boolean set(int index, E e) { validateIndex(index); this.data[index] = e; return true; } @Override public String toString() { return this.arrayToString(data); } /** * @TODO 获取字符串形式的顺序表中的数组序列 * @param a 顺序表中的数组 * @return String 字符串形式的顺序表中的数组序列 */ private String arrayToString(Object[] a) { if (a == null) return "null"; int iMax = this.size - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0;; i++) { b.append(String.valueOf(a[i])); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * @TODO 验证所给索引位置是否合法 * @param index 给出的索引位置 */ private void validateIndex(int index) { if (index >= this.size || index <= 0) { throw new RuntimeException("数组下标错误:" + index); } } /** * @TODO 判断是否需要扩充顺序表容量 * @param currentSize 当前顺序表的大小 */ private void ensureSize(int currentSize) { if (currentSize == capacity) { this.capacity = (this.capacity * 3) / 2 + 1; Object[] newData = new Object[this.capacity]; for (int i = 0; i < currentSize; i++) { newData[i] = this.data[i]; } this.data = newData; } } }主要注意上述3个私有成员变量,如下:
// 顺序表长度 private int size; // 顺序表中数组的初始化长度 private int capacity; // 顺序表默认数组为null private Object[] data = null;如同注释解释的那样,size用来表示顺序表的长度,data用来表示数组,而capacity用来表示数组的长度.
相信data应该比较好理解,而对应的两个长度变量相对难理解一些,下面解释一下:
size指的是对外界访问这个顺序表的长度时展示的值,是顺序表中数据元素的个数,随顺序表插入和删除操作而会进行改变;
capacity表示的是data数组的长度,实际上也是整个顺序表的容量,在顺序表初始化的时候可以赋值,或者之后可以调用顺序表的扩容来进行改变;
size是小于等于capacity的。
这里主要讲讲顺序表的插入和删除:
顺序表的插入演示如图所示:
根据图片可以看出插入一个元素后,插入位置之后的元素都需要向后移动一个位置。
删除操作则是插入操作的逆过程,删除位置之后的元素都需要向前移动一个位置。
时间复杂度分析:
在顺序表进行存入,查找和修改时,平均时间复杂度都是O(1);
而在进行插入和删除操作时,最快时为O(1),最慢时为O(n),所以平均时间复杂度为O(n)。
解释:上述的存入和插入有区别,存入表示存储在数组末尾,而插入表示插入在任意位置。
优缺点分析:
优点:
不用为表示表中数据元素之间的逻辑关系而增加额外的存储空间;
可以快速的存取表中任意位置的元素。
缺点:
插入和删除操作需要移动大量元素;
当线性表的长度变化较大的时候,很难确定存储空间的容量;
容易造成存储空间的“碎片”。