第1章程序设计基础知识

C语言程序设计计算机学院谭忠兵第1章程序设计基础知识第2章C语言概述第3章数据类型与运算规则第4章顺序结构的程序设计第5章选择结构的程序设计第6章循环结构的程序设计第7章数组第8章函数第11章文件目录程序与程序语言算法和算法表示第1章程序设计基础知识C语言程序设计第一章程序设计基础知识结构化程序设计方法C语言程序设计第一章程序设计基础知识§1.1程序与程序语言程序语言的发展机器语言汇编语言高级语言面向过程面向对象CPU指令系统，由0、1序列构成的指令码组成如：10000000加10010000减用助记符号描述的指令系统，可进行地址、位操作如ADDA,B编写系统软件，直接对硬件操作，可读性，移植性差面向机器的语言可读性，移植性好，编写应用程序一般较难实现汇编语言的某些功能如：地址和位的操作C语言兼有高级和低级语言的功能适合写系统软件和应用软件又称中级语言C语言程序设计第一章程序设计基础知识程序设计：用计算机语言对所要解决的问题中的数据以及处理问题的方法和步骤所做的完整而准确的描述过程。程序包括：数据结构：数据的类型和组织形式算法：操作步骤的描述NikiklausWirth提出：程序=数据结构+算法教材认为：程序=算法+数据结构+程序设计方法+语言工具和环境灵魂加工对象工具C语言程序设计第一章程序设计基础知识§1.2算法和算法的表示算法的概念广义地说，为解决一个问题而采取的方法和有限的步骤，就称为“算法”。•方法1：1+2，+3，+4，一直加到100•方法2：100+(1+99)+(2+98)+…+(49+51)+50=100+49×100+50对同一个问题，可有不同的解题方法和步骤例：求1001nn为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。计算机算法可分为两大类别：•数值运算算法：求数值解，例如求方程的根、求函数的定积分等。•非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。C语言程序设计第一章程序设计基础知识§1.2算法和算法的表示算法的概念简单算法举例例1:求1×2×3×4×5步骤1：先求1×2，得到结果2步骤2：将步骤1得到的乘积2再乘以3，得到结果6步骤3：将6再乘以4，得24步骤4：将24再乘以5，得120如果要求1×2×…×1000，则要写999个步骤C语言程序设计第一章程序设计基础知识S1：使p=1S2：使i=2S3：使p×i，乘积仍放在变量p中，可表示为：p=p×iS4：使i的值加1，即i=i+1。S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数，i为乘数。用循环算法来求结果,算法可改写：C语言程序设计第一章程序设计基础知识S1：p=1S2：i=3S3：p=p×iS4：i=i+2S5：若i≤999，返回S3。否则，结束。如果题目改为：求1×3×5×……×999算法只需作很少的改动：C语言程序设计第一章程序设计基础知识用这种方法表示的算法具有通用性、灵活性。S3到S5组成一个循环，在实现算法时要反复多次执行S3，S4，S5等步骤，直到某一时刻，执行S5步骤时经过判断，乘数i已超过规定的数值而不返回S3步骤为止。此时算法结束，变量p的值就是所求结果。C语言程序设计第一章程序设计基础知识例2有50个学生，要求将他们之中成绩在80分以上者打印出来。设n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用G代表学生成绩，gi代表第i个学生成绩，算法表示如下:S1：i=1S2：如果gi≥80，则打印，否则不打印。S3：i=i+1S4：如果i≤50，返回S2，继续执行。否则算法结束例3求算法如下：1001991......4131211S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)×signS5：term=sign×(1/deno)S6：sum=sum+termS7：deno=deno+1S8：若deno≤100返回S4，否则算法结束。单词作变量名，以使算法更易于理解：sum表示累加和，deno是英文分母（denominator）缩写，sign代表数值的符号，term代表某一项。反复执行S4到S8步骤，直到分母大于100为止。一共执行了99次循环，向sum累加入了99个分数。sum最后的值就是多项式的值。C语言程序设计第一章程序设计基础知识•有穷性：包含有限的操作步骤•确定性：算法中的每一个步骤都应当是确定的•有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果。•有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息•有一个或多个输出：算法的目的是为了求解，“解”就是输出一个算法应该具有以下特点：C语言程序设计第一章程序设计基础知识§1.2算法和算法的表示算法的基本特征可以用不同的方法表示算法，常用的有：–自然语言–程序语言–流程图–N-S图–PAD图–伪代码C语言程序设计第一章程序设计基础知识§1.2算法和算法的表示算法的表示§用流程图表示算法美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号：起止框判断框处理框输入/输出框注释框流向线连接点例1将求5!的算法用流程图表示如果需要将最后结果打印出来，可在菱形框的下面加一个输出框。例2将例2的算法用流程图表示。打印50名学生中成绩在80分以上者的学号和成绩。如果包括输入数据的部分，流程图为例3将例3的算法用流程图表示1001991......4131211小结：§流程图是表示算法的较好的工具。一个流程图包括以下几部分：(1)表示相应操作的框；(2)带箭头的流程线；(3)框内外必要的文字说明。1、传统流程图的弊端传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。如图：C语言程序设计第一章程序设计基础知识§1.3结构化程序设计方法传统流程图的流程可以是：这种如同乱麻一样的算法称为BS型算法，意为一碗面条(ABowlofSpaghetti)，乱无头绪。缺点：难以阅读、修改，使算法的可靠性和可维护性难以保证。解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去。C语言程序设计第一章程序设计基础知识传统流程图流向混乱、可读性差，所以应该采用结构化流程图。结构化程序设计基本思想：任何程序都可以用三种基本结构表示，限制使用无条件转移语句（goto）结构化程序：由三种基本结构反复嵌套构成的程序优点：结构清晰，易读，提高程序设计质量和效率2、三种基本结构计算机科学家Bohra和Jacopini提出了以下三种基本结构：顺序结构、选择结构、循环结构用这三种基本结构作为表示一个良好算法的基本单元。C语言程序设计第一章程序设计基础知识三种基本结构的图示：顺序结构选择结构C语言程序设计第一章程序设计基础知识循环结构的图示：当型(While型)循环结构直到型(Until型)循环C语言程序设计第一章程序设计基础知识三种基本结构的共同特点：(1)只有一个入口；(2)只有一个出口；（请注意：一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口(3)结构内的每一部分都有机会被执行到；(4)结构内不存在“死循环”(无终止的循环)。C语言程序设计第一章程序设计基础知识图中没有一条从入口到出口的路径通过A框。不正确的流程表示：流程内的死循环C语言程序设计第一章程序设计基础知识小结：§由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。C语言程序设计第一章程序设计基础知识C语言程序设计第一章程序设计基础知识总结结构化程序设计方法结构化程序：用三种基本结构组成的程序基本设计思路：复杂问题分解成几个最基本问题，再分别处理。采用的方法：自顶向下；逐步细化；模块化设计：复杂问题按功能分成多个子模块结构化编码：正确采用三种基本结构实现用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫做“自顶C语言程序设计第一章程序设计基础知识自顶向下，逐步细化方法的优点：考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。C语言程序设计第一章程序设计基础知识模块设计的方法：•模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。•在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。•子模块一般不超过50行•划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。C语言程序设计第一章程序设计基础知识小结：§算法为解决一个问题而采取的方法和有限的步骤§算法表示：流程图§三种基本结构：顺序结构、选择结构、循环结构§结构化程序设计方法：自顶向下；逐步细化；模块化设计：结构化编码：C语言程序设计第一章程序设计基础知识