其实主要是记一些名词

栈

没什么好说的.用数组模拟即可

应用

• 括号配对, 自己写了一下, 不难, 但好久不做题, 手有点生
• 进行四则运算, 待写
• DFS, 实际拿函数递归来实现

队列

和栈差不多…但是有一些细节. 就是为了有效利用空间, 要使用循环队列…队尾放满了要折回去放到头, 所以有个取膜的操作

数据成员

nptr front  // 头指针
nptr rear   // 尾指针
element data[maxlen]

操作

入队

rear = (rear + 1) % maxlen
data[rear] = ele;

出队

front = (front + 1) % maxlen

循环队列里存在的问题

循环队列解决了空间利用不是很有效的问题, 但是与此同时, 带来了新的问题…
就是队列空和队列满没办法区分
因为判断条件都是front == rear

解决方法:

• 增设操作标志, 当首尾指针相等时
  如果进行了入队操作, 那么队列满
  如果进行了出队操作, 那么队列空

• 约定一个保留空间
  即空出来一个空间, 最多存放maxlen - 1个…, 这样子的话

应用

杨辉三角
BFS

链表

实现方式

• 静态链表, 数组实现
• 动态链表, 指针实现

应用

• 链栈
  没什么好说的

• 链队列
  增设头结点, 头尾指针都有方便操作
  从头指针的地方出队, 从尾指针的地方入队
  在出队时候要注意的点在于…当只剩下一个头结点的时候, 要把尾指针也置为front, 因为这个时候, rear本来是指向最后一个节点的, 但我们把最后一个节点删掉了,,,所以要rear指向开头

操作(待写)

把链表就地逆置
链表合并(保持大小关系)

线性表

存储方式

• 顺序存储结构
• 链式存储结构
  按照这样子的话, 栈, 队列, 线性表都有 顺序和链式的两种存储结构

  推广

  广义表: 每个元素可以是一个不可分割的原子, 也可能是一个表
  这个..广义表有两种操作
  head(A) 取表头：返回表A中第一个元素的值。
  tail(A) 取表尾：返回表A中删除第一个元素后所得的表。
  广义表的存储有几种方式:
• 链式存储结构
• 树/图表示

树

相关概念

• 节点的度: 某节点的直接子节点的个数
• 树的度: 树中最大节点度
• 树的深度: 就是树中最深节点的高度

一个疑问就是. 深度和高度… 有的人说, 高度和深度一个是从下往上数的, 另一个则相反. 这个我也还不太知道

二叉树 & 树

ppt里说, 二叉树, 节点左右不同就算两种状态, 而树的话就不是这样子了
左子树 & 右子树这些都是,,,二叉树里的概念

一个公式

节点总数 = \sum(n_i * i) + 1…. 就是度数乘上拥有该度数的节点个数最后再加个1
这个主题好像没有Mathjax, 不能写latex公式就好坑啊

二叉树

单独拿出来, 看一下

性质

这里是把根节点作为第1层

• 第i层的节点数 <= 2 ^ (i - 1)
• 高度为k的二叉树的节点总数 <= 2^k - 1
• 度为0, 1, 2的节点数量分别记为n0, n1, n2, 那么有n0 = n2 + 1
  推倒是: n0 + n1 + n2 = n1 + 2*n2 + 1 = 节点总数

所以对于二叉树的话,由于是n0 = n2 + 1, 所以只是需要有n0, n1, 或者n2, n1就能求出节点总数了

满二叉树

高度为k, 并且有2^k - 1个节点的二叉树叫满二叉树

完全二叉树

在满二叉树中, 只有最后一层, 从右到左连续去掉了若干节点的二叉树
介绍一个概念, 肯定要有利用价值…对吧, 那完全二叉树的优势在于:
如果把根节点编号为1号, 那么树中某一节点编号i的两个子节点编号就是2i和2i + 1

需要注意的点, 就是根节点编号一定要是1, 不能是0…

关于完全二叉树的两个结论

