第5章程序设计知识

《第5章程序设计知识》由会员分享，可在线阅读，更多相关《第5章程序设计知识（56页珍藏版）》请在金锄头文库上搜索。

1、 计算机导论（计算机导论（20142014）第第5 5章章 程序设计知识程序设计知识5.1 5.1 程序设计语言程序设计语言5.2 C5.2 C语言程序设计语言程序设计5.3 5.3 数据结构数据结构5.4 5.4 编译原理编译原理憎友芥微黑狐陋遥柑驾状楼洲蛾口困詹贷邱枯利纶妮够识移责衡嘛裴泣绍第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1 5.1 程序设计语言程序设计语言机器语言机器语言汇编语言汇编语言高级语言高级语言结构化程序设计语言结构化程序设计语言 面向对象程序设计语言面向对象程序设计语言可视化程序设计语言可视化程序设计语言 人工智能程序设计语言

2、人工智能程序设计语言学习语言是设计程序的基础凡昂遵缆赤袱物啪吏弹廷氮涨蔫尖菜硷谰牲昏行挤傻折欢会盐颖摈截窟迸第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.1 5.1.1 机器语言机器语言机器语言的特点机器语言的特点 由二进制编码指令构成的语言由二进制编码指令构成的语言。是一种依附于机器硬件的语言。是一种依附于机器硬件的语言。机器语言程序可以直接执行。机器语言程序可以直接执行。机器语言程序片段机器语言程序片段 0001 0101 01101100 /把地址为把地址为01101100的内存单元中的数装入的内存单元中的数装入0101号寄存器号寄存器 0001

3、 0110 01101101 /把地址为把地址为01101101的内存单元中的数装入的内存单元中的数装入0110号寄存器号寄存器 0101 0000 01010110 /把把01101100和和01101101中的数相加中的数相加,结果存入结果存入0000号寄存器号寄存器 0011 0000 01101110 /把把0000号寄存器中的数存入地址为号寄存器中的数存入地址为01101110的内存单元中的内存单元中辱跳蓝松让椒迢落麦篓琅蕊崭汇舍井馒沈蘑抚硼惩递颅论笛符执扼装铸绪第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.2 5.1.2 汇编语言汇编语言汇

4、编语言的特点汇编语言的特点 由助记符指令构成的语言由助记符指令构成的语言。也是一种依附于机器硬件的语言。也是一种依附于机器硬件的语言。汇编语言源程序需要汇编后才能执行。汇编语言源程序需要汇编后才能执行。汇编语言程序片段汇编语言程序片段 MOV R5, X /把内存单元把内存单元X中的数装入中的数装入R5寄存器寄存器 ADD R5, Y /把把R5中的数与中的数与Y单元中的数相加，结果存入单元中的数相加，结果存入R5 MOV Z, R5 /把把R5中的数存入中的数存入Z单元中单元中 俺祥嘿杆逝胖籍私袭埂骑障稚誊堡凑悲蛮意荫泪翼疗英粪宽挽颈杭蓄幼儡第5章程序设计知识第5章程序设计知识 计算机导论（

5、计算机导论（20142014）5.1.3 5.1.3 高级语言高级语言高级语言的特点高级语言的特点 由自然语言和数学公式表示的语言由自然语言和数学公式表示的语言。是一种独立于机器硬件的语言。是一种独立于机器硬件的语言。高级语言程序需要编译后才能执行。高级语言程序需要编译后才能执行。高级语言程序片段高级语言程序片段 Z=X + Y /把内存单元把内存单元X中的数与中的数与Y中的数相加，结果存入中的数相加，结果存入Z单元单元 糊暖绥俩浩求篆仓赔谅删逊谢苏鹰诛旱攀益缴菇爬肝番垢怀郸做督酒搀付第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.3 5.1.3 高级语

6、言高级语言常用高级语言常用高级语言 FORTRAN语言语言FORTRAN是是FORmula TRANslator（公式翻译器）的缩写。（公式翻译器）的缩写。主要用于复杂的科学计算领域。主要用于复杂的科学计算领域。ALGOL语言语言ALGOL是是ALGOrithm Language（算法语言）的缩写。（算法语言）的缩写。主要用于数学与科学计算。主要用于数学与科学计算。羚辱芹天劲戳挝熬持杰舞痰棺徽盔玖晨犹尤馁盼熏蛰愤护嘉抛锣才蘑蒋潦第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.3 5.1.3 高级语言高级语言常用高级语言常用高级语言 COBOL语言语言 C

7、OBOL是是COmmon Business-Oriented Language（面向商业的（面向商业的通用语言）的缩写。通用语言）的缩写。主要用于企业管理和事务处理。主要用于企业管理和事务处理。BASIC语言语言 BASIC是是Beginners All-purpose Symbolic Instruction Code（初（初学者通用符号指令码）的缩写。学者通用符号指令码）的缩写。 主要用于初学者和较小规模的程序开发。主要用于初学者和较小规模的程序开发。砷顾钦拎卞郴兆毁扣涣婶醒叶牢有慌才冒跨充芹另貌屯戴摄莹需皱敲耳显第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（2014201

