数据结构与算法Java版——线性顺序表的实现

不念不忘少年蓝@ 2022-06-12 22:30 158阅读 0赞

数据结构一般都是由c++来讲解并且实现的，所以如果像我这种没学过c++而学过Java的就很尴尬了，不过不要以为Java不能实现数据结构那些常用的表啊，树啊之类的（不知道有没有小伙伴以为Java没有指针，所以一些功能无法实现呢？这是错误的噢）。粗略的学了数据结构这本书后，所以我打算用Java实现其中表，队，栈，树。如果你有兴趣可以持续关注我后续操作。我的个人博客地址为[我的博客][Link 1]

![这里写图片描述][6614552.jpg]

今天分享的是线性顺序表的实现，线性表底层其实是用的数组，我们创建一个顺序表时其实就是就是创建了一个数组，顺序表长度可变，但是数组长度不可变，那线性表怎么变化的呢？**其实每当底层的数组元素满的时候，底层代码就会重新创造一个数组，然后再将之前那个数组的对应复制到新的数组中，这样线性表长度就变长了。**话不多说，接下来上实现代码。

public class SequenceList<T> {
         private final int DEFAULT_SIZE=8;
         private int capacity;      //数组长度
         private int size=0;        //当前数组中元素个数
         private Object[] elementData;  //线性表实现的底层数组
    
         //默认初始化数组
         public SequenceList() {
            capacity=DEFAULT_SIZE;
            elementData=new Object[capacity];
         }
    
         /**
          *当数组已经满了后扩大容量 
          * @param ruleCapacity 数组容量
          */
         private void boardCapacity(int ruleCapacity){
             if(capacity<ruleCapacity){
                 //每次将数组容量按照原来扩大两倍，直到容量大于指定容量
                 while(capacity<ruleCapacity){
                     capacity=capacity*2;
                 }
                 elementData=Arrays.copyOf(elementData, capacity);
             }
         }
    
         //获得线性表大小
         public int getLength(){
             return size;
         }
    
         //重写toString方法
         @Override
        public String toString() {
             StringBuilder sb=new StringBuilder();
             for(int i=0;i<size;i++)
             {
                 sb=sb.append(elementData[i]+" ");
             }
             return sb+"";
        }
    
        /**
          * 按照顺序添加元素
          * @param element
          */
         public void add(T element){
             insert(element,size);
         }
    
         public void insert(T element,int index){
             if(index<0||index>size)
             {
                 throw new IndexOutOfBoundsException("索引越界");
             }
             boardCapacity(size+1);
             /*
              * 在elementData中从index开始复制，复制长度size-index,将
              * 复制的元素复制到目标数组elmentData的index+1位上直到后面结束
              * 即将index位置空出，每个元素后移一位
              */
             System.arraycopy(elementData, index, elementData, index+1, size-index);
             elementData[index]=element;
             size++;
         }
    
         /**
          * 查找指定元素的位置
          * 返回-1即没找到
          * @param element 指定元素元素
          * @return
          */
         public String locate(T element){
             StringBuilder sb=new StringBuilder();
             for(int i=0;i<size;i++)
             {
                 if(element.equals(elementData[i]))
                 {
                    sb=sb.append(i+" ");
                 }
             }
             if(sb.length()<=0)
                    return "无此元素";
             return sb+"";
         }
    
         /**
          * 删除指定位置的元素
          * @param index 元素索引
          */
         public void delete(int index){
             if(index<0||index>size)
             {
                 throw new IndexOutOfBoundsException("索引越界");
             }
             int length=size-index-1;
             //删除元素所有元素向前移动
             if(length>0)
                 System.arraycopy(elementData, index+1, elementData, index, length);
             //将最后一个数删除
             elementData[--size]=null;
         }
    
         public boolean isEmpty(){
             if(size>0){
                 return false;
             }
             return true;
         }
    
         /**
          * 清空线性表数据
          */
         public void clearSequenceList(){
             if(elementData!=null){
                 for(int i=0;i<size;i++)
                 {
                     elementData[i]=null;
                 }
                 size=0;
             }
         }
    
         //根据索引得到元素
         public Object get(int index){
             return elementData[index];
         }
    
         //删除最后一个元素
         public void remove(){
             delete(size-1);
         }
    
         public void printSequenceList(){
             if(elementData==null){
                 System.out.println("当前无数据");
             }else{
                 for(int i=0;i<size;i++)
                 {
                     System.out.print(elementData[i]+" ");
                 }
             }
         }
    
    }

这样就可以创建一个线性顺序表了，如果你自己亲自实现了，你会发现一个问题，是不是觉得ArrayList很像，其实ArrayList就是以一个数组包装实现的，就和我们写的这个顺序表很像，只是ArrayList包含的函数比我们写的多罢了。

最后上一下我的测试结果，有兴趣的小伙伴可以自己试一下。  
![这里写图片描述][75044556.jpg]

[Link 1]: http://xichangblog.com
[6614552.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-20/6614552.jpg
[75044556.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-20/75044556.jpg