数据结构基础

1.什么是数据结构

1. 数据结构是存储，组织数据的方式
2. 精心选择的数据结构可以带来更高的运行或者存储效率
3. 数据结构是很多算法得以进行的载体

比如我们常见的数组，链表，图，二叉树等等都是数据结构。

数组是内存上一块连续的空间，指定长度为一个数组的大小，如果超过这个长度，就会出现数组越界的情况。因为数组是连续的空间，那么默认某个节点的内存加1就是下一个数据节点，并且我们提前给数组标注了“下标”，所以很容易找到某个元素，即便于寻址。既然我们数组是连续的空间，那么对于数组中的数据进行增删是比较费劲的，因为需要对插入或者删除位置后边的所有的元素统一进行移动。所以数组是便于寻址，不便于增删数据。

链表内存上不一定连续，链表中的每个节点中存储着节点数据和下一个节点的“地址”，根据存储的地址进行寻址。它没有所谓的下标，没有办法一下子定位到某个元素，我们需要一个一个的遍历。但是正因为如此，我们增删数据时不依赖空间上的连续性问题，直接修改节点中的那个“地址”来进行数据的增删。所以链表是不便于寻址，但是便于增删数据。

图和二叉树比较复杂，此处先不讲。

那么我们通过一个案例来更清晰的理解数据结构的作用。

2. 案例：查询数组上L~R位置上的累加和(L<R)

举例说明

数组Array.png

如上图所示，我想求得1～3位置上的累加和，那我们可以看到是 3+ 3+ 10 = 16.
如题，我们该怎么做呢？
其实，有两种想法，仅供参考。

• 我们列一个二维数组，或者一个表格，把所有的L~R的累加和都记录下来，然后我们查询时取出来即可。

  
  L～R的累加和表格.png
  

  从图上可以看到凡是L>R的地方都是不成立的，去掉，其余任意一个L~R的累加和都可以直接取出来，这个适合于查询量巨大的情况，我们对于这点空间消耗是能够接受的，以时间换空间。

• 第二种方式我用一个等长的数组存储0位置到某个位置的累加和。

  
  前缀和数组H.png
  

  从图上我们可以看出来，每个位置存的都是0～该位置的累加和，我们称为前缀和数组。
  那么我们要求的L~R的累加和就可以这样算

1. L == 0时, 累加和= H[R]
2. L != 0时, 累加和= H[R] - H[L-1]
   第二种方式在空间上大大节约了，但是还需要再做一步计算，所以适用于查询量不那么巨大的情况。

前缀和的代码比较简单，列一下吧。

   //求前缀和数组
    public static int[] preSumArray(int[] arr){

        int n = arr.length;
        int[] preSumNum = new int[n];
        preSumNum[0] =arr[0];
        for(int i = 1; i < n; i++){
            preSumNum[i] = preSumNum[i-1] + arr[i];
        }

        return preSumNum;
    }
    
    //L~R的累加和计算
    public static int sumOfLtoR(int[] preSumArray, int L, int R){

        if(L>R){
            throw new RuntimeException("L不能大于R");
        }
        if(L == 0){
            return preSumArray[R];
        }else{
            return preSumArray[R] - preSumArray[L-1];
        }

    }