# C Data Structure

**Repository Path**: cloudcan/c-data-structure

## Basic Information

- **Project Name**: C Data Structure
- **Description**: 基于C/C++的数据结构与算法学习项目
- **Primary Language**: C/C++
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 4
- **Forks**: 5
- **Created**: 2022-10-16
- **Last Updated**: 2025-03-26

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构与算法
  
**“程序（Program）=数据结构（Data Structure）+算法（Algorithm）”**  
***
## 第一章 基础概念
### Ⅰ、数据结构发展史
数据结构的发展经历三个阶段：无结构阶段，结构化阶段和面向对象阶段  
1. 无结构阶段  
    40~60年代，计算机的主要应用还没有如此普及，当时计算机主要是正对科学计算，程序设计技术以机器语言和汇编语言为主，程序处理的是存粹的数值，数据之间的关系主要是以来数学公式或者数学模型，此时数据结构概念并没有明确形成。
2. 结构化阶段  
    60~80年代，计算机开始广泛应用于非数值处理领域，数据表示成为程序设计的重要问题，人们认识到程序设计规范化的重要性，提出了程序结构模块化，并开始注意数据表示与操作的结构化。数据结构及抽象数据类型就是在这种情况下形成的，随着数据规模的加大，程序的设计越来越依附于数据结构的设计，此时数据结构开始广泛普及。
    此间也有非常多的数据结构相关的文献产出，最为著名的是图灵奖获得者沃斯的一个著名公式：程序=数据结构+算法。
3. 面向对象阶段  
   80年代初期到现在，随着计算机不断普及，计算机性能以及需求不断增加，面向对象的程序设计被逐步提出，在对象的世界中 ，程序设计中大大减少了重复设计的部分，数据结构在这个阶段逐渐变得丰富，大量的封装类出现，减少了程序设计者的负担，数据结构因此变得更加友好。

### Ⅱ、算法基础
#### 算法的特性
1. 输入、输出  
   算法具有**零个**或者多个输入，同时，算法具有至少一个的输出。
2. 确定性  
   算法的每一步都具有确定的含义，**无二义性**。任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
3. 有穷性  
   一个算法总是需要（输入合法的情况下）在有限的步骤结束，即每个算法需要在有穷的时间内完成。
4. 可行性  
   一个算法是可以被执行的，即算法中的每个操作都可以通过已经实现的基本运算执行有限的次数完成。
#### 算法设计要求
1. 正确性（Correctness）  
   正确性指的是该算法能够满足预先指定的功能与性能的需求，即能够得到正确答案。
   其大致可以分为以下四点：
   * 该算法中不含任何语法错误。
   * 程序对于几组输入数据能够得到满足需求的结果。
   * 程序对于非法的输入也能够得到满足需求说明的结果（如抛出异常）。
   * 程序对于精心挑选的严苛数据依旧能够产生满足需求的结果。
2. 健壮性（Robustness）  
    健壮性指的是当输入数据不合法时，算法也能做出相关的处理，而不是产生不可预计的效果。
3. 可读性（Readability）  
   可读性指的是算法是可以阅读，理解和交流的。
4. 耗时低，占用空间少  
   运行时间（Running time）与占用空间（Storage space）概念，在设计算法时，我们总是希望能够更少的使用时间和空间达成我们的目标。

### Ⅲ、数据结构基础
#### 基本概念和术语
[术语表](./glossary.md "./glossary.md")  
1. 数据（Data）  
   数据是信息的载体，是可以被计算机识别，存储并加工处理的描述客观事物的信息符号的总称。数据不仅仅包括了整形，浮点数等数值类型，还包括了字符甚至声音，视频，图像等非数值的类型。
2. 数据元素（Data Element）  
   数据元素是描述数据的基本单位，也被称为记录。一个数据元素有若干个数据项组成。
3. 数据项（Data Item）  
   数据项是描述数据的最小单位，其可以分为组合项和原子项：  
   * 组合项  
    如果数据元素可以再度分割，则每一个独立处理单元就是数据项，数据元素就是数据项的集合。  
   * 原子项  
    如果数据元素不能再度分割，则每一个独立处理的单元就是原子项。
4. 数据对象（Data Object）  
   数据对象是性质相同的一类数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。
5. 数据结构（Data Structures）  
   数据结构主要是指**数据和关系的集合**，数据指的是计算机中需要处理的数据，而关系指的是这些数据相关的前后逻辑，这些逻辑**与计算机储存的位置无关**，其主要包含以下四大逻辑结构。
#### 逻辑结构（Logic Structure）
1. 集合结构（Set Structure）  
   集合结构中所有数据元素除了同属于一个集合外，并无其他关系。
2. 线性结构（Linear Structure）  
   线性结构指的是数据元素之间存在“一对一的关系”
3. 树形结构（Tree Structure）  
   树形结构指的是数据元素之间存在“一对多”的层次关系。
4. 图形结构（Graphic Structure）  
   图形结构（也称：网状结构）指的是数据元素之间存在“多对多的关系”（注：此时的“多对多”中的多表示，至少有一个）

#### 存储结构（Storage Structure）
1. 顺序存储结构（Sequential Storage Structure）：是把数据元素存放在地址连续存储单元里，其数据间的逻辑关系和物理关系是一致的。  
   优点:可以随机访问存储单元，时间复杂度为O(1)。  
   缺点:增加或者删除元素需要移动元素。  
2. 链式存储结构（Linked Storage Structure）：把数据元素存放在任意的存储单元中，可以连续可以不连续，并不能反映其逻辑关系，因此需要一个指针存放其他数据元素的地址，这样通过地址找到相关联数据元素的位置。  
   优点:增加或者删除节点方便。  
   缺点:存储结构的存储密度小，每个节点都有指针域不能随机访问存储单元。  
3. 索引存储结构（Index Storage Structure）：该方式是在存储节点信息的同时，还建立附加的索引表。  
   稠密索引（Dense Index）:每个节点都在索引表中有个一个索引，存储形式：（关键字，每个节点的存储位置）  
   稀疏索引（Spare Index）: 每组在索引表中有个一个索引，存储形式：（关键字，每组节点的起始存储位置）  
   (关键字是能够唯一标识一个节点的哪些数据项)  
   优点:利用节点索引号来检索速度快。  
   缺点:增加了索引表，会占用较多的存储空间。  
4. 散列存储结构（Hash Storage Structure）：散列存储是根据节点的关键字直接计算出该节点的存储地址的一种存储方式。通过哈希函数解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值座位该数据元素的存储地址  
   优点：存取速度快。
   缺点：只能按关键字随机存取，不能顺序窜出，也不能折半存取。

#### 数据类型
1. 数据类型（Data Type）  
   数据类型是高级程序设计语言中的概念，是数据的取值范围和对数进行操作的总和。数据类型规定了程序中对象的特性。程序中的每一个变量，常量或者表达式都属于一种数据类型。
2. 抽象数据类型（Abstract Data Type，ADT）  
   抽象数据类型是一个数学模型以及定义在模型上的一组操作。通常是对数据的抽象，定义了数据的取值范围以及对数据操作的集合。抽象数据类型的特征是实现与操作分离，从而实现封装。  
   使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
3. 抽象数据类型表示法  
   * 三元组表示：（D，S，P）  
    其中D是数据对象，S是D上的关系集，P是对D的基本操作集。
   * 书中的定义格式：  
        ```
        ADT 抽象数据类型名{
        数据对象：<数据对象的定义>
        数据关系：<数据关系的定义>
        基本操作：<基本操作的定义>
        }ADT 抽象数据类型名
        ```

### Ⅳ、复杂度概念
#### 时间空间复杂度定义
1. 时间复杂度  
   时间复杂度表示一个程序运行所需要的时间，其具体需要在机器环境中才能得到具体的值，但我们一般并不需要得到详细的值，只是需要比较快慢的区别即可，为此，我们需要引入时间频度（语句频度）的概念。  
   时间频度中，n称为问题的规模，当n不断变化时,时间频度T(n)也会不断变化。一般情况下，算法中的基本操作重复次数的是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。**记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。**
2. 空间复杂度  
   一个程序的空间复杂度是指运行完一个程序所需内存的大小，其包括两个部分。
   * 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
   * 可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
