一些大学常用算法及知识点的回顾

本文是关于大学时一些常见的数据结构、算法和知识点的总结。其实与其说工作中会用到，不如说面试时被面到的可能性更大一些。不过其中一些特定领域的算法，像银行家算法，BAT的面试中我也还没有遇到过。适当地回顾大学时学到的一些知识点，也许能给自己带来一些快乐吧，一种仅存在于回忆中的快乐。

排序算法

冒泡排序

通过相邻元素的两两比较和swap，每次都将当前子序列中的最大/最小元素交换到当前子序列的最后面。

快速排序

选定第一个元素作为中轴，然后当i < j的前提下，指针j从右至左寻找一个比中轴小的元素，指针i从左至右寻找一个比中轴大的元素，然后swap两者。最终i=j，则将i所在元素和中轴再swap。
这里的重点是j必须先走。举个例子：3、1、2、5、4这个序列，如果i先移动，则最终的结构是5、1、2、3、4，显然是错误的。原因是：中轴选的是左边第一个元素（3），如果左边的指针先移动，极端案例下会使得左边指针停留在一个比中轴大的元素上（这里的5），而右边指针无法在i < j的情况下找到一个比中轴小的元素，导致最终5和3交换而错误。
的确无法很好地进行证明，只能举个反例来说明。

#include <stdio.h>
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left,int right)
{
    int i,j,t,temp;
    if(left>right)
       return;

    temp=a[left]; //temp中存的就是基准数
    i=left;
    j=right;
    while(i!=j)
    {
                   //顺序很重要，要先从右边开始找
                   while(a[j]>=temp && i<j)
                            j--;
                   //再找右边的
                   while(a[i]<=temp && i<j)
                            i++;
                   //交换两个数在数组中的位置
                   if(i<j)
                   {
                            t=a[i];
                            a[i]=a[j];
                            a[j]=t;
                   }
    }
    //最终将基准数归位
    a[left]=a[i];
    a[i]=temp;

    quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
}

归并排序

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    }
}

bool MergeSort(int a[], int n)
{
    int *p = new int[n];
    if (p == NULL)
        return false;
    mergesort(a, 0, n - 1, p);
    delete[] p;
    return true;
}

注：有的书上是在mergearray()合并有序数列时分配临时数组，但是过多的new操作会非常费时。因此作了下小小的变化。只在MergeSort()中new一个临时数组。后面的操作都共用这一个临时数组。

鸡尾酒排序

冒泡排序的变种，也被称作定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序。
先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。

二分查找

递归版本：

int BSearch(elemtype a[],elemtype x,int low,int high)
/*在下届为low，上界为high的数组a中折半查找数据元素x*/
{
    int mid;
    if(low > high)
        return -1;
    mid=(low + high) / 2;
    if(x == a[mid])
        return mid;
    if(x < a[mid])
        return(BSearch(a, x, low, mid-1));
    else return(BSearch(a, x, mid+1, high));
}

非递归版本

int binary_search(int* a, int len, int goal)
{
    int low = 0;
    int high = len - 1;
    while(low <= high)
    {
        int middle = (low + high)/2;
        if(a[middle] == goal)
            return middle;
        //在左半边
        else if(a[middle] > goal)
            high = middle - 1;
        //在右半边
        else
            low = middle + 1;
    }
    //没找到
    return -1;
}

图的遍历

DFS深度遍历（邻接图）

首先申请一个visted[n]数组，标记每个节点是否已经访问。
循环这个数组，如果一个节点没有被访问。就对其进行DFS遍历。
DFS遍历：标记当前节点为已访问。然后从邻接图中获取该节点的第一个未访问的可连通邻居，递归对该邻居进行DFS。然后再获取第二个未访问的可连通邻居，重复这个循环直到所有可连通邻居都处理完。

BFS广度遍历（邻接图）

首先申请一个visted[n]数组，标记每个节点是否已经访问。
循环这个数组，如果一个节点没有被访问。就对其进行BFS遍历。
BFS遍历：标记当前节点为已访问。然后创建一个queue，将当前节点放入queue。然后类似于二叉树的层次遍历，以queue中的当前节点作为种子，在while循环中，每次弹出queue中的一个节点，获取其所有未访问的邻居节点加入到queue中。直到最后queue为空。

最短路径

Dijkstra最短路径算法（单源最短路径）

