疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

顺序表 Java实现


 

   

  顺序表: 线性表的顺序表是,指的是用一组地址连续的存储单元一次存储线性表的数据元素。以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。只要确定了存储线性表的起始位置,线性表中任何一数据元素都可以随机存取,所以线性表的存储结构是一种随机存取的存储结构。

  由于高级程序设计语言中的数组类型也具有随机存取的特性,因此,通常都用数组来描述数据结构中的顺序存储结构。

  优点——随机存储,读取数据的速度快

  缺点——顺序存储,当需要增加、删除数据是慢

  这里写代码片

  package ds.linerlist;

  /**

  * 顺序表的实现

  * @author Bao Yiming

  * @param

  */

  public class ArrayList {

  private Object[] data = null; // data: 用来保存此线性表数据的数组

  private int capacity; // capacity: 线性表的容量

  private int current; // current: 当前数据的下标

  /**

  * 初始化为声明大小,则设置为10。

  */

  ArrayList() {

  this(10);

  }

  /**

  * 初始化线性表,声明保存数据的数组大小。

  * @param initialSize 顺序表的初始化大小

  */

  ArrayList(int initialSize) {

  if (initialSize >= 0) {

  this.capacity = initialSize;

  data = new Object[initialSize];

  current = 0;

  } else {

  throw new RuntimeException(“初始化大小不能小于0:” + initialSize);

  }

  }

  /**

  * 在线性表的末尾添加元素,添加之前确认线性表是否已满

  * @param e 待加入的元素

  * @return

  */

  public boolean AddElement(E e) {

  ensureCapacity();

  data[current] = e;

  ++current;

  return true;

  }

  /**

  * 检查存储数据的数组容量,如果数组已经满,则扩充容量;否则不操作。

  */

  private void ensureCapacity() {

  int index;

  if (current == capacity) {

  capacity *= 2;

  Object[] newData = new Object[capacity];

  for(index = 0; index < current; ++index) {

  newData[index] = data[index];

  }

  data = newData;

  }

  }

  /**

  * 返回下标为index的元素

  * @param index 欲取得元素的下标

  * @return

  */

  public E get(int index) {

  validateIndex(index);

  return (E) data[index];

  }

  /**

  *

  * @param index 待插入的位置

  * @param e 待插入的元素

  * @return

  */

  public boolean set(int index, E e) {

  validateIndex(index);

  data[index] = e;

  return true;

  }

  /**

  * 验证下标值是否合法,非法时抛出异常

  * @param index 待验证的下标值

  */

  private void validateIndex(int index) {

  if (index < 0 || index > current) {

  throw new RuntimeException(“无效的下标:” + index);

  }

  }

  /**

  * 返回当前顺序表的大小

  * @return

  */

  public int size() {

  return current;

  }

  /**

  * 在指定位置插入指定元素

  * @param index 待插入的位置

  * @param e 待插入的元素

  * @return

  */

  public boolean insert(int index, E e) {

  validateIndex(index);

  ensureCapacity();

  for (int temp = current; temp > index; –temp) {

  data[temp] = data[temp - 1];

  }

  data[index] = e;

  return true;

  }

  /**

  * 删除下标为index元素

  * @param index 待删除元素的下标

  * @return

  */

  public boolean delete(int index) {

  validateIndex(index);

  for ( ; index < current - 1; ++index) {

  data[index] = data[index + 1];

  }

  data[current - 1] = null;

  –current;

  return true;

  }

  @Override

  public String toString() {

  String str = “[ “;

  for (Object o : data) {

  if (o != null) {

  str += o + ” “;

  }

  }

  str += “]”;

  return str;

  }

  }