#### 度量时间复杂度的两种方法
1. 事后统计法  
   顾名思义，就是指在程序运行结束之后直接查看运行时间的方式进行时间复杂度的统计，通常采用利用计算机的计时器对不同算法编制的程序进行运行时间的比较，从而确认一个算法的效率。  
   但这种方法有很多缺陷：  
   * 特别依赖计算机环境，同一套算法可能在不同的计算机上面有着截然不同的效果，老式的计算机和现代电脑的算力完完全全不是一个级别的处理速度。
   * 算法的测试困难，有时一套算法需要海量的数据才能真正比较出效果，而为了设计这样的海量数据以及正确性，则需要花费大量的时间，而对于不同的数据，同一算法又有不一样的效果，故对于数据的使用很难去抉择。
2. 事先估计法
   与事后统计法不一样，事先统计法采取在计算机编译程序前对该算法进行预估的方式估算。我们可以通过利用时间频度以及函数的思维进行对时间复杂度的解析。  
   这里就不得不讲**函数符号**，它通常用来描述算法的时间复杂度，其中:  
   〇表示最坏情况，Ω表示最好情况，θ表示平均情况，我们常用的分析使用O进行表示即可。对于一个算法的时间复杂度而言，n表示其执行问题的规模，O(n)表示执行该问题需要的时间量级，如O(n)表示线性级别，O(n2)表示平方级别，其中n主要的判断方式为算法中循环结构的执行次数。
   以下为一些常用的基本公式：    
   * O(a）=O(1)      其中a为常数  
   * O(an)=O(n)     其中a为常数  
   * O(an2+bn+c)=O(n2)      其中a,b,c均为常数，结果只与最大项n有关  
### Ⅴ、时间复杂度的度量方法
   在理解了时间复杂度的概念后，就可以根据实际的代码进行度量了，以下举例了几个常用的时间复杂度的表示，对于如何度量其最重要的是观察程序中的循环结构，每一个循环结构代表执行循环中的指令n次，而其余指令一般而言一行代码代表执行一次，对于一个程序而言，执行的次数相差较小其实没有什么区别，都是一瞬间执行完毕。
#### 度量时间复杂度
1. O(1)  
   ```C
   #include<stdio.h>
   int main(){
      printf("Hello World");  //执行一次
      return 0;       //执行一次
   }
   ```
   执行了两次，即O(2)=O(1)
2. O(n)  
   ```C
   #include<stdio.h>
   int main(){
       int n=10000,ans=0;  //执行一次
       for(int i=0;i<n;i++){   //执行n次
           ans+=i;     //执行一次
       }
       return 0;       //执行一次
   }
   ```
   执行了n*1+2次，即O(n)
3. O(n^2)  
   ```C
   #include<stdio.h>
   int main(){
       int n=10000,ans=0;  //执行一次
       for(int i=0;i<n;i++){   //执行n次
           for(int j=0;j<n;j++){   //执行n次
               ans+=j;
           }
       }
       return 0;       //执行一次
   }
   ```
   执行了n\*n\*1+2次,即O(n^2)
4. O(logn)  
   ```C
   #include<stdio.h>
   int main(){
       int i=1,n=10000;    //执行一次
       while(i<=n){    //执行logn次
           i*=2;
       }
       return 0;       //执行一次
   }
   ```
   O(logn+2)=O(logn)
5. O(n*logn)
   ```C
   #include<stdio.h>
   int main(){
       int n=10000,ans=0;  //执行一次
       for(int i=0;i<n;i++){   //执行n次
           int j=0;        //执行1次
           while(j<=n){    //执行log(n)次
               j*=2;
           }
       }
       return 0;       //执行一次
   }
   ```
   O(n\*(logn+1)+2)=O(n\*logn)
#### 各个复杂度的比较
**O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)**

### Ⅵ、内存与地址
#### 内存
每一段的内存中的数据，都有一个地址与之相对应，也真是因为有地址的存在，我们计算机中才可以轻易的去访问到其中数据，拿一个数组来说，数组在C语言中是顺序存储的，因此，如上图的数据直接用代码找到其数据以及地址的话可以这样写
```C
#include<stdio.h>
int main(){
    int i;
    char array[10]="ACDEQSFVCK";
    for(i=0;i<10;i++){
        printf("The %c Address is %x \n",array[i],&array[i]);
       //%x可以换成%p都是十六进制表示，只不过%p会把所有的位数显示出来
    }
    return 0;
}
```
其数据的输出结果如下（注意，不同的电脑可能地址不一样）：  
The A Address is 62fe40  
The C Address is 62fe41  
The D Address is 62fe42  
The E Address is 62fe43  
The Q Address is 62fe44  
The S Address is 62fe45  
The F Address is 62fe46  
The V Address is 62fe47  
The C Address is 62fe48  
The K Address is 62fe49  
可以看到这是一段连续的地址，当你把char类型换成int型之后可能又不太一样，因为char是1字节的，而int占4字节，所以int的地址会变成4个一跳的方式往上增长。
#### Malloc函数  
malloc()函数(stdlib.h)在堆中申请分配一个大小为size个字节的连续内存空间，若成功分配，则返回一个指向所分配空间起始地址的指针，否则返回空指针（NULL）。
#### Free函数  
free()函数(stdlib.h)用来释放已分配的内存空间，参数p是待释放的内存空间的首指针。
一般而言，常规的内存分配，使用再到释放的过程如下：
```C
#include<stdio.h>
#include<stdlib.h>
int main(){
    int *p;     //定义一个指向整形的指针变量
    p=(int*)malloc(5*sizeof(int));  //申请5个整形大小的内存空间并返回起始地址给p
    if(p==NULL){    //申请失败
        //执行申请失败的代码，一般print一个报错
        exit(1);    //退出
    }
    p[0]=1000;  //为空间中添加数据
    printf("%d",p[0]);  //打印这个数据
    free(p);    //释放p的内存空间，此时p依旧存在，只不过失去了指向的对象，成了野指针
    p=NULL; //为其赋NULL，此时它不再是一个野指针
    return 0;
}
```
我们设计一个数据结构程序的过程是先定义所需要的变量与指针变量---->进行内存分配---->判断是否分配成功(分配不成功就报错或者退出程序)---->对指针空间中的数据进行操作(如赋值，修改，查询，删除) ---->完成操作后释放指针
```mermaid
graph TD
    A(定义所需要的变量与指针变量)-->B(进行内存分配)--成功-->C(对指针空间中的数据进行操作)-->D(完成操作后释放指针)
    B--失败-->E(报错或者退出程序)
```


除上文提到的两个函数外，在C++中引入的对象思维，有一个极其类似于malloc函数的方法，就是new方法，但他们还是有一些区别的：

new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。


### Ⅶ、基本数据类型（C）

#### 整数类型
| 类型             | 存储大小（字节） | 值范围                                               |
|----------------|----------|---------------------------------------------------|
| char           | 1        | -128 ~ 127 或 0 ~ 255                              |
| unsigned char  | 1        | 0 ~ 255                                           |
| signed char    | 1        | -128 ~ 127                                        |
| int            | 2 或 4    | -32,768 ~ 32,767 或 -2,147,483,648 ~ 2,147,483,647 |
| unsigned int   | 2 或 4    | 0 ~ 65,535 或 0 ~ 4,294,967,295                    |
| short          | 2        | -32,768 ~ 32,767                                  |
| unsigned short | 2        | 0 ~ 65,535                                        |
| long           | 4        | -2,147,483,648 ~ 2,147,483,647                    |
| unsigned long  | 4        | 0 ~ 4,294,967,295                                 |

#### 浮点类型
| 类型          | 存储大小（字节） | 值范围                   | 精度      |
|-------------|----------|-----------------------|---------|
| float       | 4        | 1.2E-38 到 3.4E+38     | 6 位有效位  |
| double      | 8        | 2.3E-308 到 1.7E+308   | 15 位有效位 |
| long double | 16       | 3.4E-4932 到 1.1E+4932 | 19 位有效位 |

#### void 类型
| 类型        | 描述                                                                                                |
|-----------|---------------------------------------------------------------------------------------------------|
| 函数返回为空    | C 中有各种函数都不返回值，或者您可以说它们返回空。不返回值的函数的返回类型为空。例如 void exit (int status);                               |
| 函数参数为空    | C 中有各种函数不接受任何参数。不带参数的函数可以接受一个 void。例如 int rand(void);                                             |
| 指针指向 void | 类型为 void * 的指针代表对象的地址，而不是类型。例如，内存分配函数 void *malloc( size_t size ); 返回指向 void 的指针，**可以转换为任何数据类型**。 |

