数学归纳法, 递归, 栈

数学归纳法

数学归纳法(mathematical induction)是一种数学证明方法，常用于证明命题(命题是对某个现象的描述)在自然数范围内成立。随着现代数学的发展，自然数范围内的证明实际上构成了许多其他领域(比如数学分析)的基础，所以数学归纳法对于整个数学体系至关重要。

数学归纳法本身非常简单。如果我们想要证明某个命题对于自然数n都成立，那么:

第一步 证明命题对于n = 1成立。

第二步 假设命题对于n成立，n为任意自然数，证明在此假设下，命题对于n+1成立。

命题得证

想一下上面的两个步骤。它们实际上意味着，命题对于n = 1成立 -> 命题对于n = 2成立 -> 命题对于n = 3成立……直到无穷。因此，命题对于任意自然数都成立。这就好像多米诺骨牌，我们确定n的倒下会导致n + 1的倒下，然后推倒第一块骨牌，就能保证任意骨牌的倒下。

我们来看一下使用数学归纳法来证明高斯求和公式:

n为任意自然数。

(这个公式据说是高斯小学时想出来的。老师惩罚全班同学，必须算出1到100的累加，才能回家。于是高斯想出了上面的方法。天才都是被逼出来的么？)

我们的命题是: 高斯求和公式对于任意自然数n都成立。

下面为数学归纳法的证明步骤:

第一步 n = 1，等式左边(1的累加)为1，右边(右边公式代入n=1)也为1，等式两边相等，等式成立，因此命题对于 n = 1 成立。

第二步 假设上述公式对于任意n成立， 即1到n的累加为n*(n+1)/2

    那么，对于n+1，等式的左边(从1到n+1的累加)等于n*(n+1)/2 + (n+1)，即(n+1)*(n+2)/2，

                  等式的右边的n用n+1代替，成为(n+1)*(n+2)/2，

    等式两边相等，等式成立。因此，当假设命题对于n成立时，命题对于n+1成立。

因此，命题得证。

递归

递归(recursion)是计算机中的重要概念，它是指一个计算机程序调用其自身。为了保证计算机不陷入死循环，递归要求程序有一个能够达到的终止条件(base case)。比如下面的程序，是用于计算高斯求和公式:

/*
 * Gauss summation
 */

int f(n)
{
    if (n == 1) { 
        return 1;  // base case
    }
    else {
        return f(n-1) + n;  // induction
    }
}

在程序中规定了f(1)的值，以及f(n)和f(n-1)的关系。这正是数学归纳法思想的体现。想要得到f(n)，必须计算f(n-1)；想要f(n-1)，必须计算f(n-2)……直到f(1)。由于我们已经知道了f(1)的值，我们就可以填补前面所有的空缺，最终返回f(n)的值。

递归是数学归纳法在计算机中的程序实现。使用递归设计程序的时候，我们设置base case，并假设我们会获得n-1的结果，并实现n的结果。这就好像数学归纳法，我们只关注初始和衔接，而不需要关注具体的每一步。

栈

递归是用栈(stack)数据结构实现的。正如我们上面所说的，计算f(n)，需要f(n-1)；计算f(n-1)，需要f(n-2)……。我们在寻找到f(1)之前，会有许多空缺: f(n-1)的值什么？ f(n-2)的值是什么? …… f(2)的值是什么？f(1)的值是什么? 我们的第一个问题是f(n)是什么，结果，这个问题引出下一个问题，再下一个问题…… 每个问题的解答都依赖于下一个问题，直到我们找到第一个可以回答的问题: f(1)的值是什么?

我们用栈来保存我们在探索过程中的疑问。C语言中，函数的调用已经是用栈记录离场情境和返回地址。递归是函数对自身的调用，所以很自然的，递归用栈来保存我们的“疑问” 。

我们假设栈向下增长。首先，我们调用f(100)，那么当执行到

return f(n-1) + n;

f(100)暂停执行，并记录当前的状态，比如n的值，当前执行到的位置。随后调用f(99)，栈增加一个frame，直到调用f(98) ... 栈不断增长，直到f(1)。f(1)得到结果1，并返回给f(2)。f(1)栈frame删除，转移到f(2)frame情境中继续执行

return f(n-1) + n;

然后返回给f(3) ... 直到f(99)返回给f(100)，并执行

return f(n-1) + n;

返回f(100)的值，得到结果。

上述过程是C编译器自动完成的。在实现递归算法时，也可以自行手动实现栈。这样可以得到更好的运行效率。

总结

数学归纳法

递归

栈

排序算法简介及其C实现

排序算法(Sorting Algorithm)是计算机算法的一个组成部分。

排序的目标是将一组数据 (即一个序列) 重新排列，排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经典之作《计算机程序设计艺术》(The Art of Computer Programming)的第三卷就专门用于讨论排序和查找。从无序到有序，有效的减小了系统的熵值，增加了系统的有序度。对于一个未知系统来说，有序是非常有用的先验知识。因此，排序算法很多时候构成了其他快速算法的基础，比如二分法就是基于有序序列的查找算法。直到今天，排序算法依然是计算机科学积极探索的一个方向。

我在这里列出一些最常见的排序方法，并尝试使用C语言实现它们。一组数据存储为一个数组a，数组有n个元素。a[i]为数组中的一个元素，i为元素在数组中的位置 (index)。根据C的规定，数组下标从0开始。假设数组从左向右排列，下标为0的元素位于数组的最左边。

序列将最终排列成从小到大的顺序。下面函数中的参数ac是数组中元素的数目，也就是n。

(C语言的数组名都转成指针，传递给函数，所以需要传递数组中元素的数目ac给函数，详细见"Expert C Programming: Deep C Secrets"一书)

起始数列 （unsorted）

有序数列 (sorted)

下面的链接中，有相关算法的动画图例，强烈推荐同时阅读。

http://www.sorting-algorithms.com/

冒泡排序 (Bubble Sort)

对于一个已经排序好的序列，它的任意两个相邻元素，都应该满足a[i-1] <= a[i]的关系。冒泡排序相当暴力的实现了这一目标：不断扫描相邻元素，看它们是否违章。一旦违章，立即纠正。在冒泡排序时，计算机从右向左遍历数组，比较相邻的两个元素。如果两个元素的顺序是错的，那么sorry，请两位互换。如果两个元素的顺序是正确的，则不做交换。经过一次遍历，我们可以保证最小的元素(泡泡)处于最左边的位置。

然而，经过这么一趟，冒泡排序不能保证所有的元素已经按照次序排列好。我们需要再次从右向左遍历数组元素，进行冒泡排序。这一次遍历，我们不用考虑最左端的元素，因为该元素已经是最小的。遍历结束后，继续重复扫描…… 总共可能进行n-1次的遍历。

如果某次遍历过程中，没有发生交换，bingo，这个数组已经排序好，可以中止排序。如果起始时，最大的元素位于最左边，那么冒泡算法必须经过n-1次遍历才能将数组排列好，而不能提前完成排序。

/*By Vamei*/
/*swap the neighbors if out of order*/void bubble_sort(int a[], int ac)
{
    /*use swap*/
    int i,j;
    int sign;
    for (j = 0; j < ac-1; j++) {
        sign = 0;
        for(i = ac-1; i > j; i--)
        {
            if(a[i-1] > a[i]) {
                sign = 1;
                swap(a+i, a+i-1);
            }
        }
        if (sign == 0) break;
    }
}

插入排序 (Insertion Sort)

假设在新生报到的时候，我们将新生按照身高排好队(也就是排序)。如果这时有一名学生加入，我们将该名学生加入到队尾。如果这名学生比前面的学生低，那么就让该学生和前面的学生交换位置。这名学生最终会换到应在的位置。这就是插入排序的基本原理。

对于起始数组来说，我们认为最初，有一名学生，也就是最左边的元素(i=0)，构成一个有序的队伍。

随后有第二个学生(i=1)加入队伍，第二名学生交换到应在的位置；随后第三个学生加入队伍，第三名学生交换到应在的位置…… 当n个学生都加入队伍时，我们的排序就完成了。

/*By Vamei*/
/*insert the next element 
  into the sorted part*/
void insert_sort(int a[], int ac)
{
    /*use swap*/
    int i,j;    
    for (j=1; j < ac; j++) 
    {
        i = j-1;
        while((i>=0) && (a[i+1] < a[i])) 
        {
            swap(a+i+1, a+i);
            i--;
        }
    }
}

选择排序 (Selection Sort)

排序的最终结果：任何一个元素都不大于位于它右边的元素 (a[i] <= a[j], if i <= j)。所以，在有序序列中，最小的元素排在最左的位置，第二小的元素排在i=1的位置…… 最大的元素排在最后。

选择排序是先找到起始数组中最小的元素，将它交换到i=0；然后寻找剩下元素中最小的元素，将它交换到i=1的位置…… 直到找到第二大的元素，将它交换到n-2的位置。这时，整个数组的排序完成。

/*By Vamei*/
/*find the smallest of the rest,
  then append to the sorted part*/
void select_sort(int a[], int ac) 
{
    /*use swap*/
    int i,j;
    int min_idx;
    for (j = 0; j < ac-1; j++) 
    {
        min_idx = j;
        for (i = j+1; i < ac; i++) 
        {
            if (a[i] < a[min_idx]) 
            {
                min_idx = i;
            }
        }
        swap(a+j, a+min_idx);
    }    
}

希尔排序 （Shell Sort）

我们在冒泡排序中提到，最坏的情况发生在大的元素位于数组的起始。这些位于数组起始的大元素需要多次遍历，才能交换到队尾。这样的元素被称为乌龟(turtle)。

乌龟元素的原因在于，冒泡排序总是相邻的两个元素比较并交换。所以每次从右向左遍历，大元素只能向右移动一位。(小的元素位于队尾，被称为兔子(rabbit)元素，它们可以很快的交换到队首。)

希尔排序是以更大的间隔来比较和交换元素，这样，大的元素在交换的时候，可以向右移动不止一个位置，从而更快的移动乌龟元素。比如，可以将数组分为4个子数组（i=4k, i=4k+1, i=4k+2, i=4k+3），对每个子数组进行冒泡排序。比如子数组i=0，4，8，12...。此时，每次交换的间隔为4。

完成对四个子数组的排序后，数组的顺序并不一定能排列好。希尔排序会不断减小间隔，重新形成子数组，并对子数组冒泡排序…… 当间隔减小为1时，就相当于对整个数组进行了一次冒泡排序。随后，数组的顺序就排列好了。

希尔排序不止可以配合冒泡排序，还可以配合其他的排序方法完成。