这个算法既可以被划入到贪心法的范畴，也可以划入到动态规划的范畴。（排序的操作涉及贪心法，而之后的推进过程可看作是动态规划）
首先算出V0到各点的直连路径，然后从小到大排列，例如是V1、V2、V3……
建立一个大小为n的数组distances（下标从1开始），表示V0分别到这个n个点的最短距离，初始值就是直连距离。
首先V0到V1的最短路径一定就是V0到V1的直连路径，因为V1是距离V0最近的点，因此不可能有一条经过第三个点的绕路可以比V0到V1的直连路径更短。
然后V2则是比较V0-V1和V0-V1-V2，选取最短的那条。更新distances[2]。
而对于V3，则考察V0-V3直连距离，以及经过V1或V2到达V3的间接距离，选取最短的那条。更新distances[3]。
……
这里有个问题，为什么V0到V3的最短距离，一定是从已知点集合U中选择路径，而不是从未知点集合V中选择，例如V0-V4-V3这样的路径?
这就是一开始对n个直连路径进行排序的原因，V0-V4一定 >= V0-V3，因此V0-V4-V3一定 >= V0-V3。
另外本算法不能处理负权重边，用上面的例子说明，如果V0-V4是负权重，则有可能V0-V4-V3一定 < V0-V3，因此这种算法就不再使用。（此时有没有其它好的方法？除了各边都加上同一个偏移量，将负权重都转正。）

/***************************************
* About:    有向图的Dijkstra算法实现
* Author:   Tanky Woo
* Blog:     www.WuTianQi.com
***************************************/

#include <iostream>
using namespace std;

const int maxnum = 100;
const int maxint = 999999;

void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
    bool s[maxnum];    // 判断是否已存入该点到S集合中
    for(int i=1; i<=n; ++i)
    {
        dist[i] = c[v][i];
        s[i] = 0;     // 初始都未用过该点
        if(dist[i] == maxint)
            prev[i] = 0;
        else
            prev[i] = v;
    }
    dist[v] = 0;
    s[v] = 1;

    // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
    // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
    for(int i=2; i<=n; ++i)
    {
        int tmp = maxint;
        int u = v;
        // 找出当前未使用的点j的dist[j]最小值
        for(int j=1; j<=n; ++j)
            if((!s[j]) && dist[j]<tmp)
            {
                u = j;              // u保存当前邻接点中距离最小的点的号码
                tmp = dist[j];
            }
        s[u] = 1;    // 表示u点已存入S集合中

        // 更新dist
        for(int j=1; j<=n; ++j)
            if((!s[j]) && c[u][j]<maxint)
            {
                int newdist = dist[u] + c[u][j];
                if(newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
    }
}

void searchPath(int *prev,int v, int u)
{
    int que[maxnum];
    int tot = 1;
    que[tot] = u;
    tot++;
    int tmp = prev[u];
    while(tmp != v)
    {
        que[tot] = tmp;
        tot++;
        tmp = prev[tmp];
    }
    que[tot] = v;
    for(int i=tot; i>=1; --i)
        if(i != 1)
            cout << que[i] << " -> ";
        else
            cout << que[i] << endl;
}

int main()
{
    freopen("input.txt", "r", stdin);
    // 各数组都从下标1开始
    int dist[maxnum];     // 表示当前点到源点的最短路径长度
    int prev[maxnum];     // 记录当前点的前一个结点
    int c[maxnum][maxnum];   // 记录图的两点间路径长度
    int n, line;             // 图的结点数和路径数

    // 输入结点数
    cin >> n;
    // 输入路径数
    cin >> line;
    int p, q, len;          // 输入p, q两点及其路径长度

    // 初始化c[][]为maxint
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            c[i][j] = maxint;

    for(int i=1; i<=line; ++i)
    {
        cin >> p >> q >> len;
        if(len < c[p][q])       // 有重边
        {
            c[p][q] = len;      // p指向q
            c[q][p] = len;      // q指向p，这样表示无向图
        }
    }

    for(int i=1; i<=n; ++i)
        dist[i] = maxint;
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
            printf("%8d", c[i][j]);
        printf("\n");
    }

    Dijkstra(n, 1, dist, prev, c);

    // 最短路径长度
    cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;

    // 路径
    cout << "源点到最后一个顶点的路径为: ";
    searchPath(prev, 1, n);
}

Floyd最短路径算法（多源最短路径）

