语言、算法和程序设计方法

《语言、算法和程序设计方法》由会员分享，可在线阅读，更多相关《语言、算法和程序设计方法（50页珍藏版）》请在金锄头文库上搜索。

1、第第6 6 章 章 语言、算法和程序设计方法语言、算法和程序设计方法6.1 从算法到程序再到软 件 6.2 程序和指令 6.3 程序的程序：翻译系 统 6.4 程序设计语言 6.5 怎样编写程序 6.6 算法 6.7 *数据表达和数据结构 6.8 *软件工程简介 6.9 *职业：软件工程师 从算法到程序再到软件 计算机完成各种不同的任务，需 要不同的软件 软件开发算法算法程序程序软件软件程序设计是软件开发的一部分l程序设计分解为几个步骤l程序设计需要使用程序设计语言算法设计软件开发的任务之一l选择一种语言l使用这个语言编写完成操作任务的代 码 程序设计软件开发的核心工作是算法设计软件开发的核心

2、工作是算法设计算法l一项工作如何被完成的步骤l数学问题寻找如何解决特定问题的方法 一个著名的算法 欧几里德算法：求两个正整数A和B的最大公约数如：9、6的最大公约数是3l第一步：比较A和B这两个数，将A设置为较大的数，B设 置为较小的数；l第二步：A除以B，得到余数C；l第三步：如果C等于0，则最大公约数就是B；否则将B赋值给A，C赋值给B，重复进行第二 、三步从算法到程序再到软件 A B C9 6 36 3 03图灵理论 只要能被分解为有限步骤的问题就可以被计算机执 行l有限的步骤l能够将这些步骤设计为计算机所执行的程序 程序设计中，首先寻找算法，算法找到后，实现算 法的步骤 算法的描述l使

3、用某种计算机语言l不同的计算机语言对一个算法具有不同的实现方 法 算法是程序设计的基础从算法到程序再到软件 程序和指令程序 programl计算机执行某种任务的一系列操作步骤的总和 l一组计算机指令的有序集合 指令 instructionl控制计算机执行各种基本操作的命令l指令是计算机执行的最基本操作 如：处理器从内存中读取一个数据二进制的算术运算加、减、乘、除逻辑判断等l处理器能执行的二进制代码程序和指令指令作为计算机软件和硬件的接口l指令在处理器中以逻辑电路实现软件硬件 指令 指令系统指令系统l l一个一个CPUCPU能够执行的所有指令能够执行的所有指令l l指令的主要类型指令的主要类型数

4、据传输类数据传输类将数据从一个地方将数据从一个地方( (源源) )传输到另外一个地方传输到另外一个地方( (目的目的) ) 一种是在一种是在CPUCPU内部、存储器内部、内部、存储器内部、CPUCPU和存储器之间进行和存储器之间进行 一种是在一种是在CPUCPU和外设（外设接口）之间进行和外设（外设接口）之间进行的的算术逻辑运算类算术逻辑运算类控制操作类控制操作类有条件转移、无条件转移有条件转移、无条件转移翻译系统 基本概念 l源程序 用各种语言编写的程序l目标程序 源程序经过翻译，成为机器可执行的机器语言程 序l库文件 由一些标准子程序(函数和过程)及常用的应用程序 块组成的文件l可执行程序

5、目标程序与库文件连接后形成的 程序l程序的整个处理过程 翻译翻译和库文件和库文件 连接连接装入装入源程序源程序目标程序目标程序可执行程序可执行程序执行执行翻译系统l语言处理系统，翻译计算机程序l任务是把非机器语言编写的源程序翻译成目标程 序l是系统软件l不同编程语言的翻译系统是不同的分类 l汇编程序l编译程序l解释程序逐条翻译并执行源程序的语句逐条翻译并执行源程序的语句 ， 不生成可执行文件不生成可执行文件把源程序代码一次性翻译成目标程序把源程序代码一次性翻译成目标程序 代码，最终生成可执行文件代码，最终生成可执行文件把汇编语言源程序翻译为机器语言程序把汇编语言源程序翻译为机器语言程序编译系统

6、的结构和工作过程编译系统的结构和工作过程词法分析程序语法分析程序中间代码生成程序优化程序目标代码生成程序目标程序源程序If x=0 Then y=1 Else y=-1程序设计语言发展阶段l机器语言 低级语言l汇编语言 中级语言l面向过程的高级语言l面向对象的高级语言机器语言和指令 机器语言l计算机能直接执行的程序设计语言 l二进制语言，用二进制机器指令来编写程序 机器指令的信息l操作类型l操作数或操作数的地址（操作数的存储位置）l操作结果的存储位置l下一条指令的地址信息 指令格式操作码操作数或地址码下一条指令的地址机器语言和指令指令的例子：数1和3的相加l指令10000000 0000000

