大学计算机基础6

Overview

1.从算法到程序再到软件

2.程序和指令

3.程序的程序：翻译系统

4.程序设计语言

5.怎样编写程序

6.算法

7.数据表达和数据结构

8.软件工程简介

9.职业：软件工程师

6.1从算法到程序再到软件

♦完成各种不同的任务，需要不同的软件

♦整个程序设计过程为软件开发的一部分

♦程序设计需要使用程序设计语言

♦程序设计分解为几个步骤，如程序说明、

设计、编写代码以及测试、文档等

♦软件开发中，核心工作是进行算法设计

♦可视化程序设计成为今天程序设计的主流

6.1从算法到程序再到软件Cont

♦算法：一项工作如何被完成的步骤

♦算法：数学问题——寻找特定的问题如何解决的

方法

♦一个著名的例子就是欧几里德(Euclid)算法：

求两个正整数A和B的最大公约数

第一步：比较A和B这两个数，将A设置为较大的数，B为

较小的数；

第二步：A除以B,得到余数C；

第三步：如果C等于0,则最大公约数就是B；否则将B赋

值给A,C赋值给B,重复进行第二步、第三步。

4

6.1从算法到程序再到软件Cont

♦找到算法后，实现过程就是按照算法所指示的过程

♦图灵理论——只要能被分解为有限步骤的问题就可

以被计算机执行

-一是有限的步骤

-二是能够将这些步骤设计为计算机所执行的程序

♦算法是程序设计的基础，算法研究

♦算法找到，就需要对这个算法进行描述——将算法

的步骤变成计算机能够用它的语言所实现的表示方

式

♦算法的描述的研究少研究计算机的语言和语法

-算法的计算机实现就有大量的可替代的实现方案

-不同的计算机语言对一个算法的实现过程具有不同的实

现方法，这些方法也被称为程序设计范型

(Paradigm)。

5

6.2程序和指令

♦什么是程序

♦程序如何做

♦程序的定义

-Program（节目单）——演出是按照事先实现

确定好的顺序进行的

-因此程序被理解为“按预先设计的步骤执行”

-算法就是设计这些步骤

6

6.2.1程序：按步骤执行

♦程序

-从广义上看，程序是计算机进行某种任务操作的一系

列步骤的总和——是一组计算机指令的有序集合

-由机器语言、汇编语言、高级语言编写

♦指令和指令系统

-指令和指令系统构成计算机处理器的重要部分，又是

整个程序的基础

-指令就是计算机执行的最基本的操作——处理器所能

够执行的二进制代码

-指令和机器的硬件是直接相关的

7

622软硬件的交汇：

指令和指令系统

♦指令(Instruction)指令系统(InstructionSet)

-指令和指令系统是CPU的重要部分

-又是整个程序的基础。

♦指令：计算机执行的最基本的操作

-如处理器从内存中读取一个数据，进行算术运算，或

者是逻辑判断等，都属于一条指令的操作

♦指令系统：一个CPU所能够执行的所有指令

-指令系统是所有指令的集合

-指令和机器的硬件是直接相关的

指令系统的主要类型

♦数据传输类指令——将数据从一个地方

（源）传输到另外一个地方（目的）

-一种是在CPU内部、存储器内部、CPU和存

储器之间进行

-一种是在CPU和外设（外设接口）进行的

♦算术逻辑类指令

♦控制操作类指令

10

6.3程序的程序：翻译系统

♦语言处理系统一翻译计算机程序

-本身就是程序

-任务就是把其他程序翻译为机器语言程序

-是程序的程序

♦翻译程序归类为系统软件

♦除了机器语言编制的程序，其他任何语言

编写的程序都需要相应的翻译系统

♦不同的编程语言的翻译系统是不同的。

11

程序的翻译系统

翻

译

程序

源

系

统

■翻译程序根据功能的不同分为

■编译程序（CompiledProgram或称为编译器Compiler）

■解释程序（Interpreter,也叫做解释器）

12

6.3.1解释程序

♦解释程序

-对源代码程序进行逐句翻译，翻译一句执行一句

-翻译过程中并不生成可执行文件

-对计算机的硬件和存储器要求不高

♦程序运行速度较慢

♦一般不提供任何分析和程序错误更正

♦这种系统有特定的时代印记，现在主要使用在

编程环境和一些专用系统中

13