• 有n个节点的完全二叉树的高度为[logn] + 1, 按照国际惯例, 是以2为底, 并且这里的取整函数是向下取整,比如, 2.多也是取2
• 如果孩子i有父亲, 那么孩子i的父亲编号应该是: [i/2], 这里也是向下取整, 就是i >> 2, 对吧
• 度为1的节点最多有一个, 或者没有

由于节点编号的特殊性, 所以完全二叉树可以使用数组来存…多么开心的一件事情

几个题目

1. 求100个节点的完全二叉树的叶子节点数
   开始选用了, 很麻烦的做法, 算出了最后一层多少个叶子, 倒数第二层多少个, 然后加起来是总共50个…
   好的解法应该是: 根据100号节点, 算出他的父亲是50号…所以, emmmm, 从51~100号都是叶子, 所以是50个…

2. 完全二叉树第七层有10个节点…问共有多少节点, 有多少是叶子呢?
   前6层有63个…对吧, 所以共有73个
   然后最后一个节点编号是73了, 所以他爸爸是36号, 所以从37 ~ 73都是叶子, 共有37个

3. 编号为i, j的两个节点在同一层的条件是: [log(i)] = [log(j)], 依然是向下取整

4. LCA 最小公共祖先问题
   baby暴力: 最容易想到的方法是, 从根节点分别走到i, j两节点, 并且记录下路径, 然后从头比较, 到第一个分叉的地方之前的那个节点就是最小公共祖先

是不是上面的写法太暴力了…

暴力plus: 可以先dfs一下子…然后记下每个节点的父亲和深度….(其实…这个时候用bfs, dfs都可以是吗), 之后对于俩节点, 深度深的往上跳, 跳到和另一节点同一深度, 这个时候一起跳….当跳到同一点的时候就成功GG了.

暴力plusplus: 就是上面的暴力plus + 倍增, 倍增就是按照2^n这样子跳, 不是一下一下跳

在DFS中, 一个度为n, 的节点一定会被访问(n + 1) 次, 因为会回溯n次

还有离线的tarjan和在线的RMQ, QAQ, 已经都不会写了, 我现在咸鱼一条,可能只会, 那个, 俩点往上一跳一跳的操作….

先不在这里花时间了.

二叉树的遍历

其实, 有个问题是, 我们经常说的先序, 后序, 中序 和 DFS, BFS之间的关系…emmmmmm, 我可能是个傻子
网络上基本上没有人放在一起考虑过
但仔细想了一下…
其实先..中..后这个应该是dfs, 因为其实dfs和递归对应, 我现在认为前中后是给dfs节点打时间戳的不同方法…就比如先序的话就认为是…第一次访问这个节点就打…后续的话…认为dfs过程中….该节点的孩子都遍历完了, 再打…
而且由于..这个先序的特点…好像看起来先序就和我们通常意义上说的dfs是完全一样的了
再仔细想一想…dfs其实是没有规定访问子节点的顺序的, 但可以认为规定先访问左子树还是右子树..所以,其实这个dfs还比先中后要多样…可以认为我们二叉树先中后只是dfs一些…说不出来

恩, 对…前中后就是打个时间戳,你甚至可以每次遍历打两个时间戳, 一个先序, 一个后序…那么某个节点两次时间戳之间的内容就是他的子树..其实拿出代码来一看…很清楚的东西..为什么我这才意识到

void dfs(node *p) {
    // visit(p); 位置1
    dfs(p -> lson);
    // visit(p); 位置2
    dfs(p -> rson);
    // visit(p); 位置3
}
void visit(node * p) {
    print("node %d has been visited\n", p -> index);
}

在这里的dfs里, visit分别在1, 2, 3位置就是前中后序
所以, 以后就可以说是, 中序的dfs…这样子说话

而bfs这种队列实现的搜索方法…好像和这些没有关系

以上仅对二叉树而言….因为多叉树的话还能bfs, dfs, 但其实不存在中序遍历了

就是…
dfs, 栈, 递归 这都是联系在一起的
bfs, 队列是联系在一起的…, 好像bfs也叫层次遍历
所以写dfs, 原理上是用栈…但实际上只要写函数调用(递归)就可以…而不像bfs要我们自己维护一个队列