8、4）5.1.4 5.1.4 结构化程序设计语言结构化程序设计语言早期程序设计方法的不足早期程序设计方法的不足注重功能的实现注重功能的实现/注重内存的节省注重内存的节省/注重执行效率的提高。注重执行效率的提高。不注重程序结构的清晰性。不注重程序结构的清晰性。不注重程序的可理解性和可修改性。不注重程序的可理解性和可修改性。 结构化程序设计语言的特点结构化程序设计语言的特点 注重程序结构的注重程序结构的清晰性清晰性。注重程序的注重程序的可理解性可理解性和和可修改性可修改性。采用采用模块化程序设计方法模块化程序设计方法。骡冈超篙普汀窿斑鸣奎又狞清愤朵戚氧倦植峻听犊届键跳业旗鼠犯帜栽蔑第5章程序设计知识

9、第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.4 5.1.4 结构化程序设计语言结构化程序设计语言常用结构化程序设计语言常用结构化程序设计语言 PASCAL语言语言 是在是在ALGOL语言的基础上发展起来的。语言的基础上发展起来的。以法国著名科学家帕斯卡的名字命名。以法国著名科学家帕斯卡的名字命名。 严格的语法格式与结构化形式严格的语法格式与结构化形式。C语言语言 是在是在ALGOL60语言的基础上发展起来的。语言的基础上发展起来的。兼具低级语言和高级语言的特点兼具低级语言和高级语言的特点。是最为流行的程序设计语言之一。是最为流行的程序设计语言之一。砖对啥私婆呼啦申赖盏

10、蚜播雇蠕羹舶镁礁设轿怪什砰漫缺肘呛宗矮集升持第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.5 5.1.5 面向对象程序设计语言面向对象程序设计语言结构化程序设计方法的不足结构化程序设计方法的不足 面向过程的设计方法与人们习惯的思维方式仍然存在一面向过程的设计方法与人们习惯的思维方式仍然存在一定的距离，所以很难自然、准确地反映真实世界，因而定的距离，所以很难自然、准确地反映真实世界，因而用编写出来的程序，特别是规模比较大的程序，其质量用编写出来的程序，特别是规模比较大的程序，其质量是难以保证的。是难以保证的。强调了要实现功能的操作方法（模块），而被操作的

11、数强调了要实现功能的操作方法（模块），而被操作的数据（变量）处于实现功能的从属地位，即据（变量）处于实现功能的从属地位，即程序模块和数程序模块和数据结构是松散地耦合在一起据结构是松散地耦合在一起，当程序复杂度较高时，容，当程序复杂度较高时，容易出错，而且错误难以查找和修改。易出错，而且错误难以查找和修改。吉开夷递油坠梭乃百偿蹦贫监赣虏腋茅邮柯捣本协汇之邱担婴霹虐喜囤封第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.5 5.1.5 面向对象程序设计语言面向对象程序设计语言面向对象程序设计语言的特点面向对象程序设计语言的特点 将问题分解为对象。将问题分解为对

12、象。对象将自己的属性和方法封装成一个整体对象将自己的属性和方法封装成一个整体，供程序设计，供程序设计者使用。者使用。对象之间的相互作用则通过消息传递来实现。对象之间的相互作用则通过消息传递来实现。使人们对复杂系统的认识过程与程序设计过程尽可能一致。使人们对复杂系统的认识过程与程序设计过程尽可能一致。能够更好地保证程序的质量和开发效率能够更好地保证程序的质量和开发效率。孺腺哀厕吗板粕遮通肇鳖舅迄缘曲橙传挠粤狄衔匹办开赴篓寿孰苛宝恶逞第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.5 5.1.5 面向对象程序设计语言面向对象程序设计语言常用面向对象程序设计语

13、言常用面向对象程序设计语言 Simula 67 发布于发布于1967年，是面向对象语言的鼻祖。年，是面向对象语言的鼻祖。C+ 发布于发布于1983年，是在年，是在C语言的基础上发展起来的。语言的基础上发展起来的。C+C+是得到广泛应用的一种面向对象语言是得到广泛应用的一种面向对象语言。目前常用的版本有目前常用的版本有Visual C+, C#, Visual C+ .Net等。等。Java发布于发布于1995年，适合于年，适合于网络程序设计网络程序设计。也是目前得到广泛应用的一种面向对象程序设计语言。也是目前得到广泛应用的一种面向对象程序设计语言。呜仁郧四涨姓航黎旗扒谩窝洛嫡绩绝昆簧辐缝篓倒溪

14、末栈寐燕扮血撞涵豺第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.6 5.1.6 可视化程序设计语言可视化程序设计语言可视化程序设计语言的特点可视化程序设计语言的特点 以图形化的编程方式将面向对象技术的特性体现出来。以图形化的编程方式将面向对象技术的特性体现出来。使开发软件这一原本枯燥、难以理解的工作变得相对轻使开发软件这一原本枯燥、难以理解的工作变得相对轻松快捷。松快捷。常用可视化程序设计语言常用可视化程序设计语言Visual C+ 功能强大，比较适合专业人员使用。功能强大，比较适合专业人员使用。Visual Basic易于学习和掌握，比较适合非专业人

15、员和初学者使用。易于学习和掌握，比较适合非专业人员和初学者使用。搀兜剥擒纱杖蚁搪甫桑渠冲庇迁铸爬昂拂战缠舔洼拓恿扣壮氓户仙肺肯溯第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.1.7 5.1.7 人工智能程序设计语言人工智能程序设计语言人工智能程序设计语言的特点人工智能程序设计语言的特点 适合于知识表示和逻辑推理。适合于知识表示和逻辑推理。 常用人工智能程序设计语言常用人工智能程序设计语言 LISP LISP是是LISt Processing（表处理）的缩写。（表处理）的缩写。可以解决人工智能中的符号处理问题。可以解决人工智能中的符号处理问题。 PROLOG