Dijkstra算法是用于计算单点到其它点的最短距离，复杂度是O(n²)，则计算完n个点的数据的复杂度就是O(n³)。而Floyd的算法复杂度也是O(n³).
虽然两者的算法复杂度一样，但是如果依次对某个顶点运用Dijkstra算法,则与Floyd算法相比,很多路径和结果计算是重复的,虽然复杂度相同,但是运算量差了很多。
此外，Dijkstra算法使用的前提是图中路径长度必须大于等于0，但是Floyd算法则仅仅要求没有总和小于0的环路就可以了。因此Floyd 算法应用范围比Dijkstra算法要广。

Floyd算法的思路：首先求出各点之间的直连距离矩阵，然后逐步引入1号点、2号点。。。

// 经过1号顶点
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if (e[i][j] > e[i][1]+e[1][j])  e[i][j]=e[i][1]+e[1][j];
// 经过2号顶点
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if (e[i][j] > e[i][2]+e[2][j])  e[i][j]=e[i][2]+e[2][j];

从而推导出一个三重循环

for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(e[i][j]>e[i][k]+e[k][j])
                e[i][j]=e[i][k]+e[k][j];

Floyd算法另一种理解DP，为理论爱好者准备的，上面这个形式的算法其实是Floyd算法的精简版，而真正的Floyd算法是一种基于DP(Dynamic Programming)的最短路径算法。设图G中n 个顶点的编号为1到n。令c [i, j, k]表示从i 到j 的最短路径的长度，其中k 表示该路径中的最大顶点，也就是说c[i,j,k]这条最短路径所通过的中间顶点最大不超过k。因此，如果G中包含边< i, j >，则c[i, j, 0] =边< i, j > 的长度；若i= j ，则c[i,j,0]=0；如果G中不包含边< i, j >，则c (i, j, 0)= +∞。c[i, j, n] 则是从i 到j 的最短路径的长度。对于任意的k>0，通过分析可以得到：中间顶点不超过k 的i到j的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为c[i, j, k-1]，否则长度为 c[i, k, k-1] +c [k, j, k-1]。c[i, j, k]可取两者中的最小值。状态转移方程：c[i, j, k]=min{c[i, j, k-1], c [i, k, k-1]+c [k, j, k-1]}，k＞0。这样，问题便具有了最优子结构性质，可以用动态规划方法来求解。

最小生成树：Prim算法和Kruskal算法

网上的Prim实现方法的时间复杂度是O(N²)，但实际上先用快速排序对各边进行排序，然后用两个hashset，U和V记录两种点。然后遍历一次边的有序列表进行了，时间复杂度O(logN)。
Kruskal算法的实现思想是：也是先对所有边排序，然后一开始时将每条边当作一个连通分量。然后循环地遍历边的有序列表，如果边的两个顶点不在同一个连通分量中，就将这两个连通分量合并为同一个（新的连通分量标识选择两者中较小的那个）。
（描述不太清楚，还是不知道两个算法的区别）

KMP算法

（待补完）

汉诺塔

class Solution:

    def __init__(self):
        self.i = 0

    def move(self, n, src, dst):
        self.i += 1
        print "the %d step: move dish %d %s to %s." % (self.i, n, src, dst)

    def hanoi(self, n, src, dst, dep):
        if 1 == n:
            self.move(1, src, dst)
        else:
            self.hanoi(n - 1, src, dep, dst)
            self.move(n, src, dst)
            self.hanoi(n - 1, dep, dst, src)

Bloom Filter

Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

无法从Bloom Filter集合中删除一个元素。因为该元素对应的位会牵动到其他的元素。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。此外，Bloom Filter的hash函数选择会影响算法的效果。

银行家算法

银行家算法：每个资源申请者要预先填写最大申请额度，然后以后每次能提出额度内的申请，银行家评估如果通过这次申请，那剩余的资源是否能构成安全序列。这里有一个假设是，每一名资源申请者只有在获取到最大额度的申请时，才会释放掉手中的资源。因此关键在于如何判断是否能够构成安全序列。
安全序列的判定：检查所有申请者，看当前剩余资源能够使得其中至少一个申请者可以满足最大额度申请而释放掉其资源。因为这是一个使得可用资源增长的过程，因此检查的顺序是不会影响最终判定结果的。

CA工作原理