6.3.2编译程序

♦编译程序

-将整个源程序代码文件一次性翻译成目标程序代码，

最终生成可执行文件。

-编译后的程序可被单独执行，和翻译程序无关

♦类比：翻译一本书

♦编译系统，效率高

♦高级编译器还生成分析文件和程序错误文件，帮

助编程者更快地找出错误

♦各种高级语言的开发环境中一般都包含了编译系

统功能

14

编

译

系词法分析程序

统

的语法分析程序

结

构中间代码生成程序

和

工优化程序

作

遒目标代码生成程序

程

目标程序

15

编译系统

♦大多数语言系统都是将源文件的编辑、翻

译程序(解释或编译)以及调试等集成在

一起，形成集成开发环境(IDE,

IntegratedDevelopedEnvironment)

♦今天被普遍使用的C语言、VB等都是使用

专门的IDE进行程序设计的

16

6.4程序设计语言

按照程序设计语言和机器的密切程度

♦面向机器硬件的机器语言

-二进制语言，用二进制机器指令来编写程序

♦汇编语言

-机器语言的符号化，一般用英文单词或缩写表示机器

指令，因此也是面向机器的

♦面向过程的高级语言

-接近数学描述求解问题的过程，它和机器没有直接关

系。语法与自然语言接近

♦面向对象的IWJ级语言

17

6.4.1机器语言和指令

♦机器语言就是指令—二进制代码

♦能被计算机直接执行

♦一条机器指令需要包含如下信息

-操作类型

♦有几十种到上百种，如加法、访问存储器、输入输出操作等

-操作数或者操作数的的存储位置，也称操作数的地址

♦它说明参加运算的数据存储在什么地方，它可以是内存单元或

CPU内部寄存器或者直接包含在指令中

-操作结果的存储位置

♦它说明将结果存储到什么地方，如存储器单元、寄存器等

-一条指令的地址信息

♦它说明到哪里去取下一条指令。

18

机器语言和指令

操作码操作数或地址码下一条指令的地址

机器指令的一般格式

19

指令的例子

实现数2和3的相加：

100000000000001000000011

加操作码Numberl：2Number2：3

20

ForExample：

2+3=5-------------

Memory

Output

Out

21

一条指令的执行过程

程序/指令

.取操作码

10000000操作码

◄--------3.取第一个数Numberl——第一操作数

◄--------4.取第二个数

Controer——Number2—第二操作数

Progi^mCoun

下:一条指令操作码

7.取丁一条指令J

22

6.4.2汇编语言

♦用容易记忆的文字符号来表示指令中的操作码和

地址码，这种符号叫助记符

♦CPU所有指令助记符的集合以及使用规则构成了

助记符语言-汇编语言（AssembleLanguage）

♦例子（汇编语言的一条加法语句）

ADDA,B

-意思是将存储地址A和B的内容相加，结果存储在地址

A或B的存储单元（不同的计算机有不同的规定）。

23

汇编语言指令

♦与二进制的机器指令相比，汇编语言指

令可读性较好

♦它仍然是一种面向计算机硬件的言，程

序员必须熟悉计算机硬件结构、指令系

统和指令格式等

♦程序移植性也较差

24

6.4.3面向过程的高级语言

♦高级语言是一种与机器指令系统无关，表

达形式更接近于被描述问题的语言

♦高级语言可分为两种类型：

♦面向过程

♦面向对象

25

面向过程的高级语言Cont

♦Basic(BeginnerALL-PurposeSymbolicInstructionCode)

-在计算机技术发展史上应用得最广泛的语言一

-适于编程初学者编程，简单易学

-非计算机专业出身的编程者广泛使用

♦C语言

-c是一种高级语言，被广泛用于专业程序设计

-既有高级语言的优点，又有汇编语言的效率，因此也

有人把它定位为“中级语言”

-它的命令可直接对计算机内存单元中的数据进行位操

作，适合编写较接近硬件操作又要求处理速度的程序

26

♦Pascal语言

-Pascal---为纪念计算机先驱Pascal命名的

-作为一种教学和应用开发语言被普遍接受

♦Fortran语言

-第一个高级语言：IBM公司在1957年开发的

-更适合于科学、数学和应用工程方面的应用，编程人

员可用它方便地描述数学问题，解决数学计算

♦Cobol语言

