2.2 算法设计

“欲速则不达”，很多初学者看懂了问题后，一般会马上进行编码。这对于一般的小程序可能没什么问题，但若是输入数据复杂和规模较大的程序，还需要进行算法的设计。从软件工程角度看，算法设计包含在系统设计阶段内，主要包括数据设计(主要是数据结构)和算法设计两个部分。下面简单介绍数据设计及算法设计所采用的技术和描述工具，并举例说明设计的过程。

2.2.1 数据设计

数据设计是在分析问题的基础上进行的。一般程序的数据设计主要是对重要的变量和数据结构进行设计和命名。数据设计是否合理，对于后续的算法设计有着重要的影响。一般情况下，数据设计先于算法设计，也可在算法设计中穿插数据设计。

对于重要变量的设计，主要考虑的问题是数据的类型和命名。数据的类型其实主要根据问题的数据要求确定，而变量的命名则属于程序的风格。例如根据是否有负数来确定是signed或unsigned，根据数据的大小来确定是short、int或long，根据数据的精度要求来确定是float或double。另外，数据在不同的C语言版本和编译器中是不同的。例如在VC中short是16位的，如果要单独处理字节数据一般设计为char类型。另外，VC中long只有32位，如果要使用64位数据则可设计为_int64类型。一般常用的循环变量或临时变量可以不用特别考虑，在算法设计或编码时再定义也可以。

关于数据结构设计，建议做到以下几点：

(1)尽量使用简单的数据结构。一般来说，数据结构简单，操作相对也会简单。

(2)尽量使用经典的数据结构。经典的数据结构，理解起来相对容易。例如普通的二叉树大家可能都接触过，而像线段树这类不怎么使用的数据结构理解起来就比较困难。

(3)尽量使用顺序的数据结构。相对来说，动态的指针结构理解和调试起来难度会大很多。

(4)正确处理数据的冗余和关联，尽量做到平衡。

(5)设计数据结构时尽量考虑可复用性。可复用的数据结构会给下次开发带来很多方便。

(6)对于复杂的数据结构，还可以给出图形和文字描述，以便于理解。

2.2.2 结构化程序设计技术

结构化程序设计(Structured Programming)的概念最早是由迪克斯特拉(E.W.Dij kstra)在1965年提出的，是软件发展的一个重要的里程碑。一般来说，结构化程序设计是在结构分析的基础上进行的，也可以直接在设计环节使用结构化程序设计方法。对于结构化程序设计来说，主要观点有以下几点：

1．清晰第一的设计风格

在结构化程序设计概念刚提出来时，迪克斯特拉就公开提出了在高级语言中取消GOTO语句的主张，进而引发了有关程序设计“是效率第一，还是清晰第一”的争论。这场辩论最后改变了许多人单纯强调程序效率的旧观，进而确定了“清晰第一，效率第二”的设计风格。这一设计风格也成了结构化程序设计应遵守的设计风格。

2．结构化的控制结构

通过20世纪60年代以来一系列论文观点的不断综合，基本确定结构化的程序设计使用单入口、单出口，以及使用顺序、选择、循环三种基本控制结构的原则来构造程序。由这三种基本结构或三种基本结构复合嵌套构成的程序称为结构化程序。结构化程序具有结构清晰、层次分明及良好的程序可读性。

3．逐步细化的实现方法

“自顶向下，逐步求精”是一种分而治之的思维方式，它早已经在日常生活和工作中被频繁使用，只不过我们不自觉或没意识到罢了。例如写一本书，首先要写一个提纲，全书分成几章；再对每一章列出本章分几节；然后对每一节分出几小节等；最后再具体写每个小节。

2.2.3 算法的描述工具

为了描述一个算法，可以有很多种方法。常用的算法表示方法有PDL语言、N-S流程图等。

1.PDL语言(Program Design Language)

作为在软件设计中广泛使用的设计语言之一，PDL语言是由美国的Caine和Gordon在1975年提出的。它是介于自然语言和形式化语言之间的一种类自然语言，也称为结构化语言。除了用英语表示外，PDL也可以使用中文表示。图2-1和图2-2分别表示了利用PDL描述选择结构和循环结构。

例2-2和例2-3说明了如何使用英文和中文PDL对例2-1的累加求和问题进行算法描述。

【例2-2】 累加求和。算法用PDL描述(英文)。

      Read N
      Set Sum=0
      Set I=0
      Loop while I<=N
          Sum=Sum+I
      End loop
      Print  Sum

【例2-3】 累加求和。算法用PDL描述(中文)。

      输入N
      初始化Sum和I
      循环N次
          利用Sum对I进行累加
      输出Sum

