数据结构与算法--动态数组

2022-11-13 本文已影响0人冰棍儿好烫嘴

线性表

线性表是具有n个相同类型元素的有限序列（n >= 0）

- a1是首节点（首元素），an是尾节点（尾元素）
- a1是a2的前驱，a2是a1的后继

对于非空的线性表和线性结构，其特点如下：
- 存在唯一的一个被称作“第一个”的数据元素
- 存在唯一的一个被称作“最后一个”的数据元素
- 除了第一个之外，结构中的每个数据元素均有一个前驱
- 除了最后一个之外，结构中的每个数据元素都有一个后继

常见的线性表有
- 数组
- 链表
- 栈
- 队列
- 哈希表（散列表）

数组（Array）

数组是一种顺序存储的线性表，所有元素的内存地址是连续的

int[] array = new int[]{11,22,33};

在很多编程语言中，数组都有个致命的缺点：无法动态修改容量
实际开发中，更希望数组的容量是可以动态改变的

动态数组(Dynamic Array)接口设计

int size(); //元素的数量
boolean isEmpty(); //是否为空
boolean contains(E element); //是否包含某个元素
void add(E element); //添加元素到最后面
E get (int index); //返回index位置对应的元素
E set (int index,E element); //设置index位置的元素
void add(int index,E element); //往index位置添加元素
E remove(int index); //删除index位置对应的元素
int indexOf(E element); //查看元素的位置
void clear(); //清除所有的元素
简单的数组接口设计，动态扩容在后面

package com.ld;

public class Main {
    public static void main(String[] args) {
        
        //new 是向堆空间申请内存，java垃圾回收机制：list局部变量在自动释放时，对应的指向的堆内存空间也释放
        ArrayList list = new ArrayList();
        list.clear();
        
        list.add(99);
        
        list.add(88);
        list.add(77);
        list.add(66);
        list.add(55);
        list.remove(list.size()-1);
        System.out.println(list.toString());
    }
}

package com.ld;