应用场景

后序的话用在…父节点状态要在孩子节点信息之上推出的场景…其实很常用, 比如求解, 树的高度

int dfs(node * p) {
    if(p != NULL) {
        int lf = dfs(p -> lson);
        int rf = dfs(p -> rson);
        return 1 + max(lf, rf);
    }
    return 0;
}

我很久不写代码了, 也不知道写的对不对

要统计一个累加的量的时候, 感觉好像其实, 前中后就没那么重要了

void dfs(node * p) { 
    if(p != NULL) {
        sum++;
        dfs(p -> lson);
        // sum++放在这里也可以
        dfs(p -> rson);
        // sum++放在这里也可以
    }
}
// 如果用c++的话, 这里的sum可以用应用传进来.写成`void dfs(node *p, int &sum)`
void dfs(node * p, int &sum) { 
    if(p != NULL) {
        sum++;
        dfs(p -> lson, sum);
        // sum++放在这里也可以
        dfs(p -> rson, sum);
        // sum++放在这里也可以
    }
}

这里的sum是一个全局变量
还有一种和那个求树的高度的写法极其类似的写法见下边….几乎就是一毛一样…明显更加简洁. perfect

int dfs(node *p) {
    if(p != NULL) {
        return num(p -> lson) + num(p -> rson) + 1;
    }
    return 0;
}

已知先-中或者后-中, 就可以确定一颗二叉树的结构….

线索二叉树

这里先跳过了

树和森林的存储方式

这里

各种树

哈夫曼树
线段树
字典树
主席树
划分树
…
…
陷入沉思
我想回宿舍了….突然厌烦

图

表示方法: G = <V, E>
V: 定点集合
G: 边集合…又有有方向和没有方向两种
通常有方向的记为<V1, V2>, 没有方向的边记为(V1, V2)

定点的度: 有向图还分为入度和出度

这里有个东西…你看…就是…怎么说…那个.这个.我..就是
在树中, 我们说的度其实指的是某一个节点的出度…(如果把树看做图的话…), 而没有算他的入度, 对不对

一些概念

简单路径: 中间经过节点不重复的路径(不算首尾)
回路 : 首尾相同的路径
简单回路: 简单路径 + 回路

连通图: 无向图中任意两点都存在路径的话, 则称为连通图, 否则就是非联通图

1. 任何连通图的连通分量只有一个, 就是它本身
2. 非连通的无向图有多个连通分量, 这些分量好像都叫..极大连通子图

强连通图: 在有向图G中, 若任意两点都可达(可达意味着正反都存在路径), 那么就称为是强连通

1. 任何强连通图的连通分量只有一个, 就是它本身
2. 非强连通的有向图有多个强连通分量, 这些分量好像都叫..极大连通子图

完全图: 无向的话…是任意两点间都有一条边…有向的话…是相当于任意两定点都一来一回对吧, 所以
n个节点的无向完全图..共有n * (n - 1) / 2条边
n个节点的有向完全图..共有n * (n - 1)条边

树: 连通无回路的无向图, n个节点, (n - 1)条边, 树是有最少边数的连通图

你看…这个树是无向 无环, 而DAG是有向 无环, 是不是有些相似的定义

图的存储方式

1. 邻接矩阵
   无向图的邻接矩阵是三角对称结构
   对于某一顶点, 分别, 横着数, 竖着数, 就能.能!算出入度和出度了
   邻接关系也好确定

2. 邻接表
   比起邻接矩阵, 其实邻接表,在判断是否邻接的时候…比较麻烦…要遍历才能得到..无向图还好, 有向的话…确实有点…
   矩阵相当于是空间换时间了, 方便而且…如果过于稀疏的话, 我们才用邻接表, 就是这样
   有一个折中的办法是:
   用一个邻接表和一个逆邻接的表…这样子的话, 判断入度出度的话就方便一些…

图的遍历算法

