灵魂守卫

13.2 旋转

查找树操作TREE-INSERT和TREE-DELETE，运行在n个key的红黑树上，花费时间O(lg n)。由于改动了树，所以结果树可能不符合13.1节列举的红黑树的性质。为了恢复这些性质，我们必须改变树中一些结点的颜色和修改一指针结构。
我们通过旋转来修改指针结构，它是一个局部操作使查找树保持二叉查找树的属性。图13.2展示了两种旋转：左旋和右旋。当我们对结点x进行左旋时，我们假设y是x的右孩子并且不是T.nil； x可以是树中任意右孩子不空的结点。左旋的“轴”是沿着x到y的。它使y成为子树的根，x成为y的左孩子，y左孩子成为x的右孩子。
LEFT-ROTATE伪代码假设x.right≠T.nil和root的双亲为T.nil。

      图13.2 二叉查找树的左旋操作。左旋操作LEFT-ROTATE(T,x)通过修改常数个指针来改变两个结点的结构把右边的结点的结构变成左边的结构。相反的右旋操作RIGHT-ROTATE(T,y)将左边的结构变成右边的结构。α、β和γ表示任意形态的子树。旋转操作要保持二叉树的性质：α子树上的所有keys要小x.key,x.key要小于β子树上的所有keys，β子树的keys要小于y.key，y.key要小于γ子树上的所有的keys。

图13.3 展示了LEFT-ROTATE如何修改二叉查找树的实例。代码跟RIGHT-ROTATE是对称的。LEFT-ROTATE和RIGHT-ROTATE的运行时间者是O(1)。一次旋转只修改了指针；结点其它属性都保持不变。

图13.3 方法LEFT-ROTATE(T,x)如何修改一棵二叉查找树的实例。中序遍历输入树和中序遍历修改过后的树产生相同的key序列。

练习

13.2-1 写出RIGHT-ROTATE方法。
13.2-2 证明在任意n结点的二叉查找树上，刚好有n-1种可能的旋转。
13.2-3 设a,b,c分别是α、β和γ的任意结点，在图13.2的左侧。如图在结点x上做一次左旋转a,b,c的深度是如何变化的？
13.2-4 证明任意n结点的二叉查找树经过O(n)次旋转得其它任意形态的n结点二叉查找树。（提示：首先证明最多通过n-1次右旋可以将树的结构变成右链的形态。）
13.2-5 我们说如果通过一系列的调用RIGHT-ROTATE可以从二叉查找树T1转换成T2，那么二叉查找树T1右转（right-convert)成T2 。举出一个例子T1和T2，使得T1不能右转成T2。然后证明如果树T1右转成T2，那么它可以通过调用O(n^2)次RIGHT-ROTATE得到。
全文下载：第13章 红黑树

第12章我们讨论了在高度为h的二叉查找树能够在O(h)时间完成任何动态集操作，比如查找（SEARCH）,前躯（PREDECESSOR）,后继(SUCCESSOR),最小值（MINIMUM），最大值（MAXIMUM）,插入（INSERT）和删除（DELETE）操作。因此，如果树高矮的时候这些动态集的操作是很快的。如果树高很高的话，那么这些动态集的操作就没有链表快了。红黑树是众多“均衡”查找树中的一种，它可以保证基本的动态集操作在最坏的情况下运行时间为O(lg n)。

13.1 红黑树的性质

红黑树是一棵二叉查找树，并且每个结点都附加一个额外的存储位：结点颜色，它的值可以是红色或者黑色。通过对根到叶子路径上结点图色的限制，红色黑树保证没有哪一条路径是其它路径的二倍长，所以这棵树大致上是平衡的。
现在每个结点都包含属性color,key,left,right和p。如果结点没有孩子或者双亲结点不存在（译者著：根结点没有双亲结点，普通的叶子结点没有孩子），那么该结点的这些属性（译者著：孩子或者双亲指针）值是NIL。我们把这些NIL当作二叉树中指向叶子（外部结点）的指针，正常包含key的结点为树的内部结点。
红黑树是一种二叉查找树，并且还满足下面的红黑性质：

