不想动手调程序的可以试试这个任意大小屏幕录制成gif图的软件。





![在这里插入图片描述](/static/img/images/02790.png)


MATLAB 用很多图片 生成gif动图

1、生成很多图

我这里画了cos曲线和一个圆， (x0,y0)是切点，x0取值t = linspace(0.1,0.9,10); 

 (xc,yc)是圆心。计算好之后，使用plot(xxxx1,y1,'r',xxxx2,y2,'b');%画出函数1和函数2的图形，然后saveas(gcf, num2str(count_num_single), 'jpg');保存这张图，图名生成的。x0有10个点，循环10次，这样就能得到10张图。

 
```
clc
clear all
pi=3.1415926;
%目的就是根据切点画图
t = linspace(0.1,0.9,10);  % 手定
count_num_single=1;
w=1; % 改变胖瘦
for x0=t
    y0 = cos(w*x0+pi) ; % (x0,y0)是切点 根据函数公式和已经的x0得到y0
    y0i=(-w) * sin(w*x0+pi);%导数
    yc = -2.8;  % (xc,yc)是圆心  最后要满足条件 -yc<R 才能让圆的最高点在第四象限
    syms xc R    % R是圆半径  xc是圆心的横坐标
    % enqs变量就是2个方程式 就是联立1和2的式子
    eqns = [(x0 - xc)^2 + (y0 - yc)^2 - R^2==0, (y0 - yc) / (x0 - xc) * y0i + 1==0];
    vars = [xc R];
    [xc, R] = solve(eqns, vars);
    xc=vpa(xc,4);
    R=vpa(R,4);
    xc=double(xc);
    R=double(R);
    xc=max(xc);
    R=max(R);
    %下面几句是画图形
    xxxx1=linspace(-pi,2*pi,2000);%给出范围
    xxxx2=linspace(xc-R,xc+R,2000);%给出范围
    y1=cos(w*xxxx1+pi);%范围内的函数1
    y2=sqrt(R^2-(xxxx2 - xc).^2)+yc;%范围内的函数2
    plot(xxxx1,y1,'r',xxxx2,y2,'b');%画出函数1和函数2
    grid on;
    axis equal;
    saveas(gcf, num2str(count_num_single), 'jpg');
    count_num_single=count_num_single+1;
end
```


2、生成gif图

刚才生成的图，读出来，写入到gif图，最终成动图。
```
num=count_num_single-1;
for i=1:num
    str = strcat(num2str(i), '.jpg');
    A=imread(str);
    [I,map]=rgb2ind(A,256);
    if(i==1)
        imwrite(I,map,'movefig.gif','DelayTime',0.1,'LoopCount',Inf)
    else
        imwrite(I,map,'movefig.gif','WriteMode','append','DelayTime',0.1)
    end
end
```

效果图：

![在这里插入图片描述](/static/img/images/02791.gif)

MATLAB 用很多图片 生成gif动图

![在这里插入图片描述](/static/img/images/00424.png)






```csharp
from typing import List
class Solution:
    def dfs(self, grid, cur_i, cur_j) -> int:
        # 超出边界 or 不是陆地  程序靠此结束
        if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
            return 0
        grid[cur_i][cur_j] = 0  # 访问过的设置为0,全局的
        ans = 1  # 访问过的陆地，1块
        for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: # 四个方向
            next_i, next_j = cur_i + di, cur_j + dj
            ans += self.dfs(grid, next_i, next_j) # 这个位置dfs
        return ans
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i, l in enumerate(grid):
            for j, n in enumerate(l): # i,j 遍历每一个位置,在每个位置dfs搜索最大面积
                ans = max(self.dfs(grid, i, j), ans)
        return ans
s=Solution()
print(s.maxAreaOfIsland([[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]))
```

岛屿的最大面积 数据结构与算法 DFS搜索

