250217-数据结构

1. 定义

数据结构是数据的存储结构，即数据是按某些结构来存储的，比如线性结构，比如树状结构等。

2. 学习意义

数据结构是服务于算法的，为了实现算法的高效计算，所以将数据按特定结构存储。比如使用快速插入或删除的算法时，使用链表这种数据结构算法会更高效。

3.分类

判定某种数据结构的优劣是根据大O时间复杂度来判断的。

T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示程序执行完毕后执行全部计算次数的总和，因为这是一个公式， 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

复杂度分析法则

1）单段代码看高频：比如循环。 2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。 3）嵌套代码求乘积：比如递归、多重循环等 4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

时间复杂度分析

只关注循环执行次数最多的一段代码加法法则：总复杂度等于量级最大的那段代码的复杂度乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

复杂度分析的4个概念 1.最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。 2.最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。 3.平均时间复杂度：代码在所有情况下执行的次数的加权平均值。 4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

3.1 线性结构

3.1.1 顺序表（数组实现）

数据存储在连续的内存空间里；

优点：访问快；

缺点：插入删除效率低；动态扩容成本高（需复制整个数组）

手搓顺序表；

动态扩容检查索引合法性在末尾添加元素在指定位置增加元素删除元素 后面元素的前移来覆盖欲删除元素，达到删除效果（这样数组末尾会多出一个无用元素）（比如从索引 2 开始，把后面的元素依次向前移动一位。也就是将索引 3 的元素（值为 4）移到索引 2 的位置，将索引 4 的元素（值为 5）移到索引 3 的位置。其实是索引 4 的元素被复制到了索引 3 的位置，而索引 4 的位置仍然保留着之前的值，但这个值现在已经没有实际意义，成了 “无用” 元素。）建立一个新数组，把保留下来的元素复制过去 替换指定位置元素查询元素获取元素数量打印数组所有元素

下面实例中属性都被封装起来了，方法里的功能性方法比如增加元素、查看元素是公开的，但是检查是否合法、动态扩容的方法也都被封装起来了。

public class ArraysStructure { public static void main(String[] args) { ArraysDemo arr=new ArraysDemo(); int[] a={1,2,3,4,5,6,7,8,9,10,11}; for(int i:a) { arr.add(i); } System.out.println("数组指定位置元素"+arr.get(3)); System.out.println("数组的元素个数"+arr.size()); System.out.println("数组的容量"+arr.getCapacity()); arr.insert(3,100); arr.replace(4,200); System.out.println("数组指定位置元素"+arr.get(3)); System.out.print("删元素之前："); arr.printArray(); arr.deleteElement(3); System.out.print("删元素之后："); arr.printArray(); System.out.println("数组的元素个数"+arr.size()); System.out.println("数组的容量"+arr.getCapacity()); } } //总的来说，下面定义的类实现了动态数组、检查合法、添加元素、查询元素、获取元素数量三个功能 class ArraysDemo { private static final int DEFAULT_CAPACITY=10; //初始数组容量； private int[] arr; //声明数组变量 private int size; //当前元素数量 public ArraysDemo() //构造函数，初始化数组 { arr=new int[DEFAULT_CAPACITY]; size=0; } //确保数组容量足够 private void ensureCapacity(int minCapacity) { if(minCapacity>arr.length) { //扩容为原来的1.5倍 int newCapacity=DEFAULT_CAPACITY+(DEFAULT_CAPACITY>>1); int[] newArray=new int[newCapacity]; System.arraycopy(arr,0,newArray,0,size); //旧数组数据复制到新数组 arr=newArray; System.out.println("扩容为原来的1.5倍"); } else { // System.out.println("数组剩余容量为"+(arr.length-minCapacity)); } } public void add(int num) //添加元素 { //首先检查是否需要扩容 ensureCapacity(size+1); arr[size++]=num; } public int get(int index) //获取指定位置的元素 { checkIndex(index); //检查索引是否合法 return arr[index]; } public void checkIndex(int index) //检查索引是否合法 { if(index<0 || index>=size) { throw new IndexOutOfBoundsException("index"+index+"，size"+size); } } public int size() //获取元素数量 { return size; } public int getCapacity() //获取数组容量 { return arr.length; } public void replace(int a,int b) //指定索引位置替换元素 { checkIndex(a); arr[a]=b; } public void insert(int a,int b) //指定索引位置插入元素 { if(size>0) { ensureCapacity(size+1); checkIndex(a); for(int i=size;i>a;i--) { arr[i]=arr[i-1]; } arr[a]=b; size++; } else { arr[a]=b; } } public void printArray() //打印数组元素 { for(int i:arr) { System.out.print(i+""); } } // public void deleteElement(int index) //元素前移覆盖方式 // { // checkIndex(index); // for (int i = index; i < size - 1; i++) // { // arr[i] = arr[i + 1]; // } // size--; // } public void deleteElement(int index) //新建数组删除方式 { checkIndex(index); int[] newArr=new int[arr.length-1]; for(int i=0,j=0;i<size;i++) { if(i!=index) { newArr[j++]=arr[i]; } } size--; arr=newArr; } } /*输出 扩容为原来的1.5倍 数组指定位置元素4 数组的元素个数11 数组的容量15 数组指定位置元素100 删元素之前：123100200567891011000 删元素之后：123200567891011000 数组的元素个数11 数组的容量14*/

该例还有一个细节，以int[] arr=new int[n]创建的arr对象可以arr.length查看数组的总容量，然而若以ArraysDemo arr=new ArraysDemo()创建的arr对象，查看arr.length就会报错，说该类未声明length属性。 

3.1.2 链表

定义

3.1.3 栈

3.1.4 队列

3.2 树状结构

                                                      文中关于时间和空间复杂度的内容引自该文，原文链接： blog.csdn.net/ityqing/article/details/82838524。