程序设计基础讲义（二）.docVIP

第二章 程序设计概述 　　我们知道，计算机系统包括硬件系统和软件系统，硬件系统好比人的躯体，软件系统好比人的灵魂。为了能让计算机为人类做更多的事，不仅要为它配备一套性能良好的硬件设备，还要为其设计出能够解决各式各样问题的软件（即计算机程序）。而要想让计算机代替人们解决某个问题，就得设计出求解该问题的程序。 　　2.1 程序设计的基本过程和原则 　　程序设计的基本过程一般由分析所求解的问题、抽象数学模型、选择合适算法、编写程序、调试通过直至得到正确结果等几个阶段所组成。其设计步骤可以分为（书P23）： 　　(1)确定要解决的问题。 　　(2)分析问题，建立数学模型。 　　(3)选择计算方法。 　　(4)确定数据结构和算法。 　　(5)绘制流程图。 　　(6)编写程序。 　　(7)调试程序。 　　(8)整理资料，交付使用。 　　2.2 数据结构概述 　　在计算机发展的初期，计算机主要用于数值计算，处理的是数值数据，而且数据量小，结构简单，形式统一。随着计算机技术的发展，计算机应用领域的扩大，越来越多的非数值数据需要处理，数据的概念也被大大推广，数字、字符、图像、声音都可属于数据的范畴。与数值数据相比，非数值数据的结构比较复杂，其计算机表示也比较麻烦。 　　只有对数据内部的结构关系以及数据在计算机内如何存储和操作进行深入的研究，才能设计出高效可靠的程序，实现对数据的有效处理。 　　2 ．2．1. 数学模型 　　前面我们在谈到程序设计过程时讲到，用计算机解决一个实际问题，首先必须从具体问题抽象出一个适当的数学模型，用这个数学模型应能得出该问题的精确或近似解。然后确定数学模型的计算方法，根据问题的具体要求，可在已知的各种算法中选择一种合适的算法或另设计一种新的算法。接下来就是用某种程序设计语言为确定的算法编制计算机程序，同时准备好作为程序处理对象的各种数据。再接下来就开始程序的调试运行，用一些典型的数据和描述边界条件的数据对程序进行测试，以便发现和纠正程序中的错误，错误的纠正可能导致前面步骤的多次反复。最后，在程序调试达到所要求的质量标准之后，就可正式投入运行，最终在计算机上得出问题的解。 　　建立实际问题的数学模型是计算机应用必须首先进行的工作，也是一项很重要的工作。 　　常见的数学模型可分为数值计算和非数值计算两大类。许多实际问题数学抽象的结果是数学方程。这些数学方程可以用解析的方法求出精确解，或者用模拟的方法求出近似解。但是更多的实际问题无法用数学方程来描述，这些问题所求的不是某个数值，而是某种检索的结果，某种排列的状态，某种转换后的形式，某种设计的表示……这些问题的数学模型不是用数学方程，而是用一种数据结构来描述数据以及数据之间的相互关系。 　　2 ．2．2．数据结构的概念 　　数据是对客观事物的名称、数量、特征、性质的描述形式（即编码），是计算机所能处理的一切符号的总称。数据既是计算机加工的对象，又是计算机的产品（计算结果）。例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或者文字处理程序的处理对象是字符串。因此，对计算机科学来讲，数据的含义很广泛，比如图形、图象、色彩和声音等都可以通过编码而归于数据的范畴。 　　一般，我们对那些单个的孤立的数据并不感兴趣，而着重研究由众多数据元素组成的数据集合，研究集合中数据元素之间存在怎样的内在联系，通常需要对数据和数据集合进行哪些运算（即对数据进行的处理），如何提高运算效率等等，这就引出了数据结构。 　　数据结构里包括一批数据，是数据的一个集合。这个集合中的每一个数据个体称为数据元素，它是数据的基本单位。一个数据元素又叫做一个数据结点，简称结点。 　　数据类型是指程序设计语言中所允许的变量的种类，也就是变量可以取的值和可以进行的运算的集合。可以把数据类型看成是在程序设计语言中已经实现了的数据结构。 　　一个数据元素可以是简单的，只有一个数据项，例如一个数，一个字符，一个名字等；也可以是复杂的，由若干数据项组成，一个数据结点由用来描述一个独立事物的名称、数量、特征、性质的一组相关信息组成。例如，在设计处理学生成绩问题的程序时，每个学生有关的数据项(域)构成一个数据结点，可能包括学生的姓名、学号、各科考试成绩等等，学号可以作为结点的关键字。在处理库存商品问题时，一个数据结点对应一种商品的相关数据项，包括商品编号和名称、规格、数量、生产厂家、单价、入库日期等，商品编号可以作为关键字。 　　数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的存储结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法。 　　2.3 算法概述 　　为了有效地进行程序设计，不仅要掌握一门程序设计语言，还应该学会针对各类问题拟定出有效的解题方法和步