程序设计基础整.ppt
2023/11/4,程序设计-2005秋,1,第一讲程序设计基础,周水庚计算机科学与工程系2005年9月7日,2023/11/4,程序设计-2005秋,2,提要,程序设计基本概念结构化程序设计C语言基础知识高级语言程序开发环境基本知识小结,2023/11/4,程序设计-2005秋,3,提要,程序设计基本概念结构化程序设计C语言基础知识高级语言程序开发环境基本知识小结,2023/11/4,程序设计-2005秋,4,什么是程序？,程序（Program）就是供计算机执行后，能完成特定功能的指令序列（Instructions sequence）程序=计算机指令序列程序包含两方面的内容数据对象（Objects）及数据对象之间关系数据结构(Data structure)对这些对象的处理过程算法(Algorithm),2023/11/4,程序设计-2005秋,5,程序数据结构算法,程序 数据结构 算法Program Data Structure Algorithm,这个公式由Niklaus Wirth首先提出。Niklaus Wirth 是PASCAL之父和结构化程序 设计的首创者，1984图灵奖获得者。,2023/11/4,程序设计-2005秋,6,数据结构,数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure=D,R其中，D是数据对象，R是该对象中所有数据成员之间的关系的有限集合,2023/11/4,程序设计-2005秋,7,数据结构（续）,程序的处理对象是描述客观事物的数据由于客观事物的多样性，会有不同形式的数据整数、实数、字符，以及所有计算机能够接收和处理的各种各样符号集合在程序中，形式不同的数据采用数据类型来标识变量的数据类型说明变量可能取的值的集合、施于变量的操作的集合,2023/11/4,程序设计-2005秋,8,数据结构（续）,数据类型一组形式相同的数据集，对这组数据可施行的一组操作集对数据结构的总括数据结构是指数据对象及其相互关系和构造方法程序的数据结构描述了程序中的数据间的组织形式和结构关系,2023/11/4,程序设计-2005秋,9,算法,算法即问题的求解方法算法由一系列求解步骤组成。算法的描述由经明确说明的一组简单指令和规则组成，计算机按规则执行其中的指令能在有限的步骤内解决一个问题或者完成一个函数的计算算法要求组成算法的规则和步骤的意义应是唯一确定的，是没有二义性的,2023/11/4,程序设计-2005秋,10,算法（续）,算法中的操作是有序的，必须按算法指定的操作顺序执行，能在有限步骤后给出问题的结果求解同一问题可能有多种算法，选择算法主要考虑正确性可靠性简单性易理解性执行效率空间（内存和磁盘）代价等,2023/11/4,程序设计-2005秋,11,算法（续）,描述算法的常用工具有流程图（又称框图）流程图是算法的图形描述，流程图往往比程序更直观清晰，容易阅读和理解，它不仅可以作为编写程序的依据，也是交流算法思想的重要工具在逐步求精的结构化程序设计方法中，目前多数采用结构化的伪代码(pseudo code)来描述算法,2023/11/4,程序设计-2005秋,12,数据结构vs.算法,明确了问题的算法，才能较好设计数据结构要选择好算法，又常常依赖于合理的数据结构程序是和数据结构不可分割的。程序在描述算法同时，也必须完整地描述作为算法的操作对象的数据结构。对于一些复杂的问题，常有因数据的表示方式和结构的差异，问题的抽象求解算法也会完全不同,2023/11/4,程序设计-2005秋,13,程序的性质,目的性程序有明确的目的，程序运行时能完成赋予它的功能分步性程序为完成其复杂的功能，由一系列计算机可执行的步骤组成有序性程序的执行步骤是有序的，不可随意改变程序步骤的执行顺序有限性程序是有限的指令序列，程序所包含的步骤是有限的操作性有意义的程序总是对某些对象进行操作，使其改变状态，完成其功能,2023/11/4,程序设计-2005秋,14,什么是程序设计?,程序设计（Program design）：设计和编制程序的过程设计程序：数据结构设计和算法设计编制程序：把设计转化为某种程序语言的代码程序设计需要程序设计方法 软件工程（Software Engineering）方法学结构化设计方法、面向对象方法程序设计语言 程序语言学Basic,Pascal,C,C+,Java,C#,2023/11/4,程序设计-2005秋,15,什么是好的程序？,高效（Efficient）可靠（Reliable）易读（Easy to read）可维护（Maintainable）可重用（Re-usable）可移植（Portable）,2023/11/4,程序设计-2005秋,16,什么是程序设计语言？,程序设计语言是人与计算机对话的工具，是用来书写计算机程序的语言人机语言（human-machine language）程序设计语言分三类机器语言（Machine language）汇编语言（Assembly language）高级语言（High-level language）,2023/11/4,程序设计-2005秋,17,程序设计语言,High-level language,Machine language,Assembly language,2023/11/4,程序设计-2005秋,18,机器语言,机器语言：计算机的指令系统计算机都只能直接执行由其自身机器语言编写的程序机器语言与计算机的硬件密切相关机器语言中的计算机指令通常用一个二进制形式的代码，由若干位1和0组成一条计算机指令指示计算机一次完成一个最基本的操作,2023/11/4,程序设计-2005秋,19,汇编语言,汇编语言：用类英语单词缩写的符号指令代替机器语言的二进制代码指令用汇编语言编写的程序在计算机上执行，先要将用汇编语言编写的源程序转换成机器语言程序。称完成这个转换功能的程序为“汇编程序“(assembler),2023/11/4,程序设计-2005秋,20,高级程序,最接近自然语言的程序设计语言主要由语句(statements)构成，语句是要计算机完成任务的命令有统一的语法，独立于具体机器，便于人们编码，阅读和理解用高级语言编写的程序（源程序）在计算机上执行，先要由编译器（也称为编译程序）将源程序转换成机器语言程序既能方便地描述客观对象，又能借助于编译器为计算机所接受的语言,2023/11/4,程序设计-2005秋,21,机器语言/汇编语言/高级语言,机器语言,计算机,汇编程序,解释器,编译器,高级语言,汇编语言,Assembler,Interpreter,Compiler,2023/11/4,程序设计-2005秋,22,高级语言分类,目前的高级语言可分三类面向过程的语言（Procedural language）面向问题的语言（Declarative language）描述语言面向对象的语言（Object-oriented language）,2023/11/4,程序设计-2005秋,23,面向过程的语言,早期最流行最常用的程序设计语言为面向过程型的语言Cobol,Fortran,Basic,C,可独立于计算机编写程序，但编写程序时，程序不仅要说明做什么(what)，更重要的是非常详细地告诉计算机如何做(how)，程序需要详细描述解题的过程和细节,2023/11/4,程序设计-2005秋,24,面向问题的语言,不必关心问题的求解算法和求解的过程，只需指出问题是做什么，数据的输入和输出形式，就能得到所需结果数据库查询和操纵语言：SQL(Structured Query Language)语言逻辑语言专家系统语言：Prolog,Lisp等,2023/11/4,程序设计-2005秋,25,面向对象的语言,目的是克服面向过程语言过分强调求解过程细节，程序不易复用的缺点引入了对象、消息、类、继承、封装、抽象、多态性等机制和概念用面向对象语言进行程序设计时，以问题中的对象为基础，将具有类似性质的对象抽象成类，利用继承机制，对差异进行程序设计是目前的主流编程语言：C+,Java,2023/11/4,程序设计-2005秋,26,程序设计语言分类,与自然语言亲密关系机器语言、汇编语言、高级语言描述/求解问题方式面向过程语言：Basic,Pascal,C面向问题语言：SQL,Lisp,Prolog面向对象语言:C+,Java程序设计风格结构化语言Pascal,C,C+,Java非结构化语言Cobol,Fortran,Basic,2023/11/4,程序设计-2005秋,27,提要,程序设计基本概念结构化程序设计语言基础知识高级语言程序开发环境基本知识小结,2023/11/4,程序设计-2005秋,28,结构化程序设计方法,程序结构自顶向下模块化设计方法模块算法的逐步求精(stepwise refinement)设计方法用结构化控制结构描述算法和编写程序,2023/11/4,程序设计-2005秋,29,自顶向下模块化设计方法,限制程序复杂性是程序设计核心程序结构自顶向下模块化设计方法就是把大程序按功能划分成一些较小的部分，每个完成独立功能分解模块的原则是简单性、独立性和完整性。模块化设计方法开发程序，使程序具有较高的可靠性和灵活性，同时便于程序的测试和维护,2023/11/4,程序设计-2005秋,30,自顶向下模块化设计方法（续）,在用模块化方法划分程序模块时，应尽量让模块具有如下良好性质：模块具有单一入口和单一出口模块不宜过大，模块功能单一模块的执行不对环境产生副作用让模块与环境的联系仅限于输入和输出参数，模块的内部结构与调用它的程序无关尽量用模块的名字调用模块,2023/11/4,程序设计-2005秋,31,模块算法逐步求精设计方法,程序设计的基本方法是抽象、枚举、归纳抽象包括算法抽象和数据抽象算法抽象是指算法的寻求(或开发)采用逐步求精、逐层分解的方法数据抽象也指在算法抽象的过程中逐步完善数据结构和引入新的数据及确定关于数据的操作,2023/11/4,程序设计-2005秋,32,逐步求精设计方法（续）,算法设计采用逐步求精设计方法，先设计出一个抽象算法，这是一个在抽象数据上实施一系列抽象操作的算法，由粗略的控制结构和抽象的计算步骤组成。抽象操作只指明“做什么”，对这些抽象操作的细化就是想方设法回答它“如何做”采用逐步求精的方法，由粗到细，将抽象步骤进一步分解成若干子任务。分而治之，对仍不具体的抽象子任务再进行分解。如此反复地一步步细化，算法越来越具体，抽象成分越来越少，直至可以编程为止,2023/11/4,程序设计-2005秋,33,程序的基本结构单元,顺序结构条件选择结构If c Then op1 Else op2 循环结构Do While 循环结构While循环结构For 循环结构任何可计算问题，可用上述三种结构编程解决,2023/11/4,程序设计-2005秋,34,顺序结构,把复杂的计算工作分解成一系列逐条执行的操作序列顺序结构就是为把一个复杂的计算用若干简单计算的顺序执行提供控制手段。顺序结构执行时，从序列的第一个操作开始，顺序执行序列中的操作，直至序列的最后一个操作执行后结束,2023/11/4,程序设计-2005秋,35,顺序结构实例,实例：交换变量x和y的值可分解为顺序执行的三个操作步骤：,temp=x;/*将x的值暂存于temp*/x=y;/*将x置成y的值*/y=temp;/*将y置成temp的值*/,2023/11/4,程序设计-2005秋,36,条件选择结构,条件选择结构有一个判断条件和两个供选择分支操作组成一般形式：,if(判断条件)分支操作1;else 分支操作2;,2023/11/4,程序设计-2005秋,37,条件选择结构执行过程,先计算判断条件，如判断条件的值为真，即条件成立，则执行分支操作1 否则，若判断条件的值为假，即条件不成立，则执行分支操作2 注意，无论判断条件为何值，条件选择结构只执行分支操作1或分支操作2之一条件选择结构中的分支又可以是任何控制结构，当分支操作又是条件选择结构时，就呈现嵌套（nested）的条件选择结构,2023/11/4,程序设计-2005秋,38,实例,int max(int x，int y)/*定义max函数，函数值为整型，形式参数x，y为整型*/int z;/*max函数中的声明部分，定义本函数中用到的变量z为整型*/if(xy)z=x;else z=y;return(z);,2023/11/4,程序设计-2005秋,39,循环结构,循环结构为描述循环操作提供控制手段在C中，循环结构有以下三种：while 循环结构do-while 循环结构for 循环结构,2023/11/4,程序设计-2005秋,40,while 循环结构,由一个循环条件和一个循环操作语句（称为循环体）组成 一般形式：,while(循环条件)循环体,2023/11/4,程序设计-2005秋,41,while 循环结构执行过程,每次循环前，先求循环条件的值，当条件成立时，就执行循环体，并接着再次求循环条件的值，以确定循环体是否再次被执行当循环条件的值一开始为假，或某次循环后其值为假，则结束循环操作,2023/11/4,程序设计-2005秋,42,实例,计算5!：void main()int i，t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(%d，t);,2023/11/4,程序设计-2005秋,43,do-while 循环结构,由一个循环条件和一个循环操作语句（称为循环体）组成 一般形式：,do 循环体 while(循环条件);,2023/11/4,程序设计-2005秋,44,do-while循环结构执行过程,每次循环前，先执行循环体，接着再求循环条件的值，当条件成立时，再执行循环体如此反复，直到循环条件的值为假，结束循环操作,2023/11/4,程序设计-2005秋,45,实例,求 s=1+2+3+100用do-while语句可描述成：s=0;i=1;do s+=i;i+;while(i=100);,2023/11/4,程序设计-2005秋,46,for 循环结构,由为循环有关变量赋初值的表达式、循环条件、循环后对变量的修正表达式和循环执行的循环体组成一般形式：,for(赋初值表达式；循环条件表达式；修正表达式)循环体,2023/11/4,程序设计-2005秋,47,for 循环结构执行过程,循环前，先执行赋初值表达式，为循环中的有关变量赋初值每轮循环开始，先求循环条件的值，若条件不成立，则结束循环当条件成立时，执行循环体；然后求变量修正表达式，更新有关变量的值；接着再次求循环条件如此反复，直到条件为假，结束循环,2023/11/4,程序设计-2005秋,48,实例,求 s=1+2+3+100用for语句可以写成：for(s=0,i=1;i=100;i+)s+=i;,2023/11/4,程序设计-2005秋,49,提要,程序设计基本概念结构化程序设计语言基础知识高级语言程序开发环境基本知识小结,2023/11/4,程序设计-2005秋,50,Dennis M.Ritchie（丹尼斯里奇）,2023/11/4,程序设计-2005秋,51,Dennis M.Ritchie(续),Harvard University获学士和博士学位1967年加入Bell实验室工作至今1972年发明C语言1978年，Brian W.Kernighan和Dennis M.Ritchie 合著The C Programming LanguageTuring奖(1983)和IEEE先驱奖(1992)获得者、美国工程院院士,2023/11/4,程序设计-2005秋,52,C语言发展史,1960年出现的ALGOL 60是一种面向问题的高级语言，它离硬件比较远，不宜用来编写系统程序1963年英国的剑桥大学推出了CPL(combined programming language)语言。CPL语言在ALGOL 60的基础上接近硬件一些，但规模比较大，难以实现1967年英国剑桥大学的Matin Richards对CPL语言做了简化，推出了BCPL(basic combined programming language)语言,2023/11/4,程序设计-2005秋,53,C语言发展史（续）,1970年美国贝尔实验室的Ken Thompson 以BCPL语言为基础，设计出了简单且很接近硬件的B语言(取BCPL的第一个字母)，并用B语言写了第一个UNIX操作系统。但B语言过于简单，功能有限1972年至1973年间，贝尔实验室的D.M.Ritchie 在B语言的基础上设计出了C语言(取BCPL的第二个字母)。C语言既保持了BCPL和B语言的优点(精练，接近硬件)，又克服了它们的缺点(过于简单，数据无类型等)。1973年，K.Thompson和两人合作把UNIX的90%以上用C改写，即UNIX第5版,2023/11/4,程序设计-2005秋,54,C语言发展史（续）,1983年，美国国家标准化协会(ANSI)根据C语言问世以来各种版本对C的发展和扩充，制定了新的标准，称为ANSI C1987年，ANSI又公布了新标准 87 ANSIC1990年，国际标准化组织ISO(International Standard Organization)接受87 ANSI C为ISO C 的标准(ISO 98991990),2023/11/4,程序设计-2005秋,55,一个C程序实例,一个只输出一行信息的程序#include void main()/*主函数*/printf(This book is.n);,2023/11/4,程序设计-2005秋,56,C程序特点,一个C程序有一个名为 main 的主函数主函数前的关键字void表示该函数不返回结果在函数名之后要有一对圆括号，里面定义参数函数体用花括号“”括住。花括号可以用来括起任何一组C代码，从而构成复合语句或分程序简单C语句之后有一个分号“;”程序中的“/*/”表示程序的注释部分。注释便于人阅读程序，对程序编译和运行都没有作用#include 是编译预处理命令行，指明有关输入和输出标准函数也将是程序的一部分,2023/11/4,程序设计-2005秋,57,【例】读入两个整数，输出它们的和/*1*/#include/*2*/void main()/*3*/*变量定义部分*/*4*/int x,y,sum;/*定义 x,y,sum*/*5*/*以下为语句序列*/*6*/printf(Input x and yn);/*提示输入数据*/*7*/scanf(%d%d,/*输出结果*/*10*/,2023/11/4,程序设计-2005秋,58,【例】利用公式：C=（5/9）（F-32）输出F氏温度与C氏温度对照表，设已知F氏温度取0、20、200。#include void main()float f,c;/*变量定义*/int lower,upper,step;lower=0;upper=200;step=20;f=lower;while(f=upper)/*循环计算*/c=5.0/9.0*(f-32.0);printf(“%3.0f%6.1fn”,f,c);f=f+step;,2023/11/4,程序设计-2005秋,59,【例】输入两个实数,输出它们中的小的数#include void main()float x,y,c;/*变量定义*/float min(float,float);/*函数说明*/printf(“输入x和y.n);scanf(%f%f,/*返回 temp 到调用 min()函数处*/,2023/11/4,程序设计-2005秋,60,函数（Function）,C程序由若干函数组成。每个程序都有一个主函数-main()函数一个函数定义由函数头和函数体组成。函数头包括函数属性、函数返回值类型、函数名、函数形式参数名，形式参数类型。函数结构的一般形式：,函数返回值类型 函数名(参数说明表)说明和定义部分;执行语句序列,2023/11/4,程序设计-2005秋,61,函数（续）,函数可以没有参数，但函数名之后的一对圆括号是必须的函数体是函数头之后用一对花括号括住的部分。函数体用于描述实现函数功能的代码，它又包括：说明和定义部分说明数据结构(类型)和定义函数专用的局部变量等执行部分由语句和控制结构代码组成,2023/11/4,程序设计-2005秋,62,【例】统计输入字符行中各数字符、空白符与制表符符以及其它字符的出现次数。#include void main()int c,k,nWhite,nOther;int nDigit10;/*定义有10个数字符的计数器*/nWhite=nOther=0;for(k=0;k=0,2023/11/4,程序设计-2005秋,63,C语言词汇,基本符号数字10个(09)英文字母大、小写各26个(AZ,az)下线字符“_”其他构成特殊符号的字符集基本词汇字面形式常量特殊符号（运算符）关键字标识符（命名数据对象）,2023/11/4,程序设计-2005秋,64,关键词（Keyword）,auto break case char const continue default do double else enum extern float for goto if int long register return short signed static struct switch typedef union unsigned voidvolatile while,2023/11/4,程序设计-2005秋,65,关键词（续）,下面几个虽不属于关键字，但建议把它们看作关键字，不要在程序中随便使用。它们用在程序的预处理命令行中,define undef include ifdefifndefendif line elif,2023/11/4,程序设计-2005秋,66,标识符（Identifier）,作用：用来标识变量、常量、类型、函数、语句等程序对象，C语言用标识符给它们命名命名规则：在C语言中，一个合理的标识符由英文字母或下线符开头，后跟或不跟由字母、下线符、数字符组成的字符列。一般以下线符开头的标识符作内部使用,2023/11/4,程序设计-2005秋,67,标识符（续）,命名要求：标识符作为程序成分对象的名称，为了便于联想和记忆，建议使用能反映该对象意义的标识符限制：注意不同系统对标识符的有效字符个数有不同的规定。对于限制标识符8个有效字符的系统来说，两个超过8个字符的不同标识符，当前8个字符依次相同时，系统就认为它们是同一个标识符,2023/11/4,程序设计-2005秋,68,C语言数据类型,三种数据类型基本数据类型、指针类型、复合数据类型基本数据类型三种整型(short,int,long)实型(float,double,long double)字符型(char),2023/11/4,程序设计-2005秋,69,C语言数据类型(续),复合数据类型数组、结构、联合和枚举指针类型指针类型直接赋予数据对象在内存中的地址的概念,2023/11/4,程序设计-2005秋,70,常量（Constant）,在程序运行过程中，其值不能改变或不允许改变的数据对象常量按值的表示形式区分它的类型整型常量：15浮点型常量：5.0字符型常量：a指针常量：NULL字符串常量：”ABC”,2023/11/4,程序设计-2005秋,71,常量（续）,可用宏定义给常量命名其一般形式是,#define 标识符 字符列如：#define PI 3.14159,2023/11/4,程序设计-2005秋,72,变量（Variable）,在程序运行过程中，其值可以改变的数据对象变量在内存中占据一定的存贮单元，存放变量的值与变量有关的概念有：变量名、变量数据类型、变量在程序中的有效作用范围、变量在程序执行期间的存在时间等,2023/11/4,程序设计-2005秋,73,变量（续）,程序通过变量定义引入变量，变量定义的一般形式：,类型 变量名表;其中，变量名表由一个或多个变量名组成。例如：int i,j,sum;/*定义三个int型变量*/int index=100,big_int=10000,2023/11/4,程序设计-2005秋,74,提要,程序设计基本概念结构化程序设计语言基础知识高级语言程序开发环境基本知识小结,2023/11/4,程序设计-2005秋,75,C程序从开发到运行的六个阶段,C程序从开发到运行大致要经历六个阶段编辑（Edit）预处理（Pre-process）编绎（Compile）连接（Link）加载（Load）执行（Execute）,2023/11/4,程序设计-2005秋,76,编辑、预处理与编译,编辑：程序员用系统环境提供的编辑器编辑源程序，产生一个源程序文件.c 或.h 预处理：编译前，C编绎器先自动调用预处理程序，对源程序文件作文字转换，产生一个新的内部程序代码编译：若编译过程中发现程序有错误，则输出错误的详细信息；对正确的源程序产生机器语言程序，称为源程序的目的代码,2023/11/4,程序设计-2005秋,77,连接、加载与执行,连接：连接程序将目的代码和一些库函数的目的代码连接起来，产生计算机可直接执行的程序映象文件静态连接vs.动态连接加载：将要执行的程序装入内存执行：装入内存的程序在计算机的操作系统控制下执行,2023/11/4,程序设计-2005秋,78,提要,程序设计基本概念结构化程序设计语言基础知识高级语言程序开发环境基本知识小结,2023/11/4,程序设计-2005秋,79,小结,程序是为解决某一问题的某种语言指令的序列程序设计是基于某种程序语言设计和编制程序的过程结构化程序设计方法是常用的、比较有效的程序设计方法C语言是一种主流的过程化高级程序设计语言一个高级语言程序在运行前，要经过预处理、编译、连接和加载等四个过程,2023/11/4,程序设计-2005秋,80,作业,设计一个C程序，实现如下功能,C程序？,输入“2005级新生”,“出国”,“读研”,“工作”,“失业”,“肆业”,“退学”,2023/11/4,程序设计-2005秋,81,谢谢！,
