# 数据结构

**Repository Path**: KaiFeng10086/algorithm

## Basic Information

- **Project Name**: 数据结构
- **Description**: 记录算法的学习过程，以C++为主
- **Primary Language**: C++
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-08-25
- **Last Updated**: 2024-08-31

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构

#### 介绍
记录算法的学习过程，以C++为主

# Python

## 1.基础

**Python的`int`类型**: Python 中的 `int` 类型是任意精度的整数类型，不存在位数限制









# C++

时间：10^8

## 1.基础

- ### 质因子

```c++
for (int j = 2; j < n/j ; j++)
```

 `n/i`（`i <= sqrt(n)`）

- ### 输入输出

在C++中，是没有格式符的，我们可以通过使用==setprecision()==函数来实现这个需求

想要使用 setprecision() 函数，必须包含头文件#include <iomanip>，使用方式如下

```c++
cout << "a=" << setprecision(2) << a <<endl;
```


如果 a 的值为 0.20001，输出的结果为 a = 0.2，后面第二位的 0 被省略

如果想要自动补0，需要在cout之前进行补0的定义，代码如下

```c++
cout.setf(ios::fixed);
cout << "a=" <<fixed<< setprecision(2) << a <<endl; //输出a=0.20
```

也可以在输出前对 cout 进行设置，代码如下

```c++
cout.setf(ios::fixed);
cout.precision(3);
cout << a << endl;
```



## 2.#include<cmath>

```c++
pow(j, cnt)
```

```c++
sin() 
cos()
```



## 3.前缀和

![image-20240824144656623](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240824144656623.png)

```c++
double kk[100005];
double ee[100005];

    int n, m;
    cin >> n >> m;
    int op;
    double k; 
    kk[0] = 1;
    ee[0] = 0;
    for (int i = 1; i <= n; i ++ ){
        scanf("%d %lf",&op, &k);
        if(op == 1){
            kk[i] = kk[i - 1] * k;
            ee[i] = ee[i - 1];
        }
        else{
            kk[i] = kk[i - 1];
            ee[i] = ee[i - 1] + k;
        }
    }
    int ii, jj;
    double xx, yy;
    for (int i = 0; i < m; i ++){
        cin >> ii >> jj >> xx >> yy;
        double tempx = xx * (kk[jj]/kk[ii - 1]); 
        double tempy = yy * (kk[jj]/kk[ii - 1]);

        xx = tempx * cos(ee[jj] - ee[ii - 1]) - tempy * sin(ee[jj]- ee[ii - 1]);
        yy = tempx * sin(ee[jj] - ee[ii - 1]) + tempy * cos(ee[jj]- ee[ii - 1]);

        printf("%lf %lf\n", xx, yy);
    }

```

> 注意：
>
> `kk[jj]/kk[ii - 1]`
>
> `ee[jj]- ee[ii - 1]`



## 4.vector

- ### vector定义二维数组， resize方法

```c++
vector<vector<int> > ls;
ls.resize(n + 1);
for (int i = 0; i < n; i ++ ){
    ls[i] = vector<int>();
}
```

- ### vector初始化

```c++
vector<vector<int>> arr(m, vector<int>(n)); //动态开辟m*n的二维数组，并初始化为0
vector<vector<int>> arr(m, vector<int>(n, 1)); //动态开辟m*n的二维数组，并初始化为0

vector<vector<int>> arr;
arr.resize(m, vector<int>(n)); //采用resize进行初始化
```







## 5.\#include <iomanip>

- fixed << setprecision(3)

```C++
cout << fixed << setprecision(3) << (x * cos(sum_xita) - y * sin(sum_xita)) * pro_k << " "<< (x * sin(sum_xita) + y * cos(sum_xita)) * pro_k << endl;
```













# 习题



## 第五章 数组、 广义表

### 5.1

![image-20240610203316954](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240610203316954.png)

(1) 6×8×6=288 Byte

(2) LOC(5,7)=1000+(5×8+7)×6=1282

(3) LOC(1,4)=1000+(1×8+4)×6=1072

(4) LOC(4,7)=1000+(7×6+4)×6=1276

### 5.2

![image-20240610203343112](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240610203343112.png)

![image-20240610203525402](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240610203525402.png)







# 数据结构

成绩构成

- 作业5， 上课5， 实验20， 考试70

## 时间复杂度

![image-20240412174542259](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240412174542259.png)

## A*算法

![image-20240409115436125](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240409115436125.png)

## 递归&递推





# 树

树的深度（高度）、 结点的**层次**

<img src="C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240423144242092.png" alt="image-20240423144242092" style="zoom:50%;" />

## 二叉树

### 小根堆



### 大根堆



### 线索二叉树

![image-20240611135259691](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240611135259691.png)

![image-20240611140837101](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240611140837101.png)





## 完全二叉树





## 满二叉树





## 二叉排序树





## 平衡二叉树



# 图

完全图、有向完全图：
![image-20240521133551428](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240521133551428.png)

稠密图、稀疏图

![image-20240521133607270](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240521133607270.png)

## 存储

邻接表

邻接矩阵



稀疏图

稠密图



关节点   --  

## 拓扑排序：

![image-20240507144349706](C:\Users\86137\AppData\Roaming\Typora\typora-user-images\image-20240507144349706.png)

## 关键路径：



关键活动

最早发生时间：ve

最迟发生时间： vl







# other

## 并查集



## 逆序对

下标小--对应数也小

下标大 -- 对应数小 -- 逆序对  -- 归并排序