数据结构Java-顺序表

顺序表

     这段时间在复习数据结构,以前学校教的是C语言版的数据结构。正好趁这次复习机会,将以前学的数据结构用Java语言来实现,可能写出来的代码有Bug,希望大家能多多指出我的错误并提供建议,在这里感谢大家。

class ArraySqlist<ElemType> {
    int MaxSize; //最大长度
    ElemType data[]; //数组实现顺序表
    int length = 0; //当前顺序表长度

    public ArraySqlist() {
        //默认顺序表长度为10
        MaxSize = 10;
        data = (ElemType[]) new Object[MaxSize];
    }

    public ArraySqlist(int maxSize) {
        MaxSize = maxSize;
        data = (ElemType[]) new Object[MaxSize];
    }

    //扩大数组
    private void Increase() {
        MaxSize = MaxSize + 5;
        Object temp[] = new Object[MaxSize];
        for (int i = 0; i < length; i++) {
            //复制数组
            temp[i] = data[i];
        }
        //将新数组交给data
        data = (ElemType[]) temp;
    }

    /*
      将元素添加到顺序表的指定位置
      问题规模n = length(表长)
      时间复杂度:最好时间复杂度O(1),插入位置在表尾,不需移动元素
                最坏时间复杂度O(n),插入位置在表头,需要移动n个元素
                平均时间复杂度O(n),如果插入到表中的位置概率相同,则执行次数n(n+1)/2 * 1/(n+1) = n/2
     */
    public void add(ElemType e, int index) {
        if (index > length+1 || index < 0)
            throw new IndexOutOfBoundsException();
        if (length == MaxSize)
            Increase();
            for (int j = length; j >= index; j--)
                data[j] = data[j - 1];   //将length-index+1个元素往后移动
            data[index-1] = e;
            length++;
    }
        public void add (ElemType e){ //往后增加元素
        if (length == MaxSize)
            Increase();
            data[length] = e;
            length++;
        }

    /*
     将元素从顺序表中移除
     问题规模n = length(表长)
     时间复杂度:最好时间复杂度O(1),删除位置在表尾,不需移动元素
               最坏时间复杂度O(n),删除位置在表头,需要移动n个元素
               平均时间复杂度O(n),如果删除表中的元素位置概率相同,则执行次数n(n+1)/2 * 1/(n+1) = n/2
    */
        public ElemType remove (int index){
            if (index > length+1 || index < 0) //非法访问处理
                throw new IndexOutOfBoundsException();
            ElemType result = data[index-1];
            for (int i = index; i < data.length; i++)
                data[i-1] = data[i];
            length--;
            return result;
        }

        //从顺序表中指定位置获取元素 O(1)
        public ElemType get(int index){
            if(index<1 || index>length)
            return null;
            return data[index-1];
        }

        @Override
        //打印顺序表
        public String toString () {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < length; i++){
                if(i == length - 1)
                    sb.append(data[i]);
                else
                    sb.append(data[i]+" ");
                }
            return "["+sb.toString()+"]";
        }
    }
上一篇:# 用类来封装动态数组:分文件编写


下一篇:7-6 单源最短路径 (10 分)(最好用priirity_queue否则测试点2直接TLE)