#### 枚举(enum)
第一个枚举成员的默认值为整型的 0，后续枚举成员的值在前一个成员上加 1。  
在C 语言中，枚举类型是被当做 int 或者 unsigned int 类型来处理的，所以按照 C 语言规范是没有办法遍历枚举类型的。  
枚举有符号，枚举变量的大小是 1<=sizeof(enum)<=sizeof(int) 字节 （1-4字节），根据最大数值大小分配内存。  

```C
// 不定义枚举类型，不定义枚举变量
enum 
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
};
```

```C
// 先定义枚举类型，再定义枚举变量
enum DAY
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
};
enum DAY day;
```

```C
// 定义枚举类型的同时定义枚举变量
enum DAY
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
} day;
```

```C
// 省略枚举名称，直接定义枚举变量
enum
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
} day;
```

```C
// 定义枚举类型别名
typedef enum 
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
}Day;
Day day;
```
枚举的作用：  
1. 为固定的值命名，当作数组访问的下标，当固定的数据很多时，比如有几十上百个，那么如果你应0-100去表示就很难记住每个值代表什么意思。
2. 可以作为一个变量，灵活分配数组大小。在定义数组的时候，直接用该枚举类型的最后一个值作为数组大小。下次要增加或者减少数组参数的时候就不用去改数组大小了，非常方便。
3. 枚举作为设置值。比如某一寄存器的设置，每一个枚举值都代表着一个模式，最后通过把这些值写入相应寄存器，最终完成GPIO的模式配置。
4. 作为状态值。不用数字加注释去标记程序的状态，直接枚举类型提高代码可读性，方便查阅修改。
### Ⅷ、派生数据类型（C）

