Java 数据结构 自定义顺序表

顺序表特点：      

①顺序表中元素依次存放在连续的存储空间中。

②可以快速的读取顺序表中的任意位置的元素。

③插入或者删除元素时，经常要移动大量元素，效率低。

④必须事先确定一块连续的存储空间，在声明后大小不变，是静态的，可能会导致存储空间的浪费。

package list;

import java.lang.reflect.Array;
import java.lang.*;
/*
* 顺序表定义
* */
public class ListArray<T extends Comparable> {
    private int length;     //最大的容量
    private int size;       //当前容量
    private T[] elements;   //数据数组
    private Class clazz;    //T的Class对象

    public ListArray(Class z,int length){
        this.length=length;
        this.size=0;
        this.elements = (T[])Array.newInstance(z,length);
        this.clazz=z;
    }

    public int getSize(){
        return this.size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public T get(int i){
        if(i<0||i>size-1)
            return null;
        return elements[i];
    }
    //插入元素
    public boolean insert(int i,T e){
        //非法位置插入，插入失败
        if(i<0||size>=length)
            return false;
        //最大长度不足，扩展
        if(size==length)
            expandSpace();
        //若插入位置比当前表的大小大，则把元素插到尾部.
        if(i>size-1){
            elements[size]=e;
            size++;
            return true;
        }
        //若在中间，则先将要插入的位置空出来，然后再插入
        for(int j=size-1;j>=i;j--){
            elements[j+1]=elements[j];
        }
        elements[i]=e;
        size++;
        return true;
    }
    //打印数组
    public void print(){
        if(size==0)
            System.out.println("size:0");
        for(int i=0;i<size;i++)
            System.out.println(i+":"+elements[i]);
    }
    //扩展数组最大长度为原来的2倍
    public void expandSpace(){
        T[] a = (T[])Array.newInstance(clazz,elements.length);
        for(int i=0;i<elements.length;i++)
            a[i]=elements[i];
        elements = a;
    }
    //删除位置为i的元素
    public boolean remove(int i){
        if(i<0||i>size)
            return false;
        for(int j=i+1;j<=size-1;j++){
            elements[j-1]=elements[j];
            System.out.print("["+j+"]");
        }
        size--;
        return true;
    }
    //查找元素为e的位置
    public int search(T e){
        for(int i=0;i<size;i++)
            if(elements[i]==e)
                return i;
        return -1;
    }
    //两个非递减有序序列合并
    public ListArray<T> merge(ListArray<T> other){
        int i=0,j=0,k=0;
        ListArray<T> mergedList = new ListArray<>(clazz,this.length+other.getSize());
        while(i<this.getSize()&&j<other.getSize()){
            if(this.get(i).compareTo(other.get(j))<0){
                mergedList.elements[k++]=this.elements[i];
                i++;
            }
            else{
                mergedList.elements[k++]=other.get(j);
                j++;
            }
        }
        if(i<this.size)
            while(i<this.size){
                mergedList.elements[k++]=this.elements[i];
                i++;
            }
        else
            while(j<other.getSize()){
                mergedList.elements[k++]=other.elements[i];
                j++;
            }
        mergedList.size=k;
        return mergedList;
    }
    public static void main(String[] args) {
        ListArray<Integer> list = new ListArray<>(Integer.class,15);
        list.insert(0,2);
        list.insert(1,4);
        list.insert(2,4);
        list.insert(3,6);
        list.insert(4,7);

        ListArray<Integer> other = new ListArray<>(Integer.class,15);
        other.insert(0,1);
        other.insert(1,3);
        other.insert(2,3);
        other.insert(3,4);
        other.insert(4,7);
        //list.remove(2);

        ListArray<Integer> merged = list.merge(other);

        merged.print();
        System.out.println("---");
        System.out.println("Search 2:"+list.search(2));
    }
}
      

0:1
1:2
2:3
3:3
4:4
5:4
6:4
7:6
8:7
9:7
---
Search 2:0