7、1 00000011 “加”操作码 Number1：1 Number 2：3l实现过程 用计算器 计算机 程序 过程l指令执行过程 特点l既简单又难l执行速度最快l面向机器，兼容性差，移植性差 l最低级语言计算器的工作原理用VB设计的加法程序Private Sub Command1_Click()Dim A As Integer, B As Integer, S As IntegerA = Val(InputBox(“请输入第一个数“)B = Val(InputBox(“请输入第二个数“)S = A + BPrint A; “+“; B; “=“; SEnd SubMemoryInput Ou

8、tput控制器ALUFor Example：1+3=4命令：输入111命令：输入333Write Write ReadRead134OutAdd+一条指令的执行过程 1.取操作码2.内部译码3.取第一个数4.取第二个数5.ALU完成加6.保存结果7.取下一条指令汇编语言 机器语言的“符号化”l用容易记忆的文字符号(助记符)表示指令中的操作 码和地址码 指令格式 助记符 符号地址l例：加法语句 ADD A，B 特点l机器不能直接识别l可读性好l面向机器，兼容性差，移植性差l中级语言 高级语言与机器完全独立的语言，描述解题过程 语法与自然语言接近 特点l面向问题，通用，可移植 分类l面向过程 BA

9、SIC BASIC C CPASCALPASCAL FORTRANFORTRAN COBOL COBOL AdaAdal l面向对象面向对象Visual BasicVisual Basic C+C+ JAVAJAVA DelphiDelphi Power BuildPower Build面向对象程序设计程序的基本成分l对象 是具有特殊属性(数据) 和方法(行为、操作)的实 体 特点l封装性l继承性l多态性 把对象的属性和操作结合在一起，构成一个独立的对象把对象的属性和操作结合在一起，构成一个独立的对象 子类可以拥有父类的属性和行为子类可以拥有父类的属性和行为 基类中定义的属性和行为被子类继承后

10、，可以具有不同的基类中定义的属性和行为被子类继承后，可以具有不同的 数据类型或不同的行为数据类型或不同的行为 * 其它语言函数型语言 lLISPlScheme 说明性语言l逻辑语言，用于根据逻辑推理的原则回答问题lProlog 超文本链接标记语言( HTML)l由一种格式标记和超链接组成的“伪语言”，主要用于网 络上的信息服务 lXML 可扩展标记语言 其它语言l如 SQL *基于组件的程序设计 基于组件的程序设计是微软提出的思想 COM（Component Object Model，组件对象模型）l组件技术属于面向对象的程序设计技术l 使用COM技术，一个新的应用系统的开发不必按 照传统的方

11、法进行所有代码的编写，可以通过组 件进行“组装”软件l对于提高开发速度、降低开发成本、增加应用软 件的灵活性、降低软件维护费用很有帮助l软件开发技术的主流方向程序设计语言的发展历史怎样编写程序 程序设计是一个系统过程l不是简单的编写程序代码 一般可以分为六个步骤l问题的定义（程序说明）l设计解决问题的方案l编写程序代码l进行程序测试l编写程序的文档l程序应用（程序运行与维护）一、理解问题：程序说明 程序设计中最重要的部分l是对问题的描述l设计一个程序是为了解决某个特定的问题l分析特定问题，决定应该做什么，如何做 系统分析员主要弄清以下问题：l程序的目标是什么？即程序需要解决什么样的问 题l可能

12、需要输入哪些数据？l数据具体的处理过程和要求是什么？l程序可能产生的数据输出以及输出形式是什么？示例示例1 1 示例示例2 2二、设计解决问题的方案对要解决的问题设计出具体的解决方案l确定程序的逻辑结构l关键 设计算法例：欧几里德算法 求两个正整数A和B的最大公约数第一步：比较A和B这两个数，将A设置为较大的数，B设 置为较小的数；第二步：A除以B，得到余数C；第三步：如果C等于0，则最大公约数就是B；否则将B赋值给A，C赋值给B，重复进行第二、三步程序的逻辑结构所有程序都由三种结构构成l顺序结构 按命令出现的先后顺序依次执行l分支结构根据设定的条件来决定程序的执行方向l循环结构按照设定的条件

13、重复执行一组命令当型当型 直到型直到型 流程图顺序结构AB分支结构分支结构X=0X=5Y=2*X循环结构当型结构 直到型结构X=0X=0三、编写程序代码编写程序代码l选择合适的编程语言l按照上阶段设计的算法编写代码 选择哪种程序设计语言？l主要看是否能够完成程序设计任务l编程人员对这个语言的熟悉程度 程序代码的例子l计算 5！ fac=1*2*3*4*5 分别用C语言、VB和Java实现一个程序代码的例子（C语言）计算 5！#include /* C语言编译系统的库函数 */main()/* 程序开始 */ int i, fac; /* 定义变量 */fac=1;/* 变量 fac 被赋值 1

14、 */for( i =2; i0 =n* Factorial(n-1) 递归步骤排序问题 排序就是按增加或减少的顺序对一组类似的信息重 新进行安排的过程l插入排序l选择排序l冒泡排序以第一个数据作为已排序数据序列，从第二 个数据起，将各数据逐个插入到已排序序列 中的合适位置，使其继续成为有序数据序列每次从未排序的数据中选出最小（大）数据 ，放到已排序数据之后从第一个数据开始，依次对相邻两个数据比较，当发现它 们不合顺序时就进行一次交换，直到所有数据都有序为止 例：对以下数据按从小到大的顺序排列 5，4，9，2，7 排序问题迭代的延续应用n个数据元素的列表进行排序，最多需要n-1 排序问题查找问

15、题 把一个特定的数从列表中找到，并提供它所在的位 置 l顺序查找l折半查找(二分法)从列表的第一个数据开始顺序查找，直到找到从列表的第一个数据开始顺序查找，直到找到 所要找的数据或搜索完所有数据所要找的数据或搜索完所有数据首先测试中间那个数据，如果它大于查找关键字首先测试中间那个数据，如果它大于查找关键字 ，则再测试前半部分中间那个数据，否则测试后，则再测试前半部分中间那个数据，否则测试后 半部分中间那个数据，不断重复这个过程，直到半部分中间那个数据，不断重复这个过程，直到 找到了一个匹配项或所有元素都被测试遍了找到了一个匹配项或所有元素都被测试遍了 例：从以下数据中找出数 20 的位置 5，6，10，17，20，24，30数据必须有序数据必须有序