高级语言程序设计

本节主要介绍电子计算机发展、计算机语言、计算机程序和程序设计方法等基本概念，着重介绍算法及其描述方法。

计算机发展

1946年第一台电子计算机ENIAC（Electronic Numerical Integrator And Computer，ENIAC)于宾夕法尼亚州立大学诞生。

冯·诺依曼体系结构确立了现代计算机的体系结构。

根据组成电子计算机的电子器件，电子计算机已经历了四个时代

• 20世纪50年代，主要采用真空电子管制造计算机。这些由电子管组成的计算机被称为第一代计算机，主要用于科学计算，人们用机器语言编写程序，此时的计算机仅仅是计算机科学家手中的工具
• 20世纪50年代末期，出现了以晶体管为主要元件的第二代计算机。在体积、耗电量和寿命等方面较于第一代计算机有了很大的改进。同时随着高级语言和系统软件的出现，对计算机的操作和使用不再专属于少数的计算机专家
• 1964年，采用集成电路技术的第三代计算机占领市场。计算机软件也在同一时期逐渐系统化，多用户、分时处理、分布式等概念的提出以及计算机网络的的兴起，使得计算机用户可以不受地域限制快捷的共享软、硬件和信息资源。
• 随着大规模集成电路和微处理器的出现，计算机进入第四代。大规模集成电路的使用标志着集成电路技术进入微电子时代。

计算机语言

计算机语言的发展经历了从机器语言、汇编语言到高级语言的历程。

• 机器语言是用二进制代码表示的能被计算机识别和执行的指令集合。机器语言的每一条语句实际上就是一条指令。

优点：程序不需要翻译，可以直接运行，因此占用存储空间小，执行速度快且运行效率高
缺点：可读性差，编程不方便，与运行的机器底层结构关系密切。语言通用性差，程序可移植性差。

• 汇编语言：为了克服机器语言的不足，人们利用助记符代替机器语言，因此产生了汇编语言，在一定程度上克服了难以编写和阅读的缺点，同时具有占用存储空间少，执行效率高的优点。但是仍然与底层机器的结构密切相关。
• 高级语言：描述算法很方便，而且不依赖于具体的机型，能够不需修改而在任何计算机上运行，具有良好的可移植性、贴近自然语言，所以便于编程，但是执行效率较低。

因为计算机无法直接理解和执行高级语言，必须将其转换成机器语言程序才能执行。

世界上第一个高级语言是FORTRAN。

算法

计算机程序的目的是让计算机帮助人们完成工作，为此程序必须解决两个核心问题，做什么和怎么做。

做什么，需要在计算机程序设计的前半段完成，即确定程序的功能。
怎么做，需要针对具体问题设计算法。

算法就是解决问题的具体步骤，在日常生活中的任何事情也都有它的算法。

任何一个能够解决问题的算法都必须具备以下五个特性：

• 可执行性：算法中的每一步骤都是可执行的。
• 确定性：算法中每一步骤都必须是明确定义的。不得有任何歧义（非确定性）。
• 有穷性：一个算法必须在执行有穷步骤后结束。
• 有输入信息的说明：有的算法可以没有输入信息，然而绝大多数都具有。
• 有输出信息的步骤：一个算法应当至少有一个输出问题答案的步骤。

为了获得易读、易懂、易修改和可扩充的算法，人们认为必须采取一下三种措施：

• 利用自顶向下的方法设计算法
• 只利用顺序、选择和循环三种基本结构构造算法
• 具有优美的算法表达风格。

在设计算法时，应当仔细分析所需判断的条件，如何一步一步缩小判断范围。对于有些问题，判断的先后次序是无所谓的，而有些问题，判断条件的先后次序是不能任意颠倒的。算法应该具有通用性和灵活性。

算法的描述方法

描述算法可以使用多种方法。常用的算法描述方法有自然语言、传统流程图、N-S流程图、伪代码和计算机语言。

自然语言

自然语言是我们日常使用的语言。用自然语言描述算法通俗易懂，但文字冗长，容易出现歧义。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。因此除了很简单的问题。一般不用自然语言描述算法。

传统流程图

流程图是用一些图形表示各种操作。用图形描述算法形象直观、易于理解。ANSI规定了一些常用的流程图符号，已为世界各国程序人员普遍采用。

流程图的基本元素

图c判断框表示对一个给定的判断进行判断，根据给定的条件是否成立决定如何执行其后的操作。

图e的流程线，需要注意不要忘记画箭头。因为它用来反映流程执行的顺序，如果不画箭头就难以判断各个框的执行次序。

图f所示的连接点（小圆圈）表示将画在不同地方的流程线连接起来。如有两个以上的连接点，可以使用数字标注（在圆圈内写上数字），来配对。使用连接点可以避免流程线的交叉或过长，是流程图更清晰。

连接点示例

图g所示的注释框是流程图中必要的部分，它不反映流程和操作。只是为了对流程图中某些框的操作进行必要的补充说明，以帮助人们更好的理解流程图的作用。

用流程图表示算法直观形象，可以比较清晰的显示各个框之间的逻辑关系。但是这种流程图占用篇幅较大，尤其当算法比较复杂时，画流程图既费时又不方便。在结构化程序设计方法广泛使用之后，已采用N-S结构化流程图代替这种传统的流程图。但是每个编程人员都应该数量掌握传统流程图的画法。

N-S流程图

