﻿<?xml version="1.0" encoding="utf-8" standalone="yes"?><rss version="2.0" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:trackback="http://madskills.com/public/xml/rss/module/trackback/" xmlns:wfw="http://wellformedweb.org/CommentAPI/" xmlns:slash="http://purl.org/rss/1.0/modules/slash/"><channel><title>C++博客-一生为你</title><link>http://www.cppblog.com/lucency/</link><description /><language>zh-cn</language><lastBuildDate>Tue, 14 Apr 2026 20:58:27 GMT</lastBuildDate><pubDate>Tue, 14 Apr 2026 20:58:27 GMT</pubDate><ttl>60</ttl><item><title>windows上编译global</title><link>http://www.cppblog.com/lucency/archive/2008/12/11/69129.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Thu, 11 Dec 2008 01:58:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/12/11/69129.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/69129.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/12/11/69129.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/69129.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/69129.html</trackback:ping><description><![CDATA[<p>windows上使用mingw和msys编译global(以5.7.3版本为准)</p>
<p>1.将configure文件的1455到1467行注释掉.</p>
<p>2.修改libutil/path.c文件. 在include之后添加:</p>
<p>#if defined(_WIN32) &amp;&amp; !defined(__CYGWIN__)<br />#define 
mkdir(path,mode) mkdir(path)<br />#define link(one,two) (-1)<br />#endif</p>
<p>上述两个文件保存后, configure, make, make install即可.</p>
<p>用这种方式除了doc下的texi文件没法编译成功, 其他都没有问题. 编译到doc的时候, 直接C-c结束即可.</p><div style="margin: 5px; background: yellow none repeat scroll 0% 0%; position: absolute; left: 0pt; top: 0pt; z-index: 1000; font-family: arial; font-size: 13px; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial; -moz-border-radius-topleft: 5px; -moz-border-radius-topright: 5px; -moz-border-radius-bottomright: 5px; -moz-border-radius-bottomleft: 5px; opacity: 0.9; display: none;" id="dictdiv"></div><div id="dictaudio"></div><img src ="http://www.cppblog.com/lucency/aggbug/69129.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-12-11 09:58 <a href="http://www.cppblog.com/lucency/archive/2008/12/11/69129.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>All about Awk[译]</title><link>http://www.cppblog.com/lucency/archive/2008/12/10/69034.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Wed, 10 Dec 2008 03:11:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/12/10/69034.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/69034.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/12/10/69034.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/69034.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/69034.html</trackback:ping><description><![CDATA[&nbsp;&nbsp;&nbsp;&nbsp; 摘要: awk的一个实例教程, 很实用!&nbsp;&nbsp;<a href='http://www.cppblog.com/lucency/archive/2008/12/10/69034.html'>阅读全文</a><img src ="http://www.cppblog.com/lucency/aggbug/69034.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-12-10 11:11 <a href="http://www.cppblog.com/lucency/archive/2008/12/10/69034.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>gdb基础</title><link>http://www.cppblog.com/lucency/archive/2008/08/18/59214.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Mon, 18 Aug 2008 05:31:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/08/18/59214.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/59214.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#Feedback</comments><slash:comments>1</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/59214.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/59214.html</trackback:ping><description><![CDATA[<h1>gdb</h1>
<!-- Page published by Emacs Muse begins here -->
<p>这篇文章基本上是摘自gdb手册，除此之外就是加了实际的代码样例，这样可以更清楚的看到一些命令的执行效果。当然，这儿不会涉及到所有的gdb命令，而只是一些常用的。</p>
<p>我这儿使用的gdb的版本是6.8。不过因为只是一些常用命令，因此在老版本上应该也没问题。操作系统是Windows XP。</p>
<div class="contents">
<dl><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec1">一.概述</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec2">二.gdb的起停</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec3">三.gdb命令</a>
</dt><dd>
<dl><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.htm#sec4">命令语法</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec5">命令补全</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec6">获取帮助</a>
</dt></dl>
</dd><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec7">四.示例1</a>
</dt><dd>
<dl><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec8">断点</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec9">观察点</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec10">捕捉点</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec11">删除断点</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec12">禁用断点</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec13">断点条件</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec14">指定位置</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec15">栈</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec16">数据</a>
</dt></dl>
</dd><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec17">五 示例2</a>
</dt><dt>
<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#sec18">六 后记</a>
</dt></dl>
</div>
<h2><a name="sec2" id="sec2"></a>
一.概述</h2>
<p class="first">调试器的目的在于让你查看程序运行时的内部状态；或者在程序崩溃的时候，查看程序异常的原因。它们可以在一下几个方面提供帮助：
</p>
<blockquote>
<p class="quoted">1)启动程序，按照你的意愿影响程序的行为</p>
</blockquote>
<blockquote>
<p class="quoted">2)让程序在特定条件发生时停止运行</p>
</blockquote>
<blockquote>
<p class="quoted">3)当程序停止的时候，检查程序正在做什么</p>
</blockquote>
<blockquote>
<p class="quoted">4)改变程序的某些东西，这样就可以运行时修正bug，然后继续测试其他的问题。</p>
</blockquote>
<p>gdb支持多种语言的调试，不过最成熟的应该就是c/c++了。这儿也以c++程序为例来说明。如果想知道其他语言的支持情况，可以看gdb手册。</p>
<h2><a name="sec2" id="sec2"></a>
二.gdb的起停</h2>
<p class="first">gdb最常用的启动方式就是：
</p>
<blockquote>
<p class="quoted">gdb program</p>
</blockquote>
<p>或者在程序异常终止的时候这样：
</p>
<blockquote>
<p class="quoted">gdb program core</p>
</blockquote>
<p>也或者，你可以attach到一个已经运行的进程来调试它，就像这样
</p>
<blockquote>
<p class="quoted">gdb program PID</p>
</blockquote>
<p>当然，也可以在命令行设置gdb的启动参数，例如args：
</p>
<blockquote>
<p class="quoted">gdb —args gcc -O2 -c foo.c</p>
</blockquote>
<p>这样就可以调试gcc，同时将参数"-O2 -c foo.c"传给gcc。</p>
<p>可以用gdb -help查看gdb的所有选项。</p>
<p>要想中止gdb的运行，可以输入quit或者q，也可以按ctrl-d组合键。</p>
<h2><a name="sec3" id="sec3"></a>
三.gdb命令</h2>
<h3><a name="sec4" id="sec4"></a>
命令语法</h3>
<p class="first">gdb命令的形式为：command [arg1...argn]。每个命令单独一行。行的长度没有限制（当然，一般应该也不会有多长）。</p>
<p>许多gdb的命令都会有缩写的形式，例如break可以缩写为b。</p>
<p>如果直接按回车，gdb会执行刚刚被执行命令。</p>
<p>如果命令中有#字符，那么从#开始的字符都会被当成是注释。这个一般用在命令文件中。后面会有介绍。</p>
<h3><a name="sec5" id="sec5"></a>
命令补全</h3>
<p class="first">gdb具有补全功能。功能键是&lt;TAB&gt;。例如break，在输入bre之后按&lt;TAB&gt;
键，gdb就会补全为break。如果只输入b，然后按&lt;TAB&gt;，gdb会响一声，这说明有多个以b开始的命令。这种情况下再按一
次&lt;TAB&gt;，gdb就会把所有以b开始的命令输出出来。下面是此时的屏幕截图：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/gdb_tab_complete.jpg" alt=""></p>
<p>如果只是想看一下以某个(些)字符开始的命令，可以按&lt;META&gt;?，而不用按两次&lt;TAB&gt;。在没
有&lt;META&gt;键的电脑上，可以用&lt;ESC&gt;键代替。这个命令按起来有点麻烦，比按两次&lt;TAB&gt;要麻烦多了，如果
不怕&lt;TAB&gt;键被按坏，我建议你还是按&lt;TAB&gt;吧。</p>
<p>命令补全可以用于gdb命令，gdb子命令，程序中的符号名（例如函数名等）。</p>
<p>在调试c++程序时，基本上肯定会遇到的问题就是重载函数。例如，在设置断点的时候，假设有两个名为overload的函数，这时为了区分到底是那
个函数，就需要加上函数参数类型（函数名加上参数列表作为逻辑上的一个词）。为了使gdb能将参数列表两边的括号作为这个词的一部分，需要用单引号'将函
数整个的括起来。看下图：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/gdb_overload.jpg" alt=""></p>
<h3><a name="sec6" id="sec6"></a>
获取帮助</h3>
<p class="first">启动gdb后，可以输入命令help得到gdb的命令列表。注意的是这时输出的每个条目都是一类命令。上个图：
<img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/gdb_help.jpg" alt=""></p>
<p>得到命令类别后，可以用命令 help class得到此类别的所有命令。上图：
<img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/gdb_help_class.jpg" alt=""></p>
<p>上面的图中只显示了部分breakpoints命令。</p>
<p>其他跟帮助相关的命令有：</p>
<p>a)help command</p>
<blockquote>
<p class="quoted">用于显示命令command的帮助信息。</p>
</blockquote>
<p>b)apropos args</p>
<blockquote>
<p class="quoted">这里的args可以使正则表达式。显示所有匹配args的命令的简要说明。</p>
</blockquote>
<p>c)complete args</p>
<blockquote>
<p class="quoted">显示所有以args开始的命令。</p>
</blockquote>
<p>另外还有两个很有用的命令： <strong>info</strong> 和 <strong>show</strong> 。</p>
<p>a)info
</p>
<blockquote>
<p class="quoted">用于显示被调试程序的信息。例如传递到当前函数的参数-info args;或者查看当前寄存器的值-info registers;也可以查看断点-info breakpoints。可以用help info查看info的说明。</p>
</blockquote>
<p>b)show
</p>
<blockquote>
<p class="quoted">这个命令用于显示gdb的信息。也就是gdb的一些属性值。可以用help show查看帮助信息。这个命令通常应该是配合set用的（用于设定gdb的属性）。</p>
</blockquote>
<p>好了，现在对gdb应该有个大概的认识了，下面我们就要拿几个小例子来验证一些常用命令的效果。Let's go!</p>
<h2><a name="sec7" id="sec7"></a>
四.示例1</h2>
<p class="first">首先说明一点，要想高效的使用gdb的功能，需要在编译程序的时候要加上-g选项，这个选项会把调试信息加到可执行文件中。</p>
<p>下面说一下示例文件，包括三个：gdb.h， gdb.cpp， test.cpp</p>
<u>gdb.h</u>
<pre class="example">#ifndef _GDB_H<br>#define _GDB_H 1<br><br>class gdb<br>{<br>public:<br>    explicit gdb(int v);<br>    void overload(int one);<br>    void overload(int one, int two);<br>    void catch_ex(int ex); //exception<br>    void loop();<br>private:<br>    int value;<br>    int array[10];<br>};<br><br>#endif<br><br></pre>
<u>gdb.cpp</u>
<pre class="example">#include "gdb.h"<br>#include &lt;iostream&gt;<br>using namespace std;<br><br>gdb::gdb(int v)<br>{<br>    value = v;<br>    for(int i=0; i&lt;10; i++)<br>    {<br>        array[i] = i;<br>    }<br>}<br><br>void gdb::overload(int one)<br>{<br>    cout&lt;&lt;"function overload with one parameter: "&lt;&lt;one&lt;&lt;endl;<br>}<br><br>void gdb::overload(int one, int two)<br>{<br>    cout&lt;&lt;"function overload with two paremeters: "&lt;&lt;one&lt;&lt;" "&lt;&lt;two&lt;&lt;endl;<br>}<br><br>void gdb::loop()<br>{<br>    int loop_array[10];<br>    for(int i=0; i&lt;10; i++)<br>    {<br>        loop_array[i] = i;<br>    }<br><br>    int v=3;<br>    v=3;<br>    v=4;<br>}<br><br>void gdb::catch_ex(int ex)<br>{<br>    int e = ex;<br>    try<br>    {<br>        if(e &lt;= 0)<br>        {<br>            throw e;<br>        }<br>        else<br>        {<br>            cout&lt;&lt;"function catch_ex: "&lt;&lt;ex&lt;&lt;endl;<br>        }<br>    }<br>    catch(int x)<br>    {<br>        cout&lt;&lt;"exception: "&lt;&lt;x&lt;&lt;endl;<br>    }<br>}<br></pre>
<u>test.cpp</u>
<pre class="example">#include "gdb.h"<br><br>int main()<br>{<br>    gdb g(5);<br>    g.overload(1);<br>    g.overload(1, 2);<br>    g.loop();<br><br>    g.catch_ex(3);<br>    g.catch_ex(-1);<br><br>    return 0;<br>}<br></pre>
<p><a name="startup" id="startup"></a>
好了，现在开始调试。首先启动gdb，指定要调试的可执行文件。前面已经说过了，可以简单地使用gdb program来启动。或者可以首先启动gdb，然后用file命令指定要调试的文件。下面是仅启动gdb后的画面：
<img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/gdb_startup.png" alt=""></p>
<p>现在用file命令指定要调试的文件：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/gdb_file.png" alt=""></p>
<p><a name="run" id="run"></a>
然后就可以用 <strong>run</strong> 或者 <strong>r</strong> 命令来运行程序。在运行之前，你可能需要为程序设定一些信息，这些信息有一下四种：</p>
<p>1)程序参数
</p>
<blockquote>
<p class="quoted">可以用set args命令设定程序的参数。设定完后可以用show args查看设置的是否正确。如果set args后面不带任何参数，则向程序传递的参数为空。</p>
</blockquote>
<p>2)环境
</p>
<blockquote>
<p class="quoted">这儿的环境就是在系统/用户配置文件中设置的环境变量,像HOME, PATH之类的.GDB提供了在调试的时候改变这些变量值的方式,这样当需要的时候就不用退出gdb来重新设置.GDB提供的命令有:</p>
</blockquote>
<blockquote>
<p class="quoted">a) path <em>directory</em> －－ 将 <em>directory</em> 加到环境变量PATH前面.  <strong>注意</strong> 对PATH的改变只对调试的程序有效, GDB使用的PATH不会有改变.<sup><a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#fn.1" class="footref" name="fnr.1">1</a></sup></p>
</blockquote>
<blockquote>
<p class="quoted">b) show paths －－ 显示PATH的值。</p>
</blockquote>
<blockquote>
<p class="quoted">c) show environment [<em>varname</em>] －－ 显示环境变量varname的值，如果不指定varname，则显示所有环境变量的值。</p>
</blockquote>
<blockquote>
<p class="quoted">d) set environment <em>varname</em> [= <em>value</em>] －－ 设置环境变量varname的值为value。这个改变只是对调试的程序生效。如果不提供value，则将varname的值置为空。</p>
</blockquote>
<blockquote>
<p class="quoted">e) unset environment <em>varname</em> －－ 从环境中移除传递给程序的变量varname。</p>
</blockquote>
<p>3)工作目录
</p>
<blockquote>
<p class="quoted">在启动gdb调试程序的时候，被调试的程序会从gdb继承工作目录。当然gdb也提供了命令来修改工作目录：</p>
</blockquote>
<blockquote>
<p class="quoted">a) cd <em>directory</em> －－ 将 <em>directory</em> 设为新的工作目录。</p>
</blockquote>
<blockquote>
<p class="quoted">b) pwd －－ 显示当前工作目录。</p>
</blockquote>
<p>4)标准输入输出
</p>
<blockquote>
<p class="quoted">还没找到在windows里面这个东西有啥用，现在也没有linux可用，不好多说。有需要的自己看gdb手册吧。我简单抄一下手册吧。</p>
</blockquote>
<blockquote>
<p class="quoted">在gdb中，可以将run命令的输入输出重定向到文件或者其他终端。也可以通过tty命令设置被调试程序输入输出的设备。命令格式是：</p>
</blockquote>
<blockquote>
<p class="quoted">tty <em>terminal</em>  或者 set inferior-tty <em>terminal</em>.</p>
</blockquote>
<blockquote>
<p class="quoted">tty 就是 set inferior-tty 的别名。</p>
</blockquote>
<hr>
<p class="first">咚咚咚咚，下面正式开始！</p>
<p><a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#startup">上面</a>我们已经启动了程序, 也知道了如何<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#run">运行</a>程序。可是如果你直接执行run命令会发现，程序直接运行结束了。如果你想在某一行或者某个函数调用的地方，或者当某个变量/表达式的值改变的时候，也或者在某些事件发生的时候－－例如抛出异常、加载动态库，或者创建子进程－－的时候停止程序运行，那应该怎么办呢？</p>
<p>有了gdb，一切就都好办了:), 利用下面这三个强大的武器，你可以任意的停止程序。小心了，大家小心了，偶要祭出这三件宝物了，它们是：</p>
<h3><a name="sec8" id="sec8"></a>
<a name="breakpoint" id="breakpoint"></a>断点</h3>
<p class="first">断点就是指定一个位置，使得程序运行到这个位置的时候会停下来（当然，还可以设置条件断点，当运行到指定位置时，只有满足了设置的条件，程序才会停下来），这样便于观察程序的内部状态。断点相关的命令主要有：</p>
<p>a)break <em>location</em>
</p>
<blockquote>
<p class="quoted">在指定位置 <em>location</em> 处设置断点，这里的 <em>location</em> 可以是函数名，行号，指令地址等（关于如何指定 <em>location</em> ,可以看<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#location">这里</a>）。</p>
</blockquote>
<p>b)break
</p>
<blockquote>
<p class="quoted">如果不指定任何参数，break会在选定的<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#stack">栈帧</a>的下一条指令处设置断点。</p>
</blockquote>
<p>c)break <a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#location">...</a> if <em>cond</em>
</p>
<blockquote>
<p class="quoted">设置条件断点。每次到达断点的时候都会对表达式 <em>cond</em> 求值，只有当结果为非0的时候程序才会在这个断点停下来。</p>
</blockquote>
<p>d)tbreak <em>args</em>
</p>
<blockquote>
<p class="quoted">设置一个只生效一次的断点。args跟break命令里的参数意义相同（也就是说，可以为location，为空，或者条件）。</p>
</blockquote>
<p>e)hbreak <em>args</em>
</p>
<blockquote>
<p class="quoted">设置硬件断点。</p>
</blockquote>
<p>f)thbreak <em>args</em>
</p>
<blockquote>
<p class="quoted">设置只生效一次的硬件断点。</p>
</blockquote>
<p>g)rbreak <em>regex</em>
</p>
<blockquote>
<p class="quoted">在所有匹配正则表达式 <em>regex</em> 的函数上设置断点。</p>
</blockquote>
<p>h)info breakpoints [n]</p>
<p>i)info break [n]</p>
<p>j)info watchpoints [n]</p>
<blockquote>
<p class="quoted">上面三个命令都是列出当前的断点、观察点和捕捉点，如果指定参数n，则仅列出第n个的信息。</p>
</blockquote>
<p>来试验一把吧。首先用gdb启动程序，假设我们想在test.cpp的 g.overload(1) 这一行添加一个断点，那就执行命令：b test.cpp:6,执行完后：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/normal_break.png" alt=""></p>
<p>这时可以用info break等命令查看断点信息：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/info_break.png" alt=""></p>
<p>然后我们运行程序，看看有什么效果。</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/normal_break_run.png" alt=""></p>
<p>看到了吧，程序停在了断点所在的行。这时可以用where或者frame查看当前的栈帧信息，也可以用 <a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#data">print</a> 查看一些变量或者表达式的信息，或者info args查看参数信息，等等。</p>
<p>其他的命令大家可以自己尝试一下。</p>
<hr>
<p class="first">有时候我们并不确定要在哪里加断点，例如当我们想在某个变量被改变或者被读、被写的时候让程序停下来，可能由于访问变量的地方比较多，要想每个地方都加上断点比较麻烦，而且很可能有遗漏，这时候我们就需要依赖另一个强大的命令了，也就是观察点。</p>
<h3><a name="sec9" id="sec9"></a>
<a name="watchpoint" id="watchpoint"></a>观察点</h3>
<p class="first">观察点是一类特殊的断点，如果针对某个变量或者表达式指定一个观察点，那么当它们的值被读/写的时候，gdb会停止程序的执行。你不需要像设置断点时那样明确指定这个观察点在程序中的位置。观察点相关的命令有：</p>
<p>a)watch <em>expr</em> [thread <em>threadnum</em>]
</p>
<blockquote>
<p class="quoted">对 <em>expr</em> 设置一个观察点。当 <em>expr</em> 的值被改变的时候，gdb会停止程序的运行。</p>
</blockquote>
<blockquote>
<p class="quoted">如果指定了线程参数thread <em>threadnum</em> ，则 <strong>只有</strong> 在线程 <em>threadnum</em> 改变 <em>expr</em> 的值时，程序才会停止。</p>
</blockquote>
<p>b)rwatch <em>expr</em> [thread <em>threadnum</em>]
</p>
<blockquote>
<p class="quoted">对 <em>expr</em> 设置一个读观察点。当程序读 <em>expr</em> 的值时，gdb会停止程序的运行。</p>
</blockquote>
<p>c)awatch <em>expr</em> [thread <em>threadnum</em>]
</p>
<blockquote>
<p class="quoted">对 <em>expr</em> 设置一个访问观察点。当程序读或者写 <em>expr</em> 时，gdb会停止程序的运行。</p>
</blockquote>
<p>d)info watchpoints
</p>
<blockquote>
<p class="quoted">显示所有的断点、观察点、捕捉点。跟info break 相同。</p>
</blockquote>
<p>下面再来看看观察点的使用。</p>
<p>首先我们设置一个断点在g.loop()这一行，然后运行到这里。step进入loop()函数。这一串命令的执行如下：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/watch_begin.png" alt=""></p>
<p>这时我们已经进入loop()函数，现在我们设置几个观察点。设置命令序列和设置完后的效果如小：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/watch_set.png" alt=""></p>
<p>可以看到有5个停止点，其中前两个是我们设置的断点，后面三个是观察点。分别为watch, rwatch 和 awatch。另外还有一个地方就是，x86上默认是硬件观察点。</p>
<p>好了，来运行一下试试。</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/watch.png" alt=""></p>
<p>到达第一个观察点的时候程序停止运行，同时打印出了变量的旧值和新值，以及观察点的位置。</p>
<p>下面我们接着运行，看看遇到后面的观察点的时候又会怎样。</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/watch2.png" alt=""></p>
<p>程序在第三个观察点停了下来（第二个观察点为读观察点），同样打印出了变量的新旧值和观察点的位置。第二个观察点由于是读观察点，而程序中没有读这个变量的地方，因此运行的时候被跳过了。为了看一下读观察点的效果，我们再设置一个读观察点：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/read_watch.png" alt=""></p>
<p>i是循环内的迭代器，它会被复制给loop_array[i]变量，也就是会被读。可以看到，程序会停止运行，输出i的值。注意：每次对i的读操作都会使得程序停止。下面是两次执行continue命令后的输出：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/rwatch_iter.png" alt=""></p>
<p>观察点的内容差不多就这些了。另外有个需要注意的地方就是: <strong>watch命令设置的观察点只有在变量或者表达式的值被改变得时候才会使得程序停止运行，如果只是被写，但是值没有改变，则程序不会停止。</strong></p>
<hr>
<p class="first">上面已经讲了断点、观察点，而对于某些情况，这两种停止点并不是最有效的方式。例如想在c++程序中跑出异常的时候停
止程序，这时候用断点就不够有效了，因为程序中可能好多异常处理的地方，如果一个个设置断点，那就太麻烦了（当然如果只处理某几个异常，用断点也无不可，
甚至用起来更灵活）；而观察点就更不可用了。</p>
<p>这种情况就需要用到捕捉点了。</p>
<h3><a name="sec10" id="sec10"></a>
<a name="catchpoint" id="catchpoint"></a>捕捉点</h3>
<p class="first">捕捉点也是一类特殊的断点，它可以使得程序在某种事件发生时停止运行，例如c++异常，或者加载动态库、创建子进程等。设置捕捉点的命令是catch.</p>
<p>catch <em>event</em></p>
<p>其中 <em>event</em> 可以是：</p>
<p>a)throw
</p>
<blockquote>
<p class="quoted">c++抛出异常。</p>
</blockquote>
<p>b)catch
</p>
<blockquote>
<p class="quoted">c++捕捉异常。</p>
</blockquote>
<p>c)exception
</p>
<blockquote>
<p class="quoted">Ada异常。</p>
</blockquote>
<p>d)exception unhandled
</p>
<blockquote>
<p class="quoted">程序中未处理的异常。</p>
</blockquote>
<p>e)assert
</p>
<blockquote>
<p class="quoted">失败的Ada断言。</p>
</blockquote>
<p>f)exec
</p>
<blockquote>
<p class="quoted">对exec的调用（只在HP-UX和GNU/Linux中可用）。</p>
</blockquote>
<p>g)fork
</p>
<blockquote>
<p class="quoted">对fork的调用（只在HP-UX和GNU/Linux中可用）。</p>
</blockquote>
<p>h)vfork
</p>
<blockquote>
<p class="quoted">对vfork的调用（只在HP-UX和GNU/Linux中可用）。</p>
</blockquote>
<p>i)load
</p>
<blockquote>
<p class="quoted">动态加载共享库（只在HP-UX中可用）。</p>
</blockquote>
<p>j)load <em>libname</em>
</p>
<blockquote>
<p class="quoted">动态加载共享库 <em>libname</em> （只在HP-UX中可用）。</p>
</blockquote>
<p>k)unload
</p>
<blockquote>
<p class="quoted">卸载已加载的共享库（只在HP-UX中可用）。</p>
</blockquote>
<p>l)unload <em>libname</em>
</p>
<blockquote>
<p class="quoted">卸载已加载的共享库 <em>libname</em> （只在HP-UX中可用）。</p>
</blockquote>
<p>还有一个设置只生效一次的捕捉点的命令是： tcatch <em>event</em> 。</p>
<p>下面再看一下捕捉点的使用。</p>
<p>首先在vtest.cpp的 g.catch_ex(-1); 设置一个断点，然后运行，进入此函数。</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gdb/catch_init.png" alt=""></p>
<p>现在我们设置一个捕捉点。继续运行：</p>
<p class="image"><img src="http://www.cppblog.com/images/cppblog_com/lucency/gd/catch_begin.png" alt=""></p>
<p>可以看到程序在抛出异常的地方停止了。</p>
<hr>
<h3><a name="sec11" id="sec11"></a>
删除断点</h3>
<p class="first">当断点不再需要了，那就应该删除掉，否则每次执行到断点的位置程序都要停下来，会把人逼疯的。删除断点的命令有两个：clear和delete。</p>
<p>a)clear [ <em>location</em> ]
</p>
<blockquote>
<p class="quoted">如果不指定 <em>location</em> ，则删除选择的栈帧中下一条要执行的指令上的任何断点。如果选择的是最内部的栈帧（也就是当前正执行的函数的栈帧），则clear会将刚刚使程序停止的断点被删除。
关于 <em>location</em> 的说明可以看<a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#location">这里</a>。</p>
</blockquote>
<p>b)delete [breakpoints] [ <em>range</em> ... ]
</p>
<blockquote>
<p class="quoted">删除指定范围 <em>range</em> 那的所有的断点、观察点、捕捉点。如果不指定参数 <em>range</em> ，则会删除所有的停止点。这里的 <em>range</em> 指定的是断点编号区间。可以用info break查看断点信息。</p>
</blockquote>
<hr>
<h3><a name="sec12" id="sec12"></a>
禁用断点</h3>
<p class="first">如果不想删除断点，只是想暂时使它失效，则可以使用disable命令。disable命令的形式如下：</p>
<p>a)disable [breakpoints] [ <em>range</em> ...]
</p>
<blockquote>
<p class="quoted">使指定区间 <em>range</em> 内的断点失效。如果不指定 <em>range</em> ，则所有的断点都失效。</p>
</blockquote>
<p>使断点生效的命令是enable，形式有：</p>
<p>a)enable [breakpoints] [ <em>range</em> ...]
</p>
<blockquote>
<p class="quoted">使指定区间 <em>range</em> 内的断点或者所有断点生效。</p>
</blockquote>
<p>b)enable [breakpoints] once <em>range</em>...
</p>
<blockquote>
<p class="quoted">使指定区间内的断点生效一次。</p>
</blockquote>
<p>c)enable [breakpoints] delete <em>range</em>...
</p>
<blockquote>
<p class="quoted">使指定区间内的断点生效一次，然后删除。</p>
</blockquote>
<hr>
<h3><a name="sec13" id="sec13"></a>
断点条件</h3>
<p class="first">断点条件使得只有在相应的条件满足时，断点才有效。这里的条件表达式跟程序所用语言的逻辑表达式的语法相同，例如在c/c++语言里，可以用 a==b 或者 x&amp;&amp;y这种表达式。</p>
<p>断点条件可以在设置断点的时候指定，也可以在断点设置后通过condition命令来设置或者改变。 condition的形式为：</p>
<p>a)condition <em>bnum</em> <em>expression</em>
</p>
<blockquote>
<p class="quoted">设置表达式 <em>expression</em> 为停止点 <em>bnum</em> 的条件。</p>
</blockquote>
<p>b)condition <em>bnum</em>
</p>
<blockquote>
<p class="quoted">删除停止点 <em>bnum</em> 的条件。</p>
</blockquote>
<p>还有一个命令，可以使得gdb忽略断点的条件一定的次数，其形式为：</p>
<p>a)ingore <em>bnum</em> <em>count</em></p>
<hr>
<h3><a name="sec14" id="sec14"></a>
<a name="location" id="location"></a>指定位置</h3>
<p class="first">许多gdb命令都接受一个用于指定程序位置的参数。位置的指定方式有下面几种：</p>
<p>a) <em>linenum</em>
</p>
<blockquote>
<p class="quoted">当前源文件的行号。</p>
</blockquote>
<p>b) <em>-offset</em>
</p>
<blockquote>
<p class="quoted">当前行前面，跟当前行间隔为 <em>offset</em> 的行。当前行可以这样确定：使用list命令，打印出来的最后一行就是当前行；或者对于断点命令，选定的栈帧中，程序停止执行的位置就是当前行。</p>
</blockquote>
<p>c) <em>+offset</em>
</p>
<blockquote>
<p class="quoted">当前行后面，跟当前行间隔为 <em>offset</em> 的行。</p>
</blockquote>
<p>d) <em>filename:linenum</em>
</p>
<blockquote>
<p class="quoted">源文件 <em>filename</em> 中的行 <em>linenum</em>。</p>
</blockquote>
<p>e) <em>function</em>
</p>
<blockquote>
<p class="quoted">当前源文件中的函数 <em>function</em>。</p>
</blockquote>
<p>f) <em>filename:function</em>
</p>
<blockquote>
<p class="quoted">源文件 <em>filename</em> 中的函数 <em>function</em>。</p>
</blockquote>
<p>g) * <em>address</em>
</p>
<blockquote>
<p class="quoted">指定程序地址 <em>address</em>。常用的 <em>address</em> 形式有：</p>
</blockquote>
<blockquote>
<p class="quoted"><em>expression</em> －－ 当前语言中有效的表达式。</p>
</blockquote>
<blockquote>
<p class="quoted"><em>funcaddr</em>   －－ 函数的地址。在c/c++中就是函数名。</p>
</blockquote>
<blockquote>
<p class="quoted"><em>'filename'::funcaddr</em> －－ 源文件 <em>filename</em> 中的函数地址 <em>funcaddr</em>。</p>
</blockquote>
<hr>
<p><strong>后面懒得写了，暂时先放一放。发现就算是抄文档，内容多了也是个很累人的活。唉，懒了，不行了...</strong></p>
<h3><a name="sec15" id="sec15"></a>
<a name="stack" id="stack"></a>栈</h3>
<p class="first">待添加</p>
<hr>
<h3><a name="sec16" id="sec16"></a>
<a name="data" id="data"></a>数据</h3>
<p class="first">待添加</p>
<hr>
<h2><a name="sec17" id="sec17"></a>
五 示例2</h2>
<p class="first">待添加</p>
<hr>
<h2><a name="sec18" id="sec18"></a>
六 后记</h2>
<p class="first">这篇文章只是捡了GDB中最常用的一些东西，而且还只是最常用的东西中的一小部分，有兴趣或者需要的可以直接看GDB的文档，可以在<a href="http://www.gnu.org/software/gdb/documentation/">这里</a>找到。</p>
<hr>
<p class="footnote"><a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#fnr.1" class="footnum" name="fn.1">1.</a> 不知道是不是因为windows和linux系统的不同，用gdb启动程序后，执行show paths后输出：Executables and object file path: 。也就是说输出的值是空的。</p>
<!-- Page published by Emacs Muse ends here -->  <img src ="http://www.cppblog.com/lucency/aggbug/59214.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-08-18 13:31 <a href="http://www.cppblog.com/lucency/archive/2008/08/18/59214.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>Suffix Trees[译]</title><link>http://www.cppblog.com/lucency/archive/2008/07/12/55944.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Sat, 12 Jul 2008 02:44:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/07/12/55944.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/55944.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/07/12/55944.html#Feedback</comments><slash:comments>5</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/55944.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/55944.html</trackback:ping><description><![CDATA[<font face="sans-serif">这两天看了下后缀树的介绍,发现一篇文章,讲得挺清楚的,就翻译了下,希望对大家有帮助.原文章在<a href="http://www.cise.ufl.edu/%7Esahni/dsaaj/enrich/c16/suffix.htm">这儿</a><br>希望原作者不要找我麻烦哈。如果有啥版权问题，我马上删掉。也因此，<font color="#cc0000"><strong>此文暂时禁止转载</strong></font>。此中文版如果有版权,归本人所有.<br><br>我英语本来就不咋地，有些地方肯定比较生硬或者有误，欢迎指正。<br><br>顺便贴个自己的代码，只是一个简单的<a href="http://www.cppblog.com/Files/lucency/suffix_tree.rar">实现</a>，没有考虑效率问题。如果想要更成熟稳定的，可以<a target="_blank" href="http://en.wikipedia.org/wiki/Suffix_tree">看这里</a>。<br><br>再顺个便抱怨两句。文章中图片要是多点，发布的时候还真是麻烦，要一个个插入才行。用ScribeFire发布好像也不能直接上传图片（也可能是我不会）。<br><br></font><font color="#cc0000"><big><big>Data Structures, Algorithms, &amp; Applications in Java<br>Suffix Trees<br>Copyright 1999  Sartaj Sahni</big></big></font>
<h1><strong><small></small></strong></h1>
<font face="sans-serif"><br></font>
<div align="left"><font color="#3333ff" face="sans-serif"><big><font color="#000000"><font color="#3333ff"><strong>你看见过这个字符串吗?</strong>(</font></font></big></font><font color="blue" face="sans-serif"><big><big><small>Have You Seen This String?</small>)</big></big></font><font color="#3333ff" face="sans-serif"><big><font color="#000000"><br><br><small>在经典的<strong>子串查找</strong>问题中,给定一个字符串S和模式P,查找P在S中是否存在.例如,模式<font color="#3333ff">P = cat<font color="#000000">在字符串S1 = </font></font></small></font></big></font><font face="sans-serif"><code class="var">The big cat ate the small catfish</code></font><font color="#3333ff" face="sans-serif"><big><font color="#000000"><small><font color="#3333ff"><font color="#000000">存在(两次)</font></font></small></font></big></font><font color="#3333ff" face="sans-serif"><big><font color="#000000">,<small>但是不在字符串S2 = Dogs for sale中.<br><br>人类基因组计划的研究者者经常要基因数据库--其中包含数以万计的基因--中查找<font color="#3333ff">子串/模式</font>(这里的<font color="#3333ff">子串</font>和<font color="#3333ff">模式</font>可以相互替代使用).每个基因由字符集<font color="#3366ff">{A,C,G,T}</font>中的字符构成的序列或者说字符串表示.但是,基因库里的大部分字符串长度大约<font color="#3366ff">2000</font>个字符,还有一些有数以万计的字符.考虑到基因库的大小和子串查找的频率,一个尽可能快的用来从基因库的字符串中查找子串的算法是很必要的.<br><br>我们可以使用在标准的算法教科书中描述的模式匹配算法在字符串S中查找模式P.这个算法的复杂度是<font color="#3366ff">O(|P| + |S|)</font>, 这里的<font color="#3366ff">|P|</font>表示P的长度(例如字符(letter)或数字(digit)的个数).当考虑到模式P可能出现在S中的任何位置时,这个复杂度看起来是很好的.因此,在得出P不在S中存在前,我们必须测试S的每个<font color="#3366ff">字符(letter)</font>/<font color="#3366ff">数字(digit)</font>(这里的术语字符和数字意义相同。译注：后面会统一翻译为字符).更进一步,在我们得出模式在字符串中出现前,我们必须测试模式的每个字符.因此,每个字符串查找算法消耗的时间是P和S长度的线性函数.<br><br>当用经典的字符串匹配算法在S中查找多个模式<font color="#3366ff">P1,P2,...,Pk</font>时,消耗的时间是<font color="#3366ff">O(|P1| + |P2| + ... + |Pk| + k|S|)</font>(因为查找Pi消耗的时间是<font color="#3366ff">O(|Pi| + |S|)</font>).我们马上要学习的后缀树结构能将复杂度减少到<font color="#3366ff">O(|P1| + |P2| + ... + |Pk| + |S|)</font>.此时的O(|S|)用于为S创建后缀树;查找每个模式只需要花费O(|Pi|)的时间(在S的后缀树创建完成之后).因此,一旦S的后缀树创建完后,查找每个模式需要的时间决定于模式的长度.<br><br><strong><big><font color="#3333ff">后缀树<br></font></big></strong><br>字符串S的<strong>后缀树</strong>实际上是S的所有非空后缀的压缩trie树.因此我们有时将后缀树称为trie,将它的子树称为subtrie.（不清楚trie树的可以看<a href="http://www.cise.ufl.edu/%7Esahni/dsaaj/enrich/c16/tries.htm">这里</a>或者<a target="_blank" href="http://en.wikipedia.org/wiki/Trie">这里</a>）<br><br></small></font></big></font><font color="#3333ff" face="sans-serif"><big><font color="#000000"><small>字符串</small></font></big></font><font color="#3333ff" face="sans-serif"><big><font color="#000000"><small><font color="#3366ff">S=peeper</font>的非空后缀是<font color="#3366ff">peeper,eeper,eper,per,er</font>和r.因此字符串peeper的后缀树是包含元素(这些元素也是关键字)peeper,eeper,eper,per,er和r的压缩trie树.字符串peeper的字符集是<font color="#3366ff">{e,p,r}</font>.因此,压缩trie树的基数(radix)是3.如果需要,我们可以用映射<font color="#3366ff">e -&gt; 0, p -&gt; 1, r -&gt; 2</font>将字符串的字符转换为数字.这种转换只有在我们使用一种节点结构--每个节点有一个包含子节点指针的数组--才需要.图1展示了peeper后缀的压缩trie树(带有变信息).这棵压缩trie树也是字符串peeper的后缀树.<br><br></small></font></big></font>
<div align="center"><font face="sans-serif"><img src="http://www.cppblog.com/images/cppblog_com/lucency/suffix1.gif" alt="" height="162" width="326"><br></font><font color="blue" face="sans-serif">Figure 1 Compressed trie for the suffixes of peeper <br></font>
<div align="left"><font face="sans-serif"><br>由于信息节点(译注:也就是叶节点)D-I中的数据是peeper的后缀,每个信息节点只需要保存它所表示的后缀在字符串中的起始索引.当我们从1开始从左到右索引peeper中的字符时,信息节点D-I只需要保存索引<font color="#3366ff">6,2,3,5,1</font>和<font color="#3366ff">4</font>即可.利用保存在信息节点中的索引,我们可以访问S的后缀.结果如图2所示。<br><br></font>
<div align="center"><font color="blue" face="sans-serif"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix2.gif" height="255" width="317"> </font><font face="sans-serif"><br></font><font color="blue" face="sans-serif">Figure 2 Modified compressed trie for the suffixes of peeper </font><font face="sans-serif"><br></font></div>
<font face="sans-serif"><br></font></div>
<div align="left"><font face="sans-serif"><br>每个分支节点的第一个字段是到以其为根的subtrie中元素(译注:应该是指子节点)的引用.我们可以用被引用的元素的首字符的索引代替元素引用.图3展示了替换后的树.我们将会用这种修改后的形式作为后缀树的表示.<br><br></font>
<div align="center"><font color="blue" face="sans-serif"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix3.gif" height="255" width="317"> </font><font face="sans-serif"><br></font><font color="blue" face="sans-serif">Figure 3 Suffix tree for peeper </font><font face="sans-serif"><br></font></div>
<font face="sans-serif"><br><br>如果后缀树的每条边用从分支节点到其子节点的字符(串)标注,可以更容易描述后缀树的查找和构建算法.标签的第一个字符用来确定要移到哪一个子节点,剩余的字符表示要跳过的字符(串).图4展示的就是图3用这种方式画出后得到的后缀树.<br><br></font>
<div align="center"><font color="blue" face="sans-serif"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix4.gif" height="147" width="326"> </font><font face="sans-serif"><br></font><font color="blue" face="sans-serif">Figure 4 A more humane drawing of a suffix tree </font><font face="sans-serif"><br></font></div>
<font face="sans-serif"><br>在后缀树的更直观的画法中,从任意根节点到信息节点的路径上所有边的标签拼接在一起得到的就是信息节点表示的后缀.When the digit number for the root is not 1, the humane drawing of a suffix tree includes a head node with an edge to the former root. This edge is labeled with the digits that are skipped over. <br><br>后缀树的某个节点表示的字符串是由根节点到此节点的路径上的标签拼出来的.图4中的节点A表示空串<font color="#3366ff">epsilon</font>,节点C表示字符串pe,节点F表示字符串eper.<br><br>由于后缀树的关键字长度不同,我们必须保证没有一个关键字是另一个的真前缀(proper prefix).当字符串S的最后一个字符在S中只出现一次,就不会出现S的其中一个后缀是另一个后缀的真前缀的情况.在字符串peeper中,最后的字符是r,并且只出现了一次.因此peeper的后缀中就不会出现真前缀的情况.字符串data的最后字符是a,并且出现了两次.因此,data有两个以a开始的后缀,ata和a.后缀a是ata的真前缀.<br><br>当字符串S的最后字符在S中出现多于一次,就必须在S的所有后缀后面附加一个新的字符(比如说#),这样任何一个后缀都不会是其他后缀的前缀.还有一种方法是,我们可以在S后面附加新的字符#,得到新的串$#,然后创建$#的后缀树.这样做之后得到的后缀树比直接在S的每个后缀后面附加#会多一个后缀#.<br><br><big><font color="#3333ff">让我们查找那个子串吧</font></big><br></font><font color="#3366ff" face="sans-serif">但是，首先要说明几个术语</font><font face="sans-serif"><br>用<font color="#3366ff">n=|S|</font>表示要创建后缀树的字符串的长度.我们从左到右依次给S的字符编号,最左边的编号为1.<font color="#3366ff">S[i]</font>表示S的第i个字符,<font color="#3366ff">suffix(i)</font>表示从字符i开始的后缀<font color="#3366ff">S[i]...S[n],1&lt;=i&lt;=n</font>.<br><br></font><font color="#3366ff" face="sans-serif">关于查找</font><font face="sans-serif"><br>当在S中查找模式P时,用到的一个基本的观察(observation)是P在S中出现当且仅当P是S的某个后缀的前缀.<br><br>假设<font color="#3366ff">P = P[1]...P[k] = S[i]...S[i+k-1]</font>.则P是suffix(i)的前缀.既然suffix(i)在我们的压缩trie树中(也就是后缀树),我们可以利用在压缩trie树中查找关键字前缀的策略来查找P.<br><br>让我们在字符串<font color="#3366ff">S=peeper</font>中查找模式<font color="#3366ff">P=per</font>.假设我们已经为S创建好了后缀树(图4).查找从根结点A开始.因为P[1]=p,我们顺着标签以p开始的边.当顺着此边继续时,我们对边标签的剩余字符和P的后续字符做比较.由于标签的剩余字符跟P的字符相符,我们到达分支C.在到达C的过程中,我们已经使用了P的前两个字符.第三个字符是r,因此我们从节点C顺着以r开始的边继续.由于这条边没有其他字符,因此不需要其他比较,到达信息节点I.这时,P中的字符已经用完了,我们就断定P在S中.由于已经到达信息节点I,我们断定P实际上是S的后缀.在实际的后缀树表示中(而不是如图4这种人性化的表示),信息节点I包含索引4,这告诉我们模式P=per由S=peeper的第4个字符开始(也就是说,P=suffix(4)).更进一步,我们可以得到P在S中只出现一次;如果一个模式在字符串中出现多次,查找会在分支节点中止,而不是信息节点.(译注:例如查找pe,查找在节点C中止,说明它在S中出现了两次--C有两个叶子节点)<br><br>现在我们来查找模式<font color="#3366ff">P=eeee</font>.还是从根结点开始.由于P的第一个字符是e,我们沿着以e开始的边到达B.下一个字符还是e,因此我们从B开始沿着以e开始的边继续.在沿着这条边向下的过程中,我们需要比较边标签的剩余字符per和P的剩余字符ee.比较第一对字符(p,e)时无法匹配,因此我们断定P不在S中.<br><br>假设我们查找模式<font color="#3366ff">P=p</font>.从根开始,沿着以p开始的边往下.在向下的过程中,我们比较边的剩余字符(只有字符e)和模式的剩余字符.由于已经到P的结尾,我们断定P是以节点C为根的subtrie的所有关键字的前缀.可以通过遍历以C为根的subtrie、访问subtrie的所有信息节点找到P出现的所有位置。如果只需要P出现的一个位置，可以利用存储在节点C的第一部分的索引。当沿着到节点X的边查找时模式结束，我们就说已到达节点X；查找在节点X结束。<br><br>当查找模式<font color="#3366ff">P=rope</font>，利用P的第一个字符r到达信息节点D。由于模式还没有结束，我们必须根据D的字符检查P的剩余字符。检查显示P不是D的关键字的前缀，因此P不在S=peeper中。<br><br>我们要做的最后一个查找是对模式P=pepe。从图4的根结点开始，我们沿着以p开始的边到达节点C。下一个未检查的字符是p。因此，从C开始，我们希望沿着以p开始的边继续。由于没有满足这个条件的边，我们断定pepe不在peeper中。<br><br><br><big><font color="blue">Other Nifty Things You Can Do with a Suffix Tree</font></big><br><br>一旦为字符串S创建好了后缀树，我们就可以在O(|P|)时间内判断S是否包含P。这意味着如果为莎士比亚的戏剧&#8220;罗密欧与朱丽叶&#8221;的内容创建了后缀树，我们就可以非常快的判断文章中是否存在短语wherefore art thou。事实上，只需话费比较18个字符的时间（模式的长度）。查找时间跟文章的长度无关。<br><br>其他可以快速完成的有趣事情：<br><br>1.查找模式P的所有出现。这是通过对P查找后缀树实现。如果P至少出现一次，查找会在信息节点或者分支节点中止。当中止于信息节点时，P只出现一次。如果中止于分支节点X，模式出现的所有地方可以通过访问以X为根的subtrie的信息节点来得到。如果我们按照下面的方式，这个访问操作可以在O(n)（n是模式出现的次数）时间内完成。<br><br>(a)<br>    将所有的信息节点按照节点所表示的后缀的字典序链起来（这也是从左到右扫描信息节点时遇到这些节点的顺序）。图4的信息节点会按照<font color="#3366ff">E,F,G,H,I,D</font>的顺序链接起来。<br><br>(b)<br>    在每个分支节点内，保存以此节点为根的subtrie的第一个和最后一个信息节点的引用。图4中节点A,B和C分别保存序对(E,D),(E,G)和(H,I)。我们用序对(firstInformationNode, lastInformationNode)周游以firstInformationNode开始、以lastInformationNode结束的链。这个周游会得到模式P出现的所有位置。注意，当我们在分支节点中保存序对(firstInformationNode, lastInformationNode)时，就不需要再保存到subtrie中的信息节点的引用（也就是字段element）。<br><br>2.查找包含模式P的所有字符串。假设我们有一些字符串<font color="#3366ff">S1,S2,... Sk</font>，我们想得到所有包含P的字符串。例如，基因库中包含数以万计的字符串，当一个研究员提交一个查询字符串，我们就要报告所有包含此模式的字符串。为了有效的执行这类查询，就需要创建一个包含字符串<font color="#3366ff">S1$S2$...$Sk#</font>的所有后缀的压缩trie树（也称为多字符串后缀树），这里的$,#是两个不在字符串S1, S2, ..., Sk中出现的不同字符。在后缀树的每个（分支）结点N中，保存所有的字符串Si的链表，其中Si是以N为根的subtrie中所有的信息节点表示的字符串的开始点位于其中的字符串（译注：真拗口啊，这儿的意思就是对某个信息节点L，如果L表示的字符串从Si的某个位置开始，那就将Si的引用放到L的父辈节点的链表中）。<br><br>3.查找S中出现次数至少为m&gt;1次的子串。这个查询可以按照下面的方式在O(|S|)时间内完成：<br>(a)周游后缀树，对每个分支节点X，保存从根节点到X节点的字符串的长度l和以X为根的subtrie中信息节点的数目m。<br>(b)周游后缀树，访问信息节点数&gt;=m的分支节点。l最大的分支节点表示的就是出现次数&gt;=m的最长子串。<br><br>注意步骤(a)只需要执行一次。完成后，我们可以对需要的任意m执行步骤(b)。另外还要注意，当m=2是，不需要确定subtrie中信息节点的数目。在后缀树中，每个分支节点之后有两个信息节点。<br><br>4.查找字符串S和T的最长公共子串。这可以按照下面的方式在<font color="#3366ff">O(|S|+|T|)</font>时间内完成：<br>(a)为S和T创建多字符串后缀树（也就是<font color="#3366ff">S$T#</font>的后缀树）<br>(b)周游后缀树，查找表示的字符串最长，并且以其为根的subtrie的信息节点表示的字符串中，至少有一个从S开始，另一个从T开始的字符串。<br><br>注意，有个相关的查找S和T的最长公共子序列的问题用动态规划算法在<font color="#3366ff">O(|S|*|T|)</font>时间内完成。<br><br><big><font color="#3333ff">如何创建你自己的后缀树</font></big><br></font><font color="#3366ff" face="sans-serif">三个观察(observation)</font><font face="sans-serif"><br>为了更有效的创建后缀树，我们为每个分支节点添加字段longestProperSuffix。表示非空字符串Y的分支节点的longestProperSuffix字段指向表示Y的最长真后缀的分支节点（Y的最长真后缀通过去掉Y的首字符得到）。根结点的longestProperSuffix未使用。<br><br>图5表示的是给图4加上最长真后缀指针后得到（经常将最长真后缀指针简称为后缀指针）。后缀指针用红色箭头表示。节点C表示字符串pe。pe的最长后缀e由节点B表示。因此C的后缀指针指向B。e的最长后缀是空串。由于根结点A表示空串，因此B的后缀指针指向A。<br><br></font>
<div align="center"><font color="blue" face="sans-serif"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix5.gif" height="148" width="326"> </font><font face="sans-serif"><br></font><font color="blue" face="sans-serif">Figure 5 Suffix tree of Figure 4 augmented with suffix pointers </font><font face="sans-serif"><br></font></div>
<font face="sans-serif"><br>观察1 如果S的后缀树有一个表示字符串Y的分支节点，那么后缀树中也有一个表示Y的最长后缀Z的分支节点。<br>证明 设P为表示Y的分支节点。由于P是分支节点，至少有两个不同的字符x和y，使得S中有两个分别以Yx和Yy开始的后缀。因此，S有两个分别以Zx和Zy开始的后缀。因此，S的后缀树中必然有一个对应Z的分支节点。<br><br>观察2 如果S的后缀树有一个表示Y的分支节点，那么树中对Y的每个后缀都有一个对应的分支节点。<br>证明 由观察1即可得到。<br><br>注意图5中有一个表示pe的分支节点。因此，树中一定有表示e和epsilon的分支节点。<br><br>在描述后缀树的创建算法时，有两个概念很有用：<font color="#3366ff">last branch node</font>和<font color="#3366ff">last branch index</font>。后缀suffix(i)的last branch node是表示suffix(i)的信息节点的父节点。在图5中，suffix(1)...suffix(6)的last branch node分别是C,B,B,C,B和A。对任意后缀suffix(i)，其last branch index lastBranchIndex(i)是在suffix(i)的last branch node中，产生分支的字符的索引。在图5中，lastBranchIndex(1)＝3,因为：suffix(1)=peeper，suffix(1)由信息节点H表示，H的父节点是C；C的分支是在suffix(1)的第三个字符产生的；suffix(1)的第三个字符是S[3]。可以验证一下，<font color="#3366ff">lastBranIndex[1:6] = [3,3,4,6,6,6]</font>。<br><br>观察3 在S的后缀树中， lastBranchIndex(i) &lt;= lastBranchIndex(i+1), 1 &lt;= i &lt; n。<br>证明作为练习。<br><br><big><font color="blue">Get Out That Hammer and Saw, and Start Building</font></big><br><br>为了创建你自己的后缀树，你必须由你自己的字符串开始。我们使用R = ababbabbaabbabb来阐述后缀树的构建过程。由于R的最后字符b出现了不止一次，我们在R后面附加字符#，为新的字符串S=R#创建后缀树。<br><br></font><font color="#000099" face="sans-serif">创建策略</font><font face="sans-serif"><br>后缀树的创建算法从表示空串的根结点开始。根结点是一个分支节点。创建后缀树过程的任何时候，都有一个分支节点被指定位活动节点(active node)。这是插入下一个后缀的起始节点。用activeLength表示根结点对应的字符串的长度。开始时，根节点是活动节点，activeLength=0。图6展示了开始时的状态，绿色的节点是活动节点。<br><br></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix6.gif" height="39" width="54"><br></font></strong><br><strong><font color="blue">Figure 6 Initial configuration for suffix tree construction<br></font></strong><br></font></div>
<font face="sans-serif"><br>随着处理的进行，我们会不断往树中添加分支节点和信息节点。新添加的分支节点用品红色表示，新添加的信息节点用青色表示。后缀指针为红色。<br><br>后缀按照<font color="#3366ff">suffix(1), suffix(2), ..., suffix(n)</font>的顺序依次插入到树中。后缀以这种顺序插入是通过从左到右扫描字符串S的方氏完成。用<font color="#3366ff">tree(i)</font>表示插入后缀suffix(1), ..., suffix(i)之后形成的树，<font color="#3366ff">lastBranchIndex(j, i)</font>表示tree(i)中后缀suffix(j)的last branch index。<font color="#3366ff">minDistance</font>表示从活动节点到即将插入的后缀的last branch index的距离的下界（译注：感觉这个东西在实现的时候没啥意义）。开始时，minDistance = 0并且lastBranchIndex(1,1) = 1。当插入suffix(i)时，满足条件<font color="#3333ff">lastBranchIndex(i,i) &gt;= i + activeLength + minDistance</font>。<br><br>为了向tree(i)中插入suffix(i+1)，我们必须遵循如下步骤：<br>1.确定lastBranchIndex(i+1, i+1)。为了完成这点，我们从当前活动节点开始。新后缀的开始的activeLength个字符（也就是字符S[i+1], S[i+2], ..., S[i + activeLength]）已知是跟当前活动节点表示的字符串相匹配的。因此，为了确定lastBranchIndex(i+1,i+1)，需要检测新后缀的activeLength + 1, activeLength + 2, ...字符。这些字符用于确定tree(i)中进一步处理时要经过的路径，此路径始于活动节点，当lastBranchIndex(i+1,i+1)确定时中止。根据已知的lastBranchIndex(i+1,i+1) &gt;= i + 1 + activeLength + minDistance，这个过程可以简化，从而得到效率提升。<br><br>2.如果tree(i)中没有表示字符串S[i]...S[lastBranchIndex(i+1,i+1)-1]的节点X，则创建一个。<br><br>3.为suffix(i+1)添加一个信息节点。这个信息节点是X的孩子，从X到信息节点的边上的标签是S[lastBranchIndex(i+1, i+1)]...S[n]。<br></font><font color="#3366ff" face="sans-serif"><br><font color="#000099">回到例子</font></font><font face="sans-serif"><br>我们从向图6中的树tree(0)插入suffix(1)开始。根结点是活动节点，activeLength = minDistance = 0。suffix(1)的第一个字符是S[1]=a。从tree(0)的活动节点开始没有以a开始的边（事实上，此时活动节点没有任何边）。因此，lastBranchIndex(1,1) = 1。我们创建一个新的信息节点和一条边，边的标签是整个字符串。图7展示了结果tree(1)。根结点依然是活动节点，activeLength和minDistance没有变化。<br><br></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix7.gif" height="151" width="274"><br></font></strong><br><strong><font color="blue">Figure 7 After the insertion of the suffix ababbabbaabbabb#<br></font></strong><br></font></div>
<font face="sans-serif"><br><br>在我们的画法中，信息节点的入边的标签标记为i+，i表示标签在S中的开始位置，+表示标签一直到字符串的结尾。因此，在图7中，1+表示字符串S[1]...S[n]。图7也展示了字符串S。新插入的后缀用青色表示。<br><br>为了插入后缀suffix(2)，我们再次从根结点开始检查后缀的activeLength + 1 = 1, activeLength + 2 = 2, ...,字符。因为suffix(2)的第一个字符是S[2]=b，活动节点没有以S[2]=b开始的边，所以lastBranchIndex(2,2) = 2。因此我们创建新的信息节点和标记为2+的边。结果如图8所示。根结点依然是活动节点，activeLength和minDistance依旧没有变化。<br><br></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix8.gif" height="151" width="274"><br></font></strong><br><strong></strong></font></div>
<div align="center"><font face="sans-serif"><strong><font color="blue">Figure 8 After the insertion of the suffix babbabbaabbabb#<br></font></strong><br></font></div>
<font face="sans-serif"><br>注意图8是关于suffix(1)和suffix(2)的压缩trie树tree(2)。<br><br>下一个后缀suffix(3)开始于S[3]=a。由于tree(2)的活动节点有一个以a开始的边，所以lastBranchIndex(3,3) &gt; 3。为了确定lastBranchIndex(3,3)，必需要查看suffix(3)的更过字符。尤其是，我们需要查看尽可能多的字符，以便区分suffix(1)和suffix(3)。首先比较后缀的第二个字符S[4]=b和边1+的第二个字符S[2]=b。由于S[4]=S[2]，必须做进一步的比较。下一步比较S[5]和S[3]。由于这两个字符不同，我们可以确定lastBranchIndex(3,3)是5。这时，我们需要更新minDistance为2.注意，因为lastBranchIndex(3,3) = 5 = 3 + activeLength + minDistance，这是minDistance的最大可能值。<br><br>为了插入suffix(3)，我们将tree(2)的边1+一分为二。第一条边的标签是1,2;第一条边的标签是3+。这两个边之间插入新的分支节点。另外，还要为新插入的后缀添加信息节点。结果如图9所示。边标签1,2显示为字符S[1]S[2] = ab。<br><br></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix9.gif" height="205" width="317"><br></font></strong><br><strong><font color="blue">Figure 9 After the insertion of the suffix abbabbaabbabb#<br></font></strong><br></font></div>
<font face="sans-serif"><br>tree(3)还没完成，因为还没有确定新加的分支节点的后缀指针。这个分支节点的最长后缀是b，但是对应b的分支节点不存在。别惊慌，下一个要创建的分支节点就是对应b的节点。<br><br>下一个要插入的后缀是suffix(4)。这是刚插入的suffix(3)的最长后缀。新后缀的插入过程由根据当前活动节点的后缀指针确定新的活动节点开始。由于根结点没有后缀指针，活动节点没有变化。因此activeLength也没有变化。但是，我们必须更新minDistance以满足lastBranchIndex(4,4) &gt;= 4 + activeLength + minDistance。显然，对于所有的i<n，lastbranchindex(i,i)>&lt;= lastBranchIndex(i+1,i+1)。因此，lastBranchIndex(i+1,i+1) &gt;= lastBranchIndex(i,i) &gt;= i + activeLength + minDistance。为了保证lastBranchIndex(i+1,i+1) &gt;= i + 1 + activeLength + minDistance，我们必须将minDistance减小1.<br><br>因为minDistance = 1，我们从活动节点开始，沿着S[4]S[5]...指定的路径记录。我们不需要比较开始的minDistance个字符，因为在minDistance+1之前的字符都已经保证是匹配的了。由于活动节点以S[4]=b开始的边的长度大于1,我们比较S[5]和边的第二个字符S[3]。因为这两个字符不同，这条边也要一分为二。第一条边的标签为2,2=b；第二条棉的标签为3+。在两条边之间添加新的分支节点F，还要为新插入的后缀创建信息节点G。G跟F之间通过标签为5+的边连接。结果如图所示。<br><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix10.gif" height="205" width="367"><br></font></strong><br><strong><font color="blue">Figure 10 After the insertion of the suffix bbabbaabbabb#<br></font></strong><br></font></div>
<font face="sans-serif"><br>现在我们要为插入后缀suffix(3)时创建的分支节点D设置后缀指针。这个后缀指针就是新创建的分支节点F。<br><br>节点F表示的字符串b的最长后缀是空串。因此F的后缀指针指向根结点。图11是添加了后缀指针的结果。<br><br>
<div align="center"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix11.gif" height="205" width="367"><br></font></strong><br><strong><font color="blue">Figure 11 Trie of Figure 10 with suffix pointers added<br></font></strong><br></div>
<br>下一个要插入的是suffix(5)。由于suffix(5)是刚插入的后缀suffix(4)的最长后缀，我们从活动节点的后缀指针开始。但是当前作为活动节点的根结点没有后缀指针。因此，活动节点不变。为了保持lastBranchIndex, activeLength, minDistance以及将插入的后缀的索引(5)之间的关系，需要将minDistance减少1.因此，minDistance变为0.<br><br>因为activeLength=0，我们需要从suffix(5)的首字符S[5]开始检查。活动节点有一条以S[5]=b开始的边。我们沿着这条边比较后缀字符和标签字符。由于所有的字符都匹配，我们到达节点F。现在F成为活动节点（在检查后缀字符的过程中，遇到的分支节点都成为新的活动节点），activeLength=1。我们从当前活动节点的某条边开始继续比较。由于下一个要比较的后缀字符是S[6]=a，我们使用以a开始的边（如果这样的边不存在，新后缀的lastBranchIndex是activeLength+1）。这条边的标签是3+。当比较到新后缀的字符S[10]=a和边的字符S[7]=b时，比较结束。因此，lastBranchIndex(5,5) = 10. minDistance设置为允许的最大值，也就是lastBranchIndex(5,5) - (index of suffix to be inserted) - activeLength = 10 - 5 - 1 = 4.。<br><br>为了插入suffix(5)，我们将节点F和C之间的边分裂为二。分裂出现在边(F,C)的splitDigit=5的字符位置。<br><br>
<div align="center"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix12.gif" height="259" width="367"><br></font></strong><br><strong><font color="blue">Figure 12 After the insertion of the suffix babbaabbabb#<br></font></strong><big><br></big></div>
<big><strong><font color="#990000">后面几个后缀的插入过程跟前面几个完全一样，就不翻译了，感兴趣的可以看看原文，我只把图贴在这儿，如果上面的部分看明白了，那么只看下面的几张图也能明白是怎么插入的。</font></strong></big><br><br></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix13.gif" height="259" width="367"> </font></strong><br><strong><font color="blue">Figure 13 After the insertion of the suffix abbaabbabb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix14.gif" height="259" width="393"> </font></strong><br><strong><font color="blue">Figure 14 After the insertion of the suffix bbaabbabb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix15.gif" height="313" width="393"> </font></strong><br><strong><font color="blue">Figure 15 After the insertion of the suffix baabbabb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix16.gif" height="313" width="393"> </font></strong><br><strong><font color="blue">Figure 16 After the insertion of the suffix aabbabb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix17.gif" height="367" width="393"> </font></strong><br><strong><font color="blue">Figure 17 After the insertion of the suffix abbabb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix18.gif" height="367" width="420"> </font></strong><br><strong><font color="blue">Figure 18 After the insertion of the suffix bbabb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix19.gif" height="367" width="456"> </font></strong><br><strong><font color="blue">Figure 19 After the insertion of the suffix babb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix20.gif"> </font></strong><br><strong><font color="blue">Figure 20 After the insertion of the suffix abb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font>
<div align="center"><font face="sans-serif"><strong><font color="blue"><img alt="" src="http://www.cppblog.com/images/cppblog_com/lucency/suffix21.gif" height="421" width="432"> </font></strong><br><strong><font color="blue">Figure 21 After the insertion of the suffix bb# </font></strong><br></font></div>
<font face="sans-serif"><n，lastbranchindex(i,i)><br></n，lastbranchindex(i,i)></font><center> <font face="sans-serif"><strong><font color="blue"> </font></strong></font><font face="sans-serif"><strong><font color="blue"><font face="sans-serif"><strong></strong></font></font></strong></font><font face="sans-serif"><strong><font color="blue"><font face="sans-serif"><strong><br></strong></font></font></strong></font>
<div style="text-align: left;"><font face="sans-serif"><strong><font color="#000099"><big>复杂度分析</big></font></strong><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>用r表示字符串S的字符集的大小，n表示S的长度（也就是后缀的数目）。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>为了插入suffix(i)，我们</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>(a)沿着活动节点的后缀指针（除非活动节点是根结点）。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>(b)在已创建的后缀树中向下移动，直到经过了minDistance个字符。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>(c)然后依次比较后缀和边的字符，直到确定了lastBranchIndex(i,i)为止。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>(d)最后插入新的信息节点和可能的分支节点。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>(a)部分消耗的总的时间是O(n)（一共有n此插入）</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>(b)
部分中，在后缀树中往下移动时，不需要做比较。每次移动到下级分支节点需要O(1)时间。另外，每次移动都会使minDistance减少1.由于开始时
minDistance为0,并且永远不会小于0,(b)消耗的时间是O(n + n次插入操作中minDistance增加的总数). </n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>(c)
部分中，确定lastBranchIndex(i,i) 跟 i + activeLength +
minDistance是否相等需要的时间是O(1)。这只有在minDistance = 0或者位于suffix(i)的activeLength
+ minDistance + 1位置的字符x跟活动节点的合适的边的minDistance +
1位置的字符不同的时候才满足。当lastBranchIndex(i,i) != i + activeLength +
minDistance时，lastBranchIndex(i,i) &gt; i + activeLength +
minDistance，lastBranchIndex(i,i)的值通过对后缀字符和边的字符之间做一系列的比较来确定。每进行一次这种比
较，minDistance加1.本算法中，只有在这种情景下，minDistance才会增加。由于minDistance的每次递增都是S的新的位置
（也就是此位置开始的字符还未比较过的位置）的字符和边的字符相等的情形的结果，因此在n次插入中，minDistance增加的总数是O(n)。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>每次插入时，(d)消耗的时间是O(r)，因为我们需要初始化要创建的分支节点的O(r)个字段。因此步骤(d)消耗的总的时间是O(nr)。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>因此，创建后缀树消耗的总的时间是O(nr)。如果假定字符集的大小r是常数，算法的复杂度就是O(n)。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)>只有在字符集的大小r很小的情况下，才推荐每个分支节点有r个指向子节点的字段。当字符集很大的时候（可能会跟n一样大，这时上述算法的复杂度是O(n^2)），<a href="http://www.cise.ufl.edu/%7Esahni/dsaaj/enrich/c16/tries.htm">使用哈希表</a>能够得到O(n)复杂度的算法。空间复杂度有O(nr)变为O(n)。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)><a href="http://www.cs.rutgers.edu/%7Efarach">这里</a>有一个分治算法实现的后缀树，时间和空间复杂度都是O(n)（即使字符集的大小是O(n)）。</n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font><br><font face="sans-serif"><n，lastbranchindex(i,i)></n，lastbranchindex(i,i)></font></div>
<font face="sans-serif"><strong><big><big><font color="blue">References and Selected Readings</font></big></big></strong></font><br><font face="sans-serif"><strong></strong></font><br>
<div style="text-align: left;"><font face="sans-serif"><strong></strong></font><br><font face="sans-serif"><strong> </strong></font></div>
<font face="sans-serif"><strong><a name="genomics"></a>
</strong></font>
<ol style="text-align: left;">
    <font face="sans-serif"><strong>    </strong>
    <li><strong> <font face="sans-serif"><strong><a href="http://www.nhgri.nih.gov/HGP/">NIH's Web site for the human genome project</a> </strong></font></strong></li>
    <strong>    </strong>
    <li><strong> <font face="sans-serif"><strong><a href="http://www.ornl.gov/TechResources/Human_Genome/home.html">  Department of Energy's Web site for the human genomics project</a> </strong></font></strong></li>
    <strong>    </strong>
    <li><strong> <font face="sans-serif"><strong><a href="http://merlin.mbcr.bcm.tmc.edu:8001/bcd/Curric/welcome.html">  Biocomputing Hypertext Coursebook</a>. </strong></font></strong></li>
    </font></ol>
    <div style="text-align: left;"><font face="sans-serif"><strong> <font face="sans-serif"><strong></strong></font><br><font face="sans-serif"><strong></strong></font><br><font face="sans-serif"><strong>Linear
    time algorithms to search for a single pattern in a given string can be
    found in most algorithm's texts. See, for example, the texts: </strong></font></strong></font></div>
    <ol style="text-align: left;">
        <font face="sans-serif"><strong>    </strong>
        <li><strong> <font face="sans-serif"><strong><em>Computer Algorithms</em>, by E. Horowitz, S. Sahni, and S. Rajasekeran, Computer Science Press, New York, 1998. </strong></font></strong></li>
        <strong>    </strong>
        <li><strong> <font face="sans-serif"><strong><em>Introduction to Algorithms</em>, by T. Cormen, C. Leiserson, and R. Rivest, McGraw-Hill Book Company, New York, 1992. </strong></font></strong></li>
        </font></ol>
        <div style="text-align: left;"><font face="sans-serif"><strong> <font face="sans-serif"><strong></strong></font><br><font face="sans-serif"><strong></strong></font><br><font face="sans-serif"><strong>For more on suffix tree construction, see the papers: </strong></font></strong></font></div>
        <ol style="text-align: left;">
            <font face="sans-serif"><strong>    </strong>
            <li><strong> <font face="sans-serif"><strong>``A space economical suffix tree construction algorithm,'' by E. McCreight, <em>Journal of the ACM</em>, 23, 2, 1976, 262-272. </strong></font></strong></li>
            <strong>    </strong>
            <li><strong> <font face="sans-serif"><strong>``On-line construction of suffix trees,'' by E. Ukkonen, <em>Algorithmica</em>, 14,  3, 1995, 249-260. </strong></font></strong></li>
            <strong>    </strong>
            <li><strong> <font face="sans-serif"><strong>Fast string searching with suffix trees,'' by M. Nelson, <em>Dr. Dobb's Journal</em>, August 1996. </strong></font></strong></li>
            <strong>    </strong>
            <li><strong> <font face="sans-serif"><strong><a href="http://www.cs.rutgers.edu/%7Efarach">  Optimal suffix tree construction with large alphabets</a>, by M. Farach, <em>IEEE Symposium on the Foundations of Computer Science</em>, 1997. </strong></font></strong></li>
            </font></ol>
            <div style="text-align: left;"><font face="sans-serif"><strong> <font face="sans-serif"><strong></strong></font><br><font face="sans-serif"><strong></strong></font><br><font face="sans-serif"><strong>You can download C++ code to construct a suffix tree from <a href="http://www.ddj.com/ftp/1996/1996.08/suffix.zip">  http://www.ddj.com/ftp/1996/1996.08/suffix.zip</a>. This code, developed by M. Nelson, is described in paper 3 above. </strong></font><font face="sans-serif"><strong><font color="blue"><font face="sans-serif"><strong></strong></font></font></strong></font><br><font face="sans-serif"><strong></strong></font></strong></font></div>
            </center></div>
            </div>
            </div>
            <font face="sans-serif"><strong><font face="sans-serif"><strong><font color="blue"> </font></strong></font> </strong></font><img src ="http://www.cppblog.com/lucency/aggbug/55944.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-07-12 10:44 <a href="http://www.cppblog.com/lucency/archive/2008/07/12/55944.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>C++编码风格指南</title><link>http://www.cppblog.com/lucency/archive/2008/05/23/50829.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Fri, 23 May 2008 01:09:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/05/23/50829.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/50829.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/05/23/50829.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/50829.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/50829.html</trackback:ping><description><![CDATA[<div align="center">C++编码风格指南<br /></div><br /><a href="http://geosoft.no/development/cppstyle.html">C++ Programming Style Guidelines</a><br /><blockquote></blockquote><img src ="http://www.cppblog.com/lucency/aggbug/50829.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-05-23 09:09 <a href="http://www.cppblog.com/lucency/archive/2008/05/23/50829.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>ecb symboldef VS. si context window</title><link>http://www.cppblog.com/lucency/archive/2008/04/21/47726.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Mon, 21 Apr 2008 05:02:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/04/21/47726.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/47726.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/04/21/47726.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/47726.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/47726.html</trackback:ping><description><![CDATA[<title>ZoundryDocument</title>