1. 深度优先DFS
   DFS用在非连通图或者某些有向图里, 能实现一个效果…就是, 当遍历完所有节点之后(可能调用了多次DFS), 这个时候就能得到各个(强)连通分量, 代码大概如下

   void dfs(graph G) {
    for(int i = 0; i < n; i++) {
        visited[i] = false; // 初始化
    }
    for(int i = 0; i < n; i++) {
        if(!visited[i]) 
            dfs(i);
    }
   }
   

   应用(先mark, 没有具体写)
   求无向图的连通分量: 这个可以DFS一遍, 也可以并查集, 还可以BFS一遍…
   感觉应该是并查集快一些…但难写一些?

求有向图的强连通分量(SCC):

1. Tarjan
2. Kosaraju

3. Gabow
   这三种应该都是DFS, 或者多次DFS

4. 广度优先BFS
   广度优先的话可以说是层次遍历
   应用: 算出最短路径….

最小生成树

权值最小的边一定在最小生成树里
两种算法可解决

1. prim
   基本思想:
   在一端已选，另一端未选的候选边中选出一条最小的边…
   有点绕口, 但思路是很简单的
   如何高效的维护这个侯选边的集合是我们的关键

2. Kruskal
   基本思想:
   选一条最小的边使得其和已经选择的边不构成回路
   关键在于如何判断构成回路

拓扑排序(有向图)

依然是常用的两种算法, 哎, 省赛的时候就在这里搁了…自己脑残把两种算法无缝拼接了一下…然后发现运行不了了…然后和一等说白白了…23333, 回想起来, 都是泪

1. Kahn
   这个名字..其实听得不多….但一说..这个算法的关键,在于维护..那个入度为0的点的集合..每次要做的操作就是把入度为0的点去掉…就可以了
   这个算法还能判断是不是有环…即DAG的判断
   但我隐约记得…Kahn要实现按照字典序来输出拓扑排序结果好像有点问题
   因为..某一节点入度的改变是由于与她相连的的节点的删去而引起的…所以可以只考察, 刚删去的节点的后继节点是不是该加入这个候选集合, 综述, 可以使用栈来实现这个拓扑排序

2. dfs

关键路径

最短路

1. 单源Dijkstar
2. 多源Floyd
   等下写

查找

1. 简单顺序查找: 一个一个找
2. 二分查找 : 需要是有序的…也就是说要选排序, 复杂度带logn
   记得自己然后手写一个二分….虽然STL里好像有…STL啥都有…STL选手
3. 分块 : 块间有序, 块内无序, 分块的大小一般取√n, 这个复杂度带√n
   分块就是块内暴力…的方法..看着很暴力…其实还挺好用的..不太动脑筋而复杂度常常能达到要求

树

1. BST
   就是左子树中所有节点值小于父节点值, 而右子树大于父节点
   所以,按照中序遍历就能得到一个非降序列…
   BST有个问题就是刻意构造的数据可能导致BST退化成链表
   针对这个问题…大家想出了平衡树这个东西

2. 平衡树
   平衡树其实有很多很多种….
   只要满足下面条件的BST都是平衡树:

   1. 左右子树的高度差绝对值不大于1
   2. 左右子树都是平衡树
      所以…这个平衡树这一类树是采用各种方法来防止BST退化的方法的树
      具体地说, 代表之一就是AVL…
      其实朝鲜树, 替罪羊, 还有SBT这些…都算是平衡树,可能不太平衡…就是说可能不满足这里定义说的高度差不超过1, 但是用自己的方法来保证了树的相对平衡

3. AVL

4. B-Tree

Hash表

大概涉及到几个问题

1. 计算ASL
2. 构造散列函数
3. 解决冲突

构造散列函数的方法

1. 直接定址法

   Hash(k) = k, 或者 Hash(k) = a*k+b
   

2. 除留取余
   Hash(k) = k % p, 一般这个p是个质数(prime)

3. 平方取中法
   这是什么玄学…把数字算个平方…然后取出来中间两位算hash

4. 康拓展开
   这个是以前做过的一个八数码问题里遇到的, 用于把全排列进行hash的一种没有冲突的方法

冲突是指出现了:
k1 ~= k2, 但Hash(k1) = Hash(k2) 的情况
处理冲突的方法, 感觉可能会考