16、 是是PROgramming in LOGic（逻辑程序设计）的缩写。（逻辑程序设计）的缩写。自动实现模式匹配、自动回溯这两种人工智能中常用的基本操作。自动实现模式匹配、自动回溯这两种人工智能中常用的基本操作。守蕾混栗走间核兹筛丝捉邀篆笛簇糯法织坊藏俯闺驼狭羚旬下事翁券属吓第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2 C5.2 C语言程序设计语言程序设计C C语言的主要特点语言的主要特点简洁、紧凑、灵活。简洁、紧凑、灵活。语法限制不太严格，使用方便灵活；数据结语法限制不太严格，使用方便灵活；数据结构描述能力及表达式能力强；程序书写形式自由。构描述能力及

17、表达式能力强；程序书写形式自由。模块化、结构化。模块化、结构化。用语言编写程序层次清晰，便于按模块组织用语言编写程序层次清晰，便于按模块组织程序，易于实现程序的结构化。程序，易于实现程序的结构化。 功能强大。功能强大。C语言除了能实现一般的高级语言的功能外，还能实语言除了能实现一般的高级语言的功能外，还能实现汇编语言的大部分功能，兼具高级语言和低级语言的特点。现汇编语言的大部分功能，兼具高级语言和低级语言的特点。可移植性好。可移植性好。C语言程序可以容易地移植到不同型号计算机、不同语言程序可以容易地移植到不同型号计算机、不同操作系统环境下执行。操作系统环境下执行。东挪蔑好斧呆偿故疥裁纹李磊夸唆

18、钥拣哨佰亿猛蔗归恒拱恤星砷虽误猎司第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2 C5.2 C语言程序设计语言程序设计C C语言的基本要素语言的基本要素C C语言的数据类型语言的数据类型 C C语言的运算符及表达式语言的运算符及表达式 C C语言语句语言语句 C C语言程序的三种基本结构及实现语言程序的三种基本结构及实现 程序设计风格程序设计风格 算法设计与分析算法设计与分析逢歉累冷账蛹洛寝解醚菠孽蛤约引幅宪锰发毁酮致睦键但沛舶拱秽闭汰淫第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.1 C5.2.1 C语言的基本

19、要素语言的基本要素C C语言的基本词法语言的基本词法字符集字符集英文字母英文字母/数字数字/ 特殊字符特殊字符/ 转义字符。转义字符。标识符标识符C语言中各种对象的名字用标识符表示。语言中各种对象的名字用标识符表示。标识符是由字母、数字和下划线三种字符构成的且第标识符是由字母、数字和下划线三种字符构成的且第一个字符必须是字母或下划线的字符序列。一个字符必须是字母或下划线的字符序列。标识符分为三类标识符分为三类 关键字关键字/ 预定义标识符预定义标识符/ 用户标识符。用户标识符。胡捻公驴吏嘻伯矿霹剁滤于靠费租于耿持严亭蚀及篮抄化拌撰妙掺厉赠结第5章程序设计知识第5章程序设计知识 计算机导论（计算

20、机导论（20142014）5.2.1 C5.2.1 C语言的基本要素语言的基本要素常量常量在程序的执行过程中其值不能被改变的量。在程序的执行过程中其值不能被改变的量。数值型常量数值型常量 整型常量整型常量/ 浮点型常量（实型常量）。浮点型常量（实型常量）。 字符型常量字符型常量字符常量字符常量/字符串常量。字符串常量。变量变量在程序运行过程中，其值可以被改变的量。在程序运行过程中，其值可以被改变的量。一般要先定义，再使用，变量定义的一般形式为：一般要先定义，再使用，变量定义的一般形式为： 数据类型名数据类型名 变量名；变量名；桩苔岔饱脯掣村脯功诡汰森殴涅稠翠逸陡皮餐贷篷岸汤式笋绦竹呢撵吉智第5

21、章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.2 C5.2.2 C语言的数据类型语言的数据类型基本数据类型基本数据类型整型整型整型变量的定义形式为：整型变量的定义形式为：int int 变量名；变量名；实型实型实型变量的定义形式为：实型变量的定义形式为：float float 变量名；变量名；字符型字符型字符型变量的定义格式为：字符型变量的定义格式为：char char 变量名；变量名；构造数据类型构造数据类型数组数组/结构体结构体/共用体共用体/枚举类型枚举类型/用户自定义类型。用户自定义类型。指针类型指针类型在动态数据结构及其应用中有着不可替代的作用。

22、在动态数据结构及其应用中有着不可替代的作用。澳课泣瞥卒惕顷淳瓢洪蹈奥司望暮盯篆演训香屯寅铣哄贸巩殉鸿兢蟹关虽第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.3 C5.2.3 C语言的运算符及表达式语言的运算符及表达式算术运算符算术运算符, , *, /, %（求余数）。（求余数）。 赋值运算符赋值运算符在在C语言中，语言中，称为赋值运算符，其使用形式为：称为赋值运算符，其使用形式为： 变量名变量名 表达式表达式自增、自减运算符自增、自减运算符+是自增运算符是自增运算符，其功能是使变量的值增，其功能是使变量的值增1。- - -是自减运算符是自减运算符，其功

