算法描述中的'Pseudocode Conventions'

五月 10, 2006

Pseudocode，即伪码，它常常用来描述一个算法，目的是能使被描述的算法能够容易的以任何一种计算机程序语言实现。’Pseudocode Conventions’可以理解为’伪码约定’，既然是’约定’那就并非强制性的标准。但是在专业的有关算法的文献和资料中，其相关内容多符合这些’Pseudocode Conventions’。如果你是一个想学习和钻研算法的人，那么建议你熟悉这些’Conventions’，俗话说：’磨刀不误砍柴工’吗！

‘Pseudocode Conventions’应该说也是有多种多样的，但是随着这么多年的积累和进化，渐渐的一些’Conventions’退出了人们的视线，此时你在一些重要的图书典籍上能看到的大概就是被人们广泛接受的一种’Convention’了。这里介绍一种比较常用的’Pseudocode Convention’，这种’Convention’在MIT Press出版的’Introduction to Algorithms 2nd‘中被广泛采用，在国内的一些算法书籍中也是’屡见不鲜’。

介绍’Pseudocode Conventions’其实与介绍一种程序设计语言的语法相似，看多了就会产生厌烦，这里先给出一个例子，让大家有个感性认识，找到一种新鲜感。^_^

这个例子源于’Introduction to Algorithms’一书中的那个著名的’Insertion-Sort’：
Insertion-Sort(A) △ A[1..n]
    for j <- 2 to length[A]
        do key <- A[j]
            △ Insert A[j] into the sorted sequence A[1..j-1].
            i <- j-1
            while i > 0 and A[i] > key
                do A[i+1] <- A[i]
                    i <- i-1
            A[i+1] <- key

对应上面的例子，下面是对该’Convention’的一些阐述条款：

1、每个指令占据一行，指令结束或者说行尾无任何符号。
2、利用’缩进(Indentation)’表示程序的块结构(Block Structure)。
3、符号’△’表示该行其后面的内容为注释。
4、’i <- j’为赋值语句，表示将j的值赋给i；而’i <- j <- e’这样的多重赋值形式则等价于’i <- e’, ‘j <- e’。
5、变量无需声明；一般情况下变量局限于某一特定的Procedure，除非有显式说明我们才使用全局变量。
6、数组A通过A[index]方式访问到数组内元素的值。
7、条件判断语句格式如下：
if (Condition1)
    then [ Block 1 ]
    else if (Condition2)
           then [ Block 2 ]
           else [ Block 3 ]

8、支持三种循环语句：while、for、repeat … until。’for t <- 0 to n’表示 t范围为[0, n)。
9、复合数据用对象(Object)来表示。对象由属性(Attribute)和域(Field)构成。域的存取是由域名后接由方括号括住的对象名表示，如上面李子中的length[A]，数组A被看成为一个Object，其域有length，表示数组中元素的个数，即length[A]。用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f，赋值y<-x就使f[y]=f[x]，换言之，在赋值y<-x后，x和y指向同一个对象。有时一个指针不指向任何对象，这时我们赋给它NIL。
10、参数传递方式为’值传递’方式，被调用的过程拥有自己的参数拷贝，被调用过程对参数的修改是不能被调用者看到的。当传递一个对象时，只是拷贝指向该对象的指针，而不拷贝其各个域。
11、布尔运算符’and’和’or’都是’short circuiting’的。如计算表达式’x and y’，如果x为FALSE，那么整个表达式就为FALSE，我们不再计算y了。

OK，罗列了11项，照比C这类的高级语言，这种’语法’显然简单的多，更易理解。以后要做的就是尽量在进行算法描述的时候使用这种’Pseudocode Convention’，毕竟熟才能生巧！