<p>一直觉得source insight中显示变量和函数定义的context window很好,昨天突然发现原来ecb(<a href="http://ecb.sourceforge.net/" target="_blank">Emacs Code
Browser</a>)中也有个类似的东西.当layout换成left_symboldef后,左下窗口就是了.啥也不说了,贴个图吧.</p>
<p><img style="width: 564px; height: 422px;" src="http://www.cppblog.com/images/cppblog_com/lucency/ecb_symbol.JPG" border="0"><br>
</p>
<p>这个是我根据原先的layout
left_symboldef改的.可以看到左边那一栏,上面是函数啥的列表,下面就是符号定义窗口.有两点不爽的是符号定义窗口没法单独放在下面,主要是放在左边的话,函数原型比较长的就没法完整显示;二是不能像si那样双击跳转.不过也不错了,跳转用cscope也容易.
<br><br>ps:我的ecb函数列表中没法显示参数类型,哪位如果知道麻烦说一下哈,谢了!</p><img src ="http://www.cppblog.com/lucency/aggbug/47726.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-04-21 13:02 <a href="http://www.cppblog.com/lucency/archive/2008/04/21/47726.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>关于流和缓冲区的理解</title><link>http://www.cppblog.com/lucency/archive/2008/04/07/46419.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Mon, 07 Apr 2008 04:48:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/04/07/46419.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/46419.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/04/07/46419.html#Feedback</comments><slash:comments>4</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/46419.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/46419.html</trackback:ping><description><![CDATA[<title></title>
<p>0. 序曲</p>
<p>写这篇短文的起因是,前两天想去天大的acm在线系统找几道题做做。为什么呢?因为本人天大毕业,这个天大呢可是中国最早的大学,原名北洋大学堂,这可绝对是货真价实的第一所大学。给大家推荐推荐啊,学风那是相当的好。</p>
<p>扯多了,还是回到本来的话题上。上了acm系统之后,就先看了1001。那道题的意思是输入一些正整数(以EOF结束),把对应的字符输出。这个简单,程序很快就出来了:</p>
<p><br></p>
<blockquote dir="ltr" style="margin-right: 0px;">
<p>&#160;</p>
<div style="border: 1px solid #cccccc; padding: 4px 5px 4px 4px; background-color: #eeeeee; font-size: 13px; width: 98%;"><!--<br><br>Code highlighting produced by Actipro CodeHighlighter (freeware)<br>http://www.CodeHighlighter.com/<br><br>--><span style="color: #000000;">#include&nbsp;</span><span style="color: #000000;">&lt;</span><span style="color: #000000;">stdio.h</span><span style="color: #000000;">&gt;</span><span style="color: #000000;"><br></span><span style="color: #0000ff;">int</span><span style="color: #000000;">&nbsp;main()<br>{<br></span><span style="color: #0000ff;">int</span><span style="color: #000000;">&nbsp;c;<br></span><span style="color: #0000ff;">while</span><span style="color: #000000;">(scanf(</span><span style="color: #000000;">"</span><span style="color: #000000;">%d</span><span style="color: #000000;">"</span><span style="color: #000000;">,&nbsp;</span><span style="color: #000000;">&amp;</span><span style="color: #000000;">c)&nbsp;</span><span style="color: #000000;">!=</span><span style="color: #000000;">&nbsp;EOF)<br>{<br>putchar(c);<br>}<br></span><span style="color: #0000ff;">return</span><span style="color: #000000;">&nbsp;</span><span style="color: #000000;">0</span><span style="color: #000000;">;<br>}</span></div>
<p>&#160;</p>
</blockquote>
<p><br>程序运行,输入103 102 105 107&lt;enter&gt;</p>
<p>输出gfik。</p>
<p>当时运行完之后马上想,为什么不是输入一个数字马上输出一个字符呢,因为看程序确实是这样的逻辑,只要不是EOF,就会输出。又一想,对了,是缓冲的问题。想起来APUE里边说得stdin应该是行缓冲的,另外,可以用setbuf,setvbuf设定流的缓冲。于是想将stdin设成无缓冲的。于是程序变成这样:</p>
<p><br></p>
<blockquote dir="ltr" style="margin-right: 0px;">
<p dir="ltr" style="margin-right: 0px;">
<div style="border: 1px solid #cccccc; padding: 4px 5px 4px 4px; background-color: #eeeeee; font-size: 13px; width: 98%;"><!--<br><br>Code highlighting produced by Actipro CodeHighlighter (freeware)<br>http://www.CodeHighlighter.com/<br><br>--><span style="color: #000000;">#include&nbsp;</span><span style="color: #000000;">&lt;</span><span style="color: #000000;">stdio.h</span><span style="color: #000000;">&gt;</span><span style="color: #000000;"><br></span><span style="color: #0000ff;">int</span><span style="color: #000000;">&nbsp;main()<br>{<br></span><span style="color: #0000ff;">int</span><span style="color: #000000;">&nbsp;c;<br>setbuf(stdin,&nbsp;NULL);<br></span><span style="color: #0000ff;">while</span><span style="color: #000000;">(scanf(</span><span style="color: #000000;">"</span><span style="color: #000000;">%d</span><span style="color: #000000;">"</span><span style="color: #000000;">,&nbsp;</span><span style="color: #000000;">&amp;</span><span style="color: #000000;">c)&nbsp;</span><span style="color: #000000;">!=</span><span style="color: #000000;">&nbsp;EOF)<br>{<br>putchar(c);<br>}<br></span><span style="color: #0000ff;">return</span><span style="color: #000000;">&nbsp;</span><span style="color: #000000;">0</span><span style="color: #000000;">;<br>}</span></div>
</p>
</blockquote>
<p dir="ltr" style="margin-right: 0px;"><br>可是编译运行,还是老样子,没有变化。想了想,没想出是啥原因,于是开始google和APUE。终于算是明白了些,整理在这儿。</p>
<br>
<p dir="ltr" style="margin-right: 0px;">声明：</p>
<blockquote dir="ltr" style="margin-right: 0px;">
<p dir="ltr" style="margin-right: 0px;">本文很大部分内容来自APUE－－UNIX环境高级编程。</p>
</blockquote>
<p>1. 缓冲类型。</p>
<p>标准库提供缓冲是为了减少对read和write的调用。提供的缓冲有三种类型(整理自APUE):</p>
<ul>
    <li>全缓冲。 </li>