23、能是使变量的值减，其功能是使变量的值减1。关系运算符关系运算符大小判断大小判断（大于）（大于）/（大于等于）（大于等于）/（小于）（小于）/（小于等于）。（小于等于）。相等判断相等判断（等于）（等于）/!（不等于）。（不等于）。 倾嗡胀美恐鞭喀莆炳每保冯药红烙庐席京令稀条魏钝烤驴贩绰酥劈邱粪责第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.4 C5.2.4 C语言语句语言语句控制语句控制语句 用于实现一定的控制功能。用于实现一定的控制功能。条件语句：用于实现程序执行过程中的条件转移。条件语句：用于实现程序执行过程中的条件转移。循环语句：用于实现程序中重复

24、进行某些操作。循环语句：用于实现程序中重复进行某些操作。 复合语句复合语句由一对花括号由一对花括号 括起来的一组语句。括起来的一组语句。如果要在只执行一条语句的地方执行多条语句，那么这如果要在只执行一条语句的地方执行多条语句，那么这多条语句要写成一条复合语句。多条语句要写成一条复合语句。大叶掏钡竿拳忽筛帖僵降笔玛铺锅肖遵都萎叁稽臂驼悔嚼捣绢捏讶西宰坠第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.5 C5.2.5 C语言程序的三种基本结构语言程序的三种基本结构顺序结构顺序结构程序的执行按照语句出现的先后次序顺序进行。程序的执行按照语句出现的先后次序顺序进

25、行。程序中的每个语句都会被执行到。程序中的每个语句都会被执行到。程序示例程序示例：通过键盘输入一个三角形的底和高，计算其面积并输出。通过键盘输入一个三角形的底和高，计算其面积并输出。 main( ) float width,height,area; /*定义变量定义变量*/ printf(nEnter width and height:); /*输出提示信息输出提示信息*/ scanf(%f,%f,&width,&height); /*通过键盘输入底和高通过键盘输入底和高*/ area=(width*height)/2.0; /*计算面积计算面积*/ printf(nThe arae is :

26、%f ,area); /*输出面积的值输出面积的值*/ 首赌土弥纠忻啡迢鸣钓献睡炕铝酷斥卒职厉隐炎英爱巳恬咙璃茅誉资赢粪第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.5 C5.2.5 C语言程序的三种基本结构语言程序的三种基本结构分支结构分支结构根据逻辑条件的成立与否，分别选择执行不同的处理。根据逻辑条件的成立与否，分别选择执行不同的处理。if语句：语句：ifif（表达式）（表达式） 语句语句if-else语句：语句：if if （表达式）语句（表达式）语句1 1 else else 语句语句2 2含臼掠恼抄驳踢捣牵梢公壶后呵掌粹砍昔细直襟泳赘慷益玉霓

27、廉沂蹲邯揉第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.5 C5.2.5 C语言程序的三种基本结构语言程序的三种基本结构分支结构分支结构程序示例程序示例：根据输入的学生成绩对其进行判断处理，如果成绩根据输入的学生成绩对其进行判断处理，如果成绩及格，则输出及格，则输出Passed，否则输出，否则输出Failed。 main( ) float score; /*定义变量定义变量*/ printf(nEnter a score :);/*显示提示信息显示提示信息*/ scanf(%f,&score);/*通过键盘输入一个成绩通过键盘输入一个成绩*/ if (

28、score=60.0) printf(nPassed );/*大于等于大于等于60输出输出Passed*/ else printf(nFailed );/*小于小于60输出输出Failed*/ 澳研愿吕菜纺给铡氓拼母锋污绷撑苑旱慧留假河夕娄狰寞炒湃堕珐突宫亨第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.5 C5.2.5 C语言程序的三种基本结构语言程序的三种基本结构循环结构循环结构根据循环条件的变化，决定是否继续重复执行某些语句。根据循环条件的变化，决定是否继续重复执行某些语句。for循环语句的格式为：循环语句的格式为： for for （表达式（表达

29、式1 1；表达式；表达式2 2；表达式；表达式3 3） 循环体语句循环体语句 霹础删瀑铁正卢讳拴痒汇孙惨亮顶警滑乓狰徊窍觅帽姬小黔焕匡辜斋拥拎第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.5 C5.2.5 C语言程序的三种基本结构语言程序的三种基本结构循环结构循环结构程序示例程序示例：从键盘上输入从键盘上输入10个整数，求其累加和并输出。个整数，求其累加和并输出。 main( ) int i, num, sum;/*定义变量定义变量*/ sum=0;/*累加变量清零累加变量清零*/ for (i=1; i=10;i+)/*循环次数为循环次数为10*/

30、printf(Enter a data:n );/*显示提示信息显示提示信息*/ scanf(%d ,&num); /*通过键盘输入一个整数通过键盘输入一个整数*/ sum=sum+num;/*累加求和累加求和*/ printf(“nsum=%d,sum);/*输出累加结果输出累加结果*/ 顷死晴祥限届俯襟嘎女路寅外狠妆济表般谬忙疙杰自券乍匝思咐早酋卯馅第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.6 5.2.6 程序设计风格程序设计风格主要体现在主要体现在5 5个方面个方面标识符的命名要风格统一标识符的命名要风格统一、见名知义。、见名知义。一般一行写

31、一条语句，一条长语句可以写在多行上，但一般一行写一条语句，一条长语句可以写在多行上，但尽量不要把多条语句写在一行上。尽量不要把多条语句写在一行上。采用缩进格式采用缩进格式，即同一层次的语句要对齐，低层次的语，即同一层次的语句要对齐，低层次的语句要缩进若干个字符，增加程序的可读性。句要缩进若干个字符，增加程序的可读性。适当书写注释信息，有助于阅读者对程序的理解。适当书写注释信息，有助于阅读者对程序的理解。尽量少用尽量少用goto语句，否则容易导致程序结构混乱。语句，否则容易导致程序结构混乱。近吻曹赖游辙远职超眺浑绥柔襄孔迁板虎写辰梳纱驹拎仙新硫皆弧信燕薪第5章程序设计知识第5章程序设计知识 计算

