# DataStruct

**Repository Path**: XiaoXiaoChang/DataStruct

## Basic Information

- **Project Name**: DataStruct
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: MulanPSL-1.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-10-24
- **Last Updated**: 2022-10-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构
## 入门篇
### 1. 高效学习数据结构
#### 1.1 数据结构和算法的关系
* 广义上讲数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。
* 狭义上讲，是指某些著名的数据结构和算法，如队列、栈、堆、二分查找、动态规划等。

**数据结构是为算法服务的，算法要作用在特定的数据结构之上。 因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。**

比如，因为数组具有随机访问的特点，常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构，二分查找算法就无法工作了，因为链表并不支持随机访问。

数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。

#### 1.1 学习的重点在什么地方
* __首先要掌握一个数据结构与算法中最重要的概念——复杂度分析。__
数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。
* __数据结构和算法的相关知识点__
常见的数据结构和算法如下：
    * 常见的10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；
    * 常见的10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

    相对全面的知识网：
![导图](./src/picture/导图.jpg)

**本小节结语：**
对于每一种数据结构或算法，要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”。


#### 1.3 复杂度分析
* 大 O ---**T(n) = O(2n+2)**  
公式：T(n) = O(f(n))
其中，T(n) 它表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
```java
//例子一,T(n) = O(2n+2)
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
    sum = sum + i;
}
return sum;
}
```
```java
//例子二,T(n) = O(2n2+2n+3)
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
    j = 1;
    for (; j <= n; ++j) {
    sum = sum +  i * j;
    }
}
}
```
第一个例子中的 T(n) = O(2n+2)，第二个例子中的 T(n) = O(2n2+2n+3)。这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n2)。

* 时间复杂度分析
    * 只关注循环执行次数最多的一段代码
```java
//大 O 这种复杂度表示方法只是表示一种变化趋势。
//我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
    sum = sum + i;
}
return sum;
}
//其中第 2、3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。
//循环执行次数最多的是第 4、5 行代码，所以这块代码要重点分析。
//这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。
```
* 加法法则：总复杂度等于量级最大的那段代码的复杂度
```java
//这个代码分为三部分，分别是求 sum_1、sum_2、sum_3。
//我们可以分别分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的复杂度。
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
    sum_1 = sum_1 + p;
}

int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
    sum_2 = sum_2 + q;
}

int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
    j = 1; 
    for (; j <= n; ++j) {
    sum_3 = sum_3 +  i * j;
    }
}

return sum_1 + sum_2 + sum_3;
}
```
第一段的时间复杂度是多少呢？这段代码循环执行了 100 次，所以是一个常量的执行时间，跟 n 的规模无关。

`注：这里要再强调一下，即便这段代码循环 10000 次、100000 次，只要是一个已知的数，跟 n 无关，照样也是常量级的执行时间。当 n 无限大的时候，就可以忽略。尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可以忽略掉。因为它本身对增长趋势并没有影响。`

第二段的时间复杂度是多少呢？很显然是一个n次循环，所有时间复杂度是O(n)。

第三段的时间复杂度是多少呢？很显然是一个二重n次循环，所有时间复杂度是O(n2)。

综合这三段代码的时间复杂度，我们取其中`最大的量级`。所以，整段代码的时间复杂度就为 O(n2)。也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是：
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；
那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(`max`(f(n), g(n))).

* 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
```java
//我们可以把乘法法则看成是嵌套循环
int cal(int n) {
   int ret = 0; 
   int i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
 
 int f(int n) {
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }
```
我们单独看 cal() 函数。假设 f() 只是一个普通的操作，那第 4～6 行的时间复杂度就是，T1(n) = O(n)。
但 f() 函数本身不是一个简单的操作，它的时间复杂度是 T2(n) = O(n)，
所以，整个 cal() 函数的时间复杂度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。

那我们将这个乘法规律抽象成公式就是：
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；
那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).

* 几种常见时间复杂度实例分析
虽然代码千差万别，但是常见的复杂度量级并不多。如下图：
![常见的时间复杂度](./src/picture/常见的时间复杂度.jpg)
```java
//O(1)
int i = 8;
int j = 6;
int sum = i + j;
//O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。
//比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。
```
```java
//O(logn)
i=1;
while (i <= n)  {
    i = i * 2;
}
```
```java
//O(m+n)
int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}
```

我们可以结合函数图像直观的感受时间复杂度的量级，如图：
![复杂度函数图像](./src/picture/复杂度函数图像.jpg)


## 初级篇
### 数组
#### 数组为什么从0开始编号
##### 1.我们先看一下数组的内存寻址：
  > 如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：
  a[k]_address = base_address + k * type_size 
  >但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：
  a[k]_address = base_address + (k - 1) * type_size 
  >对比这两个公式我们发现，从1开始编号，每次随机访问数组都会多一次减法运算，对于CPU来说，就是多了一次减法指令。

数组作为非常基础的数据结构，通过数组下标随机访问数组又是非常基础的编程操作，效率优化就要尽可能的做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。

##### 2.历史原因
>C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在一定程度上减少 C 语言程序员学习 Java 的学习成本，因此继续沿用了从 0 开始计数的习惯。实际上，很多语言中数组也并不是从 0 开始计数的，比如 Matlab。甚至还有一些语言支持负数下标，比如 Python