devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构顺序表实现_java table数据结构

作者：花生_TL007 | 2024-05-05 09:27:56

赞

踩

java table数据结构

一，创建一个带泛型的顺序表的类MyList

1，泛型：泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。

         java 中泛型标记符：

         E - Element (在集合中使用，因为集合中存放的是元素)

         T - Type（Java 类）

         K - Key（键）

         V - Value（值）

         N - Number（数值类型）

         ？ - 表示不确定的 java 类型

2，定义属性

需要定义长度为0的数组values，存储元素的个数size，数组当前长度length，默认最大容量DEFAULT_LENGTH。

  1. public class MyList<A> {
  2.     //定义属性
  3.     private Object[] values = {};//长度为零的数组
  4.     private int size;//当下坐标，当前存储的元素个数
  5.     private int length;//表示数组当前的长度 最大容器
  6.     private static final int DEFAULT_LENGTH = 10;//默认最大容量
  7. }

二，构造方法

1，顺序表初始化

传入参数为顺序表长度，如果传入长度小于0,报错，如果传入长度小于等于10，就用默认属性初始化，大于10就用传入长度初始化。

  1. public MyList (int initiallength){
  2.         if (initiallength <= 0){
  3.             throw new IllegalArgumentException("initiallength 不能小于0");
  4.         }
  5.         if (initiallength <= 10){
  6.             length = DEFAULT_LENGTH;
  7.             values = new Object[length];
  8.             size=0;
  9.         }
  10.         else{
  11.             length = initiallength;
  12.             values = new Object[length];
  13.             size=0;
  14.         }
  15.     }

2，添加元素

传入参数为添加元素，如果顺序表还有空直接添加，如果满了需要进行扩容。

扩容：以前的长度设为oldLength，定义新长度为原来的1.5倍，令以前的长度为新长度，定义一个新数组newvalues，通过循环把之前数组里的元素存进新数组里，让初始化数组values等于新数组，再把新数组清空就完成了数组扩容。

移位运算符：在Java中>、>>的区别：>表示大于，如：if(a>b)...结果是boolean类型>>表示右移，如：int i=15; i>>2的结果是3，移出的部分将被抛弃。转为二进制的形式可能更好理解，0000 1111(15)右移2位的结果是0000 0011(3)，0001 1010(18)右移3位的结果是0000 0011(3)。

  1.  //添加
  2.     public void add(A e){
  3.         //扩容
  4.         if(size == length){
  5.             grow();
  6.         }
  7.         values[size++]=e;
  8.     }
  9.  
  10.     public void grow(){
  11.  
  12.         int oldLength = length;
  13.         int newLength = oldLength + (oldLength >>1);//1.5倍
  14.         length = newLength;
  15.         Object[] newvalues = new Object[length];
  16.         for (int i = 0;i<oldLength;i++){
  17.             newvalues[i] = values[i];
  18.         }
  19.         //替换引用
  20.         values = newvalues;
  21.         newvalues=null;
  22.         System.out.println("原始容量："+oldLength+"新增容量："+newLength);
  23.     }

3，根据索引查找元素

传入参数为需要查找的索引，在范围内返回索引对应元素，不在范围报错。

  1. public A get(int index){
  2.         // 先检查
  3.         if(index>=0&&index<size){
  4.             return (A) values[index];
  5.         }else{
  6.             throw new ArrayIndexOutOfBoundsException("index 超过了范围 max:"+(size-1));
  7.         }
  8.  
  9.     }

4，根据元素查找

传入参数为查找元素，循环顺序表判断元素是否相等，返回true或false。

  1. //根据元素查询
  2.      //有还是没有
  3.     public boolean Get(Object e) {
  4.         for (int i = 0; i < length; i++) {
  5.             if (values[i] == e || values[i].equals(e)) {
  6.                 return true;
  7.             }
  8.         }
  9.         return false;
  10.     }

5，查找一段元素

