什么是数据结构

• 数据结构是计算机存储，组织数据的方式

线性结构

• 包括 线性表，数组，链表，栈，队列，哈希表

image.png

树形结构

• 包括二叉树，AVL树，红黑树，B树，堆，Trie，哈夫曼树，并查集

image1.png

图形结构

• 包括 邻接矩阵，邻接表

image2.png

线性表

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

image3.png

• a1是首节点（首元素），an是尾节点（尾元素）
• a1是a2的前驱，a2是a1的后继
• 常见的线性表有
  • 数组
  • 链表
  • 栈
  • 队列
  • 哈希表（散列表）

数组

• 数组是一种顺序存储的线性表，所有元素的内存地址都是连续的。
• 例如:

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

• 内存地址表现形式如下:

image4.png

注意：

• 在很多编程语言中，数组都有一个致命的缺点，无法动弹修改容量
• 在实际开发中，我们更期望数组的容量是可以动态改变的。
• 解决方案：自己写一个动态数组

动态数组（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(); // 清除所有元素

动态数组的设计

• 代码示例：

public class ArrayList<E> {
    /**
     * 元素的数量
     */
    private int size;
    /**
     * 所有的元素
     */
    private E[] 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 = (E[]) new Object[capaticy];
    }
    
    public ArrayList() {
        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() {
         return size == 0;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E 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];
        }
        elements[--size] = null;
        return old;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element) {
        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;
            }
        }
        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);
        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() {
        // size=3, [99, 88, 77]
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            
            string.append(elements[i]);
            
//          if (i != size - 1) {
//              string.append(", ");
//          }
        }
        string.append("]");
        return string.toString();
    }
}

分析：

• 首先要有成员变量，至少包含两个成员变量，一个是size元素的数量，一个是存放元素的elements；

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

image6.png

分析：

• 首先要有成员变量，至少包含两个成员变量，一个是size元素的数量，一个是存放元素的elements；

/**
     * 元素的数量
     */
    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() {
        this(DEFAULT_CAPACITY);
    }

增加元素 - add(E element)

• 当size等于什么的时候，往什么位置存元素；

image7.png

打印数组

• 如果想打印数组，string.toString()这个方法；

  • 重写toString方法
  • 在toString方法中将元素拼接成字符串
  • 字符串拼接建议使用StringBuilder

• 代码示例：

@Override
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++) {
        if (i != 0) {
            string.append(", ");
        }
            
        string.append(elements[i]);
            
//      if (i != size - 1) {
//          string.append(", ");
//      }
    }
    string.append("]");
    return string.toString();
}   
    

删除元素 - remove(int index)

image8.png

• 本质：是往前挪一位，后面的赋值前面的，让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];
        }
        elements[--size] = null;
        return old;
    }
    

• 最后一个元素：不做处理；

增加元素 - add(int index, E element)

• 代码示例：

/**
* 在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++;
}

• 封装范围方法

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);
    }
}
    

• 添加末尾元素

/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
        add(size, element);
}
    

如何扩容

image10.png

• 代码示例：

/**
     * 保证要有capacity的容量
     * @param capacity
     */
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
        
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
        
    System.out.println(oldCapacity + "扩容为" + newCapacity);
}   

• 补充：oldCapacity >> 1位运算

位运算

• 概述
  • 从现代计算机中所有的数据二进制的形式存储在设备中。即0、1两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。
  • 相比在代码中直接使用(+、-、*、/)运算符，合理的运用位运算更能显著提高代码在机器上的执行效率。

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
l	或	两个位都为0时，结果才为0
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

泛型

• 使用泛型技术可以让动态数组更加通用，可以存放任何数据类型
• 在java里面用E表示，如下：

image11.png

对象数组

• 实质是放的内存地址；

Object[] object = new Object[7];

image12.png