数据结构与算法（线性结构-动态数组）

大家好，欢迎来到IT知识分享网。

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

插入元素原则按照size进行

错误添加覆盖顺序（从后往前）

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); } 在添加元素时调用检查。