当前位置： 移动技术网 > IT编程>开发语言>Java > java数据结构实现顺序表示例

java数据结构实现顺序表示例

2019年07月22日  | 移动技术网IT编程  | 我要评论

复制代码 代码如下:

import java.util.arrays;
/**
 * 顺序线性表的实现
 */
public class linelist<e>{

 private int size;   //长度
 private object[] array;  //底层数组
 private final int default_length=16; //默认长度
 /**
  * 无参构造方法
  */
 public linelist(){
  size = 0;
  //使用默认长度构造数组
  array = new object[default_length];
 }
 /**
  * 指定长度进行构造
  * @param length 指定初始长度
  */
 public linelist(int length){
  if(length<0){
   throw new illegalargumentexception("初始长度不合法:"+length);
  }
  //使用指定长度构造数组
  array = new object[length];
 }

 /**
  * 指定初始化元素和长度进行构造
  * @param element 初始化元素
  * @param length 初始化长度
  */
 public linelist(e element,int length){
  if(length<1){
   throw new illegalargumentexception("初始长度不合法:"+length);
  }
  //使用指定长度构造数组
  array = new object[length];
  //初始化第一个元素
  array[0] = element;
  size++;
 }
 /**
  * 指定初始化元素进行构造
  * @param element 初始化元素
  */
 public linelist(e element){
  //使用默认长度初始化数组
  array = new object[default_length];
  //初始化第一个元素
  array[0] = element;
 }

 /**
  * 获取元素个数
  */
 public int size() {
  return size;
 }

 /**
  * 判断是否为空
  */
 public boolean isempty() {
  return size==0;
 }

 /**
  * 判断是否包含此元素
  */
 public boolean contains(e e) {
  if(indexof(e) == -1){
   return false;
  }
  return true;
 }

 /**
  * 格式化为数组
  */
 public object[] toarray() {
  return arrays.copyof(array, size);
 }

 /**
  * 向线性表尾部添加一个元素
  * @param e
  * @return
  */
 public void add(e e) {
  extendcapacity(size+1);
  array[size]=e;
  size++;
 }

 /**
  * 扩容
  * @param length 需要的长度
  */
 private void extendcapacity(int length){
  //当前数组长度和需要的长度取最大
  int mincapacity = math.max(array.length, length);
  //判断是否需要扩容
  if(mincapacity - array.length>0){
   //数组长度增加一半
   int newlength = array.length + array.length/2;
   //如果新的长度还比需求要小,将需求的长度作为数组长度
   if(newlength < mincapacity){
    newlength=mincapacity;
   }
   //数组长度不能超过integer.max_value
   if(newlength > integer.max_value - 8){
    newlength = integer.max_value;
   }
   //数组扩容
   array = arrays.copyof(array, newlength);
  }
 }
 /**
  * 从线性表中移除所有此元素
  * @param e 需要移除的元素
  * @return
  */
 public void removeall(e e) {
  if(e==null){
   for(int i=0;i<size;i++){
    if(array[i]==null){
     fastremove(i);
    }
   }
  }else{
   for(int i=0;i<size;i++){
    if(e.equals(array[i])){
     fastremove(i);
    }
   }
  }
 }

 /**
  * 删除索引处元素,后面的元素依次前移
  * @param index 需要删除的索引
  */
 private void fastremove(int index){
  if(size-index-1>0){  
   //数组从index+1开始全部前移
   system.arraycopy(array, index+1, array, index, size-1);
  }
  //最后一个元素请空
  array[--size]=null;
 }

 /**
  * 清空线性表
  */
 public void clear() {
  //将数组全部填充为null
  arrays.fill(array, null);
  //将元素个数改为0
  size=0;
 }
 /**
  * 获得索引处的元素
  * @param index
  * @return 索引处的元素
  */
 @suppresswarnings("unchecked")
 public e get(int index) {
  checkindex(index);
  return (e)array[index];
 }

 /**
  * 验证是否为索引越界
  * @param index
  */
 private void checkindex(int index){
  if(index>=size || index<0){
   throw new indexoutofboundsexception("索引越界");
  }
 }

 /**
  * 将索引处的元素修改为新的元素
  * @param index 索引位置
  * @param element 元素
  * @return 原索引处的元素
  */
 @suppresswarnings("unchecked")
 public e set(int index, e element) {
  checkindex(index);
  e e = (e)array[index];
  array[index]=element;
  return e;
 }

 /**
  * 在指定的索引处插入指定的元素
  * @param index 索引位置
  * @param element 元素
  */
 public void add(int index, e element) {
  //验证索引
  checkindex(index);
  //是否需要扩容
  extendcapacity(size+1);
  //复制数组
  system.arraycopy(array, index, array, index+1, size-index);
  array[index]=element;
 }

 /**
  * 移除索引处的元素
  * @param index 索引
  * @return 删除了的元素
  */
 @suppresswarnings("unchecked")
 public e remove(int index) {
  checkindex(index);
  //取得索引位置的元素
  e e = (e)array[index];
  fastremove(index);
  return e;
 }

 /**
  * 取得元素第一次出现的位置的索引
  * @param e 要查找的元素
  * @return 如果为-1说明线性表没有这个元素
  */
 public int indexof(e e) {
  if(e==null){
   for(int i=0;i<size;i++){
    if(e==array[i]){
     return i;
    }
   }
  }
  for(int i=0;i<size;i++){
   if(e.equals(array[i])){
    return i;
   }
  }
  return -1;
 }

 /**
  * 取得元素最后一次出现的位置的索引
  * @param e 要查找的元素
  * @return 如果为-1说明线性表没有这个元素
  */
 public int lastindexof(e e) {
  //判断元素是否为null
  if(e==null){    
   for(int i=size-1;i>=0;i--){
    if(e==array[i]){
     return i;
    }
   }
  }
  for(int i=size-1;i>=0;i--){
   //如果为null这里会跑出nullpoint异常
   //所以前面要加上验证是否为null
   if(e.equals(array[i])){
    return i;
   }
  }
  return -1;
 }

 /**
  * 截取线性表
  * @param fromindex 开始索引
  * @param toindex 结束索引
  * @return 截取的线性表
  */
 @suppresswarnings("unchecked")
 public linelist<e> sublist(int fromindex, int toindex) {
  //判断开始索引是否越界
  if(fromindex<0 || fromindex >=size){
   throw new indexoutofboundsexception("开始索引越界:"+fromindex);
  }
  //判断结束索引是否越界
  if(toindex >=size || fromindex <0){
   throw new indexoutofboundsexception("结束索引越界:"+toindex);
  }
  //判断开始索引和结束索引是否正确
  if(fromindex > toindex){
   throw new illegalargumentexception("参数不正确,开始索引应大于等于结束索引");
  }
  linelist<e> list = new linelist<e>();
  for(int i=fromindex,j=toindex;i<=j;i++){
   list.add((e)array[i]);
  }
  return list;
 }
}

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网