数据结构与算法(线性结构-动态数组)

1.算法： 是用于解决特定问题的一系列的执行步骤。

2.评价算法

如何评判一个算法的好坏，一般从以下维度进行评估算法的优劣：
1.正确性、可读性、健壮性（对不合理的反应的解决能力）。
2.时间复杂度：估算程序指令的执行次数（执行时间）。
3.空间复杂度： 估算所需占用的存储空间。

注：每日的数据结构与算法采用JAVA来进行实现与讲解。

3.时间复杂度

估算程序指令的执行次数：
如：
1.for(int i=0;i<n ; i++)   
    int  i =0  ；    执行一次
    i< n ;              执行 n次
    i++ ;               执行 n 次
总的执行次数为 2n + 1    

2. for(int i=0;i<n ; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println("test");
        }
    }    
总的执行次数为 3n^2+3n +1    

3.  while((n=n/2)>0){
       System.out.println("test");
  }
分析：
 8 /2           4   
 4/ 2           2   
 2 / 2          1
总的执行次数为 log2(n)。

4.大O表示法

大O表示法来描述复杂度  它表示是数据规模n对应的复杂度,仅仅只是一种粗略的分析模型。
注：忽略常数、系数、低阶。

9  >>  O(1)
2n+3  >> O(n)
n*n +2n+ 5  O(n*n)
4n*n*n +3n*n + 22n +100  >> O(n*n*n)

5.数据结构

数据结构是计算机存储、组织数据的方式
包括：线性结构：线性表 （数组、链表、栈、哈希表）
          树形结构：二叉树、AVL树、红黑树、B树、堆、Tree、哈夫曼树
          图形结构：邻接矩阵、邻接表
          
我们先从线性结构说起。          

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

如上图所示：a1是首节点 ，an 是尾结点，a1是a2的前驱 ， a2是a1的后继。
日常中有很多线性表的例子： 比如冰糖葫芦，排成一列的乒乓球等等。

7.数组

数组：是一种顺序存储的线性表，所有元素的内存地址是连续的。
int[] array=new int[]{11,22,33}；  定义一个含有11 22 33 的数组。

数组存在一个致命的缺点：无法动态修改容量，而我们在实际开发中希望容量可以动态改变，所以
                                         进行动态数组的创建，实现数据可以动态修改容量。

8.动态数组创建

创建一个动态数组实现的是可以向数组中进行增删改查，并且当增加值时数组内存地址可以保证够用，
当数组内存地址不够用时，可以随时进行添加，所以一个动态数组需要包含：
  1.指向堆空间一数组地址
  2.数组的长度

9.实现常用功能

动态数组基本常用功能（参考jdk源码 ArrayList源码） 这里数组中存储就以整数来进行举例。
    int size(); //元素的数量
    boolean isEmpty(); //是否为空
    boolean contains(int element); // 是否包含某个元素
    void add(int  element);  // 添加元素到最后面
    int  get(int index); // 返回index位置对应的元素
    int set(int index,int element); // 设置index位置添加元素
    void add(int index,int element); // 往index位置添加元素
    int remove(int index); // 删除index位置对应的元素
    int indexOf(int element); //查看元素的位置
    void clear(); // 清除所有的元素

10.动态数组初始化

public class DynamicArray implements PublicInterface {  publicInterface 是实现功能方法接口
    /**
     * 元素的数量
     */
    private int size;

    /**
     * 所有的元素
     */
    private int[] elements;

//    数组默认长度  这里设置默认长度为10 可自行调整
    private static final  int NOT_DATA_FIND =10 ;

 // 定义 传值的构造方法 如果传入的值大于 默认值 采用创建传入值的数组长度
    public DynamicArray (int capacity){
        capacity = (capacity < DEFAULT_CAPACITY ) ? DEFAULT_CAPACITY: capacity;
        elements = new int[capacity];
    }
   // 默认创建为10 的数组
    public DynamicArray (){
        this(DEFAULT_CAPACITY);
    }

11.元素数量、 是否为空等功能实现

    /**
     *  元素的数量
     */
    @Override
    public int size() {
        return size;    // 直接返回size显示数组长度
    }

// 如果size 为 0  代表动态数组为空
   /**
     * 是否为空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }


/**
     * 查看元素所在的位置
     * @param element
     * @return
     */
    @Override
    public int indexOf(int element) {
        for (int i=0 ; i < size ;i++){
            if (elements[i] == element ) return i;
        }
        return NOT_DATA_FIND;  //  静态常量为-1
    }

 /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    @Override
    public boolean contains(int element) {
        return indexOf(element) == NOT_DATA_FIND;  //  静态常量为-1
    }

 /**
     * 清除所有的元素
     */
    @Override
    public void clear() {
        size = 0 ; // 重复利用内存空间
    }
注： 这里情况数组直接设置size为0 即可：
DynamicArray array = new DynamicArray();
array.add(11); // add实现方法下面会进行讲解   当调用添加方法是 size ++ ，如果将size设置为0 
调用获取数据或其他方法就不可以实现，从程序外部来看数据已经被清空了，因为这里数组存储的是
整数，如果存储的是对象，需要遍历数组将每个对象设置为null，再设置size为0 ，防止内存一直占用。

12.元素位置 、元素添加等功能实现

 /**
     * 返回index位置对应的元素
     * @param index
     * @return
     */
    @Override
    public int get(int index) {
        if(index < 0 || index >= size){
          //   不符合条件抛出异常
            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);
        }
        return elements[index];
    }


    /**
     * 设置index位置元素
     * @param index
     * @param element
     * @return
     */
    @Override
    public int set(int index, int element) {
        if(index < 0 || index >= size){
            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);
        }
      // 获取以前位置元素
        int old = elements[index];
        elements[index] = element;
        return old;
    }


  /**
     * 往index位置添加元素
     * @param index
     * @param element
     */
    @Override
    public void add(int index, int element) {
    //  这里如果是在size位置上添加，所以可以包含size
        if(index < 0 || index >  size){
            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);
        }
        for (int i = size - 1 ; i >= index ; i--){
            elements[i + 1] =  elements[i];
        }
        elements[index] = element ;
        size ++ ;

    }

  /**
     * 添加元素到最后面
     * @param element
     */
    @Override
    public void add(int element) {
       add(size , element);
    }

13.动态数组元素删除实现

  /**
     * 删除index位置对应的元素
     * @param index
     * @return
     */
    @Override
    public int remove(int index) {
        if(index < 0 || index >= size){
            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);
        }
        int old = elements[index];
        for (int i = index + 1 ; i <= size -1 ; i++ ) {
            elements[i - 1] = elements[i];
        }
        size -- ;
        return old;
    }

14.扩容

当向动态数组中进行添加元素时，需要进行判断数组内存地址是否够用，不够用需要进行扩容。

 // 不够用时新创建一个新的数组，是原有的1.5倍，再将数据元素迁移到新的数组地址。
 private void Ensurecapacity(int capacity){
        int oldCapacity = elements.length;
        if(oldCapacity >= capacity) return;

//        新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[newCapacity];

        for (int i = 0 ; i < size ; i++){
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println("扩容"+elements.length);
    }

在添加元素时调用检查。