C语言程序设计_01概述.pptx

第1章 概述1.1 程序设计基本知识1.2 C语言的发展与特点1.3 C语言程序的基本结构1.4 C语言程序的运行本章小结 1.1 程序设计基本知识1.1.1 程序与程序设计程序是用某种计算机能理解并执行的语言所描述的解决问题的方法和步骤。一个计算机程序主要描述两部分内容：一是描述问题的每个对象和对象之间的关系，二是描述对这些对象作处理的处理规则。其中关于对象及对象之间的关系是数据结构（Data Structure）的内容，而处理规则是求解的算法（Algorithm）。 使用计算机解决实际问题，通常是先要对问题进行分析并建立数学模型，然后考虑数据的组织方式和算法，并用某一种程序设计语言编写程序，最后调试程序，使之运行后能产生预期的结果。这个过程称为程序设计（Programming）。具体要经过以下4个基本步骤：（1）分析问题，确定数学模型或方法。（2）设计算法，画出流程图。（3）选择编程工具，按算法编写程序。（4）调试程序，分析输出结果。 1.1.2 算法及其描述著名的瑞士计算机科学家N. Wirth教授曾提出：算法+数据结构=程序算法是对数据运算的描述，而数据结构是指数据的组织存储方式，包括数据的逻辑结构和存储结构。程序设计的实质是对实际问题选择一种好的数据结构，并设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。 1．算法的概念计算机解决问题的方法和步骤，就是计算机解题的算法。要编写解决问题的程序，首先应设计算法，任何一个程序都依赖于特定的算法，有了算法，再来编写程序是容易的事情。下面举两个简单例子，以说明计算机解题的算法。 【例1.1】 这一题的算法并不难，可写成：（1）从键盘输入a，b的值。（2）如果ab，则 x=a2+b2,y=(a+b)/(a-b)，否则x=a2-b2,y=4/(a+b)。（3）计算u的值。（4）输出u的值。 【例1.2】输入10个数，要求找出其中最大的数。（1）输入一个数，存放在max中。（2）用i来统计比较的次数，其初值置1。（3）若i≤9，执行第(4)步，否则执行第(8)步。（4）输入一个数，放在x中。（5）比较max和x中的数，若xmax，则将x的值送给max，否则，max值不变。（6）i增加1。（7）返回到第（3）步。（8）输出max中的数，此时max中的数就是10个数中最大的数。 2．算法的特性从上面的例子中，可以概括出算法的5个特性：（1）有穷性。算法中执行的步骤总是有限次数的，不能无止境地执行下去。（2）确定性。算法中的每一步操作必须具有确切的含义，不能有二义性。（3）有效性。算法中的每一步操作必须是可执行的。（4）要有数据输入。（5）要有结果输出。 3．算法评价标准目前，评价算法质量有4个基本标准：（1）正确性。（2）可读性。（3）通用性。（4）高效率。 4．算法效率的度量算法效率的度量分为时间度量和空间度量。（1）时间度量算法的执行时间需要依据该算法编制的程序在计算机上运行时所消耗的时间来度量。通常把算法中进行简单操作的次数的多少称为算法的时间复杂度，它是一个算法执行时间的相对度量。一般没必要计算出算法的精确复杂度，只要大致计算出相应的数量级即可，即随着问题规模n的增大，算法的执行时间的增长率如何，这个时间增长率称为阶。若算法的时间复杂度是n阶的，记为T(n)=O(n)。 按数量级递增顺序，常见的几种时间复杂度有O(1)、O(log2 n)、O(n)、O(nlog2 n)、O(n2)、O(n3)、O(2n)等。T(n)=O(1)表示算法执行时间与问题规模无关。图1-1给出了各种具有代表性的时间复杂度T(n)与问题规模n的变化关系。 图1-1 时间复杂度函数曲线比较 一个算法的时间复杂度除了与问题的规模有关外，还与输入的数据的次序有关，输入的次序不同，算法的复杂度也不同，所以当分析算法的复杂度时，还要考虑到最好、最坏和平均复杂度。 （2）空间度量通常把算法在执行过程中临时占用的存储空间定义为算法的空间复杂度。 5．算法的描述常用流程图、结构化流程图和伪代码等描述工具来描述算法。（1）用流程图描述算法流程图也称为框图，它是用一些几何框图、流程线和文字说明表示各种类型的操作。 【例1.3】用流程图来描述例1.1和例1.2的算法。流程图分别如图1-2和图1-3所示。 图1-2 用一般流程图描述例1.1的算法 图1-3 用一般流程图描述例1.2的算法 （2）用N-S图描述算法① 程序的3种基本结构程序的3种基本结构：顺序结构、选择结构和循环结构。顺序结构是最简单的一种基本结构，依次顺序执行不同的程序块，如图1-4所示。其