淘先锋技术网

首页 1 2 3 4 5 6 7

数据结构与算法--顺序存储结构（线性表）

线性表可以实现好多功能，所以，就可以写一个List接口定义这些功能，然后ArrayList来实现这些功能。在之后的好多应用中，好多都是基于线性表Arraylist实现的。现在写好之后直接调用即可。

在这里插入图片描述

  1. 定义List接口继承Iterable：之所以要继承Iterable类是因为，在遍历线性表时，在不考虑位置下标的情况下，可通过foreach循环实现，改Iterable中的iterator()函数是一个迭代器。
package DS01.动态数组;
/*
定义线性表的接口List
List支持泛型E
该List线性表中所存储的具体数据类型由外界决定
*
* */
public interface List<E> extends Iterable<E>{
    //获取线性表中元素的个数
    int getSize();
    //判断线性表是否为空表
    boolean isEmpty();
    //在线性表指定的index角标处插入元素e
    void add(int index,E e);
    //在线性表的表头处插入元素e
    void addFirst(E e);
    //在线性表的表尾处插入元素e
    void addLast(E e);
    //获取线性表中指定角标index处的元素
    E get(int index);
    //获取表头元素
    E getFirst();
    //获取表尾元素
    E getLast();
    //修改线性表中指定角标index处的元素为新元素e
    void set(int index,E e);
    //判断线性表中是否包含元素e
    boolean contains(E e);
    //查找元素e的角标（从左到右默认第一个出现的元素角标）
    int find(E e);
    //删除并返回线性表中指定角标index处的元素
    E remove(int index);
    //删除并返回表头元素
    E removeFirst();
    //删除并返回表尾元素
    E removeLast();
    //删除指定元素e
    void removeElement(E e);
    //清空线性表
    void clear();
    //获取最大容量
    int getCapacity();
}
  1. 线性表ArrayList继承List类：ArrayList重写List中定义的全部函数还有List从Iterable类中继承成的函数。
package DS01.动态数组;

import java.util.Iterator;

/*
* 创建线性表List的顺序存储结构实现类ArrayList
* */
public class ArrayList<E> implements List<E>{
    //创建E类型的一维数组
    private E[] data;
    //维护元素个数
    private int size;
    //默认最大容量为10
    private static int DEFAULT_CAPACITY=10;
    //创建一个默认大小的顺序表
    public ArrayList(){
        this(DEFAULT_CAPACITY);
    }
    //创建一个容量为capacity的顺序表
    public ArrayList(int capacity){
        if(capacity<=0){
            throw new IllegalArgumentException("容量>0:"+capacity);
        }
        data=(E[])(new Object[capacity]);
        size=0;
    }
    //用户传入一个数组 将该数组封装成一个顺序表
    public ArrayList(E[] data){
        if(data==null){
            throw new IllegalArgumentException("数组不能为空");
        }
        this.data=(E[])(new Object[data.length]);
        for(int i=0;i<data.length;i++){
            this.data[i]=data[i];
        }
        size=data.length;
    }
    @Override
    public int getSize() {
        return size;
    }

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

    @Override
    public void add(int index, E e) {
        if(index<0||index>size){
            throw new IllegalArgumentException("角标越界");
        }
        if(size==data.length){
            //扩容
            resize(data.length*2);
        }
        for(int i=size;i>index;i--){
            data[i]=data[i-1];
        }
        data[index]=e;
        size++;
    }
   //扩容其实就是偷梁换柱，在函数中重新创建一个数组，
   //然后遍历原数组，把原数组的值依次放入到该数组中
   //最后把新创建的数组赋给原数组
    private void resize(int newLength){
        E[] newData=(E[])(new Object[newLength]);
        for(int i=0;i<size;i++){
            newData[i]=data[i];
        }
        data=newData;
    }
    @Override
    public void addFirst(E e) {
        add(0,e);
    }

    @Override
    public void addLast(E e) {
        add(size,e);
    }

    @Override
    public E get(int index) {
        if(isEmpty()){
            throw new IllegalArgumentException("线性表为空");
        }
        if(index<0||index>=size){
            throw new IllegalArgumentException("角标越界");
        }
        return data[index];
    }

    @Override
    public E getFirst() {
        return get(0);
    }

    @Override
    public E getLast() {
        return get(size-1);
    }