1. 每个结点不是红色就是黑色。
2. 根结点是黑色的。
3. 每个叶子结点（NIL）都是黑色的。
4.  如果一个结点是红色的，那么它所有的孩子都是黑色的。
5. 对于每一个结点，从当前结点到后代的叶子的路径上包含黑色结点的数量是相同的。

图13.1(a)展示了一棵红黑树的例子。
    为了方便处理边界条件，在实现红黑树的代码里，我们使用了一个哨兵结点也替换NIL（查看第238页）。对于一棵红黑树T，哨兵T.nil是跟树中普通结点有同样属性的一个对象。它的颜色是黑色，它的其它属性-p,left,right和key-可以是任意值。如图13.1(b)所示，所有NIL指针都替换成指向哨兵结点T.nil.
    我们使用哨兵结点是为了我们可以把x结点的NIL孩子看成是x的一个普通的孩子。尽管我们可以在树中我可以用不同的哨兵结点替换每一个NIL，第一个NIL的双亲都这样定义，但是这样将会很浪费空间。所以，我们使用一个哨兵结点T.nil代替所有NIL-所有以的叶子结点和根结点的双亲。哨兵结点的属性p,left,right和key都是无关紧要的，为了方便我们在方法里还是设置了它们。
    我们基本上只对内部结点有兴趣，是因为它们含有key值。本章剩下的部分，当我们绘制红黑树的时候，我们会忽略叶子，如图13.1(c)所示。
    我们把从结点x，不包括到x,向下到叶子结点的结点的任意路径上黑色结点的个数称为结点的black-height,记作bh(x)。通过性质5，black-height概念是明确的，结点所有下降的路径上都有数量相同的黑色结点。我们把红黑树root的black-height定义成这棵红黑色树的black-height。
    下面引理说明了为什么红黑树是一种好的搜索树。

引理13.1

具有n内部结点的红黑树的高度最高为2lg(n+1)。

证明

首先，我们论证对于以任意结点x为根的子树包含至少2^bh(x) – 1个内部结点。我们通过照给x的高度来证明这个论点。如是x的高度是0，那x一定是叶子(T.nil)，以x为根的子树的确包含至少2^bh(x) – 1=2^0-1=0个内部结点。接下来归纳，如果结点x的高度为正数并且是两个孩子的内部结点。每个孩子只的black-height是bh(x)或者bh(x-1),这取决于他们自身的颜色。由于x的孩子的高度肯定比x自身要低，我们用归纳假设得出每个孩子至少包含2^(bh(x)-1) – 1个内部结点。那么以x为根的子树包含至少2^(bh(x)-1) – 1 + 2^(bh(x)-1) – 1 +1 = 2^bh(x)-1个内部结点，这就证明了上面的提出的论点。
    为了完成引理的证明，假设树高为h。根据性质4，从根的出发到达叶子结点的任意路径，不包括根结点，至少有一半结点是黑色的。因此，根结点的black-height至少h/2;所以
    n ≥ 2^(h/2) – 1.
把1移到左边再把两边取对数，lg(n+1) ≤h/2,或h≤2log(n+1)
    由这个引理可以得出，我们可以用红黑色树去实现运行时间为O(lg n)动态集操作查找（SEARCH）,最小值（MINIMUM）,最大值（MAXIMUM）,后继（SUCCESSOR）和前驱（PREDECESSOR），因为在高度为h（第12章介绍的那样）的二叉查找树中每个操作的运行时间为O（h）,n结点的任意红黑树是高为O(lg n)的二叉树。（当然，在第12章中使用NIL指针要替换成T.nil。）对于给定的红黑树用第12章的TREE-INSERT和TREE-DELETE算法运行时间也是O(lg n)，但是这两个算法不能直接支持动态集操作INSERT和DELETE，因为它们不保证修改过的二叉树是否仍然是红黑树。然而，在13.3和13.4节，我们将看到如何在O(lg n)运行时间内实现这两种操作。

