资源描述
0,程序设计基础,C语言,程序设计基础,第2章程序的灵魂-算法,2,第2章程序的灵魂-算法,2.1算法的概念2.2算法的特性2.3算法的描述,3,2.1算法的概念,算法是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。,对于同一个问题可以有不同的解题方法和步骤，也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，既运算快、内存开销小的算法（算法的时空效率）。,4,2.2算法的特性,1.有穷性：一个算法应当包含有限的步骤；算法在执行时不能出现死循环。,2.确定性：算法中的每一个步骤都应当是确定的，不应产生歧义。,3.有0个或多个输入所谓输入是指算法执行时从外界获取必要信息。,4.有1个或多个输出算法必须有结果，没有结果的算法没有意义。,5.有效性算法的每个步骤都应当能有效执行，并能得到确定的结果。,5,2.3算法的描述,常用的算法表示方法：自然语言，传统流程图，结构化流程图（N-S流程图），伪代码、计算机语言等。,流程图：用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算法流程,常用的流程图符号：,起始框,输入输出框,判断选择框,处理框,流程线,连接点,注释框,例：求5！,t=1,i=2,t=t*i,i=i+1,i5,结束,y,n,开始,输出t,三种基本结构的流程图,1.顺序结构：按指令的顺序依次执行2.判断选择结构：根据判别条件有选择地改变执行流程3.循环结构：有条件的重复地执行某个程序块,只有一个入口。只有一个出口。结构中的每一部分都有机会被执行到。（没有“死语句”）结构内不存在“死循环”（无终止的循环）,三种基本结构，有以下共同点：,已经证明：由三种基本结构顺序组成的算法结构，可以解决任何复杂问题。由基本结构组成的算法属于“结构化”算法。,10,用N-S流程图表示算法,基本结构的顺序组合可以表示任何复杂的算法结构全部算法写在一个矩形框内，完全去掉了带箭头的流程线。这种流程图称为N-S结构化流程图(盒图)。N-S流程图适于结构化程序设计.,11,顺序结构程序设计,执行a块,执行b块,依次顺序执行程序语句,先执行a操作，再执行b操作,12,选择结构程序设计,满足条件否,满足,不满足,执行a块,执行b块,当条件成立，执行a操作，否则，执行b操作。,13,循环结构程序设计,循环又分“当型循环”和“直到型循环”,当条件p满足时,执行循环中指令,直到条件p满足为止,执行循环中的指令,当型循环先判断，再决定是否执行循环体，所以在条件p一次都不满足时，循环体可能一次都不执行,直到型循环先执行循环体，然后再判断条件p，所以循环体至少执行一次。,14,用伪代码表示算法,伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡,用计算机语言表示算法,用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。程序是程序设计的最终产品，需要经过每一步的细致加工才能得到，对于大型程序,不提倡一开始就编写程序。,15,i=1,count=0,输入n,当in,n%i=0?,Yes,N0,count加1,i加1,count2?,Yes,N0,输出n不是素数,输出n是素数,N-S图：判断n是否为素数。,程序设计基础,第3章数据类型、运算符与表达式教师：杨振平E-mail:zpyang,3.1C的数据类型,数据类型,基本类型,构造类型,指针类型(),空类型(void),字符型(char),数值类型,枚举类型(enum),数组类型(),结构体类型(struct),共用体类型(union),整型(short,int,long,unsigned),实型,单精度型(float),双精度型(double),18,3.2常量与变量,常量的分类:1）整型常量（如12、0、-3为整型常量）2）实型常量（4.6、-1.23为实型常量）3）字符常量（a、d字符常量）4)字符串常量（”A”、“Hello,C”字符串常量)5）符号常量（具有含义清楚、见名知意、修改方便的优点）。如：#definePI3.1415926,常量程序运行过程中不能被改变的量。,19,变量:在程序运行过程中，其值可以被改变的量,变量与内存单元相联系。程序中它用来存取数据。每个变量都必须有一个名字变量名。变量名的构成与标识符构成相同。,变量命名的规定：语言规定标识符只能由字母、数字和下划线三种字符组成，且第一个字符必须为字母或下划线。例：sum，_total,month,Student_name，lotus_1_2_，BASIC,li_lingM.D.John,￥123,3D64,ab,变量遵循“先定义，后使用”的原则,20,3.3整型数据,1整型常量,整型常量即整常数。整常数有三种表示形式：1）十进制；2）八进制；以0头的数是八进制数。3）十六进制以0 x开头的数是16进制数。,2.整型变量,整型数据在内存中的存放形式（二进制）,根据占用内存字节数的不同，整型变量又分为类：,1）基本整型（类型关键字为int）。2）短整型（类型关键字为shortint）。3）长整型4）无符号整型。（类型关键字为unsignedint）。,21,整数在内存中存放形式：,22,整型变量的分类：,注意：括号表示其中的内容是可选的。,六种,有符号基本整型有符号短整型有符号长整型无符号基本整型无符号短整型无符号长整型,(signed)int(signed)short(int)(signed)long(int)unsignedintunsignedshort(int)unsignedlong(int),23,整数类型数据的特征,类型类型说明符长度数的范围基本型int2字节-3276832767短整型short2字节-215215-1长整型long4字节-231231-1无符号整型unsigned2字节065535无符号短整型unsignedshort2字节065535无符号长整型unsignedlong4字节0（232-1）,24,整型变量的定义,变量说明的一般形式为：类型说明符变量名标识符，变量名标识符，.;,inta,b,c;(a,b,c为整型变量)longx,y;(x,y为长整型变量)unsignedintp,q;(p,q为无符号整型变量),25,例3.3整型数据的溢出#includevoidmain()shortinta,b;a=32767;b=a+1;printf(“%d,%dn”,a,b);,说明：数值是以补码表示的。一个整型变量只能容纳-3276832767范围内的数，无法表示大于32767或小于-32768的数。遇此情况就发生“溢出”。,运行结果：32767,-32768,26,3.4浮点型数据,1.浮点型常量的表示方法,两种表示形式,小数指数,0.1233e-3,注意:字母e(或E)之前必须有数字，且e后面的指数必须为整数：,1e3、1.8e-3、-123e-6、-.1e-3e3、2.1e3.5、.e3、e,27,3.4浮点型数据（续）,2.浮点型变量(1)浮点型数据在内存中的存放形式,28,(2)浮点型变量的分类浮点型变量分为单精度（float型）、双精度（double型）和长双精度型（longdouble）三类形式。,3.4浮点型数据（续）,29,例3.4浮点型数据的舍入误差#includevoidmain()floata,b;a=123456.789e5;b=a+20;printf(“%fn”,b);,说明：一个浮点型变量只能保证的有效数字是7位有效数字，后面的数字是无意义的，并不准确地表示该数。应当避免将一个很大的数和一个很小的数直接相加或相减，否则就会“丢失”小的数,运行结果：12345678868.000000,30,3.5字符型数据,1.字符常量(1)用单引号包含的一个字符是字符型常量(2)只能包含一个字符,例,a,A,1abc、“a”,31,字符型数据:,字符常量:用一对单引号括起来的单个字符,转义字符:是以反斜杠“”开头的。,字符变量:char，一般占用1字节内存单元。,C语言中的字符变量可以存储字符数据(实际为该字符的ASCII码值）和整型数据；字符数据也能进行整数运算；字符数据可以按字符输出也能按整数输出。例：charch=A;printf(”%d,%cn”,ch,ch);结果：65,A,32,转义字符表:,字符形式,n,t,v,b,r,f,ddd,xhh,功能,换行,横向跳格(即跳到下一个输出区),竖向跳格,退格,回车,走纸换页,反斜杠字符“”,单引号(撇号)字符,1到3位8进制数所代表的字符,1到2位16进制数所代表的字符,33,例3.6向字符变量赋以整数。#includevoidmain()charc1,c2;c1=97;c2=98;printf(“%c%cn”,c1,c2);printf(“%d%dn”,c1,c2);,说明：在第和第4行中，将整数和分别赋给c1和c2，它的作用相当于以下两个赋值语句：c1；c2；因为a和b的ASCII码为和,运行结果：9798,34,例3.7大小写字母的转换#includevoidmain()charc1,c2；c1=a;c2=b;c1=c1-32;c2=c2-32;printf(“cc，c1,c2）；,说明：程序的作用是将两个小写字母a和b转换成大写字母A和B。从代码表中可以看到每一个小写字母比它相应的大写字母的码大。语言允许字符数据与整数直接进行算术运算。,运行结果：,35,字符串常量,字符串常量是用一对双引号括起来的若干字符序列。,C语言规定：在存储字符串常量时，由系统在字符串的末尾自动加一个0作为字符串的结束标志。,a是字符常量，而”a”是字符串常量。,不能将一个字符串赋给一个字符变量。,C中没有字符串变量，需要用字符数组存放字符串。,C规定，可以在定义变量的同时给变量赋初值。,36,3.6变量赋初值,(1)语言允许在定义变量的同时使变量初始化。如:inta=3;/指定为整型变量，初值为floatf=3.56;/指定为浮点型变量，初值为.56charc=a;/指定为字符变量，初值为a,37,各类数值型数据间的混合运算,整型、单精度型、双精度型数据可以混合运算。不同类型的数据要先转换成同一类型，然后进行运算。转换规则如图：,38,3.8C运算符简介,运算符：狭义的运算符是表示各种运算的符号。C语言提供丰富多彩的运算符，可以构造灵活多样的表达式：如常见的算术、关系、逻辑运算符、赋值运算符、位操作运算符、自增自减运算符等。另外，数组下标，函数调用都作为运算符。,39,运算符类别,40,C中各类运算符的优先级：,初等运算符()、,单目运算符！、+、+、(类型),算术运算符、/、%，+、,关系运算符、=，=、!=,逻辑运算符c1=n%10；c2=n/10%10；c3=n/100%10；c4=n/1000；n=c1*1000+c2*100+c3*10+c4,43,算法2：将n的每位数字转换为字符，反序输出各个字符,unsignedintn;charc1,c2,c3,c4;c1=n%10+0；c2=n/10%10+0；/分离十位数字字符c3=n/100%10+0；/分离百位数字字符c4=n/1000+0；/分离千位数字字符输出c1,c2,c3,c4,44,3.8算术运算符和算术表达式（续）,(2)基本算术表达式:用算术运算符和括号将运算对象(也称操作数）连接起来的、符合语法规则的式子，称为算术表达式。运算对象包括常量、变量、函数等。例如:*.5a是一个合法的表达式。,（3）运算符的优先级和结合性：在表达式求值时，先按运算符的优先级别高低次序执行，例如先乘除后加减。算术运算符的结合方向为“自左至右”，即先左后右。,45,强制类型转换,强制转换是通过类型转换运算符来实现。一般形式：（类型说明符）表达式功能：把表达式的结果强制转换为类型说明符所表示的类型。,(int)a将a的结果强制转换为整型量。(int)(x+y)将x+y的结果强制转换为整型量。(float)a+b将a的内容强制转换为浮点数，再与b相加,无论隐式转换，强制转换都是临时转换，不改变数据本身的类型和值。,46,3.8算术运算符和算术表达式（续）,(4)自增、自减运算符（+、-）作用是使变量的值增或减。如：，（在使用之前，先使的值加（减），（在使用之后，使的值加（减）,47,3.8算术运算符和算术表达式（续）,例如：inti=4,j;；i的值先变成4,再赋给,j的值均为；先将i的值3赋给,的值为，然后变为,注意：(1)自增运算符（），自减运算符（），只能用于变量，而不能用于常量或表达式，(2)和的结合方向是“自右至左”。,如：inta=-2;b;b=-a+;a,b=?,48,3.9赋值运算符和赋值表达式,符号“=”为赋值运算符。赋值表达式：变量名=表达式,2.整型数据赋给实型变量,数值不变,但按实数形式存放.floatb;b=5/3;b=?,将实型数据(无论单,双精度)赋给整型变量时,舍弃小数.inta;a=3.14;a=?,赋值时,两边类型若不一致,则按以下规则转换:,49,4.将intlongint,进行符号扩展。即:符号扩展,低16位long的低16位。,5.longintint则高16位截断。,3.字符型数据赋给整型变量时:,(2)字符带符号整型变量,则字符高位扩展。,(1)字符无符号整型变量,则存入低8位,高8位补零。,50,6.将unsignedint型longint高位补0。,原值传送,但数据大小不能超值。如:unsignedinta=65535;intb;b=a;则越界。,而位数相同部分赋值unsignedintintunsignedlonglongunsignedshortshort,51,7.非unsigned型长度相同的unsigned型数据,原样传送(包括符号位),一、复合赋值运算符：在号之前加一个其它运算符。,C语言规定:凡是二目运算符均可构成复合赋值运算符。,例:a+=3;相当于a=a+3x=y+8;相当于x=x(y+8)x%=3;相当于x=x%3,52,一般形式:,二、赋值表达式,例:x=10为一赋值表达式其中又可以是一个赋值表达式。,例:x=(y=10)相当于y=10；x=y由于赋值号为右结合性,于是()可省略，即为：x=y=10；,53,例:a+=a=aa(设a12),进一步,还可用复合赋值运算符作下列运算：,步骤:aa144.a=aaa=aaa=12144=132a+=132a=a+(132)=264,54,3.10逗号运算符和逗号表达式,一般形式:表达式1,表达式2,表达式3,表达式n,其计算规则:先计算表达式1,再计算表达式2,.最后值为表达式n的值。,例:a=35,a4则:先计算35,a15,a4=60,结果为60。,55,又如:(a=35,a4),a+5,扩展形式：表达式1,表达2,表达式n,结果为20(作为逗号表达式的值),a+5a即20a.,35=15a,a4=60(此时a值仍未变),结果为表达式n的值,56,注意:x=(a=3,63)赋值表达式,x18;,x=a=3,6a逗号表达式,x3.,逗号表达式主要用于某些语句中需一次计算多个表达式值的情况。如在循环语句中。,函数调用中的实参之间虽然用的是逗号间隔,但不是逗号表达式。如:printf(%d,%d,%d,a,b,c);,57,例3-3：找零钱问题,假定有伍角、壹角、伍分、贰分和壹分共五种硬币，在给顾客找硬币时，一般都会尽可能的选用硬币个数最少的方法。例如，当要给某顾客找七角二分钱时，会给他一个伍角，2个壹角和1个贰分的硬币。请编写一个程序，输入的是要找给顾客的零钱（以分为单位），输出的是应该找回的各种硬币数目，并保证找回的硬币数最少。,58,算法：,intchange;/定义存放零钱的变量intwj,yj,wf,ef,yf;/定义存放5种硬币个数的变量输入changewj=change/50;change%=50;/5角硬币数yj=change/10;change%=10;/1角硬币数wf=change/5;change%=5;/5分硬币数ef=change/2;/2分硬币数yf=change%2;/1分硬币数输出：wj,yj,wf,ef,yf;,59,输入一个5位正整数，按要求完成：（1）分别取出高端2位数、低端2位数以及中间1位数，并按照中、低、高次序输出，输出格式如下示例。（2）以中间数作为最高位（万位），低端数作为千位和百位，高端数作为十位和个位，形成一个新的5位整数，并输出。示例：输入：12345输出：中间数：3，低端数：45，高端数：12新的数：34512,例3-4：变换整数,
展开阅读全文