每年、每月、每日、每时、每刻都要学习和积累。不要浪费一分一秒。

    博观而约取，厚积而薄发，这是一个由量变到质变的过程。

[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译

    递归在数学和计算科学中是一个基本概念。递归的简单定义：编程语言中调用自身的程序(就像数学中的递归函数是通过自身来定义的一样)。递归程序不能一直调用自己或是就远不终止(就像递归函数不能总是通过自身来定义，否则就里循环定义)。因此，第二个必不可少的成分是，当程序可以停止调用自己时，必须有一个终止条件(termination condition)(像数学中的函数不再通过自身定义时)。所有的实际计算都可用一个递归框架来表达。

    递归的研究与被称为树(tree)的递归定义结构的研究是相辅相成的。利用树不仅能帮助我们理解和分析递归程序，也能作为显式的数据结构。我们利用树来理解递归程序；利用递归来建立树；并且利用两者之间的基本关系(以及递归关系)来分析算法。在各种应用中，递归还能帮助我们开发优秀而高效的数据结构与算法。

-------------------------------------------------------

递归算法

     递归算法是通过解决一个或多个相同问题的较小实例来解决某个问题。在C语言中，应用递归函数实现递归算法。递归函数就是调用自身的函数。C语言中的递归函数对应于数学函数中的递归定义。

    我们还将会看到，递归程序总是可以转换成执行相同计算的非递归程序。反之，我们也可以不用循环而是通过递归来表达包含循环的所有计算。使用递归的原因是因为它能够以一种紧凑的形式表达复杂算法，而不降低其效率。递归实现的开销由系统中支持函数调用的机制产生，它使用内置下推栈等价的方式。尽管递归有如上优点，但我们以所会看到，很容易就会编写出一个简单但效率极其低下的递归函数，所以，务必当心避免在递归函数中使用难以控制的实现。

    从实际而言，根据数学归纳法，应该确保递归函数满足两个基本性质：

• 必须显式解决一个基本情形(basis case)；
• 每次递归调用都必须使用一个更小的参数值。

    这两点说得比较笼统——实际上是说，对于我们编写的每个递归函数，都必须能够进行有效的归纳证明。而且，这两点对于我们编制实现提供了有用的指导。

    理论上，我们可以用等价的递归程序替换任何for循环。与for循环相比，递归程序通常更自然地表达计算，所以我们应该充分利用支持递归的编程系统提供的机制。不过，我们必须要记住的是，其中存在一个潜在的开销。当我们执行递归程序时，一直在进行嵌套函数调用，直到不需要递归调用为止，然后返回。在大部分编程系统环境中，这类嵌套函数调用是通过等价的内置下推栈来实现的。递归深度是在计算过程中函数的最大嵌套深度。一般来说，嵌套深度取决于输入。在使用递归程序时，需要考虑的是，编程环境必须维持一个大小与递归深度成比例的下推栈。对于大型问题，栈所需的空间可能妨碍我们使用递归方案。

-------------------------------------------------------

分治

    许多递归程序使用了两个递归调用，每个调用作用于大约一半的输入。这种递归方案大概是算法设计中众所周知的分治(divide-and-conquer)范例的一个重要实例，它是许多极其重要算法的基础。

    以求数组a[0],...,a[N-1]里N个项中最大项为例进行说明。通过一次简单的数组遍历，就能轻松地完成这项任务，如下所示
    for (t=a[0], i=1; i<N; i++)
    if(a[i] > 5) t = a[i];

    下面我们给出同一个问题的递归分治解决方案，用它来说明分治的概念。这个函数将文件a[1],...,a[r]分解成a[1],...,a[m]和a[m+1],...,a[r](递归性地)求这两部分的最大元素，并返回其中的较大者，它就是整个文件的最大元素。假定Item是一个一级类型，它定义了>。如果文件大小为偶数，这两部分大小相等；如果文件大小为奇数，第一部分比第二部分多1个元素。
    Item max(Item a[], int l, int r)
    {
        Item u, v; int m = (l+r)/2;
        if(l==r) return a[l];
        u = max(a, l, m);
        v = ax(a, m+1, r);
        if(u > v) return u;
        else return v;
    }

-------------------------------------------------------

动态归划(dynamic programming)

    分治算法的本质特征是，它将问题分解成独立的子问题。当子问题不独立，解就更复杂，主要是因为即使这类最简单算法的直接实现也可能需要难以想象的大量时间。

    例如，下面是斐波纳契数递推式的直接递归实现。
    int F(int i)
    {
        if(i < 1) return 0;
        if(i == 1) return 1;
        return F(i-1) + F(i-2);
    }

    注意：不要使用这个程序，它的背效率极其低下。实际上，计算F(N)的递归调用次数正好等于F(N+1)。但F(N)约等于φ^N，其中φ=1.618为黄金分割率。这个程序虽然紧凑而且优雅，但是因为它药费指数时间来计算F(N)，所以不实用。计算F(N+1)的时间是计算F(N)，的时间的φ倍。

    相比之下，通过计算头N个斐波纳契数并保存在一个数组中，就容易以线性时间来计算F(N)(与N成比例)：
    F[0] = 0; F[1] = 1;
    for (i=2; i<=N; i++)
    F[i] = F[i-1] + F[i-2];

    这个数成指数变化，所以数组不大——例如，F(45)=1836311903是可以由32位整数表示的最大斐波纳契数，一个大小为46的数组就可以满足要求。

    递推是一种整数值的递归函数。我们得到这样的结论：通过计算按序排列的所有函数值，从最小值开始，在每一步使用前一步计算得到的值来计算当前值，这样可以计算任何这一类型的函数。我们将这种技术称做自底向上动态规划(bottom-up dynamic programming)。它适用于任何计算，只要我们可以保存前面的所有计算值。它是一种算法设计技术，已经被成功应用于大量的问题。我们必须花精力寻找一种简单的技术，它可以将算法的运行时间从指数减少到线性。

    自顶向下动态规划(top-down dynamic programming)就是一种更简单的技术，与自底向上动态规划相比，它能够以一种自动化的方式，花同样的开销来执行递归函数(或者开销少于自底向上动态规划)。我们让这个递归程序保存它所计算的每个值(作为其最后动作)，而且检查所保存的值，避免重新计算它们(作为一个头动作)。下面为斐波纳契数递推式的自顶向下动态规划法实现，它的运行时间为线性。自顶向下动态规划有时也称做memorization。
    int F(int i)
    {
        int t;
        if(knownF[i] != unknow) return known[i];
        if(i == 0) t = 0;
        if(i == 1) t = 1;
        if(i > 1) t = F(i-1) + F(i-2);
        return knownF[i] = t;
    }

    性质：动态规划可以减少递归函数的运行时间，最多减少到对所有小于或等于已知参数求解函数所需要的时间。这里我们将递归调用的运行时间视为常数。

    在自顶向下动态规划中我们保存已知值；而在自底向上动态规划中，我们预先计算它们。我们一般愿意选择自顶向下动态规划，因为：

• 它是问题自然解的机械转换；
• 子问题的计算级数不影响其他问题；
• 不需要所有子问题的答案。

    动态规划应用程序在子问题的本质上、在保存与子问题相关的信息的数量上有所区别。

    我们不能忽视的关键一点是，当我们所需的函数量太大，以至于不能承受保存它们(在自顶向下中)或者预先计算它们(在自底向上中)所需的开销时，动态规划变得效率低下。

-------------------------------------------------------

树(tree)

    在算法设计和分析中，树是一个扮演核心角色的数学抽象，这是因为我们

• 使用树来描述算法的动态性质；
• 生成和使用具体实现树的显式数据结构。

     树是满足一定要求的顶点(vertex)和边(edge)的非空集合。顶点是一种简单的抽象(也可以称做节点)，它可以有名字，也可以包含其他相关信息；边是两个顶点之间的连线。树中的路径(path) 为一个不同顶点的列表，这些连续的顶点在树中通过边连接在一起。树的定义性质是，任意两个节点之间，只有一条路径相连。如果在节点对之间有多条路径相连，或者在节点对之间无路径相连，则构成了图(graph)，而不是树。一个分离的树的集合称做森林(forest)。

    有根树是我们指定了某节点作为树根的树。在计算机科学中，一般术语“树”来泛指有根树，使用用术语“自由树”来指前面所描述的更一般的树。在有根树中，任何节点都是子树(subtree)的根，子树包含该节点与该节点以下的节点。

    在根与树与其他每个节点之间只有一条路径。此定义表明边是无方向的。通常将边看作都背离根，或者都指向根，依具体的需要而定。通常，我们绘制有根树时，将根放在顶端。如果x位于节点y到根的路径上(也就是说，如果y位于x之下，并通过一条不经过根的路径与x连接)，我们就说节点y在节点x之下(点x在节点y之上)。每个节点(除了根外)都刚好有一个节点在其上，这个节点称做父亲(parent)；紧邻节点的下方节点称做孩子(child)。有时，我们还进一步借用家族树的术语，使用祖父节点(grandparent)和兄弟节点(sibling)的叫法。

    无子节点的节点称做叶(leave)，或者终止节点(terminal node)。至少有一个孩子的节点有时称做非终止节点(nonterminal node)。

    在某些应用中，每个节点的孩子有序排列很重要；在其他应用中则不然。有序树是一棵有根树，其中指定了每个节点的孩子顺序。有序树是一种自然表示方式。如果每个节点必须有特定数量的孩子按特定顺序出现，则我们称之为M叉树。在这样的树中，把无孩子的节点定义为特殊的外部节点常常是合适的。然后，外部节点可以充当那些没有特定孩子数量的节点所引用的哑节点。特别是，最简单的M叉树类型是二叉树。二叉树是一棵包含两类节点的有序树：一类节点是无孩子的外部节点，另一类是只有两个孩子的内部节点。因为每个内部节点的两个孩子有序，所以称它们为内部节点的左孩子和右孩子。每个内部节点必须既有一个左孩子，又有一个右孩子，过过，其中一个孩子或两个孩子可能有一个外部节点。M叉树的叶子是孩子均为外部节点的内部节点。

    二叉树是一特殊类型的有序树，有序树是一种特殊类型的有根树，而有根树是一种特殊类型的自由树。

    定义：二叉树为连接于一对二叉树的一个外部节点或内部节点，这两棵二叉树分别称做这个节点的左子树和右子树。

    这个定义表明二叉树本身就是一个抽象数学概念。当我们制定计算机表示方式时，就是在制定这个抽象的一外具体实现。表示二叉树有多种不同方式，但它们都反应了定义的抽象本质。

    二叉树最常用的具体表示法是内部节点带两个链接的结构(左链接与右链接)。这些结构与链表相似，但它们的每个节点有两外链接，而不是一个。空节点与外部节点对应。
    typedef struct node *link;
    struct node {Item item; link l, r;};

    这种表示允许有效地实现从根向下移的运算，但对于需要沿树从孩子到父亲的上移的运算却不适合。对于要求此类运算的算法，可以给每个节点添加第三个指向父亲的链接。这种方法与双向链表类似。像链表中一样，也可心将树节点保存在一个数组中，而且在某些情况下，使用索引代替指针来作为链接。

    鉴于不同的表示方式，我们可以编制一个二叉树ADT，将希望执行的运算封装在其中，并分离这些运算的使用与实现。但这里我们不采用这种方法，因为：

• 最常用的是双链接表达方式；
• 使用树来实现更高层次的ADT，而且希望着重讨论这种方式 ；
• 对于效率取决于特殊表达方式的算法，这种效率在某种ADT中可能会失去。

    定义：M叉树是一个外部节点或内部节点，此节点与M棵树(也是M叉树)的有序序列相连。

    定义：图(graphic)由一个节点集合与连接不同节点对的边集合组成(任何节点对最多只有一条边相连)。

    假想从某节点开始，沿着一条边移向该边的构成节点，再从这个节点沿着边移向另一个节点，依此类推。按这种方式从一个节点到另一个节点，而没有节点出现两次，最后得到的一系列边就称为简单路径(simple path)。如果任何节点对之间都有简单路径相连，则称图为连通图。一条起点与终点相同的简单路径称做环路(cycle)。

    每棵树都是图，但是哪些图是树呢？如果图满足以下4个条件任何之一，就可以将图看作树：

• G有N-1条边且无环路；
• G有N-1条边且连通；
• G中的每个顶点对只有一条简单路径相连；
• G连通，但若去掉任意一条边后，就不再连通。

    以上任何一个条件都是证明其他三个条件的必要充分条件。

-------------------------------------------------------

二叉树的数学性质

     性质：一棵二叉树有N个内部节点，有N+1个外部节点。

    用归纳法证明以上性质：无内部节点的二叉树有一个外部节点，所以对于N=0时，该性质成立。对于N>0，有N个内部节点的任意二叉树在左子树有k个内部节点，在右子树有N-1-k个节点，其中k在0和N-1之间，因为根为一个内部节点。根据归纳前提，左子树有k+1个外部节点，右子树有N-k个外部节点，总数为N+1。

    性质：包含N个内部节点的二叉树有2N个链接：N-1个内部节点的链接以及N+1个外部节点的链接。

    在任意有根树中，每个节点(除根外)都有唯一的父亲，而且每条边与通向其父亲的节点相连，所以有N-1个链接连接内部节点。与之相似，所有的N+1个外部节点都有一个链接，指向唯一的父亲。

    定义：树中节点的层(level)比它的父亲的层高一级 (根为0级)。树高(height)为树节点的最大层。树路径长度(path length)为所有树节点的层总和。二叉树的内部路径长度为所有树的内部节点的层总和。二叉树的外部路径长度为所有树的外部节点的层总和。

    计算路径长度的一个简便办法是，对于所有k，求k与k层节点数之积的总和。

    性质：具有N个内部节点的任意二叉树的外部路径长度比内部路径长度大2N。

    用归纳法可以证明这条性质，而另一种证明法值得借鉴。证明过程如下：

    根据以下步骤可以构建任何一棵二叉树。从一棵只包含一个外部节点的二叉树始，重复下面的步骤N次：选出一个外部节点，用一个包含2个外部节点的新节点替换它。如果所选择的外部节点在第k层，则内部路径长度增加k，但外部路径长度增加k+2(删除了k层的一个外部节点，但在k+1层添加了2个外部节点)。这个过程从一棵内部路径长度和外部路径长度均为0的树开始，每进行N步，外部路径长度比内部路径长度多增加2。

    性质：具有N个内部节点的二叉树高度最小值为lgN(四舍五入)，最大值为N-1。

    最坏情况为只有一个叶的退化树，从根有N-1个链接指向叶。

    最佳情况是在每一层(除底层外)具有2^i个内部节点的平衡树。如果树高为h，则有2^(h-1)<N+1<2^h。因为存在N-1个外部节点。以上不等式表明以下性质：最佳情况的树高正好等于lgN的四舍五入整数。

    性质：具有N个内部节点的二叉树内部路径长度最小值为N lg(N/2)，最大值为N(N-1)/2。

     二叉树广泛运用于计算应用中，而且当二叉树为完全平衡(或接近完全平衡)时，它的性能是最优的。例如，我们用于描述分治算法(如二分搜索与归并排序)的树就是完全平衡的。

-------------------------------------------------------

树遍历

    树遍历(tree traversal)——已知树的一个指针，我们希望系统地处理该树中的每个节点。对于二叉树，有两个链接，因此访问访问节点的基本顺序有3种：

• 先序(preorder)：先访问节点，再访问左子树和右子树；
• 中序(inorder)：先访问左子树，再访问节点，然后访问右子树；
• 后序(posteorder)：先访问左子树和右子树，再访问节点。

    通过递归容易实现这些方法。

    该递归函数将树的链接算作一个参数，并将树中的每个节点作为参数调用函数visit。按这种方式，函数实现一种前序遍历；如果我们将visit的调用移到递归调用之中，就成了中序遍历；如果将visit的调用移到递归调用之后，就成了后序遍历。
    void traverse(link h, void (*visit) (link))
    {
        if (h == NULL) return;
        (*visit) (h);
        traverse(h->l, visit);
        traverse(h->r, visit);
    }

    使用显式下推栈的非递归调用实现也很有用。为了简单起见，先从考虑一个可以容纳项或树的抽象栈开始，通过树的遍历来初始化。然后，进入一个循环。在此循环中，弹出并处理栈顶对象，一直重复进行，直到栈空为止。如果弹出对象为项，则访问它；如果弹出对象为树，则根据所期望的顺序执行一系列推入运算：

• 对于前序：推入右子树，再推入左子树，然后推入节点；
• 对于中序：推入右子树，再推入节点，然后推入左子树；
• 对于后序：推入节点，再推入右子树，然后推入左子树；

    不将空树推入栈。可以证明，对于任意二叉树，这个方法得到的结果与递归方法得到的结果相同。对于前序遍历
    void traverse(link h, void (*visit) (link))
    {
        STACKinit(max); STACKpush(h);
        while (!STACKempty())
        {
            (*visit)(h = STACKpop());
           if (h->r != NULL) STACKpush(h->r);
            if (h->l != NULL) STACKpush(h->l);
        }
    }

    第四种自然的遍历策略是当树中的节点出现在页中就去访问它们，按从上到下、从左到右的顺序读取。这种方法称做层序(level-order)遍历，因为每一层所有的节点按顺序一起出现。

    我们可以把上面程序的栈替换成队列来得到层序遍历。对于前序，我们使用一个LIFO数据结构；对于层序，我们使用一个FIFO数据结构。这些程序值得研究，因为它们代表一些完成剩余工作的组织方式，而且它们在实质上有所区别。尤其是，层序与树的递归结构相关的递归实现并不对应。改变上面前序遍历中数所结构，从栈改为队列，将此遍历转换成层序遍历。
    void traverse(link h, void (*visit) (link))
    {
        QUEUEinit(max); QUEUEput(h);
        while(!QUEUEempty(h))
       {
            (*visit)(h = QUEUEget());
           if(h->l != NULL) QUEUEput(h->l);
           if(h->r != NULL) QUEUEput(h->r);
        }
    }

-------------------------------------------------------

图遍历

    所有递归程序中最重要的一个是递归图遍历，或者深度优先搜索(depth-first search)。这个对图中所有节点进行系统访问的方法是上节所讨论的树遍历方法的直接推广，而且它是许多用以处理图的基本算法的基础。它是一个简单的递归算法。从任意节点开始：

• 访问v；
• (递归)访问依附于v的每个未访问节点。

    如果图是连通的，最终我们到达所有的节点。假如我们使用邻接表来表示图，沿着图中的每条边，取两种路线中的其中一种：如果这条边将我们带到已经访问过的节点，则忽略它；如果带到尚未访问的节点，则通过一个递归调用沿着该边到达此节点。按这种方式，所经过的所有边集合构成了该图的生成树(spaaning tree)。

    深度优先搜索与一般树遍历之间的差别在于需要明确防止访问已访问过的节点。在树中，我们从未碰到这样的节点。实际上，如果图为一棵树，则从根开始的深度优先搜索等价于前序遍历。

    深度优先搜索过程的一个递归实现如下，为了访问与图中节点k相连的所有节点，我们将它标记为visited，然后，在k的邻接表中递归访问所有未访问过的节点。
    void traverse(int k, void (*visit) (int))
    {
       link t;
        (*visit) (k); visited[k] = 1;
        for(t=adj[k]; t!=NULL; t=t->next)
            if(!visited[t->v]) traverse(t->v, visited);
    }

     性质：对于具有V个顶点、E条边的图，使用邻接表表达法，深度优先搜索所需的时间与V+E成比例。

    在邻接表表示法中，存在一个与图中每条边对应的表节点，以及与图中的每个顶点对应的表头指针。深度优先搜索要到达所有表节点与表头指针，最多为一次。

    与在树遍历中一样，我们可以定义使用显式栈的图遍历方法。我们可以考虑容纳双项的抽象栈：一个节点与节点邻接表的指针。通过将栈初始化为起始节点，将指针初始化为该节点邻接表中的首节点，深度优先搜索相当于进入一个循环，其中，我们在栈顶访问节点(前提是它尚未被访问)；保存被当前邻接表指针引用的节点；更新邻接表引用下一个节点(如果位于邻接表的末尾，则弹出该项)；以及对于保存的节点推入相应栈项，引用邻接表中的首节点。

     另一种方案是，与在树遍历中一样，我们可以让栈只包含节点的链接。通过将栈顶初始化为起始节点，我们进入这样一个循环：先访问栈顶的节点(如果尚未被访问)，然后将所有与之相邻的节点推入栈上。

    这两种方法都与深度优先搜索等价，而且这种等价具有普遍性。

    访问顶部节点并推入所有邻居的算法是深度优先搜索的一种简单模式，但这种算法具有栈中可能留有每个节点的多个拷贝的缺点。即使我们测试每个即将入栈的节点是否已经被访问，而且如果已被访问就拒绝将它放入栈中，也不能避免这个缺陷。为了避免这个问题，我们可以使用遗忘旧项策略来禁止重复的栈实现，因为复制栈项最近者总是第一个被访问的，所以，其他就可以弹出了。

    深度优先搜索的栈动态特征取决于每个邻接表中的节点，它们在栈中消失的顺序与它们出现在表中的顺序相同。当一次推入一个节点时，为了得到已知邻接表的这个顺序，必须首先推入最后一个节点，然后推入倒数第二个节点，依此类推。而且，为了将栈大小限制为顶点数，而同时按深度优先搜索相同的顺序访问节点，我们需要使用采用了遗忘旧项策略的栈。如果按深度优先搜索的相同顺序访问节点对我们不重要，我们可以避免这些复杂性，并直接形成非递归基于栈的图遍历方法：将栈初始化为起始节点，进入如下循环——首先访问栈顶的节点，然后处理它的邻接表，将每个节点推入栈(如果该节点尚未被访问)，通过忽略新项策略使用一种禁止重复的栈实现。这个算法按深度优先搜索的相似方式访问图中所有节点，但它不是递归性的。

    前面所述的算法值得注意，因为我们可以使用任意广义队列ADT，并仍然访问图中的每个节点(还生成一个生成树)。例如，如果我们使用队列代替栈，则得到广度优先搜索，与树的层序遍历相似。

    要访问所有与图中节点k相连的节点，我们将k放到FIFO队列上，然后，进入这样一个循环：从队列中获得下一个节点，如果它尚未被访问，则访问它并将所有的未访问节点推入邻接表中，直到队列变空之前一直持续这个过程。
    void traverse(int k, void (*visit) (int))
    {
       link t;
       QUEUEinit(V); QUEUEput(k);
        while(!QUEUEempty())
        if (visited[k=QUEUEget()] == 0)
           {
               (*visit) (k); visited[k] = 1;
                for(t=adj[k]; t!=NULL; t=t->next)
                  if(visited[t->v] == 0) QUEUEput(t->v);
           }
    }

     广度优先搜索和深度优先搜索都访问图中的所有节点，但它们的完成方式大不一样。广度优先搜索实际上是多路搜索逐渐扩展到所有领域；深度优先搜索相当于单个搜索尽可能深入到未知领域，直到死胡同才回头。除了图搜索外，在许多计算科学领域中，它们都是重要而基本的问题解决范例。

[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译

    为数据以及数据处理的方法建立抽象模型是用计算解决问题过程中的基本步骤。在低层的日常编程中以及在高层的解决问题过程中，很多例子都体现了这一原理。通过抽象数据类型(abstract data type, ADT)可以编制使用高层抽象的程序。通过抽象数据类型，可以将程序作用于数据的概念性转换与特定数据结构表示法及算法分离。

    一方面，使用抽象机制后，我们不必特别关注它们是如何实现的；另一方面，当我们执行程序中的运算时，需要认识到基本运算的开销。我们通常根据更初级的抽象生成更衷高级的抽象。每个层次均符合相同原理：我们希望确定程序中的关键运算以及数据的关键特征，在抽象层次中准确地定义它们，然后开发有效的具体分析机制来支持它们。

    为开发新的抽象层，需要定义我们希望操纵的抽象对象以及作用于它们的运算；需要用某些数据结构来表示数据并实现这些运算；然后(从实践的角度出发)我们希望确保这些对象方便用于解决应用问题。以上原理也适用于简单数据类型。

    定义： 抽象数据类型(ADT)是一种只通过接口访问的数据类型(值的集合以及作用于这些集合上的运算集合)。我们把使用ADT的程序称做客户(client)程序，定义数据类型的程序称做实现(implementation)。

    数据类型成为抽象的关键的区别仅在于：使用ADT后，除非通过接口提供的运算，否则客户程序不会访问任何数据值。数据的表示法以及实现运算的函数均存在于实现中，通过接口与客户完全分离。接口是不透明的：客户不能通过接口看到实现。

    C串库不是一个ADT，因为使用串的程序知道串是如何表示的(表示为字符的数组)，而且一般情况下，通过数组索引或指针运算可以直接访问它们。再次说明，区别ADT的关键点是，ADT要求数据类型仅通过接口来访问。

-------------------------------------------------------

抽象对象与对象集合 (collection of object)

    抽象对象集合根据如下两种运算构建而成：

• 在集合中插入新对象；
• 从集合中删除对象。

    我们将这类ADT称做广义队列(generalized queue)。为了方便，我们还包含显示运算来初始化数据结构，并计算数据结构中项的数量(或者啥时测试它是否为空)。另一种方案是，通过定义适当的返回值，在插入和删除运算中包含以上运算。

    在上一章我们知道，数组和链表都提供了允许插入和删除特定项的基本机制。实际上，链表和数组是实现许多广义队列的相应数据结构。我们将讨论若干ADT的例子，链表和数组为它们提供了适当的解决方案。

    包含抽象对象集合的数据类型是计算机科学研究中的核心对象，因为它们直接支持基本计算范例。我们发现，对于大量的计算，要使用的对象很多，但一次只能处理一个对象。所以，要在处理其中一个对象时，需要保存其他对象。这个过程可能包括检查那些已经的对象，在集合中添加更多的对象，但根据某些准则保存对象以及读取对象的运算是基础。许多经典数据和算法符合上述模式。

-------------------------------------------------------

下推栈ADT

    在所有支持对象集合的插入与删除的数据类型中，最重要的被称为下推栈(pushdown stack)。

    定义： 下推栈是一种ADT，它包含两个基本运算：插入(压入，push)新项，删除(弹出，pop)最近被插入的项。

    下推栈的特征是：根据后进先出(last-in , first-out--LIFO)的原则删除项。

    栈的主要的应用之一就是计算算术表达式的值。比如，我们要求下面这个简单的算术表达式的值，它包括整数乘法和加法：

    5*(((9+8)*(4*6))+7)

    计算过程涉及到中间结果的保存。例如，如果首先计算9+8,则必须在计算4*6时保存它的计算结果17。在这类计算中，下推栈是保存中间结果的理想机制。

    我们书写算术表达式的习惯方式是中缀式(infix)，上面的算术式就是用中缀式书写的。

    所有的算术表达式都可以表示成这样一种形式：每个运算符出现在两个参数之后，而不是位于两个参数中间。这种形式被称为后缀式(postfix)或者叫逆波兰式。上面的算术式用后缀式表示为：

    5 9 8 + 4 6 * * 7 + *

    与后缀式相反的是前缀式(prefix)，也称波波兰表示法(Polish notation，因为它由波兰逻辑学家Lukasiewicz发明）。

    在中缀式中，我们需要用小括号来分隔，如5*(((9+8)*(4*6))+7)与((5*9)+8)*((4*6)+7)为两个不同的表达式。

    但是，后缀式(或前缀式)不需要使用小括号。

    借助于堆栈可以执行这此运算，并求任何后缀式表达式的值。从左到右，将每个操作数解释成命令“将操作数推入栈”，将每个运算符解释成“从栈中弹出两个操作数，执行运算，再推入结果”。

    我们也可以使用下推栈将使用了小括号的算术表达式从中缀式转换成后缀式。其操作方法式为：将运算符推入栈，将操作数传递给输出，右括号表明最后的运算符的两个参数都被输出，所以运算符本身可以弹出并传递给输出。

    打印用的PostScript语言是一种全面的编程语言，其中的程序用后缀式写成，并在内置栈的辅助下加以解释。

    实际上，许多计算机在硬件中实现基本的栈操作，因为它们自然简单地实现了一种函数调用机制：将信息推入栈，在函数入口保存当前环境，将信息弹出栈达到恢复出口处环境的目的。

-------------------------------------------------------

栈ADT的实现

    这里讲解栈ADT的两种实现：一种使用数组，另一种使用链表。两种实现都是上一章所述的基本数据类型的简单应用。它们唯一的区别在于各自的性能特征不同。

    使用数组表示方式有一个潜在的缺陷：对于基于数组的结构，在使用它之前，我们通常要知道数组大小的最大值，之后才能给它分配内存，将数组大小作为初始化的参数。灵活性不好。

    要允许栈能够自由地伸缩，我们需要使用链表。对于pop运算，是从表的前端删除节点并返回它对应的项；对于push运算，就是创建一个新节点，并将它添加到表的前端。因为所有的链表运算都在表的起始处，所以不需要使用头节点。通常栈的链表实现要比数组实现耗费更多的系统资源。如果我们需要一个几乎充满的庞大栈，我们宁愿选择数组实现；如果我们使用的栈其大小动态变化，还使用了其他数据结构，它可能在栈中仅有少数几项时，我们宁愿选择表实现。

    下推栈的链表实现：

    它使用辅助函数NEW为节点分配内存，根据函数参数设置它的域，并返回节点的链接。

typedef struct STACKnode* link;
struct STACKnode { Item item; link next; };
static link head;
link NEW(Item item; link next)
{
    link x = malloc(sizeof *x);
    x->item = item; x->next = next;
    return x;
}

void STACKinit()
{
    head = NULL;
}

int STACKempty()
{
    return head = NULL;
}

STACKpush(Item item)
{
    head = NEW(item, head);
}

Item STACKpop()
{
    Item item = head->item;
    link t = head->next;
    free(head);
    head = t;
    return item;
}

    使用数组或链表，我们都可以以恒定的运行时间实现下推栈ADT的push和pop运算。

-------------------------------------------------------

FIFO队列

    先进先出(FIFO)队列是另一个与下推栈相似的基本ADT，但它使用相反的规则决定delete运算删除哪一个元素。它不是删除最近插入的元素，而是删除队列中待的时间最长的元素。

    一个非常形象的例子：如果杂货商在货架前排放上新商品，客户从前排取商品，这就是栈原则。这个原则对杂货商却存在问题，因为货架后排的商品可能因长时间放置而变坏。把新商品放到货架后排，杂货商确保任何商品在货架上的存放时间由客户取走货架上最大数量商品数所花的时间，这就是FIFO队列原则。

    定义：FIFO队列是一种包含两个基本操作的ADT。这两个基本操作是：插入新项(put)和删除插入最久项(get)。

    为了实现链表的FIFO队列ADT，我们让表中项的顺序是从最久插入项到最近插入项。这个顺序与栈的实现的顺序相反。对于这个链表，我们用到了两个指针：一个指向起始处(从而可以获取首元素)，另一个指向末尾(从而可以在队列中放置新元素)。

    FIFO队列链表实现：

typedef struct QUEUEnode* link;
struct QUEUEnode { Item item; link next; };
static link head, tail;
link NEW(Item item, link next)
{
    link x = malloc(sizeof *x);
    x->item = item; x->next = next;
    return x;
}

void QUEUEinit()
{
    head = NULL;
}

int QUEUEempty()
{
    return head == NULL;
}

QUEUEput(Item item)
{
    if(head == NULL)
    {
        head = (tail = NEW(item, head));
        return;
    }
    tail->next = NEW(item, tail->next);
    tail = tail->next;
}

Item QUEUEget()
{
    Item item = head->item;
    link t = head->next;
    free(head);
    head = t;
    return item;
}

-------------------------------------------------------

广义队列

     下推栈与FIFO队列是更一般的ADT-广义队列(generalized queue)的特例。广义队列的不同实例间的区别在于删除项时所采用的规则。对于栈，所采用的规则是“删除最近插入的项”；对于FIFO队列，所采用的规则是“删除插入最久的项”；而且还有其他的规则。

    我们根据在队列中插入项的时间确定性描述了栈和FIFO队列。描述这些抽象概念的另一种方法是利用按顺序排列的顺序表，它在表的起始和末尾处插入项和删除项。如果在末尾插入和末尾删除，就得到一个栈；如果在表的起始处插入和起始处删除，也得到一个栈；如果在末尾处插入，在起始处删除，则得到一个FIFO队列；如果在起始处插入，在末尾处删除，仍然得到一个FIFO队列。鉴于此，就出现了双端队列ADT(deque ADT)，它允许在两端进行插入和删除操作。

    另一种简单但强大的队列是随机队列，它所使用的规则是“删除随机项”，客户获取队列中任何项的概率都相同。使用数组表示可以实现随机队列的恒定时间运算。不过相对于栈和FIFO队列，随机队列使用链表方案吸引力不大，因为同时高效实现插入和删除工作是一项极具挑战性的工作。

    还有一种队列叫做优先级队列(priority queue)。优先级队列中的项具有键(key)，删除的规则是“删除具有最小键的项”。

    符号表(symbol table)是另一种广义队列，其中的项具有键，删除的规则为“删除键等于已知键的项”。

[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译

    组织要处理的数据是开发计算机程序最基本的步骤。对于许多应用程序，选择恰当的数据结构是实现过程中唯一主要的决策：一旦作出了选择，得到所需的算法也就简单了。对于同样的数据，不同的数据结构所要求的窨不一样：对于作用于数据上的同样运算，不同的数据结构导致的算法效率不一样。算法的选择与数据结构的选择息息相关，我们将通过正确的选择，不断寻求节省时间与空间的方式。

    数据结构并不是被动的对象：我们还须考虑作用于它之上的运算(以及用于这些运算的算法)。这个概念通过数据类型(data type)来表达。通过下一篇笔记中将要讲到的抽象数据类型(abstract data type)，我们将数据类型的定义与实现分离开来。

    现代编程中，我们考虑数据类型时，更多的是根据程序的需要，而不是机器的差异(主要是为了让程序具有移植性)。数据类型(data type)是一个值集合，以及作用于这些值上的运算集合。运算与类型关联，而不是毫无关系。许多与标准数据类型关联的运算(如处术运算)都已经被集成到了C语言中。其他运算可以在标准库里定义的函数中找到，还有一些运算以程序中自定义C函数的形式出现。数据类型的概念不仅仅与整型、浮点型以及字符等内置类型有关。我们还经常定义自己的数据类型，作为组织软件的有效方式。

    在C语言中，我们推荐通过下面的方式来组织程序，将程序分解 成3种文件：

• 接口(interface)。定义数据结构，并声明用来操作该数据结构的函数。一般是.h文件。
• 在接口中声明了的函数的实现(implementation)。一般是.c文件。
• 客户程序(client program)。使用接口中声明的函数在较高的抽象层次工作。一般是.c文。

    我们常常希望构建可以处理数据集合的数据结构。在C语言中，以一种有组织性的方式分组数据结构的最简单机制是数组(array)和结构(structure)。结构属于聚集类，用来定义数据集合，使我们可以把整个集合作为一个单元来操纵，但仍然用名字来指向已知数据的单个元素。

    在许多场合，我们感兴趣的是处理可能庞大的数据集合。现在主讲解应付这种场合的基本方法。一般而言，术语“数据结构”指组织信息的机制，它为访问和操纵信息提供方便而且有效的机制。我们可以使用数组，以一种固定有序的方式组织对象，这更适合于访问，而不适合于操纵；或者可以使用(线性)表(list)，它按一种逻辑顺序方式来组织对象，这更适合于操纵，而不适合于访问。

-------------------------------------------------------

数 组

    最基本的数据结构可能就属数组了，在C和其他大部分编程语言中，它都被定义成基本数据结构。数组是连续保存的相同类型数据的固定集合，通过索引进行访问。

    数组与内存系统存在直接的对应关系。为了从内存中读取内容，就要提供相应的地址。我们可以将整个计算机内存看作一个数组，让内存地址与数组索引对应。

-------------------------------------------------------

链 表

    当主要任务是按顺序逐个遍历一个项集合时，可以把这些项组织成一个链表。链表是一种基本数据结构，其中每一项都包含访问下一项所需要的信息。链表相对于数组的主要优点是，链表提供了重新排列项的有效能力。这种灵活性以影响快速访问列表中的任意项为代价，因为访问表中某项的唯一途径是跟踪列表链接，从一个节点到另一个节点。

    定义： 链表是一个项集合，其中的每个项是某节点的一部分，这个节点又包含到达其他节点的链接。

    我们用节点的引用来访问节点，所以链表有时被称作自引用结构。而且，尽管节点的链接通常引用不同的节点，但也可以引用节点自身，所以链表也可以是循环结构(cyclic structure)。

    通常，我们将链表看作项集合顺序排列的实现：从一个已知节点开始，认为它的项位于序列的首位。然后，跟踪它的链接到达另一个节点，它提供我们另一个项，这是序列中的次位项，依此类推。从原理上讲，该链表可能是循环的，该序列可能看起来是无限的，但最通常处理的链表对应于有限项集合的简单顺序排列。在最后一个节点，采用如下链接约定之一：

• 它是不指向任何结点的空链接(null link)；
• 它引用不包含任何项的哑节点(dummy node)；
• 它返过来引用第一个节点，使该链表成为循环链表。

     在每一种情况下，从第一个节点开始跟踪，直到最后一个节点，定义了一个项的顺序排列。数组也定义了一组顺序排列的项。不过，在数组中，顺序组织由数组中的位置隐式提供。(数组还可以通过索引随机访问，而链表不支持。)

     在一些编程环境中，链表被定义成基本结构，但在C中不是这样。在C中将指针用于链接，将结构用于节点。typedef声明提供了引用链接和节点的途径，如下所示：
    typedef struct node *link;
    struct node { Item item; link next;};

     链接是节点的指针，节点包含项和链接。假定程序的另一部分使用type或其他基制声明了Item类型的变量。

    内存的分配是有效使用链表的中心问题。一般而言，直到程序执行时我们才会知道所需要的节点数量。只要想使用一个新的节点，就要创建一个node类型的实例，并为它开辟内存。一般用如下代码
    link x = malloc(sizeof *x);

来引导stdlib.h中的malloc函数和sizeof运算符来为节点分配足够的内存，并在x中返回一个指向它的指针。这行代码是创建新节点的一个C习惯做法。

    链接C指针之间的这种对应关系是必需的，但我们必须要记住，前者是一种抽象，后者是一种具体的表现形式。其实，有时也可用数组索引表达链接。

    在C中，插入和删除都只需要两条语句。

• 删除节点x的下一个节点，使用如下语句
  t = x->next; x->next = t->next; [free(t);]
  或使用简单形式
  x->next = x->next->next;
• 在表中节点x之后位置插入节点t，使用如下语句
  t->next = x->next; x->next = t;

    插入和删除的简单性正是链表存在的理由。对应的运算在数组中不自然，也不方便，因为它们要求多云受影响项之后的所有数组内容。

    与之相比，链表不太适合于查找第k个项的运算(查找一个已知索引的项)，而这是数组访问能轻松实现的。在数组中，只根访问a[k]就可以找到第k个项；在表中，却必须遍历k个链接。对于链表，另一个不自然的算是“查找已知项之前的项”。

-------------------------------------------------------

基本表处理

    处理按链表组织的数据被称作表处理(list processing)。

    作用于表的最常用的运算之一是遍历(traverse)。按顺序扫描表中的项，对每个项执行某些运算。例如，如果x为表中第一个节点的指针，最后一个节点有一个空指针，而visit是一个把项当成参数的函数，则可用如下语句
    for(t=x; t!=NULL; t=t->next) visit(t->item);
来遍历表。这个循环(或其等价while形式)在表处理程序中无处不在，就像在数组处理程序中频繁使用如下循环一样：
    for(i=0; i<N; i++)

    其它的表处理操作还有：表倒置 和 表排序。

    链表中头和改尾的约定主要有4种：1.循环、非空，2.头指针、空尾，3.哑头节点、空尾，4.哑头和尾节点。有时方便使用头节点的一种重要情形是，当我们希望作为参数将表的指针传递给函数之时，这个函数可能修改该表，与修改数组的形形式一样。使用头节点可以让函数接受或返回一个空表。如果我们不使用头节点，则在函数离开空表时，需要一种通知调用程序的机制。其中一种基制就是让表处理函数将输入表的指针作为自己的参数，并且返回输出表的指针。通过这种约定，我们不需要使用头节点，而且非常适用于递归表处理，因而这种机制被广泛使用。

    通过添加更多的链接，链表可以获得回溯(move backward through a linked list)的能力。例如，使用双链表(dbouly linked list)可以支持“查找已知项之前的项”运算。双链表中每个节点有两个链接：一个指向前项的链接(prev)，另一个是指向后项的链接(next)。通过哑节点或循环表，可能确保x、x->next->prev以及x->prev->next在链表中对每一个节点都是相同的。请注意，双链表中对于删除，并不需要表中该节点之前(或之后)节点的额外信息，就像处理单链表一样——这些信息被包含在节点本身之中。

    实际上双链表的主要意义在于，它可以在我们只掌握了节点链接的唯一信息时，还能够删除该节点。典型情形是，链接在函数调用中被作为参数传送，同时节点具有其他链接，是其他数据结构的一部分。提供额外的功能使得在每个节点中链接所需求的空间加倍，同时每次基本运算操纵的链接数量也加倍。所以，双链表并不常用，除非迫不得以。

-------------------------------------------------------

表的内存分配

    链表相对于数组的一个优点是，链表在生存周期可以自如地伸缩(grow and shrink)。尤其是，它的最大长度不需要预先知道。这种特性的一个重要应用是，我们可以让多个数据结构共享同一空间，而不必随时特意关注它们的相对大小。

    下面我们考虑系统函数malloc可能是如何实现的。

    系统函数free是malloc的反函数。当我们完成内存分配块的使用后，调用free通知系统该内存块可以用于其它场合了。动态内存分配(dynamic memory allocation)是管理并对客户程序调用malloc和free作出反应的过程。
    当我们在应用中直接调用malloc时，请求一个内存块。一种保持对分配的可用内存的跟踪方法是：仅仅使用链表就可以达到目的。不处于目前使用中任何表中的所有节点可用一个链表来保存。我们将这个链表称做自由表(free list)。当我们需要为某节点分配内存空间时，从自由表中删除它即可；当我们从任何表中删除某节点时，将它插入自由表即可。

    当然在C环境中实现一个一般性的内存分配器比以上例子要复杂的多。malloc必须处理不同大小节点的存储分配请求，可能很小，也可能 非常巨大。人们为此已经开发了若干智能算法。一些现代系统使用的另外一种途径是使用垃圾回收(garbage-collection)算法自动删除不被任何链接使用的节点。这样减轻了用户必须显式释放内存的负担(使用free)。若干智能存储管理算法也因此得以开发出来。

-------------------------------------------------------

串

    串指变长字符数组，由一个起点以及一个标记其结尾的串终止符来定义。串在底层数据结构中有利用价值。

    以串终止符结束的字符序列的抽象概念可以用多种途径来实现。例如，可以用链表来实现，尽管选择的代价是一个字符要配备一个指针。而我们所讨论的基于数组的具体实现是一种已经集成到C中的实现。

    串与数组之间的区别与长度有关。两者都表示连续的内存区域，但数组的长度在创建数组时设置，而串的长度可以在程序运行期间改变。这种区别表明了一些有趣的含义。

    我们需要为串保留内存，或者是在编译时，通过声明定长字符数组来实现，歌者在运行时，通过调用malloc来实现。一旦分配了数组，就可以填充字符，从起点开始，以串终结符结束。没有串终止符，串只是字符的数组；有了串终止符，我们可以在更高层抽象进行工作，而且只考虑从起点到串终结符的数组部分，让这部分 包含有意义的信息。在C中，终止符为0，或者表示为'\0'。 

-------------------------------------------------------

复合数据结构

    数组、链表以及串都提供了按顺序构建数据的简单方式。它们提供了用于组合对象的第一层抽象，其方式有利于高效处理对象。确定这些抽象后，就能以一种层次性的方式应用它们来构建更复杂的结构。我们可以构建数组的数组、表的数组、串的数组等等。

    一维数组对应于向量，按相同的方式，带有两个索引的二维数组与矩阵(matrix)对应。二维数组广泛被用于数学计算中。

    二维数组的分配：
    这个函数把二维数组当成数组的数组为它动态分配内存。首先，分配一个指针的数组，然后为每一行分配内存。使用这个函数，如下语句
    int **a == malloc(M, N);
函数定义：

    int **malloc2d(int r, int c)

    {

        int i;

        int **t = malloc(r * sizeof(int*));

        for(i=0; i<r; i++)

            t[i] = malloc(c * sizeof(int));

        return t;

}

    二维数组是一种记号上的方便，因为数组中的数字最后被保存在计算机内存中时，也实质上是一个一维数组。在许多编程环境中，二维数组以行主序(row-major order)保存一个一维数组中：在数组a[M][N]中，头N个位置将由第一行(从a[0][0]到a[0][N-1]的元素)占据，接下来的N个位置由第二行占据(从a[1][0]到a[1][N-1]的元素)占据，依此类推。

    动态分配数组的方法，让程序用于不同的问题规模而不必重新编译它们，对于多维数组，也存在相似的方法。对于在编译时不知道大小的数组，我们不能用声明int a[M][N]，因为M和N的值是动态的。对于主序，如下语句
    int* a = malloc(M*N*sizeof(int));
是分配M×N整数数组的有效途径，但这种方案并不适用于所有C环境，因为并不是所有的实现都使用行主序。而上面提到的malloc2d的是一种有效的解决方案，它基于数组的数组的定义。

    因为我人对于串的抽象概念是字符的数组，所以初看之下，我们 可以把串的数组表示为数组的数组。不过，在C语言中，我们所使用的具体实现是一个指字符数组起始处的指针，所以，串的数组 也是指针的数组。只要重排序数组中的指针，就可以获得重新排列串的效果。

    只通过链接也可以建立复合数据结构。多重表(multilist)就是这样的例子，其中的节点有多个链接域，而且属于独立维护的链表。在算法设计中，我们通常使用多个链接来构建复杂数据结构，但通过这种方式，我们可以有效处理它们。例如，双链表是一个多重表，它满足x->l->r以及x->r->l均等于x。

    如果多维矩阵为稀疏矩阵(极少项为0)，于是，我们可以使用多重表代替多维数组表表示 它。可以让一个节点对应矩阵中的一个值，一个链接对应一维，链接指向该维中的下一项。这种安排降低了存储空间的要求，原来要求具备各个维中最大索引之积的存储空间，现在降低为只需要与非零数成比例的存储空间，但是增加了许多算法的时间，因为它们必须遍历链接访问各个元素。

    图(graph)是一种基本的组合式数据结构，被简单定义为对象(称作顶点,vertex)的集合以及顶点间连接(称作边，edge)的集合。假定图有V个顶点、E条边，由E个0~V-1之间的整数对集合来定义。也就是说，假定顶点标记为整数0,1,...V-1，边正义为顶点对。对于无向图(undirected graph)，将i-j对或j-i对定义为i-j之间的连通。

    为了同时突出索引式和链接式数据结构的区别，我们用两种方法来表示图。

    表示图的一种简单方法是使用二维数组，这种数组被称做邻接矩阵(adjacency matrix)。使用邻接矩阵，我们可以立即判断出顶点i到j之间是否存在一条边，只要机查矩阵i行、j列的值是否为0就可以达到目的。对于无向图，如果矩阵i行、j列的有一个项，则在矩阵j行、i列也一定存在一个项，所以这个矩阵是对称的。

    表示图的另一种方法是，使用链接数组，被称做邻接表(adjacency list)。为每个顶点设置一个链表，与该顶点连接的每个顶点设置一个节点。

    两种图表示法都是较简单数据结构的数组，每个顶点对应的数据结构描述了附属于这个顶点的边。对于邻接矩阵，较简单数据结构实现为索引数组；对于邻接表，则实现为一个链表。

    当我们表示图时，将直接面对空间上的得与失。邻接矩阵使用与V^2成比例的空间；邻接表使用与V+E成比例的空间。如果边很少(这类图称做稀疏图)，则邻接表表示使用少得多的空间；如果大部分顶点对存在连接的边(这类图称做稠密图)，选择邻接矩阵较适宜，因为它不涉及链接。一些算法使用邻接矩阵表示更有效，因为它能让”在顶点i和顶点j之间是否存在一条边？“这样的问题在一定时间内得以回答；其他一些算法使用邻接表表示法更有效,因为它能用与V+E成比例的时间 处理所有的边，而不是与V^2成比例。

    根据基本抽象构造体，通过显式或隐式的链接形式，我们可以构建极其复杂的数据结构，可以将不同类型的数据构建成对象，现将对象序列化，形成复合对象。

    在Robert Sedgewick所著的Algorithm In C中，把二维数组当成数组的数组为它动态分配内存。

    首先，分配一个指针的数组，然后为每一行分配内存。
函数定义：
    void **malloc2d(int r, int c, int size)
    {
        int i;
        int **t = malloc(r * sizeof(void*));
        for(i=0; i<r; i++)
            t[i] = malloc(c * size);
        return t;
    }

    void free2d(void **arr, int r)
    {
        int i = 0;
        for(i=0; i<r; i++)

            free(arr[i]);
        free(arr);
    }

    这种方法好处是可以用a[i][j]的方式来访问数组元素，但是它需要分配额外内存来存储行指针。

    另外，这种方法分配的内存是不连续的，而且在分配和释放二维数组时，要多次调用malloc和free操作，增加了系统开销。而使用以下两种方法为二维数组分配的内存是连续的，可以避免因频繁分配和释放内存而带来的内存开销。

方法一：

    用一维数组来实现二维数组的功能，在内存中二维数组还是线性排列的。对于想申请a[m][n]数组可以如下实现：
    int   *ptr_array;
    ptr_array   =   (int*) malloc(m*n*sizeof(int));
当需要访问a[i][j]时,   用如下方式访问:  
  *(ptr_array   +   i   *   n   +   j);
当需要释放空间时，用如下方式访问：
    free ptr_array;

    这种方式实际上是把二维数组用一维数组表示,  再模拟成二维数组使用.

方法二：

void **malloc2d(int row, int col, int size)
{
    void **arr;
    arr = (void **) malloc(sizeof(void *) * row + size * row * col);
    if (arr != NULL)
    {
        void *head;
        head = (void *) arr + sizeof(void *) * row;
        memset(arr, 0, sizeof(void *) * row + size * row * col);
        while (row--)
            arr[row] = head + size * row * col;
    }
    return arr;
}

void free2d(void **arr)
{
    if (arr != NULL)
    free(arr);
}

    这种方法的好处和不足之处同Robert Sedgewick的方法一样，可以用a[i][j]的方式来访问，但仍然需要额外分配内存来存储行指针。但它分配的空间是连续的，可以避免因频繁分配和释放内存而带来的内存开销，这一点又可与方法一媲美。

最值得推荐的方法是方法二。

[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译

    分析是充分理解算法并将其有效应用到实际问题中的关键。用数学分析精确描述复杂算法性能的思想初听之下似乎是一种令人畏惧的奢望，但我们的确弘常参考研究文献，引用那些基于详细数学研究的结论。当我们想比较不同的算法时，首先意只到我们是基于科学的基础这上的，这一点对于我们也很重要。

    算法分析有试验分析(empirical analysis)和近似分析(approximate analysis,一种数学的分析方法)两种。试验分析得到的性能结果不仅直接给予我们有效性的指示，而且提供比较算法以及验证那些可能应用的数学分析所需要的信息。当试验研究开始消耗大量宝贵的时间时，则需要使用数学分析。等待程序1个小时或1天来完成，以此断定程序的快慢，这种方法很难大量应用，尤其是用直接分析就能得到相同的信息时。

    在试验分析中，我们面临的第一个挑战是开发一个正确而且完整的实现。

    试验分析面临的第二个挑战是判断输入数据以及其他对所进行试验有直接影响的因子的性质。典型情况下，我们有3种选择：使用实际数据(actual data)、使用随机数据(random data)、使用不合法数据(perverse data)。分析算法时，也存在决定使用哪一种输入数据来比较算法的问题。

    试验分析对于某些任务可能就足够了，但数学分析提供的信息更多(而且付出的代价不多)。

    数学分析在比较算法性能的过程中发挥作用，基本算法应用数学分析，奠定了讨论基本分析结果的基础。我们做算法数学分析的原因有：

• 比较同一任务的不同算法；
• 预测在新环境中的性能；
• 设置算法参数值。

-------------------------------------------------------

函数增长

    大部分算法有一个主参数(primary parameter) N，它对运行时间的影响最大。参数N可能是多项式的度、排序和搜索的文件大小、文本串中的字符数，或者被考虑问题规模的抽象度量：最通常情况下，它与被处理的数据大小成正比。当存在多个这样的参数时，通常将其中一个参数表达为另一个参数的函数，或者每次只考虑一个参数(令另一个参数为常数)，以此来简化分析。可以在不失一般性的前提下，只考虑单个参数。我们的目标是使用尽可能简单、对于大值参数正确的数学公式，用N表达程序所需要的资源(通常就是运行时间)。典型情况下的运行时间与下面的函数之一成正比：

• 1
  大部分程序的大部分指令只执行一次，或者至多执行几次。如果程序的所有指令都具有该性质，我们就说程序的执行时间为常数。
• logN
  当程序的运行时间具有对数属性时，则程序运行时间增长比N增长稍慢些。将一个大问题转换成一系列小问题，每一步都把问题规模分解为恒定的小部分，这样的程序通常具有这种运行时间。在我们的兴趣范围之内可能将运行时间看作小于一个大常数。对数的底数改变这个常数，但改变不大。当N等于1000时，若底数为10，则logN等于3，若底数为2，则logN约等于10。当N等于10^6时，logN的值才加倍。只要N加倍，logN就增加一个常数，但只有N增加到N^2时，logN才会加倍。
• N
  当程序运行时间为线性(linear)时，一般的情况是，对每个输入元素只进行少量的处理。N等于10^6时，运行时间也是这么多。只要N加倍，运行时间也加倍。这种情况对于必须处理N个输入(或生成N个输出)的算法最理想。
• NlogN
  当问题分解成较小的子问题，每个子问题独立解决，然后综合这些解决方案时，解决此类问题的算法就具有NlogN运行时间。当N等于10^6时，NlogN约为2*(10^7)，当N加倍时，运行时间比其倍数更大(但不会太多)。
• N^2
  当算法的运行时间为二次时，该算法只对相对较小的问题实用。处理所有数据项对的算法具有二次性运行时间(大概位于双重嵌套的循环中)，这种算法只对于小问量实用。当N为100时，运行时间为10^6。N加倍，运行时间增加到4倍。
• N^3
  与N^2类似，处理三次方数据项的算法具有立方性运行时间(大概位于三重嵌套的循环中)，这种算法只对于小问量实用。当N为100时，运行时间为10^8。N加倍，运行时间增加到8倍。
• 2^N
  具有指数关系运行时间的少数算法适合于实际应用，尽管这种算法是在使用蛮用手法解决问题时自然得出来的。当N等于20时，运行时间为10^6。N加倍，运行时间增加到原值的平方。

    特定程序的运行时间可能 是某常数乘以以上项之一(即主项，leading term)，再加上一些小项。常系数取决于分析结果和实现细节。粗略的讲，主项的系数与内部循环的指令数有关：在算法设计的任何一级，要谨慎限制这类指令的数量。对于大N，主项起主要支配作用；对于小N或严格设计的算法更多的项发挥作用，算法的比较更困难。在大部分情况下，我们把程序的运行时间简单称作“线性”、“logN”、“立方”等等。

    为了减少程序的运行时间，我们集中最小化内部循环的指令数。

    对于小规模问题，使用哪一种方法区别不大——高速的现代计算机可以迅速完成任务。但随着问题规模的增大，处理的数量也变大。算法执行的指令变得相当庞大，即使对于最快的计算机，执行这些指令需要的时间也长得让算法难以实现。

-------------------------------------------------------

对数函数

    对数函数在算法的设计和分析中扮演着特殊的角色，所以有必要详细讨论它。因为我们经常只针对某常数因子处理分析结果，因而使用记号logN，而没有指定底数。将底数从一个常数改为另一个常数，算法的值只是变为原值的一个常数倍，指定的底数通常表明它处在特殊的上下文中。在数学中，由于自然对数(底数e=2.71828...)十分重要，我们通常使用lnN来表示。在计算科学领域，二进制对数(底数为2)常使用lgN来表示。

    有时我们要迭代对数计算，即反复将对数应用在一个庞大的数字上。例如，lglg(2^256)=lg256=8。这个例子说明，基于实际目的，由于它是如此小，我们一般将loglogN看作一个常数(甚至在N为大数时也将loglogN看作一个常数)。

    比lgN大的最小整数是按二进制表示N所需要的位数，同理，大于log10N的最小整数是以十进制表示N所需要的位数。如下C语句：
    for (lgN=0; N>0; lgN++, N/=2);
是计算大于lgN的最小整数的简单方式。计算这个函数的相似方法是：
    for (lgN=0, t=1; t<N; lgN++, t+=t);
第二种方法基于的原理是：当n为大于lgN的最小整数时有2^n <= N < 2^(n+1)。

-------------------------------------------------------

常用函数和数学记号

    下面我们介绍一些在经典分析中频繁碰到的特殊函数和数学记号，它们在简洁描述程序的性质时有用。

     算法和分析最经常处理的是离散单元(discrete unit)，如下函数将实数转换成整数：

• ┕x┙ 小于或等于x的最大整数
• ┍x┑ 大于或等于x的最小整数

    它们分别对应于C语言math.h中的floor和ceil函数。例如┍lg(N+1)┑为用二进制表示N所需的位数。

     自然对数lnN为曲线1/x在定义域1和N之间的面积lnN=∫1..N dx/x。

    自然对数的离散化版本叫做调和数(harmonic nmber)，它在算法分析中经常出现。第N个调和函数定义如下：
    HN = 1 + 1/2 + 1/3 + ... + 1/N

     调和数HN等于1/x定义的阶跃函数在定义域1和N之间的面积。常数 γ表示HN与lnN=∫1..N dx/x的差。
    HN ≈ lnN + γ + 1/(12N)   其中，常数γ=0.57721...(即欧拉常数)。

     数列：0 1 1 2 3 5 8 13 21 34 55 89 144 233 377...由以下公式定义：
    FN = FN-1 + FN-2，    其中N>=2，F0=0， F1=1
这就是我们所熟悉的斐波纳契数列(Fibonacci number)。斐波纳契数列具有许多有趣的性质。例如，两个连续项的比约等于黄金比例φ=(1+√5)/2≈1.61803...。进行更详细的分析可知，FN为φ^n/√5四舍五入后最接近的整数。

     我们还有机会接触到熟悉的阶乘函数N!。与指数函数一样，阶乘出现在蛮力解决方案中。由于实际方面的原因，阶乘在这种解决方案中增长得相当快。在算法分析中也存在阶乘函数，它表示排列N个对象的所有方式。可以使用斯特林公式(Stirling's formula)求N！的近似值：
    lgN! ≈ NlgN + Nlge + lg√(2πN)
例如，根据斯特林公式可知，N!二进制表示的位数约等于NlgN。

-------------------------------------------------------

O记号

    为了在分析算法时简化细节，人为指定数学标记O记号(O-notation，渐近记号)，或大Oh记号(big-Oh notation)。定义如下：

    定义：如果存在常数co和No，对于所有N>No，有g(N)<cof(N)则g(N)=Of(N)。

    使用O记号有3个不同的目的：

• 当忽略公式中的小项时，限制错误的发生；
• 当忽略对总分析结果有微小贡献的程序部分时，限制错误的发生；
• 允许根据总运行时间的上限将算法分类。

    O记号中包含的常数co和No通常隐藏那些实际中重要的实现细节。如果N刚好小于No，算法运行时间为Of(N)的表述就无意义了，而co可能隐藏了设计用来避免最坏情况的大量开销。我们宁愿选择一个运行时间为N^2纳秒的算法，而不会选择运行时间为logN个世纪的算法，但我们无法根据O记号来作出这种选择。

    通常，数学分析的结果并不准确，从精确的技术意义上讲只是一种近似。这个果可能是一个由递减序列组成的表达式。正如我们关心程序的内部循环一样，我们最关心的是数学表达式的主项(leading term)，也就是最大项。当讨论近似数学表达式时，我们可以通过O记号跟踪主项同时乎略较小项，最终精简表达式，得到与分析量较近似的值。我们称带有一个O项的公式称做渐近式(asymptotic expression)。

    Windows平台下可以使用的GCC编译器主要有CygWin和MinGW。相对而言，IDE(集成开发环境)却一直没有一个令人满意的选择。MinGW Developer Studio和Dev C++都已很不完善，而且都很久没有更新过了。

    最近在学习 Algorithms  In C: Part 1-4 Fundamentals, data structures, sorting, searching ，需要测试书中的一些例子。由于先前一直使用的Visual Studio 2005过于庞大，觉得写小程序没有必要，于是便想找一个轻量级的IDE。

    从网上苦苦搜寻，终于发现了一个年轻的，支持多种编译器的IDE Code::Blocks 。其特性有：

Highlights:

• Open Source! GPLv3, no hidden costs.
• Cross-platform. Runs on Linux, Mac, Windows (uses wxWidgets).
• Written in C++. No interpreted languages or proprietary libs needed.
• Extensible through plugins

Compiler:

• Multiple compiler support:
  • GCC (MingW / GNU GCC)
  • MSVC++
  • Digital Mars
  • Borland C++ 5.5
  • Open Watcom
  • ...and more
• Very fast custom build system (no makefiles needed)
• Support for parallel builds (utilizing your CPU's extra cores)
• Multi-target projects
• Workspaces to combine multiple projects
• Inter-project dependencies inside workspace
• Imports MSVC projects and workspaces (NOTE: assembly code not supported yet)
• Imports Dev-C++ projects

Debugger:

• Interfaces GNU GDB
• Also supports MS CDB (not fully featured)
• Full breakpoints support:
  • Code breakpoints
  • Data breakpoints (read, write and read/write)
  • Breakpoint conditions (break only when an expression is true)
  • Breakpoint ignore counts (break only after certain number of hits)
• Display local function symbols and arguments
• User-defined watches (support for watching user-defined types through scripting)
• Call stack
• Disassembly
• Custom memory dump
• Switch between threads
• View CPU registers

Interface:

• Syntax highlighting, customizable and extensible
• Code folding for C++ and XML files.
• Tabbed interface
• Code completion
• Class Browser
• Smart indent
• One-key swap between .h and .c/.cpp files
• Open files list for quick switching between files (optional)
• External customizable "Tools"
• To-do list management with different users

And many more features provided through plugins!

    值得称赞的是这个IDE的作者们都很勤奋，更新很快，是一个有前途的集成开发环境。

看了以后发现挺有用的。

• 手诊讲座\经络全息手诊—观手知健康1   [30:54]
• 手诊讲座\经络全息手诊—观手知健康2   [52:46]
• 手诊讲座\经络全息手诊—观手知健康3   [34:05]
• 手诊讲座\经络全息手诊—观手知健康4   [41:22]
• 手诊讲座\经络全息手诊—观手知健康5   [49:38]
• 手诊讲座\经络全息手诊—观手知健康6   [23:14]
• 手诊讲座\经络全息手诊—观手知健康7   [31:50]
• 手诊讲座\经络全息手诊—观手知健康8   [50:39]
• 手诊讲座\经络全息手诊—观手知健康9   [58:15]
• 手诊讲座\经络全息手诊—观手知健康10 [xx:xx]

    C A Referenc Manual  (Fifth Edition)

    By Samuel P. Harbison III, Guy L. Steele Jr.

    这又是一本工具书级的书，该书在C语言书籍中的地位相当于Herbert Schildt的The C++: Complete Reference在C++书籍中的地位，都是经典中的经典。

    这本书的影印版从上学期就买来了，一直只是当工具书来用，没有时间系统地学习。前一段时间又开始用C写程序，写完之后就有了一股想好好复习一次C语言的冲动。于是又拿出了这本书，抽空就看看。平均每天看二三十页，零零散散看了一周多，终于把该书的第一部分看完了。

    全书分两大部分，第一部分(308页以前)讨论了C语言的所有语言特征，包括词法、预处理机制、声明、类型、表达式、语句及函数等基本语言特性。第二部分讨论了C语言的标准库。

    该书与纯粹的语言手册不同，除了分门别类并且详细地介绍语言的基本特性以外，还加入了一些说明性的实例，提供一些背景介绍或解释。该书对细节的描述毫不含糊，好些平时编程时经常拿不准的东西，都解释的很彻底很详细。读本书的时候经常有一种既之其然又知其所以然的豁然开朗的感觉。

    本书的另外一个特点就是将K&R C、ANSI C、和C99放在同一个框架里，互相对照着一起介绍。并且每一章的最后一部分都归纳了该章内容与C++标准的兼容性问题。

    该书无论作为一本参考书还是一本系统学习C语言的中级教材都非常值得推荐。

    准备下一步把第二部分(既C语言标准库)也看完。

    另外人民邮电出版的这本影印版书籍纸张还是相当不错的，又厚又白，就是字有点太小，阅读时间长了会有点累。

     今天是清明节作为法定节假日第一次实施，我没有心情出去玩，在实验室看了一上午的 C A Reference Manual (5th ed)。后来忽然想到山东省人事考试中心网站上查一查软件设计师证书出来了没。证书还没有，但发现昨天贴出了全国前50名名单。顺便打开看看都有哪些人，没想到自己的名字竟然在里面。这个级别山东省入围的总共有3个人。真是狂喜~

 

山东省人事考试中心

[关于印发我省2007年下半年计算机技术与软件专业技术资格（水平）考试各级别总成绩进入全国前50名人员名单的通知]

信息产业部电子教育与考试中心

[2007年下半年计算机技术与软件专业技术资格（水平）考试各个资格前50名排位]