public class ArrayList {
    /*
     * 元素的数量
     * */
    private int size;
    /*
     * 所有的元素
     * */
    private int[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1; 
    public ArrayList(int capaticy) {
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
        elements = new int[capaticy];
    }
    public ArrayList() {
//      elements = new int[DEFAULT_CAPACITY];
        this(DEFAULT_CAPACITY);
    }

    /*
     * 清除所有元素
     * */
    public void clear() {
        size = 0;
    }
    /*
     * 元素的数量
     * @return
     * */
    public int size() {
        return size;
    }
    /*
     * 是否为空
     * @return
     * */
    public boolean isEmpty() {
        return size == 0;
    }
    /*
     * 是否包含某个元素
     * @param element
     * @return
     * */
    public boolean contains(int element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
    
    /*
     * 添加元素到尾部
     * @param element
     * */
    public void add(int element) {
        elements[size++] = element;
        //等价于add(size, element);
        
    }
    /*
     * 获取index位置的元素
     * @param index
     * @return
     * */
    public int get(int index) {
        rangeCheck(index);
        return elements[index];
    }
    /*
     * 设置index位置的元素
     * @param index
     * @param element
     * @return 原来的元素
     * */
    public int set(int index,int element) {
        rangeCheck(index);
        int old = elements[index];
        elements[index] = element;
        return old;
    }
    /*
     * 在index位置插入一个元素
     * @param index
     * @param element
     * */
    public void add(int index,int element) {
        rangeCheckForAdd(index);
        for (int i = size-1; i >=index; i--) {
            elements[i+1] = elements[i];
        }
        elements[index] = element;
        size++;
    }
    /*
     * 删除index位置的元素
     * @param index
     * @return
     * */
    public int remove(int index) {
        rangeCheck(index);
        int old = elements[index];
        for (int i = index+1; i <= size-1; i++) {
            elements[i - 1] = elements[i];
        }
        size--;
        return old;
    }
    /*
     * 查看元素的索引
     * @param element
     * @return
     * */
    public int indexOf(int element) {
        for (int i = 0; i < size; i++) {
            if (elements[i] == element) {
                return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:"+index+",size:"+size);
    }
    private void rangeCheck(int index) {
        if (index<0 || index>=size) {
            outOfBounds(index);
        }
    }
    private void rangeCheckForAdd(int index ) {
        if (index<0 || index>size) {
            outOfBounds(index);
        }
    }
    
    @Override
    //打印数组
    //重写toString方法，在toString方法中将元素拼接成字符串，
    //字符串拼接建议使用StringBuilder
    public String toString() {
        //打印效果 size = 3,[99,88,77]
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(",[");
        for (int i = 0; i < size; i++) {
            string.append(elements[i]);
            if (i != size-1) {
                string.append(",");
            }
        }
        string.append("]");
        return string.toString();
    }
}

动态扩容以及泛型

动态扩容的思路：堆内存开辟空间时，是随机分配的，所以之前的数组如果内存不够用时，是不可以直接在之前的数组后边继续开辟空间的，只能是判断内存不够用时，重新开辟一个新的更大的数组内存空间，把之前的数组的内容拷贝到新的数组里边，然后销毁之前的旧数组就可以了
泛型：使用泛型技术可以让动态数组更加通用，可以存放任何数据类型

最后的代码结果
ArrayList.java

package 动态数组;

import java.util.Iterator;

public class ArrayList<E> {
    /*元素的数量*/
    private int size;
    /*所有的元素*/
    private E[] elements;
    //private 私有，static静态，能保证内存只有一份，final常量，相当于其他语言的const
    private static final int DEFAULT_CAPACITY = 2;
    private static final int ELEMENT_NOT_FOUND = -1;
    //构造函数
    @SuppressWarnings("unchecked")
    public ArrayList(int capaticy) {
        //最开始用户给的数小于常量的值，就直接给设置成常量的值，个人设计问题，也可以判断<0.直接设置容量为1，但是很快就会不够用了，所以暂时先设计成，容量小于我给的常量就先设置成容量为常量的数值
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY:capaticy;
        elements = (E[]) new Object[capaticy];
    }
    public ArrayList() {
        //elements = new E[DEFAULT_CAPACITY];
        //或者用下边的方法
        this(DEFAULT_CAPACITY);//调用自己的上面的构造函数
    }
    
    /*清除所有元素*/
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }//销毁数组中的对象，回收对象的内存空间，但是不销毁数组开辟的内存空间
        size = 0;
    }
    /*元素的数量
     * @return*/
    public int size() {
        return size;
    }
    /*是否为空
     * @return*/
    public boolean isEmpty() {
//      if (size == 0) {
//          return true;
//      }else {
//          return false;
//      }
        return size == 0;
    }
    /*是否包含某个元素
     * @param element
     * @return*/
    public boolean contains( E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
    /*
     * 添加元素到尾部
     * @param element*/
    public void add(E element) {
//      elements[size] = element;
//      size++;
//      //或者
//      //elements[size++] = element;
        
        add(size, element);
    }
    /*获取index位置的元素
     * @param index
     * @return*/
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }
    /*设置index位置的元素
     * @param index
     * @param element
     * @return原来的元素*/
    public E set(int index,E element) {
        rangeCheck(index);
        E old = elements[index];
        elements[index] = element;
        return old;
    }
    /*在index位置插入一个元素
     * @param index
     * @param element*/
    public void add(int index,E element) {
        rangeCheckForAdd(index);
        
        ensureCapacity(size+1);
        
        for (int i = size-1; i >=index ; i--) {
            elements[i+1] = elements[i];
        }
        elements[index] = element;
        size++;
    }
    /*删除index位置的元素
     * @param index
     * @return*/
    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index+1; i <=size-1; i++) {
            elements[i-1] = elements[i]; 
        }
        size -- ;
        elements[size] = null;
        return old;
    }
    /*查看元素的索引
     * @param element
     * @return*/
    public int indexOf(E element) {
        //因为add的方法是可以寸null的，java里也是支持保存null的，但是如果某一个对象是null，
        //当调用下边的.equals(element)方法时是会报异常的，所以这里需要判断if==null的情况
        if (element == null) {
            for (int i = 0; i <size; i++) {
                if (elements[i] == null)  return i;
            }
        }else {
            for (int i = 0; i <size; i++) {
                if (element.equals(elements[i]))  return i;
                /*if这里不能直接用==号去判断，需要调用对象方法里边的equals方法去判断对象是否相等，
                在对象的类里需要去重写equals方法，如果对象里没有重写equals方法，
                那么对比的就是两个对象是否完全相等，也就是意味着两个对象的地址值是否完全相等
                如果重写了equals，就意味着自己去定义相等的条件是什么
                */
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    /*保证要有capacity的容量
     * @param capacity*/
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) {
            return;
        }
        //新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5*oldCapacity
        @SuppressWarnings("unchecked")
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        
        System.out.println(oldCapacity + "扩容为" + newCapacity);
    }
    
    private void outofBounds(int index) {
        throw new IndexOutOfBoundsException("index:" +index + ",size:" + size);//抛出异常
    }
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outofBounds(index);
        }
    }
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outofBounds(index);
        }
    }
    
    @Override
    public String toString() {
        // TODO Auto-generated method stub
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(",[");
        for (int i = 0; i < size; i++) {
            string.append(elements[i]);
            if (i != size-1) {
                string.append(",");
            }
        }
        string.append("]");
        return string.toString();
    }
}

Main.java

package 动态数组;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        
        ArrayList<Person> persons = new ArrayList<>();

        persons.add(new Person(10, "jack"));
        persons.add(new Person(12, "james"));
        persons.add(new Person(15, "rose"));
        
        System.out.println(persons);
        //      list.add(99);
//      list.add(88);
//      list.add(77);
//      list.add(66);
//      list.add(55);
//      
//      
//      list.set(3, 80);
//      
//      
//      System.out.println(list.toString());
    }
}

Person.java

package 动态数组;

public class Person {
    private int age;
    private String name;
    
    //option+command+s快捷键，-> Generate Constructors from Superclass->勾选要生成构造函数的属性->Generate 
    //自动生成如下的构造方法
    public Person(int age, String name) {
        super();
        this.age = age;
        this.name = name;
    }

    //option+command+s快捷键，-> Generate toString()自动生成toString方法
    @Override
    public String toString() {
        return "Person [age=" + age + ", name=" + name + "]";
    }
    
    @Override
    //判断对象是否相等，在java中可以重写equals方法，在equals方法中自定义是否相等的条件，     
    public boolean equals(Object obj) {
        // TODO Auto-generated method stub
        Person person = (Person) obj;
        return this.age == person.age;
    }
}

数据结构与算法--动态数组

线性表

数组（Array）

动态数组(Dynamic Array)接口设计

动态扩容以及泛型

猜你喜欢

热点阅读