C语言程序设计基础教程：算法表示及应用

任务描述

如何从多个数据中找到最大值；如何从成千上万的数据中查找数据；如何进行密码的加密处理等问题，最终都要用计算机来实现，在实现之前首先要找到问题的求解方法，然后再用计算机来实现。而这里所谓的方法就是算法。如何将问题的求解方法描述出来，将是本任务的学习重点。

知识学习

算法是解决问题的方法和步骤，生活中处处都有算法，比如打扫一个房间，做一顿美味佳肴，只有明确了算法，才能做好一件事。对于程序来说也是有算法的，著名的计算机科学家沃思（Nikiklaus Wirth）曾提过一个公式：程序=数据结构+算法。数据结构是对数据的描述，而算法则是对操作的描述。由此，程序设计是离不开算法的，算法可以看作程序的灵魂。那什么是算法呢？

（1）算法

为解决一个问题而采取的方法和步骤称为算法。对于同一个问题，可以有不同的解题方法和步骤，一般采用简单和运算步骤少的算法。算法具有以下特性：

①有穷性。一个算法的操作步骤是有限的。

②确定性。算法的每一步应该是确定的，不应该产生歧义，也就是不能被理解成多种可能性。

③有零个或多个输入。有些算法需要输入一些原始数据，有些算法就不需要输入。

④有一个或多个输出。设计算法的最终目的是解决问题，因此每个算法至少有一个输出结果来反映问题的解决情况，如果算法无输出没有任何意义。

⑤有效性。算法的每一步都应有效地被执行，并得到确定的结果。

（2）算法的表示

在实际应用中，描述算法的方法有很多，如自然语言、传统流程图、N-S 流程图、伪代码和计算机语言等。

1）自然语言表示法

自然语言表示法是人类日常生活中使用的语言，也是最接近人类思想的一种方法，简单易懂，所以是最简单的算法描述工具。

举例：用自然语言表示两个数中最大值。

①定义两个变量x，y，存放要比较的两个数字。

②定义一个变量z，用于存放较大值。

③在键盘上输入两个数，分别赋给x，y。

④判断x 是否大于y，若成立，将x 赋给z，不成立，将y 赋给z。

⑤输出z 值。

可以看出，用自然语言表示程序的算法，虽然易懂但是麻烦，一般情况下，不建议采用这种方式来表达。

2）伪代码表示法

伪代码介于自然语言和计算机语言之间，采用了文字和符号来描述算法。伪代码结构清晰，代码简单，可读性好，类似于自然语言的特点。

举例：伪代码表示两数中较大值的算法。

①x 获得键盘中的值。(www.xing528.com)

②y 获得键盘中的值。

③

④输出max 的值。

可以看出，伪代码也是不使用图形，每一行或者每几行表示一个基本的操作。

3）流程图表示

流程图的作用是描述人们解决问题的方法、思路或者算法。流程图是用一些图形框来代表程序中的操作。这些图形框是由美国国家标准协会规定了的，见表3.1。

表3.1　流程图的符号

举例：用流程图表示求两个数中较大者的算法，如图3.1所示。

流程图具有采用简单的符号，画法简单，比较直观，结构清晰，逻辑性强，方便描述，容易理解，产生歧义等特点。

4）N-S 流程图

N-S 流程图是1973年由I.Nassi 和B.Shneiderman 两位美国学者提出的，也称为盒子图。将全部算法都写在一个矩形框内，去掉了带箭头的流程线，适用于结构化的程序设计，比较大小的N-S 盒子图如图3.2所示。

5）计算机语言

人与人之间交流用自然语言是比较方便的，但是这门课程要实现的是人与计算机的交流，那这就需要能被计算机直接或间接识别的语言，就是计算机语言。

图3.1　比较大小流程图

图3.2　比较大小的N-S 图

计算机语言作为指挥计算机工作的工具，经历了机器语言、汇编语言和高级语言3 个阶段，C语言就是高级语言中的一种。用计算机语言描述算法的好处在于可以在计算机中运行程序，这符合算法要最终变成程序，以便在机器上实现的需求。

使用C语言完成前面例子的实现：

任务总结

算法必须能在执行有限个步骤之后终止，算法的每一步骤必须有确切的定义。一个算法有0 个或多个输入，以刻画运算对象的初始情况，所谓0 个输入是指算法本身定出了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的，算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称为有效性）。

一个问题的求解算法可能不止一种，必须择优而选，“优”主要考虑两个方面：时间复杂度和空间复杂度。