《C语言程序设计》第二章算法及算法设计简介课件

2020/5/30,1,武汉理工大学计算机学院,授课教师：彭德巍,C语言程序设计,2020/5/30,2,第二章算法及算法设计简介,2.1算法的概念2.2算法的设计与表达2.3简单的算法实例2.4结构化程序设计方法简介,2020/5/30,3,算法的概念,任何一个程序应包含的如下两方面的内容：(1)对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构(datastructure).(2)对操作的描述。即操作步骤，也就是算法(algorithm)。,著名计算机科学家沃思(NikiklausWirth)提出公式数据结构算法程序,算法：是对解决某个问题的方法步骤的描述。,程序：从计算机角度来说，程序是用某种计算机能理解并执行的计算机语言描述解决问题的方法和步骤。,2020/5/30,4,实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：程序算法数据结构程序设计方法语言工具和环境在这4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的算法。算法是解决“做什么”和“怎么做”的问题。,2020/5/30,5,算法的表示,1、用自然语言表示算法采用汉语、英语或其它语言来描述解决问题的方法和步骤。由于自然语言容易出现“歧义性”，且描述问题的文字冗长，因此一般很少使用自然语言来描述算法。,2020/5/30,6,例1：有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩，算法可表示如下：S1：1iS2：读入学号ni和成绩giS3:如果gi80，则打印ni和gi，否则不打印S4：i+1iS5:如果i50,返回S2，继续执行；否则，算法结束。,2020/5/30,7,2、用流程图表示算法,（1）常用的流程图符号,2020/5/30,8,上例用流程图表示：,（1）流程图表示算法的优点：表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。简单，易于掌握。,流程图,2020/5/30,9,3、用NS图表示算法,1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框。,这种流程图又称NS结构化流程图。,NS流程图用以下的流程图符号：,（1）顺序结构：,A,B,2020/5/30,10,（2）选择结构：,P,成立,不成立,A,B,（3）循环结构：,当p1成立,A,当型循环结构,直到p1成立,A,直到型循环结构,用以上3种NS流程图中的基本框，可以组成复杂的NS流程图，以表示算法,2020/5/30,11,上例用NS图表示：,用NS表示算法如图,2020/5/30,12,4、用伪码表示算法,伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它不用图形符号，因此书写方便，格式紧凑，也比较好懂，便于向计算机语言算法（即程序）过渡。,例有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1表示第一个学生学号，ni表示第i个学生学号。用g表示学生成绩，gi表示第i个学生成绩。,2020/5/30,13,BEGIN(算法开始)1=iWhileiiEND（算法结束）,用伪代码表示算法如下：,2020/5/30,14,5、用计算机语言表示算法,设计算法的目的是为了实现算法。因此，不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。,我们的任务是用计算机解题，也就是要用计算机实现算法。计算机是无法识别流程图和伪代码的。只有用计算机语言编写的程序才能被计算机执行（当然还要经过编译成目标程序才能被计算机识别和执行）。因此，在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程序。,2020/5/30,15,例：有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1表示第一个学生学号，ni表示第i个学生学号。用g表示学生成绩，gi表示第i个学生成绩。,C语言程序如下：main()intg50,n50,i;for(i=0;i=80)printf(“%6d,%3dn”,ni,gi);,2020/5/30,16,例2：对一个大于或等于3的正整数，判断它是不是一个素数。,方法：将n(其中n3)作为被除数，将2到（n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。,简单的算法实例,2020/5/30,17,算法表示如下：S1：输入n的值S2：2i(i作为除数）S3:n被i除，得余数rS4:如果r等于0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5：i+1iS6:如果in-1,返回S3；否则，打印n“是素数”，算法结束。,2020/5/30,18,S1:1signS2:1sumS3:2denoS4:(-1)*signsignS5:sign*(1/deno)termS6:sum+termsumS7:deno+1denoS8:若deno100返回S4；否则算法结束。,例3：求1-1/2+1/31/4+1/991/100。,2020/5/30,19,结构化程序设计方法简介,1、三种基本结构回顾,（1）顺序结构,2020/5/30,20,(2)选择结构，或称分支结构,2020/5/30,21,(3)循环结构，它又称为重复结构，即反复执行某一部分的操作。又两类循环结构：,（a）当型（while型）循环结构,2020/5/30,22,(b)直到型（Until型）循环结构,2020/5/30,23,2、结构化程序,所谓结构化程序，就是仅仅使用顺序、选择、循环等三种基本结构所构造的程序。,3、结构化程序设计方法,结构化程序设计方法的基本思想是，把一个复杂问题的求解过程分阶段进行。每个阶段的问题都控制在人们容易理解和处理的范围内。,2020/5/30,24,1=i,i+1=i,gi80,i50,结束,开始,打印ni,gi,Y,N,N,Y,读入ni和gi,2020/5/30,25,解答：（）用自然语言表示（）用传统的流程图表示（）NS流程图（）用伪代码表示等。,1、算法的表示形式主要有哪些？,课堂练习,2020/5/30,26,2、设计算法：A、B两人各有一桶油，现两人要将各自桶内的油互换。,解答：必须借助另外一个空桶，并按如下算法进行：（用Si表示第i步操作，A的桶叫A，B的桶叫B，空桶叫M）开始：S1：将A桶中的油倒入M桶中；S2：将B桶中的油倒入A桶中；S3：将M桶中的油倒入B桶中；,2020/5/30,27,3、设计算法写出求n!的算法,解答：S1：给出n的值；S2:1=p;S3:2=i;S4:p*i=p;S5:i+1=i;S6:若i、=、!）,逻辑运算符（！、floatf=5.0,g=10.0;doubled=5.0,e=10.0;,则n的结果是10nm，nm，n*m，n/m，n%m的结果分别为13、7、30、3、1de，de，d*e，d/e的结果分别为15.0，5.0，50.0，0.5nmf*g/d的运算顺序相当于（nm（f*g）/d），结果是3.0nm*f*d的运算顺序相当于（nm）*f）*d，结果是25.0,如果参加运算的两个数中有一个为浮点型，则结果是double型,2增1减1运算符,（1）增1减1运算符的运算对象、运算规则与结果、结合性如下表所示：,对象数,单目,名称,运算符,运算规则,运算对象,运算结果,结合性,增1(前缀),先加1后使用,增1(后缀),减1(前缀),减1(后缀),先使用后加1,先减1后使用,先使用后减1,整型、字符型、指针型变量或数组元素,同运算对象的类型,自右向左,（2）增1减1运算符的优先级：,增1减1运算符优先于双目基本算术运算符增1减1运算符和单目运算符、同级别，结合性是自右向左,注意：,若出现难以区分的若干个或组成运算符串时，C语言规定，自左向右取尽可能多的符号组成运算符。,例1：,ab应理解为（a）bab应理解为（a）b,例2：增1减1运算符的使用,设变量定义如下：charc1b，c2B；（c1，c2可看成整型，其值分别为98，66）,则：c1的值是99，运算后c1的值是cc1的值是98，运算后c1的值是ac1c2的值是164，运算后c1的值是c，c2的值是Bc1c2的值是32，运算后c1的值是a，c2的值是B,三.赋值运算符,1.赋值运算符,赋值运算符是双目运算符，赋值运算符的左边必须是变量，右边是表达式。,(1)赋值运算符的运算对象及有关规则如下表：,(2)赋值运算符的优先级,算术运算符优先于关系运算符优先于双目逻辑运算符优先于赋值运算符赋值运算符的结合性是自右向左,(3)赋值运算符的使用,设变量定义如下：charc1a,c2；intn165，n2，n3，n4，n5，n6；floatf13.0，f2；,则：c2n1运算后，c2的值是65，n1的值不变。n2!c1运算后，n2的值是0，c1的值不变。f2f10.001运算后，f2的值是3.001，f1的值不变。n3c1n1|c1!n1运算后，n3的值是1，c1和n1的值不变。注：运算顺序相当于n3(c1n1)|(c1！n1)n4n5n6(n1)运算后，n4，n5，n6的值均是64，n1的值是64。,注意：上述表达式的值就等于赋值表达式中的最左边的变量值。,2.算术自反赋值运算符,(1)运算规则,对象数,名称,运算符,运算规则,运算对象,运算结果,结合性,双目,加赋值,减赋值,乘赋值,除赋值,模赋值,*,/=,%=,a+=b相当于a=a+(b),a=b相当于a=a(b),a*=b相当于a=a*(b),a/=b相当于a=a/(b),a%=b相当于a=a%(b),数值型,数值型,自右向左,整型,整型,（2）算术自反赋值运算符的优先级,算术运算符优先于关系运算符优先于双目逻辑运算符优先于算术自反赋值运算符算术自反赋值运算符和赋值运算符是同级别的，结合性是自右向左,（3）算术自反赋值运算符的使用,设变量定义如下intn1=10,n2=10,m1=10,m2=10,m3=10,m4=10;,则：n1n2，n1的值为20，n2的值不变n1n2，n1的值为0，n2的值不变n1*n2，n1的值为100，n2的值不变n1/n2，n1的值为1，n2的值不变m1m2m3*m4/2运算后，m1，m2，m3，m4的值依次是30，40，50，5。运算顺序相当于m1（m2（m3*（m4/2）,四.逗号运算符,逗号运算符是双目运算符，其运算对象是表达式。,1.逗号运算符,注意：由逗号运算符组成的式子也是表达式，其值等于最右边的表达式的值,2.逗号运算符的优先级,任何运算符优先于逗号运算符逗号运算符的结合性是自左向右,3.例题。设整型变量a，b为2，,则：ba3，cb4运算结果：a不变，b为5，c为9，表达式的值为9da，ed，fe运算结果：a为1，d为1，e为1，f为1，表达式的值为1,五.条件运算符,1.条件运算符,2.条件运算符的优先级,其它运算符优先于条件运算符优先于赋值、算术自反赋值运算符条件运算符的结合性是自右向左,3.例子,(1)设整型变量a，b，c，d均为2则ab？（c1）：（d0）；结果a，b，d不变，c为1，表达式的值为1,(2)a13？（ba2）：（ca3）；结果a，c不变，b为4，表达式值为4,(3)ab？（c0）：(ab？（c1）:（c1）)；结果a，b不变，c为0，表达式的值为0,1.长度运算符,六.长度运算符,2.长度运算符优先级,和单目算术运算符、单目逻辑运算符、增1减1运算符同级别,3.例子,设变量定义如下：intn；shorts；unsignedlongu3；floatf；charc；,则sizeof（n）的值是2sizeof（s）的值是2sizeof（long）的值是4sizeof（unsignedint）的值是2sizeof（u3）的值是4sizeof（f）的值是4sizeof（double）的值是8sizeof（c）的值是1,注意：上述结果是TurboC2.0在微机上运行的结果。,2020/5/30,79,七位运算C语言中提供的位运算符：、（这是赋值语句）a+（这是表达式)a+;（这是赋值语句，等价与a=a+1;）,2020/5/30,89,3.5输入输出在C语言中的实现,1.输入输出的概念从计算机向外部输出设备（如显示屏、打印机、磁盘等）输出数据称为“输出”，从外部向输入设备（如键盘、磁盘、光盘、扫描仪等）输入数据称为“输入”。,2.C语言本身不提供输入输出语句，输入和输出操作是由函数来实现的。在C标准函数库中提供了一些输入输出函数，例如，printf函数和scanf函数。,2020/5/30,90,3.在使用C语言库函数时，要用预编译命令“include”将有关的“头文件”包括到用户源文件中。在调用标准输入输出库函数时，文件开头应有以下预编译命令：#include或#include“stdio.h”,4.允许在使用printf和scanf两个函数时可不加#include命令。,2020/5/30,91,一、字符数据的输入输出,1.putchar函数（字符输出函数）函数格式：putchar(C);C可以是字符型变量或整型变量或常量函数的功能：向终端输出一个字符,2020/5/30,92,2.程序实例#includemain()chara,b,c;a=B;b=O;c=Y;putchar(a);putchar(b);putchar(c);,注意：该程序可以输出控制字符，如putchar(n)输出一个换行符，也可以输出其他转义字符如putchar(101)（输出字符A）putchar()（输出单引号字符）,运行结果：BOY,2020/5/30,93,3.getchar函数（字符输入函数）函数格式，getchar()函数的功能：从终端输入一个字符，函数的值就是从输入设备得到的字符。,4.程序实例#includemain()charc;c=getchar();putchar(c);在运行时，如果从键盘输入字符a并按回车键，就会在屏幕上看到输出的字符a。a（输入a后，按“回车”键，字符才送到内存）a（输出变量c的值a）,2020/5/30,94,注意：（1）getchar()只能接收一个字符，getchar函数收到的字符可以赋给一个字符变量或整型变量。（2）若在程序中调用getchar、putchar函数，则必须在程序的开头部分加上“包含命令”#include或#include“stdio.h”,2020/5/30,95,二、格式输入与输出,（一）、printf函数（格式输出函数）,1.printf函数的一般格式为printf（“格式控制字符串”，输出表列）括弧内包括两部分：（1）“格式控制字符串”是用双引号括起来的字符串，也称“转换控制字符串”，它包括两种信息：格式说明，由“”和格式字符组成，如%d,%f等。它的作用是将输出的数据转换为指定的格式输出。格式说明总是由“”字符开始的。普通字符，即需要原样输出的字符。（2）“输出表列”是需要输出的一些数据，可以是表达式。,2020/5/30,96,下面是一个例子：printf(“%d%d”,a,b);,格式说明输出表列,printf(“a%db=%d”,a,b);,格式说明输出表列,2020/5/30,97,2.格式字符常用的有以下几种格式字符：,（1）d格式字符。用来输出十进制整数。有以下几种格式字符：d，按整型数据的实际长度输出。md，m为指定的输出字段的宽度。如果数据的位数小于m，则左端补以空格，若大于m，则按实际位数输出。如printf(“%4d,%4d”,a,b);若a123，b12345，则输出结果为|_|123，12345ld，输出长整型数据。如longa=135790;printf(“%ld”,a);,2020/5/30,98,对long型数据应当用ld格式输出。对长整型数据也可以指定字段宽度，如将上面printf函数中的“ld”改为“8ld”则输出为：|_|_|135790（8列）一个int型数据可以用d或ld格式输出。,（2）O格式符，以八进制数形式输出整数。由于是将内存单元中的各位的值（0或1）按八进制形式输出，因此输出的数值不带符号，即将符号位也一起作为八进制数的一部分输出。例如：inta=-1;printf(“%d,%o”,a,a);,2020/5/30,99,1111111111111111输出为1，177777对长整型数（long型）可以用“lo”格式输出。同样可以指定字段宽度，如printf（“8o”，a）输出为|_|_|177777,1在内存单元中的存放形式（以补码形式存放）如下：,2020/5/30,100,（3）x格式符，以十六进制数形式输出整数。同样不会出现负的十六进制数。例如inta=1;Printf(“%x,%o,%d”,a,a,a);,输出结果为：ffff，177777，1,2020/5/30,101,（4）u格式符，用来输出unsigned型数据，即无符号数，以十进制形式输出。,（5）c式符，用来输出一个字符。如：charc=a;printf(“%c”,c);输出字符a，请注意：“c”中的c是格式符，引号右边的c是变量名,不要搞混。一个整数，只要它的值在0255范围内，也可以用字符形式输出,在输出前，系统会将该整数作为ASCII码转换成相应的字符；反之,一个字符数据也可以用整数形式输出。,2020/5/30,102,(6)S格式符，用来输出一个字符串。有几种用法：,s，例如：printf(“%s”,“CHINA”);输出“CHINA”字符串（不包括双引号）。,ms，输出的字符串占m列，如字符串本身长度大于m，则突破m的限制，将字符串全部输出。若串长小于m，则左补空格。,2020/5/30,103,ms，如果串长小于m，则在m列范围内，字符率向左靠，右补空格。,mns，输出占m列，但只取字符串中左端n个字符。这n个字符输出在m列的右侧，左补空格。,mns，其中m、n含义同上，n个字符输出在m列范围的左侧，右补空格。如果nm，则m自动取n值，即保证n个字符正常输出。,2020/5/30,104,（7）f格式符，用来输出实数（包括单、双精度），以小数形式输出。有以下几种用法：,m.nf指定输出的数据共占m列,其中有n位小数。如果数值长度小于m，则左端补空格。,-mnf与m.nf基本相同，只是使输出的数值向左端靠，右端补空格。,f，不指定字段宽度，由系统自动指定，使整数部分全部如数输出。并输出6位小数。应当注意，并非全部数字都是有效数字。单精度实数的有效位数一般为7位。,2020/5/30,105,(1)字符数据的输出：main()charc=a;inti=97;printf(“%c,%dn”,c,c);printf(“%c,%dn”,i,i);,运行结果为：a,97a,97,3.例子,2020/5/30,106,(2)字符串的输出main()printf(“%5s,%7.2s,%.4s,%-5.3sn”,”CHINA”,”CHINA”,“CHINA”,”CHINA”);输出如下：CHINA,|_|_|_|_|_|CH,CHIN,CHI|_|_|其中第3个输出项,格式说明为“%.4s”，即只指定n,没指定m,自动使m=n=4，故占4列。,2020/5/30,107,(3)输出实数时的有效位数：main()floatx,y;x=111111.111;y=222222.222;printf(“%f”,x+y);,运行结果为：333333.328125,2020/5/30,108,(4)输出实数时指定小数位数：main()floatf=123.456;printf(“%f|_|_|%10f|_|_|%10.2f|_|_|%.2f|_|_|%-10.2fn”,f,f,f,f,f);,运行结果为：123.456001|_|_|123.456001|_|_|_|_|_|_|123.46|_|_|123.46|_|_|123.46|_|_|_|_|,2020/5/30,109,4.格式符小结,printf格式字符,2020/5/30,110,2020/5/30,111,printf的附加格式说明字符,2020/5/30,112,5.使用printf函数时，还需注意以下几点,（1）除了X，E，G外，其他格式字符必须用小写字母，如d不能写成D。（2）可以在printf函数中的“格式控制”字符串内包含“转义字符”，如“n”,“t”,“b”,“r”,“f”,“377”等。（3）上面介绍的d、o、x、u、c、s、i、e、g等字符，如用在“”后面就作为格式符号。一个格式说明以“”开头，以上述9个格式字符之一为结束，中间可以插入附加格式字符（也称修饰符）。例如：,2020/5/30,113,printf(“c=%cf=%fs=%s”,c,f,s);,格式说明,第一个格式说明为“c”而不包括其后的f，第二个格式说明为“f”，不包括其后的S，第三个格式说明为“s”。其他的字符为原样输出的普通字符。,（4）如果想输出字符“”，则应该在“格式控制”字符串中用连续两个表示，如printf(“%f%”,1.0/3);输出：0.333333%,2020/5/30,114,（二）、scanf函数（格式输入函数）,1.一般形式scanf（“格式控制字符串”，地址表列）“格式控制字符串”的含义同pr