32、机导论（计算机导论（20142014）5.2.7 5.2.7 算法设计与分析算法设计与分析用计算机解决问题的步骤用计算机解决问题的步骤分析问题、设计算法。分析问题、设计算法。选定语言、编写源程序。选定语言、编写源程序。对源程序进行编译生成目标文件。对源程序进行编译生成目标文件。对目标文件进行连接操作，生成可执行的程序。对目标文件进行连接操作，生成可执行的程序。调试执行可执行程序。调试执行可执行程序。责砂争襟逼贺锻骏韩整蔚莎犁天棱慢依佳院宛躇激儒款社靛婉裴竿尾赣吕第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.2.7 5.2.7 算法设计与分析算法设计与分析程

33、序与算法程序与算法算法是指为解决某一问题而采取的方法和步骤算法是指为解决某一问题而采取的方法和步骤。程序是程序设计人员编写的、计算机能够理解并执行的程序是程序设计人员编写的、计算机能够理解并执行的命令集合，是命令集合，是算法在计算机中的实现算法在计算机中的实现。算法的特点算法的特点有穷性有穷性/确定性确定性/有效性有效性/输入及输出。输入及输出。算法的表示算法的表示自然语言自然语言/流程图流程图/伪码。伪码。算法的评价标准算法的评价标准正确性正确性/时间复杂度时间复杂度/空间复杂度空间复杂度/可理解性。可理解性。蘸晚恶谍京绎淤培觉忿奇骸雄际恼稍慢戳爸书券据走馅诈芽卷纬颁霸漆妙第5章程序设计知识

34、第5章程序设计知识 计算机导论（计算机导论（20142014）5.3 5.3 数据结构数据结构概念和术语概念和术语线性结构线性结构树形结构树形结构图状结构图状结构驴决么赎骨鼻口矮砚那叹愤铬交偏根视愤襟村昆锄下衅缩恬鼎朝碘特遗腑第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.1 5.3.1 概念和术语概念和术语数据数据信息的载体，能够被计算机识别、存储和加工处理。信息的载体，能够被计算机识别、存储和加工处理。数据项数据项数据不可分割的最小单位。数据不可分割的最小单位。数据元素数据元素数据的基本单位，具有完整、确定的实际意义。一般由数据的基本单位，具有完整、

35、确定的实际意义。一般由若干数据项组成。若干数据项组成。数据对象数据对象具有相同性质的数据元素的集合，是数据的一个子集。具有相同性质的数据元素的集合，是数据的一个子集。数据结构数据结构互相之间存在着一种或多种关系的数据元素的集合。互相之间存在着一种或多种关系的数据元素的集合。珐宛谅嘻脐纵狗羽厨沁柯乌粒泡队遥漾吾塞掷电慌睬贼旭涅显宛江榔协悉第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.1 5.3.1 概念和术语概念和术语数据的逻辑结构数据的逻辑结构描述的是描述的是数据元素之间的逻辑关系数据元素之间的逻辑关系。数据的物理结构数据的物理结构数据在计算机中的表示

36、数据在计算机中的表示，包括数据元素的表示及，包括数据元素的表示及数据元素间关系的表示。数据元素间关系的表示。整一贸宫指泡材牛崔丫摈购个疚普宁指陋栖口膳钟癌消桥话纪阿妥仓焰魄第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.1 5.3.1 概念和术语概念和术语顺序存储顺序存储逻辑上相邻的元素存储在物理位置也相邻的存储单元中逻辑上相邻的元素存储在物理位置也相邻的存储单元中。链式存储链式存储逻辑上相邻的元素不要求其物理位置相邻逻辑上相邻的元素不要求其物理位置相邻，元素间的逻，元素间的逻辑关系通过附设的指针字段来表示。辑关系通过附设的指针字段来表示。驮隧允峦旱溯这

37、涵蹬影毫讼顾君穷昔兄咸利碑皂冤厦菠鉴了哑灯也铺参由第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.2 5.3.2 线性结构线性结构线性结构的特点线性结构的特点数据元素之间存在着一对一的关系数据元素之间存在着一对一的关系。每个元素有且只有一个前驱（第一个元素除外）。每个元素有且只有一个前驱（第一个元素除外）。每个元素有且只有一个后继（最后一个元素除外）。每个元素有且只有一个后继（最后一个元素除外）。应用示例应用示例一维数组一维数组二维数组二维数组领涯屿捅界顾临腆坷兽拷比疗鹊控呈酝牲赔笛饭穿夺止骡冲蟹伯吻障沸翔第5章程序设计知识第5章程序设计知识 计算机导论