</ul>
<blockquote dir="ltr" style="margin-right: 0px;">
<p>在这种情况下,实际的I/O操作只有在缓冲区被填满了之后才会进行。对驻留在磁盘上的文件的操作一般是有标准I/O库提供全缓冲。缓冲区一般是在第一次对流进行I/O操作时,由标准I/O函数调用malloc函数分配得到的。</p>
<p>术语flush描述了标准I/O缓冲的写操作。缓冲区可以由标准I/O函数自动flush(例如缓冲区满的时候);或者我们对流调用fflush函数。</p>
</blockquote>
<ul>
    <li>
    <div>行缓冲</div>
    </li>
</ul>
<blockquote dir="ltr" style="margin-right: 0px;">
<p>在这种情况下,只有在输入/输出中遇到换行符的时候,才会执行实际的I/O操作。这允许我们一次写一个字符,但是只有在写完一行之后才做I/O操作。一般的,涉及到终端的流--例如标注输入(stdin)和标准输出(stdout)--是行缓冲的。</p>
</blockquote>
<ul>
    <li>
    <div>无缓冲</div>
    </li>
</ul>
<blockquote dir="ltr" style="margin-right: 0px;">
<p>标准I/O库不缓存字符。<span style="color: #ff0000;">需要注意的是,标准库不缓存并不意味着操作系统或者设备驱动不缓存。<br></span></p>
</blockquote>
<p dir="ltr"><span style="color: #000000;">ISO C要求:</span></p>
<ul dir="ltr">
    <li>
    <div><span style="color: #000000;">当且仅当不涉及交互设备时,标准输入和标准输出是全缓存的。</span></div>
    </li>
    <li>
    <div><span style="color: #000000;">标准错误绝对不是全缓存的。</span></div>
    </li>
