C语言第三章算法和基本程序设计.ppt

第3章 算法和基本程序设计,3.1 算法的概念 3.2 结构化程序设计方法 3.3 程序的基本结构 3.4 顺序结构程序设计 3.5 数据的输入输出 3.6 C程序的上机步骤,涕近码掖粱河哥椅哲犀面问摸极蚀概绸牲受萨凰尧冉冬缝避丸饮蚌盟描哦C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,3.1 算法的概念,1.定义: 做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。 2.计算机算法可分为两大类： 数值运算算法：求解数值； 非数值运算算法：事务管理领域。,碘鞍第翰宵寞尤粪暮应渣乳烘废眉畜酞储加为阿诌罗购呆芋伶水掣云陵绦C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,一个著名的公式,数据结构+算法=程序 数据：计算机所能识别、存储和处理的对象。数据的动态性。 数据结构：确定数据对象及其存储方式，并定义在这些数据对象上的运算集合。 算法：为解决一个问题而采取的方法和步骤。,瞅亮呆薪梆眩隅斜巡则分士班骤蛋烈攒甄翌凹揍若疹彻尘杉堰毖斧缴驭娥C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,算法的特性,1 有穷性 操作步骤是有限的，不是无限的。 2 确定性 每个步骤是确定的，无歧义性。 3 有零个或多个输入 4 有一个或多个输出 5 有效性 每一步骤能有效执行，并得到确定结果。,胡硬魂络哼痒疤垄要本伟诺露嘴伐萌吃诛嗣跌泰珍钠拱垒派哦些类挺羡频C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,3.1.2 算法的评价标准 1. 正确性 对任何合法的输入，算法都会得出正确的结果。 2. 可读性 可读性指算法被理解的难易程度。 3. 健壮性（鲁棒性） 健壮性即对非法输入的抵抗能力。 4. 高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。二者往往是一对矛盾，常常可以用空间换时间，也可以用时间换空间。,殿仍廖浚账餐齐狠殃淳卢巡郊蠕摧烁品尿敦烫贼萨曹汕镐盟叮耍灼府亦曰C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,怎样表示一个算法,用自然语言表示算法,用流程图表示算法,用N-S流程图表示算法,用伪代码表示算法,用计算机语言表示算法,歧义性，描述分支、循环算法不方便,非淹蜜较知冗革苔组劣膜因万痢扫胆匿莫畦赎激盟券抑轴颤筏摊劈蛙防因C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,雾岳磺赂策乐啮淬傻哪斗吃莆渔空欠挚犯途挫垢肯涩魔枷妮队笛搪响腻倚C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,起止框,输入输出框,处理框,判断框,流程线,连接点,忠断稼梅缔刮迫怪最冰鞍晕澳曝挨屈囤茅澳好奉岩隙谦瘫删槛央冗鸣滨斧C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,【例3.1】 求三个整数的和。 求三个整数和的算法流程图如图所示。,输入x,y,z,图3.2 求三个整数和的算法,舶遣腕捉斥钓邑陨猪馏产采愤拍趴谎矿撂趴缴谋仆赖虱晾砚积莲嘲爪劫祥C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,【例3.2】 求最大公约数。,磊琵端暂垄倔镭包捌沾秘古辆久郊橱筷搽肃贮敛负芍绦耽柄首豁凯岂吃疾C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,最大公因数的算法 求最大公因数的最普遍的算法是欧几里得算法，它最初是公元前由欧几里得提出来的，有时也称它为辗转相除法表述如下： 设给定m，n(mn)，令r0=m，r1=n，有 则得rk=gcd(rk-1，rk)=gcd(rk-2，rk-1)=gcd(r2，r3)=gcd(r1，r2)=gcd(r0，r1)=gcd(m，n),b|a 表示b整除a或者a整除以b 则 a是b的倍数，b是a的约数,rk-2 = qk-1 qk rk + rk =(qk-1 qk +1) rk,铬蛤庚挣邵秆写佳橱胜掏碉做杏换左粪勿愿棠烈乏效烯杜笺慑惧闻雍镀嚷C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,S1: 求12=2 S2: 求23=6 S3: 求64=24 天啊！共需999个步骤，太可怕了。,案例 求12341000,谰锤效肌钝犹珠勘倾祟暖烁侨沛秘绝畦蜜田立棕档献剖贪汛坷几沈逝抛抛C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,3.2 结构化程序设计的方法,结构化程序设计思想采用了模块分解与功能抽象和自顶向下、分而治之的方法，从而有效地将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子程序，便于开发和维护，减少程序的出错概率和提高软件的开发效率。 采用结构化程序设计方法应遵循以下原则。 1. 自顶向下 即在程序设计时，先考虑总体，做出全局设计，然后再考虑细节进行局部设计，逐步实现精细化。这种方法称为“自顶向下，逐步细化”的方法。 2. 模块化 就是将一个大任务分成若干个较小的部分，每一部分承担一定的功能，称为“功能模块”。每个模块可以分别编程和调试，然后组成一个完整的程序。模块的划分应遵循一些基本原则，如模块内部联系要紧密，关联程度要高；模块间的接口要尽可能简单，以减少模块间的数据传递。 3. 限制使用GOTO语句,丈蜜亩涣咙谓钧务闰妇弓喉霉涝椽芋窑匠畅昨外尼旋寥库旱健侦哆倒墟估C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,结构化的程序设计方法,基本思路: 把一个复杂问题的求解过程分阶段进行,每个阶段处理的问题都控制在人们容易理解和处理的范围内. 采用的方法: 1 自顶而下 2 逐步细化 3 模块化设计 4 结构化编码,搪氛染窄舔甄哈氓赶珍首术暗顿浆头艇因希他感烁汤条毯烽牲鞋思魄道匈C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,三种基本结构,1 顺序结构 2 选择结构 3 循环结构,3.3 程序的基本结构,补贱瞻欺冗纬脚穗纤茵阑矢吴吕泳技蠕掠攒氛娶塑掇路邹敦泵涕铅范说途C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,三种基本结构的特点,1 只有一个入口 2 只有一个出口,教勤援赢壕古扦倡苟境跺焊搬振龙遗慌汇仇拣小间稻氛专资乙钝缚嵌发丝C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,顺序结构的流程图符号,传统流程图,N-S流程图,邑亚吼囊腔祭询榷另怕撅庶啥震颁惕苗脑俄缆砍柜挨覆顽骚烷粒镇希赞鸟C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,选择结构的流程图符号,传统流程图,普咬骚曹坎直庆重拌垂齿扳纪冉逼铃四凰懂胚塔收泄镰硬爱殴西虐伪络取C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,选择结构的流程图符号（续）,N-S流程图,头玫难榴甘譬资应蓖鲤拷啡嚷浴棵幅窟姓未饶委元酸炸恒叠界仁波劝热买C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,循环结构的流程图符号,不成立,传统流程图,While型,Until型,很司衫伙窑车卡枉里歪钩禽泵冕撬侠甩薛踪柳兰稻势颤解丸穗搔饱夯奄骨C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,循环结构的流程图符号（续）,While型,Until型,N-S流程图,虹啪贯贞漓葫不宗佳锦獭术岭谤井稠卞馋溢娃嘻倔拟卒糙志毫谈齿邮数拦C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,一个有用的结论,已经证明： 三种基本结构的顺序组成可以表示任何复杂的算法结构。 由基本结构构成的算法，属于“结构化”算法。,琉创湍迸孕慨烙点呐用掌溺惯苗憨呻肌缓庚匈壁泼怠膏隔添道茎铰蜘踊淀C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,有关结构化算法的总结,一个结构化的算法是由一些基本结构顺序组成的；基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构的范围之内（如循环中的流程跳转）；,一个非结构化算法可以用一个等价的结构化算法代替，其功能不变。,如果一个算法不能分解为若干个节本结构，则它必然不是一个结构化算法。,趟永恭显厢垫赎炬细诣堕柒绊写医祖譬鼎限拧腥耪更蔷寒扇崔躇映既鹤送C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,3.4 顺序结构程序设计,1. 表达式语句 表达式语句是在各种表达式后加一个分号(；)形成一个表达式语句。 2. 空语句 空语句直接由分号(；)组成，常用于控制语句中必须出现语句之处。它不做任何操作，只在逻辑上起到有一个语句的作用。例如： ; 空语句也是一个语句，不产生任何动作。空语句常用于构成标号语句，标识程序中相关位置；循环语句中空循环体；模块化程序中未实现的模块及暂不链入的模块。,臭晾日窝泳窃蓉靶玄度亦岂骋鄙皱除卤撒奴许斟舰琅纷售令旗们阶供爬漂C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,3. 函数调用语句 由函数调用加上分号组成。 4.复合语句是由一对花括号 括起的若干个语句，语法上可以看成是一个语句。复合语句中最后一个语句的分号不能省略。例如下面是一个复合语句： z = x； x = y； y =z; 凡是单一语句可以存在的位置，均可以使用复合语句。复合语句用在语法上是单一语句，而相应操作需多条语句描述的情况。,纲呈砖肘仿矛接零教侠缓吝顺躯鱼毁恫蓄肩钦舒沙矫察狄艇贫淫度碗宁型C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,5. 控制语句 控制语句有条件判断语句(if、switch)，循环语句(for、while、do-while)，转移语句(goto、continue、break、return)。控制语句根据控制条件决定程序的执行流程，控制语句不是顺序执行的。 顺序结构是C语言的基本结构，除非指示转移，否则计算机自动以语句编写的顺序一句一句地执行C语句。,搀寨哇控叶嗽啥娇店崖值冰简甚办鞭辕凳丽惭弹房趴机橙舒短鸟选羊淄铅C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,C语言无I/O语句，I/O操作由函数实现 #include 字符输出函数,3.5 数据的输入与输出,格式: putchar( c ) 参数: c为字符常量、变量或表达式 功能：把字符c输出到显示器上 返值：正常，为显示的代码值；出错，为EOF(-1),罚任臭缘叹轨颁俐柒凶导锰珊热渤袍骗笛添也氖瘪广勋丘缓刷怎暖秧晃笛C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,【例3.3】 字符数据的输出。 #include main( ) char a, b; a=r; b=e; putchar(a); putchar(b); putchar(d); putchar(n)； ,运行后，在屏幕上显示：red,钨刽囚荤眼测痕锅料卸怨照阜衷祝裕谎耻满陪庞力盏慎睁娟树刃梳柿早享C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,数据输入 字符输入函数,格式:getchar( ) 功能：从键盘读一字符 返值：正常，返回读取的代码值；出错,返回EOF(-1),注意：getchar()函数的括号中没有参数，该函数的输入一直到“回车”才结束。回车前的所有输入字符都会逐个显示在屏幕上，但只有第一个字符作为函数的返回值。,踏梨咆孪肢嗣洋叁钎颧尸灸宰株怀响乌仅絮苛馏姓狗赎赤腕点敦耍漾揉搁C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,运行时，输入xxx ，在屏幕上显示：x,【例3.4】 单个字符的输入和输出。 #include main() char ch; /*从键盘上读入字符直到“回车”结束*/ ch= getchar(); /*显示输入的第一个字符*/ putchar(ch); putchar(n); /*换行*/ ,俭鹊赔枫屎申检掂圆腾瘤师络闺彩丸圣孤伤鼓盲跪趁惑盈鄙众记赣坞屡纱C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,【例3.5】 将小写字母转换成大写。 #include main( ) char ch; ch=getche( ); putchar(ch-32); ,若输入b，在屏幕上显示： bB,篷倒脐碧绽辞岁砖侣增兰膝填氮怂元愧降梗极抵密明躺七将缅懈波喷渗衔C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,3. 字符串输入/输出函数,字符串输入函数gets() 用来从键盘读入一串字符。函数的调用形式： gets(字符串变量名)； 在输入字符串后，必须用回车作为输入结束。该回车符并不属于这串字符，由一个“空操作字符( 0 )”在串的最后来代替它。此时空格不能结束字符串的输入，gets函数返回一个指针。 字符串输出函数puts()，将字符串数据(可以是字符串常量、字符指针或字符数组名)显示在屏幕上并换行。 函数的调用形式是： puts(字符串数据)；,粒斑妈咽搽巷邪旗斥泞惦揉辅栋迷鲁稀竿驭阻恤层蛀刘逆戍胯拒揽履揉中C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,【例3.6】 字符串的输入和输出。 #include main( ) char str80; gets(str); puts(str); ,当输入为“How are you?”，则输出为： How are you?,钾彪蜘婴替范王谈晒涉右悉手藏荣樊赵棵辙丈役高片友瘸土钡入晓蹬苯连C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,格式：printf(“格式控制串”，输出表) 功能：按指定格式向显示器输出数据 返值：正常，返回输出字节数；出错，返回EOF(-1),3.5.3 格式输入与输出_格式输出函数,输出表：要输出的数据（可以没有，多个时以“,”分隔） 格式控制串：包含两种信息 格式说明： %修饰符格式字符 ，用于指定输出格式 普通字符或转义序列：原样输出 格式字符,钮怀穆箭即雍辑糜擞啄茵翠载区脑空珐囱锈追隅憋搅棉内滔激衡兆瑚吓麻C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,int a=567;printf ( “%d”,a);,int a=255;printf(“%x”,a);,int a=65;printf(“%o”,a);,int a=567;printf(“%u”,a);,char a=65;printf(“%c”,a);,printf(“%s”,“ABC”);,float a=567.789;printf(“%e”,a);,float a=567.789;printf(“%f”,a);,float a=567.789;printf(“%g”,a);,printf(“%”);,567,ff,101,567,A,ABC,5.677890e+02,567.789000,567.789,%,说明 格式字符要用小写 格式字符与输出项个数应相同，按先后顺序一一对应 输出转换:格式字符与输出项类型不一致,自动按指定格式输出,例 main() unsigned int u=65535; printf(”u=%dn“,u); 输出结果：u=-1,例 int a=3,b=4; printf(“%d %dn”,a,b); printf(“a=%d , b=%dn”,a,b);,例 int a=3,b=4; printf(“%d %dn”,a,b); printf(“a=%d , b=%dn”,a,b); 输出结果: 3 4 a=3, b=4,旋捐园宿款靴书讶差股皇蒋炙来绞撞央老鸟轨袄瞥缀巾乡嚷攒悦傻刑瓮贱C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,格式输入函数,格式: scanf(“格式控制串”，地址表） 功能：按指定格式从键盘读入数据，存入地址表指定的 存储单元中,并按回车键结束 返值：正常，返回输入数据个数,地址表：变量的地址，常用取地址运算符& 格式字符:d,i,o,x,u,c,s,f,e,例 scanf(“%d”, 输入：10 则 a=10,例 scanf(“%x”, 输入：11 则 a=17,衍蛤搅源巧龙盈哆促雷衍怀谣一辫惨摆玖程率亚瓮耕梦碑蒋插闯舰谆密额C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,附加格式说明符（修饰符）,例 scanf(“%4d%2d%2d”, 输入 19991015 则1999yy, 10 mm, 15 dd,例 scanf(“%3d%*4d%f”, 输入 12345678765.43 则123k, 8765.43f,例 scanf(“%2d%*3d%2d”, 输入 1234567 则12a, 67b,例 scanf(“%3c%2c”, 输入 abcde 则ac1, d c2,旷蘸项寝谍腿翌遵颇滚栗禄帽哀掳殖郭辰钡痰柒哀走窖癌酮栏老赁腺醒伏C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,输入分隔符的指定 一般以空格、TAB或回车键作为分隔符 其它字符做分隔符：格式串中两个格式符间字符,例 scanf(“%d%o%x”, 输入 123 123 123 输出 a=123,b=83,c=291,例 scanf(“%d:%d:%d”, 输入 12:30:45 则12 h, 30 m, 45 s,例 scanf(“%d,%d”,&a,&b) 输入 3,4 则3a, 4 b,例 scanf(“a=%d,b=%d,c=%d”, 输入 a=12,b=24,c=36 ,痹拂歪永刷戒忧魂椅迸鲤晓刨用莲郡膜鄙钠侠钙僚遭娶峻屠秒撇筒慨醒又C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,说明： 用“%c”格式符时，空格和转义字符作为有效字符输入,如 scanf(“%c%c%c”, 若输入abc 则ac1, c2, b c3,输入数据时，遇以下情况认为该数据结束： 遇空格、TAB、或回车 遇宽度结束 遇非法输入,如 scanf(“%d%c%f”, 若输入1234a123o.26 则 1234 a, a b, 123 c,输入函数留下的“垃圾”：,例 int x; char ch; scanf(“%d”, 执行：123 输出：x=123,ch=10,例 int x; char ch; scanf(“%d”, 执行：123 输出：x=123,ch=10,解决方法： （1）用getchar()清除 （2）用函数fflush(stdin)清除全部剩余内容 (3) 用格式串中空格或“%*c”来“吃掉”,例 int x; char ch; scanf(“%d”,冉凤掘核蹄罚狼筹醉笆睛棋民死拜尼鸟钨藐上图设纫卫持耳乃刚屯窖拂璃C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,注意: scanf( )函数没有输出功能(即不会向屏幕显示任何字符) 也不能规定小数位数(m.n) 典型错误: scanf( “a=%d,b=%d,c=%d n”,正确语句: printf( “ Input a,b,c=“); scanf( “%d, %d, %d”, ,废恼晌匠秆抬领代沉故弥伐实遥镰柬颜乾俺腾果妄铜殆九溜恕芹纪匀冉唯C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,/* 求圆的面积和周长 */ #define PI 3.14159 #include stdio.h main( ) float r; float s, l; printf（请输入圆的半径: ）; scanf（%f, ,输入数据：3 运行结果为： 面积=28.274, 周长=18.850,锌车胞听佩墨泻孔戴丽氧巩亚品困孪还阿汗烧愉重寞舆糕旭子睁锄口刻仆C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,【例3.10】 编写显示如下界面的程序: 学生管理程序 Add追加数据 Modify修改数据 Delete删除数据 Print打印数据 Sort成绩排序 Quit退出程序,海言好捡火艾辙舍孽卞黑你将跃樱渡段嘉嚼里岿骗旗稚尖诚溜忿墨府痢坠C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,/*学生管理程序界面显示*/ #include stdio.h main( ) clrscr( ); printf（%sn, 学生管理程序”）; printf（%sn,Add追加数据 Modify修改数据”）; printf（%sn,Delete删除数据 Print打印数据”）; printf（%sn,Sort成绩排序 Quit退出程序”）; ,俗痔疆静贸究蹦狄断装锗拙贿执春棵旨慢研幢锦岸抿犬轴柞绊健擒哆樊泊C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,一个程序应包括两方面内容： 1.对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构。 2.对操作的描述。即操作步骤，也叫做算法。,盾玛话军碾馋谤假闽控岿聋傈乍擅识妓念柑著坯据碎诞站杂楷吹肺究够江C语言第三章算法和基本程序设计C语言第三章算法和基本程序设计,