对于PDL的使用，以下几点需要注意：

(1)相对于自然语言，PDL要严谨一些，有一定的语法，但是在实际的使用过程中，也不一定要严格遵守，如程序的控制结构也可使用中文的“如果……则……”结构，另外如例2-3中的“初始化Sun和I”的简单过程描述，只要大家都能看懂，也是可以的。

(2)对于复杂问题用PDL进行描述，也可以使用结构化程序设计的“逐步求精”思想，先描述程序总体的控制结构，中间某些处理过程可以先用自然语言进行总体的描述，再进行细化描述。

2.N-S图

N-S图是结构化程序设计方法中用于表示算法的图形工具之一。对于结构化程序设计来说，传统流程图显得太复杂和有所欠缺。因为传统流程图出现得较早，它更多地反映了机器指令系统设计和传统程序设计方法的需要，难以保证程序的结构良好。另外，结构化程序设计的一些基本结构在传统流程图中没有相应的表达符号。例如，在传统流程图中，循环结构仍采用判断结构符号来表示，这样不易区分到底是哪种结构。为此，两位美国学者Nassi和Shneiderman于1973年就提出了一种新的流程图形式，并以两位创作者姓名的首字母取名为N-S图。

N-S图的基本单元是矩形框，它只有一个入口和一个出口。长方形框内用不同形状的线来分割，可表示顺序结构、选择结构和循环结构。在N-S图中，完全去掉了带有方向的流程线，程序的三种基本结构分别用三种矩形框表示，将这种矩形框进行组装就可表示全部算法。这种流程图从表达形式上就排除了随意使用控制转移对程序流程的影响，限制了不良程序结构的产生。

与顺序、选择和循环这三种基本结构相对应的N-S图的基本符号如图2-3所示。图2-3(a)和图2-3(b)分别表示顺序结构和选择结构，图2-3(c)表示循环结构。由图可见，在N-S图中，流程总是从矩形框的上面开始，一直执行到矩形框的下面，这就是流程的入口和出口，这样的形式不可能出现无条件转移的情况。

【例2-4】 利用N-S图描述累加求和，如图2-4所示。

对于N-S图的使用，也有以下几点需注意：

(1)N-S图符合结构化程序设计的基本思想，同时也可以使用“逐步求精”方法进行描述。

(2)对于初学者来说，N-S图存在一定问题，当程序内嵌套的层数增多时，内层方框会越来越小，这会增加画图难度，并影响图形的清晰度。这个问题可以通过使用调用或转义方式。如图2-5所示，如果一个盒子小到一定程度后可以另外再画一个盒子进行描述。

2.2.4 结构化程序设计示例

在了解了结构化程序设计的基本思想和算法描述工具后，下面介绍利用N-S图来对选择排序算法进行算法设计。

【例2-5】 利用N-S图选择排序算法设计。

第一步，进行数据结构设计。首先，如果问题没有特殊要求，排序的数据可以使用数组进行存储。其次，根据可理解性和可维护性要求，先定义一个数组的最大长度的变量DATASIZE。最后，为方便操作，可定义数组data及当前的数组长度DataLen。

第二步，将问题的算法的处理过程先分解为输入、处理和输出三个部分，并画出N-S图，结果如图2-6所示。

第三步，一般情况下，可先对处理过程的关键过程进行细化，这里先对“对数据进行选择排序”的处理过程进行细化，得到如图2-7所示的结果。

第四步，在图2-7中的“进行一趟排序”还是比较模糊的，再进行细化后得到如图2-8所示的排序。当然，这里也可以对一趟排序中涉及的变量进行定义。

第五步，再对图2-6的输入和输出进行细化，可以得到如图2-9所示的N-S图。当然，还可以对循环过程中涉及的循环变量进行定义，并对其中的几个条件加以改进。另外，还可以对其中的一些处理过程进行细化。

几点总结：

(1)很多初学者觉得进行算法设计并且进行描述很麻烦，很多时候都是编好了程序再回头进行算法的描述。当然，这种方法虽然很简单，但是，正如前面所介绍的，这种方法对付小程序可能没什么问题，但对于复杂的程序就不行了。“自顶向下，逐步求精”的分而治之的思想能降低解决问题的难度，希望初学者能坚持使用。

(2)很多初学者一开始很纠结算法设计时的细化程度，觉得算法设计要确定所有的变量及处理过程，最好细化到每条语句。其实程序的算法设计细化程度可以因人而异，只要清楚了处理过程，编码时没有难度和二义性就可以了。