不努力的话,天赋就会被收回

  menu

线性表 - Java实现

老师布置的作业,用Java实现线性表,自己写了一个,小小的测试了一下,可能我不够细心,没发现什么bug.如果有发现什么问题,欢迎指出(✪ω✪)

代码:

interface List<T> {
    boolean isEmpty();                      //  判断线性表是否为空

    int length();                           //  求线性表长度

    void clear();                           //  清空线性表

    void add(T elem);                       //  向表尾添加元素

    void addAll(List<? extends T> list);    //  合并两个表

    T get(int index);                       //  获得指定位置的值

    void insert(int index, T elem);         //  向指定位置插入元素

    void replace(int index, T elem);        //  替换指定位置的值

    int indexOf(T elem);                    //  返回元素在表中的位置

    T remove(int index);                    //  删除指定位置的值

    boolean contains(T elem);               //  判断值是否在表中
}

public class SeqList<T> implements List<T> {

    private int defaultCapacity = 10;       //  默认容器大小
    private Object[] elemData;              //  存储元素的容器
    private int size;                       //  线性表长度

    public SeqList() {
        elemData = new Object[defaultCapacity];
    }

    public SeqList(int initialCapacity) {
        elemData = new Object[initialCapacity];
    }

    public SeqList(Object[] arr) {
        this.elemData = new Object[arr.length];
        System.arraycopy(arr, 0, elemData, 0, arr.length);
        size = arr.length - 1;
    }

    /**
     * 判空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获得表长
     * @return
     */
    public int length() {
        return size;
    }

    /**
     * 清空
     */
    public void clear() {
        elemData = new Object[defaultCapacity];
        size = 0;
    }

    public void add(T elem) {
        if (size > elemData.length) {
            throw new IndexOutOfBoundsException("顺序表已满!");
        }
        elemData[size++] = elem;
    }

    public void addAll(List<? extends T> list) {
        for (int i = 0; i < list.length(); i++) {
            insert(this.length(), list.get(i));
        }
    }