传入第一个元素和最后一个元素的索引，超出范围报错，在范围内则遍历输出。

  1. //获取一段
  2.     public void getAll(int index,int last){
  3.         if(index<0||last<0||index>size-1||last>size-1){
  4.             throw new ArrayIndexOutOfBoundsException("index或last 超过了范围");
  5.         }else {
  6.             for (int i = index; i <= last; i++) {
  7.                 System.out.println(values[i]);
  8.             }
  9.         }
  10.     }

6，根据索引删除元素

传入删除元素的索引，不在范围内报错，在范围内索引对应元素令为空，通过循环前移索引后的元素。

  1. //检查范围
  2.      //将对应位置的元素 设置为null
  3.      //后置数据前移一位
  4.      //返回移除的元素对象
  5.     public A remove(int index){
  6.         if(index<0||index>size-1){
  7.             throw new ArrayIndexOutOfBoundsException("index 超过了范围 max:"+(size-1));
  8.         }else{
  9.              values[index]=null;
  10.             for(int i=index;i<size;i++){
  11.                 values[i]=values[i+1];
  12.                 }
  13.         }
  14.         return null;
  15.     }

7，删除所有相同元素

传入需要删除的元素，通过循环找到相等的元素，令为空，前移后面的元素。

  1. //找到所有的对象所在的下标位置
  2.      //分别清除之后 数据移动位置
  3.     public Object Remove(Object e){
  4.         for(int i=0;i<size;i++){
  5.             if(values[i]==e){
  6.                 values[i]=null;
  7.                 for( int x=i ;x<size;x++){
  8.                     values[x]=values[x+1];
  9.                 }
  10.             }
  11.         }
  12.         return true;
  13.     }

8，根据索引移除一段

传入删除一段的第一个元素索引和最后一个元素索引，不在范围报错，在范围最后一个元素索引后的元素前移。

  1. public void removeAll(int index,int last){
  2.         if(index<0||last<0||index>size-1||last>size-1){
  3.             throw new ArrayIndexOutOfBoundsException("index或last 超过了范围");
  4.         }else{
  5.                 int n = 1;
  6.                 for (int y=index ;y<size ;y++ ){
  7.                     values[y]=values[last+n];
  8.                     n++;
  9.                 }
  10.                 size -= (last-index)+1;
  11.         }
  12.     }

9，添加数组

传入一个数组，循环去除里面的元素依次添加，有空直接添加，没空先扩容再添加。