</ul>
<p><span style="color: #000000;">但是,这并没有告诉我们当标准输入/输出在涉及交互设备时,它们是无缓存的还是行缓存的;也没有告诉我们标准错误应该是行缓存的还是无缓存的。不过,大多数实现默认的缓存类型是这样的:</span></p>
<ul>
    <li>
    <div><span style="color: #000000;">标准错误总是无缓存的。</span></div>
    </li>
    <li>
    <div><span style="color: #000000;">对于所有的其他流来说,如果它们涉及到交互设备,那么就是行缓存的;否则是全缓存的。</span></div>
    </li>
</ul>
<br>
<p><span style="color: #000000;">2. 改变默认缓存类型</span></p>
<p><span style="color: #000000;">可以通过下面的函数改变缓存类型(摘自APUE):</span></p>
<blockquote dir="ltr" style="margin-right: 0px;">
<p dir="ltr" style="margin-right: 0px; text-align: justify;"><span style="color: #000000;">void setbuf(FILE *restrict <span class="docEmphItalicAlt">fp</span>, char *restrict <span class="docEmphItalicAlt">buf</span>);<br>int setvbuf(FILE *restrict <span class="docEmphItalicAlt">fp</span>, char *restrict <span class="docEmphItalicAlt">buf</span>, int <span class="docEmphItalicAlt">mode</span>,
<span class="docEmphItalicAlt">size_t size</span>);<br></span></p>
</blockquote>
<p dir="ltr" style="margin-right: 0px;"><span style="color: #000000;">这些函数必须在流打开之后、但是未对流做任何操作之前被调用(因为每个函数都需要一个有效的文件指针作为第一个参数)。</span></p>
<p dir="ltr" style="margin-right: 0px;"><span style="color: #000000;">利用setbuf，可以打开或者关闭缓存。为了打开缓存，buf参数必须一个大小为BUFSIZ的缓存，BUFSIZ是定义在stdio。h中的常量。&amp;amp;lt;&amp;amp;lt;ISO/IEC
9899&amp;amp;gt;&amp;amp;gt;要求：BUFSIZ至少为256。如果要关闭缓存，可以将buf设成NULL。</span></p>
<p dir="ltr" style="margin-right: 0px;"><span style="color: #000000;">利用setvbuf，我们可以设定缓存类型。这是通过mode参数指定的。</span></p>
<p dir="ltr" style="margin-right: 0px;"><span style="color: #000000;">关于这两个函数，可以看下表（摘自APUE）：</span></p>
<br>
<table class="allBorders" border="1" cellpadding="4" cellspacing="0" rules="all">
    <thead>
        <tr>
            <th class="thead" scope="col" align="middle" valign="top">
            <p class="docText"><span class="docEmphRoman">Function</span></p>
            </th>
            <th class="thead" scope="col" align="middle" valign="top">
            <p class="docText"><span class="docEmphRoman"><span class="docEmphasis">mode</span></span></p>
            </th>
            <th class="thead" scope="col" align="middle" valign="top">
            <p class="docText"><span class="docEmphRoman"><span class="docEmphasis">buf</span></span></p>
            </th>
            <th class="thead" scope="col" align="middle" valign="top">
            <p class="docText"><span class="docEmphRoman">Buffer and length</span></p>
            </th>
            <th class="thead" scope="col" align="middle" valign="top">
            <p class="docText"><span class="docEmphRoman">Type of
            buffering</span></p>
            </th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td class="docTableCell" rowspan="2" align="left" valign="center">
            <p class="docText"><tt>setbuf</tt></p>
            </td>
            <td class="docTableCell" rowspan="2" align="left" valign="center">
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">non-null</p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">user <span class="docEmphasis">buf</span> of length
            <tt>BUFSIZ</tt></p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">fully buffered or line buffered</p>
            </td>
        </tr>
        <tr>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText"><tt>NULL</tt></p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">(no buffer)</p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">unbuffered</p>
            </td>
        </tr>
        <tr>
            <td class="docTableCell" rowspan="5" align="left" valign="center">
            <p class="docText"><tt>setvbuf</tt></p>
            </td>
            <td class="docTableCell" rowspan="2" align="left" valign="center">
            <p class="docText"><tt>_IOLBF</tt></p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">non-null</p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">user <span class="docEmphasis">buf</span> of length <span class="docEmphasis">size</span></p>
            </td>
            <td class="docTableCell" rowspan="2" align="left" valign="center">
            <p class="docText">fully buffered</p>
            </td>
        </tr>
        <tr>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText"><tt>NULL</tt></p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">system buffer of appropriate length</p>
            </td>
        </tr>
        <tr>
            <td class="docTableCell" rowspan="2" align="left" valign="center">
            <p class="docText"><tt>_IOFBF</tt></p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">non-null</p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">user <span class="docEmphasis">buf</span> of length <span class="docEmphasis">size</span></p>
            </td>
            <td class="docTableCell" rowspan="2" align="left" valign="center">
            <p class="docText">line buffered</p>
            </td>
        </tr>
        <tr>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText"><tt>NULL</tt></p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">system buffer of appropriate length</p>
            </td>
        </tr>
        <tr>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText"><tt>_IONBF</tt></p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">(ignored)</p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">(no buffer)</p>
            </td>
            <td class="docTableCell" align="left" valign="top">
            <p class="docText">unbuffered</p>
            </td>
        </tr>
    </tbody>