1. 开放地址法

2. 拉链法
   把hash值相同的丢到一个vector里…这不就是一个邻接表吗….

3. 再散列法

排序

其实…看了下整个块…排序算是不太熟悉的…因为自己遇到问题, 复杂度不要求的话写个最好写的冒泡, 要求的话写个快排..其他的这些奇奇怪怪的排序都很少手写

几个概念：
稳定排序 : 排序过程中， 关键字相同的元素相对次序不变
不稳定排序: 排序过程中， 不能保证关键字相同的元素相对次序不变
内/外部排序: 外部的话。。。部分数据在内存， 部分在外存

插入排序

思想: 把整个待排序的表看成两部分. 左边是有序的, 右边是无序的…整个过程是把无序区的元素插入到有序区

1. 简单插入排序

   void insert(element_type A[]) {
    for(int i = 1; i <= n; i++) {
        int temp = A[i];
        int j = i - 1;
        while((A[j].key > temp.key) && (j >= 1)) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = temp;
    }
   }
   

   就是一轮下来， 边比较, 边挪位置A[j + 1] = A[j], 的那满足条件的时候…把本次考察的值放到找好的这个空位置上…
   有一个技巧叫设置烧饼 哨兵, 我们把A[0]作为烧饼的话, 就是A[0]一定会满足条件… 那我们上面代码中的边界状态判断j >= 1, 就可以去掉了

   void insert(element_type A[]) {
    for(int i = 1; i <= n; i++) {
        A[0] = A[i];
        int j = i - 1;
        while((A[j].key > A[0].key)) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = A[0];
    }
   }
   

   很明显，这个直接插入排序是稳定的

2. 希尔排序
   分组的简单插入排序
   这个排的我有点迷…不稳定排序， 但复杂度变成了nlogn
   每次相隔d的元素化成一组进行排序….这个d是变步长的..开始的时候 d = n/2, 每次都会有d /= 2…最后一次的d是1…就是所有元素都排
   代码上来讲,,,,和普通插基本一样的感觉

   void shell(elementtype A[]) {
    d = n / 2;
    while(d > 0) {
        for(int i = d + 1; i <= n; i++) {
            int x = A[i];
            j = i - d;
            while((A[j].key > x.key) && (j >= 1)) {
                A[j + d].key = A[j].key;
                j = j - d;
            }
            A[j + d] = x;
        }
        d /= 2;
    }
   }
   

交换类排序

思想: 两两比较交换, 一边比啊一边换

比较插入排序的话, 插入是每次考察一个元素, 和已经有序的区域比较, 直到找到合适的位置放进去

1. 冒泡排序

   void bubble(elementtype A[]) {
    for(int i = 1; i <= n - 1; i++)
        for(int j = n; j >= i+1; j--)
            if(A[j].key < A[j - 1].key)
                swap(A[j], A[j - 1])
   }
   

   冒泡是稳定的..

1. 快排
   快排不稳定…然后写个好看的快排

选择排序

在每一趟排序中, 从待选子表中选出关键字最大或者最小的元素放到最终位置上

1. 直接选择排序

   void select(elementtype A[]) {
    for(int i = 0; i < n - 1; i++) {
        min = i;
        for(int j = i + 1; j < n; j++) {
            if(A[j].key < A[min].key)
                min = j;
        }
        if(min != i)
            swap(A[min], A[i]);
    }
   }
   

   选择排序居然也是不稳定排序, emmmmm

2. 树形选择排序
   看到树,首先想到复杂度肯定是比较小….
   md， 这个操作还挺好看的…言语不是很好描述

3. 堆排序
   这个最难写了，我肯定不会用这个
   堆
   用完全二叉树实现, 父亲(i)的值比儿子(2i, 2i + 1)的值要大(小), 就对应着大(小)顶堆

归并排序

归并也算是…二分的结构吧
两两合并， 一直到合成一个…和希尔排序有点像???
也不太像…

然而归并是稳定的, 希尔是不稳定的

而且归并有二路归并，四路， 八路…????

基数排序

其实还感觉…这一块比较乱…我学这么多排序干啥呢