三，完整代码

  1. public class MyList<A> {
  2.     //定义属性
  3.     private Object[] values = {};//长度为零的数组
  4.     private int size;//当下坐标，当前存储的元素个数
  5.     private int length;//表示数组当前的长度 最大容器
  6.     private static final int DEFAULT_LENGTH = 10;//默认最大容量
  7.  
  8.     //构造方法
  9.     public MyList (int initiallength){
  10.         if (initiallength <= 0){
  11.             throw new IllegalArgumentException("initiallength 不能小于0");
  12.         }
  13.         if (initiallength <= 10){
  14.             length = DEFAULT_LENGTH;
  15.             values = new Object[length];
  16.             size=0;
  17.         }
  18.         else{
  19.             length = initiallength;
  20.             values = new Object[length];
  21.             size=0;
  22.         }
  23.     }
  24.  
  25.     //添加
  26.     public void add(A e){
  27.         //扩容
  28.         if(size == length){
  29.             grow();
  30.         }
  31.         values[size++]=e;
  32.     }
  33.  
  34.     public void grow(){
  35.  
  36.         int oldLength = length;
  37.         int newLength = oldLength + (oldLength >>1);//1.5倍
  38.         length = newLength;
  39.         Object[] newvalues = new Object[length];
  40.         for (int i = 0;i<oldLength;i++){
  41.             newvalues[i] = values[i];
  42.         }
  43.         //替换引用
  44.         values = newvalues;
  45.         newvalues=null;
  46.         System.out.println("原始容量："+oldLength+"新增容量："+newLength);
  47.     }
  48.  
  49.     public A get(int index){
  50.         // 先检查
  51.         if(index>=0&&index<size){
  52.             return (A) values[index];
  53.         }else{
  54.             throw new ArrayIndexOutOfBoundsException("index 超过了范围 max:"+(size-1));
  55.         }
  56.  
  57.     }
  58.  
  59.      //根据元素查询
  60.      //有还是没有
  61.     public boolean Get(Object e) {
  62.         for (int i = 0; i < length; i++) {
  63.             if (values[i] == e || values[i].equals(e)) {
  64.                 return true;
  65.             }
  66.         }
  67.         return false;
  68.     }
  69.  
  70.  
  71.      //获取一段
  72.     public void getAll(int index,int last){
  73.         if(index<0||last<0||index>size-1||last>size-1){
  74.             throw new ArrayIndexOutOfBoundsException("index或last 超过了范围");
  75.         }else {
  76.             for (int i = index; i <= last; i++) {
  77.                 System.out.println(values[i]);
  78.             }
  79.         }
  80.     }
  81.      //检查范围
  82.      //将对应位置的元素 设置为null
  83.      //后置数据前移一位
  84.      //返回移除的元素对象
  85.     public A remove(int index){
  86.         if(index<0||index>size-1){
  87.             throw new ArrayIndexOutOfBoundsException("index 超过了范围 max:"+(size-1));
  88.         }else{
  89.              values[index]=null;
  90.             for(int i=index;i<size;i++){
  91.                 values[i]=values[i+1];
  92.                 }
  93.         }
  94.         return null;
  95.     }
  96.  
  97.      //找到所有的对象所在的下标位置
  98.      //分别清除之后 数据移动位置
  99.     public Object Remove(Object e){
  100.         for(int i=0;i<size;i++){
  101.             if(values[i]==e){
  102.                 values[i]=null;
  103.                 for( int x=i ;x<size;x++){
  104.                     values[x]=values[x+1];
  105.                 }
  106.             }
  107.         }
  108.         return true;
  109.     }
  110.  
  111.     public void removeAll(int index,int last){
  112.         if(index<0||last<0||index>size-1||last>size-1){
  113.             throw new ArrayIndexOutOfBoundsException("index或last 超过了范围");
  114.         }else{
  115.                 int n = 1;
  116.                 for (int y=index ;y<size ;y++ ){
  117.                     values[y]=values[last+n];
  118.                     n++;
  119.                 }
  120.                 size -= (last-index)+1;
  121.         }
  122.     }
  123.  
  124.     public void addAll(Object[] objArr){
  125.         if(objArr.length < length-size){
  126.             for (int i = 0; i < objArr.length; i++) {
  127.                 add ((A) objArr[i]);
  128.             }
  129.         }else{
  130.             grow ();
  131.             addAll (objArr);
  132.         }
  133.     }
  134.  
  135.  
  136.     public static void main(String[] args){
  137.         MyList<Integer> myList = new MyList(50);
  138.  
  139.         System.out.println("----------MyList----------");
  140.         long Start = System.currentTimeMillis ();
  141.         for (int i =0;i<500000;i++){
  142.             myList.add(i);
  143.         }
  144.         long End = System.currentTimeMillis ();
  145.         System.out.println ("存储50万组数据- 耗时："+(End-Start));
  146.  
  147.         Start = System.currentTimeMillis ();
  148.         for (int i = 1; i < 5000;i++) {
  149.             Integer integer = myList.get (i);
  150.         }
  151.         End = System.currentTimeMillis ();
  152.         System.out.println ("查询多个数据- 耗时："+(End-Start));
  153.  
  154.         Start = System.currentTimeMillis ();
  155.         for (int i = 1; i < 5000;i++) {
  156.             Integer integer = myList.remove(i);
  157.         }
  158.         End = System.currentTimeMillis ();
  159.         System.out.println ("移除多个数据- 耗时："+(End-Start));
  160.     }
  161. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/538292
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号