SSL(Secure Socket Layer) 是一种加密技术，可以提供对称加密和非对称加密。由于它在协议层里正好是在传输层与应用层之间，这就决定了上层应用必须经过它，这就是它广泛流行和易于实现的原因。
对称加密有md5，sha1。由于md5已被学者证明可以计算出加密冲突，即它有一定的不安全性，所以建议用sha1加密。
非对称性加密有RSA，即密码有一对，一个私钥，一个公钥，公钥可以让所有人知道，私钥只有自己知道。
这样理解，服务器产生一对密钥，公钥给别人即客户端，客户端用它来加密，加密后发给服务端，服务端用自己的私钥解密后得到数据。
数字签名就和上面的过程相反，即数据由服务端用私钥加密，客户端用服务端的公钥解密，解得出来就说明这数据包的确是出服务端发过来的。
数字签名是由服务端自己签的，但没人去验证这个服务端是不是你所要访问的真实的，所以需要第三方来帮忙检验，就和支付宝处于第三方来协调的位置一样。这个第三方就叫CA。
所以服务器产生的公钥就交给CA，CA用CA自己的私钥加密，即数字签名，加密生会生成证书，证书还是要交给服务端，放在服务端那边。当客户端访问服务端时，服务端就会把这个证书安装到客户端上。
客户端就会用CA提供的CA自己的公钥来解密这个证书，（当然这个CA是浏览器预装时嵌入的可信的CA，如果不是预装时嵌入的CA，此时就没有CA的公钥，就解不了，就会弹出告警。）解得开就说明这个证书是某个CA认证过了的，是可信的，解开后就会得到数据，而这个数据就是服务端的公钥，此时用这个公钥与服务端进行数据传输。
数据传输过程中，由于RSA方式加解密速度非常慢，所以会把对称与非对称两者结合起来用，即用RSA把对称加密的密码进行加密传输，再用对称密码进行加解密，这样就可以提高效率，且是安全的。

B树

B树：分支节点和叶节点均保存记录的关键码和记录的指针
B+树：分支节点只保存记录关键码的复制，无记录指针。
所有记录都集中在叶节点一层，并且叶节点可以构成一维线性表，便于连续访问和范围查询。
两者的插入、删除基本一致。
对于同样阶的B树和B+树，B+树的树高和平均检索长度均大于B树（因为B+树必须检索到叶节点一层）
但实际上检索过程中，最耗时间的是…………IO，也就是访盘次数越少越好。
B+树的分支节点无记录指针，同样一个盘块可以存放的关键码数就更多，所以虽然平均检索长度大，但访盘次数反而少，速度也就比B树快。

deque、stack、queue、priority_queue，heap

deque和list/vector一样是基本的容器类型。但stack/queue/priority_queue/heap则是抽象容器类型，必须基于一种基本容器类型。
stack和queue默认是使用deque，而priority_queue默认是使用vector。
queue是一种单向队列，push类似push_back，pop类似pop_front，其实就是用adapter模式将基本容器类型的接口变化了一下，所以目前看来实际应用的不多。stack也类似。
priority_queue/heap则是基于基本容器类型，实现了一种高层的抽象数据结构。

堆算法

堆中每一个节点的父节点的下标是(i-1)/2, i!=0。
第一个非叶子结点是size/2。

堆的建立

从最后一个非叶子结点开始，从后向前推，每次都比较一个非叶子结点和其两个子节点，将最大者交换到该非叶子结点的位置。时间复杂度是O(N)。

堆的插入

将元素放到最后面，然后逐步与父节点进行调整。
父节点的下标是(i-1)/2,i!=0，对于大顶堆，如果当前节点比其父节点大，则swap，然后重复这个过程。
时间复杂度是o(logN)。

堆的删除

将堆顶元素弹出，然后将最后一个元素填充到堆顶，然后逐步与子节点进行调整。
子节点的下标是2i+1和2i+2，比较这两个节点与当前节点，将（可能的）最大者与当前节点进行swap，重复这个过程。
时间复杂度是o(logN)。

堆排序

首先需要建立堆。
然后每次将堆顶的元素与当前子序列中的最后一个元素交换，这样就同时完成了一个元素的直接选择排序，又完成了堆删除中的一步：将最后一个元素填充到堆顶。重复这个过程。
时间复杂度是O(N)+Nlog(N)=Nlog(N)
另外堆排序是不稳定的排序。（有没有可能规定相等元素在比较、替换等时的一套规则，使得堆排序能够稳定？）

路由协议

LS/DV

路由协议分成链路状态协议（LS）、和距离矢量协议（DV）两大类。

链路状态协议：例如OSPF协议。使用链路状态路由协议时，每台路由创建自己的LSA（链路状态通告），并在路由更新中泛洪（将网络的所有细节通告给其他的所有路由器）LSA给其他的所有路由器。泛洪LSA就是路由器将LSA发给邻居，邻居再将它转发给他的邻居，知道所有的路由器都收到这个LSA，路由器相连的子网也会创建并泛洪链路LSA，最后每台路由器都有所有路由器的LSA和所有链路LSA。