图13.1 这是一棵红黑树，黑色表示黑结点，阴影表示红结点。红黑树中的每一个结点，不是红色的就是黑色的，红结点的孩子都是黑色的，从某结点到叶子结点的所有路径中的有相同数量的黑结点。（a）每一个叶子，用NIL来表示，是黑色的。每一个非NIL结点都标记它的black-height；NIL结点的black-heigth为0.(b)同样的红黑树，但是用一个T.nil替换了所有的NILL，它总是黑色的，并且它的black-height被忽略。根结点的双亲是哨兵。（c）同样的红黑色树，但是叶子结点和根的双亲被完全忽略了。在本章的剩余部分，我们将用这种方式绘制红黑树。

练习

13.1-1 按照13.1(a)的方式，绘制高度为3的完全二叉查找树,key值为{1,2,…,15}。添加NIL叶子结点并分别画出black-height为2，3，4三种不同方式的红黑树。
13.1-2 画出向图13.1中的树调用TREE-INSERT，key为36的结点后的红黑树。如果插入的结点着成红色它还是一棵红黑树吗？如果着成黑色呢？
13.1-3 让我定义一种relaxed red-black树，它一棵二叉查找树，并且满足红黑树的性质1，3，4和5。换句说，根可能是红色或者黑色。假设有一棵relaxed red-black树T，它的根是红色的。如果我们将根着成黑色树T其它的都不变，那么着色后它是一棵红黑树吗？
13.1-4 假设在红黑色树我们让每个红色结点都被它的黑色双亲结点“吸纳”，那么红色结点的孩子都变成黑色双亲的孩子。（忽略key的变化）所有红色结点被吸纳后，黑色结点可能的度是多少？你能说出结果这个棵树的高度是多少吗？
13.1-5 证明在红黑树中从结点x开始到叶子最长路径的长度最多是从结点x开始到叶子的最短路径的两倍。
13.1-6 在高度为k的红黑树中内部结点数量最多是多少？最少是多少？
13.1-7 请描述下n个key构成的红黑树，它的红色内部结点与黑色内部结点比值最大，这个最大比值是多少？那比值最小的红黑树是什么样的，比值是多少？
全文下载：第13章 红黑树

12.3 二叉树的插入和删除

插入和删除操作将会导致由二叉树表示的动态集合改变。要反应出这种变化，数据结构也会作出相应变化，但在修改的同时，二叉树的性质还要继续保持。正如我们看到的那样向树中插入一个新元素相对比较简单，但是处理删除操作就更加复杂了。
插入
向二叉查找树T插入一个新的元素v，我们使用TREE-INSERT方法。方法传入一个z,并且z.key=v,z.left=NIL,z.right=NIL.这个方法会将会修改T和z的一些属性，并将z插入到树的合适的位置。


图12.3 向二叉查找树中插入key为13的数据项。浅色阴影部分标明了一条从根到插入数据项的自上而下的简易路径。虚线表明了向树中添加项的链接。

图12.3展示了TREE-INSERT的工作原理。跟TREE-SEARCH和ITERATIVE-TREE-SEARCH一样，TREE-INSERT也是从根开始指针x向下遍历找到NIL替换成输入项z。这个方法维护跟踪指针y作为x的双亲。初始化完成后，第3-7行的while循环中使两个指针沿树直下而上，向左还是向右取决非于z.key与x.key的比较，直到x变成NIL。该NIL的位置就是我希望的项z插入的位置。我们还需要尾随的指针y，因为当我找到z插入的NIL位置，搜索程序往结点后一步找到需要修改的结点。第8-13行设置了相应的指针使z插入。
跟其他的二叉查找树的原始操作一样，TREE-INSERT在高为h的树中运行时间是O(h)。

删除
在二叉查找树T中删除结点z的所有方法中有三种情况，正如我们将看到的那样，有一种情况有一点复杂。

• 如果z没有孩子，我们简单的删除它并修改它的双亲，用NIL作为孩子来代替z。
• 如果z只有一个孩子，我们通过修改z双亲，用该孩子替换z,提升这个孩子代替z在树中的位置。
• 如果z有两个孩子，我们先找到z的后继y，y一定在z的右子树，然后用y替换z的位置，然后z原来的右子树变成y的新右子树，z的左子树变成y的新左子树。这种情况有一点小复杂，因为正我们所看到的，y必须是z的右孩子。