-COBOL是一种专门的商用的高级程序设计语言，于

1960年问世

-大部分命令都与英语类似

-比较适用于存储、检索公司的财务信息，实现票据管

理和工资报表等功能

27

6.4.4面向对象的程序设计语言

♦OOPL,Object-OrientedProgrammingLanguage

♦特点

-封装(Encapsulation)是面向对象方法的一个重要原则

♦对象的属性和操作结合在一起

♦隐蔽内部信息——通过有限的接口与对象发生联系

♦对于外界而言，只需知道对象所表现的外部行为，不必了解对

象行为的内部细节

-继承(Inheritance)

♦子类可以拥有父类的属性和行为

♦提高了软件代码的复用性，定义子类时不必重复定义那些已在

父类中定义的属性和行为

28

面向对象的程序设计语言(Cont)

♦特点

一多态性(Polymorphism)

♦基类中定义的属性和行为被子类继承后，可以具有

不同的数据类型或不同的行为

♦软件的结构设计提供了灵活性，还减少了信息冗余,

提高了软件的可扩展性

29

面向对象的程序设计语言（Cont）

♦VisualBasic

-简称VB,BASIC引入了面向对象的设计方法

-为开发图形界面的应用程序而设计的

-它比较简单易学，功能强大，得到广泛应用

♦JAVA

-SunMicrosystem公司开发

-具有纯面向对象、平台无关性、多线程、高安全性等

转点

-解茶了困扰软件界多年的软件移植问题

♦C++

-传统的C语言进行面向对象的扩展而成的语言

-它在C语言的基础上增加了面向对象程序设计的支持

30

*6.4.5其他语言

♦函数型语言——主要有LISP和Scheme

♦说明型语言——也叫逻辑语言，它被用于

根据逻辑推理的原则回答问题

♦超文本链接标记语言——由一种格式标记

何超链接组成的“伪语言”，主要用于网

络上的信息服务

31

*6,4.6基于组件的程序设计

♦基于组件的程序设计是微软提出的思想

♦COM（ComponentObjectModel,组件对象模型）

-组件技术属于面向对象的程序设计技术

-使用COM技术，一个新的应用系统的开发不

必按照传统的方法进行所有代码的编写，可以

通过组件进行“组装”软件

-对于提高开发速度、降低开发成本、增加应用

软件的灵活性、降低软件维护费用很有帮助

-软件开发技术的主流方向=一

BackOverview

32

6.5怎样编写程序

♦程序设计不是简单的编写程序代码，它是

一个系统过程

♦一般可以把这个系统过程分为六个步骤

-问题的定义或叫做程序说明

-设计解决问题的方案

-编写程序代码

-进行程序测试

-程序的文档

-程序应用

33

6.5.1理解问题：程序说明

♦程序设计中最重要的部分

♦设计一个程序是为了解决某个特定的问题，

那么应该做什么，如何做——系统分析员

♦主要是要弄清以下几个问题

-程序目标是什么？即程序需要解决什么样的问题

-可能需要输入哪些数据？

-数据具体的处理过程和要求是什么？

-程序可能产生的数据输出以及输出形式是什么？

34

设计解决问题的方案

♦本阶段需要对要解决的问题设计出具体的

解决方案——设计算法

-逻辑结构

-算法

-流程图

-伪代码

35

6.5.2程序的逻辑结构

所有的程序都由三种结构构成

♦顺序结构

-是程序最简单的一种结构，它使计算机按照命令出现

的先后顺序依次执行

♦循环结构

-使计算机按照设定的条件重复执行一组命令

♦分支结构

-在程序执行过程中，根据设定的条件来决定程序的执

行方向

36

顺序结构分支结构

37

循环结构

(a)While结构(b)Until结构

38

6.5.3编写程序代码

♦编写程序代码

-需要选择合适的编程语言

-按照设计程序过程中形成的算法编写代码

♦选择哪种程序设计语言？

-主要看是否能够完成程序设计任务

-编程人员对这个语言的熟悉程度

39

一个程序代码的例子C语言

include<stdio.h>/*C语言编译系统的库函数7

main()/*程序开始*/