/*By Vamei*/
/*quickly sort the turtles at the tail of the array*/
void shell_sort(int a[], int ac)
{
    int step;
    int i,j;
    int nsub;
    int *sub;

    /* initialize step */
    step = 1;
    while(step < ac) step = 3*step + 1;

    /* when step becomes 1, it's equivalent to the bubble sort*/
    while(step > 1) {
       /* step will go down to 1 at most */
       step = step/3 + 1;
       for(i=0; i<step; i++) {
           /* pick an element every step, 
              and combine into a sub-array */
           nsub = (ac - i - 1)/step + 1;            
           sub = (int *) malloc(sizeof(int)*nsub);
           for(j=0; j<nsub; j++) {
               sub[j] = a[i+j*step]; 
           }
           /* sort the sub-array by bubble sorting. 
              It could be other sorting methods */
           bubble_sort(sub, nsub);
           /* put back the sub-array*/
           for(j=0; j<nsub; j++) {
               a[i+j*step] = sub[j];
           }
           /* free sub-array */
           free(sub);
       }    
    }
}

Shell Sorting依赖于间隔(step)的选取。一个常见的选择是将本次间隔设置为上次间隔的1/1.3。见参考书籍。

归并排序 (Merge Sort)

如果我们要将一副扑克按照数字大小排序。此前已经有两个人分别将其中的一半排好顺序。那么我们可以将这两堆扑克向上放好，假设小的牌在上面。此时，我们将看到牌堆中最上的两张牌。

我们取两张牌中小的那张取出放在手中。两个牌堆中又是两张牌暴露在最上面，继续取小的那张放在手中…… 直到所有的牌都放入手中，那么整副牌就排好顺序了。这就是归并排序。

下面的实现中，使用递归：

/*By Vamei*/
/*recursively merge two sorted arrays*/
void merge_sort(int *a, int ac)
{
    int i, j, k;    
    int ac1, ac2;
    int *ah1, *ah2;
    int *container;

    /*base case*/    
    if (ac <= 1) return;

    /*split the array into two*/
    ac1 = ac/2;
    ac2 = ac - ac1;
    ah1 = a + 0;
    ah2 = a + ac1;

    /*recursion*/
    merge_sort(ah1, ac1);
    merge_sort(ah2, ac2);
 
    /*merge*/
    i = 0;
    j = 0;
    k = 0;
    container = (int *) malloc(sizeof(int)*ac);
    while(i<ac1 && j<ac2) {
        if (ah1[i] <= ah2[j]) {
            container[k++] = ah1[i++];
        } 
        else {
            container[k++] = ah2[j++];
        }
    }
    while (i < ac1) {
        container[k++] = ah1[i++];
    }
    while (j < ac2) {
        container[k++] = ah2[j++];
    }

    /*copy back the sorted array*/
    for(i=0; i<ac; i++) {
        a[i] = container[i];
    }
    /*free space*/
    free(container);
}

快速排序 (Quick Sort)

我们依然考虑按照身高给学生排序。在快速排序中，我们随便挑出一个学生，以该学生的身高为参考(pivot)。然后让比该学生低的站在该学生的右边，剩下的站在该学生的左边。

很明显，所有的学生被分成了两组。该学生右边的学生的身高都大于该学生左边的学生的身高。

我们继续，在低身高学生组随便挑出一个学生，将低身高组的学生分为两组(很低和不那么低)。同样，将高学生组也分为两组(不那么高和很高)。

如此继续细分，直到分组中只有一个学生。当所有的分组中都只有一个学生时，则排序完成。

在下面的实现中，使用递归:

/*By Vamei*/
/*select pivot, put elements (<= pivot) to the left*/
void quick_sort(int a[], int ac)
{
    /*use swap*/

    /* pivot is a position, 
       all the elements before pivot is smaller or equal to pvalue */
    int pivot;
    /* the position of the element to be tested against pivot */
    int sample;

    /* select a pvalue.  
       Median is supposed to be a good choice, but that will itself take time.
       here, the pvalue is selected in a very simple wayi: a[ac/2] */
    /* store pvalue at a[0] */
    swap(a+0, a+ac/2);
    pivot = 1; 

    /* test each element */
    for (sample=1; sample<ac; sample++) {
        if (a[sample] < a[0]) {
            swap(a+pivot, a+sample);
            pivot++;
        }
    }
    /* swap an element (which <= pvalue) with a[0] */
    swap(a+0,a+pivot-1);

    /* base case, if only two elements are in the array,
       the above pass has already sorted the array */
    if (ac<=2) return;
    else {
        /* recursion */
        quick_sort(a, pivot);
        quick_sort(a+pivot, ac-pivot);
    }
}

理想的pivot是采用分组元素中的中位数。然而寻找中位数的算法需要另行实现。也可以随机选取元素作为pivot，随机选取也需要另行实现。为了简便，我每次都采用中间位置的元素作为pivot。 

堆排序 (Heap Sort)

堆(heap)是常见的数据结构。它是一个有优先级的队列。最常见的堆的实现是一个有限定操作的Complete Binary Tree。这个Complete Binary Tree保持堆的特性，也就是父节点(parent)大于子节点(children)。因此，堆的根节点是所有堆元素中最小的。堆定义有插入节点和删除根节点操作，这两个操作都保持堆的特性。

我们可以将无序数组构成一个堆，然后不断取出根节点，最终构成一个有序数组。

堆的更详细描述请阅读参考书目。

下面是堆的数据结构，以及插入节点和删除根节点操作。你可以很方便的构建堆，并取出根节点，构成有序数组。

/* By Vamei 
   Use an big array to implement heap
   DECLARE: int heap[MAXSIZE] in calling function
   heap[0] : total nodes in the heap
   for a node i, its children are i*2 and i*2+1 (if exists)
   its parent is i/2  */

void insert(int new, int heap[]) 
{
    int childIdx, parentIdx;
    heap[0] = heap[0] + 1;
    heap[heap[0]] = new;
    
    /* recover heap property */
    percolate_up(heap);
}

static void percolate_up(int heap[]) {
    int lightIdx, parentIdx;
    lightIdx  = heap[0];
    parentIdx = lightIdx/2;
    /* lightIdx is root? && swap? */
    while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {
        /* swap */
        swap(heap + lightIdx, heap + parentIdx); 
        lightIdx  = parentIdx;
        parentIdx = lightIdx/2;
    }
}


int delete_min(int heap[]) 
{
    int min;
    if (heap[0] < 1) {
        /* delete element from an empty heap */
        printf("Error: delete_min from an empty heap.");
        exit(1);
    }

    /* delete root 
       move the last leaf to the root */
    min = heap[1];
    swap(heap + 1, heap + heap[0]);
    heap[0] -= 1;

    /* recover heap property */
    percolate_down(heap);
 
    return min;
}

static void percolate_down(int heap[]) {
    int heavyIdx;
    int childIdx1, childIdx2, minIdx;
    int sign; /* state variable, 1: swap; 0: no swap */

    heavyIdx = 1;
    do {
        sign     = 0;
        childIdx1 = heavyIdx*2;
        childIdx2 = childIdx1 + 1;
        if (childIdx1 > heap[0]) {
            /* both children are null */
            break; 
        }
        else if (childIdx2 > heap[0]) {
            /* right children is null */
            minIdx = childIdx1;
        }
        else {
            minIdx = (heap[childIdx1] < heap[childIdx2]) ?
                          childIdx1 : childIdx2;
        }

        if (heap[heavyIdx] > heap[minIdx]) {
            /* swap with child */
            swap(heap + heavyIdx, heap + minIdx);
            heavyIdx = minIdx;
            sign = 1;
        }
    } while(sign == 1);
}

总结

除了上面的算法，还有诸如Bucket Sorting, Radix Sorting涉及。我会在未来实现了相关算法之后，补充到这篇文章中。相关算法的时间复杂度分析可以参考书目中找到。我自己也做了粗糙的分析。如果博客园能支持数学公式的显示，我就把自己的分析过程贴出来，用于引玉。

上面的各个代码是我自己写的，只进行了很简单的测试。如果有错漏，先谢谢你的指正。

最后，上文中用到的交换函数为：