删除二叉查找树T中的指定结点z的的方法需要两个参数指针T和z.它的过程跟之前描述的三种情况有点点不同，如图12.4考虑到了四种情况。

• 如果z没有左孩子(图中的a部分),我们将右孩子替换z,右孩子也有可能是NIL。当z的右孩子为NIL，这种情况等同于z没有孩子那个情形处理。当z的右孩子为非NIL，这种情况的处理相当于z只有一个孩子，并且这个孩子是右孩子。
• 如果z只有一个孩子，这个孩子是左孩子（图中的b部分）,那我们就用z的左孩子替换z。
• 除此之外，z即有左孩子又有右孩子。我们找到z的后继y，y分布在z的右子树上并且没有左孩子（查看练习12.2-5）。我们想把y拼接到当前输出的位置这样就替换了z的位置。
• 如果y是z的右孩子（图示c部分），那我们就用y替换z, 只剩下了y的右孩子。
• 除此之外，y在z的右子树里面，并不是z的右孩子（图示d部分）.这种情况，我们首先我们用y来替换z的右孩子，然后再用y来替换z.

为了方便在二叉查找树中移动子树，我们定义了一个子方法TRANSPLANT，用v为根结点的子树替换以u为根结点的子树，u的双亲变成v的双亲，并且u的双亲连接v作为它合适的孩子(译者注：如果u是双亲的左孩子，那么v就是双亲左孩子，反之亦然)。

第1-2行处理u是根的情况。除此之外，u的双亲不是有左子树就是有右子树(译者注：u如果有双亲，那么u的双亲至少有一个孩子)。第3-4行如果u是一个左孩子更新u.p.left，第5行表示如果u是右孩子更新u.p.right.我们允许v为NIL，第6-7如果v为非NIL，更新v.p。TRANSPLANT没有尝试去更新v.left和v.right；要不更去更新，取决于TRANSPLANT的调用者。

图12.4 从二叉查找树中删除结点z。z结点可能是根结点，结点的q的左孩子或者结点q的右孩子。(a)z没有左孩子。我们拿它的右孩子r替换z,r可能是空或者非空。(b)结点z有左孩子l但没有右孩子。我们拿l替换z.(c)结点z有两个孩子；它的左孩子为l,它的右孩子为就是它的后继y,y的右孩子为结点x.我们用y来替换z,y的左孩子变成了l,剩下的x作为y的右孩子。(d)结点z有两个孩子（左孩子为l并且右孩子为r）,并且它的后继y≠r,y在它的右子树里，右子树根结点为r。我们用y的右孩子x替换y，并且我设置y为r的双亲。然后我们设置y为q的孩子，设置y为l的双亲。

利用上面的方法TRANSPLANT，下面方法是从二叉查找树T删除结点z：

TREE-DELET方法处理了下面的四种情况。第1-2行得理结点z有左孩子，第3-4行处理z有左孩子但没有右孩子的情形。第5-12处理剩下z有两个孩子的两种情况。第5找到y,y是z的后继。因为z右子树非空，它的后继一定是右子树key最小的结点；因此调用方法TREE-MINIMUM(z.right)。从前面的介绍，我们可以知道y没有左孩子（译者注：因为y是z右子树中key最小的结点，故y没有左孩子）。我们想把y拼接到当前输出的位置并且替换树中的z。如果y是z的右孩子，第10-12行用y替换了作为z双亲的孩子替换了z,用z的左孩子替换了 y的左孩子。如是y不是z的左孩子（译者注：这里应该“如果y不是z的右孩子”）第7-9行用y的右孩子作为y双亲的孩子替换y然后把z的右孩子变成y的右孩子，然后第10-12行用y作为z的双亲的孩子替换z,用z的左孩子替换y的左孩子。