距离矢量协议：例如RIP协议。它们发送的全部的周期性（默认每隔30秒）的路由更新。更新中只包括子网和各自的距离（即到达目的子网的度量值）。除了邻居路由之外，路由器不了解网络拓扑的细节（因为它之和邻居路由交换数据）。如果到相同的子网有多条路由时，路由器选择最低度量值的路由，如果度量值相同时，就都选择（如rip协议中，有时有2个最佳路由）。

自治系统AS

自治系统AS：每一个AS分配一个16位的ASN号码，中国貌似至少有几十个ASN号码，上海电信、广东电信啥的都有自己独立的ASN号码。
在互联网中，一个自治系统(AS)是一个有权自主地决定在本系统中应采用何种路由协议的小型单位。这个网络单位可以是一个简单的网络也可以是一个由一个或多个普通的网络管理员来控制的网络群体，它是一个单独的可管理的网络单元（例如一所大学，一个企业或者一个公司个体）。一个自治系统有时也被称为是一个路由选择域（routing domain）。一个自治系统将会分配一个全局的唯一的16位号码，有时我们把这个号码叫做自治系统号（ASN）。

IGP/EGP

IGP是内部网关协议，是一类协议的统称，其本身并不是协议。例如OSPF、RIP就属于IGP协议。
EGP同样，是外部网关协议的统称。而BGP是EGP中一个具体的协议。

RIP协议

RIP协议被设计用于使用同种技术的中型网络，因此适应于大多数的校园网和使用速率变化不是很大的连续线的地区性网络。对于更复杂的环境，一般不使用RIP协议。
RIP作为一个系统长驻进程（daemon）而存在于路由器中，负责从网络系统的其它路由器接收路由信息，从而对本地IP层路由表作动态的维护，保证IP层发送报文时选择正确的路由。同时负责广播本路由器的路由信息，通知相邻路由器作相应的修改。RIP协议处于UDP协议的上层，RIP所接收的路由信息都封装在UDP协议的数据报中，RIP在520号UDP端口上接收来自远程路由器的路由修改信息，并对本地的路由表做相应的修改，同时通知其它路由器。
RIP路由协议用“更新（UNPDATES）”和“请求（REQUESTS）”这两种分组来传输信息的。每个具有RIP协议功能的路由器每隔30秒用UDP520端口给与之直接相连的机器广播更新信息。更新信息反映了该路由器所有的路由选择信息数据库。路由选择信息数据库的每个条目由“局域网上能达到的IP地址”和“与该网络的距离”两部分组成。请求信息用于寻找网络上能发出RIP报文的其他设备。

由于RIP的路由条目中并不保存完整路径，因此一旦网络波动，以及通讯延迟，可能会产生技术到无穷的问题。RIP设置最大条数15跳，也是为了避免这个问题。

水平分割：记录每条最佳路由是从哪个邻居的哪个端口收到的，将不会再通过该端口向该邻居广播这条最佳路由。但是局限是只能在两个路由器时有效，三个及更多的路由器，仍有可能形成环。
毒化逆转：与水平分割不同，还是会通过该端口向该邻居广播这条路由，但是会设置成距离16：不可达。有可能立刻解决路由选择环路。否则，不正确的路径将在路由表中驻留到超时为止。破坏逆转的缺点是它增加了路由更新的的数据大小，且还是有可能形成环。
保持定时器法：当一条路由被删除后，一定时间内（如180s）不会再更新该路由。
触发更新法：毒化逆转将任何两个路由器构成的环路打破，但三个或更多个路由器构成的环路仍会发生，直到无穷（16）时为止。触发式更新法可加速收敛时间，它的工作原理是当某个路径的跳数改变了，路由器立即发出更新信息，不管路由器是否到达常规信息更新时间都发出更新信息。

OSPF算法

OSPF算法真的不会成环么？例如A和B，两者交替地到目的IP的延时较短，那packet不就有可能在这两台路由器之间循环么？

海明码

（待补完）

欧拉回路/哈密顿回路

欧拉回路是经过所有边一次然后回到原点，哈密顿回路是经过所有节点一次然后回到原点，TSP旅行商问题就是哈密顿回路。
可见欧拉回路是有可能重复经过一个点的，但哈密顿回路不能重复经过一条边。

本文地址：http://xnerv.wang/some-knowledge-points-learned-in-university/