38、（计算机导论（20142014）5.3.2 5.3.2 线性结构线性结构一维数组应用示例一维数组应用示例 main() int i, g, sum, ave; /*定义变量，每一变量代表一内存单元定义变量，每一变量代表一内存单元*/ int a50; /*定义数组，代表定义数组，代表50个内存单元个内存单元*/ for (i=1; i=50; i+) /*循环执行下面大括号中的语句循环执行下面大括号中的语句50次次*/ printf(“nEnter a grade:”); /*在屏幕上显示提示信息在屏幕上显示提示信息*/ scanf(“%d”,&g); /*通过键盘输入一个学生的成绩给变量通过

39、键盘输入一个学生的成绩给变量g*/ ai-1=g; /*把把g单元中的成绩存入数组的相应位置单元中的成绩存入数组的相应位置*/ sum=0; /*作为累加器的单元初值清零作为累加器的单元初值清零*/ for (i=1; i1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m（m1）个互不相）个互不相交的集合交的集合T1，T2，Tm，其中每一个集合，其中每一个集合Ti（1im）本身）本身又是一棵树，树又是一棵树，树T1，T2，Tm称为这个根结点的子树。称为这个根结点的子树。谚绅捧侨雹将喧酉破钟铺张敞方民府曼眩华桓赊墟苇牡郑迎蛊茁泄退秃詹第5章程序设计知识第5章程序设计知识 计算机

40、导论（计算机导论（20142014）5.3.3 5.3.3 树形结构树形结构二叉树的定义二叉树的定义二叉树是有限个结点的集合，该集合或者为空、或者由二叉树是有限个结点的集合，该集合或者为空、或者由一个称为根的结点及两个不相交的、被分别称为左子树一个称为根的结点及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。空二叉树。满二叉树满二叉树：在二叉树中，如果所有分支结点都存在左子树和右子：在二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满树，并且所有叶子结点都在

41、同一层上，这样的一棵二叉树称作满二叉树。二叉树。完全二叉树完全二叉树：一棵深度为：一棵深度为k的有的有n个结点的二叉树，对树中的结点个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为按从上至下、从左到右的顺序进行编号，如果编号为i（1in）的结点与满二叉树中编号为的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。棵二叉树称为完全二叉树。 谐曙雕柑村憎沙甥弃剿支豫兹涪筋穆誊灾箩倡惺把莽哇呻娱胀圭慧裔沙椿第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.3 5.3.3 树形

42、结构树形结构二叉树示例二叉树示例满二叉树满二叉树完全二叉树完全二叉树非完全二叉树非完全二叉树冈贰户敏叶裳迸碰特空甄粮辣获星纶芥贱益街肌遭唁条产爪性剿代泉宪蔡第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.3 5.3.3 树形结构树形结构图5.7 满二叉树8DHIEJKFLGBCA2345679101112M13OP1415图5.8 完全二叉树18DHIEJKFLGBCA2345679101112二叉树的存储二叉树的存储 顺序存储结构顺序存储结构用一组连续的存储单元（数组）存放二叉树中的结点用一组连续的存储单元（数组）存放二叉树中的结点。一般是按。一般是按

43、照二叉树结点从上至下、从左到右的顺序存储。照二叉树结点从上至下、从左到右的顺序存储。完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。中的位置以及结点之间的关系。 韦肪迟丙诡葫彦泪履向榔虚狂痒捣线账针排型裕玄磺扰碰汕巡泵骨缘潍选第5章程序设计知识第5章程序设计知识 计算机导论（计算机导

44、论（20142014）5.3.3 5.3.3 树形结构树形结构图5.7 满二叉树8DHIEJKFLGBCA2345679101112M13OP1415图5.8 完全二叉树18DHIEJKFLGBCA2345679101112二叉树的存储二叉树的存储 链式存储结构链式存储结构用链表来表示一棵二叉树。链表中每个结点由三个域组成，除了用链表来表示一棵二叉树。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点的左子结点和数据域外，还有两个指针域，分别用来给出该结点的左子结点和右子结点所在的链结点的存储地址。右子结点所在的链结点的存储地址。非完全二叉树的链式存储非完全二叉树的链

45、式存储必啄熊定凭制琼谬核慷饶戌勒偏仑天缝帚来酋驮延馆先争志藤窟畏追播赛第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.3 5.3.3 树形结构树形结构树的应用树的应用用于分类的用于分类的决策树决策树用于各种比赛的用于各种比赛的博弈树博弈树券戈议扦蚁莽呕拈萎酚绕池兰瞻箍砚振炸痢漂绝炼悼次檀螟舀敬糙局亚杏第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.4 5.3.4 图状结构图状结构图状结构的特点图状结构的特点数据元素之间存在着多对多的关系数据元素之间存在着多对多的关系。图的定义图的定义 G（V，E）; 其中其中Vvi

46、| vidataobject； E( vi,vj)| vi, vj V P(vi, vj)。G表示一个图，表示一个图，V是图是图G中顶点的集合，顶点集合构成数据对象中顶点的集合，顶点集合构成数据对象（dataobject），顶点就代表数据元素，），顶点就代表数据元素，E是图是图G中边的集合，集合中边的集合，集合E中中P(vi,vj)表示顶点表示顶点vi和顶点和顶点vj之间有一条直接连线，即偶对之间有一条直接连线，即偶对(vi,vj)表示表示图中的一条边。图中的一条边。 赎掂臼介牵垛竹篓端立阴佯腻邦绳贱歹屏匪祷鱼撅赃勾导琅蛛绥旨钝佬地第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（

47、20142014）5.3.4 5.3.4 图状结构图状结构图的示例图的示例图的存储图的存储邻接矩阵邻接矩阵用矩阵表示图中各顶点之间的邻接关系，有边相连对应的矩阵元用矩阵表示图中各顶点之间的邻接关系，有边相连对应的矩阵元素值为素值为1，否则为，否则为0。痰铅滑愉桨诞掐诊庙肆区拙割旷盒颐畦瘁巢裕酷搽捎符纠第央诅垢烟威令第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.4 5.3.4 图状结构图状结构图的存储图的存储邻接表邻接表一种顺序存储与链式存储结合的存储方法。对于图一种顺序存储与链式存储结合的存储方法。对于图G中的每个顶中的每个顶点点vi，将所有邻接于，将

48、所有邻接于vi的顶点的顶点vj链成一个单链表，这个单链表就称链成一个单链表，这个单链表就称为顶点为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图的邻接表。构成了图的邻接表。奸请腋渭虞挣也诉壬砒靖砰卫溜剿计狗皿智唱邱滩血豫票呀滦娄鬼庇婿帐第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.3.4 5.3.4 图状结构图状结构图的应用图的应用求最短路径求最短路径网络性能分析网络性能分析社会网络分析社会网络分析皆受遂檀缴拘怕赃榔喊取斟紊僧空监曰鸭粱鹃萝郑尔朋用雌申蚜萨液墩验第5章程序设计知识第5章程序设

49、计知识 计算机导论（计算机导论（20142014）5.4 5.4 编译原理编译原理编译程序概述编译程序概述词法分析词法分析语法分析语法分析中间代码生成中间代码生成中间代码优化中间代码优化目标代码生成目标代码生成编译程序的开发编译程序的开发掂歉嫩弓毕它摈祈娱孩刘爆孪诵哩撒谐游净竞叠警绸尖茎九柬蕉赏希珍帖第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.4.1 5.4.1 编译程序概述编译程序概述高级语言的特点高级语言的特点简单易学，易于编写和修改程序。简单易学，易于编写和修改程序。编写出的源程序不能直接执行。编写出的源程序不能直接执行。编译程序编译程序把用高级语

50、言编写的源程序翻译成等价的机器语言程序把用高级语言编写的源程序翻译成等价的机器语言程序的翻译程序的翻译程序。学习编译知识的作用学习编译知识的作用深入理解高级语言程序设计。深入理解高级语言程序设计。有助于提高程序设计能力和培养程序设计思维。有助于提高程序设计能力和培养程序设计思维。雨讹皑邻例铀朋辟俘的潭渠疫阳美既慌壕宋驶辱掷阵碎虏邀瓶狠繁致拐穿第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.4.2 5.4.2 词法分析词法分析词法分析的主要任务词法分析的主要任务从源程序中识别出单词从源程序中识别出单词。发现词法错误并指出错误位置。发现词法错误并指出错误位置。以

51、某种机内符的形式表示单词。以某种机内符的形式表示单词。单词种类单词种类基本字：也称关键字，如基本字：也称关键字，如C语言中的语言中的for、do、while等；等；标识符：用来表示各种名字的符号串，如变量名、函数名等；标识符：用来表示各种名字的符号串，如变量名、函数名等；常数：各种类型的常数，如整数、实数、字符串等；常数：各种类型的常数，如整数、实数、字符串等；运算符：各种算术运算、关系运算符，如运算符：各种算术运算、关系运算符，如+、-、=等；等；界限符：如逗号（，）、分号（；）等。界限符：如逗号（，）、分号（；）等。侍栋蠕遭简销汗昌爪两寐邀弟葱木堡婶侍桃舵寒抒沤亏袋坎搭羌瘸秉乔服第5章程序

52、设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.4.3 5.4.3 语法分析语法分析语法分析的主要任务语法分析的主要任务确认作为词法分析结果的确认作为词法分析结果的单词序列是否为给定语言的一单词序列是否为给定语言的一个正确程序个正确程序。给定语言用文法表示，如果给定的单词串能够识别成该给定语言用文法表示，如果给定的单词串能够识别成该文法的句子，则认为程序是正确的，否则认为程序是错文法的句子，则认为程序是正确的，否则认为程序是错误的。误的。自顶向下分析方法自顶向下分析方法/ /自底向上分析方法。自底向上分析方法。调用语义子程序进行语义处理。调用语义子程序进行语义处理。审

53、查每个语法结构的静态语义，即确认语法结构合法的程序是否审查每个语法结构的静态语义，即确认语法结构合法的程序是否真正有意义。真正有意义。焰寄琴禾逾绷汰李钩坑震皂荒蜒贸凋洲翼住叫眺蝗瞎窍洗团拜猖行车午肘第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.4.4 5.4.4 中间代码生成中间代码生成中间代码生成的主要任务中间代码生成的主要任务以某种以某种便于计算机处理的形式表示程序便于计算机处理的形式表示程序。引入中间代码的优点引入中间代码的优点使编译程序结构在逻辑上更为简单明确。使编译程序结构在逻辑上更为简单明确。可以将与机器相关的某些实现细节置于代码生成阶段仔可以

54、将与机器相关的某些实现细节置于代码生成阶段仔细处理。细处理。使得计算和代码优化比较容易实现。使得计算和代码优化比较容易实现。常用的中间代码形式常用的中间代码形式逆波兰式逆波兰式/ /三元式三元式/ /四元式。四元式。瓢骏嘿逊音选葡埃狭突妈铱求滋垣望重臆佑共课默啸量忙寥搬闺鸡屡壤借第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.4.4 5.4.4 中间代码生成中间代码生成逆波兰式计算的优点逆波兰式计算的优点a+bc的逆波兰式形式为的逆波兰式形式为abc+。对于逆波兰式对于逆波兰式abc+，计算机先扫描到运算对象，计算机先扫描到运算对象a、b和和c，然后，然后扫

55、描到运算符，先计算扫描到运算符，先计算bc（假定结果为（假定结果为t），继续扫描到运算），继续扫描到运算符符+，再计算，再计算a+t，从而完成，从而完成a+bc的计算。的计算。无论表达式多复杂，无论表达式多复杂，只一遍扫描就能完成表达式的计算。只一遍扫描就能完成表达式的计算。对于一般表达式对于一般表达式a+bc，计算机先扫描到运算对象，计算机先扫描到运算对象a，然后扫描，然后扫描到运算符到运算符+和运算对象和运算对象b，由于不知道后面的运算符是什么，不能，由于不知道后面的运算符是什么，不能决定是否先完成决定是否先完成+的运算，继续扫描到运算符和运算对象的运算，继续扫描到运算符和运算对象c，知，

56、知道的优先级高，先计算道的优先级高，先计算bc（假定结果为（假定结果为t），再往回扫描计算），再往回扫描计算a+t。对于比较复杂的表达式，可能需要多次来回扫描表达式，对于比较复杂的表达式，可能需要多次来回扫描表达式，才能完成计算，这会很浪费时间。才能完成计算，这会很浪费时间。雕颤扰陡丛育瑰挠锣榜丝趾晶柬仇钎惰柞兹泰员惶戏谱砌狰纪差躁仍怖痘第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.4.5 5.4.5 中间代码优化中间代码优化中间代码优化的主要任务中间代码优化的主要任务对中间代码进行等价变换。对中间代码进行等价变换。变换后的代码运行结果与变换前运行结果相同

57、。变换后的代码运行结果与变换前运行结果相同。运行效率提高运行效率提高（速度提高或（速度提高或/ /和占用存储空间减少）。和占用存储空间减少）。常用的优化技术常用的优化技术删除多余运算删除多余运算/代码外提代码外提/强度削弱。强度削弱。变换循环控制条件变换循环控制条件/合并已知量与复写传播。合并已知量与复写传播。删除无用赋值。删除无用赋值。逐盐驼拧主昭毕芦逆喊赞歪睡贝询敝阿您括瑶绝智耪锨夹笨猖窘喘县睦讽第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.4.6 5.4.6 目标代码生成目标代码生成目标代码生成的主要任务目标代码生成的主要任务把经过优化后的中间代码把

58、经过优化后的中间代码转换成特定机器的机器语言程转换成特定机器的机器语言程序序或汇编语言程序。或汇编语言程序。由于一个高级语言源程序的目标代码需多次使用，因此由于一个高级语言源程序的目标代码需多次使用，因此代码生成器的设计要着重考虑目标代码的质量。代码生成器的设计要着重考虑目标代码的质量。目标代码的质量主要从占用空间和执行时间两个方面综目标代码的质量主要从占用空间和执行时间两个方面综合考虑。合考虑。 幽摹紫耸院淆司懂拒泳典蘑沙鸦桓盲委暖搽陵胸漓概褥宗贵榴税椅娟饲掇第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.4.7 5.4.7 编译程序的开发编译程序的开发编

59、译程序的特点编译程序的特点一个相当复杂的系统软件。一个相当复杂的系统软件。编译程序的自动生成编译程序的自动生成主要是主要是语义分析语义分析和和代码优化代码优化问题。问题。完全自动生成编译程序，目前还不现实。完全自动生成编译程序，目前还不现实。翔褂稀持斧挠汇懈牵驾摆若侣恢垒称灵笆定包七示警野双膏葱砂盗成桃墩第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）GNU C/C+编译编译,汇编汇编、链链接器接器编译编译程序程序 gcc参数含义-o Place the output into -c Compile and assemble, but do not link-g

60、gdbProduce debugging information for use by GDB.-S 编译到汇编语言，不进行汇编和链接-c编译、汇编到目标代码，不进行链接链链接程序接程序ld豹匆嗣承袄陈占啪毛咏燎圾雕豁自工墨桓绷媒扳赎篮格虚遮绅蹿斜匡不氖第5章程序设计知识第5章程序设计知识 计算机导论（计算机导论（20142014）5.5 5.5 本章小结本章小结程序设计能力、程序设计思维是计算机专业学生应具备的基本能程序设计能力、程序设计思维是计算机专业学生应具备的基本能力和素质。力和素质。计算机专业人员要想发挥专业特长，在工作中有竞争力，较强的计算机专业人员要想发挥专业特长，在工作中有竞争

61、力，较强的程序设计能力和软件开发能力是坚实的基础。程序设计能力和软件开发能力是坚实的基础。与提高程序设计能力相关的知识有与提高程序设计能力相关的知识有程序设计语言程序设计语言、数据结构数据结构、编编译原理译原理和和算法设计与分析算法设计与分析。熟悉一种程序设计语言和基本的程序设计方法是编写程序的基础。熟悉一种程序设计语言和基本的程序设计方法是编写程序的基础。对于数据量比较大或数据之间关系比较复杂的程序，要选用合适的数据对于数据量比较大或数据之间关系比较复杂的程序，要选用合适的数据结构合理地组织数据。结构合理地组织数据。计算机专业学生重点还是要培养和提高算法设计能力。计算机专业学生重点还是要培养和提高算法设计能力。用高级语言编写的源程序需要翻译成机器语言程序，才能被计算机执行。用高级语言编写的源程序需要翻译成机器语言程序，才能被计算机执行。编译原理就是介绍如何把高级语言源程序翻译成机器语言程序的。编译原理就是介绍如何把高级语言源程序翻译成机器语言程序的。偿扬盎寒勺荤窝捏墒岸绍肋纵硫洲规返四琅乙撵抓泼壹恃杠夯惺刹芽哑伏第5章程序设计知识第5章程序设计知识