</table>
<p><span style="color: #000000;">需要注意的是：如果在函数内为流分配了自动变量作为缓存，那么在退出之前需要将流关闭。因此最好让系统自己分配缓存，这些缓存在流关闭的时候会自动被释放。</span></p>
<br>
<p><span style="color: #000000;">3.如果清理输入缓存</span></p>
<p><span style="color: #000000;">关于这点可以参看comp.lang.c
FAQ的Question12.26b:</span></p>
<blockquote dir="ltr" style="margin-right: 0px;">
<p style="font-family: courier new;"><span style="color: #000000;"><span style="font-size: 0.75em; color: #000000;">Q: If fflush won't work, what can I
use to flush input?<br><br>A: It depends on what you're trying to do. If you're
trying to get rid of an unread newline or other unexpected input after calling
scanf (see questions 12.18a-12.19), you really need to rewrite or replace the
call to scanf (see question 12.20). Alternatively, you can consume the rest of a
partially-read line with a simple code fragment like<br><br>while((c =
getchar()) != '\n' &amp;amp;&amp;amp; c != EOF)<br>/* discard */ ;<br><br>(You may also
be able to use the curses flushinp function.)<br><br>There is no standard way to
discard unread characters from a stdio input stream. Some vendors do implement
fflush so that fflush(stdin) discards unread characters, although portable
programs cannot depend on this. (Some versions of the stdio library implement
fpurge or fabort calls which do the same thing, but these aren't standard,
either.) Note, too, that flushing stdio input buffers is not necessarily
sufficient: unread characters can also
accumulate in other, OS-level input buffers. If you're trying to actively
discard input (perhaps in anticipation of issuing an unexpected prompt to
confirm a destructive action, for which an accidentally-typed ``y'' could be
disastrous), you'll have to use a system-specific technique to detect the
presence of typed-ahead input; see questions 19.1 and 19.2. Keep in mind that
users can become frustrated if you discard input that happened to be
typed too quickly.<br><br>References: ISO Sec. 7.9.5.2<br>H&amp;amp;S Sec.
15.2</span></span></p>
<p><span style="color: #000000;">4. 几点需要注意的地方</span></p>
</blockquote>
<ul>
    <li><span style="color: #000000;">对输入流进行fflush操作是无定义的。</span>
    </li>
    <li><span style="color: #000000;">无缓存并不意味着一个个的那样处理输入，而是说当操作系统返回它们时，对于标准库函数来说它们是立即可用的。因为还可能有操作系统级甚至是硬件级的缓存，这些并不是setbuf可以控制的。</span>
    </li>
    <li><span style="color: #000000;">另外可以参考<a href="http://bbs.chinaunix.net/viewthread.php?tid=588099&amp;amp;extra=page%3D2%26amp%3Bfilter%3Ddigest">这里</a>（我就是最先从这里开始看的）。还有<a href="http://groups.google.com/group/comp.lang.c/browse_thread/thread/2249847ef34a3849/1a21051c26299b4c?hl=en">这里</a>。我从后面那个链接摘录一些重要的下来：</span>
    </li>
