Java实现顺序线性表

Z时代
2024-01-10
分类：综合

java

import java.util.Arrays;

public class SequenceList<T> {
    private int DEFAULT_SIZE=16;
    //保存数组的长度
    private int capacity;
    //定义一个数组用于保存顺序线性表的元素
    private Object[] elementData;
    //保存顺序表中元素的当前个数
    private int size=0;

    public SequenceList(){
        capacity=DEFAULT_SIZE;
        elementData=new Object[capacity];
    }
    public SequenceList(T element){
        this();
        elementData[0]=element;
        size++;
    }

    public SequenceList(T element,int initSize){
        capacity=1;
        //把capacity=1设为大于initSize的最小2的n次方
        while(capacity<initSize){
            capacity<<=1;
        }
        elementData=new Object[capacity];
        elementData[0]=element;
        size++;
    }
    //获取顺序表的大小
    public int length(){
        return size;
    }
    //获取顺序表中索引为i处的元素
    public T get(int i){
        if(i<0||i>size-1){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        return (T)elementData[i];
    }
    //查找顺序表中指定元素的索引
    public int locate(T element){
        for(int i=0;i<size;i++){
            if(elementData[i]==element){
                return i;
            }
        }
        return -1;
    }
    //向顺序线性表中指定位置插入一个元素
    public void insert(T element,int index){
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        ensureCapacity(size+1);
        //将指定索引处之后的所有元素向后移动一格
        System.arraycopy(elementData, index, elementData, index+1, size-index);
        elementData[index]=element;
        size++;
    }
    //在线性顺序表的最后处添加一个元素
    public void add(T element){
        insert(element,size);
    }
    private void ensureCapacity(int minCapacity) {
        // TODO Auto-generated method stub
        if(minCapacity>capacity){
            while(capacity<minCapacity){
                capacity<<=1;
            }
            elementData=Arrays.copyOf(elementData, capacity);
        }
    }
    public T delete(int index){
        if(index<0||index>size-1){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        T oldValue=(T)elementData[index];
        int numMoved=size-index-1;
        if(numMoved>0){
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        }
        elementData[--size]=null;
        return oldValue;
    }
    public T remove(){
        return delete(size-1);
    }
    public boolean empty(){
        return size==0;
    }
    public void clear(){
        Arrays.fill(elementData, null);
        size=0;
    }
    public String toString(){
        if(size==0){
            return "[]";
        }else{
            StringBuilder sb=new StringBuilder("[");
            for(int i=0;i<size;i++){
                sb.append(elementData[i].toString()+", ");
            }
            int len=sb.length();
            return sb.delete(len-2, len).append("]").toString();
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        SequenceList<String> list=new SequenceList<String>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        System.out.println(list.toString());
        list.insert("ddd", 1);
        list.add("aa");
        System.out.println(list.toString());
        list.delete(2);
        System.out.println(list.toString());
        System.out.println("ccc在顺序线性表中的位置:"+list.locate("ccc"));
    }
}