TREE-DELETE除了第5行调用了TREE-MINIMUM之行，其它每一行代码，包括调用TRANSPLANT都花费常数时间。因此TREE-DELETE在高为h的树运行时间为O(h).
总之，我们证明了下面的定理。
定理12.2
在高度为h的二叉查找树上，我们实现的动态集操作，INSERT,DELETE运行时间都是O(h)。
练习12.2
12.3-1  给出TREE-INSERT方法的递归版本。
12.3-2 假想我们反复向二叉树插入不同的元素来构建一棵二叉查找树。证明从中查找某一个结点所要检查结点的数量等于首次向树中插入该结点所要检查结点的数量加1.
12.3-3 我们可以通过构建二叉查找树（使用TREE-INSERT反复一个一个地插入数字）对给定有数字集合进行排序，然后中序打印遍历打印这些数字。对于这种排序算法它的最坏情况与最好情况的运行时间是多少？
12.3-4 对二叉查找树的删除先从二叉查找树中删除x再删除y和先从二叉树删除y再删除y的操作是可交换吗?证明是或者举出一个反例。
12.3-5 假设替换结点属性x.p成x.succ，x.p指向双亲结点,x.succ指向x的后继指点。使用这个属性给出二叉查找树T的SEARH,INSERT和DELETE操作的方法。在高为h二叉查找树中，这些方法运行时间是O(h)。（提示：你可以实现一个子方法返回双亲结点）。
12.3-6 在TREE-DELETE中删除结点z时，我们可以选择前驱结点y而不是后继结点。如果这样做TREE-DELETE要做哪些改变？有些人提出一个公平策略，前驱和后继具有相同的优先级，而获取更高的性能。如何修改TREE-DELETE实现这个公平策略。
全文下载:Chapter_12-Binary_Search_Trees

12.2 二叉树的搜索

我们经常需要在二叉查找树查找某个key。除了查找（SEARCH）操作之外，二叉查找树也支持譬如最小值（MINIMUM），最大值（MAXIMUM），后继（SUCCESSOR）和前驱（PREDECESSOR）的查找。在本节，我们将会考查这些操作并且给出如何在高度为h的二叉查找树中，用O(h)时间内完成这些操作。

查找

我们使用下面的方法在二叉查找树中查找指定的key的结点。指定树的根结点root和键值k, TREE-SEARCH返回键值为k的指针，如果不存在k则返回NIL。

图12.2 搜索二叉查找树。要在树中查找key为13的结点，搜索路径为从树出发15->6->7->13。树中最小key值为2，它沿树根的left指针上可以找到。最大key值20，它沿树根的right指针上可以找到。结点key为15的后继是key为17的结点，因为key为17的结点是key为15结点的右子树上key最小的结点。Key为13的结点没有右子树，因此它的后继是它最低的祖先，该祖先的左孩子也是一个祖先。在本例中，key为15的结点是13的后继。

上面的方法从树根开始查找并沿树枝的路径向下搜索，如图12.2所示。每个遍历到地结点，它都会拿这结点的值跟目标对比，如两个值相等，搜索结束。如果k小于前结点的x->key,将会在x的左子树继续搜索，因为根据二叉查找树的性质表明了k不可能x的右子树中。同理，如果k大于前结点的x->key,将会在x的右子树继续搜索。递归遍历的结点形了一条由树根向下的路径。因此TREE-SEARCH运行时间是O(h),h为树的高度。

我们可以用while循环迭代“铺开”递归过程重写上面的算法。在大多数计算机中，这个算法的迭代版本会更高效一点。

最小值和最大值

在二叉查找树上，我们可以从根结点出发沿着结点的left指针直到某个结点的left为空，就可以找到二叉树中key最小的那个元素，如图12.2所示。下面的方法返回以指定结点x为根的二叉树中key最小的元素，假设x为非空。

二叉的性质保持TREE-MINIMUM方法是正确的。如果一个结点没有左子树，那么结点x的右子树上的所有结点的key都不小于x->key,那么根结点key肯定是它们当中的最小值。如果结点x有左子树，那么右子树上没有节点的key比x->key小并且左子树上的结点都不大于x->key,所以以x为根节点的子树上最小值一定在以左子树x->left为根的子树中。

同上，TREE-MAXIMUM方法的伪代码：