{inti,fac；/*定义变量*/

fac=1;/*变量fac被赋值1*/

for(i=2；i<=5；i++)

/*从2到5,循环执行乘法得到5的阶乘*/

fac=fac*i；

printf("the5!=%d"，fac)；/*输出结果*/

40

一个程序代码的例子VB语言

'定义i、fac为整型数变量

DimiAsInteger,facasinteger

fac=l'变量fac赋值1

'循环，从2到5,每次步长为1

fori=2to5step1

fac=fac*i'计算5的阶乘

nexti

next和for构成循环体

printttfac=,,;fac输出阶乘结果

41

6.5.4寻找错误：程序测试

♦程序设计是复杂的，程序测试也是复杂的

♦此程序测试“是测试程序中的错误，而不

是使得程序中没有错误”！

♦测试方法

-黑盒测试

-白盒测试

♦除非是极为简单的程序，几乎不存在没有

问题的程序！

42

6.5.5编写程序文档

♦程序文档

-对前面所做的各种设计形成完整的手册

-设计程序阶段中形成的流程图、变量列表、代

码、运行结果等编写文档，供日后的程序维护、

升级使用

-程序的功能、操作说明编写成册——程序使用

手册

43

6.5.6运行与维护

♦用户进行培训

♦程序的安装、设置等

♦程序进行修改甚至升级

44

6.6算法

♦程序就是与机器兼容的算法的实现

♦相对于硬件，算法以及实现算法的语言就

是软件

♦算法不仅仅是单纯的问题的分解，它和人

（研究算法的人）的活动——主要是大脑

的活动和行为有关，包括想象、思考、创

造以及选择等

45

6.6.1算法的分类和特性

♦分类：数值运算算法和非数值运算算法

♦特性

-确定性：算法中的每一个步骤都应该是确定的，不应

使不同的编程者对算法中的描述产生不同的理解

-有穷性：算法中的步骤应该是有限的，否则计算机就

会永远无休止地执行程序

-有效性：算法中的每一个步骤都应该被有效地执行，

并应能得到一个明确的结果

-可有零个或多个输入

-有一个或多个输出

46

6.6.2算法的表示

使用图形系统设计算法是目前算法研

究中的一个趋势

♦自然语言

♦流程图

♦结构图

♦伪代码

♦PAD图

47

例1用伪代码表示的求5!的算法

算开始

置的初值为

法P1

置i的初值为2

的当i<=5,执行下面操作:

例使p=p*I

使i=i+1

子（循环体到此结束）

打印出p的值

结束

48

6.6.3流程图表达

例2判断一个整数是否为素数的算法

思路：素数只能被1和它本身整除——判断方法——将n（设n

是要被判断的整数）作为被除数，用2到（n—1）的各个整数

轮流去除，如果都不能整除，贝狂是素数。

自然语言来描述此算法

第一步：输入n的值

第二步：j=2（用j去除n）

第三步：n被j除，得到余数a

第三步：n被j除，得到余数a。

第四步：如a=0,表示n能被j整除，显示信息“n不是素

数”，算法结束；否则进入下一步。

第五步：将j加1送回给j。

第六步：如果jvn,则跳到第三步执行，否则显示“n是

素数”的信息，算法结束

BackOverviewso

*6.6.4自然语言表达

自然语言的算法描述（，同样我们假设P为

被乘数，1%乘数）：

第一步：使P=1

第二步：使i=2

第三步：使p*i，乘积仍放在p中

第四步：使i的值加1再放回至以中

第五步：如果i不大于5,返回重新执行第

三步及其后的步骤，否则，算法结束。最

后得到的p就是5!的值。

51

*6.6.5伪码表达

♦定义——也叫做伪代码表示，不用很正式

的、但在表达上更直观的符号系统表达算

法

♦伪码表示是在程序开发过程中表达算法的

一种非正式的符号系统，只是通过和程序

设计过程一致的、表达简明扼要的语义结

构的方法

52

题

用伪代码表示的求5!的算法:

一开始

-置p的初值为1

-置i的初值为2

-当i〈二5,执行下面循环操作:

-使p=p*I

-使i=i+1

-（循环体到此结束）

-打印出P的值

—结束

6.6.6算法设计

♦有两个阶段

-第一个是设计算法

-第二是这个算法的实现

解决问题技能的基本原理。

1.理解问题

2.设计一个解决问题的方案

3.执行这个方案

4.检验这个方案

54

，个有趣的例子

如果一个旅客持有一个7个环的链子（如图

7.10所示），他必须使用这个链子支付旅

馆的费用，每天一个环。要支付环需要将

环从链子上切割开，哪么怎么切割才能保

证每天支付一个环而切割的次数最少

GG8008D

*6.6.7算法举例

1.迭代结构——建立再循环基础上的算法

♦举例：“判断一个整数是否为素数”的迭代算法

-第1步：输入n的值

-第2步：j=2（准备用j去除n）

-第3步：n被j除,得到余数a

-第4步：如a=0,表示n能被j整除，输出信息“n不是素

数”，算法结束；否则就是n不能被j整除，进入下一

止

少；

-第5步：将j加1送回给j

-第6步：如果j〈n,则跳到第三步执行

-否则输出“n是素数”的信息

-算法结束

56

算法举例

♦递归结构一一把一个或者一类问题分解或分割为

一个个更小的问题，然后解决这些小问题

♦确定迭代算法的方法一一看这个算法定义中是否

包含它本身

57

算法举例

3.排序问题一一迭代的延续应用。把排序按照从小

到大的顺序排列，对未排序的数据进行寻找其

中最小的，然后插入到已经排序的数据的后面

♦步骤

1.从未排序的数据中找出最小的数据

2.取出这个数据，调整未排序数据的存放空间，将这个

空间移交给已经排序的数据表

3.将这个数据放入到新的位置

♦主要的是选择排序和冒泡排序

♦n个数据元素的列表进行排序，最多需要n—1

59

算法举例

4.查找问题

-顺序查找——从列表的第一个数据（或叫做元

素）开始，但给定的数据和表中的数据匹配时,

查找过程结束，给出这个数据所在表中的位置

一折半查找一-也叫二分法，从列表的一半开始,

比较列表处于一半（中间）位置的数据，判断

是在前半部分还是后半部分（根据列表的排序

确定的）

60

*6.8数据表达和数据结构

♦算法最终都需要通过适当的数据表达，以便能够

被计算机所处理

♦数据表达是对数据的符号化表示

-解代数方程的程序，其处理对象是整数和实数

-文字处理程序的处理对象是字符串

♦确定了算法后，要选择合适的数据表达并选择合

适的数据结构，并使用计算机语言处理它们

♦数据结构包括

-逻辑结构、存储结构、和对数据的操作

-按照它的结构形式也可以分为链、表、堆、队、树等

61

6.6.1抽象数据类型与数据结构

♦数据间的结构实际上就是数据元素之间存

在的关系(Relation)

-线性结构(LinearStructure)

-树形结构(TreeStructure)

-图状或网状结构(GraphStructure)

♦结构反映了数据间的逻辑关系，也是对客

观世界中多种多样数据的一种抽象

♦数据的逻辑结构在计算机程序中的实现就

是数据的物理结构，又称存储结构

62

图6.14数据间的结构类型

63

抽象数据类型的，个例子：队列

♦FIFO,FirstInandFistOut)