/* By Vamei */
/* exchange the values pointed by pa and pb*/
void swap(int *pa, int *pb)
{
    int tmp;
    tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

表 (list)

表

表(list)是常见的数据结构。从数学上来说，表是一个有序的元素集合。在C语言的内存中，表储存为分散的节点(node)。每个节点包含有一个元素，以及一个指向下一个(或者上一个)元素的指针。如下图所示:

表: 橙色储存数据，蓝色储存指针

图中的表中有四个节点。第一个节点是头节点(head node)，这个节点不用于储存元素，只用于标明表的起始。头节点可以让我们方便的插入或者删除表的第一个元素。整个表中包含有三个元素(5， 2， 15)。每个节点都有一个指针，指向下一个节点。最后一个节点的指针为NULL，我们用“接地”来图示该指针。

表的功能与数组(array)很类似，数组也是有序的元素集合，但数组在内存中为一段连续内存，而表的每个节点占据的内存可以是离散的。在数组中，我们通过跳过固定的内存长度来寻找某个编号的元素。但在表中，我们必须沿着指针联系起的长链，遍历查询元素。此外，数组有固定的大小，表可以根据运行情况插入或者删除节点，动态的更改大小。表插入节点时需要从进程空间的堆中开辟内存空间，用以储存节点。删除节点可以将节点占据的内存归还给进程空间。

删除节点, free释放内存

插入节点，malloc开辟内存

表有多种变种。上面的表中，指针指向是从前向后的，称为单向链表(linked list)。还有双向链表(double-linked list)，即每个节点增加一个指向前面一个元素的指针。以及循环链表(tabular list)，最后一个元素的指针并不为NULL，而是指向头节点。不同类型的链表有不同的应用场景。

双向链表

循环链表

双向循环链表

单向链表的C实现

一个数据结构的实现有两方面: 1. 数据结构的内存表达方式; 2. 定义在该数据结构上的操作。我们这里实现最简单的单向链表。表所支持的操作很灵活多样，我们这里定义一些最常见的操作。每个操作都写成一个函数。

/* By Vamei */
#include <stdio.h>#include <stdlib.h>
typedef struct node *LIST; 
typedef struct node *position;

/* node，节点 */struct node {
    int element;
    position next;
};/* 
 * operations (stereotype)
 * 操作
 */
LIST init_list(void);void delete_list(LIST);
int is_null(LIST);
void insert_node(position, int);void delete_node(LIST, position);
position find_last(LIST);
position find_value(LIST, int);
position find_previous(LIST, position);
void print_list(LIST);
/* for testing purpose */void main()
{
    LIST L;
    position np;
    
    int i;
    /* elements to be put into the list */
    int a[] = {1, 3, 5, 7, 9};

    /* initiate a list */
    L = init_list();
    print_list(L);

    /* insert nodes. Insert just after head node */
    for (i=4; i>=0; i--) {
        insert_node(L, a[i]);
    }
    print_list(L);

    /* delete first node with value 5 */
    np = find_value(L, 5);
    delete_node(L, np);
    print_list(L);

    /* delete list */
    delete_list(L);

    /* initiate a list */
    L = init_list();
    print_list(L);

    /* insert nodes. Insert just after head node */
    for (i=4; i>=0; i--) {
        insert_node(L, a[i]);
    }
    print_list(L);

    /* delete list */
    delete_list(L);
}/*
 * Traverse the list and print each element
 * 打印表 */void print_list(LIST L)
{
    position np;
    if(is_null(L)) {
        printf("Empty List\n\n");
        return;
    }

    np = L;
    while(np->next != NULL) { 
        np = np->next;
        printf("%p: %d \n", np, np->element);
    }
    printf("\n");

}/*
 * Initialize a linked list. This list has a head node
 * head node doesn't store valid element value
 * 创建表 */LIST init_list(void) 
{
    LIST L;
    L = (position) malloc(sizeof(struct node));
    L->next = NULL;
    return L;
}/*
 * Delete all nodes in a list
 * 删除表 */void delete_list(LIST L)
{
    position np, next;

    np   = L;
    do {
        next = np->next;
        free(np);
        np   = next;
    } while(next != NULL);    
}/*
 * if a list only has head node, then the list is null.
 * 判断表是否为空 */int is_null(LIST L) 
{
    return ((L->next)==NULL);
}/*
 * insert a node after position np
 * 在np节点之后，插入节点 */void insert_node(position np, int value) 
{
    position nodeAddr;
    
    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = value;
    nodeAddr->next = np->next;
    np->next = nodeAddr;    
}/*
 * delete node at position np
 * 删除np节点 */void delete_node(LIST L, position np)
{
    position previous, next;
    next     = np->next;
    previous = find_previous(L, np);
    if(previous != NULL) {
        previous->next = next;
        free(np); 
    }
    else {
        printf("Error: np not in the list");
    }
}/*
 * find the last node of the list
 * 寻找表的最后一个节点
 */position find_last(LIST L)
{
    position np;
    np = L;
    while(np->next != NULL) {
        np = np->next;
    }
    return np;
}/*
 * This function serves for 2 purposes:
 * 1. find previous node 
 * 2. return NULL if the position isn't in the list
 * 寻找npTarget节点前面的节点 */position find_previous(LIST L, position npTarget)
{
    position np;
    np = L;
    while (np->next != NULL) {
        if (np->next == npTarget) return np; 
        np = np->next;
    } 
    return NULL;
}/*
 * find the first node with specific value
 * 查询 */position find_value(LIST L, int value) 
{
    position np;
    np = L;
    while (np->next != NULL) {
        np = np->next;
        if (np->element == value) return np;
    }
    return NULL;
}

在main()函数中，我们初始化表，然后插入(1, 3, 5, 7, 9）。又删除元素5。可以看到，节点零散的分布在内存中。删除节点操作不会影响其他节点的存储位置。

我们随后删除表，又重新创建表。可以看到，这次表占据内存的位置与第一次不同。

下面是main()函数的运行结果。

Empty List

0x154d0b0: 1 
0x154d090: 3 
0x154d070: 5 
0x154d050: 7 
0x154d030: 9 

0x154d0b0: 1 
0x154d090: 3 
0x154d050: 7 
0x154d030: 9 

Empty List

0x154d070: 1 
0x154d010: 3 
0x154d0b0: 5 
0x154d090: 7 
0x154d050: 9

总结

表: 内存中离散分布的有序节点

插入，删除节点

栈 (stack)

栈(stack)是简单的数据结构，但在计算机中使用广泛。它是有序的元素集合。栈最显著的特征是LIFO (Last In, First Out, 后进先出)。当我们往箱子里存放一叠书时，先存放的书在箱子下面，我们必须将后存放的书取出来，才能看到和拿出早先存放的书。

栈中的每个元素称为一个frame。而最上层元素称为top frame。栈只支持三个操作， pop, top, push。

pop取出栈中最上层元素(8)，栈的最上层元素变为早先进入的元素(9)。

top查看栈的最上层元素(8)。

push将一个新的元素(5)放在栈的最上层。

栈不支持其他操作。如果想取出元素12, 必须进行3次pop操作。

栈以及pop, push, top操作

栈最经典的计算机应用是函数调用。每个进程都会有一个栈，每个frame中记录了调用函数的参数，自动变量和返回地址。当该函数调用一个新的函数时，栈中会 push一个frame。当函数执行完毕返回时，该frame会pop，从而进入调用该函数的原函数，继续执行。详细请参阅Linux从程序到进程

实际使用的栈并不一定符合数据结构的栈。比如说，有的语言允许被调用函数查看非top frame的记录。这样的栈更类似于下面的经典游戏

栈的C实现 (基于表)

由于栈是限定了操作的有序的元素集合，所以我们既可以在数组的基础上来实现栈，也可以在表的基础上来实现栈。如果使用数组来实现栈，我们需要预留充足的空间供栈使用，并需要一个下标来记录最上层元素的位置。

我们这里使用单向链表来实现栈。我们可以利用介绍表(list)的文章中已经定义的操作来实现三个操作，但这里相对独立的重写了代码。

/* By Vamei */
/* use single-linked list to implement stack */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

// point to the  head node of the list
typedef struct node *STACK;
 
struct node {
    ElementTP element;
    position next;
};

STACK init_stack(void);
void delete_stack(STACK);
ElementTP top(STACK);
void push(STACK, ElementTP);
ElementTP pop(STACK);
int is_null(STACK);

void main(void)
{
    ElementTP a;
    int i;
    STACK sk;
    sk = init_stack();
    push(sk, 1);
    push(sk, 2);
    push(sk, 8);
    printf("Stack is null? %d\n", is_null(sk));
    for (i=0; i<3; i++) {
        a = pop(sk);
        printf("pop: %d\n", a);
    }

    printf("Stack is null? %d\n", is_null(sk));    
    delete_stack(sk);
}

/*
 * initiate the stack
 * malloc the head node.
 * Head node doesn't store valid data
 * head->next is the top node
 */
STACK init_stack(void)
{
    position np;
    STACK    sk;
    np = (position) malloc(sizeof(struct node));
    np->next     = NULL;  // sk->next is the top node
    sk = np; 
    return sk;
}

/* pop out all elements 
 * and then delete head node
 */
void delete_stack(STACK sk)
{
    while(!is_null(sk)) {
        pop(sk);
    }
    free(sk);
}
/* 
 * View the top frame
 */
ElementTP top(STACK sk)
{
    return (sk->next->element);
}

/*
 * push a value into the stack
 */
void push(STACK sk, ElementTP value) 
{
    position np, oldTop;
    oldTop = sk->next;    

    np = (position) malloc(sizeof(struct node));
    np->element  = value;
    np->next     = sk->next;

    sk->next     = np; 
}

/* 
 * pop out the top value
 */
ElementTP pop(STACK sk)
{
    ElementTP element;
    position top, newTop;
    if (is_null(sk)) {
        printf("pop() on an empty stack");
        exit(1);
    } 
    else {
        top      = sk->next;
        element  = top->element;     
        newTop   = top->next;
        sk->next     = newTop;
        free(top);
        return element;
    } 
}

/* check whether a stack is empty*/
int is_null(STACK sk)
{
    return (sk->next == NULL);
}

输出结果:

Stack is null? 0
pop: 8
pop: 2
pop: 1
Stack is null? 1

总结

栈, LIFO

pop, push, top

欢迎继续阅读“纸上谈兵: 算法与数据结构”系列。

Update:

我之前是用双向循环链表实现的栈，后来发现这样没有必要。它不能给栈带来额外的好处，还会增加所需的内存空间。

队列 (queue)

队列(queue)是一个简单而常见的数据结构。队列也是有序的元素集合。队列最大的特征是First In, First Out (FIFO，先进先出)，即先进入队列的元素，先被取出。这一点与栈(stack)形成有趣的对比。队列在生活中很常见，排队买票、排队等车…… 先到的人先得到服务并离开队列，后来的人加入到队列的最后。队列是比较公平的分配有限资源的方式，可以让队列的人以相似的等待时间获得服务。

队列支持两个操作，队首的元素离开队列(dequeue)，和新元素加入队尾(enqueue)。

队列

队列在计算机中应用很广泛。一个经典的应用是消息队列(参考Linux进程间通信)，实际上就是利用队列来分配有限的进程。还有FIFO文件(哦，你可以看到，这种文件叫做FIFO，肯定是和队列有关)，用以实现管道传输。再比如，我们将多个打印任务发送给打印机，打印机也是使用队列来安排任务的顺序。

队列的C实现 (基于表)

和栈相似，队列也可以有多种实现方式，这里是基于单链表的实现。

与表(list)中的实现方式略有不同的是，这里的head node有两个指针，一个(next)指向下一个元素，一个(end)指向队列的最后一个元素。这样做的目的是方便我们找到队尾，以方便的进行enqueue操作。我们依然可以使用之前定义的表，在需要找到队尾的时候遍历搜索到最后一个元素。

用于队列的表

下面是代码:

/* By Vamei */
/* use single-linked list to implement queue */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

// point to the head node of the list
typedef struct HeadNode *QUEUE;
 
struct node {
    ElementTP element;
    position next;
};

/*
 * CAUTIOUS: "HeadNode" is different from "node", 
 * it's another struct
 * end: points to the last value in the queue
 */
struct HeadNode {
    ElementTP element;
    position next;
    position end;
};


/*
 * Operations
 */
QUEUE init_queue(void);
void delete_queue(QUEUE);
void enqueue(QUEUE, ElementTP);
ElementTP dequeue(QUEUE);
int is_null(QUEUE);

/*
 * Test
 */
void main(void)
{
    ElementTP a;
    int i;
    QUEUE qu;
    qu = init_queue();

    enqueue(qu, 1);
    enqueue(qu, 2);
    enqueue(qu, 8);
    printf("Queue is null? %d\n", is_null(qu));
    for (i=0; i<3; i++) {
        a = dequeue(qu);
        printf("dequeue: %d\n", a);
    }

    printf("Queue is null? %d\n", is_null(qu));    
    delete_queue(qu);
}

/*
 * initiate the queue
 * malloc the head node.
 * Head node doesn't store valid data
 * head->next is the first node in the queue.
 */
QUEUE init_queue(void)
{
    QUEUE hnp;
    hnp = (QUEUE) malloc(sizeof(struct HeadNode));
    hnp->next = NULL;  // qu->next is the first node
    hnp->end  = NULL;
    return hnp;
}

/*
 * dequeue all elements 
 * and then delete head node
 */
void delete_queue(QUEUE qu)
{
    while(!is_null(qu)) {
        dequeue(qu);
    }
    free(qu);
}

/*
 * enqueue a value to the end of the queue 
 */
void enqueue(QUEUE qu, ElementTP value) 
{
    position np, oldEnd;
    oldEnd = qu->end;    

    np = (position) malloc(sizeof(struct node));
    np->element  = value;
    np->next     = NULL;

    /* if queue is empyt, then oldEnd is NULL */
    if (oldEnd) {
        oldEnd->next = np;
    }
    else {
        qu->next     = np;
    }

    qu->end = np; 
}

/* 
 * dequeue the first value
 */
ElementTP dequeue(QUEUE qu)
{
    ElementTP element;
    position first, newFirst;
    if (is_null(qu)) {
        printf("dequeue() on an empty queue");
        exit(1);
    } 
    else {
        first        = qu->next;
        element      = first->element;     
        newFirst     = first->next;
        qu->next     = newFirst;
        free(first);
        return element;
    } 
}

/*
 * check: queue is empty?
 */
int is_null(QUEUE qu)
{
    return (qu->next == NULL);
}

运行结果如下:

Queue is null? 0
dequeue: 1
dequeue: 2
dequeue: 8
Queue is null? 1

总结

队列，FIFO

enqueue, dequeue

 树, 二叉树, 二叉搜索树

树的特征和定义

树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树：

树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。

每个节点可以有多个子节点(children)，而该节点是相应子节点的父节点(parent)。比如说，3,5是6的子节点，6是3,5的父节点；1,8,7是3的子节点, 3是1,8,7的父节点。树有一个没有父节点的节点，称为根节点(root)，如图中的6。没有子节点的节点称为叶节点(leaf)，比如图中的1,8,9,5节点。从图中还可以看到，上面的树总共有4个层次，6位于第一层，9位于第四层。树中节点的最大层次被称为深度。也就是说，该树的深度(depth)为4。

如果我们从节点3开始向下看，而忽略其它部分。那么我们看到的是一个以节点3为根节点的树：

三角形代表一棵树

再进一步，如果我们定义孤立的一个节点也是一棵树的话，原来的树就可以表示为根节点和子树(subtree)的关系:

上述观察实际上给了我们一种严格的定义树的方法：

1. 树是元素的集合。

2. 该集合可以为空。这时树中没有元素，我们称树为空树 (empty tree)。

3. 如果该集合不为空，那么该集合有一个根节点，以及0个或者多个子树。根节点与它的子树的根节点用一个边(edge)相连。

上面的第三点是以递归的方式来定义树，也就是在定义树的过程中使用了树自身(子树)。由于树的递归特征，许多树相关的操作也可以方便的使用递归实现。我们将在后面看到。

(上述定义来自"Data Structures and Algorithm Analysis in C, by Mark Allen Weiss"。 我觉得有一点不太严格的地方。如果说空树属于树，第三点应该是 “...以及0个和多个非空子树...” )

树的实现

树的示意图已经给出了树的一种内存实现方式: 每个节点储存元素和多个指向子节点的指针。然而，子节点数目是不确定的。一个父节点可能有大量的子节点，而另一个父节点可能只有一个子节点，而树的增删节点操作会让子节点的数目发生进一步的变化。这种不确定性就可能带来大量的内存相关操作，并且容易造成内存的浪费。

一种经典的实现方式如下:

树的内存实现

拥有同一父节点的两个节点互为兄弟节点(sibling)。上图的实现方式中，每个节点包含有一个指针指向第一个子节点，并有另一个指针指向它的下一个兄弟节点。这样，我们就可以用统一的、确定的结构来表示每个节点。

计算机的文件系统是树的结构，比如Linux文件管理背景知识中所介绍的。在UNIX的文件系统中，每个文件(文件夹同样是一种文件)，都可以看做是一个节点。非文件夹的文件被储存在叶节点。文件夹中有指向父节点和子节点的指针(在UNIX中，文件夹还包含一个指向自身的指针，这与我们上面见到的树有所区别)。在git中，也有类似的树状结构，用以表达整个文件系统的版本变化 (参考版本管理三国志)。

文件树

二叉搜索树的C实现

二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点：

二叉树

由于二叉树的子节点数目确定，所以可以直接采用上图方式在内存中实现。每个节点有一个左子节点(left children)和右子节点(right children)。左子节点是左子树的根节点，右子节点是右子树的根节点。

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。

(如果我们假设树中没有重复的元素，那么上述要求可以写成：每个节点比它左子树的任意节点大，而且比它右子树的任意节点小)

二叉搜索树，注意树中元素的大小

二叉搜索树可以方便的实现搜索算法。在搜索元素x的时候，我们可以将x和根节点比较:

1. 如果x等于根节点，那么找到x，停止搜索 (终止条件)

2. 如果x小于根节点，那么搜索左子树

3. 如果x大于根节点，那么搜索右子树

二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n，最少为log(n)。

下面是用C语言实现的二叉搜索树，并有搜索，插入，删除，寻找最大最小节点的操作。每个节点中存有三个指针，一个指向父节点，一个指向左子节点，一个指向右子节点。

(这样的实现是为了方便。节点可以只保存有指向左右子节点的两个指针，并实现上述操作。)

删除节点相对比较复杂。删除节点后，有时需要进行一定的调整，以恢复二叉搜索树的性质(每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大)。

• 叶节点可以直接删除。

• 删除非叶节点时，比如下图中的节点8，我们可以删除左子树中最大的元素(或者右树中最大的元素)，用删除的节点来补充元素8产生的空缺。但该元素可能也不是叶节点，所以它所产生的空缺需要其他元素补充…… 直到最后删除一个叶节点。上述过程可以递归实现。

删除节点

删除节点后的二叉搜索树

/* By Vamei */
/* binary search tree */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

struct node {
    position parent;
    ElementTP element;
    position lchild;
    position rchild;
};

/* pointer => root node of the tree */
typedef struct node *TREE;

void print_sorted_tree(TREE);
position find_min(TREE);
position find_max(TREE);
position find_value(TREE, ElementTP);
position insert_value(TREE, ElementTP);
ElementTP delete_node(position);

static int is_root(position);
static int is_leaf(position);
static ElementTP delete_leaf(position);
static void insert_node_to_nonempty_tree(TREE, position);

void main(void) 
{
    TREE tr;
    position np;
    ElementTP element;
    tr = NULL;
    tr = insert_value(tr, 18);
    tr = insert_value(tr, 5);
    tr = insert_value(tr, 2); 
    tr = insert_value(tr, 8);
    tr = insert_value(tr, 81);
    tr = insert_value(tr, 101);
    printf("Original:\n");
    print_sorted_tree(tr);

    np = find_value(tr, 8);
    if(np != NULL) {
        delete_node(np);
        printf("After deletion:\n");
        print_sorted_tree(tr);
    }
}


/* 
 * print values of the tree in sorted order
 */
void print_sorted_tree(TREE tr)
{
    if (tr == NULL) return;
    print_sorted_tree(tr->lchild);
    printf("%d \n", tr->element);
    print_sorted_tree(tr->rchild);
}

/*
 * search for minimum value
 * traverse lchild
 */
position find_min(TREE tr)
{
    position np;
    np = tr;
    if (np == NULL) return NULL;
    while(np->lchild != NULL) {
        np = np->lchild;
    }
    return np;
}

/*
 * search for maximum value
 * traverse rchild
 */
position find_max(TREE tr)
{
    position np;
    np = tr;
    if (np == NULL) return NULL;
    while(np->rchild != NULL) {
        np = np->rchild;
    }
    return np;
}

/*
 * search for value
 *
 */
position find_value(TREE tr, ElementTP value) 
{
    if (tr == NULL) return NULL; 

    if (tr->element == value) {
        return tr;
    }
    else if (value < tr->element) {
        return find_value(tr->lchild, value);
    }
    else {
        return find_value(tr->rchild, value);
    }
}

/* 
 * delete node np 
 */
ElementTP delete_node(position np) 
{
    position replace;
    ElementTP element;
    if (is_leaf(np)) {
        return delete_leaf(np);
    }   
    else {
        /* if a node is not a leaf, then we need to find a replacement */
        replace = (np->lchild != NULL) ? find_max(np->lchild) : find_min(np->rchild);
        element = np->element;
        np->element = delete_node(replace);
        return element;
    }
}

/* 
 * insert a value into the tree
 * return root address of the tree
 */
position insert_value(TREE tr, ElementTP value) {
    position np;
    /* prepare the node */
    np = (position) malloc(sizeof(struct node));
    np->element = value;
    np->parent  = NULL;
    np->lchild  = NULL;
    np->rchild  = NULL;
 
    if (tr == NULL) tr = np;
    else {
        insert_node_to_nonempty_tree(tr, np);
    }
    return tr;
}


//=============================================

/*
 * np is root?
 */
static int is_root(position np)
{
    return (np->parent == NULL);
}

/*
 * np is leaf?
 */
static int is_leaf(position np)
{
    return (np->lchild == NULL && np->rchild == NULL);
}

/* 
 * if an element is a leaf, 
 * then it could be removed with no side effect.
 */
static ElementTP delete_leaf(position np)
{
    ElementTP element;
    position parent;
    element = np->element;
    parent  = np->parent;
    if(!is_root(np)) {
        if (parent->lchild == np) {
            parent->lchild = NULL;
        }
        else {
            parent->rchild = NULL;
        }
    }
    free(np);
    return element;
}

/*
 * insert a node to a non-empty tree
 * called by insert_value()
 */
static void insert_node_to_nonempty_tree(TREE tr, position np)
{
    /* insert the node */
    if(np->element <= tr->element) {
        if (tr->lchild == NULL) {
            /* then tr->lchild is the proper place */
            tr->lchild = np;
            np->parent = tr;
            return;
        }
        else {
            insert_node_to_nonempty_tree(tr->lchild, np);
        }
    }
    else if(np->element > tr->element) {
        if (tr->rchild == NULL) {
            tr->rchild = np;
            np->parent = tr;
            return;
        }
        else {
            insert_node_to_nonempty_tree(tr->rchild, np);
        }
    }
}

运行结果:

Original:
2 
5 
8 
18 
81 
101 
After deletion:
2 
5 
18 
81 
101

上述实现中的删除比较复杂。有一种简单的替代操作，称为懒惰删除(lazy deletion)。在懒惰删除时，我们并不真正从二叉搜索树中删除该节点，而是将该节点标记为“已删除”。这样，我们只用找到元素并标记，就可以完成删除元素了。如果有相同的元素重新插入，我们可以将该节点找到，并取消删除标记。

懒惰删除的实现比较简单，可以尝试一下。树所占据的内存空间不会因为删除节点而减小。懒惰节点实际上是用内存空间换取操作的简便性。

总结

树, 二叉树, 二叉搜索树

二叉搜索树的删除

懒惰删除

堆 (heap)

堆(heap)又被为优先队列(priority queue)。尽管名为优先队列，但堆并不是队列。回忆一下，在队列中，我们可以进行的限定操作是dequeue和enqueue。dequeue是按照进入队列的先后顺序来取出元素。而在堆中，我们不是按照元素进入队列的先后顺序取出元素的，而是按照元素的优先级取出元素。

这就好像候机的时候，无论谁先到达候机厅，总是头等舱的乘客先登机，然后是商务舱的乘客，最后是经济舱的乘客。每个乘客都有头等舱、商务舱、经济舱三种个键值(key)中的一个。头等舱->商务舱->经济舱依次享有从高到低的优先级。

再比如，封建社会的等级制度，也是一个堆。在这个堆中，国王、贵族、骑士和农民是从高到低的优先级。

封建等级

Linux内核中的调度器(scheduler)会按照各个进程的优先级来安排CPU执行哪一个进程。计算机中通常有多个进程，每个进程有不同的优先级(该优先级的计算会综合多个因素，比如进程所需要耗费的时间，进程已经等待的时间，用户的优先级，用户设定的进程优先程度等等)。内核会找到优先级最高的进程，并执行。如果有优先级更高的进程被提交，那么调度器会转而安排该进程运行。优先级比较低的进程则会等待。“堆”是实现调度器的理想数据结构。

(Linux中可以使用nice命令来影响进程的优先级)

堆的实现

堆的一个经典的实现是完全二叉树(complete binary tree)。这样实现的堆成为二叉堆(binary heap)。

完全二叉树是增加了限定条件的二叉树。假设一个二叉树的深度为n。为了满足完全二叉树的要求，该二叉树的前n-1层必须填满，第n层也必须按照从左到右的顺序被填满，比如下图:

为了实现堆的操作，我们额外增加一个要求: 任意节点的优先级不小于它的子节点。如果在上图中，设定小的元素值享有高的优先级，那么上图就符合该要求。

这类似于“叠罗汉”。叠罗汉最重要的一点，就是让体重大的参与者站在最下面，让体重小的参与者站在上面 (体重小，优先级高)。为了让“堆”稳固，我们每次只允许最上面的参与者退出堆。也就是，每次取出的优先级最高的元素。

三个“叠罗汉”堆

我已经在排序算法简介及其C实现中实际使用了堆。堆的主要操作是插入和删除最小元素(元素值本身为优先级键值，小元素享有高优先级)。在插入或者删除操作之后，我们必须保持该实现应有的性质: 1. 完全二叉树 2. 每个节点值都小于或等于它的子节点。

在插入操作的时候，会破坏上述堆的性质，所以需要进行名为percolate_up的操作，以进行恢复。新插入的节点new放在完全二叉树最后的位置，再和父节点比较。如果new节点比父节点小，那么交换两者。交换之后，继续和新的父节点比较…… 直到new节点不比父节点小，或者new节点成为根节点。这样得到的树，就恢复了堆的性质。

我们插入节点2:

插入

删除操作只能删除根节点。根节点删除后，我们会有两个子树，我们需要基于它们重构堆。进行percolate_down的操作: 让最后一个节点last成为新的节点，从而构成一个新的二叉树。再将last节点不断的和子节点比较。如果last节点比两个子节点中小的那一个大，则和该子节点交换。直到last节点不大于任一子节点都小，或者last节点成为叶节点。

删除根节点1。如图:

删除根节点

下面是代码。与我们在二叉搜索树中使用表不同，我们这里使用数组来表示完全二叉树。数组下标为0的元素不用于储存节点，而用于记录完全二叉树中元素的总数。

/* By Vamei 
   Use an big array to implement heap
   DECLARE: int heap[MAXSIZE] in calling function
   heap[0] : total nodes in the heap
   for a node i, its children are i*2 and i*2+1 (if exists)
   its parent is i/2  */

void insert(int new, int heap[]) 
{
    int childIdx, parentIdx;
    heap[0] = heap[0] + 1;
    heap[heap[0]] = new;
    
    /* recover heap property */
    percolate_up(heap);
}

static void percolate_up(int heap[]) {
    int lightIdx, parentIdx;
    lightIdx  = heap[0];
    parentIdx = lightIdx/2;
    /* lightIdx is root? && swap? */
    while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {
        /* swap */
        swap(heap + lightIdx, heap + parentIdx); 
        lightIdx  = parentIdx;
        parentIdx = lightIdx/2;
    }
}


int delete_min(int heap[]) 
{
    int min;
    if (heap[0] < 1) {
        /* delete element from an empty heap */
        printf("Error: delete_min from an empty heap.");
        exit(1);
    }

    /* delete root 
       move the last leaf to the root */
    min = heap[1];
    swap(heap + 1, heap + heap[0]);
    heap[0] -= 1;

    /* recover heap property */
    percolate_down(heap);
 
    return min;
}

static void percolate_down(int heap[]) {
    int heavyIdx;
    int childIdx1, childIdx2, minIdx;
    int sign; /* state variable, 1: swap; 0: no swap */

    heavyIdx = 1;
    do {
        sign     = 0;
        childIdx1 = heavyIdx*2;
        childIdx2 = childIdx1 + 1;
        if (childIdx1 > heap[0]) {
            /* both children are null */
            break; 
        }
        else if (childIdx2 > heap[0]) {
            /* right children is null */
            minIdx = childIdx1;
        }
        else {
            minIdx = (heap[childIdx1] < heap[childIdx2]) ?
                          childIdx1 : childIdx2;
        }

        if (heap[heavyIdx] > heap[minIdx]) {
            /* swap with child */
            swap(heap + heavyIdx, heap + minIdx);
            heavyIdx = minIdx;
            sign = 1;
        }
    } while(sign == 1);
}

你可以尝试一下构建自己的main函数，测试相关的操作。

总结

堆，优先级

插入元素，删除最大优先级元素

哈希表 (hash table)

HASH

哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系，而且集合A的某个元素只能对应集合B中的一个元素。但反过来，集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素，这样的映射被称为一一映射。这样的对应关系在现实生活中很常见，比如：

A  -> B

人 -> 身份证号

日期 -> 星座

上面两个映射中，人 -> 身份证号是一一映射的关系。在哈希表中，上述对应过程称为hashing。A中元素a对应B中元素b，a被称为键值(key)，b被称为a的hash值(hash value)。

 韦小宝的hash值

映射在数学上相当于一个函数f(x):A->B。比如 f(x) = 3x + 2。哈希表的核心是一个哈希函数(hash function)，这个函数规定了集合A中的元素如何对应到集合B中的元素。比如：

A: 三位整数    hash(x) = x % 10    B: 一位整数

104                               4

876                               6

192                               2

上述对应中，哈希函数表示为hash(x) = x % 10。也就是说，给一个三位数，我们取它的最后一位作为该三位数的hash值。

哈希表在计算机科学中应用广泛。比如：

Ethernet中的FCS：参看小喇叭开始广播 (以太网与WiFi协议)

IP协议中的checksum：参看我尽力 (IP协议详解)

git中的hash值：参看版本管理三国志

上述应用中，我们用一个hash值来代表键值。比如在git中，文件内容为键值，并用SHA算法作为hash function，将文件内容对应为固定长度的字符串(hash值)。如果文件内容发生变化，那么所对应的字符串就会发生变化。git通过比较较短的hash值，就可以知道文件内容是否发生变动。

再比如计算机的登陆密码，一般是一串字符。然而，为了安全起见，计算机不会直接保存该字符串，而是保存该字符串的hash值(使用MD5、SHA或者其他算法作为hash函数)。当用户下次登陆的时候，输入密码字符串。如果该密码字符串的hash值与保存的hash值一致，那么就认为用户输入了正确的密码。这样，就算黑客闯入了数据库中的密码记录，他能看到的也只是密码的hash值。上面所使用的hash函数有很好的单向性：很难从hash值去推测键值。因此，黑客无法获知用户的密码。

(之前有报道多家网站用户密码泄露的时间，就是因为这些网站存储明文密码，而不是hash值，见多家网站卷入CSDN泄密事件 明文密码成争议焦点)

注意，hash只要求从A到B的对应为一个映射，它并没有限定该对应关系为一一映射。因此会有这样的可能：两个不同的键值对应同一个hash值。这种情况叫做hash碰撞(hash collision)。比如网络协议中的checksum就可能出现这种状况，即所要校验的内容与原文并不同，但与原文生成的checksum(hash值)相同。再比如，MD5算法常用来计算密码的hash值。已经有实验表明，MD5算法有可能发生碰撞，也就是不同的明文密码生成相同的hash值，这将给系统带来很大的安全漏洞。(参考hash collision）

HASH与搜索

hash表被广泛的用于搜索。设定集合A为搜索对象，集合B为存储位置，利用hash函数将搜索对象与存储位置对应起来。这样，我们就可以通过一次hash，将对象所在位置找到。一种常见的情形是，将集合B设定在数组下标。由于数组可以根据数组下标进行随机存取(random access，算法复杂度为1)，所以搜索操作将取决于hash函数的复杂程度。

比如我们以人名(字符串)为键值，以数组下标为hash值。每个数组元素中存储有一个指针，指向记录 (有人名和电话号码)。

下面是一个简单的hash函数:

#define HASHSIZE 1007
/* By Vamei
 * hash function
 */int hash(char *p)
{
    int value=0;
    while((*p) != '\0') {
       value = value + (int) (*p); // convert char to int, and sum
       p++;
    }
    return (value % HASHSIZE); // won's exceed HASHSIZE}

hash value of "Vamei": 498

hash value of "Obama": 480

我们可以建立一个HASHSIZE大小的数组records，用于储存记录。HASHSIZE被选择为质数，以便hash值能更加均匀的分布。在搜索"Vamei"的记录时，可以经过hash，得到hash值498，再直接读取records[498]，就可以读取记录了。

(666666是Obama的电话号码，111111是Vamei的电话号码。纯属杜撰，请勿当真)

hash搜索

如果不采用hash，而只是在一个数组中搜索的话，我们需要依次访问每个记录，直到找到目标记录，算法复杂度为n。我们可以考虑一下为什么会有这样的差别。数组虽然可以随机读取，但数组下标是随机的，它与元素值没有任何关系，所以我们要逐次访问各个元素。通过hash函数，我们限定了每个下标位置可能存储的元素。这样，我们利用键值和hash函数，就可以具备相当的先验知识，来选择适当的下标进行搜索。在没有hash碰撞的前提下，我们只需要选择一次，就可以保证该下标指向的元素是我们想要的元素。

冲突

hash函数需要解决hash冲突的问题。比如，上面的hash函数中，"Obama"和"Oaamb"有相同的hash值，发生冲突。我们如何解决呢？

一个方案是将发生冲突的记录用链表储存起来，让hash值指向该链表，这叫做open hashing:

open hashing

我们在搜索的时候，先根据hash值找到链表，再根据key值遍历搜索链表，直到找到记录。我们可以用其他数据结构代替链表。

open hashing需要使用指针。我们有时候想要避免使用指针，以保持随机存储的优势，所以采用closed hashing的方式来解决冲突。

closed hashing

这种情况下，我们将记录放入数组。当有冲突出现的时候，我们将冲突记录放在数组中依然闲置的位置，比如图中Obama被插入后，随后的Oaamb也被hash到480位置。但由于480被占据，Oaamb探测到下一个闲置位置(通过将hash值加1)，并记录。

closed hashing的关键在如何探测下一个位置。上面是将hash值加1。但也可以有其它的方式。概括的说，在第i次的时候，我们应该探测POSITION(i)=(h(x) + f(i)) % HASHSIZE的位置。上面将hash值加1的方式，就相当于设定f(i) = 1。当我们在搜索的时候，就可以利用POSITION(i)，依次探测记录可能出现的位置，直到找到记录。

(f(i)的选择会带来不同的结果，这里不再深入)

如果数组比较满，那么closed hashing需要进行许多次探测才能找到空位。这样将大大减小插入和搜索的效率。这种情况下，需要增大HASHSIZE，并将原来的记录放入到新的比较大的数组中。这样的操作称为rehashing。

总结

hash表，搜索

hash冲突, open hashing, closed hashing

 图 (graph)

图(graph)是一种比较松散的数据结构。它有一些节点(vertice)，在某些节点之间，由边(edge)相连。节点的概念在树中也出现过，我们通常在节点中储存数据。边表示两个节点之间的存在关系。在树中，我们用边来表示子节点和父节点的归属关系。树是一种特殊的图，但限制性更强一些。

这样的一种数据结构是很常见的。比如计算机网络，就是由许多节点(计算机或者路由器)以及节点之间的边(网线)构成的。城市的道路系统，也是由节点(路口)和边(道路)构成的图。地铁系统也可以理解为图，地铁站可以认为是节点。基于图有许多经典的算法，比如求图中两个节点的最短路径，求最小伸展树等。

图的经典研究是柯尼斯堡七桥问题(Seven Bridges of Königsberg)。柯尼斯堡是现今的加里宁格勒，城市中有一条河流过，河中有两个小岛。有七座桥桥连接河的两岸和两个小岛。送信员总想知道，有没有一个办法，能不重复的走过7个桥呢？

(这个问题在许多奥数教材中称为"一笔画"问题)

欧拉时代的柯尼斯堡地图

柯尼斯堡的可以看作由7个边和4个节点构成的一个图:

这个问题最终被欧拉巧妙的解决。七桥问题也启发了一门新的数学学科——图论(graph theory)的诞生。欧拉的基本思路是，如果某个节点不是起点或者终点，那么连接它的边的数目必须为偶数个(从一个桥进入，再从另一个桥离开)。对于柯尼斯堡的七桥，由于4个节点都为奇数个桥，而最多只能有两个节点为起点和终点，所以不可能一次走完。

图的定义

严格的说，图G=(V,E)$G=(V,E)$是由节点的集合V和边的集合E构成的。一个图的所有节点构成一个集合V$V$。一个边可以表示为(v1,v2)$(v_1,v_2)$，其中v1,v2∈V$v_1,v_2\in V$，即两个节点。如果(v1,v2)$(v_1,v_2)$有序，即(v1,v2)$(v_1,v_2)$与(v2,v1)$(v_2,v_1)$不同，那么图是有向的(directed)。有序的边可以理解为单行道，只能沿一个方向行进。如果(v1,v2)$(v_1,v_2)$无序，那么图是无向的(undirected)。无序的边可以理解成双向都可以行进的道路。一个无序的边可以看作连接相同节点的两个反向的有序边，所以无向图可以理解为有向图的一种特殊情况。

(七桥问题中的图是无向的。城市中的公交线路可以是无向的，比如存在单向环线)

图的一个路径(path)是图的一系列节点w1,w2,...,wn$w_1,w_2,...,w_n$，且对于1≤i<n$1\le i<n$，有(wi,wi+1)∈E$(w_i,w_{i+1})\in E$。也就是说，路径是一系列的边连接而成，路径的两端为两个节点。路径上边的总数称为路径的长度。乘坐地铁时，我们会在选择某个路径，来从A站到达B站。这样的路径可能有不止一条，我们往往会根据路径的长度以及沿线的拥挤状况，来选择一条最佳的路线。如果存在一条长度大于0的路径，该路径的两端为同一节点，那么认为该图中存在环路(cycle)。很明显，上海的地铁系统中存在环路。

找到一条环路

如果从每个节点，到任意一个其它的节点，都有一条路径的话，那么图是连通的(connected)。对于一个有向图来说，这样的连通称为强连通(strongly connected)。如果一个有向图不满足强连通的条件，但将它的所有边都改为双向的，此时的无向图是连通的，那么认为该有向图是弱连通(weakly connected)。

如果将有火车站的城市认为是节点，铁路是连接城市的边，这样的图可能是不连通的。比如北京和费城，北京有铁路通往上海，费城有铁路通往纽约，但北京和费城之间没有路径相连。

图的实现

一种简单的实现图的方法是使用二维数组。让数组a的每一行为一个节点，该行的不同元素表示该节点与其他节点的连接关系。如果(u,v)∈E$(u,v)\in E$，那么a[u][v]记为1，否则为0。比如下面的一个包含三个节点的图:

可以简单表示为

这种实现方式所占据的空间为O(|V|2)$O(|V{|}^2)$，|V|$|V|$为节点总数。所需内存随着节点增加而迅速增多。如果边不是很密集，那么很多数组元素记为0，只有稀疏的一些数组元素记为1，所以并不是很经济。

更经济的实现方式是使用邻接表(adjacency list)，即记录每个节点所有的相邻节点。对于节点m，我们建立一个链表。对于任意节点k，如果有(m,k)∈E$(m,k)\in E$，就将该节点放入到对应节点m的链表中。邻接表是实现图的标准方式。比如下面的图，

可以用如下的数据结构实现：

左侧为一个数组，每个数组元素代表一个节点，且指向一个链表。该链表包含有该数组元素所有的相邻元素。

总体上看，邻接表可以分为两部分。邻接表所占据的总空间为O(|V|+|E|)$O(|V|+|E|)$。数组部分储存节点信息，占据|V|$|V|$)的空间，即节点的总数。链表存储边的信息，占据|E|$|E|$的空间，即边的总数。在一些复杂的问题中，定点和边还可能有其他的附加信息，我们可以将这些附加信息储存在相应的节点或者边的位置。

下面为具体的C代码:

/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 5

typedef struct node *position;

/* node */
struct node {
    int element;
    position next;
};

/* 
 * operations (stereotype)
 */
void insert_edge(position, int, int);
void print_graph(position graph, int nv);

/* for testing purpose */
void main()
{
    struct node graph[NUM_V];
    int i;

    // initialize the vertices
    for(i=1; i<NUM_V; i++) {
        (graph+i)->element = i;
        (graph+i)->next    = NULL;
    }

    // insert edges
    insert_edge(graph,1,2);
    insert_edge(graph,1,4);
    insert_edge(graph,3,2);
    insert_edge(graph,4,2);
    insert_edge(graph,4,3);

    print_graph(graph,NUM_V);
}

/* print the graph */
void print_graph(position graph, int nv) {
    int i;
    position p;
    for(i=1; i<nv; i++) {
        p = (graph + i)->next;
        printf("From %3d: ", i);
        while(p != NULL) {
            printf("%d->%d; ", i, p->element);
            p = p->next;
        }
        printf("\n");
    }
}

/*
 * insert an edge
 */
void insert_edge(position graph,int from, int to)
{
    position np;
    position nodeAddr;

    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = to;
    nodeAddr->next    = np->next;
    np->next = nodeAddr;
}

运行结果:

From   1: 1->4; 1->2; 
From   2: 
From   3: 3->2; 
From   4: 4->3; 4->2;

上面的实现主要基于链表，可参考纸上谈兵: 表 (list) 。

总结

图是一种很简单的数据结构。图的组织方式比较松散，自由度比较大，但也造成比较高的算法复杂度。我将在以后介绍一些图的经典算法。

 拓扑排序

《文明》是一款风靡20多年的回合制策略游戏，由Sid Meier开发。《文明》结构宏大，内容丰富，玩法多样，游戏性强，称得上是历史上最伟大的游戏。在文明中，你可以选择某个文明的，从部落开始发展，在接下来的几千年的历史中，发展科技、开荒拓野、发动战争等等。游戏在保持自由度的前提下，对各个社会文明的发展顺序有很好的仿真性，让玩家仿佛置身于历史长河，坐观文明的起落。美国的一些大学的历史系甚至于使用该游戏作为教学工具。

(作为《文明》的忠实爱好者，多少个昼夜耗费在一张张地图上啊。好吧，是为了学习历史。)

“科技树”

《文明》中的科技树

游戏有一个“科技树”系统，即你可以按照该图所示的顺序来发展科技。“科技树”是这样一个概念: 为了研发某个科技，我们必须已经掌握了该科技的所有前提科技(prerequisite)。科技树中有一些箭头，从A科技指向B科技，那么A就是B的前提科技。比如，根据上面的科技树，为了研发物理(Physics)，我们必须已经掌握了化学(Chemistry)和天文学(Astronomy)。而为了研发化学(Chemistry)，我们又必须掌握了火药(Gunpowder)。如果一个科技没有其它科技指向，那么就不需要任何前提科技就可以研发，比如图中的封建主义(Feudalism)。如果同一时间只能研发一项科技，那么玩家的科技研发就是一个序列，比如封建主义，工程(Engineering)，发明(Invention)，火药，一神教(monotheism)，骑士制度(Chivalry)…… 有些序列是不合法的，比如工程，发明，火药……，在研发的“发明”时，并没有满足“封建主义”的前提条件。

一个有趣的问题是，如何找到合法的序列呢？当我们在设计计算机玩家时，很可能需要解决这样一个问题。

图(graph)中的拓扑排序算法(Topological Sort)可以给出一个合法序列。虽然在游戏中被称为“科技树”，但“科技树”并不符合数据结构中的树结构。在数据结构中，树的每个节点只能由一个父节点，整个树只有一个根节点。因此，“科技树”是一个不折不扣的图结构。此外，该树是一个有向的无环(acyclic)图。图中不存在环 (cycle, 环是一个长度大于0的路径，其两端为同一节点)。

拓扑排序

拓扑排序利用了一个事实，即在一个无环网络中，有一些节点是没有箭头指入的，比如科技树中的一神教、封建主义、工程。它们可以作为序列的起点。

• 选择没有箭头指入的节点中的任一个，可以作为合法序列的起点，放入序列。

• 当我们将某个节点放入序列后，去掉该节点以及从该节点指出的所有箭头。在新的图中，选择没有箭头指向的节点，作为序列中的下一个点。

• 重复上面的过程，直到所有的节点都被放入序列。

对于每个节点，我们可以使用一个量入度(indegree)，用来表示有多少个箭头指入该节点。当某个节点被删除时，图发生变化，我们需要更新图中节点的入度。

为了方便，我将“科技树”中的节点编号，为了符合C语言中的传统，编号从0开始。下面是对应关系:

我们根据编号，绘制上述图(graph)。我同时用三种颜色，来表示不同点的入度(indegree):

我们使用邻接表的数据结构(参考纸上谈兵: 图)，来实现图。构建代码如下:

/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 22

typedef struct node *position;

/* node */
struct node {
    int element;
    position next;
};

/* 
 * operations (stereotype)
 */
void insert_edge(position, int, int);
void print_graph(position graph, int nv);

/* for testing purpose */
void main()
{
    struct node graph[NUM_V];
    int i;

    // initialize the vertices
    for(i=0; i<NUM_V; i++) {
        (graph+i)->element = i;
        (graph+i)->next    = NULL;
    }

    // insert edges
    insert_edge(graph,0,1);
    insert_edge(graph,0,5);
    insert_edge(graph,1,2);
    insert_edge(graph,1,10);
    insert_edge(graph,2,3);
    insert_edge(graph,3,4);
    insert_edge(graph,7,8);
    insert_edge(graph,9,5);
    insert_edge(graph,9,15);
    insert_edge(graph,10,6);
    insert_edge(graph,10,7);
    insert_edge(graph,10,11);
    insert_edge(graph,11,12);
    insert_edge(graph,11,13);
    insert_edge(graph,13,14);
    insert_edge(graph,13,18);
    insert_edge(graph,15,16);
    insert_edge(graph,16,17);
    insert_edge(graph,17,13);
    insert_edge(graph,17,20);
    insert_edge(graph,19,15);
    insert_edge(graph,20,21);

    print_graph(graph,NUM_V);
}

/* print the graph */
void print_graph(position graph, int nv) {
    int i;
    position p;
    for(i=0; i<nv; i++) {
        p = (graph + i)->next;
        printf("From %3d: ", i);
        while(p != NULL) {
            printf("%d->%d; ", i, p->element);
            p = p->next;
        }
        printf("\n");
    }
}

/*
 * insert an edge
 */
void insert_edge(position graph,int from, int to)
{
    position np;
    position nodeAddr;

    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = to;
    nodeAddr->next    = np->next;
    np->next = nodeAddr;
}

我们可以根据上面建立的图，来获得各个节点的入度。使用一个数组indeg来储存各个节点的入度，即indeg[i] = indgree of i_th node。下面的init_indeg()用于初始化各节点的入度:

// according to the graph, initialize the indegree at each vertice
void init_indeg(position graph, int nv, int indeg[]) {
    int i;
    position p;

    // initialize
    for(i=0; i<nv; i++) {
        indeg[i] = 0;
    }

    // assimilate the graph
    for(i=0; i<nv; i++) {
        p = (graph + i)->next;
        while(p != NULL) {
            (indeg[p->element])++;
            p = p->next;
        }
    }   
}

正如我们之前叙述的，我们需要找到入度为0的节点，并将这些节点放入序列。find_next()就是用于寻找下一个入度为0的节点。找到对应节点后，返回该节点，并将该节点的入度更新为-1:

/* find the vertice with 0 indegree*/
int find_next(int indeg[], int nv) {
    int next;
    int i;
    for(i=0; i<nv; i++) {
        if(indeg[i] == 0) break;
    }
    indeg[i] = -1;

    return i;
}

当我们取出一个节点放入序列时，从该节点出发，指向的节点的入度会减1，我们用update_indeg()表示该操作:

// update indeg when ver is removed
void update_indeg(position graph, int nv, int indeg[], int ver) {
    position p;
    p = (graph + ver)->next;
    while(p != NULL) {
        (indeg[p->element])--;
        p = p->next;
    }
}

有了上面的准备，我们可以寻找序列。使用数组seq来记录序列中的节点。下面的get_seq()用于获得拓扑排序序列:

// return the sequence
void get_seq(position graph, int nv, int indeg[], int seq[]){
    int i;
    int ver;
    for(i = 0; i<nv; i++) {
        ver = find_next(indeg, nv);
        seq[i] = ver;
        update_indeg(graph, nv, indeg, ver);
    }
}

综合上面的叙述，我们可以使用下面代码，来实现拓扑排序:

/* By Vamei */

#include <stdio.h>

#include <stdlib.h>

#define NUM_V 22

typedef struct node *position;

/* node */

struct node {

    int element;

    position next;

};

/* 

 * operations (stereotype)

 */

void insert_edge(position, int, int);

void print_graph(position, int);

void init_indeg(position, int , int *);

void update_indeg(position, int, int *, int);

void get_seq(position, int, int *, int *);

int find_next(int *, int);

/* for testing purpose */

void main()

{

    struct node graph[NUM_V];

    int indeg[NUM_V];

    int seq[NUM_V];

    int i;

    

    // initialize the graph

    for(i=0; i<NUM_V; i++) {

        (graph+i)->element = i; 

        (graph+i)->next    = NULL;

    }

    

    insert_edge(graph,0,1);

    insert_edge(graph,0,5);

    insert_edge(graph,1,2);

    insert_edge(graph,1,10);

    insert_edge(graph,2,3);

    insert_edge(graph,3,4);

    insert_edge(graph,7,8);

    insert_edge(graph,9,5);

    insert_edge(graph,9,15);

    insert_edge(graph,10,6);

    insert_edge(graph,10,7);

    insert_edge(graph,10,11);

    insert_edge(graph,11,12);

    insert_edge(graph,11,13);

    insert_edge(graph,13,14);

    insert_edge(graph,13,18);

    insert_edge(graph,15,16);

    insert_edge(graph,16,17);

    insert_edge(graph,17,13);

    insert_edge(graph,17,20);

    insert_edge(graph,19,15);

    insert_edge(graph,20,21);

    print_graph(graph,NUM_V);

    

    init_indeg(graph,NUM_V,indeg);

    get_seq(graph, NUM_V, indeg, seq);

    for (i=0; i<NUM_V; i++) {

        printf("%d,", seq[i]);

    }

}

void print_graph(position graph, int nv) {

    int i;

    position p;

    for(i=0; i<nv; i++) {

        p = (graph + i)->next;

    printf("From %3d: ", i);

    while(p != NULL) {

        printf("%d->%d; ", i, p->element);

        p = p->next;

    }

    printf("\n");

    }

}

/*

 * insert an edge

 */

void insert_edge(position graph,int from, int to) 

{

    position np;

    position nodeAddr;

    

    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));

    nodeAddr->element = to;

    nodeAddr->next    = np->next;

    np->next = nodeAddr;    

}

void init_indeg(position graph, int nv, int indeg[]) {

    int i;

    position p;

    // initialize

    for(i=0; i<nv; i++) {

        indeg[i] = 0;

    }

    // update

    for(i=0; i<nv; i++) {

        p = (graph + i)->next;

        while(p != NULL) {

            (indeg[p->element])++;

            p = p->next;

        }

    }  

}

// update indeg when ver is removed

void update_indeg(position graph, int nv, int indeg[], int ver) {

    position p;

    p = (graph + ver)->next;

    while(p != NULL) {

        (indeg[p->element])--;

        p = p->next;

    }

}

/* find the vertice with 0 indegree*/

int find_next(int indeg[], int nv) {

    int next;

    int i;

    for(i=0; i<nv; i++) {

        if(indeg[i] == 0) break;

    }

    indeg[i] = -1;

    return i;

}

// return the sequence

void get_seq(position graph, int nv, int indeg[], int seq[]){

    int i;

    int ver;

    for(i = 0; i<nv; i++) {

        ver = find_next(indeg, nv);

        seq[i] = ver;

        update_indeg(graph, nv, indeg, ver);

    }

}

上面算法中有一个遍历所有节点的for循环，而循环中的find_next()函数也会遍历所有的节点。因此，算法复杂度为O(|V|2)$O(|V{|}^2)$。

在find_next()中，我们将放入序列的节点入度记为-1。find_next()每次会遍历所有的节点，没有必要遍历入度为-1的节点。为了改善算法复杂度，我们可以使用一个队列(或者栈)来记录入度为0的元素。我们每次从队列中取出一个元素放入拓扑序列，并更新相邻元素的入度。如果该元素的相邻元素的入度变为0，那么将它们放入队列中。可以证明，这样的改造后，算法复杂度为O(|V|+|E|)$O(|V|+|E|)$

问题拓展

通过上面的算法，我们可以获得一个合法的科技发展序列。我随后想到一个问题，如何输出所有的科技发展序列呢？

这个问题的关键在于，某个时刻，可能同时有多个节点的入度同时为0。它们中的任何一个都可以成为下一个元素。为此，我们需要记录所有的可能性。

(我想到的，是复制入度数组和序列数组，以储存不同的可能性。不知道大家有什么更好的想法呢？)

总结

图，拓扑排序

最短路径与贪婪

图是由节点和连接节点的边构成的。节点之间可以由路径，即边的序列。根据路径，可以从一点到达另一点。在一个复杂的图中，图中两点可以存在许多路径。最短路径讨论了一个非常简单的图论问题，图中从A点到B点 ，那条路径耗费最短？

这个问题又异常复杂，因为网络的构成状况可能很复杂。

一个最简单的思路，是找出所有可能的从A到B的路径，再通过比较，来寻找最短路径。然而，这并没有将问题简化多少。因为搜索从A到B的路径，这本身就是很复杂的事情。而我们在搜索所有路径的过程中，有许多路径已经绕了很远，完全没有搜索的必要。比如从上海到纽约的路线，完全没有必要先从上海飞到南极，再从南极飞到纽约，尽管这一路径也是一条可行的路径。

所以，我们需要这样一个算法：它可以搜索路径，并当已知路径包括最短路径时，即停止搜索。我们先以无权网络为例，看一个可行的最短路径算法。

无权网络

无权网络(unweighted network)是相对于加权网络的，这里的“权”是权重。每条边的耗费相同，都为1。路径的总耗费即为路径上边的总数。

我们用“甩鞭子”的方式，来寻找最短路径。鞭子的长度代表路径的距离。

手拿一个特定长度的鞭子，站在A点。甩出鞭子，能打到一些点。比如C和D。

将鞭子的长度增加1。再甩出鞭子。此时，从C或D出发，寻找距离为1的邻接点，即E和F。这些点到A点的距离，为此时鞭子的长度。

记录点E和F，并记录它们的上游节点。比如E(C)， F(D)。我们同样可以记录此时该点到A的距离，比如5。

如果要记录节点E时，发现它已经出现在之前的记录中，这说明曾经有更短的距离到E。此时，不将E放入记录中。毕竟，我们感兴趣的是最短路径。如下图中的E：

黄色的E不被记录

最初的鞭子长度为0，站在A点，只能打到A点自身。当我们不断增加鞭子长度，第一次可以打到B时，那么此时鞭子的长度，就是从A到B的最短距离。循着我们的记录，倒推上游的节点，就可以找出整个最短路径。

我们的记录本是个很有意思的东西。某个点放入记录时，此时的距离，都是A点到该点的最短路径。根据记录，我们可以反推出记录中任何一点的最短路径。这就好像真诚对待每个人。这能保证，当你遇到真爱时，你已经是在真诚相待了。实际上，记录将所有节点分割成两个世界：记录内的，已知最短距离的；记录外的，未知的。

加权网络

在加权网络中(weighted network)，每条边有各自的权重。当我们选择某个路径时，总耗费为路径上所有边的权重之和。

加权网络在生活中很常见，比如从北京到上海，可以坐火车，也可以坐飞机。但两种选择耗费的时间并不同。再比如，我们打出租车和坐公交车，都可以到市区，但车资也有所不同。在计算机网络中，由于硬件性能不同，连接的传输速度也有所差异。加权网络正适用于以上场景。无权网络是加权网络的一个特例。

这个问题看起来和无权网络颇为类似。但如果套用上面的方法，我们会发现，记录中的节点并不一定是最短距离。我们看下面的例子：

很明显，最短路径是A->C->D->B，因为它的总耗费只有4。按照上面的方法，我们先将A放入记录。从A出发，有B和C两个如果将B和C同时放入记录，那么记录中的B并不符合最短距离的要求。

那么，为什么无权网络可行呢？假设某次记录时，鞭子长度为5，那么这次记录点的邻接点，必然是距离为6的点。如果这些邻接点没有出现过，那么6就是它们的最短距离。所有第一次出现的邻接点，都将加入到下次的记录中。比如下面的例子，C/D/E是到达A的邻接点，它们到A的最短距离必然都是1。

对于加权网络来说，即使知道了邻接点，也无法判断它们是否符合最短距离。在记录C/D/E时，我们无法判断未来是否存在如下图虚线的连接，导致A的邻接点E并不是下一步的最短距离点：

但情况并没有我们想的那么糟糕。仔细观察，我们发现，虽然无法一次判定所有的邻接点为下一步的最短距离点，但我们可以确定点C已经处在从A出发的最短距离状态。A到C的其它可能性，比如途径D和E，必然导致更大的成本。

也就是说，邻接点中，有一个达到了最短距离点，即邻接点中，到达A距离最短的点，比如上面的C。我们可以安全的把C改为已知点。A和C都是已知点，点P成为新的邻接点。P到A得距离为4。

出于上面的观察，我们可以将节点分为三种：

• 已知点：已知到达A最短距离的点。“我是成功人士。”

• 邻接点：有从记录点出发的边，直接相邻的点。“和成功人士接触，也有成功的机会哦。”

• 未知点：“还早得很。”

最初的已知点只有A。已知点的直接下游节点为邻接点。对于邻接点，我们需要独立的记录它们。我们要记录的有：

• 当前情况下，从A点出发到达该邻接点的最短距离。比如对于上面的点D，为6。

• 此最短距离下的上游节点。对于上面的点D来说，为A。

每次，我们将邻接点中最短距离最小的点X转为已知点，并将该点的直接下游节点，改为邻接点。我们需要计算从A出发，经由X，到达这些新增邻接点的距离：新距离 = X最短距离 + QX边的权重。此时有两种情况，

• 如果下游节点Q还不是邻接点，那么直接加入，Q最短距离 = 新距离，Q上游节点为X。

• 如果下游节点Q已经是邻接点，记录在册的上游节点为Y，最短距离为y。如果新距离小于y，那么最小距离改为新距离，上游节点也改为X。否则保持原记录不变。

我们还用上面的图，探索A到E的路径：

第一步

第二步

第二步

第三步

最后，E成为已知。倒退，可以知道路径为E, P, C, A。正过来，就是从A到E的最短路径了。

上面的算法是经典的Dijkstra算法。本质上，每个邻接点记录的，是基于已知点的情况下，最好的选择，也就是所谓的“贪婪算法”(greedy algorithm)。当我们贪婪时，我们的决定是临时的，并没有做出最终的决定。转换某个点成为已知点后，我们增加了新的可能性，贪婪再次起作用。根据对比。随后，某个邻接点成为新的“贪无可贪”的点，即经由其它任意邻接点，到达该点都只会造成更高的成本； 经由未知点到达该点更不可能，因为未知点还没有开放，必然需要经过现有的邻接点到达，只会更加绕远。好吧，该点再也没有贪婪的动力，就被扔到“成功人士”里，成为已知点。成功学不断传染，最后感染到目标节点B，我们就找到了B的最短路径。

实现

理解了上面的原理，算法的实现是小菜一碟。我们借用图 (graph)中的数据结构，略微修改，构建加权图。

我们将上面的表格做成数组records，用于记录路径探索的信息。

重新给点A,C,D,E,P命名，为0, 1, 2, 3, 4。

代码如下：

/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 5
#define INFINITY 10000

typedef struct node *position;
typedef struct record *label;

/* node */
struct node {
    int element;
    position next;
    int weight;
};

/* table element, keep record */
struct record {
    int status;
    int distance;
    int previous;
};

/* 
 * operations (stereotype)
 */
void insert_edge(position, int, int, int);
void print_graph(position, int);
int new_neighbors(position, label, int, int);
void shortest_path(position, label, int, int, int);

/* for testing purpose */
void main()
{
    struct node graph[NUM_V];
    struct record records[NUM_V];
    int i;

    // initialize the vertices
    for(i=0; i<NUM_V; i++) {
        (graph+i)->element = i;
        (graph+i)->next    = NULL;
        (graph+i)->weight  = -1;
    }

    // insert edges
    insert_edge(graph,0,1,1);
    insert_edge(graph,0,2,6);
    insert_edge(graph,0,3,9);
    insert_edge(graph,1,4,3);
    insert_edge(graph,4,3,3);

    print_graph(graph,NUM_V);
    
    // initialize the book
    for (i=0; i<NUM_V; i++){
        (records+i)->status   = -1;
        (records+i)->distance = INFINITY;
        (records+i)->previous = -1;
    }
    
    shortest_path(graph, records, NUM_V, 0, 3);
    
    // 
}
void shortest_path(position graph, label records, int nv, int start, int end) {
    int current;
    
    (records+start)->status   = 1;
    (records+start)->distance = 0;
    (records+start)->previous = 0;
    
    current = start;
    while(current != end) {
        current = new_neighbors(graph, records, nv, current);
    }
    
    while(current != start) {
        printf("%d <- ", current);
        current = (records+current)->previous;
    }
    printf("%d\n", current);
}

int new_neighbors(position graph, label records, int nv, int current) {
    int newDist;
    int v;
    int i;
    int d;
    
    position p;
    
    // update the current known
    (records + current)->status = 1;
    
    // UPDATE new neighbors
    p = (graph+current)->next;
    while(p != NULL) {
        v = p->element;
        (records + v)->status = 0;
        newDist = p->weight + (records + current)->distance;
        if ((records + v)->distance > newDist) {
            (records + v)->distance = newDist;
            (records + v)->previous = current;
        }
        p = p->next;
    }
    
    // find the next known
    d = INFINITY;
    for (i=0; i<nv; i++) {
        if ((records + i)->status==0 && (records + i)->distance < d){
            d = (records + i)->distance;
            v = i;
        }
    }
    return v;
}

/* print the graph */
void print_graph(position graph, int nv) {
    int i;
    position p;
    for(i=0; i<nv; i++) {
        p = (graph + i)->next;
        printf("From %3d: ", i);
        while(p != NULL) {
            printf("%d->%d; w:%d ", i, p->element, p->weight);
            p = p->next;
        }
        printf("\n");
    }
}

/*
 * insert an edge
 * with weight
 */
void insert_edge(position graph,int from, int to, int weight)
{
    position np;
    position nodeAddr;

    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = to;
    nodeAddr->next    = np->next;
    nodeAddr->weight  = weight;
    np->next = nodeAddr;
}

运行结果如下：

From   0: 0->3; w:9 0->2; w:6 0->1; w:1 

From   1: 1->4; w:3 

From   2: 

From   3: 

From   4: 4->3; w:3 

3 <- 4 <- 1 <- 0

即从0到1到4到3，也就是从A到C到P到E，是我们的最短路径。

上面的算法中，最坏情况是目标节点最后成为已知点，即要寻找O(|V|)$O(|V|)$。而每个已知点是通过寻找O(|V|)$O(|V|)$个节点的最小值得到的。最后，打印出最短的路径过程中，需要倒退，最多可能有O|E|$O|E|$，也就是说，算法复杂度为O(|V|2+|E|)$O(|V{|}^2+|E|)$。

上面的records为一个数组，用于记录路径探索信息。我们可以用一个优先队列来代替它，将已知的节点移除优先队列。这样可以达到更好的运算效率。

练习: 自行设计一个加权网络，寻找最短路径。

总结

最短路径是寻找最优解的算法。在复杂的网络中，简单的实现方式无法运行，必须求助于精心设计的算法，比如这里的Dijkstra算法。利用贪婪的思想，我们不断的优化结果，直到找到最优解。