#### 指针(pointer)
[网页资料](https://www.runoob.com/w3cnote/c-pointer-detail.html "菜鸟教程")

[]优先级高于单目*运算符
```C
*a[i]//先结合[]，取数组索引i，再结合*取值，可判断a为指针数组。
(*a)[i]//先取值，再取索引i，可判断a为数组指针。
```

#### 结构体(struct)
[网页资料](https://www.runoob.com/w3cnote/c-structures-intro.html "菜鸟教程")

.：访问结构体成员
->：访问结构体指针成员
**[位域](https://www.runoob.com/cprogramming/c-bit-fields.html "菜鸟教程")**  
* 当相邻成员的类型相同时，如果它们的位宽之和小于类型的大小，那么后面的成员紧邻前一个成员存储，直到不能容纳为止；如果它们的位宽之和大于类型的大小，那么后面的成员将从新的存储单元开始，其偏移量为类型大小的整数倍。
  ```C
   int main(){
      struct bs{
         unsigned m: 6;
         unsigned n: 12;
         unsigned p: 4;
   };   //sizeof(bs)为4
  ```
  m、n、p 的类型都是 unsigned int，sizeof 的结果为 4 个字节（Byte），也即 32 个位（Bit）。m、n、p 的位宽之和为 6+12+4 = 22，小于 32，所以它们会挨着存储，中间没有缝隙。  
  如果将成员 m 的位宽改为 22，那么输出结果将会是 8，因为 22+12 = 34，大于 32，n 会从新的位置开始存储，相对 m 的偏移量是 sizeof(unsigned int)，也即 4 个字节。  
  如果再将成员 p 的位宽也改为 22，那么输出结果将会是 12，三个成员都不会挨着存储。  
* 当相邻成员的类型不同时，不同的编译器有不同的实现方案，GCC 会压缩存储，而 VC/VS 不会。
   ```C
   struct bs{
      unsigned m: 12;
      unsigned char ch: 4;
      unsigned p: 4;
   };
   ```
   在 GCC 下的运行结果为 4，三个成员挨着存储；在 VC/VS 下的运行结果为 12，三个成员按照各自的类型存储（与不指定位宽时的存储方式相同）。
* 如果成员之间穿插着非位域成员，那么不会进行压缩。例如对于下面的 bs：
  ```C
   struct bs{
      unsigned m: 12;
      unsigned ch;
      unsigned p: 4;
   };
  ```
* 位域成员可以没有名称，只给出数据类型和位宽，一般用来作填充或者调整成员位置。因为没有名称，无名位域不能使用。如下所示：
  ```C
   struct bs{
      int m: 12;
      int  : 20;  //该位域成员不能使用
      int n: 4;
   };
  ```
* 位域的宽度不能超过它所依附的数据类型的长度，成员变量都是有类型的，这个类型限制了成员变量的最大长度，: 后面的数字不能超过这个长度。
* 位域的陷阱：位域在内存中的布局是与机器相关的，具有**固有的不可移植的特性**。使用位域的时候，必须明确程序运行的机器是大端还是小端，再在代码中定义各位域的具体顺序。  

**大小端**  
大小端存储由 CPU架构 决定。  
大端模式（ big endian ）：低地址存在高位，高地址存在低位。  
小端模式（ Little Endian ）：低地址存在低位；高地址高位。  
使用大端模式的有：TCP/IP网络数据流；使用小端模式的有：x86；ARM可以是大端模式，也可以是小端模式；
#### 共用体(union)
[网页资料](https://www.runoob.com/cprogramming/c-unions.html "菜鸟教程")

共用体的作用：  
如下代码利用重叠技术实现用UINT型对数组数据进行接收，然后再将其组合成浮点型（32位）数据进行赋值。
```C
static union
{
    uint8_t data[24];
    float ActVal[6];
}posture;
        
 if(USART_GetITStatus(USART1, USART_IT_RXNE)==SET)   
{
    USART_ClearITPendingBit( USART1,USART_IT_RXNE);
    ch=USART_ReceiveData(USART1);
    posture.data[i] = ch;
    i++;
    if(i >= 24)
    {
        i = 0;
                break;
    }
    
}             
SetPositionX(posture.ActVal[3]);
SetPositionY(posture.ActVal[4]);
SetAngle(posture.ActVal[0]);
```
#### 数组(array)
[网页资料](https://www.runoob.com/cprogramming/c-arrays.html "菜鸟教程")

```C
int **res;//二维动态数组初始化与访问
res=(int**)malloc(size*sizeof(int*));
for (int i = 0; i < size; i++) {
   res[i] = (int *) calloc(colsize, sizeof(int));
}
res[0][0] = 1;
```
**注意**：
memset()只能用于char类型（字符串），它写入的尺度是1字节，如果类型为int（4字节），会导致错误。
#### 串(string)（非派生类型）

注意：
strlen是string.h中的函数，以'\0'结束。  
sizeof是运算操作符。

| 函数              | 目的                                                       |
|-----------------|----------------------------------------------------------|
| strcpy(s1, s2); | 复制字符串 s2 到字符串 s1。                                        |
| strcat(s1, s2); | 连接字符串 s2 到字符串 s1 的末尾。                                    |
| strlen(s1);     | 返回字符串 s1 的长度。                                            |
| strcmp(s1, s2); | 如果 s1 和 s2 是相同的，则返回 0；如果 s1<s2 则返回小于 0；如果 s1>s2 则返回大于 0。 |
| strchr(s1, ch); | 返回一个指针，指向字符串 s1 中字符 ch 的第一次出现的位置。                        |
| strstr(s1, s2); | 返回一个指针，指向字符串 s1 中字符串 s2 的第一次出现的位置。                       |

##### KMP算法（快速模式匹配算法）
[网页资料](http://data.biancheng.net/view/180.html "菜鸟教程")

### Ⅸ、基本存储型
1. auto  
   auto 存储类是所有**局部变量默认**的存储类。
2. register  
   register 存储类用于定义**存储在寄存器中**而不是 RAM 中的局部变量。这意味着变量的最大尺寸等于寄存器的大小（通常是一个字），且不能对它应用一元的 '&' 运算符（因为它没有内存位置）。  
   定义 'register' 并不意味着变量将被存储在寄存器中，它意味着变量可能存储在寄存器中，这**取决于硬件和实现的限制**。
3. static  
   static 存储类指示编译器在**程序的生命周期内保持局部变量的存在**，而不需要在每次它进入和离开作用域时进行创建和销毁。因此，使用 static 修饰局部变量可以在函数调用之间保持局部变量的值。  
   static 修饰符也可以应用于全局变量。当 static 修饰全局变量时，会使变量的**作用域限制在声明它的文件内**。  
   全局声明的一个 static 变量或方法可以被任何函数或方法调用，只要这些方法出现在跟 static 变量或方法同一个文件中。
1. extern  
   extern 存储类用于提供一个全局变量的引用，全局变量**对所有的程序文件都是可见的**。当您使用 extern 时，对于无法初始化的变量，会把变量名指向一个之前定义过的存储位置。  
   当您有多个文件且定义了一个可以在其他文件中使用的全局变量或函数时，可以在其他文件中使用 extern 来得到已定义的变量或函数的引用。可以这么理解，extern 是**用来在另一个文件中声明一个全局变量或函数**。  

   ```C
   extern int a; // 声明一个全局变量 a
   int a; // 定义一个全局变量 a
   extern int a =0 ; // 定义一个全局变量 a 并给初值。
   int a =0;    // 定义一个全局变量 a, 并给初值，
   ```
   头文件中只存放“声明”，而不存放“定义”。  
   不提倡使用全局变量，尽量不要在头文件中出现现象 extern int value 这类声明，用访问器（函数）替代全局变量。  
## 第二章 线性结构
### Ⅰ、线性表(Linear List)
#### 逻辑结构
线性表是n(n>=0)个数据元素的有限序列。在表中，元素存在线性的逻辑关系：表中有且仅有一个开始结点;有且仅有一个终端结点；除开始结点外，表中的每个结点均只有一个前驱结点(predecessor);除终端结点外，表中的每个结点均只有一个后继结点(successor)。根据它们之间的关系可以排成一个线性序列,记作（a1,a2,…,an）
#### 基本操作
| N   | 方法                | 描述                               |
|-----|-------------------|----------------------------------|
| 1.  | InitList(L)       | 线性表初始化,构造一个空的线性表L                |
| 2.  | ListLength(L)     | 求线性表的长度,返回线性表L中数据元素的个数           |
| 3.  | GetElem(L,i,x)    | 用x返回线性表中的第i个数据元素的值               |
| 4.  | locaionElem(L,x)  | 按值查找,确定数据元素x在表中的位置               |
| 5.  | ListInsert(L,i,x) | 插入操作,在线性表L中第i个位置之前插入一个新元素。L的长度加1 |
| 6.  | ListDelete(L,i)   | 删除操作,删除线性表L中的第i个元素,L的长度减1        |
| 7.  | ListEmpty(L)      | 判断线性表L是否为空,空表返回TRUE,非空表返回FALSE   |
| 8.  | ClearList(L)      | 将已知的线性表L置为空表                     |
| 9.  | DestroyList(L)    | 销毁线性表L                           |

其他操作：合并、分拆、复制、排序等等。
#### 顺序表(Sequential List)
[代码示例](./Linear&#x20;Structure/linear_list/sq_list.h "sq_list.h")  


**顺序存储**是指在内存中用一块地址连续的存储空间按顺序存储线性表的各个数据元素。  
采用顺序存储结构的线性表称为“顺序表”，顺序表中逻辑上相邻的数据元素在物理存储位置上也是相邻的。  
物理结构上由数组来实现。
* 静态分配  
```C
typedef struct {
	int data[InitList];
	int length;
}SqlList;
```
* 动态分配  
```C
typedef struct {
    int *data;
    int length;   //当前长度
    int MaxSize;  //最大长度
} SqlList;
```

#### 单向链表(Singly Linked List)
[代码示例](Linear&#x20;Structure/linear_list/sl_list.h "sl_list.h") 

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示的线性表称作线性链表（单链表），单链表是**链式存储**的结构。  
```C
typedef struct Node {
    int data;           //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
    struct Node *next;  //单链表的指针域
} Node,*LinkedList;     //Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型
```

#### 双向链表(Double Linked List)
[代码示例](Linear&#x20;Structure/linear_list/dl_list.h "dl_list.h")
   
在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表。  
双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。  
一个完整的双向链表应该是头结点的pre指针指为空，尾结点的next指针指向空，其余结点前后相链。  
```C
typedef struct DNode {
    ElemType data;
    struct DNode* prior, * next;
}DNode, * DLinkList;
```
#### 循环链表(Circular Linked Lists)
[代码示例](Linear&#x20;Structure/linear_list/cl_list.h "cl_list.h")
  
循环链表的尾指针指向的是链表的开头。  
通过将单链表的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）。  
```C
typedef struct LNode {
    int data;
    struct LNode* next;
}LNode, * LinkList;
```

### Ⅱ、栈(Stack)
#### 逻辑结构  
只允许在一端进行插入或删除操作的线性表。  
栈是一种后进先出（LIFO）的数据结构。  
术语：栈顶、栈底、空栈。  
#### 基本操作  
| N   | 方法               | 描述                        |
|-----|------------------|---------------------------|
| 1.  | InitStack(&S)    | 初始化栈。构造一个空栈 S，分配内存空间      |
| 2.  | DestroyStack(&S) | 销毁栈。销毁并释放栈 S 所占用的内存空间     |
| 3.  | Push(&S,x)       | 入栈，若栈S未满，则将x加入使之成为新栈顶     |
| 4.  | Pop(&S,&x)       | 出栈，若栈S非空，则弹出栈顶元素，并用x返回    |
| 5.  | GetTop(S, &x)    | 读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素 |

#### 顺序栈  

* 数组实现
[代码示例](./Linear&#x20;Structure/stack/sq_stack.cpp "sq_stack.cpp")
  
   ```C
   typedef int ElemType;

   typedef struct {
      ElemType data[MaxSize];
      int top;
   } SqStack;
   ```
* 链表实现
[代码示例](./Linear&#x20;Structure/stack/sql_stack.cpp "sql_stack.cpp")
  
  优点: 便于多个栈共享储存空间,提高其效率,不会栈满上溢  
  特点：所有操作在表头进行,通常没有头结点,将头指针作为栈顶指针,便于结点插入/删除
   ```C
   bool Push(LiStack &S, ElemType x) {
      auto p = (LinkNode *) malloc(sizeof(LinkNode));
      if (p == nullptr) return false;
      p->data = x;
      p->next = S;
      S = p;
      return true;
   }
   ```
#### 共享栈
[代码示例](./Linear&#x20;Structure/stack/sh_stack.cpp "sh_stack.cpp")

定义: 将两个栈的栈底设置在共享空间的两端,两个栈顶向中间延伸
   ```C
   typedef int ElemType;

   typedef struct {
      ElemType data[MaxSize];
      int top0;
      int top1;
   } ShStack;
   ```

### Ⅲ、队列(Queue)
#### 逻辑结构  
只允许在一端进行插入（入队），在另一端删除（出队）的线性表。  
队列是一种先进先出（FIFO）的数据结构。  
术语：队头、队尾、空队列。
#### 基本操作  
| N   | 方法               | 描述                      |
|-----|------------------|-------------------------|
| 1.  | InitQueue(&Q)    | 初始化队列，构造一个空队列Q          |
| 2.  | DestroyQueue(&Q) | 销毁队列。销毁并释放队列Q所占用的内存空间   |
| 3.  | EnQueue(&Q,x)    | 入队，若队列Q未满，将x加入，使之成为新的队尾 |
| 4.  | DeQueue(&Q,&x)   | 出队，若队列Q非空，删除队头元素，并用x返回  |
| 5.  | GetHead(Q,&x)    | 读队头元素，若队列Q非空，则将队头元素赋值给x |

#### 顺序队列(Sequential Queue)
一般采用链表实现，**长度不固定**。  
* ~~数组实现~~
[代码示例](./Linear&#x20;Structure/queue/sq_queue.cpp "sq_queue.cpp")  

  无法正常使用，当rear到达数组末端，未采用循环机制进行将导致空间用尽。  
* 链表实现
[代码示例](./Linear&#x20;Structure/queue/sql_queue.cpp "sql_queue.cpp")
  
  链表长度不固定可以动态申请，避免数组空间用尽的问题。  
  ```C
  typedef int ElemType;
    
  typedef struct LinkNode {
      ElemType data;
      struct LinkNode *next;
  } LinkNode;
    
  typedef struct {
      LinkNode *front, *rear;
  } LinkQueue;
  ```
#### 循环队列(Sequential Queue)
**长度固定**，只能存入有限数量元素。
* 数组实现
[代码示例](./Linear&#x20;Structure/queue/c_queue.cpp "c_queue.cpp")
  
  front、rear到达数组末端时，移动到数组头部进行循环，缺点在于：front=rear时，队列可能为空可能为满。
  解决front=rear的多状态问题，可以采用的方法：  
  1. rear指向队尾后一个元素，且保持该元素为空，此时front=rear仅包含队空的状态；缺点是数组空置一个空间；
  2. （推荐）入队出队时记录当前的队列长度；  
  3. 记录上一个操作是入队（队满）还是出队（队空）。  
   ```C
   typedef int ElemType;
   
   typedef struct {
      int front, rear;
      int size;
      ElemType data[MaxSize];
   } CQueue;
   ```
* 链表实现
[代码示例](./Linear&#x20;Structure/queue/cl_queue.cpp "cl_queue.cpp")
  
  使用循环链表模拟循环队列固定长度的情景。
   ```C
   typedef int ElemType;

   typedef struct LinkNode {
      ElemType data;
      struct LinkNode *next;
   } LinkNode;

   typedef struct {
      LinkNode *front, *rear;
      int size;
   } ClQueue;
   ```
#### 双端队列(Double-Ended Queue)
[代码示例](./Linear&#x20;Structure/queue/de_queue.cpp "de_queue.cpp")
  
双端队列即在两端都可以执行入队和出队操作的数据结构。  
```C
bool EnQueue_Head(DeQue &Q, ElemType x) {
    if (QueueFull(Q)) return false;
    Q.front = (Q.front - 1 + MaxSize) % MaxSize;
    Q.data[Q.front] = x;
    Q.size++;
    return true;
}

bool DeQueue_Rear(DeQue &Q, ElemType &x) {
    if (QueueEmpty(Q)) return false;
    Q.rear = (Q.rear - 1 + MaxSize) % MaxSize;
    x = Q.data[Q.rear];
    Q.size--;
    return true;
}
```



## 第三章 非线性结构  

### Ⅰ、树(Tree)

#### 逻辑结构
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。  

 **树的基本术语**  

* **节点的度**：树中某个节点的子树的个数。

* **树的度**：树中各节点的度的最大值。

* 分支节点：度不为零的节点。

* 叶子节点：度为零的节点。

* 路径长度：路径上经过的边的个数。

* 孩子节点：某节点的后继节点；双亲节点：该节点为其孩子节点的双亲节点（父母节点）；兄弟节点：同一双亲的孩子节点；子孙节点：某节点所有子树中的节点；祖先节点：从树节点到该节点的路径上的节点。

* **树的高度(深度)**：树中结点的最大层数。**结点的深度**：从根结点开始自顶向下逐层累加。**结点的高度**：从叶结点开始自底向上逐层累加。

* 有序树：树中节点子树按次序从左向右安排，次序不能改变；无序树：与之相反

* 森林：互不相交的树的集合。

* 有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

* 无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

* **度为m的树**: 度最大的节点的度为m，必须是非空树；**m叉树**：节点的最大度为m，度最大的节点的度可以小于等于m，允许是空树。

**树的性值**  

* 结点数=总度数+1（加根节点）。

* 度为m的树中第i层最多有$m^{i-1}$个节点。

* 高度为h的m次树至多$\frac{m^h-1}{m-1}$个节点。

* 具有n个节点的m次树的最小高度为$log_m( n(m-1) + 1 )$向上取整。

#### 二叉树(Binary Tree)
[代码示例](./Non-linear&#x20;Structure/tree/b_tree.cpp "b_tree.cpp")
  

**二叉树的特点**

1. 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。

2. 左子树和右子树是有顺序的，次序不能任意颠倒。

3. 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

**二叉树的性质**

* 性质1：二叉树第$i$层上的结点数目最多为 $2^{i-1}$ 个节点$(i≥1)$。
* 性质2：深度为k的二叉树至多有$2$的$k$次方$-1$个结点$(k≥1)$。
* 性质3：包含n个结点的二叉树的高度至少为$log_2(n+1)$。
* 性质4：在任意一棵二叉树中，若终端结点的个数为$n0$，度为$2$的结点数为$n2$，则$n0=n2+1$。


**特殊二叉树**  

1. **斜树**  
所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

2. **满二叉树**  
在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。  
特点有：  
   1. 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

   2. 非叶子结点的度一定是2。

   3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

3. **完全二叉树**  
对一棵具有n个结点的二叉树按层编号，如果编号为$i(1<=i<=n)$的结点与同样深度的满二叉树中编号为 $i$ 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。  
特点有：  
   1. 叶子只能出现在最后两层。

   2. 最多只能有一个度为1的节点。

4. **二叉排序树**  

   1. 左子树上所有结点的关键字小于根结点

   2. 右子树上所有结点的关键字大于根结点

   3. 左右子树又各是一棵二叉排序树

5. **平衡二叉树**  
树上任一结点的左子树和右子树的深度之差不超过1（搜索效率高）

**二叉树的存储结构**  
* **线性存储**  
   二叉树的顺序存储结构，**只适合存储完全二叉树**，因为最坏情况下高度为h的右斜树，也至少需要$2^h-1$个存储单元  
   * i 的左孩子 ——2i
   * i 的右孩子 ——2i+1
   * i 的父节点—— i/2
   * i 所在的层次 —— log2(n + 1)或log2n+ 1

   若完全二叉树中共有n个结点，则

   * 判断 i 没有左孩子 ——2i < n
   * 判断 i 没有右孩子 ——2i+1 < n
   * 判断 i 不是叶子/分支结点 ——2i > n


* **链式存储**  

  1) 结点元素，data域，用来存储数据，其可以是int，char等基本的类型，同时也可以是struct等这些复杂的复合数据类型。

  2) 左孩子结点，left指针，总是用来指向当前结点的下一层的左边结点，其属于一种指针。

  3) 右孩子结点，right指针，总是用来指向当前结点的下一层的右边结点，其属于一种指针。

  4) 父结点（可选），parent指针，总是指向当前结点的前一个结点，简称父亲结点，其不属于必须结点设计，省略掉可以打扰节省内存的效果，而使用则可以更方便进行定向搜索，本案例中不使用父节点。

  5) 我们使用一棵树的时候需要建立一棵树根，由这个“根”，来进行逐步的向下构建。

  ```C++
  //树的结点
  typedef struct node{
     int data;
     struct node* left;
     struct node* right;
  } BiTNode，*BiTree;
  ```

**二叉树的遍历**  

1. 先序遍历（DFS）：根左右  
   ```C++
   //树的先序遍历 Pre-order traversal
   void preorder(Node* node){
      if (node != NULL)
      {
         printf("%d ",node->data);
         preorder(node->left);
         preorder(node->right);
      }
   }
   ```
   前缀表达式（波兰式）:(a+b)*c ——> *+cab  
2. 中序遍历（DFS）：左根右   
   ```C++
   //树的中序遍历 In-order traversal
   void inorder(Node* node){
      if (node != NULL)
      {
         inorder(node->left);
         printf("%d ",node->data);
         inorder(node->right);
      }
   }
   ```
   中缀表达式（常规算式）：(a+b)*c
3. 后序遍历（DFS）：左右根  
   ```C++
   //树的后序遍历 Post-order traversal
   void postorder(Node* node){
      if (node != NULL)
      {
         postorder(node->left);
         postorder(node->right);
         printf("%d ",node->data);
      }
   }
   ```
   后缀表达式（逆波兰式）:(a+b)\*c ——> ab+c\* 
4. 层序遍历（BFS）：
   1. 初始化一个辅助队列

   2. 根结点入队

   3. 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）

   4. 重复3直至队列为空

**由双遍历序列逆向构造二叉树**  
若只给出一棵二叉树的前、中、后、层序遍历序列中的一种，**不能唯一确定一棵二叉树**。  
仅仅由前序、后序、层序序列两两组合也无法唯一确定一棵二叉树，**必须有一个中序序列才能逆向构造**。
1. **前序+中序遍历序列**
   前序遍历序列：**根结点**——左子树的前序遍历序列——右子树的前序遍历序列
   中序遍历序列：左子树的中序遍历序列——**根结点**——右子树的中序遍历序列
2. **后序+中序遍历序列**
   后序遍历序列：左子树的中序遍历序列——右子树的中序遍历序列——**根结点**
   中序遍历序列：左子树的中序遍历序列——**根结点**——右子树的中序遍历序列
3. **层序+中序遍历序列**
   层序遍历序列：**根结点**——左子树的根——右子树的根
   中序遍历序列：左子树的中序遍历序列——**根结点**——右子树的中序遍历序列

#### 线索二叉树(Threaded Binary Tree)
[代码示例](./Non-linear&#x20;Structure/tree/tb_tree.cpp "tb_tree.cpp")
    
对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树。  

目的: 知道了“前驱”和“后继”信息，就可以把二叉树看作一个链表结构，从而可以像遍历链表那样来遍历二叉树，进而提高效率。  

如何线索化：所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继，所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。  
```C++
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;   //增加了左右标识域
}ThreadNode,*ThreadTree;
```
标识域：
如果ltag=0，表示指向节点的左孩子。如果ltag=1，则表示lchild为线索，指向节点的直接前驱
如果rtag=0，表示指向节点的右孩子。如果rtag=1，则表示rchild为线索，指向节点的直接后继

方法 | 中序线索二叉树 | 先序线索二叉树 | 后序线索二叉树
----|---------|---------|--------
找前驱 | √ | × | √ 
找后继 | √ | √ | × 

除非采用暴力或者三叉树才能实现表中打叉的部分,所以一般中序线索二叉树最常用。

#### 树、森林（forest）  
**树的存储结构**  

1. **双亲表示法**（顺序存储）  
   1. 定义: 连续空间存储,每个结点增设一个伪指针,**指示双亲在数组中位置**,根结点下标为0,其伪指针为-1
   2. 特点: 可以很快得到双亲,但求孩子要遍历整个结构
2. **孩子表示法**（顺序+链式存储）  
   1. 定义：顺序存储各个节点，每个结点中保存孩子链表头指针，链表中的元素为子节点的索引
   2. 特点: 求孩子很方便,求双亲不方便
3. **孩子兄弟表示法**（链式存储）  
   1. 定义: **左**指针指向第一个**孩子**,**右**指针指向第一个**兄弟**,二叉链表作为存储结构
   2. 优点: 方便实现树转化为二叉树,易于查找孩子
   3. 缺点: 查找双亲麻烦,若增设parent指向双亲,会方便
   ```mermaid
   graph TD;
   subgraph 二叉树
   A--son-->B;
   A---G(( ))
   B--son-->E;
   
   E---H(( ))
   E--bro-->F;
   
   C---I(( ))
   B--bro-->C--bro-->D;
   
   style G fill:#f100,opacity:0
   style H fill:#f100,opacity:0
   style I fill:#f100,opacity:0
   linkStyle 1,3,5 stroke:#fff,stroke-width:0px
   linkStyle 4,6,7 stroke:#f70
   end

   subgraph 树
   a-->b;
   a-->c;
   a-->d;
   b-->e;
   b-->f;
   end
   
   ```

**树、森林和二叉树的转换**

1. 树转换为二叉树  
左指针指向第一个孩子,右指针指向第一个兄弟,根没有兄弟,二叉树根节点没有右子树
2. 森林转化为二叉树  
森林中的树依次转化为二叉树，每棵二叉树的根依次作为上一颗二叉树的右子树
3. 二叉树转化为森林  
   1. 二叉树的根及左子树作为第一棵树的二叉树形态,再转换为树(右孩子变为兄弟)
   2. 根的右子树及其左孩子作为第二棵树,右孩子作为第三棵树,反复下去

**树和森林的遍历**  
1. 树的先根遍历（深度优先遍历DFS）
先访问根，再从左到右遍历每棵子树，**与相应二叉树的先序序列相同**。
2. 树的后根遍历（深度优先遍历DFS）
从左到右遍历每棵子树，再访问根，**与相应二叉树的中序序列相同**。
1. 树的层次遍历（广度优先遍历BFS）
   1. 若树非空，则根节点入队。
   2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队。
   3. 重复2直到队列为空。
2. 森林的先序遍历==依次对各个子树进行先序遍历
   若森林为非空，则按如下规则进行遍历：
   1. 访问森林中第一棵树的根结点。
   2. 先序遍历第一棵树中根结点的子树森林。
   3. 先序遍历除去第一棵树之后剩余的树构成的森林。
3. 森林的中序遍历==依次对各个子树进行后序遍历
   若森林为非空，则按如下规则进行遍历：
   1. 中序遍历森林中第一棵树的根结点的子树森林。
   2. 访问第一棵树的根结点。
   3. 中序遍历除去第一棵树之后剩余的树构成的森林。

#### 哈夫曼树（Huffman Tree）
[代码示例](./Non-linear&#x20;Structure/tree/hfm_tree.cpp "hfm_tree.cpp")
  
又名：最优二叉树  

其标准含义是：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。  

**基本术语**  
1) 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。  
2) 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。  
3) 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。  
4) 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。  
5) 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL”。

**构建哈夫曼树**
构建哈夫曼树时，只需要遵循一个原则，那就是权重越大的结点距离树根越近，权重小的节点远离根节点。由于性值，需要利用parent访问双亲节点。  
```C++
//哈夫曼树结点结构
typedef struct {
    int weight; //结点权重
    int parent, left, right;    //父结点、左孩子、右孩子在数组中的位置下标
} HTNode, *HuffmanTree;
```

1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。

2. 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新 结点的权值置为左、右子树上根结点的权值之和。

3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。

4. 重复步骤2和3，直至F中只剩下一棵树为止。

```mermaid
graph TD;
subgraph 构成哈夫曼树;
E(26)-->H(15);
H-->I((7));
H-->A((8));
E-->F;
F(11)-->B((6));
F-->G;
G(5)-->C((1));
G-->D((4));
end

subgraph 四个叶子节点
a((8));b((6));c((1));d((4));i((7));
end
```

如图这颗哈夫曼树的WPL值为：$$WPL=(1+4)\times3+(6+7+8)\times2 = 57$$

**哈夫曼树的特点**  
1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大  
2. 哈夫曼树的==结点总数为2n − 1==  
3. 哈夫曼树中不存在度为1的结点。  
4. 哈夫曼树并==不唯一==，但==WPL必然相同且为最优== 

**哈夫曼编码（Huffman Coding）**   

又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。主要目的是根据使用频率来最大化节省字符（编码）的存储空间。  

**性质**  
霍夫曼编码是一种前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。  
如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称该编码是 **“前缀无歧义编码”(prefix-free code)简称PFC编码** 。  

**构造哈夫曼编码**  
1. 字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树。  
2. 从根结点到叶子结点的路径上标记序列,0转向左孩子,1转向右孩子。
#### 并查集（Disjoint Set）
[代码示例](./Non-linear&#x20;Structure/tree/dj_set.cpp "dj_set.cpp")
  
并查集是一种树型的数据结构，它是逻辑结构**集合**的一种具体实现，用于处理一些不交集（Disjoint Sets）的合并及查询问题。  

**基本操作**  
* Find：确定元素属于哪一个子集。这个确定方法就是不断向上查找找到它的根节点，它可以被用来确定两个元素是否属于同一子集。  
* Union：将两个子集合并成同一个集合。  

**并查集的存储结构**  
用一个数组即可表示集合关系，使用双亲表示法（顺序存储），即数组存储双亲节点的数组下标，根节点的值为-1。  

**优化操作**  
1. 采用负数表示根节点，其绝对值为这棵树的总节点数或者树的深度。
2. “按秩合并”，Union合并操作时，将秩（深度）小的树合并到秩大的树的根节点上去，这样合并后的秩较小，可提高查询效率。
3. “路径压缩”，是一种在执行“查找”时扁平化树结构的方法。Find递归地经过树，改变每一个节点的引用到根节点。得到的树将更加扁平，为以后直接或者间接引用节点的操作加速。

#### 二叉搜索树（Binary search tree,BST）
[代码示例](./Non-linear&#x20;Structure/tree/bs_tree.cpp "bs_tree.cpp")
  
二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：
1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也为二叉查找树。
4. 没有值相等的节点。

**二叉搜索树的性能分析**  
对于有n个结点的二叉搜索树：  
1. 最优的情况下，二叉搜索树为完全二叉树，其平均比较次数为：$logN$
2. 最差的情况下，二叉搜索树退化为单支树，其平均比较次数为：$N/2$

#### 平衡二叉搜索树(balanced binary search tree, BBST)  
在插入和删除后，二叉搜索树性质＆平衡性破坏。  
为了防止BST出现性能下降，为 BST 引入了平衡的概念，来有效的控制树高，以追求更低的树。
**理想平衡**  
* 节点数目固定，兄弟子树高度越接近（平衡），全树的树高也将倾向于更低，若树高恰好为$log_2 n$,则称作理想平衡树。如完全二叉树，满二叉树等。  

**适度平衡**  
* 理想平衡出现的概率极低，维护的成本过高，故须适当的放低标准，引入适度平衡
* 高度渐进地不超过 $O(log n)$，即可称之为适度平衡 ，即 $height(Tree) = O(log n)$
* **适度平衡的BST**，称作平衡二叉搜索树BBST

**等价变换**  
对于 BST ，拓扑结构不尽相同，但**中序遍历序列**如果相同，则称之为 **等价 BST**。  
等价BST规律：  
1. 上下可变 ： 联结关系不尽相同  
2. 左右不乱 ： 中序序列不变  

基本操作  
1. **zig** ： 顺时针（向右R）旋转调整  
   ![zig](./img/3-8-1.png "zig")  
2. **zag** ：逆时针（向左L）旋转调整  
   ![zag](./img/3-8-2.png "zag")

**自平衡二叉搜索树（AVL tree）**[^1]  
[^1]:由G. M. Adelson-Velsky和E. M. Landis不1962年证明  

任一节点v的**平衡因子(balance factor)** 定义为“其左、右子树的高度差”,即
$balFac(v)=height(lc(v)) - height(rc(v))$
所谓AVL树,即平衡因子受限的二叉搜索树其中各节点平衡因子的绝对值均不超过1。 
**红黑树**  
**伸展树**  
**替罪羊树**  

#### 多路搜索树（MuitlWay Search Tree）

### Ⅱ、图（Graph）  

#### 逻辑结构  
图$G$由顶点集$V$和边集$E$组成，记为$G = (V, E)$，其中$V(G)$表示图$G$中顶点的 ==有限非空集==；$E(G)$ 表示图$G$中顶点之间的关系（边）集合。若$V = \{v1, v2, … , vn\}$，则用 ==$|V|$表示图$G$中顶点的个数==，也称图$G$的阶，$E = \{(u, v) | uÎV, vÎV\}$，用 ==$|E|$表示图G中边的条数==。  

注意：线性表可以是空表，树可以是空树，但图不可以是空，即**V一定是非空集** ，E可以是空集。  

**有向图**： 若E是有向边（也称弧）的有限集合时，则图G为有向图。 弧是顶点的有序对，记为==<v,w>，其中v、w是顶点，v称为 弧尾，w称为弧头==，称为从顶点v到顶点w的弧，也称 v邻接到w，或w邻接自v。 <v,w> ≠<w,v>  

**无向图**： 若E是无向边（简称边）的有限集合时，则图G为无向图。边 是顶点的无序对，记为(v, w)或(w, v)，因为==(v, w) = (w, v)，其 中v、w是顶点==。可以说顶点w和顶点v互为邻接点。边(v, w) 依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。  

**简单图**： 1. 不存在重复边； 2. 不存在顶点到自身的边。

**多重图**：图G中某两个结点之间的边数多于 一条，又允许顶点通过同一条边和自己关联， 则G为多重图。
#### 基本概念  
**顶点的度、入度、出度**  
**无向图**：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。无向图的全部顶点的度的和**等于边数的2倍**。
**有向图**： **入度**是以顶点v为终点的有向边的数目，记为ID(v)；**出度**是以顶点v为起点的有向边的数目，记为OD(v)。==顶点v的度==等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

**顶点-顶点的关系描述**  
* 路径——顶点vp到顶点vq之间的一条路径是指顶点序列 ，
* 回路——第一个顶点和最后一个顶点相同的路径称为回路或环
* 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。
* 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
* 路径长度——路径上边的数目
* 点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。 若从u到v根本不存在路径，则记该距离为无穷（∞）
* 无向图中，若从顶点v到顶点w有路径存在，则称v和w是**连通**的
* 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是**强连通**的
* 若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图
* 若图中任何一对顶点都是强连通的，则称此图为**强连通图**
* 子图： 设有两个图G = (V, E)和G’ = (V’,E’)，若V’是V的子集，且E’是 E的子集，则称G’ 是G的子图。
* 生成子图：满足 ==V(G’) = V(G)== 的子图G’
* 连通分量： 无向图中的极大连通子图称为连通分量。
* 极大连通子图：子图必须连通，且包含 尽可能多的顶点和边。
* 强连通分量:有向图中的极大强连通子图称为有向图的强连通分量。
* 连通图(无向)的**生成树**是包含图中全部顶点的一个极小连通子图。
* 若图中顶点数为n，则它的生成树含有 n-1 条边。
* 在非连通图中，连通分量的生成树构成了非连通图的生成森林。

**边的权、带权图/网**  
* 边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
* 带权图/网——边上带有权值的图称为带权图，也称网。
* 带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

**特殊形态的图**  
* 无向完全图——无向图中任意两个顶点之间都存在边。
* 有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧。
* 边数很少的图称为稀疏图，反之称为稠密图。
* 树——不存在回路，且连通的无向图，n个顶点的树，必有n-1条边。
* 有向树——一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

#### 图的存储
**邻接矩阵法（Adjacency Matrix）**  
* 第i个结点的度 = 第i行（或第i列）的非零元素个数
* 第i个结点的出度 = 第i行的非零元素个数
* 第i个结点的入度 = 第i列的非零元素个数
* 第i个结点的度 = 第i行、第i列的非零元素个数之和
* 邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)
* 空间复杂度：O(|V|2) ——只和顶点数相关，和实际的边数无关

邻接矩阵法的性质： 设图G的邻接矩阵为A（矩阵元素为0/1），则An 的元素An [i] [j]等于由顶点i到顶点j的长度为n的路径的数目。

特点：邻接矩阵存在以下缺点
1) 浪费空间—— 存稀疏图（点很多而边很少）有大量无效元素
2) 浪费时间—— 统计稀疏图中一共有多少条边

**邻接表法（Adjacency List）（顺序+链式存储）**  
通过链表或者利用数组模拟链表的方式将图的相连接关系表示的一种方法，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。空间复杂度：无向图O(|V|+2|E|)，有向图O(|V|+|E|)

邻接表的链表表示的是单向边关系，如果连接到空结点的那一条边不算，那么双向图的边正好就是单向图的两倍。

邻接表就相当于是一种改良，对于稀疏图能够很好的适应，使用较少的空间和时间就能表达。  

**邻接多重表（Adjacency Multilists）（顺序+链式存储）**  
顺序表存储顶点编号以及与顶点相连的第一条边的指针。链表用来表示边，存储边的两个顶点编号、权值以及对应顶点的下一条边的指针，删除边，删除节点等操作方便。但只适合用来**存储无向图**，因为不包含方向的信息。空间复杂度O(|V|+|E|)

**十字链表（Orthogonal List）（顺序+链式存储）**  
顺序表存储顶点编号以及与顶点相连的该顶点作为弧头的第一条弧、该顶点作为弧尾的第一条弧的指针。链表用来表示边，存储弧头弧尾编号、权值以及弧头相同的下一条弧、弧尾相同的下一条弧的指针，删除边，删除节点等操作方便。但只适合用来**存储有向图**，空间复杂度O(|V|+|E|)

#### 基本操作  
* Adjacent(G,x,y)：判断图G是否存在边或(x, y)。
* Neighbors(G,x)：列出图G中与结点x邻接的边。
* InsertVertex(G,x)：在图G中插入顶点x。
* DeleteVertex(G,x)：从图G中删除顶点x。
* AddEdge(G,x,y)：若无向边(x, y)或有向边不存在，则向图G中添加该边。
* RemoveEdge(G,x,y)：若无向边(x, y)或有向边存在，则从图G中删除该边。
* FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点 或图中不存在x，则返回-1。
* NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一 个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
* Get_edge_value(G,x,y)：获取图G中边(x, y)或对应的权值。
* Set_edge_value(G,x,y,v)：设置图G中边(x, y)或对应的权值为v。



## 第四章 排序算法  

**比较类排序**：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(nlogn)$，因此也称为非线性时间比较类排序。
**非比较类排序**：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

排序算法可以分为**内部排序**和**外部排序**，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张表格概括：  

| 排序算法 | 平均时间复杂度      | 最好情况           | 最坏情况          | 空间复杂度       | 排序方式        | 稳定性  |
|------|--------------|----------------|---------------|-------------|-------------|------|
| 冒泡排序 | $O(n^2)$     | $O(n)$         | $O(n^2)$      | $O(1)$      | In-place    | 稳定   |
| 快速排序 | $O(n log n)$ | $O(n log n)$   | $O(n^2)$      | $O(log n)$  | In-place    | 不稳定  |
| 插入排序 | $O(n^2)$     | $O(n)$         | $O(n^2)$      | $O(1)$      | In- place   | 稳定   |
| 希尔排序 | $O(n log n)$ | $O(n log^2 n)$ | $O(n log^2n)$ | $O(1)$      | In- place   | 不稳定  |
| 选择排序 | $O(n^2)$     | $O(n^2)$       | $O(n^2)$      | $O(1)$      | In-place    | 不稳定  |
| 堆排序  | $O(n log n)$ | $O(nlogn)$     | $O(nlogn)$    | $O(1)$      | In-place    | 不稳定  |
| 归并排序 | $O(n log n)$ | $O(nlogn)$     | $O(nlogn)$    | $O(n)$      | In-Out-place   | 稳定   |
| 计数排序 | $O(n + k)$   | $O(n + k)$     | $O(n + k)$    | $O(k)$      | Out-place   | 稳定   |
| 桶排序  | $O(n + k)$   | $O(n + k)$     | $O(n^2)$      | $O(n + k)$  | Out- -place | 稳定   |
| 基数排序 | $O(nk)$      | $O(nk)$        | $O(nk)$       | $O(n + k)$  | Out-place   | 稳定   |

### Ⅰ、比较类排序算法

#### 交换排序算法
##### 冒泡排序(Bubble Sort)
![bubble_sort](img/bubble_sort.gif "bubble sort")
[代码示例](./Sort/bubble_sort.h)  

算法思想  
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

算法步骤  
1. 比较相邻的元素。如果第一个元素比第二个元素大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

> 注：原始的冒泡是从后往前的

##### 快速排序(Quick Sort)
![quick_sort](img/quick_sort.gif "quick sort")
[代码示例](./Sort/quick_sort.h)

算法思想  
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

算法步骤  
1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

#### 插入排序算法
##### 简单插入排序(Insertion Sort)
![insertion_sort](img/insertion_sort.gif "insertion sort")
[代码示例](./Sort/insertion_sort.h)

算法思想  
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。就像我们斗地主时，抽牌阶段会把抽到的牌插入到相应的位置中去，使手上的牌有序。  
插入排序有个小优化叫做折半插入，就是往前寻找插入位置时，因为前面的数组全部有序，因此我们用二分查找法来寻找插入位置。

算法步骤  
1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面，保持相应顺序不变，插入排序是一个稳定的排序算法。）

##### 希尔排序(Shell Sort)
![shell_sort](img/shell_sort.gif "shell sort")
[代码示例](./Sort/shell_sort.h)

算法思想  
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。  
希尔排序是基于插入排序的以下两点性质而提出改进方法的：  
* 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率  
* 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位  

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

算法步骤  
1. 选择一个增量序列$t_1，t_2，…，t_k$，其中$t_i > t_j$,$t_k = 1$；
2. 按增量序列个数 $k$，对序列进行 $k$ 趟排序；
3. 每趟排序，根据对应的增量$t_i$将待排序列分割成若干长度为 $m$ 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

#### 选择排序算法
##### 简单选择排序(Selection Sort)
![selection_sort](img/selection_sort.gif "selection sort")
[代码示例](./Sort/selection_sort.h)

算法思想
选择排序是一种简单直观的排序算法，无论什么数据进去都是 $O(n^2)$ 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤
1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

##### 堆排序(Heap Sort)
![heap_sort](img/heap_sort.gif "heap sort")
[代码示例](./Sort/heap_sort.h)

算法思想  
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法，堆排序的本质是建立在堆上的选择排序。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：  
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列  
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列  

堆排序的平均时间复杂度为 Ο(nlogn)，利用堆的特性，其实我们可以很方便的得到一个未排序数组中的Top K元素。 

算法步骤 
1. 首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；
2. 之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；
3. 以此类推，在第 n-1 次操作后，整个数组就完成了排序。
#### 归并排序(Merge Sort)
![merge_sort](img/merge_sort.gif "merge sort")
[代码示例](./Sort/merge_sort.h)

算法思想  
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。  
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；  
自下而上的迭代（双指针的思想）；  

算法步骤  
二路归并排序：  
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；  
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；  
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；  
4. 重复步骤 3 直到某一指针达到序列尾；  
5. 将另一序列剩下的所有元素直接复制到合并序列尾。  

### Ⅱ、非比较类排序算法
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

计数排序：每个桶只存储单一键值；  
桶排序：每个桶存储一定范围的数值；  
基数排序：根据键值的每位数字来分配桶；  
#### 计数排序(Counting Sort)
![counting_sort](img/counting_sort.gif "counting sort")
[代码示例](./Sort/counting_sort.h)

算法思想  
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 $O(n + k)$。计数排序不是比较排序，排序的速度快于任何比较排序算法。  
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。  
通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。  

算法步骤  
1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第 i 项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素 i 放在新数组的第C(i)项，每放一个元素就将C(i)减去1

#### 桶排序(Bucket Sort)
![bucket_sort](img/bucket_sort.gif "bucket sort")
[代码示例](./Sort/bucket_sort.h)

算法思想  
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：  

在额外空间充足的情况下，尽量增大桶的数量  
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中  
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。  

1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢
当输入的数据被分配到了同一个桶中。

算法步骤  
1. 设置一个定量的数组当作空桶；
2. 遍历序列，并将元素一个个放到对应的桶中；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把元素再放回原来的序列中。

#### 基数排序(Radix Sort)
![radix_sort](img/radix_sort.gif "radix sort")
[代码示例](./Sort/radix_sort.h)

算法思想  
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，基数排序将待排序的元素拆分为 k 个关键字，所以基数排序也不是只能使用于整数。 

如果对自然数进行比较，将自然数按个位对齐后往高位补齐 0，则一个数字从左往右数第 i 位数就可以作为第 i 关键字；  
如果对字符串基于字典序进行比较，一个字符串从左往右数第 i 个字符就可以作为第 i 关键字；  

如果是从第 1 关键字到第 k 关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first）基数排序；  
如果是从第 k 关键字到第 1 关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first）基数排序。


## 第五章 查找算法  

查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

1. 查找表（Search Table）：由同一类型的数据元素构成的集合
2. 关键字（Key）：数据元素中某个数据项的值，又称为键值
3. 主键（Primary Key）：可唯一的标识某个数据元素或记录的关键字

查找表按照操作方式可分为：

1. **静态查找表（Static Search Table）：** 只做查找操作的查找表。它的主要操作是：
2. **动态查找表（Dynamic Search Table）：** 在查找中同时进行插入或删除等操作：

**平均查找长度（Average Search Length，ASL）：** 在所有的查找过程中进行关键字的比较次数的平均值。
对于含有n个数据元素的查找表，查找成功的平均查找长度计算公式如下：
$$ASL = \sum_{i=1}^{n}P_{i}C_{i}$$
$P_iP$​：查找表中第i个数据元素的概率,一般等概率为$\frac{1}{n}$ 
​$​C_i$​：找到第i个数据元素时已经比较过的次数。


#### 顺序查找(Sequential Search)
顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。时间复杂度$O(n)$。

基本思路

从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。

优缺点

缺点：当n 很大时，平均查找长度较大，效率低；
优点：对表中数据元素的存储没有要求。另外，对于**线性链表**，只能进行顺序查找。


#### 二分查找(Binary Search)
[代码示例](./Search/binary_search.cpp)

二分查找（Binary Search），也称折半查找，是一种在**有序数组**中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。  
这种查找算法每一次比较都使查找范围缩小一半。时间复杂度为$O(log_2^n)$。

基本思路
给予一个包含 $n$个带值元素的数组A
1、 令$L$为$0$， $R$为$n-1$；
2、 如果$L>R$，则搜索以失败告终 ；
3、 令$m$(中间值元素)为$(L+R)/2$(**向下取整**)；
4、 如果$A_m<T$, 令$L$为$m + 1$并回到步骤二；
5、 如果$​A_m>T$​，令$R$为$m - 1$并回到步骤二；

**注意**：
**折半查找的前提条件是需要有序表顺序存储**，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

#### 插值查找()


#### 分块查找(Block Search)