同TREESEARCH一样，上述的两个方法在高度为h的树中都要花费O(n),访问的结点形成了一条由根出的向上的一条简易的路径。

后继和前驱

给出一棵二叉查找树上指定的结点，有时候我们需要找到这个结点的中序遍历的顺序的后继。（译者注：二叉查找的中序遍历序列下是有序的）。如果所有结点的key都是不相同的结点x的后继是那些key大于x->key之中最小那个的结点。二叉树的结构特点，使我们不需要比较key就能找到指定结点的后继。下面的方法返回结点x的后继，如果x的key是二叉树中最大的则返回NIL。

我们在TREE-SUCCESSOR方法中的两种情况下退出返回。如果x结点的右子树非空，那么结点x的后继就是它右子树中最左那的结点，在第2行我们可看到调用了TREE-MINIMUM(x->right)。举个例子，在图12.2中key为15的结点后继是key为17的结点。

另一种情况，如练习12.2-6让你去实现的那样，如果x结点的右子树是空的并且x有祖先y，那y是x的祖先中最小的那个祖先，并且y的左孩子也是x的祖先。在图12.2中，key为13的结点的后继是key为15。为了找到y，我们简单的从x向上查找直到我们找到某个结点是双亲结点的左孩子为止；TREE-SUCCESSOR中第3到7行就为了处理这种情况。
TREE-SUCCESSOR在高为h的树上的运行时间是O(h)，因为我们是沿着树向上或者向下的一条简单的路径。TREE-PREDECESSOR,跟TREE-SUCCESSOR同理，运行时间也是O(h)。
即使所有key不都是完全相同，我们也把TREE-PREDECESSOR(x)返回结点作为x的前驱，TREE-SUCCESSOR(x)返回的作为后继。

总之，我们通过上面的叙述证明这样一个定理：

定理12.2 在高度为h的二叉查找树上，我们实现的动态集操作，SEARCH,MINIMUM,MAXIMUM，SUCCESSOR和PREDECESSOR运行时间都是O(h)。

练习
12.2-1 假设我们有一棵二叉查找树，元素值是都是在1到1000之间，我们想查找数字363.下面哪个查找序列不属于正确的访问序列。
a. 2, 252, 401, 398, 330, 344, 397, 363.
b. 924, 220, 911, 244, 898, 258, 362, 363.
c. 925, 202, 911, 240, 912, 245, 363.
d. 2, 399, 387, 219, 266, 382, 381, 278, 363.
e. 935, 278, 347, 621, 299, 392, 358, 363.
12.2-2 写出递归版本的TREE-MINIMUM和TREE-MAXIMUM
12.2-3 写出TREE-PREDECESSOR方法
12.2-4 Bunyan教授认为他发现了二叉查找树的一个重要的性质。假设在二叉查找树上查找key为k的结点,并且key为k的结点是一个叶子结点。那么有三个集合：A，搜索路径的左边结点集合；B，搜索路径上的结点；C是搜索路径右边的结点集合。Buyan教授认为对于三个集合的任意值a∈A，b∈B，c∈C一定满足a≤b≤c。对于上面的观点，请给出最小可能一个的反例。
12.2-5 证明：对于二叉查找树，如果一个结点有两个孩子，那么它的后继没有左孩子并且它的前驱没有右孩子。
12.2-6 二叉查找树T是没有重复key的集合。证明如果结点x的右子树为空并且x有后继y，那么y是x的最低祖先，并且y的左孩子也是x的祖先。（注意每个结点都是自己的祖先）。
12.2-7 有一种非常规的方法中序遍历n个结点的二叉查找树。通过TREE-MINIMUM找到最小元素然后通过n-1次调用TREE-SUCCESSOR。证明这种算法运行时间为O(n)。
12.2-8 证明不论从高度为h的二叉查找树的哪个结点开始，连续k次调用TREE-SUCCESSOR将花费O(k+h)时间。（译者注：前一次调用的结果作为后一次的调用参数）。
12.2-9 T是没有重复key的二叉查找树。如果x为它的一个叶子结点，y为x的双亲。证明y.key是T中大于x.key的集合中最小的或者y.key是T中小于x.key的集合中最大的。
全文下载:Chapter_12-Binary_Search_Trees