[https://blog.csdn.net/darkrabbit/article/details/89409548](https://blog.csdn.net/darkrabbit/article/details/89409548)






（1） 出栈序列共有多少种可能？

（2） 求出所有出栈（入栈）序列。

（3） 给出一个出栈序列，问栈的容量最少需要多少？

（4） 给出一个（或多个）出栈序列，问此序列是不是（哪一个序列不是）原序列混洗得到的？


![在这里插入图片描述](/static/img/images/00970.png)

python

题目描述

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。

要求输出所有火车出站的方案，以字典序排序输出。
```python
while True:
    try:
        n = int(input())
        trains = [  str(1+i)  for i in range(n)]
        res = []
        def rec_trains(cur_idx, in_trains, out_trains):
            # 如果原始火车列表的最后一个元素已经进站，此时只能出站，将入站列表中的火车倒序加入出站火车中
            if trains[-1] in in_trains:
                res.append(' '.join(out_trains + in_trains[::-1]))
                return
            # 如果进站列表为空，此时只能进站，进站列表加上当前火车，出站列表不变
            elif in_trains == []:
                rec_trains(cur_idx + 1, in_trains + [trains[cur_idx]], out_trains)
            # 否则，就既有可能进站也有可能出站
            else:
                # 出站，当前火车索引不变，进站火车列表减去最后一个元素，出站列表加上进站列表刚刚出站的火车
                rec_trains(cur_idx, in_trains[:-1], out_trains + [in_trains[-1]])
                # 进站，当前火车索引加1，进站列表加上当前火车，出站列表不变
                rec_trains(cur_idx + 1, in_trains + [trains[cur_idx]], out_trains)
        rec_trains(0, [], [])
        res.sort()
        print(len(res))
    except:
        break
```

数据结构 栈混洗 个数 Stack Shuffling 卡特兰数

![在这里插入图片描述](/static/img/images/01120.png)





前序[0, 1, 3, 4, 2]

```python
# Definition for a binary tree node.
from typing import List
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return res
root = TreeNode(0)
lc = TreeNode(1)
rc = TreeNode(2)
lc_lc = TreeNode(3)
lc_rc = TreeNode(4)
root.left = lc
root.right = rc
lc.left=lc_lc
lc.right=lc_rc
print(Solution().inorderTraversal(root))
```

中序  [3, 1, 4, 0, 2]

```python
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
```

后序  [3, 4, 1, 2, 0]

```python
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)
```

数据结构 python3 二叉树遍历 前序 中序 后序

[https://mp.weixin.qq.com/s?__biz=MzU0ODMyNDk0Mw==&mid=2247487910&idx=1&sn=2670aec7139c6b98e83ff66114ac1cf7&chksm=fb418286cc360b90741ed54fecd62fd45571b2caba3e41473a7ea0934f918d4b31537689c664&token=1327182919&lang=zh_CN#rd](https://mp.weixin.qq.com/s?__biz=MzU0ODMyNDk0Mw==&mid=2247487910&idx=1&sn=2670aec7139c6b98e83ff66114ac1cf7&chksm=fb418286cc360b90741ed54fecd62fd45571b2caba3e41473a7ea0934f918d4b31537689c664&token=1327182919&lang=zh_CN#rd)






递归函数模板：

```c
public void recursion(参数0) {
    if (终止条件) {
        return;
    }
    可能有一些逻辑运算
    recursion(参数1)
    可能有一些逻辑运算
    recursion(参数2)
            ……
    recursion(参数n)
    可能有一些逻辑运算
}
```

递归模板

十大排序算法 python

[深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜](http://data.biancheng.net/view/39.html)





# 1 图的基本概念

图的几个应用场合：

（1）一张带权图，代表城市之间的距离。求一个城市到另一个城市的最短路径。或者说导航上用的。Dijkstra 算法。

（2）图最小生成树。城市光纤网建造，最小生成树代表了耗材最少的方法。

（3）网页排序。一个网页就是图的一个顶点，权重如何升高。

图 是一种非常重要的数据结构。树 就是一种特殊的退化的图结构。

图的生成树（也叫支撑树）通常不是唯一的。边有权重，图就是带权网络。同一网络的声称树中，总权重最小者为最小支撑树。

# 2 邻接矩阵

![在这里插入图片描述](/static/img/images/01361.png)

![在这里插入图片描述](/static/img/images/01362.png)

# 3 邻接矩阵优缺点

![在这里插入图片描述](/static/img/images/01363.png)

![在这里插入图片描述](/static/img/images/01364.png)

# 4 邻接表

![在这里插入图片描述](/static/img/images/01365.png)

![在这里插入图片描述](/static/img/images/01366.png)

# 5 广度优先搜索

![在这里插入图片描述](/static/img/images/01367.png)

![在这里插入图片描述](/static/img/images/01368.png)

# 6 深度优先搜索

![在这里插入图片描述](/static/img/images/01369.png)

# 7 遍历算法的应用

![在这里插入图片描述](/static/img/images/01370.png)

数据结构 图 图的表示 图的搜索 深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）

# 0 从“树”到“搜索树”





前面所说的都是线性表，基于数组实现或者基于链表实现都有优缺点，数组做查找元素快，链表做插入删除元素快。

树是半线性结构（semi-linear structure），结合了二者特点。

本书约定，仅含单个节点的树高度为0，空树高度为-1。

特别地，约定根节点的深度depth(r) = 0，故属于第0层。

特别地，不含一度节点的二叉树称作真二叉树（proper binary tree）。

有序多叉树 = 二叉树 ，在全遍历中就能看出能相互转化。

二叉树表达能力和多叉数一样的，而且得益于其定义的简洁性以及结构的规范性，所以都用二叉树。

树是怎么做到高效率的动态修改和高效率的静态查找？答案是用一些搜索树和高级搜索树。

![在这里插入图片描述](/static/img/images/01380.png)


# 1 二叉搜索树（binary search tree）

二叉搜索树的实现与分析，search()、insert()和remove()等主要接口的运行时间，均线性正比于二叉搜索树的高度。

将二分搜索树与常规二叉树分开的属性是

 - 左子树的所有节点均小于根节点 

 - 右子树的所有节点均大于根节点 

 - 每个节点的两个子树也是BST，即它们具有以上两个属性

查找、插入和删除操作 操作：

查找：从根节点出发，比较左孩子和右孩子，从而判断进入左子树递归还是进入右子数递归。（分而治之）

![在这里插入图片描述](/static/img/images/01381.png)

插入：利用查找返回大于数值一点的节点。然后把数值作为左孩子，最后更新祖先高度。

![在这里插入图片描述](/static/img/images/01382.png)

删除：利用查找找到位置后，单分支和双分支处理不一样。

![在这里插入图片描述](/static/img/images/01383.png)

# 2 平衡搜索树-AVL树

通过合理设定适度平衡的标准，并借助以上等价变换，AVL树（AVL tree）可以实现近乎理想的平衡。在渐进意义下，AVL树可始终将其高度控制在O(logn)以内，从而保证每次查找、插入或删除操作，均可在O(logn)的时间内完成。

任一节点v的平衡因子（balance factor）定义为“其左、右子树的高度差”，即balFac(v) = height(lc(v)) - height(rc(v))

插入或者删除会造成树不平衡，此时通过一些旋转操作让树重新平衡，满足AVL特点。

# 3 伸展树splay tree

[\[一个很好的介绍伸展树的博客点我\]](https://blog.csdn.net/u014634338/article/details/49586689)

伸展树也是一种平衡搜索树。

我们评估算法结构用的随机的最坏的，但实际应用场合有一定规律，如果我们适应这种规律设计算法结构，可以使得数据结构这个应用中得到更高效率。伸展树就是这么想的。

![在这里插入图片描述](/static/img/images/01384.png)

![在这里插入图片描述](/static/img/images/01385.png)

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，`被查频率高的那些条目就应当经常处于靠近树根的位置`。于是想到设计一个简单方法，`在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。`伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。它的优势在于不需要记录用于平衡树的冗余信息。

![在这里插入图片描述](/static/img/images/01386.png)



# 4 B树 

B树

B-树结构非常适宜于在相对更小的内存中，实现对大规模数据的高效操作。

所谓m阶B-树（B-tree），即m路平衡搜索树（m >= 2），其宏观结构如图8.11所示。

![在这里插入图片描述](/static/img/images/01387.png)

> 下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：

> 

> 1.根结点至少有两个子女。

> 

> 2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

> 

> 3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

> 

> 4.所有的叶子结点都位于同一层。

> 

> 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

[\[读一下这里介绍B数和B+数的，生动形象。点我\]](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653190965&idx=1&sn=53f78fa037386f85531832cd5322d2a0&chksm=8c9909efbbee80f90512f0c36356c31cc74c388c46388dc2317d43c8f8597298f233ca9c29e9&scene=21#wechat_redirect)

数据库存储或者磁盘存储，读取数据还需要考虑到I/O时间，一次读取1一个数据和10个数据所花费的时间相当，但使用10次读取每次读取1个数据却是很耗时间，所以考虑使用m路平衡搜索树。

B树 查找、插入、删除操作。B树主要用于文件系统以及部分数据库索引（比如非关系型数据库MongoDB）。

大部分关系型数据库使用B+树作为索引。

# 5    B+树

大神的漫画比看书快，多看几遍后再去看书。

[还是看这里，点我](https://www.cxyxiaowu.com/3726.html)

# 6    红黑树

> 平衡二叉搜索树的形式多样，且各具特色。比如，8.1节的伸展树实现简便、无需修改节点

> 结构、分摊复杂度低，但可惜最坏情况下的单次操作需要(n)时间，故难以适用于核电站、医

> 院等对可靠性和稳定性要求极高的场合。反之，7.4节的AVL树尽管可以保证最坏情况下的单次

> 操作速度，但需在节点中嵌入平衡因子等标识；更重要的是，删除操作之后的重平衡可能需做多

> 达(logn)次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。

> 红黑树即是针对后一不足的改进。通过为节点指定颜色，并巧妙地动态调整，红黑树可保证：

> 在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个节点。尽管最坏

> 情况下需对多达(logn)个节点重染色，但就分摊意义而言仅为O(1)个（习题[8-14]）。

> 当然，为此首先需在AVL树“适度平衡”标准的基础上，进一步放宽条件。实际上，红黑树 所采用的“适度平衡”标准，可大致表述为：

> 任一节点左、右子树的高度，相差不得超过两倍。

大神的漫画比看书快，多看几遍后再去看书。

[还是看这里，点我](https://www.cxyxiaowu.com/7374.html)

数据结构 树 树的表示（存储） 搜索树（用于高效查找）

C语言 链表 栈与队列 二叉树遍历

![在这里插入图片描述](/static/img/images/01392.png)





`1 栈的注意点`

先进后出。

递归的时候就会用到栈，把这次结果压入栈，去计算下一次的。

题外话：算法中避免用递归。不断压入栈有时会导致过多占用内存，

`2 栈的典型应用`

可线性描述、逆序输出、大小规模不确定。

递归嵌套：具有自相似性的问题多可嵌套地递归描述。

栈混洗（stack permutation）、括号匹配、

![在这里插入图片描述](/static/img/images/01393.png)

逆波兰表达式



`3  试探回溯法  高效地实现试探回溯策略`

n皇后问题

迷宫路径问题




`4 栈与队列`

都是一种数据结构，应用场合不定，作用广泛。