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 顺序表（数组实现）

手搓顺序表；

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

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);}arr.get(3);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;}
}
/*输出结果
数组剩余容量为9
数组剩余容量为8
数组剩余容量为7
数组剩余容量为6
数组剩余容量为5
数组剩余容量为4
数组剩余容量为3
数组剩余容量为2
数组剩余容量为1
数组剩余容量为0
扩容为原来的1.5倍数组的元素个数11
数组的容量15*/

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