Conner's profile☆ Conner Wang ☆PhotosBlogListsMore  |  Tools Help |
|
|
May 25 《Algorithms In C》读书笔记之(六)—快速排序[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译 快速排序(quicksort)大概是比其他任何排序算法都应用广泛的排序算法。快速排序流行的原因是，它易于实现、能够很好地适用于各种不同输入数据，而且消耗的资源比其他任何排序方法都少。 快速排序有着与其相应的特征(只使用一个小的辅助栈)，排序N个项的平均时间仅与NlogN成比例，而且其内循环时间极短。它的缺点是不稳定，在最坏情况下，需要N^2次运算：而且，实现中的一个简单的错误可能难以察觉，可能导致某些文件性能低下，从这种意义上说，快速排序是脆弱的。 ------------------------------------------------------- 基本算法 快速排序是排序的一种分治算法(divide-and-conquer method)。它的工作方式是，次数组划分为两组，然后独立排序各个部分。划分的准确位置取决于输入文件中元素的初始顺序。方法的关键在于划分过程，它将数组重排，使如下3个条件成立：
通过划分实现完全排序，然后递归地在子文件中应用这个方法。因为划分总是至少将一个子元素放到位，所以，通过归纳法证明递归方法构成了一个正确的排序并不难。 如果数组只有一个或者更少的元素，则无任何运算。否则，partition程序将处理这个数组，它将a[i]放到最终位置(i为l和r之间某个值，且含r)，并重排其他元素，让递归调用能正确完成排序。
我们使用如下通用策略来实现划分。首先，任意选定a[r]为划分元素(partitioning element)——将处于最终位置的元素。下一步，从数组右端进行扫描，直至发现一个小于该划分元素的元素。停止扫描的这两个元素显然不在最后划分数组的正确位置，所以交换它们。按这种方式继续划分，确保左指针左边的元素都小于划分元素，而且右指针右边的元素都大于划分元素。 变量v保存划分元素a[r]的值，i和j分别为左右扫描指针。划分循环增加i、减小j，同时保持一个不变的性质：i左边的元素没有比v大的，j右边的元素没有比v小的。一旦指针相遇，交换a[i]与a[r]后就完成了划分，这次交换将v放到a[i]，使得v的右边没有更小的元素，发的左边没有更大的元素。划分实现为一个无穷循环，当指针相遇时使用break跳出。测试j==l避免划分元素为文件中最小元素的情况发生。
划分的过程是不稳定的，因为在交换中，任何键可能被移过大量等于它的键。尚无使基于数组的快速排序变得稳定的简单办法。 对于键等于划分元素的情况，可以采取3种基本策略：碰到这类键时，让两个指针停止；让一个指针停止，让另一个跳过；或者让两个指针都越过。研究表明，最好是让两个指针停止，主要是因为当存在许多重复键时，这个策略可以平衡划分，而其他两种策略对于某些文件可能导致严重不平衡划分。 排序的效率最终取决于文件的划分良莠程度，而后者又取决于划分元素的值。 ------------------------------------------------------- 快速排序的性能特征 未完待续...... May 20 《Algorithms In C》读书笔记之(五)—基本排序方法[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译 排序文件由数据项由数据项(item)组成，数据项又包含键(key)。在现代编程环境下，所有这些概念都具有自然抽象性。键通常只是项的一部分，它用于控制排序。排序方法的目标是重排这些项，让它们的键根据一些明确定义的排序规则来排序(通常按数字或字母来排序)。键和项的特性在各种应用中都可以各不相同，但键与相关信息按顺序排列的抽象概念是排序问题的本质。 如果被排序的文件可以装载于内存中，则称该排序方法为内部排序(internal sort)。若排序文件来自碰带或磁盘，则称做外部排序(external sort)。两者的主要区别是，内部排序可以轻松访问任意项，而外部排序必须按顺序访问项，或者至少要按大数据块来访问。 排序数组的问题以及排序链表的问题都很重要：在算法编制中，我们会碰到一些最适合于顺序排序的基本任务，还有其他一些最适合于链式分配的任务。一些经典的算法具有充分的抽象性，它们可以用数组或链表来实现；另外一些算法特别适合于用某一种数据结构来实现。 我们首先学习数组排序。下面的程序是我们 的一个约定。它是一个驱动程序，通过从标准输入读取整数或者生成随机整数来填充数组；然后调用排序函数将整数按序放入数组；接着打印排序后的结果。排序函数假定被排序的数据类型为Item，而且为Item定义了运算less(比较两个键)、exch(交换两个项)以及compexch(比较两个项，并在必要时交换它们，让第二个项不小于第一个项)。
该示例sort函数是插入排序的一个变体。因为它只使用比较交换运算，所以它属于非适应性排序(nonadaptive sort)。它所执行的运算序列独立于数据的顺序。相比而言，适应性排序(adaptive sort)执行不同的运算序列，它们取决于比较(less运算)的结果。非适应性排序值得注意，因为它非常适合于硬件实现，但我们考虑的大部分通用排序都是适应性的。 排序通常按两种途径之一来访问项：或者访问键进行比较，或者访问整个项进行移动。如果排序的项庞大，进行间接排序，避免打乱这些项是明智的。我们排的不是项本身，而是指针(或索引)的数组，让第一个指针指向最小的项，第二个指针指向第二小的项，依此类推。我们可以让键与项一起(如果键庞大)，或者与指针一起(如果键小)。排序后，可以重排项，但通常没有必要这样做，因为在排序后的状态，我们还可以(间接地)引用它们。 ------------------------------------------------------- 选择排序 首先，找出数组中的最小元素，并用首位置的元素与它交换。然后，找出次大元素，并用第十个位置的元素与它交换。重复此步骤，直到排序完整个数组。这个方法称做选择排序(selection sort)，因为它重复性地选择剩余元素中的最小元素来完成排序。
内循环仅仅测试当前元素是否为目前为止最小元素(另外，还有增加当前元素索引并检查它未越过数组的对应代码)。移动项的工作在外循环中完成：每次交换将一个元素放到它的最终位置上，所以，交换次数为N-1(对最后一个元素不需要交换)。因此，运行时间受比较次数的限制。 选择排序的一个缺点是，它的运行时间与文件中已完成的排序量只有一点关系。遍历文件查找最小元素的过程似乎对于下一次遍历文件时最小元素可能所在的位置并没有提供多少信息。例如，排序用户可能惊奇地发现，排序一个已经排序好的文件，或者排序一个所有键相等的文件与排序一个随机排序的文件，它们所花的时间一样长。 尽管使用了暴力方式，但它在一个重要应用中，胜过更复杂的算法：对于具有庞大项、小键值的文件，使用选择排序则更为合适。对于这种应用，移动数据的开销控制比较的开销，而且没有其他算法在排序文件时，数据移动的次数会比选择排序更少。 ------------------------------------------------------- 插入排序 人们通常用于排序手中桥牌的方法是一次考虑一张牌，将它插入到已经排序过的牌的适当位置中。本章第一节的程序是这个方法的一个实现，它被称做插入排序(insertion sort)。 第一节的插入排序的实现简单，但有效。但还有值得我们改进的地方。首先，我们碰到不大于正被插入项的键时，停止compexch运算，因为左边的子数组已经排序好了。这种修改将实现变成一种适应性排序，而且对于随机排序的钕，程序加速约2倍。 通过前一段中描述的改进，终止内循环的条件有两个——可以将它重新用while循环来编码，以明确反映这一事实。实现的一个较细微的改进是j>l的测试是多余的。 第三个改进也是包含删除内循环中的过多指令。它的依据是对同一个元素的连续交换率不高，因而只将较大元素右移一个位置，而不使用交换，因此避免了上述方式的时间浪费。 改进程序：(i)它首先将数组中的最小的元素放在第一个位置，让它作为标记；(ii)在内循环中，它进行单个赋值，而不是进行交换；(iii)当正插入的元素已经就位时，终止内循环。
与选择排序不一样，插入排序的运行时间主要取决于输入数组中键的初始顺序。如果文件庞大，而且已经排序过(或者接近排序状态)，则插入排序速度快，而选择排序较慢。 ------------------------------------------------------- 冒泡排序 许多人学的第一种排序方法是冒泡排序(bubble sort)，因为它相当简单。冒泡排序不断地扫描文件，交换没有按顺序排列的邻近元素，直到完成整个文件的排序才停止。冒泡排序的主要优点是它易于实现，但实际上是否真的比插入排序和选择排序更容易实现值得商榷。一般说来，冒泡排序会比其他两种方法要慢。 对于从l到r-1的每个i，内部(j)循环通过从右到左的元素传递、比较交换连续的元素，将a[i], ..., a[r]中的最小元素放到a[i]的位置上。最小元素通过这种比较一直向左移动，因此就“冒泡”似地移到了起始处。与在选择排序中一样，当索引i从左向右在文件中移动时，索引左边的元素就是该元素在数组中的最终位置。
------------------------------------------------------- 基本排序的性能特征 选择排序、插入排序和冒泡排序不管在最坏情况下还是在一般情况下，它们都是二次性时间算法，而且都不需要额外内存。它们的运行时间因此只相差常数倍，但它们的运算方式大不一样。 一般来说，排序算法的运行时间与算法使用的比较次数成正比例，与移动或交换的项数成比例，或者与两者比成比例。对于随机输入，比较这些方法包括对比较和交换次数常数倍差异的研究、对内循环长度的常数倍差异的研究。对于具有特殊性质的输入，这些方法的运行时间可能相差不只常数倍。 性质： 插入排序约平均使用N^2/4次比较、N^2/4次半交换(移动)，在最坏情况下，比较与交换次数加倍。 性质：冒泡排序在最坏情况下，约平均使用N^2/2次比较、N^2/2次交换。 定义：倒置(inversion)指颠倒文件中一对键的次序。 为了定义文件中的倒置数，对每个元素，可以加和其左边元素大于该元素的个数(称这个量为元素对应的倒置数)。这个计数正好是插入排序中插入元素时它必须移动的距离。部分正序的文件与任意分布的文件相比，其倒置数要少。 性质：对于对应于每个元素的倒置数都都不超过某常数的文件，插入排序和冒泡排序使用线性数量的比较和交换。 性质：至多有一定数量的元素具有多于一定数量的相应倒置时，对于这种文件，插入排序使用线性数量的比较和交换。 对于小文件，插入排序和选择排序的速度是冒泡排序的两倍，但是运行时间呈二次性增长（当文件大小成倍增长时，运行时间成4倍增长）。对于庞大的随机排序文件，以上方法都无能为力。当比较开销昂贵时（例如，其中的键为串），则插入排序比其他两种排序方法要快得多，因为它使用的比较要少。在交换开销昂贵的场合，选择排序是最佳选择。 插入排序的运行时间取决于文件中倒置的总数量，与倒置的分布方式无关。 要得到运行时间的结论，需要分析比较和交换的相对开销，这个因子又反过来取决于项的大小和键。 性质：对于大项、小键文件，选择排序的运行时间为线性。 ------------------------------------------------------- 希尔排序 插入排序速度慢，因为它进行的唯一交换涉及到邻接项，因此，在数组中，项只能一次移动一个位置。例如，如果最小项刚好就在数组的末端，则需要N步将它移到位。希尔排序(shell sort)是插入排序的简单扩展，它允许离得很远的元素进行交换，所以提高了速度。 希尔排序的思想是，重建文件后让它具有以下性质：每h取一个元素(从任意处开始)，得到一个有序文件。这种文件称称作h-有序(h-sorted)。换一个角度看，一个h-有序文件是h个独立的有序文件，它们交叉排列在一起。当h较大时，通过h-排序我们可以在数组中长距离移动元素，因此，使得对于更小的h，更容易进行h-排序。对于任意的h值序列(以1结尾)，使用这样的过程都生成一个有序文件。这就是希尔排序的实质。 一种实现希尔排序的方式是，对每个h，分别使用插入排序独立排序所有h个子文件。尽管这个过程已经很简单，但我们甚至还可以使用更简单的方式，因为这些子文件是独立的。当使用h-排序文件时将较大元素移到时右边，然后在h-子文件的前面元素中插入。 如果我们不使用标记，则在插入排序中，将其中的每个"1"换成"h"，得到的程序对文件做h-排序。添加一个循环来更改增量，得到如下紧凑的希尔排序实现。本程序使用的增量序列为：1 4 13 40 121 364 1093 3280 9841...(这是Knuth在1969年推荐的值，计算该增量序列很容易，从1开始，通过乘以3再加1得到下一个增量，而且得到一个相当有效的排序，即使对于中等大小的大型文件也有效)
性质：对于一个k-有序文件进行h-排序的结果是一个既h-有序又k-有序的文件。 性质：g-排序一个既h-有序又k-有序的文件，希尔排序进行的比较次数少于N(h-1)(k-1)/g。设h和k互质。 性质：对于增量序列1 4 13 40 121 364 1093 3280 9841...，希尔排序的比较次数少于O(N^(3/2))。 性质：对于增量序列1 8 23 77 281 1073 4193 16577...，希尔排序的比较次数少于O(N^(4/3))。 性质：对于增量序列1 2 3 4 6 9 8 12 18 27 16 24 36 54 81...，希尔排序的比较次数少于O(N(logN)^2)。 设计一个优秀希尔排序增量序列的问题是简单算法具有复杂行为的一个突出例子。 April 29 《Algorithms In C》读书笔记之(四)—递归和树[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译 递归在数学和计算科学中是一个基本概念。递归的简单定义：编程语言中调用自身的程序(就像数学中的递归函数是通过自身来定义的一样)。递归程序不能一直调用自己或是就远不终止(就像递归函数不能总是通过自身来定义，否则就里循环定义)。因此，第二个必不可少的成分是，当程序可以停止调用自己时，必须有一个终止条件(termination condition)(像数学中的函数不再通过自身定义时)。所有的实际计算都可用一个递归框架来表达。 递归的研究与被称为树(tree)的递归定义结构的研究是相辅相成的。利用树不仅能帮助我们理解和分析递归程序，也能作为显式的数据结构。我们利用树来理解递归程序；利用递归来建立树；并且利用两者之间的基本关系(以及递归关系)来分析算法。在各种应用中，递归还能帮助我们开发优秀而高效的数据结构与算法。 ------------------------------------------------------- 递归算法 递归算法是通过解决一个或多个相同问题的较小实例来解决某个问题。在C语言中，应用递归函数实现递归算法。递归函数就是调用自身的函数。C语言中的递归函数对应于数学函数中的递归定义。 我们还将会看到，递归程序总是可以转换成执行相同计算的非递归程序。反之，我们也可以不用循环而是通过递归来表达包含循环的所有计算。使用递归的原因是因为它能够以一种紧凑的形式表达复杂算法，而不降低其效率。递归实现的开销由系统中支持函数调用的机制产生，它使用内置下推栈等价的方式。尽管递归有如上优点，但我们以所会看到，很容易就会编写出一个简单但效率极其低下的递归函数，所以，务必当心避免在递归函数中使用难以控制的实现。 从实际而言，根据数学归纳法，应该确保递归函数满足两个基本性质：
这两点说得比较笼统——实际上是说，对于我们编写的每个递归函数，都必须能够进行有效的归纳证明。而且，这两点对于我们编制实现提供了有用的指导。 理论上，我们可以用等价的递归程序替换任何for循环。与for循环相比，递归程序通常更自然地表达计算，所以我们应该充分利用支持递归的编程系统提供的机制。不过，我们必须要记住的是，其中存在一个潜在的开销。当我们执行递归程序时，一直在进行嵌套函数调用，直到不需要递归调用为止，然后返回。在大部分编程系统环境中，这类嵌套函数调用是通过等价的内置下推栈来实现的。递归深度是在计算过程中函数的最大嵌套深度。一般来说，嵌套深度取决于输入。在使用递归程序时，需要考虑的是，编程环境必须维持一个大小与递归深度成比例的下推栈。对于大型问题，栈所需的空间可能妨碍我们使用递归方案。 ------------------------------------------------------- 分治 许多递归程序使用了两个递归调用，每个调用作用于大约一半的输入。这种递归方案大概是算法设计中众所周知的分治(divide-and-conquer)范例的一个重要实例，它是许多极其重要算法的基础。 以求数组a[0],...,a[N-1]里N个项中最大项为例进行说明。通过一次简单的数组遍历，就能轻松地完成这项任务，如下所示 下面我们给出同一个问题的递归分治解决方案，用它来说明分治的概念。这个函数将文件a[1],...,a[r]分解成a[1],...,a[m]和a[m+1],...,a[r](递归性地)求这两部分的最大元素，并返回其中的较大者，它就是整个文件的最大元素。假定Item是一个一级类型，它定义了>。如果文件大小为偶数，这两部分大小相等；如果文件大小为奇数，第一部分比第二部分多1个元素。 ------------------------------------------------------- 动态归划(dynamic programming) 分治算法的本质特征是，它将问题分解成独立的子问题。当子问题不独立，解就更复杂，主要是因为即使这类最简单算法的直接实现也可能需要难以想象的大量时间。 例如，下面是斐波纳契数递推式的直接递归实现。 注意：不要使用这个程序，它的背效率极其低下。实际上，计算F(N)的递归调用次数正好等于F(N+1)。但F(N)约等于φ^N，其中φ=1.618为黄金分割率。这个程序虽然紧凑而且优雅，但是因为它药费指数时间来计算F(N)，所以不实用。计算F(N+1)的时间是计算F(N)，的时间的φ倍。 相比之下，通过计算头N个斐波纳契数并保存在一个数组中，就容易以线性时间来计算F(N)(与N成比例)： 这个数成指数变化，所以数组不大——例如，F(45)=1836311903是可以由32位整数表示的最大斐波纳契数，一个大小为46的数组就可以满足要求。 递推是一种整数值的递归函数。我们得到这样的结论：通过计算按序排列的所有函数值，从最小值开始，在每一步使用前一步计算得到的值来计算当前值，这样可以计算任何这一类型的函数。我们将这种技术称做自底向上动态规划(bottom-up dynamic programming)。它适用于任何计算，只要我们可以保存前面的所有计算值。它是一种算法设计技术，已经被成功应用于大量的问题。我们必须花精力寻找一种简单的技术，它可以将算法的运行时间从指数减少到线性。 自顶向下动态规划(top-down dynamic programming)就是一种更简单的技术，与自底向上动态规划相比，它能够以一种自动化的方式，花同样的开销来执行递归函数(或者开销少于自底向上动态规划)。我们让这个递归程序保存它所计算的每个值(作为其最后动作)，而且检查所保存的值，避免重新计算它们(作为一个头动作)。下面为斐波纳契数递推式的自顶向下动态规划法实现，它的运行时间为线性。自顶向下动态规划有时也称做memorization。 性质：动态规划可以减少递归函数的运行时间，最多减少到对所有小于或等于已知参数求解函数所需要的时间。这里我们将递归调用的运行时间视为常数。 在自顶向下动态规划中我们保存已知值；而在自底向上动态规划中，我们预先计算它们。我们一般愿意选择自顶向下动态规划，因为：
动态规划应用程序在子问题的本质上、在保存与子问题相关的信息的数量上有所区别。 我们不能忽视的关键一点是，当我们所需的函数量太大，以至于不能承受保存它们(在自顶向下中)或者预先计算它们(在自底向上中)所需的开销时，动态规划变得效率低下。 ------------------------------------------------------- 树(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叉树的叶子是孩子均为外部节点的内部节点。 二叉树是一特殊类型的有序树，有序树是一种特殊类型的有根树，而有根树是一种特殊类型的自由树。 定义：二叉树为连接于一对二叉树的一个外部节点或内部节点，这两棵二叉树分别称做这个节点的左子树和右子树。 这个定义表明二叉树本身就是一个抽象数学概念。当我们制定计算机表示方式时，就是在制定这个抽象的一外具体实现。表示二叉树有多种不同方式，但它们都反应了定义的抽象本质。 二叉树最常用的具体表示法是内部节点带两个链接的结构(左链接与右链接)。这些结构与链表相似，但它们的每个节点有两外链接，而不是一个。空节点与外部节点对应。 这种表示允许有效地实现从根向下移的运算，但对于需要沿树从孩子到父亲的上移的运算却不适合。对于要求此类运算的算法，可以给每个节点添加第三个指向父亲的链接。这种方法与双向链表类似。像链表中一样，也可心将树节点保存在一个数组中，而且在某些情况下，使用索引代替指针来作为链接。 鉴于不同的表示方式，我们可以编制一个二叉树ADT，将希望执行的运算封装在其中，并分离这些运算的使用与实现。但这里我们不采用这种方法，因为：
定义：M叉树是一个外部节点或内部节点，此节点与M棵树(也是M叉树)的有序序列相连。 定义：图(graphic)由一个节点集合与连接不同节点对的边集合组成(任何节点对最多只有一条边相连)。 假想从某节点开始，沿着一条边移向该边的构成节点，再从这个节点沿着边移向另一个节点，依此类推。按这种方式从一个节点到另一个节点，而没有节点出现两次，最后得到的一系列边就称为简单路径(simple path)。如果任何节点对之间都有简单路径相连，则称图为连通图。一条起点与终点相同的简单路径称做环路(cycle)。 每棵树都是图，但是哪些图是树呢？如果图满足以下4个条件任何之一，就可以将图看作树：
以上任何一个条件都是证明其他三个条件的必要充分条件。 ------------------------------------------------------- 二叉树的数学性质 性质：一棵二叉树有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种：
通过递归容易实现这些方法。 该递归函数将树的链接算作一个参数，并将树中的每个节点作为参数调用函数visit。按这种方式，函数实现一种前序遍历；如果我们将visit的调用移到递归调用之中，就成了中序遍历；如果将visit的调用移到递归调用之后，就成了后序遍历。 使用显式下推栈的非递归调用实现也很有用。为了简单起见，先从考虑一个可以容纳项或树的抽象栈开始，通过树的遍历来初始化。然后，进入一个循环。在此循环中，弹出并处理栈顶对象，一直重复进行，直到栈空为止。如果弹出对象为项，则访问它；如果弹出对象为树，则根据所期望的顺序执行一系列推入运算：
不将空树推入栈。可以证明，对于任意二叉树，这个方法得到的结果与递归方法得到的结果相同。对于前序遍历 第四种自然的遍历策略是当树中的节点出现在页中就去访问它们，按从上到下、从左到右的顺序读取。这种方法称做层序(level-order)遍历，因为每一层所有的节点按顺序一起出现。 我们可以把上面程序的栈替换成队列来得到层序遍历。对于前序，我们使用一个LIFO数据结构；对于层序，我们使用一个FIFO数据结构。这些程序值得研究，因为它们代表一些完成剩余工作的组织方式，而且它们在实质上有所区别。尤其是，层序与树的递归结构相关的递归实现并不对应。改变上面前序遍历中数所结构，从栈改为队列，将此遍历转换成层序遍历。 ------------------------------------------------------- 图遍历 所有递归程序中最重要的一个是递归图遍历，或者深度优先搜索(depth-first search)。这个对图中所有节点进行系统访问的方法是上节所讨论的树遍历方法的直接推广，而且它是许多用以处理图的基本算法的基础。它是一个简单的递归算法。从任意节点开始：
如果图是连通的，最终我们到达所有的节点。假如我们使用邻接表来表示图，沿着图中的每条边，取两种路线中的其中一种：如果这条边将我们带到已经访问过的节点，则忽略它；如果带到尚未访问的节点，则通过一个递归调用沿着该边到达此节点。按这种方式，所经过的所有边集合构成了该图的生成树(spaaning tree)。 深度优先搜索与一般树遍历之间的差别在于需要明确防止访问已访问过的节点。在树中，我们从未碰到这样的节点。实际上，如果图为一棵树，则从根开始的深度优先搜索等价于前序遍历。 深度优先搜索过程的一个递归实现如下，为了访问与图中节点k相连的所有节点，我们将它标记为visited，然后，在k的邻接表中递归访问所有未访问过的节点。 性质：对于具有V个顶点、E条边的图，使用邻接表表达法，深度优先搜索所需的时间与V+E成比例。 在邻接表表示法中，存在一个与图中每条边对应的表节点，以及与图中的每个顶点对应的表头指针。深度优先搜索要到达所有表节点与表头指针，最多为一次。 与在树遍历中一样，我们可以定义使用显式栈的图遍历方法。我们可以考虑容纳双项的抽象栈：一个节点与节点邻接表的指针。通过将栈初始化为起始节点，将指针初始化为该节点邻接表中的首节点，深度优先搜索相当于进入一个循环，其中，我们在栈顶访问节点(前提是它尚未被访问)；保存被当前邻接表指针引用的节点；更新邻接表引用下一个节点(如果位于邻接表的末尾，则弹出该项)；以及对于保存的节点推入相应栈项，引用邻接表中的首节点。 另一种方案是，与在树遍历中一样，我们可以让栈只包含节点的链接。通过将栈顶初始化为起始节点，我们进入这样一个循环：先访问栈顶的节点(如果尚未被访问)，然后将所有与之相邻的节点推入栈上。 这两种方法都与深度优先搜索等价，而且这种等价具有普遍性。 访问顶部节点并推入所有邻居的算法是深度优先搜索的一种简单模式，但这种算法具有栈中可能留有每个节点的多个拷贝的缺点。即使我们测试每个即将入栈的节点是否已经被访问，而且如果已被访问就拒绝将它放入栈中，也不能避免这个缺陷。为了避免这个问题，我们可以使用遗忘旧项策略来禁止重复的栈实现，因为复制栈项最近者总是第一个被访问的，所以，其他就可以弹出了。 深度优先搜索的栈动态特征取决于每个邻接表中的节点，它们在栈中消失的顺序与它们出现在表中的顺序相同。当一次推入一个节点时，为了得到已知邻接表的这个顺序，必须首先推入最后一个节点，然后推入倒数第二个节点，依此类推。而且，为了将栈大小限制为顶点数，而同时按深度优先搜索相同的顺序访问节点，我们需要使用采用了遗忘旧项策略的栈。如果按深度优先搜索的相同顺序访问节点对我们不重要，我们可以避免这些复杂性，并直接形成非递归基于栈的图遍历方法：将栈初始化为起始节点，进入如下循环——首先访问栈顶的节点，然后处理它的邻接表，将每个节点推入栈(如果该节点尚未被访问)，通过忽略新项策略使用一种禁止重复的栈实现。这个算法按深度优先搜索的相似方式访问图中所有节点，但它不是递归性的。 前面所述的算法值得注意，因为我们可以使用任意广义队列ADT，并仍然访问图中的每个节点(还生成一个生成树)。例如，如果我们使用队列代替栈，则得到广度优先搜索，与树的层序遍历相似。 要访问所有与图中节点k相连的节点，我们将k放到FIFO队列上，然后，进入这样一个循环：从队列中获得下一个节点，如果它尚未被访问，则访问它并将所有的未访问节点推入邻接表中，直到队列变空之前一直持续这个过程。 广度优先搜索和深度优先搜索都访问图中的所有节点，但它们的完成方式大不一样。广度优先搜索实际上是多路搜索逐渐扩展到所有领域；深度优先搜索相当于单个搜索尽可能深入到未知领域，直到死胡同才回头。除了图搜索外，在许多计算科学领域中，它们都是重要而基本的问题解决范例。 April 17 《Algorithms In C》读书笔记之(三)—抽象数据类型[读书笔记]<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为节点分配内存，根据函数参数设置它的域，并返回节点的链接。
使用数组或链表，我们都可以以恒定的运行时间实现下推栈ADT的push和pop运算。 ------------------------------------------------------- FIFO队列 先进先出(FIFO)队列是另一个与下推栈相似的基本ADT，但它使用相反的规则决定delete运算删除哪一个元素。它不是删除最近插入的元素，而是删除队列中待的时间最长的元素。 一个非常形象的例子：如果杂货商在货架前排放上新商品，客户从前排取商品，这就是栈原则。这个原则对杂货商却存在问题，因为货架后排的商品可能因长时间放置而变坏。把新商品放到货架后排，杂货商确保任何商品在货架上的存放时间由客户取走货架上最大数量商品数所花的时间，这就是FIFO队列原则。 定义：FIFO队列是一种包含两个基本操作的ADT。这两个基本操作是：插入新项(put)和删除插入最久项(get)。 为了实现链表的FIFO队列ADT，我们让表中项的顺序是从最久插入项到最近插入项。这个顺序与栈的实现的顺序相反。对于这个链表，我们用到了两个指针：一个指向起始处(从而可以获取首元素)，另一个指向末尾(从而可以在队列中放置新元素)。 FIFO队列链表实现：
------------------------------------------------------- 广义队列 下推栈与FIFO队列是更一般的ADT-广义队列(generalized queue)的特例。广义队列的不同实例间的区别在于删除项时所采用的规则。对于栈，所采用的规则是“删除最近插入的项”；对于FIFO队列，所采用的规则是“删除插入最久的项”；而且还有其他的规则。 我们根据在队列中插入项的时间确定性描述了栈和FIFO队列。描述这些抽象概念的另一种方法是利用按顺序排列的顺序表，它在表的起始和末尾处插入项和删除项。如果在末尾插入和末尾删除，就得到一个栈；如果在表的起始处插入和起始处删除，也得到一个栈；如果在末尾处插入，在起始处删除，则得到一个FIFO队列；如果在起始处插入，在末尾处删除，仍然得到一个FIFO队列。鉴于此，就出现了双端队列ADT(deque ADT)，它允许在两端进行插入和删除操作。 另一种简单但强大的队列是随机队列，它所使用的规则是“删除随机项”，客户获取队列中任何项的概率都相同。使用数组表示可以实现随机队列的恒定时间运算。不过相对于栈和FIFO队列，随机队列使用链表方案吸引力不大，因为同时高效实现插入和删除工作是一项极具挑战性的工作。 还有一种队列叫做优先级队列(priority queue)。优先级队列中的项具有键(key)，删除的规则是“删除具有最小键的项”。 符号表(symbol table)是另一种广义队列，其中的项具有键，删除的规则为“删除键等于已知键的项”。 April 14 《Algorithms In C》读书笔记之(二)—基本数据结构[读书笔记]<Algorithms In C: Part 1-4 Fundamentals, data structures, sorting, searching> 第三版 Robert Sedgewick著 周良忠 译 组织要处理的数据是开发计算机程序最基本的步骤。对于许多应用程序，选择恰当的数据结构是实现过程中唯一主要的决策：一旦作出了选择，得到所需的算法也就简单了。对于同样的数据，不同的数据结构所要求的窨不一样：对于作用于数据上的同样运算，不同的数据结构导致的算法效率不一样。算法的选择与数据结构的选择息息相关，我们将通过正确的选择，不断寻求节省时间与空间的方式。 数据结构并不是被动的对象：我们还须考虑作用于它之上的运算(以及用于这些运算的算法)。这个概念通过数据类型(data type)来表达。通过下一篇笔记中将要讲到的抽象数据类型(abstract data type)，我们将数据类型的定义与实现分离开来。 现代编程中，我们考虑数据类型时，更多的是根据程序的需要，而不是机器的差异(主要是为了让程序具有移植性)。数据类型(data type)是一个值集合，以及作用于这些值上的运算集合。运算与类型关联，而不是毫无关系。许多与标准数据类型关联的运算(如处术运算)都已经被集成到了C语言中。其他运算可以在标准库里定义的函数中找到，还有一些运算以程序中自定义C函数的形式出现。数据类型的概念不仅仅与整型、浮点型以及字符等内置类型有关。我们还经常定义自己的数据类型，作为组织软件的有效方式。 在C语言中，我们推荐通过下面的方式来组织程序，将程序分解 成3种文件：
我们常常希望构建可以处理数据集合的数据结构。在C语言中，以一种有组织性的方式分组数据结构的最简单机制是数组(array)和结构(structure)。结构属于聚集类，用来定义数据集合，使我们可以把整个集合作为一个单元来操纵，但仍然用名字来指向已知数据的单个元素。 在许多场合，我们感兴趣的是处理可能庞大的数据集合。现在主讲解应付这种场合的基本方法。一般而言，术语“数据结构”指组织信息的机制，它为访问和操纵信息提供方便而且有效的机制。我们可以使用数组，以一种固定有序的方式组织对象，这更适合于访问，而不适合于操纵；或者可以使用(线性)表(list)，它按一种逻辑顺序方式来组织对象，这更适合于操纵，而不适合于访问。 ------------------------------------------------------- 数 组 最基本的数据结构可能就属数组了，在C和其他大部分编程语言中，它都被定义成基本数据结构。数组是连续保存的相同类型数据的固定集合，通过索引进行访问。 数组与内存系统存在直接的对应关系。为了从内存中读取内容，就要提供相应的地址。我们可以将整个计算机内存看作一个数组，让内存地址与数组索引对应。 ------------------------------------------------------- 链 表 当主要任务是按顺序逐个遍历一个项集合时，可以把这些项组织成一个链表。链表是一种基本数据结构，其中每一项都包含访问下一项所需要的信息。链表相对于数组的主要优点是，链表提供了重新排列项的有效能力。这种灵活性以影响快速访问列表中的任意项为代价，因为访问表中某项的唯一途径是跟踪列表链接，从一个节点到另一个节点。 定义： 链表是一个项集合，其中的每个项是某节点的一部分，这个节点又包含到达其他节点的链接。 我们用节点的引用来访问节点，所以链表有时被称作自引用结构。而且，尽管节点的链接通常引用不同的节点，但也可以引用节点自身，所以链表也可以是循环结构(cyclic structure)。 通常，我们将链表看作项集合顺序排列的实现：从一个已知节点开始，认为它的项位于序列的首位。然后，跟踪它的链接到达另一个节点，它提供我们另一个项，这是序列中的次位项，依此类推。从原理上讲，该链表可能是循环的，该序列可能看起来是无限的，但最通常处理的链表对应于有限项集合的简单顺序排列。在最后一个节点，采用如下链接约定之一：
在每一种情况下，从第一个节点开始跟踪，直到最后一个节点，定义了一个项的顺序排列。数组也定义了一组顺序排列的项。不过，在数组中，顺序组织由数组中的位置隐式提供。(数组还可以通过索引随机访问，而链表不支持。) 在一些编程环境中，链表被定义成基本结构，但在C中不是这样。在C中将指针用于链接，将结构用于节点。typedef声明提供了引用链接和节点的途径，如下所示： 链接是节点的指针，节点包含项和链接。假定程序的另一部分使用type或其他基制声明了Item类型的变量。 内存的分配是有效使用链表的中心问题。一般而言，直到程序执行时我们才会知道所需要的节点数量。只要想使用一个新的节点，就要创建一个node类型的实例，并为它开辟内存。一般用如下代码 来引导stdlib.h中的malloc函数和sizeof运算符来为节点分配足够的内存，并在x中返回一个指向它的指针。这行代码是创建新节点的一个C习惯做法。 链接C指针之间的这种对应关系是必需的，但我们必须要记住，前者是一种抽象，后者是一种具体的表现形式。其实，有时也可用数组索引表达链接。 在C中，插入和删除都只需要两条语句。
插入和删除的简单性正是链表存在的理由。对应的运算在数组中不自然，也不方便，因为它们要求多云受影响项之后的所有数组内容。 与之相比，链表不太适合于查找第k个项的运算(查找一个已知索引的项)，而这是数组访问能轻松实现的。在数组中，只根访问a[k]就可以找到第k个项；在表中，却必须遍历k个链接。对于链表，另一个不自然的算是“查找已知项之前的项”。 ------------------------------------------------------- 基本表处理 处理按链表组织的数据被称作表处理(list processing)。 作用于表的最常用的运算之一是遍历(traverse)。按顺序扫描表中的项，对每个项执行某些运算。例如，如果x为表中第一个节点的指针，最后一个节点有一个空指针，而visit是一个把项当成参数的函数，则可用如下语句 其它的表处理操作还有：表倒置 和 表排序。 链表中头和改尾的约定主要有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作出反应的过程。 当然在C环境中实现一个一般性的内存分配器比以上例子要复杂的多。malloc必须处理不同大小节点的存储分配请求，可能很小，也可能 非常巨大。人们为此已经开发了若干智能算法。一些现代系统使用的另外一种途径是使用垃圾回收(garbage-collection)算法自动删除不被任何链接使用的节点。这样减轻了用户必须显式释放内存的负担(使用free)。若干智能存储管理算法也因此得以开发出来。 ------------------------------------------------------- 串 串指变长字符数组，由一个起点以及一个标记其结尾的串终止符来定义。串在底层数据结构中有利用价值。 以串终止符结束的字符序列的抽象概念可以用多种途径来实现。例如，可以用链表来实现，尽管选择的代价是一个字符要配备一个指针。而我们所讨论的基于数组的具体实现是一种已经集成到C中的实现。 串与数组之间的区别与长度有关。两者都表示连续的内存区域，但数组的长度在创建数组时设置，而串的长度可以在程序运行期间改变。这种区别表明了一些有趣的含义。 我们需要为串保留内存，或者是在编译时，通过声明定长字符数组来实现，歌者在运行时，通过调用malloc来实现。一旦分配了数组，就可以填充字符，从起点开始，以串终结符结束。没有串终止符，串只是字符的数组；有了串终止符，我们可以在更高层抽象进行工作，而且只考虑从起点到串终结符的数组部分，让这部分 包含有意义的信息。在C中，终止符为0，或者表示为'\0'。 ------------------------------------------------------- 复合数据结构 数组、链表以及串都提供了按顺序构建数据的简单方式。它们提供了用于组合对象的第一层抽象，其方式有利于高效处理对象。确定这些抽象后，就能以一种层次性的方式应用它们来构建更复杂的结构。我们可以构建数组的数组、表的数组、串的数组等等。 一维数组对应于向量，按相同的方式，带有两个索引的二维数组与矩阵(matrix)对应。二维数组广泛被用于数学计算中。 二维数组的分配： 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的值是动态的。对于主序，如下语句 因为我人对于串的抽象概念是字符的数组，所以初看之下，我们 可以把串的数组表示为数组的数组。不过，在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成比例。 根据基本抽象构造体，通过显式或隐式的链接形式，我们可以构建极其复杂的数据结构，可以将不同类型的数据构建成对象，现将对象序列化，形成复合对象。 April 11 《Algorithms In C》读书笔记之(一)—算法分析原理[读书笔记]<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表达程序所需要的资源(通常就是运行时间)。典型情况下的运行时间与下面的函数之一成正比：
特定程序的运行时间可能 是某常数乘以以上项之一(即主项，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语句： ------------------------------------------------------- 常用函数和数学记号 下面我们介绍一些在经典分析中频繁碰到的特殊函数和数学记号，它们在简洁描述程序的性质时有用。 算法和分析最经常处理的是离散单元(discrete unit)，如下函数将实数转换成整数：
它们分别对应于C语言math.h中的floor和ceil函数。例如┍lg(N+1)┑为用二进制表示N所需的位数。 自然对数lnN为曲线1/x在定义域1和N之间的面积lnN=∫1..N dx/x。 自然对数的离散化版本叫做调和数(harmonic nmber)，它在算法分析中经常出现。第N个调和函数定义如下： 调和数HN等于1/x定义的阶跃函数在定义域1和N之间的面积。常数 γ表示HN与lnN=∫1..N dx/x的差。 数列：0 1 1 2 3 5 8 13 21 34 55 89 144 233 377...由以下公式定义： 我们还有机会接触到熟悉的阶乘函数N!。与指数函数一样，阶乘出现在蛮力解决方案中。由于实际方面的原因，阶乘在这种解决方案中增长得相当快。在算法分析中也存在阶乘函数，它表示排列N个对象的所有方式。可以使用斯特林公式(Stirling's formula)求N！的近似值： ------------------------------------------------------- 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)。 April 10 开源跨平台集成开发环境Code::BlocksWindows平台下可以使用的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 。其特性有：
值得称赞的是这个IDE的作者们都很勤奋，更新很快，是一个有前途的集成开发环境。 February 29 VS.NET 2005下Doxygen的设置与使用昨天下午安装上了Doxygen和Graphviz，并花了一晚上时间看了看文档，基本学会使用。用Doxygen结合Graphviz生成的文档比较清晰，带有类和函数的关系图。 现将Doxygen在VS.NET 2005 下的配置过程记录如下： 假设Doxygen安装在c:\program files\doxygen\ 在VS.NET 2005“工具”菜单下添加外部工具“Doxygen文档自动生成“，参数如下: 对于每个VS工程(Project) 点击VS.NET 2005“工具”菜单下的“Doxygen文档自动生成“，就在项目的\Doc目录下生成图文并貌的文档了。是不是很有成就感？ 源代码自动文档产生工具DOC++和DoxygenDOC++和Doxygen是两个类似于JavaDoc的文档生成工具。 DOC++ DOC++ is a documentation system for C, C++, IDL and Java generating both TeX output for high quality hardcopies and HTML output for sophisticated online browsing of your documentation. The documentation is extracted directly from the C/C++/IDL header/source files or Java class files. Here is a short list of highlights:
It is known to work on Linux, Solaris, AIX, HP/UX, IRIX, OSF, Unixware, FreeBSD and BeOS, but should work without any modifications on other UNIXes too, because it uses "autoconf"/"automake" configuration scripts, which ensure a high portability degree. It also works on Windows 95, 98, 2000, XP and NT. 链接： Doxyen Doxygen is a documentation system for C++, C, Java, Objective-C, Python, IDL (Corba and Microsoft flavors), Fortran, VHDL, PHP, C#, and to some extend D. It can help you in three ways:
Doxygen is developed under Linux and Mac OS X, but is set-up to be highly portable. As a result, it runs on most other Unix flavors as well. Furthermore, executables for Windows are available. 链接： February 28 Unicode的编码和实现[整理] Unicode（统一码、万国码、单一码）是一种在计算机上使用的字符编码。它为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。 编码方式 实现方式 参考： January 20 我看编程语言的学习有些时候觉得自己可能太过于盲目了，其实有很多东西在真正使用它之前是不需深入了解的。毕竟现在还在学生阶段，还没有进入职业生涯，当然也就还没有把某项技能当作生存的依赖。比如说编程语言吧，我认为现在只要把C/C++深入掌握就行了。至于其它语言，比如说Java、C#、Ruby等等，只要把基础的语法级别的东西了解下就行了。这些语言所包含的高级特性和思想，不是一时半刻就能参悟得了的，而是要等有了实践经验之后才能体会到的，更何况工作以后可能根本就用不到。而且有些新兴的东西，还没有经过时间的考验和锤炼，学了可能也白学。 我一向认为C/C++是最折磨人的语言，因而也是最能锻炼人的语言。从面向过程到面向对象，从继承到范型，从底层操作到高层抽象，C/C++都能让你如愿以偿。甚至于如果你愿意，你可以自己实现任意级别的封装与抽象。你一旦经过C/C++的洗礼，再转向其它编程语言就会很简单了。 现在可以把网撒得很大，尽量开阔自己的视野，但不可强求样样精通。因为一个人的精力是有限的，我可不想把睁着眼睛的时间都用来研究新技术。 下一步，我不想再在编程语言上花费太大功夫了，想学一学Linux C和网络编程的东西。我知道这个课题还是很大，只有一步一步来了。 January 17 我看《对象揭密：Java、Eiffel和C++》[读书笔记] 花了两天时间看完了这本书。 该书作者无疑是面向对象领域的专家，但不知道是对C/C++有愁恨还是怎么着，这本书自始至终都在批判C/C++。该书从各个角度，把C/C++批判的狗血淋头、体无完肤。我相信很多C/C++程序员看这本书会看得咬牙切齿，但想一想却又觉得作者说得不无道理。确实，C/C++的功能是最强大的，它能让你从各个层次让程序员知道自己的程序是如何工作的。程序员在用C/C++编程的时候，会从最底层知道自己都干了些什么，而且对于优秀的C/C++程序员，必须要知道自己在干什么。C/C++这样的语言是对程序员极度信任的语言，从而也把更多的责任推卸给了程序员。而语言本身又有许多陷阱，所以开发C/C++程序往往很低效，并且普通程序员是很难开发出高质量的程序的。而其它一些相对年轻的语言如Java、Eiffel，往往是让编译器和运行环境来做更多的工作，从而提高了程序开发的效率的质量。 虽然书中重点比较了Java、Eiffel和C++这三种语言（其中Eiffel语言是我所没接触过的），但作者的讨论并没有仅限于这三种语言。书中提到了好多其它的语言，及其发展和特点，并作了一定的论述，使我从一个更广阔的视野和角度来理解编程语言本身。无论你使用的是哪一种语言，看此书都会对提高你的编程水平有所帮助。 最近正好在学C#语言，C#语言是一种相对较新的语言，它结合了其它许多编程语言的优点。在学C#的过程中，我发现C#语言本身的特性都和该书中所讲的内容不谋而合。本书成书于1999年，至今也已经八年了，可见作者当时对编程语言的发展趋势的把握还是很到位的。 我自己平时都是用C/C++来写程序。由于我写的程序一般都是用于科学计算的，对程序的执行速度有严格要求的，唯有C/C++才能满足我的要求。我相信系统级的编程和驱动级的编程也将永远离不开C/C++这类的语言。当然现在编程的主流是基于网络服务的应用程序，像Java、C#之类的语言更胜任这一工作。但是，不是主流的应用并不代表不再需要，底层程序必须也得有人写，底层的语言也必将永远存在。正像现在好多电子设备都是数字化的，数学技术和器件的应用无所不在。但是模拟技术和器件却将永远也不会消失，因为它们是基础。无论是一个什么样的电子设备，能支撑它运行的最最底层的物理量仍然是模拟量。 语言之争一直在持续，正如书中所说：语言的进化史上将不会有一个最终的胜利者，新的语言会被不断地发明出来，编程语言的世界不会在哪一天稳定下来不再前进，所以我们要将所有的语言都看作过客，不应该对它们长久效忠。我觉得这一句话是很有道理的，但是这一句话应该是只适用于那些面向高层应用的语言，如Java、C#、Php、Perl、Python、Ruby等。而C/C++程序员一定要劳记，我们的定位是与它们有别的。我忘了是谁说的了，也许哪一天你就会被当作稀有动物给保护起来。 October 16 随机数产生原理及应用[转载]原文作者：EmilMatthew(EmilMatthew@126.com) 摘要:本文简述了随机数的产生原理，并用C语言实现了迭代取中法，乘同余法等随机数产生方法，同时，还给出了在符合某种概率分布的随机变量的产生方法。 关键词: 伪随机数产生，概率分布 1前言:在用计算机编制程序时，经常需要用到随机数，尤其在仿真等领域，更对随机数的产生提出了较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。本文简单的介绍随机数产生的原理及符合某种分布下的随机变量的产生，并用C语言加以了实现。当然，在这里用计算机基于数学原理生成的随机数都是伪随机数。 注:这里生成的随机数所处的分布为0-1区间上的均匀分布。我们需要的随机数序列应具有非退化性，周期长，相关系数小等优点。 2.1迭代取中法：这里在迭代取中法中介绍平方取中法,其迭代式如下:
其中，Xn+1是迭代算子，而Rn+1则是每次需要产生的随机数 。 第一个式子表示的是将Xn平方后右移s位，并截右端的2s位。 而第二个式子则是将截尾后的数字再压缩2s倍，显然:0=<Rn+1<=1. 这样的式子的构造需要深厚的数学(代数，统计学，信息学)功底，这里只是拿来用一下而已，就让我们站在大师的肩膀上前行吧。 迭代取中法有一个不良的性就是它比较容易退化成0. 平方取中法的实现: #include <stdio.h> #include <math.h> #define S 2 float Xn=12345;//Seed & Iter float Rn;//Return Val void InitSeed(float inX0) {
} /* Xn+1=(Xn^2/10^s)(mod 10^2s) Rn+1=Xn+1/10^2s */ float MyRnd() {
} /*测试主程序，注意，这里只列举一次测试主程序，以下不再重复*/ int main() {
getchar(); return 0; } 前一百个测试生成的随机数序列: 0.399000 0.920100 0.658400 0.349000 0.180100 0.243600 0.934000 0.235600 0.550700 0.327000 0.692900 0.011000 0.012100 0.014600 0.021300 0.045300 0.205200 0.210700 0.439400 0.307200 0.437100 0.105600 0.115100 0.324800 0.549500 0.195000 0.802500 0.400600 0.048000 0.230400 0.308400 0.511000 0.112100 0.256600 0.584300 0.140600 0.976800 0.413800 0.123000 0.512900 0.306600 0.400300 0.024000 0.057600 0.331700 0.002400 0.000500 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 容易看出其易退化成0的缺点. 2.2乘同余法：乘同余法的迭代式如下:
各参数意义及各步的作用可参2.1 当然，这里的参数的选取是有一定的理论基础的，否则所产生的随机数的周期将较小，相关性会较大。 经过前人检验的两组性能较好的素数取模乘同余法迭代式的系数为:
相应C程序关键代码段: double long M;//请注意，这里一定要用到double long,否则计算2^32会溢出 float MyRnd() {
} 初始化段,应有:
图1： 乘同余法生成的300随机数的产生序列图
图2: 乘同余法生成的300随机数的分布情况 可以看到，该随机数生成方法所生成的随机序列比较符合0-1上的均匀分布,不过在某些数据段还有些起伏。 2.3混合同余法：混合同余法是加同余法和乘同余法的混合形式,其迭代式如下:
经前人研究表明，在M=2^q的条件下，参数lamda,miu,X0按如下选取，周期较大，概率统计特性好: Lamda=2^c+1,c取q/2附近的数 Miu=(1/2+sqrt(3))/M X0为任意非负整数 相应C程序关键代码段: //init proper argu number M=pow(2,32); Lamda=pow(2,16)+1; Miu=(0.5+sqrt(3)/6)/M; float MyRnd() {
}
图3: 乘同余法生成的300随机数的产生序列图
图4: 乘同余法生成的300随机数的分布情况 由图4可以看出，该种随机数生成方法已相当接近0-1上的均匀分布。但在图3中可以看出它的一个致命的弱点，那就是随机数的生成在某一周期内成线性增长的趋势，显然，在大多数场合，这种极富“规律”型的随机数是不应当使用的。 下面的概率分布型随机变量的生成，均采用乘同余法或C函数库中的随机数来生成0-1区间上的随机数。 下面将C语言中的随机数生成序列图和Matlab中的随机数生成序列图列于下面，以作对比之用:
C语言生成的300个随机数的序列图
Matlab中rand函数生成的300个随机数的序列图 可以看出:乘同余法生成的随机数序列的随机性与上述两个标准库函数相接近。 3连续型随机变量的生成:3.1反函数法采用概率积分变换原理,对于随机变量X的分布函数F(X)可以求其反函数，得:
其中,Ri为一个0-1区间内的均匀分布的随机变量. F(X)较简单时，求解较易，当F(X)较复杂时，需要用到较为复杂的变换技巧。 3.1.1平均分布:例:已知炮弹对目标的方位角Fi在0-2*P内均匀分布，试用（0，1）均匀随机数变换，模拟弹着点方位角的抽样值Fi. 解: R=F(Fi)=Fi/2*PI 得Fi=G(R)=2*PI*R ,其中，R为0-1区间上的均匀分布的随机数. 程序略 试验结果:
图5:用反函数法生成的300随机数的平均分布情况 由于这里相当对0-1上的分布进行线性变换，所以变换后仍呈均匀分布是显然的。 3.1.2指数分布:指数分布的分布函数为: x<0时,F(x)=0 ; x>=0,F(x)=1-exp(-lamda*x) 利用反函数法，可以求得: x=-lnR/lamda 试验结果:
图6:用反函数法生成的300随机数的指数分布情况 可以看出，生成的随机量较好的符合了指数分布特征。 3.2正态分布随机变量的生成:正态分布在概率统计的理论及应用中占有重要地位，因此，能产生符合正态分布的随机变量就在模拟一类的工作中占有相当重要的地位。下面介绍两种方法。 3.2.1舍选法：这种方法便捷而有效，且具有一定的代表性，其基本思路是: 在概率密度的函数图像的外围画一个大框，然后在这个框内部产生随机点（rx,ry），根据是否落在概率密度函数的下方，来决定是否要留下这个点。
经过一定的计算变行，符合二维的正态分布的随机变量的生成可按下面的方法进行：
如果为(miu,sigma^2)正态分布,则按上述方法产生x后，x’=miu+sigma*x 由于采用基于乘同余法生成的0-1 上的随机数的正态分布随机数始终无法能过正态分布总体均值的假设检验。而采用C语言的库函数中的随机数生成函数rand()来产生0-1 上的随机数，效果较为理想。 关键程序段(funNorm返回一维的正态分布，而funNorm2则生成二维的随机分布): float funNorm(float miu,float sigma) {
} typedef struct {
} sPoint; sPoint funNorm2(float miu1,float sigma1,float miu2,float sigma2) {
} 列出在Matlab下对某次试验（生成分布为N(0,1)的随机数）的检测结果:
Output:
由此可见，在这种条件下生成的正态随机数序列基本能符合使用的要求,在精度上仍有该进的余地。 3.2.2利用中心极限定理生成符合正态分布的随机量：根据独立同分布的中心极限定理，有:
这里，其实只要取n=12（这里，亦即生成12个0-1上的随机数序列）就会有比较好的效果。 经验证，用该种方法生成生的随机数序列同样能比较好的符合正态分布特性。 由于生成的都是标准正态分布，所以，当需要生成N(a,b)的正态分布随机量时，根据正态分布的线性变换特性，只要用x=a*x0+b即可。（其中，x0表示生成的符合N(0,1)分布的正态随机变量。方法3.1亦是如此） 4离散型随机变量的生成:离散型随机变量的生成主要是希望得到在已知X符合某类分布的条件下，生成相应的X。 4.1符合泊松分布的随机变量的生成:这里，采用”上限拦截”法进行测试，其本的思想是这样的： 1）在泊松分布中，求出X取何值时，p(X=k)取最大值时，设为Pxmax. 其时，这样当于求解f(x)=lamda^k/k! 在k取何值时有最大值，虽然，这道题有一定的难度，但在程序中可以能过一个循环来得到取得f(x)取最大值时的整数自变量Xmax。 2) 通过迭代，不断生成0-1区间上的随机数，当随机数<Pxmax时，则终止迭代，否则重复(2) 3) 记录迭代过程的次数，即为所需要得到的符何泊松分布的随机量。 显然，这种方法较为粗糙，在试验的过程中发现：生成的的随机量只能算是近似的服从 泊松分布，所以，更为有效的算法还有待尝试。 4.2符合二项分布的随机变量的生成:符合二项分布的随机变量产生类似上限拦截法，不过效果要好许多，这是由二项分布的特点决定的。 具体方法如下: 设二项分布B(p,n)，其中，p为每个单独事件发生的概率： 关键算法: i=0;reTimes=0 while(i<n) {
} 显然，直观的看来，这种算法将每个独立的事件当作一个0-1分布来做，生成的0-1区间上的随机数，若小于1-p则不发生，否则认为发生，这样的生成方式较为合理。实验结果也验证了其合理性。 5实验结论:通过本实验，使我感受到，要生成符合要求的随机数序列，绝不是一件很轻松的事，除了要有相当的知识储备外，更应当有严谨求实的态度在其中；否则，光凭主观感觉说某些随机数的随机性好，是会在实际应用中是要栽跟头的。 有些随机数的生成仍未达到要求，有机会仍应继续被充，加深该方面理论和应用的理解。 参考文献:[1]王可定,计算机摸拟及其应用,东南大学出版社,1997 完成日:06/04/21 附录:1全文测试程序下载:http://emilmatthew.51.net/EmilPapers/06_14RandomNum/code.rar 若直接点击无法下载(或浏览)，请将下载(或浏览)的超链接粘接至浏览器地（ 推荐MYIE或GREENBORWSER）址栏后按回车.若不出意外，此时应能下载. 若下载中出现了问题，请参考: http://blog.csdn.net/emilmatthew/archive/2006/04/08/655612.aspx October 12 初试Source Insight很早就听说过Source Insight这款阅读和编辑源代码的软件，一直没能偿试使用。今天从官网上Down了一个共享版，试用了一下，感觉就是一个字“爽”！ Source Insight 是一个面向工程的程序编辑器和代码浏览器，内建支持C/C++、C#和Java程序。其特有的彩色和多字体代码显示方式、自动补全功能、上下文参考窗口以及快速而方便的代码间的链接跳转功能大大方便了代码的阅读和编写；它还可以显示程序中的引用关系、类继承关系、和调用关系，可以帮助你非常直观得分析程序。 在使用中还有一个很大的感受就是“快”，各子窗口几乎是同时随着代码的变化而更新，感觉不到延迟的存在。 对于程序的详细功能，需要在实际使用中慢慢体会了。 October 11 Monospace/Fixed Width Programmer's Fonts[转载]一篇介绍等宽字体的文章。转自：http://www.lowing.org/fonts/ About This Page Becoming frustrated with source code not aligning in my favorite source editor I decided to hunt for the best font. In particular, I began to hunt down the available fixed-width or monospaced fonts. What are monospaced fonts you ask? From Xerox: Monospace fonts (Such as Courier or LetterGothic), or "fixed pitch" fonts, contain characters that all have the same character width, producing text that can be used to create forms, tabular material or documents that require exact text line lengths. An example of a fixed pitch font is Courier 12 pitch, which is a 10 point font that will print at exactly 12 characters per inch. Why use monospaced fonts? Primarily because the text will align more readily. Especially is areas like the comment block header. Updated versions of this document will be located at Good Programming Font Criteria
Fonts Reviewed (Best Listed First) (View All) (Name, Sizes -Fontinfo, Type, Description, Download Info)
Not Yet Reviewed
ToolsMarch 13 《代码大全》传奇[转载]久违了，代码大全
□ 专题策划：孟岩 佘广 陈元玉 《代码大全》的英文版名称是 Code Complete: A Practical Handbook of Software Construction。作者是美国Contrux公司总裁 Steve McConnell。 它获得1993年美国软件开发杂志Jolt大奖，被美国包括MIT在内的十多所大学作为计算机软件学科的教材。全书的中文名实际应该理解为《代码完成：软件创建实践手册》。 《代码大全》这本书影响了90年代很多的程序员，帮助他们实现了自己在软件开发领域的梦想。在推出第二版的中译版之际,我们组织了一期关于《代码大全》的技术专题,一方面,回顾一下这本著作创作过程的前前后后,以及中译版的感人故事;另一方面,也对本书第二版向读者作一个介绍。在这里,让我们用法国作家图尼埃在他的《飞翔的吸血蝠》一文中的这段话来打开这本著作的传奇故事：
“是的，书的自然的、不可遏止的志愿是离心的。它写出来就是要发表、传播、推广、被人买、被人读。那赫赫有名的作家的象牙之塔实为一座发射塔。总是要从那里回到作者，如同回到作家之不可或缺的合作者一样。一本书不是只有一个作者，而是有无数的作者。因为在创造行为中，读过的人、正在读或将要读的人之总和有充分的权利加诸那个写的人身上。一本书写出但尚未被阅读，其存在是不完全的。 它只拥有半个存在。那是一种潜在性、一个没有血肉的、空的、不幸的生命。它要活起来就要呼唤帮助。一个作家出版一本书的时候，他知道他是朝着一群无名无姓的男人和女人放出一大群纸鸟，一大群干瘪的、渴望着血的吸血蝠，它们散开来寻找读者，碰上谁是谁。一本书一旦冲向一个读者，就立刻因他的热、他的梦而膨胀起来。它绽开花朵，终于实现了自身……”
《代码大全》传奇
□ 文/金戈 《代码大全》（第2版）的中文版已经面世，我作为本书译者之一，受《程序员》杂志之邀，来写一篇文字，讲讲《代码大全》这一传奇佳作背后的故事，实在荣幸。
讲这本传奇佳作的故事，还要从它背后的传奇人物说起，他就是Steve McConnell（斯蒂夫·麦克奈尔）。 距离微软美国总部和波音公司不远的地方，就是华盛顿州的第五大城市——Bellevue。McConnell就和他的妻儿住在这个美丽的地方。 McConnell是一位牧师的儿子，然而他选择了一条不同的道路。早年，McConnell在华盛顿州的Whitman大学学的是哲学系，并取得了学士学位。当时，学计算机只是他的第二计划。 正是在大学的计算机编程课堂上，McConnell最早接触到编程。对他来说，编程序并不是什么难事，然而直到毕业的时候，他也不知道自己以后要做什么。McConnell心想，反正学过编程，出去就能找到程序员的工作，一边工作一边再慢慢地想以后到底要干什么吧。就这样，在走出校园后的那几年，McConnell就一直在寻寻觅觅，想知道自己以后到底要做什么。直到一天早上，他一觉醒来之后突然就意识到，原来他已经在做着他想做的事情了——做一名软件开发人员。从此以后，McConnell就和编程结下了不解之缘。 McConnell在大学实习阶段就开始为一家保险公司写程序，积累了一些编程经验。后来，McConnell去了另一家软件公司，编写面向最终用户的软件，又积累了不少经验，却最终由于公司差劲的管理和不佳的道德而选择了离开。不过在这段时间， McConnell知道了IEEE（电子工程学会），并决定长期为该组织撰稿写作，这也成为他职业生涯中的一项重要选择。 1989年从那家公司离职后，McConnell已经有了四年多在公司工作的经验。这时他放弃了给某家公司固定打工的念头，攒了大半年的备用金，收集了西雅图地区一些大的科技公司的联系方式，开始了新的工作。McConnell一边做着他的咨询工作，一边读着“成人自考”。他所服务过的公司就包括有大名鼎鼎的波音和微软。最终，McConnell在西雅图大学以优等成绩获得软件工程硕士学位，并被列入该校美国大学优等生荣誉学会，几年后他还成为该校的副教授呢。 接下来，McConnell又想做另一件事了，就是写一本书了。他很想把他这么多年来的编程经验和所学到的有用知识写出来和其他人分享。于是，他花了一年半的时间完成初稿，交给出版社，而后又历经了11个月的时间完成终稿，又花了11个月的时间进行编辑，最终完成了这本处女作，并在1993年由微软出版社出版。按McConnell的话说，他就像做一项软件工程一样精心地写作这本书，前后花了近4年的时间。如果再算上McConnell此前积累经验、收集素材、整理代码等等，真可谓是十年磨一剑啦。 这本书，正是被我们称为传奇之作的《Code Complete》。 1994年，McConnell所写的这本《Code Complete》被美国《软件开发》杂志授予震撼大奖（Jolt Award），这可是素有软件业界奥斯卡之奖之称的巨大荣誉。 在Amazon网站上，这本13年前的著作至今已被上百位读者打过分[LD1]，目前得分是4.5颗星，可见它在读者心中的价值。让我们来看看国外的读者们读了此书之后都说了些什么吧： ◆ 如果你只想买“一”本关于软件开发的书的话，就买这一本吧！ ◆ 要让这本书发挥最大的功效，一定要把它放在身边随时备用……直到你的同事把它“顺”走。然后你还得再买一本，还是要放在触手可及的地方。如此反复，直到你身边到处都能找到这本书的时候，这时候再买一本自己留好。从1993年到现在（这是读者1996年10月发的评论），我已经“经手”11本《Code Complete》了，不过我还是觉得它物有所值！ ◆ 是程序员就一定要读过这本书！然后再读一遍！之后……找个时间再读一读！把它放在你的桌上（现在它应该已经够旧了）——让别人把它“偷走”——然后再买一本回来——如此循环往复…… ◆ 我想，我从来没见过如此吸引人的计算机书——写得真好，关于构建软件的几乎所有细节都写得恰到好处……我已经读过两遍了，每一遍都读得很爽。我曾把这本书当成结婚礼物送给我的一个朋友，他也是做程序员的，可没过多久他就差不多快离婚了——因为在度蜜月的时候他还只顾着读这本书…… ◆ 这本书里所讲的内容在学校里没人教过，但是学校真应该教教这些内容！ 最后这位读者说的没错，这本书的内容在当时美国教计算机的学校是不教的。当时的美国高校逐渐呈现出两极分化的趋势，传统的计算机科学（Computer Science）教育不能很好的适应业界的人才需要，因此亟待加强软件工程（Software Engineering）方面的教育。随着《Code Complete》这本书的影响力越来越广，作为一本内容翔实、生动、全面、权威的软件构建与编码技术手册，它轻理论而重实践的特点获得很多高校的青睐，于是美国包括MIT（麻省理工学院）在内的十多所大学都最终将其作为计算机软件学科的教材。可以说，这本书影响了全世界很多国家一代的程序员。 到今天，McConnell已经著有7本书，而其中的3本都曾获得《软件开发》杂志的震撼大奖或生产力大奖，这不能不说是一个软件业界作家不可跨越的奇迹。1998年，《软件开发》杂志的读者将McConnell评为软件行业中最具影响力的三人之一，与大名鼎鼎的Bill Gates和Linus Torvalds齐名。 Steve McConnell的7本著作（1993-2006） ● 1993年——《代码大全》（Code Complete）Amazon网站4.5星。
● 1996年——《快速软件开发》（Rapid Development），关于优化软件开发计划的策略和最佳实践。Amazon网站5星。 ● 1998年——《软件项目生存指南》（Software Project Survival Guide），手把手教你成功运作软件项目的指导手册。Amazon网站4.5星。 ● 1999年——《淘金热过后》（After the Gold Rush），创建真正的软件工程专业。Amazon网站3.5星。 ● 2004年——《专业软件开发》（Professional Software Development），《淘金热过后》一书的第二版，还是讲软件工程专业的事情。Amazon网站4星。 ● 2004年——《代码大全（第2版）》（更新了大量内容，如Web开发、面向对象软件开发、敏捷软件实践，以及其它现代软件构建问题。）Amazon网站5星。 ● 2006年——《Software Estimation》，论述软件项目规划与估算的专业著作。 在1993年《Code Complete》刚发布之后，北京希望电脑公司和学苑出版社就从微软出版社引进了此书，由天奥主持翻译，并于同年11月首印10000册发行——速度可谓是“相当”地快了。
不知道今天手捧《程序员》杂志的各位读者，有多少在12年前就在写程序的？90年代初期，中国的软件开发还非常不成熟，IT行业也刚刚起步，从事计算机软件开发的人员也是凤毛麟角，十分稀少。在那样的环境下，甭说软件工程了，能把一本专业的外文计算机图书翻译过来并在如此短的时间内出版已经是难能可贵了。受限于当时国内软件业相对落后的水平，当初的译本并非尽善尽美——尤其是对《Code Complete》这一书名的翻译，就更是引发了不小的争议。 Code Complete用做这样一本书的书名，到底是什么意思呢？我们不妨对比其它一些常见的说法：Mission Complete——“任务完成”（游戏中常见）；Download Complete——“下载完成”（浏览器中常见）……那么，Code Complete不就是“编码完成”的意思吗？ 我了解到，在一些现代软件工程中，“Code Complete”常常是指整个软件开发过程中一个重要的里程碑，就像更为耳熟能详的Beta、Final、Release Candidate（RC）以及Release-To-Manufacture（RTM）等等代号或称呼一样。在开发一个软件的过程中，到达这个里程碑，就意味着已经编写完成软件规格中所列出的所有功能了。当然，这里所谓的“完成”还只是在在局部而言，此后还需要进行系统级的代码集成与测试才能达到“产品完成”的程度。 在软件工程到达“Code Complete”这一里程碑之前的主要工作内容，就是逐层地完成系统中的每一个部件——从一个个变量、一条条语句聚成一个个子程序、一个个类，再到一个个包、一个个子系统……直到所有这些部件把软件规格中所定义的所有功能特性都实现完成。 这，才是《Code Complete》一书的主题所在——教会你为了到达“编码完成”这一重要里程碑所必需的所有软件构建技术。 本书把软件构建过程中的方方面面讲的淋漓尽致，尤其是细微之处，更是能够窥见作者深厚的编码功力和丰富的编码经验。从内容上讲，全书确实是关于软件构建技术的“大全”之作。如此说来，当初这么一个简单的主谓结构短语被误译为 “代码大全”之后，却也被大多数业内人士所接受、认可甚至广为流传，还是有一定道理的。 当然了，在现代的集成开发环境（IDE）中，“code complete”还有另外一个意思，就是“补全代码”——一种根据代码的上下文自动把不完整的代码补充完整的功能。如果有些人把这个意思认定为本书主题的话，那就实在是谬误至极了。 摘自熊可宜对《代码大全》（第1版）的评价
第一次阅读《代码大全》时，是在大约8年前，我读大学时。觉得读不懂，因为自己才刚刚抛弃Basic，开始学习C语言，除了一些习题，并没有多少编程的实际经验，书中的许多概念与方法都觉得非常陌生。随着一个DOS下的绘图软件Romantic Painter的开发，随着自己在开发这种较大软件时不断遇到各种问题，就越来越觉得《代码大全》不但提供了关于代码创建的最丰富的实践指南，而且就像一位导师逐渐辅导你成为一个真正专业的软件开发者。《代码大全》的英文名称是Code Complete，即代码完成，这是软件开发中的创建阶段的里程碑，即所有代码都编写完成了。而《代码大全》这个名字实际上应该理解为代码创建大全。
盖茨说过微软最重要的财产就是代码。不错，软件开发中所有的关键活动，最终的目的都为了能够创建出正确的健壮的最好用的代码。而这本书，10年前写的书，至今仍未过时，因为它所探讨的内容不是表面的现象而是关于代码创建的内在本质。毫不夸张地说，这是世界上关于代码创建的最为丰富最为深刻的实践指南。 由于年代久远，当年的《代码大全》也早已绝版，市面上甚至很多图书馆中也根本就见不到这本传奇之作的影子了。于是，2001年前后，在网友bear（熊可宜）的牵头带领下，百十来位素不相识的网友在“学苑版”《代码大全》的基础之上，历经4个多月的不懈努力，终于修订成了《代码大全》电子版图书。这些是近年来很多程序员能以窥此书的唯一途径了。 事实上，“代码大全”这四个字从它在十多年前被确定下来之时，就注定要和这本书一起成为经典的代名词，甚至成为一个品牌。鉴于“代码大全”的大名早已深深印在一代程序员的心中，最终我们决定在本书的第2版中继续沿用这一“恰如其分”的错误，也借此向原书第1版各位译者、修订者们的辛勤劳动表示我们的敬意。 时过境迁，再加上计算机行业本来就发展迅速，原书的一些内容已经看上去有些过时了——主要是书中所有示例所用的编程语言，有些早已淡出了历史舞台。而且McConnell在这几年间又有了更多的经验和感悟，他希望把这些内容也补充到原书中，让经典继续发扬光彩。于是他开始大幅度地修订《Code Complete》，让书中的内容与时俱进。没想到，这件事远没有想象的容易。 在这十多年间，关于编程的新鲜概念层出不穷。编程技术已经全面地“面向对象”了；软件过程与方法也越来越“敏捷”了；尤其是随着基于Web的软件开发逐渐兴起，软件发行的节奏已经彻底地改变了，软件项目的周期变得越来越短，软件过程自然也需要适应这一变化；编程语言也得以迅猛发展，原书写作时McConnell所熟悉的Ada、C语言已经逐渐不再适应现今主流的软件开发任务了，而面向对象的开发语言，如Java、C++、C#等等日益成为程序员们的主流选择；伴随着全社会对计算机软件越来越强烈的需求，软件项目节奏的加快，也必定带动了诸如重构、测试驱动开发等编码技术的发展……等等。 终于，2004年《Code Complete》第二版由微软出版社发行，再一次引起了编程类图书市场的火爆。用Amazon网站上读者评论的话来说：The Best Gets Better！新版的《Code Complete》继续演绎着传奇佳作的魅力，经过Amazon网站上数十位读者的评分，目前该书还保持着5颗星的佳绩，并在上架后相当长的一段时间内名列计算机编程类图书的销售榜首。这不得不让人对McConnell这位IT写作奇才佩服得五体投地。 这次电子工业出版社引进《Code Complete》的第2版，实在是国内广大程序员的一件幸事。当年读过《代码大全》第1版的那一代程序员现如今有的已经走上领导岗位，也有的转向了其它的行业。国内的程序开发人员终于有机会再次读到这本风靡全球的软件构建与编码技术宝典。 世界上最优秀的程序员们都是读过这本书的，你呢？ [LD1]注：Amazon网站是在1995年7月才对外营业的，所以已经找不到更早的读者评论了。 如何成为一名优秀的程序员？
□ 文/左轻侯
我一直想当然地认为《代码大全》(Code Complete)是一本讨论算法和数据结构的书，就象《编程珠玑》(Programming Pearls)一样。直到阅读了出版社发给我的样章以后，我才发现，不是那么一回事。在我收到的10章内容中，作者Steve McConnell广泛讨论了结对编程、代码检查、重构、测试、调试、增量集成、性能调整，甚至是程序员个人性格等诸多领域内的问题，并且结合自身的丰富经验，进行了鞭辟入里的分析。这些内容并没有涉及太多的代码，虽然偶尔也会涉及到代码。从这些内容来看，本书似乎应属于软件工程一类，但是又不能完全划分为软件工程类别。 在dearbook网站上的图书简介中写道：“……这也是一本完整的软件构建手册，涵盖了软件构建过程中的所有细节。它从软件质量和编程思想等方面论述了软件构建的各个问题，并详细论述了紧跟潮流的新技术、高屋建瓴的观点、通用的概念，还含有丰富而典型的程序示例。”照我看来，这个概括似乎仍然难以令人满意。如果用我自己的语言来描述，应该是这样：相对于关注代码本身（从算法到特定的编程语言）的图书，本书主要讨论的是代码以外的经验和技巧，它们涉及的范围极其广泛，从贴近代码层面的命名规则，到和代码相差十万八千里的“把程序员当人看”问题。其中有很多东西，已经远远超出传统意义上的软件工程的范围。但是，它们的最终目的，都是指向“如何写出高质量的代码”这一问题。 正如作者在前言中指出的：“我写这本书的首要目的，就是希望缩小本行业中一般商业实践与大师级人物及专家们之间的知识差距。”很多证据都表明，在程序编写这一行业中，新手的生产效率和经验丰富的专家相比，可以达到数量级的差距。如何在尽量短的时间内缩小这一差距，是每一个希望成为优秀程序员的读者都关心的问题。讨论代码层面的技术的图书已经汗牛充栋，相比之下，讨论代码以外的技术的图书就要少得多，而正如我们所知，产生优质代码的条件，决不仅仅取决于程序员对编程语言的熟悉。本书正是试图缩短这种差距的一次尝试，它的努力方向是将代码层面以外的实践经验传授给读者。 作者努力的结果是显而易见的。就象Samuelson的《经济学》影响了好几代经济学家一样，十几年来，这本书影响了一代程序员。我想任何一个程序员，在阅读了本书的目录以后，都很难不对它产生极大的兴趣。一个小小的例子是，一位从Redmond(微软总部)归来的同事告诉我，那里的开发人员人手一册《Code Complete》。 事有凑巧，在收到出版社的约稿之前，我正致力于在一个新成立的团队中构建他们的开发过程，这让我有机会实际接触到许多本书涉及的问题，并对它们进行思考。因此，我愉快地接受了为本书撰写书评这一任务，并希望结合自己的经验写出一些心得。由于我没有能够看到本书的完整内容，也由于时间和能力有限，我没有对全书进行整体的分析，而是采用了引用一部分原文再加以评论的方式。对于一本厚达964页的大书来，这无疑是管中窥豹，我只能希望读者能够从一斑中窥视到全豹的彪炳花纹。 第20章，软件质量概述
大部分研究都发现，检查比测试的成本更小。NASA 软件工程实验室的一项研究发现，阅读代码每小时能够检测出的缺陷要比测试高出80%左右（Basili and Selby 1987），另一个组织则发现使用测试来检测缺陷的成本是检查的6 倍（Ackerman, Buchwald and Lewski 1989）。后来，IBM 的一项研究又发现，检查发现一个错误只需要3.5 个工作时，而测试则需要花费15-25 个工作时（Kaplan 1995）。 在净室（ClearRoom）方法中，尽量将缺陷消灭在编码阶段而不是测试阶段是一个基本的思想。这种思想也许在更早的时代就已经有人提出过了，但似乎没有人把它运用到这样近乎极端的地步。在净室过程中，通过严格的代码复查（Code Review）来保证最少的缺陷。代码在进行复查之前甚至没有编译过（这意味着程序员不能再依赖编译器的强制语法检查），而通过复查的代码可以不经过模块级别的测试，就直接进行集成测试。程序员的表现由代码最终的缺陷数量来决定。
也许这种方法确实过于极端，但是这个基本方向是确凿无确的。依赖编译器和测试人员来找出缺陷，是程序员最大的恶习之一，即使不通过净室方法，也应该通过其他方法来加以避免。考虑到现实情况，完全的代码复查可能几乎无法实现，最大的原因在于生产率。实施净室过程后，一个程序员每月最终完成的代码量可能在200-300行，但是在我们面对的项目中，往往一个程序员一天完成的代码量都要远远超过这个数字。能够采取的平衡措施是，实行代码抽查，并且仍然在更大的程度上依赖测试人员（在本书中也提到，综合多种方法可以获得更高的缺陷排除效率）。这样至少可以尽量地提高代码的质量。 第23章，调试
就解决问题的表象而言，一种方法是随机的修改代码，直到你的代码看起来能工作。典型的思维逻辑是这样的：“这个循环好像有问题。可能是一个off-by-one 错误。让我先来写一个-1 试试。哦，这样不行。那么我就写个+1 试试。哈，看来程序正常工作了。我可以宣布问题搞定了。” 尽管这种方法受到了很多程序员的追捧，但它非常低效。随机地修改代码就如同是把一辆Pontiac Aztek 汽车转来转去，以为这样能修复它的引擎故障。你学不到任何东西，你只是在晃来晃去地浪费时间。你会争辩说随机修改程序是有效的，因为“我不知道这段代码到底出了什么事，我想试试这样修改，希望它有用。”不要随机修改代码。这就是所谓的“voodoo programming（巫毒编程）”。在没有理解代码的时候对它所做的修改越大，你对它能正确工作的信心就越低。 这是在初学者，甚至在某些有多年经验的程序员身上都能见到的习惯。据我个人的经验，在程序员者失去对解决问题的兴趣或感到疲惫的时候，最容易被这种习惯所左右。而某些程序员对解决问题从来就没有兴趣——他们并不试图理解问题，他们只是试图写出一段代码可以生成一个正确的结果而已。这种习惯是导致代码缺陷的最大来源之一。如果他们不改正这种习惯，将永远也无法成为优秀的程序员。
某次代码复查时，在进入代码的细节之前，一位程序员先向别人介绍他解决这个问题的思路。但他一开始就遇到了问题，他无法清晰地表述他的思路。进入代码层次之后，大家发现，他使用了一种非常古怪的方式来实现需要的功能。这种方式是如此古怪，以致于别人难以阅读他的代码，甚至他自己也无法清晰地表述。很明显，这是 “随机的修改代码，直到你的代码看起来能工作”的典型例子。 在编码之前，必须透彻地了解需要解决的问题，并且找到清晰的解决思路。如果在编码过程中发现原有的思路不够清晰，或者无法达到目的，必须先停下来重新思考，即使这样做的结果可能导致重写全部代码。 第34章，软件工艺
不要将编程思路局限到所用语言能自动支持的范围。杰出的程序员会考虑他们要干什么，然后才是怎样用手头的工具去实现他们的目标。 如果某个类的子程序成员与类的抽象不一致，你会为图省事用它，而不用更一致的子程序吗？应以尽量保持类接口抽象的方式写代码。不必因为语言支持全局数据和goto，就使用它们。要避免用这些有危险的编程特性，而代之以编程规范来弥补语言的弱项。编程要使用所用语言里最显而易见的方式。这等于说是“如果Freddie从桥上跳下来，难道你也愿意跳吗？”认真考虑你的技术目标，然后确定如何用你的语言最好地实现这些目标。 你的语言不支持断言？那就编写自己的assert()子程序，也许功能上与内置的assert()不完全一样，但你仍能实现其大部分用处。你的语言不支持枚举类型或具名常量？不碍事，可以按一定方式用全局变量定义自己的枚举或具名常量，只要有清楚的命名规范。 所有的人都在说：“语言不重要，重要是思想。”理论上这句话并不算错，但很少有人深入探讨这个问题的细节。 在不同的编程语言里，有一些东西是相通的，了解这些东西，就是了解编程的思想。但是这并不意味着，你一旦掌握了他们就能够精通所有的编程语言。每一门编程语言都在解决某些问题上有独到之处，这也是它们存在的意义。必须深入地学习需要掌握的语言，尽量透彻地掌握它的细节。在另一门语言上的经验有助于缩短你的学习过程，但不会取代学习过程。而深入了解一门语言的目的，正是为了用更好的方式贯彻编程思想。反过来，学习和实践一门优秀的语言，也会有利于你更深入地思考和理解编程的思想。
第33章，个人性格
正如第5章“软件构建中的设计”所提到的，Edsger Dijkstra在1972年的图灵奖演讲会上宣读了一篇名为《The Humble Programmer.》（谦卑的程序员）的文章。他认为大部分编程工作都旨在弥补我们有限的智力。精通编程的人是那些了解自己头脑有多大局限性的人，都很谦虚。而那些编程糟糕的人，总是拒绝接受自己脑瓜不能胜任工作的事实，自负使得他们无法成为优秀的程序员。承认自己智力有限并通过学习来弥补，你会成为更好的程序员。你越是谦虚，进步就越快。
个人性格和编码能力是否有关？这是一个象上去相当玄虚的问题，也是一个争议很大的问题（二者互为因果）。就我个人的经验而言，我见过的许许多多程序员，他们的技术水平和谦虚程度成严格的正比关系，无一例外。而且，当一个人的技术水平提高时，他的谦虚程度也会随之提高。这话听上去简直都不那么能令人相信。
我们已经见过了太多too smart的程序员和他们写下的代码。这些代码充斥着故作高深的思路和晦涩难懂的代码，并成为炫耀的资本。事实上，过于复杂的东西跟软件开发的本质是相悖的，因为“致力于降低复杂度是软件开发的核心”（第34章《软件工艺》）。优秀的程序员写下的代码，必定清晰、简洁、优雅。 正如本书中所说：“编程的整个过程如同建造空中楼阁一样——这是人们能做的纯粹脑力劳动之一。”（第33章《个人性格》）软件开发在某种意义上就是表达人对现实世界的理解，因此，一个伟大的程序员必定是一个伟大的哲学家。而伟大的哲学家都很明白人类理性的局限，这就是谦虚的来源。 如何编写高质量的代码
——来自《代码大全（第2版）》的启示
□ 编译/陈硕 软件的首要技术使命是管理复杂度，计算先驱Edsger Dijkstra指出，只有在“计算(Computing)”这种职业中，人的思维需要从一个字节大幅跨越到几百兆字节——跨度为109比1，也就是9个数量级1。Dijkstra还指出，没有谁的大脑能容得下一个现代的计算机程序，也就是说，作为软件开发人员，我们不应该试着在同一时间把整个程序都塞进自己的大脑，而应该试着以某种方式去组织程序，以便能够在一个时刻可以专注于一个特定的部分。这么做的目的是尽量减少在任一时间所要考虑的程序量，你需要同时记住的东西越多，就越可能漏掉其中的某一个，从而导致设计或编码的错误。 尽管谁都希望成为英雄，自如地应对各种计算机问题，但没有人的大脑真正有能力同时掌握9个数量级的细节。计算机科学和软件工程已经开发了许多智力工具，来应对这种复杂度，《代码大全》围绕这一主题作了详尽的讨论。 ◆ 在架构层将系统划分为多个子系统，以便让思绪在某段时间内能专注于系统的一小部分。（第5章） ◆ 仔细定义类接口，从而可以忽略类内部的工作机理。（第6.1节） ◆ 保持类接口的抽象性，从而不必记住不必要的细节。（第6.2节） ◆ 避免全局变量，因为它会大大增加总是需要兼顾的代码比例。（第13.3节） ◆ 避免深层次的继承，因为这样会耗费很大精力。（第6.3节） ◆ 避免深度嵌套的循环或条件判断，因为它们都能用简单的控制结构取代，后者占用较少的脑力资源。（第19.4节） ◆ 别用goto语句，因为它们引入了非顺序执行，多数人都不容易弄懂。（第17.3节） ◆ 小心定义错误处理的方法，不要滥用不同的错误处理技术。（第8.3节） ◆ 以系统的观点对待内置的异常机制，后者会成为非线性的控制结构。异常如果不受约束地使用，会和goto一样难以理解。（第8.4节） ◆ 不要让类过度膨胀，以至于占据整个程序。（第6章） ◆ 子程序应保持短小。（第7.4节） ◆ 使用清楚、不言自明的变量名，从而大脑不必费力记住诸如“i代表账号下标，j代表顾客下标，还是另有它意？”之类的细节。（第11章） ◆ 传递给子程序的参数数目应尽量少。更重要的是，只传递保持子程序接口抽象所必需的参数。（第7.5节） ◆ 用规范和约定来使大脑从记忆不同代码段的随意性、偶然性差异中解脱出来。（第4.2节，第31、32章） ◆ 只要有可能，一般情况下应避免“偶然性困难”2。（第5.2节） 如果将复杂的逻辑判断代码放入布尔函数，并将其意图概括出来，就可以降低代码的复杂程度（第19.1节）。用查表法代替繁琐的逻辑链，也能达到同样目的（第18章）。如果采用定义良好的一致的类接口，你就无须操心类的实现细节，从而整体上简化自己的工作。 采用编码规范主要也是为了降低复杂度。如果在格式编排、循环、变量命名、建模表示法等方面有统一的考虑，就能将精力集中于更具挑战性的编码问题上。规范最有用之处在于它们能免于你做出任意决定，省却了为之辩解的麻烦。 各种形式的抽象对于管理复杂度都是很强大的工具。通过增强程序组件的抽象性，编程领域已经取得了很大的进步。Fred Brooks指出，计算机的科学最了不起的成就，就是从机器语言跃进到高级语言，解放了程序员——我们不用再操心某种特定的硬件细节，而能够专心于编程。子程序的想法则是另一个巨大的进步，随后的重要进步是类和程序包。 以其功能对变量命名，说明问题是什么，而非其怎样实现，能提升其抽象层次。如果你说：“这是弹出栈，意味着我在取最近雇员的信息”，那么抽象使你可以省掉记住“弹出栈”的脑力步骤，你只需简单地说“我在取最近雇员的信息。”这一长进是微不足道的，但当你要减少从1到109这么大范围的复杂度时，任何改进措施都是值得的，勿以善小而不为。采用具名常量而非文字量（神秘数值）也能提高抽象级别。面向对象的编程方法提供同时适用于算法和数据的抽象，单靠功能分解做不到这一点。 总而言之，软件设计与构建的主要目标就是征服复杂度。许多编程实践背后的动机正是为了降低程序的复杂度。降低复杂度几乎是衡量程序员成果的最重要依据。这是《代码大全》体现的最主要的编程思想。（虽然这本书从头至尾没有正式提到过“编程思想”这个词。） 以上讨论“抽象”的文字本身也够抽象的，下面谈谈具体的、看得见摸得着的代码。 何谓“高质量的代码”
就“高质量的代码”而言，正确性、简单性、清晰性是首要的[SA04, Item 6]，可测试性也同样重要。清晰性（可读性）是“易于维护、易于重构的程序”最有价值的特性。若无法读懂代码，你就不能有信心地修改，也无法调试和修正错误。阅读代码的次数要比编写代码多得多，即使在开发的初期也是如此。 因此，为了让编写代码更方便而降低代码的可读性是非常不经济的。一项可读性原则是应该把修改你代码的人记在心上。编程首先是与人交流，其次才是与计算机交流。代码的维护者会感激你使代码容易理解——而且将来的维护者很可能就是你自己，到时候你得尝试记起自己六个月以前在想什么。 可测试性指的是能很方便地用自动化的手段来测试你的程序，把代码应有的功能用另一种形式（测试用例）描述一遍，等于给代码再加一道保险，降级出错的可能。下面两句话经常被引用来说明代码可读性的重要。 程序必须是写给人看的，仅仅偶尔才在机器上执行。——Harold Abelson等人[SICP] 编写程序首先为人，其次为计算机。——Steve McConnell[M04, Section 34.3] 与之相比，复用性、高效率就显得不那么重要，“使正确的程序变快”远远比“使快的程序变正确”容易得多[SA04, Item 8]。清晰的代码更容易写正确，更容易理解，更易于重构——因此更易于性能优化。 至于富于技巧(tricky)、聪明(clever)更可算是代码的恶劣品质，编程不是为了炫耀自己的聪明程度，这样写程序简直是歪门邪道。不能手里拿个铁锤，就把满世界都看成钉子。（比如在重载操作符的时候应该保持其自然语义，否则宁可用具名子程序来实现相同的操作。[SA04, Item 26]）Dijkstra在1972年的图灵奖演讲会上宣读了一篇名为《The Humble Programmer》（谦卑的程序员）的文章。 他认为大部分编程工作都旨在弥补我们有限的智力。精通编程的人是那些了解自己头脑有多大局限性的人，都很谦虚。而那些编程糟糕的人，总是拒绝接受自己脑瓜不能胜任工作的事实，自负使得他们无法成为优秀的程序员。研究表明，谦虚的程序员善于弥补其不足之处，使用能奏效的最简单的技术，所编写的代码让自己和他人都易看懂，其中的错误也较少。 调试代码的难度是首次编写这些代码的两倍。因此，如果你在编写代码的时候就已经发挥了全部聪明才智，那么按照常理，你将无法凭借自己的智慧去调试这些代码。——Brian Kernighan[KP78] 那么代码的可读性具体体现在哪些方面呢？大致有以下几点。一是名字，最常见的有类名、子程序名、变量名；二是长度，比如类的长度、数据成员的数目、子程序的长度、子程序的参数数目、语句的嵌套层数；三是复杂度，包括表达式的复杂度、语句逻辑的复杂度等；四是耦合度，包括由于共享数据（含全局数据）导致的耦合、类之间耦合（继承、组合、友元）、子程序之间的耦合等；五是格式，包括缩进、空格、注释等。 下面谈谈其中三点影响代码可读性的因素。 名不正则言不顺
“为变量命名”恐怕是编程中最普通的一项活动，一般介绍编程风格的书都会用几页的篇幅给出一些好的建议[KP99, Section 1.1]，而《代码大全》用了整整一章30多页的篇幅（第11章）来讨论变量的命名，另外第7.3节专门讨论子程序的命名，第6.2节讨论了类的命名。如果变量、子程序和类型命名得当，代码本身就能用作程序的文档，可以减少注释和外部文档（第32.2节）。 变量名 为变量命名时最重要的考虑事项是，该名字要完全、准确地描述出该变量所代表的事物。currentDate和todaysDate都是很好的名字，因为它们都完全而且准确地描述出了“当前日期”这一概念。事实上，这两个名字都用了非常直白的词。程序员们有时候会忽视这些普通词语，而它们往往却是最明确的。cd和c是很糟的命名，因为它们太短，同时又不具有描述性。current也很糟，因为它并没有告诉你是当前的什么。date看上去不错，但经过最后推敲它也只是个坏名字，因为这里所说的日期并不是所有的日期均可，而只是特指当前日期；而date本身并未表达出这层含义。x、x1和x2永远是坏名字——传统上用x代表一个未知量；如果你不希望你的变量所代表的是一个未知量，那么请考虑取一个更好的名字吧。 名字应该尽可能地明确。像x、temp、i这些名字都泛泛得可以用于多种目的，它们并没有像应该的那样提供足够信息，因此通常都是命名上的败笔。有人也许会反驳说，把i用作循环下标是最正常不过的了，难道非得写成indexOfTheLoop这种又臭又长的名字才算好吗？ Steve McConnell认为，如果循环只有寥寥数行，而且只是单层循环，那么用i是也是可行的。不过试想一下，如果你一直习惯用i作循环下标，而你将来可能需要把这个循环放到另一个循环中去执行，即循环嵌套，那么内外层循环都用i作下标肯定是不行的。如果编译器提醒你说变量i重复定义，那还算走运；如果编译器默不作声，而你自己又忘了修改，呃，你听见虫子飞舞的声音了吗？由于代码会经常修改、扩充，或者复制到其他程序中去，因此很多有经验的程序员索性不使用类似于i这样的名字。 如果循环不是只有几行，那么代码阅读者会很容易忘记i本来具有的含义，因此最好给循环下标换一个更有意义的名字。导致循环变长的常见原因之一是出现循环的嵌套使用。如果你使用了多个嵌套的循环，那么就应该给循环变量赋予更长的名字以提高可读性： for (int teamIndex = 0; teamIndex < teamCount; teamIndex++) {
for (int eventIndex = 0; eventIndex < eventCount[teamIndex]; eventIndex++){ score[teamIndex][eventIndex] = 0; } } 谨慎地为循环下标变量命名可以避免产生常见的下标串话（index cross-talk）问题：想用j的时候写了i，想用i的时候却写了j。同时这也使得数据访问变得更加清晰：score[teamIndex][eventIndex]要比score[i][j]给出的信息更多。 如果你一定要用i、j、k，那么不要把它们用于简单循环的循环下标之外的任何场合——这种传统已经太深入人心了，一旦违背该原则，将这些变量用于其他用途就可能造成误解。要想避免出现这样的问题，最简单的方法就是想出一个比i、j、k更具描述性的名字来。 变量名的最佳长度似乎应该介于x和maximumNumberOf PointsInModernOlympics之间。太短的名字无法传达足够的信息。诸如x1和x2这样的名字所存在的问题是，即使你知道了x代表什么，也无法获知x1和x2之间的关系。太长的名字很难写，同时也会使得程序的视觉结构变得模糊不清。 研究发现，当变量名的平均长度在10到16个字符的时候，调试程序所需花费的气力是最小的。平均名字长度在8到20个字符的程序也几乎同样容易调试。这项原则并不意味着你应该尽量把变量名的长度控制在9到15或者10到16个字符。它强调的是，如果你查看自己写的代码时发现了很多更短的名字，那么需要认真检查，确保这些名字含义足够清晰。 子程序名
好的子程序名字能清晰地描述子程序所做的一切。《代码大全》第7.3节列举并详细说明了若干条指导原则：描述子程序所做的所有事情，避免使用无意义的、模糊或表述不清的动词，不要仅通过数字来形成不同的子程序名字，根据需要确定子程序名字的长度，给函数命名时要对返回值有所描述，给过程起名时使用语气强烈的动词加宾语3的形式，准确使用对仗词，为常用操作确立命名规则等。 类名
类的名称应该表达了其中心目的，准确的描述该类的接口所模塑的抽象概念（第5.3节），一般用名词。 无论如何，命名不是一锤子买卖，一旦发现有更好的名称，借助现代的IDE工具（Eclipse或Visual Studio 2005），我们很容易对变量、常量、类、子程序进行重命名（rename），这恐怕也是用得最多的一项重构操作了。 宜短不宜长
很多编程书籍都告诉我们不要写过长的子程序[SA04, Item 20]，那么子程序写多长才合适呢？《代码大全》第7.4节专门讨论了这个问题。与一般书不同的是，McConnell不是以一个先知的口吻说“汝当如何如何”，而是列出了学术界的十多项研究成果，然后分析作结论。 有研究表明，子程序的长度与错误量成反比，即：随着子程序长度的增加（上至200行代码），每行代码所包含的错误数量就会减少。另一项研究则发现，子程序的长度与错误量没有关联，而结构复杂度以及数据量却与错误量有关。还有研究发现，短小的子程序（含有32行或更少代码）与更低的成本或错误率无关。有证据表明，较长的子程序（含有65行或更多代码）使得每行代码的成本更低。……IBM所做的一项研究发现，最容易出错的是那些超过500行代码的子程序。超过500行之后，子程序的出错率就会与其长度成正比。 这似乎与我们平时接受的“子程序越短越好”的教导相违背。McConnell认为，在任何时候，复杂的算法总会导致更长的子程序。在这种情况下，可以允许子程序的长度有序地增长到100至200行（不算源代码中的注释行和空行）。数十年的证据表明，这么长的子程序也和短小的子程序一样不易出错。与其对子程序的长度强加限制，还不如让其他因素——如子程序的内聚性、嵌套的层次、变量的数量、决策点的数量、解释子程序用意所需的注释数量以及其他一些跟复杂度相关的考虑事项等——来决定子程度的长度。 这就是说，如果要编写一段超过200行代码的子程序，那就要小心了。对于超过200行代码的子程序来说，没有哪项研究发现它能降低成本和/或降低出错率，而且在超过200行后，迟早会在可读性方面遇到问题。 不过，话说回来，在一开始写程序的时候，可以不必在意这个限制。在写完一个子程序，实现了应有的功能，并通过单元测试之后，如果它过长，我们可以很容易地用Extract Method重构法对它进行改进，使之符合项目编码标准中规定的子程序长度。 McConnell似乎对数字7情有独钟，他建议把子程序的参数个数限制在大约7个以内（第7.4节），告诉我们要警惕拥有超过约7个数据成员的类，并把基类的派生类总数（注意不是继承体系的层数）限制在7±2等（第6.3节）。当然，书中都给出了理由，这里就不赘述了。 格式与规范
《代码大全》第31章专门介绍代码的布局与风格，前面提到过，编码规范最有用之处在于让你避免做出武断决定，避免把时间花在无谓的争执上（第34.5节）。McConnell并不像一位“家具警察”那样对待代码的格式，他认为好的代码布局应凸现程序的逻辑结构，使代码易于阅读、理解、检查及修改。至于循环体应该缩进几个空格，大括号的摆放位置这些问题，正确答案不止一种。每次回答同样内容比起只是回答正确更重要。 第28.5节谈到了程序员的信仰问题，缩进风格、大括号的摆放位置、注释风格、命名习惯、对goto的使用、对全局变量的使用等等都是十分敏感的话题。关于这种问题，我觉得Herb Sutter和Andrei Alexandrescu的观点更贴近程序员的想法[SA04, Item 0]。 那些“仅仅是个人品味、而不影响正确性或可读性的”议题不应出现在编码标准中。任何一个专业的程序员都应该能轻易地阅读并编写“那种格式与自己的习惯略有不同的”代码。 每个源文件（甚至每个项目）内确保采用一致的编排格式，因为在同一块代码中切换若干种风格是很不和谐的。但是不要试图对多个项目（甚至对整个公司）强制使用相同的编排格式。 ◆ 不要指明缩进多少字符，但缩进要显出结构：你愿意用多少个空格来缩排都行，但至少每个文件保持一致。 ◆ 不要规定每行的长度，但确保可读性。 ◆ 不要规定注释的风格（某些工具将特定风格的注释提取为文档的情况除外），但一定编写有用的注释：只要有可能，尽量以代码代替注解。不要编写与代码重复的注解；这些注解会逐渐变得与代码不同步。一定编写说明性的注解，以解释所用的方法和基本原理。 …… 关于大括号的摆放，以下数种做法在可读性上没有区别： void using_k_and_r_style() {
// ... } void putting_each_brace_on_its_own_line() { // ... } void or_putting_each_brace_on_its_own_line_indented() { // ... } 如果你知道什么样的代码才是高质量的，那么怎样才能编写出这种代码呢？McConnell认为，好习惯很重要，因为程序员做的大部分事情都是无意识完成的（第33.9节）。例如，你曾想过该如何格式化缩进的循环体，但现在每当写新的循环体时就不再去想了，而以习惯的方式来做。对程序格式的方方面面几乎都是如此。你上次质疑编排风格是什么时候？如果你有五年编程经验，最后一次提出这个问题多半是在四年半之前，其余时间都是按习惯编程的。Bill Gates说过，任何日后出色的程序员在入行的前几年就做得很好，从那以后，程序员的优劣就定型了。其实任何行当都是如此，因此在初涉编程时，就应端正态度来学，尽快培养良好的习惯。 说明：这篇文章大量文字直接取自《代码大全（第2版）》中译本。 写在代码大全中文电子版之后
□ 文/徐勇
第一次阅读《代码大全》时，是在大约10年前(1995)， 我读大学低年级时。觉得读不懂，因为自己才刚刚抛弃Basic，开始学习C语言，除了一些习题，并没有多少编程的实际经验，书中的许多概念与方法都觉得非常陌生。随着一个DOS下的绘图软件RomanticPainter的开发，随着自己在开发这种较大软件时不断遇到到各种问题，就越来越觉得《代码大全》不但提供了关于代码创建的最丰富的实践指南，而且还像一位经验丰富的导师循序渐进地辅导你成为一个真正专业的软件开发者。 2000年4月，我在工作之余利用空闲时间，系统重读了《代码大全》，作了一个全书的内容摘要，便于随时看看其中的要点，提醒自己或者加深理解。这时更加发现这本书的价值，觉得非常需要向更多的程序员推荐这本书，然而这时候，这本书早就没有出版了。 这时我有了一个想法：将其扫描后，然后利用www.delphidevelopers.com网站发动大家OCR，然后校对后作为电子版供广大软件开发人员参考。于是我买了一台扫描仪。刚好在这个时候，我从一个论坛里看到在香港工作的Sequoia扫描了全部代码大全全书，于是便与他联系，托他回深圳的时候带过来。Sequoia扫描的图片应该是在图书馆里扫描的，质量很好，这为我们以后的OCR（光学字符识别）打下了很好的基础。 然后2000年年底的时候，便在www.delphidevelopers.com 上提出了制作电子版的倡议，并在几个BBS上发了一些消息。接着陆续收到了许多朋友的回复。2001年元旦的时候，项目正式开始了。当时项目的口号是：One For All, All For One ! 这是取自电影《三剑客》中三剑合一时三位剑客说的那句话，用在这里再恰当不过了。 化整为零。OCR，校对，汇编的工作被分割成许多小份，然后分派给每个志愿者。每个志愿者的名字与工作内容，发出日期，与送回日期都被公布在网上，便于大家对整个项目的进度有及时地了解。 人们总愿意在自愿而乐意的事情中投入更多的精力。所有的朋友都素昧平生，作为软件开发者，大部分人都是很忙的，需要在晚上抽出自己的休息时间，将图片利用OCR软件变成文本文件，然后再对照图片，将这些包含有不少错误的纯文本排版为与原书一样的版式，最后交回Word文档。 大家的热情都很高。 第一个志愿者是Wu Ke,OCR工作最多的志愿者是differ，一个人完成了4个人的工作；工作持续时间最长的是 dongfang7，他也有一本代码大全，遇到没有的图片，就自己扫描OCR了，从最初的OCR工作一直到最后的统校，都有他的热情的支持；最具执着精神的是叫ctx的朋友，由于没有收到图片，结果自己照着书，一个字一个字地敲上去；还有远在加拿大的hcqian，花了两个星期对测试版的前面10章进行了系统的检查，发现不少缺陷。 还有的朋友当日完成自己的任务，有的朋友工作至凌晨，有的朋友把书中的表格做得非常漂亮，有的朋友提出修改部分术语译法的建议，有的朋友一人完成几人的工作，有朋友认为这是一项享受而不是一项工作，还有朋友遗憾自己未能参加这个工作。 我也将许多晚上花在对送回来的Word文档的校对上，体会到编辑工作的不易，常常觉得老眼昏花。所以，拥有一本纸质的《代码大全》是一件多么保护视力的事！ 其间还收到过CSDN蒋涛先生的Email鼓励。 其实最终的电子版是来自天涯海角的近100位素不相识的朋友的热情和协作的成果。 盖茨说过微软最重要的财产就是代码。不错，软件开发中所有的关键活动，最终的目的都为了能够创建出正确的健壮的最好用的代码。而这本书，10年前写的书，至今仍未过时，因为它所探讨的内容不是表面的现象，而是关于代码创建的内在本质与规律。毫不夸张地说，这是世界上关于代码创建的最为丰富最为深刻的实践指南。 《代码大全》书评
□ 文/徐勇 《代码大全(第二版)》——软件构建实用手册 编程既不完全是艺术，也不完全是科学。归因于其实践过程，它是介于艺术和科学之间的“工艺”。 —— Steve McConnell 《代码大全（第二版）》必将在每个开发者的计算机书架上熠熠发光。书的每一页都体现了通过多年高效编程经历才能得到的深遽眼光，它仍将是软件构建实践者的主要手册。项目领导应当从头至尾读读这本书，然后为其手下每人买上一本。您所在项目的软件品质将因此而有所提高。 软件大师Steve McConnell的成名之作很可能是《代码大全》——一本软件构建的实用手册。（McConnell总是以“软件构建”来描述软件开发）。《代码大全》前所未有地影响了我对软件开发的思维方式。我知道内容有些琐碎，但要是哪本技术书堪称“即刻经典”的话，那么非此书莫属。这正是我殷切期待《代码大全》第二版的原因。如果您从未听说过《代码大全》，不要以为它高深莫测——该书并不像CMMI那样大谈软件开发的标准，而是为程序员的实践提供实用建议。它致力于深入设计、测试和集成方面的编码和调试问题。 在该书的前言里列出了其九点主要益处，每一点都和作者主张一致。比如，该书是完整的软件开发参考书、即时可用的自我检查表、软件开发的透视，没有夸夸其谈。这本书通过自顶向下的方法循循善诱读者，从蓝图和设计讲起，深入合适的变量和语句命名方法和用法，最后来到改进代码的广阔世界（问答、测试、调试、重构和调整）、系统考虑（大小、集成度和工具），还有软件工艺的终极内容。 像一本好的业务书那样，《代码大全（第二版）》有许多读者承认好却懒得做的规则。在阅读循环次数变量应命名为有意义的名字时，我只能笑一笑。CS-101课程曾斥责那种乱取变量名的憋脚作法，编程新手应对循环变量的命名约定铭记在心。如同贯穿本书的其它方面，对命名的推荐作法强调了共同的主题——写代码就要像编重要文档那样小心翼翼、考虑周全。思路和组织越清晰越好。 除了彻底的重塑外，新版本还将过了时的C和Pascal代码示例多数替换为C++，有些是Java，还有少量的Visual Basic代码。和前面一版相同，这些例子所用的语言并不重要，只是为了说明演示的原理。网络的威力也在此得到了发挥，书中的页边空白处会时不时标一些能够直接访问的网址，来说明某些概念或提供检查表。并且承袭了McConnell以往所写书的风格，配套的网站（在Apache Web server下用PHP所写）和书有同样价值的参考作用。然而，不像先前书的网站，cc2e.com要求访问者在打开其知识宝库前，要注册或得到Construx网站会员资格。 程序员 在你的生涯中应养成良好的编程习惯，越早越好。如果你是学生，或者自学、想把事情做好，建议你马上阅读《代码大全》的下列几章： 第7章“高质量子程序”—— 该章剖析子程序的方方面面，话题涵盖创建子程序的理由、子程序的长度、子程序名等等。 第15章“使用条件语句”—— 该章论及if和case语句的正确用法。 第16章“控制循环”—— 该章说明for、while和foreach循环结构的控制方法。 对于老手们，作者则提供了调试、代码调整策略、程序源代码的布局和风格、罕用数据类型（结构、指针和全局数据）和协作构建（用以与其他程序员合作）。 管理人员
该书并不面向管理。不过，“管理构建”一章大概足以让管理者从开发人员那里借来《代码大全》看看。为了避免一大堆问题，应要求新手管理者，尤其是没有技术背景的新管理人员读一读“把程序员当人看（Treating Programmers as People）”一节。 批判者
《代码大全》并非没有批判者。有人抱怨1993年出版的第一版没有面向对象的编程方法（OOP）。1993年时OOP还是新颖的玩艺儿，所以第一版对此确实没有提及。现在McConnell对《代码大全》加入了“工作类”一章，后者含有创建高质量类的精华建议。这本书完全是OOP的气息。书中数不清的好坏编码示例都用Visual Basic、Java、C++、C#和C重新编写（这里“坏”指的是那些提供编码禁忌的示例）。 另外一些批评者说书“只是对学校东西的老调重弹”，或者“尽是些老掉牙的东西，谁都知道。”这些评论者的确受过良好教育，但并非每个人都知道该如何做。我赞赏McConnell，不仅是因为他把这些知识编纂成册，更归功于他的书包括了要点和自我检查表。 要点和自我检查表穿插于文中，归纳出McConnell认为是重要的地方。正如有经验的飞行员起飞前要做各项检查，软件开发者在发布代码前，可以使用McConnell的自我检查表。即使你不完全赞同作者的观点，该书可能促使你创建自己的开发检查表。 购买者
你还没有自己的《代码大全》书吗？然而，如果你已有第一版的话，是否该买第二版就不太好说了，因为作者认为仍有95%的内容与第一版相关。要想了解更多内容，请查看《代码大全》第二版网页上作者“关于第二版的说明”之内容，也可以看到第二版的目录、前言和第1、5章。 这本书说的是软件开发中常被忽视之处：代码的写法。它并不针对某种特定语言、编程范例或开发方法，也并非讲的是通用标记语言（UML）、设计模式或数据结构，而是编码、低层设计、命名规范等等所有我们花费太多时间，多数开发书却闭口不谈的东西。从这个意义上说，Steve McConnell的《代码大全》相当独特，第一版刚被奉若神明，又有了新一版，拓展了原书的内容，巩固了该书的权威地位。 在涵盖代码构建各个方面的同时，这部巨著充满着明智的建议、示例代码、无可辩驳的事实和有力的论据。通过无数新闻报纸和学术研究中的数据，结合争战故事和轶闻，该书下功夫来说服读者，而不是靠强词夺理来做到这一点。McConnell意在帮助读者成为更好的开发人员，但他希望采用劝说而不是说教的办法。这也是该书成为一本优秀书的原因之一。 话题组织成七个不同的部分，从软件构建到伪代码的用法，到变量的命名，再到代码的编排等等。资料的安排很广泛，所以即使变量命名的话题就单独占了有用且有趣的一章。信仰意义之类的话题（如代码编排）也有所提及。 我们可以对本书逐节考察其概要，但这样做对本书尚不能物尽其用。最好是着重于文中的若干关键主题。首当其冲的就是复杂性问题。克服复杂性是卓越开发者追求的重要目标——这就意味着应当写组织精良、易懂易维护的代码；意味着不要写花俏却是维护恶梦的代码。 这一原则可延伸到所其次是要牢记代码通常看的次数要比写的次数多。因而应确保代码是可读懂的，同理要注意程序结构、命名规范的使用及注释代码等等。有地方，从如何命名子程序到怎样编排代码，还有另一个重要之处是最好的开发者总在不断自我发展和学习。所以要奋力完善自己，对自己做的事有清醒认识，关注业界的动态，不要夜郎自大。变量该如何称谓。 书中的精彩资料太丰富了，以致于难以简单地评述之。希望进步的开发者都该阅读此书。对它的推我期待过《代码大全》第二版在6月8日的问世，每个开发者都该有一本此书。现在我已拿到手一个星期，并读了约一半内容。可以说这本书比它的第一版还要好。它以C++和Java等现代语言更新了内容，绝对是软件构建方面无与伦比的书籍……阅读此书我还将能学到很多知识，强烈推荐！无以言表。 来源:http://www.cc2e.com.cn October 25 RFC3092 "Foo" 的词源组织：中国互动出版网（http://www.china-pub.com/） RFC文档中文翻译计划（http://www.china-pub.com/compters/emook/aboutemook.htm） E-mail：ouyang@china-pub.com 译者：流浪猫（neko neko@126.com） 译文发布时间：2001-4-8 版权：本中文翻译文档版权归中国互动出版网所有。可以用于非商业用途自由转载，但必须保留本文档的翻译及版权信息。 Network Working Group D. Eastlake 3rd Request for Comments: 3092 Motorola Category: Informational C. Manros Xerox E. Raymond Open Source Initiative 1 April 2001 RFC3092 "Foo" 的词源
(RFC3092 Etymology of "Foo") 目录
1. 介绍 2 2. 定义和语源 2 3. 缩写 5 附录 6 安全考虑 11 参考 11 作者的地址 13 完整的版权声明 14 鸣谢 14 1. 介绍
至今约有212 个RFC， 或者约7%的RFC， 从[RFC269]开始，包括了术语''''foo'''', ''''bar'''' 或''''foobar''''作为伪变量而没有任何适当的解释或定义。这可能被认为是 微不足道的，但一些新来者，特别是那些非英语国家的人，在理解这些术语时 会遇到困难。本文纠正这一问题。 下面的第二节描述了这些词定义和语源，第三节把它们作为缩写词进行了解释。
在附录中，包括了这些词作为伪变量在RFC 中出现位置的表格。 2. 定义和语源 bar /bar/ n. [JARGON] 1. 第二个伪变量，在foo 之后而在baz 之前。
"Suppose we have two functions: FOO and BAR. FOO calls BAR...." 2. 经常加在foo 后面构成foobar。
foo /foo/
1. interj. 令人反感的术语。
2. 用于任何东西的一般的名称，特别是程序和文件（特别是草稿文件）。
3. 用于语法例释的标准伪变量表中的第一个(bar, baz, qux, quux, corge,
grault, garply, waldo, fred, plugh, xyzzy, thud). [JARGON] 当连接''''bar'''' 时通常可以追溯到二战时军中的俚语FUBAR (`Fucked Up
Beyond All Repair'''')， 最后演变成了foobar。早期版本的Jargon File [JARGON]称这一变化是战后的修正，但现在看来更像是FUBAR 本身是''''foo'''' 的衍生词。可能是受到了德语''''furchtbar''''（可怕的） 的影响 -- 也许最 初形式是''''foobar''''。 似乎''''foo'''' 这个词在战前的漫画和卡通中可以找到历史。在1938年华纳兄
弟卡通公司Robert Clampett 指导的"The Daffy Doc"，Daffy Duck 的早 期版本，有一句口号"SILENCE IS FOO!"。''''FOO''''和''''BAR'''' 也在Walt Kelly
的连环漫画"Pogo"中出现。最早有文献记载的使用是在Bill Holman 的描 写一个消防队员的超现实主义连环漫画"Smokey Stover" 中。在1930到 1952年间该连环漫画出现在许多美国漫画中，包括"Everybody''''s"。 它经 常在汽车的车牌中包含单词"FOO"， 在背景画面中无意义的话中，如"He who foos last foos best"或"Many smoke but foo men chew"，Smokey 说"Where there''''s foo, there''''s fire"。Bill Holman，该漫画的作者， 在其中充满了奇妙的笑话和个人发明，包括其它无意义的短语如"Notary Sojac"和"1506 nix nix"。依照华纳兄弟卡通公司[WBCC]的说法，Holman
是在一个中国小雕像的底部发现"foo" 这个词的。这是个似是而非的说法； 中国的小雕像经常有避邪用的题字，这可能是中文''''fu''''（有时候音译为 ''''foo''''）， 当发音正确时意为“幸福”（立在许多中餐馆侧面的狮子--狗型 守护神正确的称呼是"fu dogs"）[PERS]。 说英语的人认为Holman的''''foo'''' 这个无意义的词毫无疑问的受到Yiddish 语的''''feh'''' 和英语的''''fooey'''' 以 及''''fool''''的影响。[JARGON, FOLDOC] Holman的漫画描写了一台两轮消防车名叫Foomobile。 该系列漫画在1930
年代后流行极了，传说Indiana 的一个制造商甚至造出了一台可操作的 Foomobile。 按照美国漫画百科全书[EAC] 的说法，''''Foo'''' 热横扫美国， 在流行歌曲和超过500个‘Foo 俱乐部‘ 中可以找到证据。作为流行的遗迹 ''''foo'''' 嵌入了流行文化（包括华纳兄弟卡通公司1938-39的the couple of appearances） 但它的起源被迅速遗忘了。[JARGON] 二战后该术语在美国军队仍存留下来。在1944-45 年，术语''''foo
fighters''''[FF] 被雷达操作员用来描述一种神秘的或伪造的轨迹。那后来 被称为UFO（ 在1995年通过一个叫Better grunge-rock bands[BFF] 的词 老的术语又重新露面）。据信它和漫画Smokey Stover 有关[PERS]。 战争中美国和英国军队经常交换俚语。Period sources报告说二战中''''FOO''''
变成了半传奇式的主题，英国军队的涂鸦或多或少等于美国的Kilroy [WORDS]。 英国军队走到哪里，都会涂上"FOO was here"或者类似的话。 几本俚语字典断言FOO 来自前线巡查官，但这（像同时代的"FUBAR"）也许 是backronym[JARGON]。 40年后，Paul Dickson的优秀著作"Words" [WORDS]追踪"Foo"到了一个不明的英国海军杂志，引用如下： "Mr. Foo is a mysterious Second World War product, gifted with
bitter omniscience and sarcasm." 更早版本的Jargon File 暗示其用法的可能来自"FOO, Lampoons and
Parody"，1958 年发行的一本漫画的标题，Charles 和Robert Crumb合作 的一个项目。 尽管Robert Crumb（在他后来十几年）后来成了最重要最有影响力的地下
漫画作家，这次成功相当艰难；实际上，因为厌恶，兄弟俩后来烧掉了大 部分的拷贝。标题FOO 用大号字印在封面上。然而，非常少的拷贝确实流 传了下来，Crumb ‘全集’的学生确定它参考的是较早的Smokey Stover 漫 画。Crumb的作品可能也受到1951-52年出版的的短命加拿大滑稽杂志 "Foo"的影响[JARGON]。 一个old-time成员报告说在1959年TMRC（MIT 的技术模型铁路俱乐部）编
译的“TMRC语言字典” 中有Foo 的词条。当前在线版本中的"Foo" 是唯一 标记为红色的词，有如下内容[TMRC]： Foo: The sacred syllable (FOO MANI PADME HUM); to be spoken
only when under obligation to commune with the Deity. Our first obligation is to keep the Foo Counters turning. 这个定义用了Bill Holman 的无意义的词，流行之后20年且确实存在流行
文化和俚语中，使一个"ha ha only serious"象西藏佛教一样深奥。今天 的人会发现很难抵挡这样精心制作的笑话，而不象1959年代的人那样不易 受感染。[JARGON] 4. [EF]王子Foo 是Pheebor 最后的统治者，和Phee Helm 的所有者，在
rgign of Entharion之前约400 年。当Foo 被来自Borphee 的叫作 "eastern fop" 的什么人砍头时，Pheebor 的显赫时代结束了，而Borphee 越升到它现在的位置。 5. [OED] 一个13-16 世纪用法，指恶魔或任何敌人。最早的引用是在1366
年，Chaucer A B C (84): "Lat not our alder foo [devil] make his bobance [boast]"。Chaucer的"Foo"可能是现代英语的"foe" 6. 稀有种类的狗
波美拉尼亚丝毛狗被认为灭绝很长时间后又被发现了，中国的Foo 狗，或
新疆的神狗，可能起源于越过北欧的猎狗和远古的蒙古中国狗或者中国狼 和中国狗的杂交种。它可能由foochow， 或流行在Foochow 的种或风格， 或者从中国东南部城市Foochow （现在Minhow）得名。[DOG] foobar n. [JARGON]广泛使用的伪变量；语源参考foo。 最初可能在60年代到70年代
早期通过数字设备公司(DEC) 的DEC 系统手册传播的；能确证的目击例可 以追溯到1972年。热心者一般不使用其表示FUBAR， 无论是作为俚语还是 作为专业术语。这似乎暗示"foobar"部分的在早期计算机工程师中传播， 由于FUBAR，部分也因为"foo bar"听起来象电子技术术语反转的foo信号。 foo-fighter n.
二战术语，德英双方都用于表示不明飞行物(UFO)。参看foo词条对[FF]的
说明。 3. 缩写 下面信息主要来自Cork大学<http://www.ucc.ie/acronyms>和缩写发现者 <http://www.AcronymFinder.com>用于一般计算机用途。 .bar: 一般文件扩展名，不暗示任何文件类型。 BAR: 基地址寄存器(Base Address Register) 缓冲区地址寄存器(Buffer Address Register) FOO: 转送观察观察员(Forward Observation Observer) FOO Of Oberlin. 一个缩写名为递归词的组织。Motto: The FOO, the Proud, the FOO. 参看 <http://cs.oberlin.edu/students/jmankoff/FOO/home.html>。 为输出打开文加(File Open for Output)。一个NFILE错误码[RFC1037]。 FOOBAR: FTP 在大地址记录上的操作[RFC1639]。 （特别恰当的使用"foo" 的第一 个RFC，[RFC269]，也是关于文件传输的） FUBAR: 失败的统一总线地址寄存器(Failed UniBus Address Register) - 在 VAX 中，来自数字设备公司工程师。 Fucked Up Beyond All Recognition/Repair - 来自二战时的美国军队。 有时候简化成"Fouled Up ..."。 FUBARD - FUBAR 的过去式 附录 下表列出了这些词在RFC 中作为伪变量的使用（这不包括合理的使用如 "vertical bar"或 "bar BoF"）。许多用途是作为域名例。这用用法会减少， 因为[RFC2606]中作为当前最佳经验提出了用于举例用的域名。 +------+-----+-----+---------+-------+-----+
| RFC# | bar | foo | foo.bar | fubar | # | | | | | foobar | | | +------+-----+-----+---------+-------+-----+ | 269 | X | X | | | 1 | | 441 | X | X | | | 2 | | 614 | | X | | | 3 | | 686 | | X | | | 4 | | 691 | | X | | | 5 | | 733 | X | X | | | 6 | | 742 | | X | | | 7 | | 743 | X | X | | | 8 | | 756 | | X | | | 9 | | 765 | X | X | | | 10 | | 772 | X | X | | X | 11 | | 775 | | | X | | 12 | | 780 | X | X | | X | 13 | | 788 | X | X | | | 14 | | 810 | X | X | X | | 15 | | 819 | | X | | | 16 | | 821 | X | X | | | 17 | | 822 | X | X | | | 18 | | 882 | X | X | | | 19 | | 883 | | X | | | 20 | | 897 | X | X | | | 21 | | 913 | | X | | | 22 | | 921 | X | X | | | 23 | | 934 | | X | | | 24 | | 952 | X | X | X | | 25 | | 959 | | | X | | 26 | | 976 | | | X | | 27 | | 977 | | X | X | | 28 | | 987 | | | X | | 29 | | 1013 | | X | | | 30 | | 1033 | X | X | | | 31 | | 1035 | | X | | | 32 | | 1037 | | X | | | 33 | | 1056 | X | X | X | | 34 | | 1068 | | X | | | 35 | | 1137 | | | X | | 36 | | 1138 | | X | X | | 37 | | 1148 | | X | X | | 38 | | 1173 | | | X | | 39 | | 1176 | | | X | | 40 | | 1186 | | X | | | 41 | | 1194 | | X | | | 42 | | 1196 | | X | | | 43 | | 1203 | | X | X | | 44 | | 1288 | | X | | | 45 | | 1291 | | X | | | 46 | | 1309 | | X | | | 47 | | 1327 | | X | X | | 48 | | 1341 | X | X | X | | 49 | | 1343 | | X | X | | 50 | | 1344 | | X | | | 51 | | 1348 | | | X | | 52 | | 1386 | | X | | | 53 | | 1408 | | X | | | 54 | | 1411 | | X | | | 55 | | 1412 | | X | | | 56 | | 1459 | X | X | X | X | 57 | | 1480 | | X | | | 58 | | 1505 | | X | | | 59 | | 1519 | | X | | | 60 | | 1521 | X | X | | | 61 | | 1523 | | X | | | 62 | | 1524 | | X | X | | 63 | | 1526 | X | X | | | 64 | | 1535 | X | X | X | | 65 | | 1536 | X | | X | | 66 | | 1537 | | X | X | | 67 | | 1563 | | X | | | 68 | | 1564 | | | X | | 69 | | 1572 | | X | | | 70 | | 1573 | | X | | | 71 | | 1622 | | X | | | 72 | | 1635 | | | X | | 73 | | 1636 | | X | X | | 74 | | 1642 | | X | | | 75 | | 1645 | | | X | | 76 | | 1649 | | X | | | 77 | | 1664 | | | X | | 78 | | 1681 | | | X | | 79 | | 1697 | | X | | | 80 | | 1716 | | X | | | 81 | | 1718 | | X | | | 82 | | 1730 | X | X | X | | 83 | | 1734 | | | X | | 84 | | 1738 | | X | | | 85 | | 1783 | | | X | | 86 | | 1784 | | | X | | 87 | | 1786 | X | X | | | 88 | | 1813 | X | X | | | 89 | | 1835 | | X | X | | 90 | | 1856 | | | X | | 91 | | 1861 | | | X | | 92 | | 1866 | | X | | | 93 | | 1894 | | | X | | 94 | | 1896 | | X | | | 95 | | 1898 | | X | | | 96 | | 1913 | | X | X | | 97 | | 1945 | X | X | | | 98 | | 1985 | | X | X | | 99 | | 2015 | X | X | | | 100 | | 2017 | | X | | | 101 | | 2033 | X | X | | | 102 | | 2045 | | | X | | 103 | | 2046 | X | X | | | 104 | | 2049 | X | X | | | 105 | | 2055 | | X | | | 106 | | 2060 | X | X | X | | 107 | | 2065 | | X | | | 108 | | 2068 | | | X | | 109 | | 2071 | | X | | | 110 | | 2088 | | | X | | 111 | | 2109 | | X | | | 112 | | 2110 | | X | X | | 113 | | 2111 | X | X | X | | 114 | | 2141 | | X | | | 115 | | 2150 | | X | | | 116 | | 2152 | | X | | | 117 | | 2156 | | X | X | | 118 | | 2163 | | | X | | 119 | | 2167 | | | X | | 120 | | 2168 | | | X | | 121 | | 2169 | | | X | | 122 | | 2180 | X | X | | | 123 | | 2193 | X | X | | | 124 | | 2224 | | X | | | 125 | | 2227 | X | X | | | 126 | | 2233 | | X | | | 127 | | 2234 | X | X | X | | 128 | | 2243 | | X | | | 129 | | 2255 | | X | X | | 130 | | 2280 | X | X | | | 131 | | 2295 | | X | | | 132 | | 2302 | | X | | | 133 | | 2311 | X | | | | 134 | | 2326 | X | X | X | | 135 | | 2342 | | X | | | 136 | | 2348 | | | X | | 137 | | 2349 | | | X | | 138 | | 2359 | | | X | | 139 | | 2369 | X | X | X | | 140 | | 2378 | | X | | | 141 | | 2384 | | | X | | 142 | | 2392 | X | X | X | | 143 | | 2396 | | | X | | 144 | | 2401 | | | X | | 145 | | 2407 | | | X | | 146 | | 2421 | | X | | | 147 | | 2425 | | | X | | 148 | | 2434 | | X | | | 149 | | 2446 | | X | X | | 150 | | 2447 | X | X | | | 151 | | 2458 | | X | X | | 152 | | 2459 | | | X | | 153 | | 2476 | | X | | | 154 | | 2483 | X | X | | | 155 | | 2486 | | X | | | 156 | | 2505 | X | X | | | 157 | | 2518 | X | X | X | | 158 | | 2535 | | X | | | 159 | | 2538 | | X | | | 160 | | 2543 | X | X | X | | 161 | | 2554 | | | X | | 162 | | 2557 | | X | X | | 163 | | 2565 | | X | X | | 164 | | 2569 | X | X | | | 165 | | 2593 | X | X | | | 166 | | 2595 | | X | | | 167 | | 2608 | | X | | | 168 | | 2609 | | X | | | 169 | | 2616 | X | X | X | | 170 | | 2622 | X | X | | | 171 | | 2626 | | X | | | 172 | | 2633 | X | | | | 173 | | 2640 | | X | X | | 174 | | 2645 | | | X | | 175 | | 2650 | X | | | | 176 | | 2659 | | | X | | 177 | | 2673 | | X | X | | 178 | | 2693 | | X | | | 179 | | 2704 | X | X | | | 180 | | 2705 | X | X | | | 181 | | 2717 | | X | X | | 182 | | 2725 | X | X | | | 183 | | 2731 | X | X | X | | 184 | | 2732 | | X | | | 185 | | 2782 | | X | X | | 186 | | 2803 | | X | | | 187 | | 2806 | | X | | | 188 | | 2812 | X | X | X | X | 189 | | 2818 | X | X | | | 190 | | 2828 | | X | X | | 191 | | 2830 | X | | | | 192 | | 2831 | X | X | X | | 193 | | 2839 | | X | | | 194 | | 2846 | X | X | | | 195 | | 2853 | | X | | | 196 | | 2863 | | X | | | 197 | | 2910 | | X | X | | 198 | | 2912 | | X | X | | 199 | | 2915 | | X | | | 200 | | 2926 | | | X | | 201 | | 2942 | | X | | | 202 | | 2965 | | X | | | 203 | | 2967 | X | X | X | | 204 | | 2970 | | X | | | 205 | | 2993 | X | X | | | 206 | | 3010 | X | X | | | 207 | | 3023 | | X | | | 208 | | 3028 | | X | | | 209 | | 3075 | X | X | | | 210 | | 3080 | | X | | | 211 | | 3092 | X | X | X | X | 212 | +------+-----+-----+---------+-------+-----+ | RFC# | bar | foo | foo.bar | fubar | # | | | | | foobar | | | +------+-----+-----+---------+-------+-----+ 安全考虑 本文不讨论安全问题。 参考 [BFF] "Best of Foo Fighters: Signature Licks", Troy Stetina, Foo Fighters, October 2000, Hal Leonard Publishing Corporation, ISBN 063401470. [DOG] <http://www.rarebreed.com/breeds/foo/foo.html>. [EAC] "Encyclopedia of American Comics", Ron Goulart, 1990, Facts on File. [EF] "Encyclopedia Frobozzica", <http://www.everything2.com/index.pl?node=Prince%20Foo> [FF] Foo Fighters - "The Rainbow Conspiracy", Brad Steiger, Sherry Hansen Steiger, December 1998, Kensington Publishing Corp., ISBN 1575663635. - Computer UFO Network <http://www.cufon.org> particularly <http://www.cufon.org/cufon/foo.htm>. [FOLDOC] "Free On-Line Dictionary Of Computing", <http://www.foldoc.org>. [JARGON] The Jargon File. See <http://www.jargon.org>. Last printed as "The New Hacker''''s Dictionary", Eric S. Raymond, 3rd Edition, MIT Press, ISBN 0-262-68092-0, 1996. [OED] "The Oxford English Dictionary", J. A. Simpson, 1989, Oxford University Press, ISBN 0198611862. [PERS] Personal communications. [RFC269] Brodie, H., "Some Experience with File Transfer", RFC 269, December 1971. [RFC1037] Greenberg, B. and S. Keene, "NFILE - A File Access Protocol", RFC 1037, December 1987. [RFC1639] Piscitello, D., "FTP Operation Over Big Address Records (FOOBAR)", RFC 1639, June 1994. [RFC2606] Eastlake, D. and A. Panitz, "Reserved Top Level DNS Names",
BCP 32, RFC 2606, June 1999. [TMRC] The Tech Model Railroad Club (The Model Railroad Club of the Massachusetts Institute of Technology) Dictionary, <http://tmrc-www.mit.edu/dictionary.html>. [WBCC] "Warner Brothers Cartoon Companion", <http://members.aol.com/EOCostello/>. [WORDS] "Words", Paul Dickson, ISBN 0-440-52260-7, Dell, 1982. 作者的地址 Donald E. Eastlake 3rd Motorola 155 Beaver Street Milford, MA 01757 USA Phone: +1 508-261-5434 (w)
+1 508-634-2066 (h) Fax: +1 508-261-4777 (w) EMail: Donald.Eastlake@motorola.com Carl-Uno Manros
Xerox Corporation 701 Aviation Blvd. El Segundo, CA 90245 USA Eric S. Raymond
Open Source Initiative 6 Karen Drive Malvern, PA 19355 Phone: +1 610-296-5718
EMail: esr@thyrsus.com 完整的版权声明 Copyright (C) The Internet Society (2001). All Rights Reserved. This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 鸣谢 Funding for the RFC Editor function is currently provided by the Internet Society. October 06 正则表达式学习笔记[转载] 正则表达式(regular expression)描述了一种字符串匹配的模式，可以用来检查一个串是否含有某种子串、将匹配的子串做替换或者从某个串中取出符合某个条件的子串等。
列目录时， dir *.txt或ls *.txt中的*.txt就不是一个正则表达式,因为这里*与正则式的*的含义是不同的。 为便于理解和记忆，先从一些概念入手，所有特殊字符或字符组合有一个总表在后面，最后一些例子供理解相应的概念。
正则表达式是由普通字符（例如字符 a 到 z）以及特殊字符（称为元字符）组成的文字模式。正则表达式作为一个模板，将某个字符模式与所搜索的字符串进行匹配。 可以通过在一对分隔符之间放入表达式模式的各种组件来构造一个正则表达式，即/expression/ 普通字符由所有那些未显式指定为元字符的打印和非打印字符组成。这包括所有的大写和小写字母字符，所有数字，所有标点符号以及一些符号。 非打印字符
特殊字符所谓特殊字符，就是一些有特殊含义的字符，如上面说的"*.txt"中的*，简单的说就是表示任何字符串的意思。如果要查找文件名中有＊的文件，则需要对＊进行转义，即在其前加一个\。ls \*.txt。正则表达式有以下特殊字符。
限定符限定符用来指定正则表达式的一个给定组件必须要出现多少次才能满足匹配。有*或+或?或{n}或{n,}或{n,m}共6种。 *、+和?限定符都是贪婪的，因为它们会尽可能多的匹配文字，只有在它们的后面加上一个?就可以实现非贪婪或最小匹配。 正则表达式的限定符有：
定位符用来描述字符串或单词的边界，^和$分别指字符串的开始与结束，\b描述单词的前或后边界，\B表示非单词边界。不能对定位符使用限定符。 选择用圆括号将所有选择项括起来，相邻的选择项之间用|分隔。但用圆括号会有一个副作用，是相关的匹配会被缓存，此时可用?:放在第一个选项前来消除这种副作用。 其中?:是非捕获元之一，还有两个非捕获元是?=和?!，这两个还有更多的含义，前者为正向预查，在任何开始匹配圆括号内的正则表达式模式的位置来匹配搜索字符串，后者为负向预查，在任何开始不匹配该正则表达式模式的位置来匹配搜索字符串。 后向引用对一个正则表达式模式或部分模式两边添加圆括号将导致相关匹配存储到一个临时缓冲区中，所捕获的每个子匹配都按照在正则表达式模式中从左至右所遇到的内容存储。存储子匹配的缓冲区编号从 1 开始，连续编号直至最大 99 个子表达式。每个缓冲区都可以使用 '\n' 访问，其中 n 为一个标识特定缓冲区的一位或两位十进制数。 可以使用非捕获元字符 '?:', '?=', or '?!' 来忽略对相关匹配的保存。 各种操作符的运算优先级相同优先级的从左到右进行运算，不同优先级的运算先高后低。各种操作符的优先级从高到低如下：
全部符号解释
部分例子
欲了解更多，请参考网站：
August 31 影响算法世界的十位大师(图)[转载]Don E. Knuth 伟大的智者——Don E.Knuth，中文名：高德纳(1938-)算法和程序设计技术的先驱者。Oh,God!一些国外网站这样评价他。一般说来，不知道此人的程序员是不可原谅的。其经典著作《计算机程序设计艺术》更是被誉为算法中“真正”的圣经，像KMP和LR(K)这样令人不可思议的算法，在此书比比皆是。难怪连 Bill Gates都说：“如果能做对书里所有的习题，就直接来微软上班吧！” 对于Don E.Knuth本人，一生中获得的奖项和荣誉不计其数，包括图灵奖，美国国家科学金奖，美国数学学会斯蒂尔将（AMS Steel Prize），以及发明先进技术荣获的极受尊重的京都奖（KyotoPrize）等等，写过19部书和160余篇论文，每一篇著作都能用影响深远来形容。 Don E.Knuth也被公认是美国最聪明的人之一。当年他上大学的时候，常写些各种各样的编译器来挣外快，只要是他参加的编程比赛，总是第一名，同时也是世上少有的编程达到40年以上的程序员之一。他除了是技术与科学上的泰斗外，更是无可非议的写作高手，技术文章堪称一绝，文风细腻，讲解透彻，思路清晰而且没有学究气，估计这也是《计算机程序设计艺术》被称为圣经的原因之一。 ·Edsger Wybe Dijkstra 谦逊的长者——Edsger Wybe Dijkstra，1930年出生于荷兰阿姆斯特丹，2002年逝世于荷兰纽南。他在祖国荷兰获得数据和物理学学士，理论物理博士学位，2000年退休前一直是美国Texas大学的计算机科学和数学教授。以发现了图论中的最短路径算法（Dijkstra算法）而闻名于世，1972年因为ALGOL第二代编程语言而获得图灵奖。“Go To Statement Considered Harmful”(EWD215)也是被广为传颂的经典之作。除了科学研究之外，他最喜欢做的事情就是教学，被人称作“一天教学24小时”的教授。 且不说Dijkstra算法对计算科学，网络科学发展的深远影响，单从他在1972年获得图灵奖时的演讲“The Humble Programmer”就不得不肃然起敬，在获得计算机科学中至高无上的奖项时，Edgs Wybe Dijkstra仍然称自己不过是一个谦逊普通的程序员，何等胸襟，举世之中几人可比。 ·George Dantzig 运筹学大师——George Dantizig可谓是由父亲一手培养出的天才。George的父亲是俄国人，曾在法国师从著名的科学家Henri Poincar e。他曾经这样回忆自己的父亲：“在我还是个中学生时，他就让我做几千道几何题……解决这些问题的大脑训练是父亲给我的最好礼物。这些几何题，在发展我分析能力的过程中，起了最最重要的作用。” 在伯克利学习的时候，有一天George上课迟到，只看到黑板上写着两个问题，他只当是课堂作业，随即将问题抄下来并做出解答。六个月后，这门课的老师——著名的统计学家Jerzy Neyman——帮助他把答案整理了一下，发表为论文，George这才发现自己解决了统计学领域中一直悬而未决的两个难题。 George后来在运筹学建树极高，获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在Linear programming and extensions一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。天妒英才，他于2005年5月13日去世。 ·James Cooley 推动时代前进的人——James Cooley(1926-)美国数学家，哥伦比亚大学的数学博士，以他所创造的快速傅立叶变换(FFT)而著名，不能不说是意义极其重大，FFT的数学意义不光在于使大家明白了傅立叶(Fourier)变换计算起来是多么容易，而且使得数字信号处理技术取得了突破性的进展，对于现在的网络通信，图形图像处理等等领域的发展与前进奠定了基 础。Fourier变化的意义在于将电能变为了工业的命脉，而FFT的意义更是在于他推动了整个社会信息化的进程。在IBM研究中心中主要从事数字信号处理的研究一直到1992年退休，同时他还是IEEE的数字信号处理委员会的成员。1980年获得ASSP's Meritorious Service Award,1984年获得ASSP Society Award以及IEEE Centennial Medal。 ·John Backus FORTRAN 之父——John Backus早年在Hill School学习的时候因为讨厌学习，成绩一踏糊涂而不得不在暑假补课。1943年他在父亲的要求下到维吉尼亚大学学习化学，随后参军、照顾头部受伤的伤员、在医学学校学习治疗，可是最后又都放弃了。不过还好，战后Backus进入纽约哥伦比亚大学学习数学，并于1949年毕业。在毕业前夕，他跑到了麦迪逊大街的IBM计算机中心参观。事情凑巧，和导游聊天的时候Backus谈到自己正在找工作，在导游的鼓励下，他和中心一位主管的面谈，成为了一名IBM 的程序员。 在IBM，Backus的才华得到了施展，发明了人类历史上第一个高级语言——FORTRAN。接着，又提出了规范描述编程语言语法的 Backus-Naur Form(BNF)。这位当年的“差生”终于被整个计算机世界肯定——美国计算机协会于1977年授予John Backus图灵奖。 ·Jon Bentley 实践探索先锋——Jon Bentley 1974年获得了斯坦福大学的学士学位，1976年获得北卡罗莱纳大学的硕士和博士学位。毕业后在卡耐基梅隆大学教授了6年计算机科学课程，1982年进入贝尔实验室。2001年退休后加入了现在的Avaya实验室，他还曾作为访问学者在西点军校和普林斯顿大学工作。他的研究领域包括编程技术、算法设计、软件工具和界面设计等等。 他写作过三本编程书籍，其中最著名的就是涵盖从算法理论到软件工程各种主题的Programming Pearls(《编程珠玑》)，这其实是他发表过的文章的合集。在这些文章里，Jon从工程实现的角度出发，为程序员们提供了一个个艰难问题的解决方案，犹如一颗颗闪闪发亮的珍珠。Bentley的珍珠超出了可靠工程学的范畴，利用他的洞察力和创造力为那些恼人的问题提供了独特而巧妙的解决方案。 ·Nicklaus Wirth Pascal之父——Nicklaus Wirth，如果说有一个人因为一句话而得到了图灵奖，那么这个人应该就是Nicklaus Wirth，这句话就是他提出的著名公式“算法+数据结构=程序”。这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的“E=MC^2”——一个公式展示出了程序的本质。 Nicklaus Wirth，1934年出生于瑞士，1963年在加州大学伯克利分校取得博士学位。取得博士学位后直接被以高门槛著称的斯坦福大学聘到刚成立的计算机科学系工作。在斯坦福大学成功的开发出Algol W以及PL360后，爱国心极强的Nicklaus Wirth于1967年回到祖国瑞士，第二年在他的母校苏黎世工学院他创建与实现了Pascal语言——当时世界上最受欢迎的语言之一。后来他的学生 Philipe Kahn毕业后和Anders Hejlsberg(Delphi之父)创办了Borland公司靠Turbo Pascal起家，很快成为了将Borland发展成为全球最大的开发工作厂商，这一切都不得不说要归工于PASCAL语言的魅力。PASCAL已经影响了整整几代的程序员，Nicklaus Wirth的思想还将会继续指引现在和以后的程序员前进的方向。 ·Rebort Sedgewick 算法的讲解者——Robert Sedgewick是普林斯顿大学的计算机科学教授。他还是Adobe Systems 的一名主管，也曾作为访问学者在Xerox PARC、IDA和INRIA工作。他在斯坦福大学获得博士学位。他的著作包括Algorithm in C、Algorithm in C++、Algorithm in Java等系列书籍，这些都再版多次。“没有人能够将算法和数据结构解释得比Robert Sedgewick更清楚易懂了！”很多读过他著作的程序员这样说。 目前Robert正在研究算法设计、数据结构、算法分析等方面的基础理论。他善于通过数学方法评估和预测算法性能，设法发现算法、数据结构的通用机制，例如使用逼近方法寻找更快速更高效的算法。另外，他还将算法和图形学结合起来，例如使用可视化方法评估算法效率，算法的图形化模拟，用于出版物的高质量算法表现方法等等。 ·Tony Hoare 计算机领域的爵士——Tony Hoare，1934年出生于英国，1959年博士毕业于俄罗斯莫斯科国立大学，获得语言机器翻译专业学士学位。1960年发布了使他闻名于世的快速排序算法（Quick Sort），这个算法也是当前世界上使用最广泛的算法之一。 Tony Hoare在取得博士学位后，就职于Elliott Brothers，领导了Algol 60第一个商用编译器的设计与开发，由于其出色的成绩，最终成为该公司首席科学家。从1977年开始，Tony Hoare博士任职于牛津大学，投身于计算系统的精确性的研究、设计及开发。因其对Algol 60程序设计语言理论、互动式系统及APL的贡献，1980年被美国计算机协会授予“图灵奖”。 1999年在牛津大学退学后，Tony Hoare博士被微软剑桥研究院聘请担任高级程序员，从事微软剑桥研究院研究生成果的工业化应用的工作，以及协助其它研究人员进行服务于软件产业及用户的长期基础研究项目。2000年因为其在计算机科学与教育上做出的贡献被封为爵士。 ·Udi Manber 首席算法官——世界上还有如此奇怪的职位？但是对于Amazon乃至Google来说，这一点也不奇怪。Udi Manber，这位前Amazon的“首席算法官”，现在是Google负责工程事务的副总裁。他研究WWW的应用程序、搜索以及隐藏在这背后的算法设计。在此期间，他与其他人共同开发了Agrep、Glimpse和Harvest等Unix上的搜索软件。1998年，Udi成为了Yahoo!的首席科学家。2002年，Amazon创造性地给了Udi“首席算法官”的职位，和Udi为Amazon的“Search Inside the Book”搜索项目所做的工作相得益彰。 Udi还因为他所著的Introduction to Algorithms——A Creative Approach而被大家称道。 |
|
|
