1. 简介
clrscode3e是《算法导论(第三版)》使用的伪代码的宏包,clrs其实表示的是Cormen、Leiserson、Rivest和Stein。
它有个更老的版本clrscode,这个宏包CTEX自带。《算法导论》中的伪代码风格与clrscode3e的风格完全一致,要比lstlistings更适合写伪代码。
源码及手册链接http://www.cs.dartmouth.edu/~thc/clrscode/
2. 安装
clrscode3e并没有预装在CTEX中,因此需要手动加入DB中。其实很简单。
首先,下载clrscode3e.sty,将其放置在XXX\CTEX\MiKTeX\tex\latex\clrscode3e文件夹下,注意这里可能需要创建clrscode3e文件夹。
这里,可以将clrscode3e.pdf放置在XXX\CTEX\MiKTeX\source\latex\clrscode3e文件夹方便检索。
然后,打开WinEdt,依次点击Tex $\rightarrow$ MikTex $\rightarrow$ MikTex Options,将它打开后,单机FNDB,会更新宏包的数据库。
等待完成即可,如下图所示:
3. 基本类型
CLRS3e风格的伪代码包含四种基本类型:
(1)\id:变量;
(2)\proc:函数;
(3)\const:常量,如nil、true等;
(4)\func:可以将其理解成库函数,如sin、sqrt等。
这四种类型可以在使用模式下使用,也可以在非公式编辑模式下使用。如下图:
4. 基本属性
CLRS3e将对象的属性主要可以分成三类:
- $\textit{i-string}$,主要指使用\id修饰的字符串,并且不包含希腊字母;
- $\textit{x-string}$,主要指使用\id修饰的字符串,包含希腊字母或者公式下表;
- 不属于上述两种,有时会把$i-string$用作$x-string$。
\attrib命令是对象名是$x-string$,属性名是$i-string$的常用命令。如
此外,\attribxi、\attribxx、\attribii、\attribix用来表示这两个参数是$i-string$或$x-string$的全排列组合。(第一个字符表示对象的类型,第二字符表示属性的类型)
使用的时候,要注意的是$i-string$可以当做$x-string$用,但是一般来说$x-string$不会用作$i-string$。如
\attribb命令包含三个参数,用来表示级联属性,如
此外,\attribe用来表示边$(u,v)$的属性信息,\attribe表示属性是$i-string$,\attribex表示属性是$x-string$,如:
5. 杂项
下面三个命令仅适用于公式编辑模式
- \twodots 表示".."(\cdtos等表示$\cdots$)
- \gets 表示赋值运算符
- \isequal 表示相等运算发,3e中等价于$==$但是长度略小于
6. codebox环境
codebox是编写伪代码的主要环境:
- 使用\Procname指定函数名
- 使用\li表示有编号的新行
- 使用\zi表示不使用编号的行
\begin{codebox}
\Procname{$\proc{Insertion-Sort}(A)$}
\li \For $j \gets 2$ \To $\attrib{A}{length}$
\li \Do
$\id{key} \gets A[j]$
\li \Comment Insert $A[j]$ into the sorted sequence
\li $i \gets j-1$
\li \While $i > 0$ and $A[i] > \id{key}$
\li \Do
$A[i+1] \gets A[i]$
\li $i \gets i-1$
\End
\li $A[i+1] \gets \id{key}$
\End
\end{codebox}
生成的伪代码如下图所示:
codebox环境定义了一些关键字,具体实现可以参考源代码,可以定制自己喜欢的关键字。
- Loop相关:\For, \To, \By, \Downto, \Do, \While, \Repeat, \Until
- Selection相关:\If, \Then, \Else, \ElseIf, \ElseNoIf
- Jumps相关:\Return, \Error, \Goto
- Multithreading相关:\Spawn, \Sync, \Parfor
- Comments相关:\Comment(注释"//"),\RComment(右对齐注释),\CommentSymbol(注释符号)
- Indentation相关:\Indentmore(增加缩进),\Startalign(后续行从指定字符串开始对齐),\Stopalign(停止前面的\Startalign命令)
其中,\Do与\Then表示的命令是完全一样的(详见源码)并增加1单位的缩进,都可与\End(减少1单位的缩进)配合使用。
需要注意的是使用\li对\Do和\Then所在行编号,但是它们的下一行不编号(因为\Do与\Then及\End都仅仅修改缩进并不实际显示)。
\begin{codebox}
\Procname{$\proc{KMP-Matcher}(T,P)$}
\li $n \gets \attrib{T}{length}$
\li $m \gets \attrib{P}{length}$
\li $\pi \gets \proc{Compute-Prefix-Function}(P)$
\li $q \gets 0$ \RComment number of characters matched
\li \For $i \gets 1$ \To $n$ \RComment scan the text from left to right
\li \Do
\While $q > 0$ and $P[q+1] \neq T[i]$
\li \Do $q \gets \pi[q]$ \RComment next character does not match
\End
\li \If $P[q+1] \isequal x[i]$
\li \Then $q \gets q+1$ \RComment next character matches
\End
\li \If $q \isequal m$ \RComment is all of $P$ matched?
\li \Then
print ``Pattern occurs with shift'' $i-m$
\li $q \gets \pi[q]$ \RComment look for the next match
\End
\End
\end{codebox}
上面代码实际运行效果:
可以使用\label{li:xxx}给某行伪代码做标记,然后在正文交叉引用该行所在编号。
同时可以使用\setlinenumber{li:xxx}直接设定伪代码中的当前行所引用的行号。
CLRS居然是没有break、continue这些关键词的,除了自己定制新关键词外也可以使用\kw命令实现$\texttt{break}$、$\texttt{continue}$的效果。