疯狂java


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

Java实现线性表


 

      //看大话数据结构,开始学习数据结构,并一步一步的实现

  public class LinearListMain {

  public static void main(String[] args) {

  JavaLinearList list = new JavaLinearList();

  list.addElement("A");

  list.addElement("B");

  list.addElement("C");

  list.addElement("D");

  list.addElement("E");

  list.addElement("F");

  list.addElement(0,"Zero");

  list.addElement(90,"G");

  System.out.println("list.length=="+list.getLength());

  System.out.println("list========="+list.toString());

  list.removeElement();

  list.removeElement(90);

  list.removeElement(-20);

  System.out.println("--------after remove----------");

  System.out.println("list.length=="+list.getLength());

  System.out.println("list========="+list.toString());

  System.out.println("Element at 3 is "+ list.getElement(3));

  list.setElement(1,"A");

  System.out.println("--------after SET----------");

  System.out.println("list.length=="+list.getLength());

  System.out.println("list========="+list.toString());

  list.clear();

  System.out.println("lis is empty? "+list.isEmpty());

  System.out.println("list.length=="+list.getLength());

  System.out.println("list========="+list.toString());

  }

  }

  interface LinearList {

  public int getLength(); //获取当前线性表的实际长度

  public boolean addElement(T e); //在表尾插入数据元素

  public boolean addElement(int index,T e); //在指定位置插入数据元素

  public T removeElement();//删除表尾的数据元素,并将原数据元素返回给T

  public T removeElement(int index); //删除指定位置的数据元素,并将原数据元素返回给T

  public T setElement(int index,T t);//修改指定位置数据元素的值

  public T getElement(int index);//查看指定位置的数据元素

  public void clear();//清空线性表

  public boolean isEmpty();//判断该线性表是否为空表

  // public void sort(); //由时间研究下如何排序

  }

  class JavaLinearList implements LinearList {

  private int length; //线性表的实际长度

  private T[] data;//用数组做容器

  /**

  *创建一张容量为20的线性表

  */

  JavaLinearList() {

  this(20);

  }

  /**

  *@param int 创建长度为size的线性表,参数不能为负,否则程序停止执行

  */

  JavaLinearList(int size) {

  if(size <= 0) {

  System.out.println("表的长度应该 > 0");

  System.exit(-1);

  return;

  }

  this.length = 0;

  data = (T[])new Object[size];

  }

  /**

  *@return int 返回该线性表当前包含的所有数据元素个数

  */

  public int getLength() {

  return this.length;

  }

  public boolean addElement(T e) {

  return addElement(this.length+1,e);

  }

  public boolean addElement(int index, T e) {

  if(e == null)

  return false;

  //如果该线性表已满,那么按原长度的一半扩容

  if(this.length == data.length) {

  T[] temp = data;

  data = (T[])new Object[data.length+data.length>>2];

  for(int k = 0;k < temp.length; k++) {

  data[k] = temp[k];

  }

  }

  //如果指定插入位置大于当前表的实际长度,默认从表尾位置插入数据元素

  if(index > this.length) {

  index = this.length;

  }

  //如果指定位置小于表的实际长度,那么从最后一个数据元素开始依次向后移一位,直到index

  if(index < this.length) {

  //如果指定插入位置是负数,默认从第一个位置插入数据元素

  if(index < 0)

  index = 0;

  for(int i = this.length; i >= index ; i--) {

  // System.out.println(i);

  data[i + 1] = data[i];

  }

  }

  data[index] = e;

  this.length++;

  return true;

  }

  public T removeElement() {

  return removeElement(this.length);

  }

  public T removeElement(int index) {

  if(this.length == 0) {

  System.out.println("当前线性表是空表");

  return null;

  }

  T e = (T)new Object();

  if(index > this.length) {

  index = this.length;

  e = data[index];

  }

  if(index < this.length) {

  if(index < 0)

  index = 0;

  e = data[index];

  for(int i = 0; i < this.length; i++) {

  data[i] = data[i+1];

  }

  }

  this.length--;

  return e;

  }

  public T getElement(int index) {

  T t = (T)new Object();

  if(index > this.length)

  index = this.length;

  if(index < this.length) {

  if(index < 0)

  index = 0;

  t = data[index];

  }

  return t;

  }

  public T setElement(int index,T e) {

  if(index >= 0 && index <= this.length && e != null) {

  T t = (T)new Object();

  t = data[index];

  data[index] = e;

  return t;

  }else {

  return null;

  }

  }

  public void clear() {

  for(int k = 0; k < this.length; k++) {

  data[k] = null;

  }

  data = null;

  this.length = 0;

  }

  public boolean isEmpty() {

  return this.length == 0;

  }

  public String toString() {

  StringBuffer str = new StringBuffer();

  for(int k = 0;k < this.length;k++) {

  str.append(data[k].toString()+" ");

  }

  return "[ "+str+"]";

  }

  }

  线性顺序表的优缺点总结:

  元素的存储与读取时间复杂度都是O(1),插入、删除操作的时间复杂度都是O(N),所以线性顺序表比较适合元素个数不太变化,而更多是存取数据的应用。

  优点:

  1、无须为表示表中元素之间的逻辑关系而增加额外的存储空间

  2、可以快速地存取表中任一位置的元素

  缺点:

  1、插入和删除操作需要移动大量的元素

  2、当线性表的长度变化较大时,难以确定存储空间的容量

  3、造成存储空间的“碎片”