    /**
     * 获得顺序表指定位置的元素
     * @param index
     * @return
     */
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        return (T) elemData[index];
    }

    /**
     * 向指定位置插入元素,如果表满了,则进行扩容操作
     * @param index
     * @param elem
     */
    public void insert(int index, T elem) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        Object[] objects = elemData;

        /**
         * 表满了,扩容
         */
        if (size == elemData.length) {
            elemData = new Object[objects.length * 2];
            for (int j = 0; j < index; j++) {
                this.elemData[j] = objects[j];
            }
        }
        for (int i = size - 1; i >= index; i--) {
            elemData[i + 1] = objects[i];
        }
        elemData[index] = elem;
        size++;
    }

    /**
     * 替换指定位置的元素
     * @param index
     * @param elem
     */
    public void replace(int index, T elem) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        elemData[index] = elem;
    }

    /**
     * 获得指定元素第一次出现的位置
     * @param elem
     * @return
     */
    public int indexOf(T elem) {
        for (int i = 0; i < size; i++) {
            if (elemData[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除表中指定位置的元素
     * @param index
     * @return
     */
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(index + "超出线性表范围");
        }
        T old = (T) this.elemData[index];
        for (int j = index; j < size - 1; j++) {
            this.elemData[j] = this.elemData[j + 1];
        }
        //将表的末尾元素置空
        this.elemData[this.size - 1] = null;
        size--;
        return old;
    }

    /**
     * 判断表中是否包含此元素
     * @param elem
     * @return
     */
    public boolean contains(T elem) {
        return indexOf(elem) != -1;
    }

    public Object[] toArray() {
        Object[] arr = new Object[this.length()];
        for (int i = 0; i < size; i++) {
            arr[i] = elemData[i];
        }
        return arr;
    }

    /**
     * 将线性表反转
     *
     * @param list
     * @return
     */
    public Object[] reverseList(Object[] list) {

        //计算出要移动元素的长度
        int len = list.length % 2 == 0 ? list.length / 2 : list.length / 2 + 1;
        for (int i = 0; i < len; i++) {
            Object temp = list[list.length - i - 1];
            list[list.length - i - 1] = list[i];
            list[i] = temp;
        }
        return list;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        sb.append(elemData[0]);
        for (int i = 1; i < this.size; i++)
            sb.append(", " + this.elemData[i]);
        sb.append("]");
        return sb.toString();
    }

    public void Print(){
        for(int i = 0; i < this.size; i++){
            if(elemData[i] != null)
            System.out.println(elemData[i]);
        }
    }
}

排序顺序表:

public class SortedSeqList<T extends Comparable<? super T>> extends SeqList<T> {

    public SortedSeqList() {
        super();
    }

    public SortedSeqList(int initialCapacity) {
        super(initialCapacity);
    }

    public SortedSeqList(Object[] arr){
        super(arr);
    }

    /**
     * 插入元素,按照元素升序排列
     *
     * @param elem
     */
    public void insert(T elem) {
        if (this.isEmpty()) {
            this.insert(0, elem);
        } else {
            int index = this.length();
            //找出待插入的位置
            for (int i = 0; i < this.length(); i++) {
                if (elem.compareTo(this.get(i)) < 0) {
                    index = i;
                    break;
                }
            }
            //调用父类的插入方法
            this.insert(index, elem);
        }
    }

    /**
     * 由于线性表有序,则使用二分查找提高查找效率
     *
     * @param elem
     * @return
     */
    public int binarySearch(T elem) {
        int low = 0;
        int mid = 0;
        int high = this.length() - 1;
        while (low <= high) {
            mid = low + ((high - low) / 2);
            if (this.get(mid).compareTo(elem) < 0) {
                low = mid + 1;
            } else if (this.get(mid).compareTo(elem) > 0) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return mid;
    }

    public SortedSeqList<T> mergeTwoLists(SortedSeqList<T> another) {
        
        Object[] arr = new Object[this.length() + another.length()];
        /**
         * System.arraycopy()
         * 参数: Object src,  int srcPos, Object dest, int destPos,int length
         * src 源数组
         * srcpos 源数组起始位置
         * dest 目标数组
         * destPos 目标数组起始位置
         * length 要进行复制的长度
         */
        System.arraycopy(this.toArray(), 0, arr, 0, this.length());

        //也可以使用下面的
//        for(int i = 0; i < this.length(); i++){
//            arr[i] = this.get(i);
//        }
        
        SortedSeqList<T> new_s = new SortedSeqList<>(arr);

        for (int i = 0; i < another.length(); i++) {
            new_s.insert(another.get(i));
        }
        
        return new_s;
    }

    public T remove(T elem) {
        int index = binarySearch(elem);
        return this.remove(index);
    }

    public static void main(String[] args) {
        SortedSeqList<Student> s = new SortedSeqList<>();
        s.insert(new Student("20180861201", "力尚龙", "男"));
        s.insert(new Student("20180861229", "任德祺", "男"));
        s.insert(new Student("20180861202", "孔德水", "男"));
        
        System.out.println("顺序表一:");
        s.Print();
        
        System.out.println();
        SortedSeqList<Student> q = new SortedSeqList<>();
        q.insert(new Student("20180861203", "林宇轩", "男"));
        q.insert(new Student("20180861225", "游章勋", "男"));
        q.insert(new Student("20180861224", "蔡凯洲", "男"));
       
        System.out.println("顺序表二:");
        q.Print();

        System.out.println();
        SortedSeqList<Student> mergeTwoLists = s.mergeTwoLists(q);
        System.out.println("两个排序顺序表合并后:");
        mergeTwoLists.Print();

    }
}

愿你生活的每一个角落,都有细微安静的美,愿你看淡世事沧桑,内心安然无恙,愿你洗净铅华,能被岁月温柔相待

标题:线性表 - Java实现
作者:Bursteretion
地址:https://www.lwjppz.cn/linear-list-implement-Java.html
版权声明:本博客除了特殊声明的文章外,均采用CC BY 3.0 CN协议进行许可。转载请署名作者且注明文章出处。
评论
  • 有个想法就是把那个扩容操作抽出来,独自写成一个函数,还有那个add,额,给它特殊一点,要不然直接调用insert太没意思了,( • ̀ω•́ )✧

    Reply
  • 添加到数组满了之后要扩展数组,不应该抛出错误 (逃

    Reply