哲学家就餐问题：
有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌上有五个碗和五只筷子，他们的生活方式是思考和进餐。平时，哲学家进行思考，饥饿时就便试图去他们左右的筷子来就餐。只有在他拿到两个筷子时才能就餐。

服务生解法
所有哲学家想吃饭都必须告诉服务生，吃完饭同时也告诉服务生。由服务生根据筷子的使用情况决定是否准予吃饭。
下载:waiter.c 

编译: gcc waiter.c -lpthread -o waiter
运行:./waiter

请您自行安装vc2010
参照下面的文章安装：http://www.codeman.net/?p=24
下载代码与vs2010工程：
nginx-1.3.15
打开vs2010文件夹中的nginx.sln即可编译和调试nginx
如果您想使用VC2005或者其它IDE编译，要把握下面的要点：
1.配置源码，生成ngx_modules.c,ngx_auto_headers.h,ngx_auto_config.h（使用./auto/configure 命令，如果提示没有pcre和zlib,没有关系使用./auto/configure --with-cc=cl --with-pcre=./ --with-zlib=./）
2.确定要使用哪些源文件：参看objs/Makefile文件下的*.objs有哪些即可
3.配置包含目录
4.配置包含库
注：
下载的vs2010文件夹里自带了两个库pcre与zlib头文件均位于vs2010/include下,库文件位于vs2010/lib下
source:
svn://svn.nginx.org/nginx/trunk

version:
1.3.15 (subversion 5140)

configure command:
./auto/configure –with-cc=cl –with-pcre=./ –with-zlib=./

include 47 mudules:
ngx_core_module
ngx_errlog_module
ngx_conf_module
ngx_events_module
ngx_event_core_module
ngx_iocp_module
ngx_select_module
ngx_regex_module
ngx_http_module
ngx_http_core_module
ngx_http_log_module
ngx_http_upstream_module
ngx_http_static_module
ngx_http_autoindex_module
ngx_http_index_module
ngx_http_auth_basic_module
ngx_http_access_module
ngx_http_limit_conn_module
ngx_http_limit_req_module
ngx_http_geo_module
ngx_http_map_module
ngx_http_split_clients_module
ngx_http_referer_module
ngx_http_rewrite_module
ngx_http_proxy_module
ngx_http_fastcgi_module
ngx_http_uwsgi_module
ngx_http_scgi_module
ngx_http_memcached_module
ngx_http_empty_gif_module
ngx_http_browser_module
ngx_http_upstream_ip_hash_module
ngx_http_upstream_least_conn_module
ngx_http_upstream_keepalive_module
ngx_http_write_filter_module
ngx_http_header_filter_module
ngx_http_chunked_filter_module
ngx_http_range_header_filter_module
ngx_http_gzip_filter_module
ngx_http_postpone_filter_module
ngx_http_ssi_filter_module
ngx_http_charset_filter_module
ngx_http_userid_filter_module
ngx_http_headers_filter_module
ngx_http_copy_filter_module
ngx_http_range_body_filter_module
ngx_http_not_modified_filter_module

强列推荐

wget http://wdl.cache.ijinshan.com/wps/download/Linux/unstable/wps-office-8.1.0.3724-0.1.b1p2.i686.rpm

rpm -i wps-office-8.1.0.3724-0.1.b1p2.i686.rpm

strncmp与strcmp
二者都字符串比较，前者有限定最多只能比较n个字符
如:

1. strcmp(“hello”,“hel”);    //none zero
2. strncmp(“hello”,“hel”,3); //zero

strncmp与memcmpy
二者都限定最多比较n个字符，但前者如果遇到’\ 0’结束比较
如:

1. strncmp(“ababc”,“abcba”,6); //zero
2. memcmp(“ababc”,“abcba”,6);  //none zero

strncpy与strcpy
二者均为字符串复制，但前者限定最多只能复制n个字符（不会自动追加’\ 0’）
如：

