《趣学算法》学习打卡Day6

附录A 特征方程和通项公式

? 了解这个知识点，那么你需要回顾一下斐波那契数列，推导有点麻烦，涉及数学公式的输入，skip这个点啦！

附录B sort函数

? 头文件：include< algorithm>

? 语法描述为：

sort(begin,end)//参数begin，end表示一个范围，分别为待排序数组的首地址和尾地址。
    sort(a,a+10);

sort()函数默认为升序！

如何使sort函数排序结果成倒序？

1. 自己编写compare函数

   bool compare(int a,intb)
   {
   return ab,则为降序
   }
   

   sort(begin,end,compare)
   //compare表示比较的类型
   sort(a,a+10,compare);
   

2. 利用functional标准库

   # include 
   

   fonctional提供了如下的基于模板的比较函数对象

   • equal_to< Type>；等于
   • not_equal_to< Type>；不等于
   • greater< Type>；大于
   • greater_equal< Type>；大于等于
   • less< Type>；小于
   • less_equal< Type>；小于等于

   sort(a,a+10,greater);//从大到小排序
   

附录C 优先队列

相对于普通队列先进先出的数据结构而言，只能在队尾添加，队头删除来说，在优先队列中，元素被赋予优先级，当访问元素时，具有最高优先级的元素最先删除。

优先队列：允许队列的元素按照某种次序输出（升序，降序），而不是先进先出啦！

现在学的知识点还没有涉及到，但是我真的想不出这玩意有jier用！

操作：

• 查找
• 插入一个新元素
• 删除

函数

• empty()；队列为空，则返回真。
• pop()；删除第一个元素
• push()；加入一个元素
• size()；返回队列中拥有的元素
• top()；返回最高优先级元素的个数

priority_queue,cmp>,cmp>que;
//第一个参数为数据类型
//第二个参数为容器类型
//第三个参数为比较函数

priority_queue que;
//参数为数据类型，默认优先级（最大值优先）构造队列

如何控制优先队列的优先级？

1. 使用c++自带的库函数< functional>。
2. 自定义优先级a
3. 自定义优先级b
4. 自定义优先级c

附录D 邻接表

? 邻接表是图（有序图）的一种主要存储结构，用来描述图上的每一个点。对图的每一个顶点建立起一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点v_i的所有邻接顶点。

如图：

生成邻接表相关步骤：

输入部分：

• 用户输入顶点个数和边数
• 用户输入每条边的顶点u，v和边的权值w

代码部分：

1. 数据结构

   头结点表、结点表。

   //头结点
   struct Hnode
   {
       Node *first；
   }
   //表结点
   struct Node{
       int v;
       int w;
       Node *next;
   }
   

   如图：

2. 创建邻接表

3. 输出邻接表

附录E 并查集

附录F 四边不等式

附录G 排列数

附录H 贝尔曼规则

附录I 增广路中称为关键边的次数

附录J 最大流最小割定理

总结：

嗯哼，今天捣鼓服务器去了，没有注意到学这个了！