S6.15

64

6.6.2数组

♦程序设计中也使用变量(Variable)表示

数据

♦数组是在计算机内存中使用一组连续的存

储单元保存数据类型和名字相同的变量

-一维数组

-二维数组

-多维数组

♦使用数组(Array)简化表达相同类型的大

量数据

65

内存地址数组元素内存地址数组元素

Addr+0A[。]Addr+0

Addr+1A[1LAddr+1

Addr+2A[2]

IAddr+m-1

A[n-2]

Addr+n-1A[n-1]Addr+nxm-1

n个元素的一维数组结构nxm个元素的二维数组结构

图6.16数组结构示意图

66

6.6.3链表

♦链表(LinkedList)----构造方式灵活

♦链表中每一个元素包含下一个元素的地址

(address),也就是

-数据为可用信息

-链则把数据元素按顺连在一起，它指明元素列表中下

一个元素所在的位置

♦链表结构：单向，双向表、循环链表等

♦链表与数组的重要区别是

-数组的各元素在内存中是连续存放的

-链表中的各个元素可以处于内存的不同地方

67

664堆栈

♦堆栈(Stack是一种受限制的线性列表

-队列的操作为FIFO

一堆栈的操作为后进先出(LIFO,LastInand

FirstOut)

栈顶

5io152Qv-进栈----

——出松^―►

图6.18含有四个数据元素的堆栈

69

*6.9软件工程简介

♦程序设计仅仅是软件开发工作中的一部分

♦众多