1. char b[]=“abcdef”;
2. strcpy(b,“hello”);     //b: hello\ 0
3. strncpy(b,“hello”,5);  //b: hellof
4. strcpy(s,d)等价于strncpy(s,d,strlen(s)+1);

strncpy与memcpy
二者均为固定内存复制，但前者如果遇到\ 0会停止复制
如:

1. char b[7]=“hello”;
2. char d[7] = {0};
3. strncpy(d,b,7); //d: “he\ 0\ 0\ 0\ 0\ 0”
4. memcpy(d,b,7);  //d: “he\ 0llo\ 0”

1.错误定义

分析源码从最简单的地方入手，首先来看nginx的错误码定义，代码在ngx_errno.h,ngx_errno.h文件中。一共就两个函数。

1. u_char *ngx_strerror(ngx_err_t err, u_char *errstr, size_t size);
2. ngx_uint_t ngx_strerror_init(void);

系统启动时会初始化全局变量ngx_sys_errlist，这是一个全局ngx_str_t数组，数组大小为NGX_SYS_NERR，每个元素都一个结构体为：

1. typedef struct {
2.     size_t      len;//data成员的大小
3.     u_char     *data;//一个字符串
4. } ngx_str_t;

初始化：ngx_uint_t ngx_strerror_init
所以初始化的函数是填充每一个元素，该元素的数组下标即为错误码，元素len成员是指元素data字符串的大小，data是该错误码(数组下标)的文字描述，通过函数strerror(err)来取得错误码的信息串。
获取错误码对应的信息串:ngx_strerror
在ngx_sys_errlist找到err对应位置的错误信息，如果错误码不在数组下标范围则返回未知错误，同时检查传入的长度，太小于将会截断错误信息串。

在windows下编译nginx可以利用VC编译来调试nginx，当我们很熟悉了操作系统上层的实现之后转向分析nginx代码也方便一些。
在windows下编译nginx跟在Linux下的步骤差不多。利用svn工具下载源码，第三方网站下载的tar文件中没有win32的配置文件；由于configure文件是sh脚本，所以只能用第三方仿真软件，我这里用的是MinGW Shell；配置完成后就是编译，只要调用VC的编译工具cl.exe编译就行了。

下载工具
需要的工具有：
1.TortoiseSVN:http://downloads.sourceforge.net/project/tortoisesvn/1.7.5/Application/TortoiseSVN-1.7.5.22551-win32-svn-1.7.3.msi
2.MinGW32:http://10.10.4.6/download/7377061/8602355/3/exe/230/40/1322227850470_40/mingw-get-inst-20111118.exe
3.VC2010 express:http://download.microsoft.com/download/e/5/e/e5e362e1-6a2a-4ce3-bbac-659c9740ab04/vc_web.exe
上面的工具下载安装完成即可。

下载源码
源码地址在：svn://svn.nginx.org/nginx/trunk 使用svn将源码检出到本地任意目录，比如f:\nginx\trunk
目录结构如下：
f—nginx—trunk—(auto conf contrib docs misc src)

配置代码环境
打开cmd命令行提示:

2.设置VC的环境变量：在命令提示符中键入命令（根据VC的安装目录不同而不同,x86为参数）

设置MinGW：在命令提示符键入命令（根据MinGW32安装目录不同而不同）：

检查环境：
弹出MinGW窗口，关闭其它的cmd窗口。在MinGW32的窗口输入:

有如下显示：
用于 80×86 的 Microsoft (R) 32 位 C/C++ 优化编译器 16.00.30319.01 版
版权所有(C) Microsoft Corporation。保留所有权利。
用法: cl [ 选项… ] 文件名… [ /link 链接选项… ]
说明编译环境配置成功
编译
cd进入主目录，即truck目录

配置:

注解：
–prefix=. 表示安装目录在本目录下
–with-cc-opt=”-D FD_SETSIZE=4096″ 预定义宏FD_SETSIZE大小4096
–without-http_rewrite_module 不加载rewite模块
–without-http_gzip_module 不加载gzip模块
–with-cc=cl 编译器为cl
编译:

在obj/目录下为生成的中间文件和nginx.exe文件。