</ul>
<blockquote dir="ltr" style="margin-right: 0px; font-family: courier new;">
<p>setbuf() has to do with the
delivery of bytes between the<br>C library FILE* management layer and the OS I/O
layer.<br></p>
<p>Calls to fread(), fgets(),
fgetc(), and getchar() work within<br>whatever FILE* buffered data is available,
and when that data<br>is exhausted, the calls request that the FILE* buffer be
refilled<br>by the system I/O layer.<br></p>
<p>When full buffering is turned
on, that refill operation results in the<br>FILE* layer requesting that the
operating system hand it a full<br>buffer's worth of data; when buffering is
turned off, that<br>refill operation results in the FILE* layer requesting that
the<br>operating system return a single character.</p>
<p>...setting an input stream to
be unbuffered<br>does <span style="color: #ff0000;">NOT</span> tell the operating
system to tell the device driver<br>to go into any kind of "raw"
single-character mode. There are<br>system-specific calls such as ioctl() and
tcsetterm() that<br>control what the device driver will
do.</p>
</blockquote>
<p><span style="color: #000000;"></span></p>
<p><br><br></p>
<br>
<p><br></p><img src ="http://www.cppblog.com/lucency/aggbug/46419.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-04-07 12:48 <a href="http://www.cppblog.com/lucency/archive/2008/04/07/46419.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>makefile笔记</title><link>http://www.cppblog.com/lucency/archive/2008/02/24/43160.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Sun, 24 Feb 2008 03:23:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/02/24/43160.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/43160.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/02/24/43160.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/43160.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/43160.html</trackback:ping><description><![CDATA[&nbsp;&nbsp;&nbsp; 注：这里的makefile指的是gnu makefile，可能跟其他的makefile略有不同。若有不同，我尽量提及。而且这也不算是一篇教程，只是我在用make的时候记得一些笔记。推荐看&lt;<Managing projects="" with="" gnu="" make="">&gt;。另外网上有一篇《跟我一起写makefile》也很好。<br /><br />&nbsp;&nbsp;&nbsp; makefile规则分为三部分：目标(target)、条件(prerequisite)、命令(commands)。<br />&nbsp;&nbsp;&nbsp; target:prereq1...prereqn<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;  commans<br /><br />1.自动变量<br /><br />&nbsp;&nbsp;&nbsp; $@：代表目标文件名<br />&nbsp;&nbsp;&nbsp; $%：The filename element of an <a name="make3-CHP-2-ITERM-910"></a>archive member  specification.<br />&nbsp;&nbsp;&nbsp; $&lt;：条件列表中的第一个条件的文件名<br />&nbsp;&nbsp;&nbsp; $?：条件列表中所有比目标新的那些条件的文件名，以空格分割<br />&nbsp;&nbsp;&nbsp; $^：条件列表中所有条件的文件名，以空格分割。如果列表中有重复的条件，则会被删掉。<br />&nbsp;&nbsp;&nbsp; $+：跟$^类似，区别在不会去掉重复的条件。<br />&nbsp;&nbsp;&nbsp; $*：目标文件名的词干部分(去掉扩展名剩下的部分)<br /><br />&nbsp;&nbsp;&nbsp; 自动变量只能用在规则的命令部分，因为这些变量是make匹配到规则的目标和条件后才设置值的。<br />&nbsp;&nbsp;&nbsp; 举个例子说明一下。假设某个工程有三个文件：cal.cpp，cal.h，test.cpp(下面再有说明时也以此为例)。makefile如下：<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; OBJS=test.o cal.o cal.o<br /><br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; TARGET=cal.exe<br /><br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; all:$(TARGET)<br /><br />&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; $(TARGET):$(OBJS)<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; @echo $@<br />&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; @echo $&lt;<br />&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; @echo $^<br />&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; @echo $?<br />&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; @echo $+<br />&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; @echo $%<br />&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; @echo $*<br />&nbsp;&nbsp;&nbsp; 输出为：<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; cal.exe<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; test.o<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; test.o cal.o<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; test.o cal.o<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; test.o cal.o cal.o<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; ECHO is off.<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; ECHO is off.<br />&nbsp;&nbsp;&nbsp; <b>至于最后两个为什么会这样输出我还不太清楚，有清楚地麻烦告诉我一下这两个怎么用。先谢谢了</b>。<br /><br />2.模式规则<br />&nbsp;&nbsp;&nbsp; 模式规则也是规则，也要满足make的规则形式，分为目标、条件、命令三个部分。只是目标、条件中的文件名的词干部分用%代替了，这个%跟shell中的*类似，代表任意长度的字符串。还以上面说得工程为例，makefile如下：<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; CPPFLAGS= -g<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; CC=g++<br /><br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; test:cal.o test.o<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; cal.o:cal.h<br />&nbsp;&nbsp;&nbsp; make的时候，输出如下内容：<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; g++&nbsp; -g&nbsp; -c -o test.o test.cpp<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; g++&nbsp; -g&nbsp; -c -o cal.o cal.cpp<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; g++&nbsp;&nbsp; test.o cal.o&nbsp;&nbsp; -o test<br />&nbsp;&nbsp;&nbsp; 这个makefile之所以能够正确被处理，是因为make内建了一些规则。例如：<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; %.o: %.c<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $(COMPILE.c) $(OUTPUT_OPTION) $&lt;<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; %.o: %.cpp<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $(COMPILE.cpp) $(OUTPUT_OPTION) $&lt;<br />&nbsp;&nbsp;&nbsp; 以及<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; %: %.o         <br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $(LINK.o) $^ $(LOADLIBES) $(LDLIBS) -o $@<br />&nbsp;&nbsp;&nbsp; 这些规则里面的$变量都是make的标准变量(还有上面的CPPFLAGS,CC也是。另外还有一些别的)，这些标准变量有的有默认值(例如CC的默认值是cc)，有的没有。make在处理makefile文件时，如果没有显式的规则，那么就会查找是否有隐式的可用规则，如果找到就会利用隐式规则来生成目标。<br /><br />&nbsp;&nbsp;&nbsp; 2.1静态模式规则<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; 静态模式规则指的是类似下面的规则：<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $(OBJECTS): %.o: %c<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $(CC) -c $(CFLAGS) $&lt; -o $@<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;  这跟上面的模式规则类似，不同在于将规则的适用范围限制在了$(OBJECTS)。也就是只针对这些目标来应用规则。<br /><br />&nbsp;&nbsp;&nbsp; 2.2后缀规则<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;  后缀规则是指用一个或者两个后缀连接起来作为目标，同时省略掉条件部分。如下：<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; .c.o:<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp; $(COMPILE.c) $(OUTPUT_OPTION) $&lt;<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;  容易混淆的地方是条件后缀在前，目标后缀在后。<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;  这跟上面的规则：<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; %.o: %.c<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $(COMPILE.c) $(OUTPUT_OPTION) $&lt;<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;  功能是一样的，只是为了兼容一些老的make系统。<br />&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;  需要注意的是，这里用到的后缀必须在已知后缀列表里面。有个专用的目标(target)——.SUFFIXES——用来设定后缀列表。例如：.SUFFIXES：.pdf .o .c 。而.SUFFIXES:（也就是后面列表为空）用来清空后缀列表。<br /><br /><br />3.自动依赖生成<br />&nbsp;&nbsp;&nbsp; 还没发现这个在实际应用中有多方便，有兴趣的可以看看我开始推荐的两个文档。<br /></Managing><img src ="http://www.cppblog.com/lucency/aggbug/43160.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-02-24 11:23 <a href="http://www.cppblog.com/lucency/archive/2008/02/24/43160.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>终于体会到emacs比vim方便的地方！</title><link>http://www.cppblog.com/lucency/archive/2008/02/16/42818.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Sat, 16 Feb 2008 15:48:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/02/16/42818.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/42818.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/02/16/42818.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/42818.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/42818.html</trackback:ping><description><![CDATA[<p dir="ltr" style="margin-right: 0px; text-align: justify;">&nbsp;&nbsp;&nbsp; 刚刚试用了一下在emacs里用gdb调试程序，不是一般的方便啊，呵呵。有直观的界面，而且还有console对gdb方便的控制，使用了好几天emacs了，觉得这是少有的比vim方便的地方。</p><br /><p>&nbsp;&nbsp;&nbsp; 当然，单纯用来编辑文件的话还是vim方便一些，毕竟vim区分模式，有些操作可以用很少的按键快速的完成。</p><br /><p>&nbsp;&nbsp;&nbsp; 不知道emacs的宏录制功能如何。感觉vim里面的宏真的是太好用了，弄得我很是舍不得vim。要是有个编辑器能集合vim的高效快捷跟emacs的强大扩展能力就好了。</p><img src ="http://www.cppblog.com/lucency/aggbug/42818.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-02-16 23:48 <a href="http://www.cppblog.com/lucency/archive/2008/02/16/42818.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>Blog api</title><link>http://www.cppblog.com/lucency/archive/2008/02/16/42817.html</link><dc:creator>季阳</dc:creator><author>季阳</author><pubDate>Sat, 16 Feb 2008 15:39:00 GMT</pubDate><guid>http://www.cppblog.com/lucency/archive/2008/02/16/42817.html</guid><wfw:comment>http://www.cppblog.com/lucency/comments/42817.html</wfw:comment><comments>http://www.cppblog.com/lucency/archive/2008/02/16/42817.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/lucency/comments/commentRss/42817.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/lucency/services/trackbacks/42817.html</trackback:ping><description><![CDATA[<p>cpp blog api</p><br /><p><a href="http://www.cppblog.com/lucency/services/metaweblog.aspx">http://www.cppblog.com/lucency/services/metaweblog.aspx</a></p><br /><br /><p>google blog api</p><br /><p><a href="http://www.blogger.com/feeds/default/blogs">http://www.blogger.com:80/feeds/default/blogs</a></p><img src ="http://www.cppblog.com/lucency/aggbug/42817.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/lucency/" target="_blank">季阳</a> 2008-02-16 23:39 <a href="http://www.cppblog.com/lucency/archive/2008/02/16/42817.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item></channel></rss>