    @Override
    public void set(int index, E e) {
        if(isEmpty()){
            throw new IllegalArgumentException("线性表为空");
        }
        if(index<0||index>=size){
            throw new IllegalArgumentException("角标越界");
        }
        data[index]=e;
    }
	//是否包含该字母
    @Override
    public boolean contains(E e) {
        return find(e)!=-1;
    }
	//从左向右找，返回第一个元素的位置
    @Override
    public int find(E e) {
        if(isEmpty()){
            throw new IllegalArgumentException("线性表为空");
        }
        for(int i=0;i<size;i++){
            if(data[i].equals(e)){//不是比对象地址，因为对象的地址肯定不一样。
                return i;
            }
        }
        return -1;
    }

    @Override
    //返回删除指定角标的元素：当前位置删完之后，要把当前位置之后的元素要向前移动。
    public E remove(int index) {
        if(isEmpty()){
            throw new IllegalArgumentException("线性表为空");
        }
        if(index<0||index>=size){
            throw new IllegalArgumentException("角标越界");
        }
        E ret=data[index];
        for(int i=index+1;i<size;i++){
            data[i-1]=data[i];
        }
        size--;
        //缩容：当前的有效长度要小于容量的1/4，不然不利于下一次操作
       // 并且当前的容量缩小后不能小于默认长度。
        if(size<=data.length/4&&data.length/2>=10){
            resize(data.length/2);
        }
        return ret;
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }
    //删除并返回表尾的元素
    @Override
    public E removeLast() {
        return remove(size-1);
    }

    @Override
    //删除指定元素e，从左向右第一个
    public void removeElement(E e) {
        int index=find(e);//找到指定元素的角标
        if(index!=-1){
            remove(index);
        }else{
            throw new IllegalArgumentException("元素不存在");
        }
    }
	//清空线性表就是，恢复默认时刻
    @Override
    public void clear() {
        size=0;
        data=(E[])(new Object[DEFAULT_CAPACITY]);
    }
    @Override
    public int getCapacity(){
        return data.length;
    }
    //主函数中运用System.out.println(stack)，打印一个对象其实就是运用toString();
    public String toString(){
        StringBuilder sb=new StringBuilder();
        sb.append(String.format("ArrayList: %d/%d\n",size,data.length));
        sb.append('[');
        if(isEmpty()){
            sb.append(']');
        }else {
            for(int i=0;i<size;i++){
                sb.append(data[i]);
                if(i==size-1){
                    sb.append(']');
                }else {
                    sb.append(',');
                }
            }
        }
        return sb.toString();
    }
    //该函数就是重写的Iterable类的那个函数
    //返回当前数据结构的一个迭代器对象
    //迭代器用于在没有角标支持的环境下遍历元素
    //主要就是为了运用foreach循环
    @Override
    public Iterator<E> iterator() {
        //Iterator是一个接口，不能被实例化，所以需要一个实现子类
        return new ArrayListIterator();
    }
    //写一个内部类来实现此迭代器接口
    private class ArrayListIterator implements Iterator{
        private int index=-1;
        @Override
        //下一个位置有元素
        public boolean hasNext() {
            return index<size-1;
        }

        @Override
        //返回下一个元素
        public E next() {
            index++;
            return  data[index];
        }
    }
}

3.编写测试类TestArrayList，来进行测试ArrayList是否写的正确。 需定义ArrayList的对象。

package DS01.动态数组;

import java.util.Iterator;

public class TestArrayList {
    public static void main(String[] args) {
       /* 
       运用foreach循环遍历该数组
       	int[] a=new int[]{1,2,3,4};
        for (int num:a) {
            System.out.print(num+" ");//a[i]
        }*/
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=1;i<=5;i++){
            list.addFirst(i);
        }
        for(int i=6;i<=10;i++){
            list.addLast(i);//进表的长度会超过默认长度，所以会扩容
        }
        System.out.println();
        for(int i=0;i<list.getSize();i++){
            System.out.print(list.get(i)+" ");
        }
        /*
        但凡能够被foreach循环迭代的对象
        都是具有可迭代性的
        */
        System.out.println();
        /*for (Integer i:list) {
            System.out.print(i+" ");
        }*/
        //引用当前的ArrayList的内部类，就是引用iterator()那个函数，目的为了实现接口的子类创建对象，运用foreach语句
        Iterator<Integer> it=list.iterator();
        while(it.hasNext()){
            System.out.print(it.next()+" ");
        }
    }
}

4.测试结果
在这里插入图片描述