为了提高算法的质量，使算法的设计和阅读更加方便，人们设想规定出了三种基本结构，由这三种基本结构按照一定规律组成算法结构。这个算法结构是自上而下地将各个基本结构顺序的排列起来。如果能做到这点，算法的质量就能得到保证和提高。

三种基本结构：

• 顺序结构
• 选择结构（分支结构）
  • 一个判断框的出口有两个，但是一个选择结构只有一个出口。
• 循环结构（重复结构）

三种结构中，每一个部分都有机会被执行到。结构内不存在死循环。

由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于结构化的算法。不存在无规律的跳转，只在基本结构内才允许存在分支和向前或向后的跳转。

既然使用三种基本结构的循序组合可以表示任何复杂的算法。那么基本结构之间的流程线就多余了。1973年I.Nassi和B.Shneiderman提出了新的流程图形式，完全去掉了带箭头的流程线，这个算法写在一个矩形框内，在该框内还可以包含其他从属它的框。这种流程图又称为N-S结构流程图。由于这种流程图适合结构化程序设计，因而很受欢迎。

顺序结构 选择结构 循环结构

综上，N-S流程图表示算法的优势是比自然语言描述直观、形象、易于理解；比传统流程图紧凑易画，尤其是废除了流程线。

N-S流程图中的上下顺序就是执行时的顺序，写算法和看算法只需从上至下即可。用N-S流程图表示的算法都是结构化的算法，不可能出现流程无规律的跳转。

N-S流程图如同一个多层的盒子，因此又称为盒图（Box Diagram)。

伪代码

伪代码是用介于自然语言和计算机语言之间的文字和符号描述算法。伪代码不使用图形符号，因此书写方便，格式紧凑、也容易理解，便于向计算机语言过渡。

计算机语言中的语句关键字用英文表示，总之以便于书写和阅读为原则。用伪代码描述算法无固定、严格的规则。只要把意思表达清楚，并且书写的格式清晰易读即可。

计算机语言

我们执行程序来实现算法，所以计算机语言也是算法的一种描述方法。相较于伪代码，编写程序必须严格遵循所用编程语言的语法规则。应当强调的是。只有程序执行时才是真正的实现算法。

程序

程序是利用计算机语言将所要解决问题中的数据以及处理问题的方法和步骤进行完整而准确的描述，这一描述的过程称为程序设计。

对数据的描述是指明数据结构形式；对处理方法和步骤的描述即是描述算法。所以：

程序设计方法

程序设计方法主要有两种：结构化程序设计方法和面向对象程序设计方法

结构化程序设计方法

结构化程序设计方法又称为面向过程的程序设计，是荷兰 E.W.Dijkstra于1965年提出。结构化程序设计方法的核心是模块化。即将待开发的程序划分为若干个相互独立的模块，每个模块完成特定的功能。这样就可以使程序员完成每个模块的工作变得单纯和明确，适合于设计大规模的复杂程序。

要点：

采用自顶向下，逐步求精的设计方法。程序员在接到程序设计的任务后，先整体规划，形成一个笼统和抽象的方案框架，称之为顶层设计。在顶层设计的基础上，进一步细化，每一次细化都会是方案更加的具体和明确，依次称为第2层、第3层…，知道不需要细化为止。最后，整个方案被分解称一系列功能独立的程序模块。
程序由三种基本结构组成。在每个模块内部以及模块之间都只有顺序、选择和循环三种基本结构。
优点：

因为采用自顶向下，逐步求精的设计方法，使得整个设计方案层次分明，程序员容易编码实现，读者容易阅读理解。对于复杂的程序，可以先易后难，先抽象后具体，使得程序设计工作整体思路清晰，目标明确，程序员可以有条不紊地推进。
程序有相互独立的模块构成，因此在设计某个模块时，不会受到其他模块的牵连，因而可将较为复杂的问题化简为一系列简单模块的设计。模块的独立性还为扩充已有的系统、建立新系统带来方便
缺点：

用户的要求难以在需求分析阶段被准确定义，这样有可能导致在程序交付时产生问题。
由于程序的开发工作分为若干各顺序的阶段，每个阶段任务完成才能进行之后的工作，开发周期较长，而且如果这一过程中若用户需求发生变化，之前的工作则需要推倒重来。

面向对象程序设计方法

1967年，Kristen Nygaard和Ole Johan Dahl开发了Simula 67语言，它提供了比子程序更高一级的抽象和封装，引入了数据抽象和类的概念，被认为是第一个面向对象的语言。从此，面向对象的程序设计方法也随之产生。

面向对象的核心思想是将程序或软件看成是一个由对象组成的集合：这些对象具有足够的智能，能够理解从其他对象接受的信息，并以适当的行为做出响应；允许底层对象从高层对象继承属性和行为。通过这样的设计思想和方法，将所模拟的现实世界中的事物直接映射到软件系统的解空间。

与传统的结构化程序设计方法相比，面向对象程序设计吸取了结构化程序设计的一切优点，而二者间最大的区别是：

面向对象方法采用数据抽象和信息隐藏技术是组成类的数据和操作是不可分割的，避免了结构化程序设计数据和过程分离引起的弊病。
面向对象的程序由类、对象（类的实例）和对象之间的动态联系组成的。而结构化程序是由结构化的数据、过程的定义以及调用过程处理相应的数据组成的。

面向对象编程是一门哲学，它通过对语言建模来适应问题，而不是对问题建模以适应语言。
From 《C Primer Plus》6th Edition