程序设计与算法分析

1、第六章第六章 程序设计与程序设计与算法分析算法分析本章要点本章要点初步了解程序设计的基础知识初步了解程序设计的基础知识掌握结构化程序设计和面向对象程序设计的基本方掌握结构化程序设计和面向对象程序设计的基本方法法掌握数据结构中的基本数据类型及其实现掌握数据结构中的基本数据类型及其实现掌握程序设计算法的基本思想及几种经典的算法掌握程序设计算法的基本思想及几种经典的算法了解编译原理的基本知识了解编译原理的基本知识6.1.1 6.1.1 程序的概念程序的概念 程序程序就是能够实现特定功能的一组指令序列的就是能够实现特定功能的一组指令序列的集合。集合。 程序设计程序设计是程序员编写一系列可存储的指令以是

2、程序员编写一系列可存储的指令以指示计算机完成某些工作的过程。这些指令用指示计算机完成某些工作的过程。这些指令用程序设计语言写成。程序设计语言写成。 程序设计语言程序设计语言是一组专门设计的用来生成一系是一组专门设计的用来生成一系列可被计算机处理和执行的指令的符号集合。列可被计算机处理和执行的指令的符号集合。 程序设计人员用程序设计语言写成的指令称作程序设计人员用程序设计语言写成的指令称作代码代码。6.1 6.1 程序设计基础程序设计基础6.1.2 6.1.2 计算机程序设计语言计算机程序设计语言 分类：分类： 低级语言、高级语言。低级语言、高级语言。1）低级语言包括两种类型：机器语言和汇）低级

3、语言包括两种类型：机器语言和汇编语言。编语言。机器语言机器语言 机器语言面向机器，可以由机器语言面向机器，可以由CPU直接识直接识别和执行。别和执行。 不同的机器能够识别的机器语言是不相不同的机器能够识别的机器语言是不相同的。同的。 机器语言指令都是用一串机器语言指令都是用一串0、1构成的二构成的二进制位串来表示的。进制位串来表示的。 指令系统是机器提供的机器指令的集合。指令系统是机器提供的机器指令的集合。 用二进制编码表示的指令，称为机器指用二进制编码表示的指令，称为机器指令，或称为机器码。令，或称为机器码。 用机器指令编写的程序称为机器语言程用机器指令编写的程序称为机器语言程序，或称为目标

4、程序，这是计算机能够序，或称为目标程序，这是计算机能够直接执行的程序。直接执行的程序。 机器语言难以阅读和理解，编写和修改机器语言难以阅读和理解，编写和修改都比较困难，而且通用性较差。都比较困难，而且通用性较差。汇编语言汇编语言 汇编语言也称符号语言。汇编语言也称符号语言。 指令助记符是指令英文名称的缩写，容指令助记符是指令英文名称的缩写，容易记忆。易记忆。 所谓汇编语言，就是采用字母、数字和所谓汇编语言，就是采用字母、数字和符号来代替由一个个符号来代替由一个个0和和1构成的指令操构成的指令操作码、寄存器、数据和存储地址等，并作码、寄存器、数据和存储地址等，并在程序中用它们代替二进制编码数，这

5、在程序中用它们代替二进制编码数，这样编写出来的程序就称为符号语言程序样编写出来的程序就称为符号语言程序或汇编语言程序。或汇编语言程序。 大多数情况下，一条汇编指令直接对应大多数情况下，一条汇编指令直接对应一条机器指令，少数对应几条机器指令。一条机器指令，少数对应几条机器指令。 汇编语言具有一个本质上与机器语言一汇编语言具有一个本质上与机器语言一一对应的指令系统。汇编语言的实质和一对应的指令系统。汇编语言的实质和机器语言是相同的。机器语言是相同的。低级语言的特点低级语言的特点 都与特定的计算机硬件系统紧密相关，来自都与特定的计算机硬件系统紧密相关，来自于特定系统的指令系统，可移植性差；于特定系统

6、的指令系统，可移植性差； 专业知识要求高，要求对计算机硬件的结构专业知识要求高，要求对计算机硬件的结构和工作原理非常熟悉；和工作原理非常熟悉； 每条指令的功能很单一，程序员编制源程序每条指令的功能很单一，程序员编制源程序时指令比较繁琐；时指令比较繁琐； 由于直接针对特定硬件编程，所以，最终的由于直接针对特定硬件编程，所以，最终的可执行程序代码精炼，而且执行效率非常高。可执行程序代码精炼，而且执行效率非常高。 两者主要的区别在于：机器语言无需翻两者主要的区别在于：机器语言无需翻译或编译，译或编译，CPU能够直接识别和执行。能够直接识别和执行。而汇编语言必须经过汇编才能得到目标而汇编语言必须经过汇

7、编才能得到目标程序。程序。汇编汇编 虽然汇编语言比机器语言容易阅读理解和便于虽然汇编语言比机器语言容易阅读理解和便于检查，所以仍然需要一种特殊的程序，该程序检查，所以仍然需要一种特殊的程序，该程序能够将用汇编语言编写的程序能够将用汇编语言编写的程序“翻译翻译”成成CPU能够识别的机器语言。能够识别的机器语言。 实现这种翻译功能的特殊程序称为实现这种翻译功能的特殊程序称为汇编语言翻汇编语言翻译程序、汇编程序或汇编器译程序、汇编程序或汇编器。程序员手工编写。程序员手工编写的程序统称为源程序，用汇编语言编写的源程的程序统称为源程序，用汇编语言编写的源程序称为汇编语言源程序，汇编程序将源程序翻序称为汇

8、编语言源程序，汇编程序将源程序翻译得到的机器语言程序称为目标程序，翻译的译得到的机器语言程序称为目标程序，翻译的过程称为过程称为汇编汇编。反汇编程序反汇编程序用于将目标代码程序转换成相用于将目标代码程序转换成相应的汇编语言源程序，这一过程称为反应的汇编语言源程序，这一过程称为反汇编。反汇编主要用于识别源程序代码，汇编。反汇编主要用于识别源程序代码，常用的调试工具程序常用的调试工具程序DEBUG就提供了反就提供了反汇编功能。汇编功能。高级语言的产生高级语言的产生 一个问题：如何解决程序的可移植性，即：程一个问题：如何解决程序的可移植性，即：程序员编写的源程序如何可以从一台计算机很容序员编写的源程

9、序如何可以从一台计算机很容易地转到另一台计算机上工作。为了解决这些易地转到另一台计算机上工作。为了解决这些问题，人们引入了高级语言来编写程序。问题，人们引入了高级语言来编写程序。 所谓高级语言是一种由表达各种意义的所谓高级语言是一种由表达各种意义的“词词”和和“公式公式”，按照一定的，按照一定的“语法规则语法规则”来编写来编写程序的语言，又称为程序设计语言或算法语言。程序的语言，又称为程序设计语言或算法语言。 高级语言之所以高级语言之所以“高级高级”，就是因为它使程序，就是因为它使程序员可以完全不用与计算机的硬件打交道，可以员可以完全不用与计算机的硬件打交道，可以不必了解机器的指令系统。不必了

10、解机器的指令系统。 程序员可以把硬件上复杂的概念比如存储空间程序员可以把硬件上复杂的概念比如存储空间抽象成一个所谓的变量之类的概念，因而程序抽象成一个所谓的变量之类的概念，因而程序员就可以绕开硬件问题而集中精力解决问题本员就可以绕开硬件问题而集中精力解决问题本身，编程效率大大提高。身，编程效率大大提高。 由于高级语言与具体机器无关，那么在一种机由于高级语言与具体机器无关，那么在一种机器上运行的高级语言程序可以几乎不经改动地器上运行的高级语言程序可以几乎不经改动地移植到另一种机器上运行，大大提高了程序的移植到另一种机器上运行，大大提高了程序的通用性。通用性。 此外，由于高级语言与自然语言此外，由

11、于高级语言与自然语言(尤其是英语尤其是英语)很相似，因此易学、易懂，也易编写。很相似，因此易学、易懂，也易编写。高级语言的常见类型高级语言的常见类型 目前已经有许多高级语言在流行，并且目前已经有许多高级语言在流行，并且新的类型还在不断出现和升级。新的类型还在不断出现和升级。 用户在实际应用中进行程序设计时，可用户在实际应用中进行程序设计时，可根据情况选择适合的高级语言。根据情况选择适合的高级语言。 (1) BASIC语言语言 (2) FORTRAN语言语言 (3) COBOL语言语言 (4) PASCAL语言语言 (5) C语言语言 (6) C+语言语言 (7) 其他高级语言其他高级语言 基于

12、视窗类操作系统的，如基于视窗类操作系统的，如Visual Basic、Visual C+、Delphi、Power Builder、Java等等等。等。 高级语言的优点是语句的功能强，源程序比较高级语言的优点是语句的功能强，源程序比较短，容易学习，使用方便，通用性较强，便于短，容易学习，使用方便，通用性较强，便于推广和交流。推广和交流。 其缺点是编译程序比汇编程序复杂，而且编译其缺点是编译程序比汇编程序复杂，而且编译出来的目标程序往往效率不高，目标程序的长出来的目标程序往往效率不高，目标程序的长度比有经验的程序员所编的同样功能的汇编语度比有经验的程序员所编的同样功能的汇编语言程序要长言程序要长

13、半以上，运行时间也要长一些。半以上，运行时间也要长一些。 因此，在很多对时间要求比较高的系统，如某因此，在很多对时间要求比较高的系统，如某些实时控制系统或者大型计算机控制系统中，些实时控制系统或者大型计算机控制系统中，低级语言，主要是汇编语言，仍然得到了一定低级语言，主要是汇编语言，仍然得到了一定的应用。的应用。6.1.3 6.1.3 高级语言的基本内容高级语言的基本内容 高级程序设计语言依赖于各自特定的语句和语高级程序设计语言依赖于各自特定的语句和语法。一条一条的语句是构成源程序的基本单位。法。一条一条的语句是构成源程序的基本单位。高级语言的一条语句被编译或解释时往往会对高级语言的一条语句被

14、编译或解释时往往会对应多条机器指令。应多条机器指令。 每一种编程语言都包含一组语句和语法。所谓每一种编程语言都包含一组语句和语法。所谓语法，是指管理语言结构和语句的一组规则。语法，是指管理语言结构和语句的一组规则。不论使用何种设计语言，都必须遵循其语法规不论使用何种设计语言，都必须遵循其语法规则。则。 以下内容主要描述了大多数高级语言都共同具以下内容主要描述了大多数高级语言都共同具备的特性，但不一定是所有高级语言都有的。备的特性，但不一定是所有高级语言都有的。1 1高级语言的基本符号高级语言的基本符号 高级语言都是由所谓的基本符号组成的。基本高级语言都是由所谓的基本符号组成的。基本符号可以分为

15、单字符和多字符两种情况。单字符号可以分为单字符和多字符两种情况。单字符基本符号由单个字符组成，在高级语言中通符基本符号由单个字符组成，在高级语言中通常都有下列几种单字符基本符号：常都有下列几种单字符基本符号： (1) 字母字母 大写英文字母大写英文字母AZ，小写英文字母，小写英文字母az，共，共52个符号。个符号。 (2) 数字数字 09，共，共10个数字符号。个数字符号。 (3)特殊字符特殊字符 (加加)，(减减)，*(乘乘)，/(除除)，(乘方乘方)，(等号等号)，(左括号左括号)，)(右括号右括号)，(大大于于)，(小于小于)，(逗号逗号)，(空格空格)等。等。 在高级语言中的多字符基本

16、符号由两个在高级语言中的多字符基本符号由两个或两个以上的字符组成，例如或两个以上的字符组成，例如GoTo(转转移移)、(小于或等于小于或等于)、AND(与与)等等。等等。2 2高级语言的基本元素高级语言的基本元素 基本元素由基本符号组成，可分为数、基本元素由基本符号组成，可分为数、逻辑值、名字、标号和字符串等五大类。逻辑值、名字、标号和字符串等五大类。 (1) 数数 它由它由09共共10个基本数字和其他一些符个基本数字和其他一些符号号(如小数点如小数点“.”、正负号、正负号“、”及及指数符号指数符号“E”等所构成。等所构成。 (2) 逻辑值逻辑值 由真由真(True)和假和假(False)两个

17、值表示。两个值表示。 (3) 名字名字 由字符组成，一般约定名字的开头是字母或者由字符组成，一般约定名字的开头是字母或者下划线，其后可为字母或数字，如下划线，其后可为字母或数字，如XYZ、A123、_C等。名字可用来定义常量、变量、等。名字可用来定义常量、变量、函数、过程或子程序的，也被用来定义成某些函数、过程或子程序的，也被用来定义成某些东西，故也称为标识符。在高级语言中，一般东西，故也称为标识符。在高级语言中，一般还规定了组成名字的字符的长度，即字符个数。还规定了组成名字的字符的长度，即字符个数。 (4) 标号标号 是在高级语言中的程序语句前所加的一个名字，是在高级语言中的程序语句前所加的

18、一个名字，主要用来指示程序可能的转移方向。主要用来指示程序可能的转移方向。 (5) 字符串字符串 由一串字符所组成。在不同的高级语言由一串字符所组成。在不同的高级语言中，字符串中的多个字符放在一对单引中，字符串中的多个字符放在一对单引号或双引号中。号或双引号中。3 3基本的数据类型基本的数据类型 任何一种高级语言都会定义一些基本的任何一种高级语言都会定义一些基本的数据类型。基本的数据类型通常包括整数据类型。基本的数据类型通常包括整数数据类型、实数数据类型和字符数据数数据类型、实数数据类型和字符数据类型等。类型等。 在程序中，除了值无需改变的常数外，在程序中，除了值无需改变的常数外，大部分数据的

19、值是可以修改的。在程序大部分数据的值是可以修改的。在程序中，中，变量变量是指代表某个具体数值，并且是指代表某个具体数值，并且所代表的数值可改变的一个符号名字。所代表的数值可改变的一个符号名字。 变量必须先定义，然后才能使用，这是变量必须先定义，然后才能使用，这是条基条基本原则。本原则。 变量实质上代表了一个特定大小的内存单元空变量实质上代表了一个特定大小的内存单元空间。间。 定义变量的实质就是让程序为该变量分配一个定义变量的实质就是让程序为该变量分配一个特定的内存空间。特定的内存空间。 变量的类型实质上反映了该数据占用内存空间变量的类型实质上反映了该数据占用内存空间的大小，即分配给该变量代表的

20、数据的所占据的大小，即分配给该变量代表的数据的所占据的内存单元的字节数目。的内存单元的字节数目。4 4结构数据类型结构数据类型 是在基本数据类型的基础上构造出来的数据类是在基本数据类型的基础上构造出来的数据类型。数组和结构体是大多数高级语言都支持的型。数组和结构体是大多数高级语言都支持的两种最基本的结构数据类型。两种最基本的结构数据类型。 (1) 数组类型数组类型 数组是若干个相同类型的数据的集合。数组是若干个相同类型的数据的集合。 (2) 用户自定义的结构体类型用户自定义的结构体类型 结构体是隶属于同一个事物的多个不同类型的结构体是隶属于同一个事物的多个不同类型的数据的集合，用来表示具有若干

21、个属性的一个数据的集合，用来表示具有若干个属性的一个事物。事物。 除了以上两种最基本的结构数据类型外，许多除了以上两种最基本的结构数据类型外，许多高级语言还有比如枚举、集合，以及更复杂的高级语言还有比如枚举、集合，以及更复杂的队列、堆栈等多种数据类型。队列、堆栈等多种数据类型。 结构数据类型在使用时也必须定义相应类型的结构数据类型在使用时也必须定义相应类型的“变量变量”名字。名字。5 5运算符与表达式运算符与表达式 表达式是由基本符号、基本元素和各种数据通表达式是由基本符号、基本元素和各种数据通过各种运算符连接而成的。按表达式的运算结过各种运算符连接而成的。按表达式的运算结果可以分为果可以分为

22、算术表达式、逻辑表达式和字符串算术表达式、逻辑表达式和字符串表达式表达式等几种情况。等几种情况。 高级语言中的运算符大致包括以下几个方面：高级语言中的运算符大致包括以下几个方面： (1) 逻辑运算：逻辑运算：与、或、非、异或。与、或、非、异或。 (2) 算术运算：算术运算：加、减、乘、除、取模。加、减、乘、除、取模。 (3) 数据比较：数据比较：大于、小于、等于、不等于。大于、小于、等于、不等于。 (4) 数据传送；数据传送；输入、输出、赋值。输入、输出、赋值。 (5) 算术表达式：算术表达式：该表达式的运算结果是数，该表达式的运算结果是数，它非常近似于日常的数学公式。它非常近似于日常的数学公

23、式。 (6) 关系运算表达式：关系运算表达式：该表达式的运算结果是该表达式的运算结果是逻辑值，常用的运算符包含逻辑值，常用的运算符包含(大于大于)、(小小于于)、(等于等于)、(小于等于小于等于)、(大于等大于等于于)、不等于。、不等于。 (7) 字符串表达式：字符串表达式：该表达式的运算结果是字该表达式的运算结果是字符串。符串。6 6语句语句 语句是构成高级语言源程序的基本单位，语句是构成高级语言源程序的基本单位，是由基本元素、运算符、表达式等组成。是由基本元素、运算符、表达式等组成。任何一种高级语言往往都支持赋值、条任何一种高级语言往往都支持赋值、条件判断、循环、输入输出等语句。程序件判断

24、、循环、输入输出等语句。程序员利用这些语句的结合，能够很方便地员利用这些语句的结合，能够很方便地编制出功能强大的程序。编制出功能强大的程序。7 7库函数和用户自定义的函数库函数和用户自定义的函数 为了支持用户编写出功能强大的源程序，为了支持用户编写出功能强大的源程序，几乎所有的高级语言都为用户提供了丰几乎所有的高级语言都为用户提供了丰富的库函数，这些库函数能够实现某些富的库函数，这些库函数能够实现某些特定的功能，比如计算一个比较复杂的特定的功能，比如计算一个比较复杂的数学函数。数学函数。 在源程序中，用户也可以自己定义自己在源程序中，用户也可以自己定义自己的函数的函数 (子程序或过程子程序或过

25、程)，以便以后可以，以便以后可以反复调用这些代码集合。反复调用这些代码集合。8 8注释注释 任何一种程序设计语言都强调注释的重要性。任何一种程序设计语言都强调注释的重要性。源程序所包含的代码往往比较冗长，添加必要源程序所包含的代码往往比较冗长，添加必要的注释不仅有助于阅读程序，更重要的是，在的注释不仅有助于阅读程序，更重要的是，在需要对程序功能进行扩充时，注释可以极大地需要对程序功能进行扩充时，注释可以极大地帮助程序员对原始程序的理解。帮助程序员对原始程序的理解。 经常会出现这样一种情况，程序员自己编写的经常会出现这样一种情况，程序员自己编写的程序，经过一段时间后，可能就是半年或者几程序，经过

26、一段时间后，可能就是半年或者几个月以后，程序员自己也读不懂自己的程序了。个月以后，程序员自己也读不懂自己的程序了。况且，程序不仅要自己看得懂，更重要的是也况且，程序不仅要自己看得懂，更重要的是也要让别人能够看懂。要让别人能够看懂。9 9程序设计风格程序设计风格(1) 编码格式和编码约定在整个程序中应保持一致。编码格式和编码约定在整个程序中应保持一致。(2) 程序中应给出必要的注释，尤其在变量定义、调用接口、参程序中应给出必要的注释，尤其在变量定义、调用接口、参数传递处，在修改程序时应注明修改人、时间、简要的修改原因。数传递处，在修改程序时应注明修改人、时间、简要的修改原因。(3) 对变量、函数

27、标识等的命名，采用规范的命名方法，避免含对变量、函数标识等的命名，采用规范的命名方法，避免含义不明确的缩写，从命名最好就可以一目了然读出命名标识的含义不明确的缩写，从命名最好就可以一目了然读出命名标识的含义和数据类型。义和数据类型。(4) 采用缩进格式，突出程序的逻辑层次结构。采用缩进格式，突出程序的逻辑层次结构。(5) 每一行只写一条语句，使用括号间隔表达式或语句的组成部每一行只写一条语句，使用括号间隔表达式或语句的组成部分，使组成部分清晰；分，使组成部分清晰；(6) 使用结构化、面向对象的编程技术，提高程序可重用性、可使用结构化、面向对象的编程技术，提高程序可重用性、可扩充性。扩充性。(7

28、) 除非完全必要，应尽量避免多任务和多重处理。除非完全必要，应尽量避免多任务和多重处理。(8) 尽量避免使用复杂的算术和逻辑表达式。尽量避免使用复杂的算术和逻辑表达式。(9) 提高程序健壮性，预防用户的操作错误，做到废进废出。提高程序健壮性，预防用户的操作错误，做到废进废出。 1010高级语言程序的运行高级语言程序的运行 使用高级语言编制程序的一般过程可以归纳为使用高级语言编制程序的一般过程可以归纳为以下几个步骤：以下几个步骤： (1) 使用文本编辑工具，逐条编写源程序的语使用文本编辑工具，逐条编写源程序的语句。存储源程序文件时文件的后缀名与所用的句。存储源程序文件时文件的后缀名与所用的高级语

29、言有关。高级语言有关。 (2) 编译源程序文件，生成目标文件，文件后编译源程序文件，生成目标文件，文件后缀名通常为缀名通常为obj。 (3) 链接目标文件，生成可执行文件，文件后链接目标文件，生成可执行文件，文件后缀名通常为缀名通常为exe。 (4) 在计算机上执行可执行程序文件，进在计算机上执行可执行程序文件，进步步调试和维护。调试和维护。6.2.1 6.2.1 结构化程序设计方法结构化程序设计方法 采用自顶向下、逐步求精的设计方法和单入口单出口的控制结构。1. 1. 结构化程序设计思想结构化程序设计思想 . . . . . . 二级子问题 二级子问题 二级子问题 需要解决的复杂问题 三级子

30、问题 三级子问题 三级子问题 . . . . . . . . . 最小问题 最小问题 最小问题 结构化程序设计的结构化程序设计的原则原则是：是： (1) 使用顺序、选择、循环使用顺序、选择、循环3种基本控制种基本控制结构表示程序逻辑。结构表示程序逻辑。 (2)程序语句组织成容易识别的语句模块，程序语句组织成容易识别的语句模块，每个模块都是单入口、单出口。每个模块都是单入口、单出口。 (3)严格控制严格控制GOTO语句的使用。语句的使用。(a) 顺序结构 (b) 选择结构 (c) while循环 (d) do-while循环 A B 出口 假 真 入口 A B S 假 真 入口 S A 出口 假

31、 真 入口 A S 2 2模块模块 一个复杂的问题可以划分为多个简单问题的组一个复杂的问题可以划分为多个简单问题的组合。合。 在自顶向下、逐步细化的过程中，把复杂问题在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块分解成一个个简单问题的最基本方法就是模块化。化。 模块化便于问题的分析，模块体现了信息隐藏模块化便于问题的分析，模块体现了信息隐藏的概念。模块常用子程序加以实现。的概念。模块常用子程序加以实现。1 1面向对象的思想面向对象的思想6.2.2 6.2.2 面向对象的程序设计方法面向对象的程序设计方法 OO(Object Oriented，面向对象，面向对象

32、)的程序的程序设计把客观事物看作具有属性和行为的设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同对象，通过抽象找出同一类对象的共同属性属性(静态特征静态特征)和行为和行为(动态特征动态特征)，形成，形成类。类。2 2对象和类对象和类 对象对象 是对现实问题的高度概括、分类和是对现实问题的高度概括、分类和抽象。每个对象都只有自己的数据和相抽象。每个对象都只有自己的数据和相应的处理函数，整个程序是由一系列相应的处理函数，整个程序是由一系列相互作用的对象来构成，不同对象之间是互作用的对象来构成，不同对象之间是通过发送消息来实现相互联系、相互作通过发送消息来实现相互联系、相互作用。

33、用。 方法方法 在对象内的操作通常叫做方法。在对象内的操作通常叫做方法。 类 定义了一组大体上相似的对象。一个类定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行所包含的方法和数据描述一组对象的共同行为和属性。为和属性。 对象则是类的具体化，是类的实例。对象则是类的具体化，是类的实例。 类通过派生可以有子类，同样也可以有父类，类通过派生可以有子类，同样也可以有父类，形成层次结构。形成层次结构。3 3抽象抽象 抽象 是对具体事物是对具体事物(即对象即对象)进行概括，进行概括，即忽略事物的非本质特征，只注意那些即忽略事物的非本质特征，只注意那些与当前目标有关的本质特征，从而抽

34、象与当前目标有关的本质特征，从而抽象出一类对象的共性并加以描述。出一类对象的共性并加以描述。 对一个问题的抽象一般来讲应该包对一个问题的抽象一般来讲应该包括两个方面：数据抽象和代码抽象括两个方面：数据抽象和代码抽象(或称或称为行为抽象为行为抽象)。4 4封装性封装性 封装的两个含义封装的两个含义： 第一是，将抽象得到的数据成员和代码成第一是，将抽象得到的数据成员和代码成员相结合，形成一个不可分割的整体，即对象，员相结合，形成一个不可分割的整体，即对象，这种数据及行为的有机结合也就是封装。这种数据及行为的有机结合也就是封装。 第二个含义称为信息隐蔽，即尽可能隐蔽第二个含义称为信息隐蔽，即尽可能隐

35、蔽对象的内部细节。在隐蔽对象内部细节的同时，对象的内部细节。在隐蔽对象内部细节的同时，对象需要提供与外部世界进行交流的接口，并对象需要提供与外部世界进行交流的接口，并实现对数据访问权限的合理控制，把整个程序实现对数据访问权限的合理控制，把整个程序中不同部分的相互影响减少到最低限度。中不同部分的相互影响减少到最低限度。5 5继承性继承性 继承性继承性 是父类和子类之间共享数据和方法的机制。是父类和子类之间共享数据和方法的机制。在定义一个类的时候，可以以一个已经存在的在定义一个类的时候，可以以一个已经存在的类为基础，并把这个已经存在的类所包含的属类为基础，并把这个已经存在的类所包含的属性和方法作为

36、自身的一部分，然后加入新的属性和方法作为自身的一部分，然后加入新的属性和方法以区别于原来的类。性和方法以区别于原来的类。 原有的类称为原有的类称为基类或父类基类或父类，产生的新类，产生的新类称为称为派生类派生类。6 6多态性多态性 多态性多态性 在收到外部消息时，对象通常要予在收到外部消息时，对象通常要予以响应。不同的对象收到同一消息可能以响应。不同的对象收到同一消息可能产生完全不同的结果。产生完全不同的结果。1 1数据、数据类型数据、数据类型 数据数据 是对客观事物的符号表示。在计算机系统是对客观事物的符号表示。在计算机系统内，数据通常是指能够输入到计算机中并被计内，数据通常是指能够输入到计

37、算机中并被计算机进行处理的符号的集合。算机进行处理的符号的集合。 数据类型数据类型 是指具有相同取值范围和可以实施同种操是指具有相同取值范围和可以实施同种操作的数据的集合的总称。例如，在程序设计中，作的数据的集合的总称。例如，在程序设计中，通常会有字符型、整型、数组等多种数据类型。通常会有字符型、整型、数组等多种数据类型。6.3.1 6.3.1 基本概念基本概念6.3 6.3 数据结构数据结构2 2数据元素、数据项、数据对象数据元素、数据项、数据对象 能够独立并完整地描述客观世界实体的基本数能够独立并完整地描述客观世界实体的基本数据单元称为据单元称为数据元素数据元素，它是组成数据的基本单，它是

38、组成数据的基本单位。位。 数据项数据项是组成数据元素的不可分割的最小单位。是组成数据元素的不可分割的最小单位。最简单的数据元素就是由一个数据项构成的。最简单的数据元素就是由一个数据项构成的。 同类数据元素的集合称为同类数据元素的集合称为数据对象数据对象。3 3数据结构数据结构 数据结构 是指数据元素之间的相互关系的集是指数据元素之间的相互关系的集合，包括了数据的逻辑结构、物理结构合，包括了数据的逻辑结构、物理结构以及数据的运算。以及数据的运算。 数据的逻辑结构 数据的逻辑结构是指数据元素之间数据的逻辑结构是指数据元素之间的逻辑关系。数据之间可以根据不同的的逻辑关系。数据之间可以根据不同的关系组

39、成不同的数据结构。关系组成不同的数据结构。 线性结构线性结构 数据结构中，如果数据元素之间存在着前后顺序的数据结构中，如果数据元素之间存在着前后顺序的关系，即除了第一个数据元素和最后一个元素外，其关系，即除了第一个数据元素和最后一个元素外，其他每个元素都有惟一的一个前驱和一个后继元素，这他每个元素都有惟一的一个前驱和一个后继元素，这样的数据元素之间的关系被称为线性结构。样的数据元素之间的关系被称为线性结构。 树形结构树形结构 数据结构中，如果数据元素之间有顺序关系，且数据结构中，如果数据元素之间有顺序关系，且除了一个被称为根节点的元素外，每个元素都有一个除了一个被称为根节点的元素外，每个元素都

40、有一个前驱节点，并且可以有多个后继节点，这种逻辑结构前驱节点，并且可以有多个后继节点，这种逻辑结构称为树形结构。称为树形结构。 图形结构图形结构 数据结构中，如果任何一个数据元素都可以有多个数据结构中，如果任何一个数据元素都可以有多个前驱节点和多个后继节点，这种逻辑结构称为图形结前驱节点和多个后继节点，这种逻辑结构称为图形结构。构。 (2) 数据的物理结构 数据的物理结构是指逻辑结构在计数据的物理结构是指逻辑结构在计算机存储器中的表示。数据的物理结构算机存储器中的表示。数据的物理结构不仅要存储数据本身，还要存储表示数不仅要存储数据本身，还要存储表示数据间的逻辑关系。据间的逻辑关系。 数据的物理

41、结构主要有四种，分别数据的物理结构主要有四种，分别是顺序结构、链表结构、索引结构及散是顺序结构、链表结构、索引结构及散列结构。列结构。 顺序结构顺序结构 把所有元素存放在一片连续的存储单元中，把所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存储在物理位置相邻的存储逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结单元中，由此得到的存储表示称为顺序存储结构。构。 顺序存储结构常借助于程序设计语言中顺序存储结构常借助于程序设计语言中的数组来实现。优点是使用方法简单，缺点是的数组来实现。优点是使用方法简单，缺点是必须预先分析出所需定义数组的大小。必须预先分析出所需

42、定义数组的大小。 链表结构链表结构 对逻辑上相邻的元素不要求其物理对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设位置相邻，元素间的逻辑关系通过附设的指针域来实现，由此得到的存储表示的指针域来实现，由此得到的存储表示称为链式存储结构。称为链式存储结构。 链式存储结构通常借助于程序设计链式存储结构通常借助于程序设计语言中的指针来实现。语言中的指针来实现。 索引结构索引结构 针对每个数据结构建立一张所谓的针对每个数据结构建立一张所谓的索引表，每个数据元素占用表中的一项，索引表，每个数据元素占用表中的一项，每个表项包含一个能够惟一识别一个元每个表项包含一个能够惟一识别一个元素的关键字

43、和用以指示该元素的地址指素的关键字和用以指示该元素的地址指针。针。 散列结构散列结构 通过构造相应的散列函数，由散列通过构造相应的散列函数，由散列函数的值来确定元素存放的地址。函数的值来确定元素存放的地址。 (3) 数据运算数据运算 数据操作的集合。常见的数据操作数据操作的集合。常见的数据操作有数据的插入、删除、查找、遍历等。有数据的插入、删除、查找、遍历等。 数据操作通常由计算机程序加以实数据操作通常由计算机程序加以实现，通常也叫现，通常也叫算法实现算法实现。6.3.2 6.3.2 线性表线性表 1定义定义 线性表线性表是由有限个相同的数据元素构成的序列，是由有限个相同的数据元素构成的序列，

44、元素之间是一对一的线性关系，除了第一个元素元素之间是一对一的线性关系，除了第一个元素只有直接后继、最后一个元素只有直接前驱外，只有直接后继、最后一个元素只有直接前驱外，其余数据元素都有一个直接前驱和一个直接后继，其余数据元素都有一个直接前驱和一个直接后继，如图。如图。 元素 1 uansu 元素 2 1 元素 3 1 元素 n 1 ua 2运算和实现运算和实现 线性表通常采用顺序和链表两种物线性表通常采用顺序和链表两种物理实现。对于经常变化的表，通常采取理实现。对于经常变化的表，通常采取链表结构。线性表常用的运算主要有：链表结构。线性表常用的运算主要有：插入、删除、查询和遍历。插入、删除、查询

45、和遍历。 插入插入 在保持原有的存储结构的前提下，根据插在保持原有的存储结构的前提下，根据插入要求，在适当的位置插入一个元素。插入操入要求，在适当的位置插入一个元素。插入操作要求线性表要有足够的存放新元素的空间，作要求线性表要有足够的存放新元素的空间，如果空间不足，插入操作无法进行，线性表会如果空间不足，插入操作无法进行，线性表会溢出。溢出。 删除删除 在线性表中，找到满足条件的数据元素，在线性表中，找到满足条件的数据元素，并删除。如果线性表为空，删除就会失败。并删除。如果线性表为空，删除就会失败。 查询查询 在线性表中，按照查询条件，定位数据在线性表中，按照查询条件，定位数据元素的过程就是查

46、询。查询的条件一般根据数元素的过程就是查询。查询的条件一般根据数据元素中的关键字进行。实际上，数据的插入据元素中的关键字进行。实际上，数据的插入和删除都需要首先定位数据元素。对于空的线和删除都需要首先定位数据元素。对于空的线性表是无法查询的。性表是无法查询的。 遍历遍历 是指按照某种方式，逐一访问线性表中是指按照某种方式，逐一访问线性表中的每一个数据元素，并执行相同处理的操作。的每一个数据元素，并执行相同处理的操作。这里的处理可以是读、写、或查询等。这里的处理可以是读、写、或查询等。6.3.3 6.3.3 栈栈 1定义定义 对于由对于由N个数据元素构成的一个线性序列，个数据元素构成的一个线性序

47、列，如果只允许在其固定的一端位置插入和删除一如果只允许在其固定的一端位置插入和删除一个数据元素，那么这种逻辑结构的数据结构称个数据元素，那么这种逻辑结构的数据结构称为为堆栈或栈堆栈或栈(stack)。 允许插入或删除的这一端称为允许插入或删除的这一端称为栈项栈项，另一，另一个固定端称为个固定端称为栈底栈底。当表中没有元素时称为。当表中没有元素时称为空空栈栈。2 2运算和实现运算和实现 栈的基本运算主要有：入栈、出栈和判断。栈的基本运算主要有：入栈、出栈和判断。 入栈入栈 入栈也叫压栈，是在栈顶添加新元素的操入栈也叫压栈，是在栈顶添加新元素的操作，新的元素入栈后成为新的栈顶元素。作，新的元素入栈

48、后成为新的栈顶元素。 出栈出栈 出栈也叫退栈或弹栈，是将栈顶元素从栈出栈也叫退栈或弹栈，是将栈顶元素从栈中退出并传递给用户程序的操作中退出并传递给用户程序的操作 D C B A 入栈数据元素 E E D C B A D C B A 出栈数据元素D C B A 判断判断 判断操作用来检查栈内数据是否为判断操作用来检查栈内数据是否为空，返回结果是一个逻辑值：真或假。空，返回结果是一个逻辑值：真或假。如果栈顶和栈底重合，说明堆栈为空。如果栈顶和栈底重合，说明堆栈为空。6.3.4 6.3.4 队列队列 1定义定义 对于由对于由N个数据元素构成的一个线个数据元素构成的一个线性序列，如果在其固定的一端只允

49、许插性序列，如果在其固定的一端只允许插入数据元素，且在另一端只允许删除数入数据元素，且在另一端只允许删除数据元素，则这种逻辑结构的数据结构称据元素，则这种逻辑结构的数据结构称为为队列队列(queue)。 把允许插入的一端叫把允许插入的一端叫队尾队尾(rear)，把，把只允许删除的一端叫只允许删除的一端叫队首队首(front)。2 2运算运算 队列的基本运算主要有：入队、出队和判断。队列的基本运算主要有：入队、出队和判断。 入队入队 入队是在队列中插入一个新数据元素的过入队是在队列中插入一个新数据元素的过程，插入在队尾进行，新的元素成为队尾，。程，插入在队尾进行，新的元素成为队尾，。 出队出队

50、出队是在队列中删除一个数据元素的过程，出队是在队列中删除一个数据元素的过程，删除在队首进行并把出来的数据传递给用户程删除在队首进行并把出来的数据传递给用户程序。序。 A B C D E 头指针 尾指针 A B C D E F G 头指针 尾指针 F，G入队 A B C D E 头指针 尾指针 D E F G 头指针 尾指针 A，B，C 出队 判断：判断： 判断操作用来检查队列是否为空，返判断操作用来检查队列是否为空，返回结果是一个逻辑值：真或假，如图。回结果是一个逻辑值：真或假，如图。 头 指 针 尾 指 针 3 3循环队列的实现循环队列的实现 F G A B C D E 头指针 尾指针 内存

51、块第一个存储单元 内存块最后一个存储单元 队列移动 6.3.5 6.3.5 树树 1定义定义 树形数据结构中，每个数据元素称树形数据结构中，每个数据元素称为是一个节点，除了一个惟一的所谓为是一个节点，除了一个惟一的所谓根根节点节点外，其他每个节点都有且只有一个外，其他每个节点都有且只有一个父节点，每个元素可以有多个子节点。父节点，每个元素可以有多个子节点。 树主要用在大型、动态列表的搜索，树主要用在大型、动态列表的搜索，人工智能系统和编码算法等问题中。人工智能系统和编码算法等问题中。2 2运算运算 树常见的基本运算有：插入、删除和遍历。树常见的基本运算有：插入、删除和遍历。 插入插入 在树中合

52、适的位置，添加一个节点，通常插入新在树中合适的位置，添加一个节点，通常插入新的节点后，仍然应该保持该树本身所具有的性质。的节点后，仍然应该保持该树本身所具有的性质。 删除删除 在树中找到满足条件的节点并删除。通常删除节在树中找到满足条件的节点并删除。通常删除节点后，也要保持该树本身所具有的性质。点后，也要保持该树本身所具有的性质。 遍历遍历 按照某种顺序或规则，对树中的每个节点逐一进按照某种顺序或规则，对树中的每个节点逐一进行访问的过程。行访问的过程。3 3实现实现 Left A Right Left B Right C Right D E F 6.3.6 6.3.6 图图 1定义定义 在图形

53、结构中，每个数据元素称为一个顶在图形结构中，每个数据元素称为一个顶点，任意两个顶点之间都可能相关，这种相关点，任意两个顶点之间都可能相关，这种相关性用一条边来表示，顶点之间的邻接关系可以性用一条边来表示，顶点之间的邻接关系可以是任意的。是任意的。 图可以用来描述计算机网络的拓扑结构，图可以用来描述计算机网络的拓扑结构，以及图论中获得最小生成树。除此以外，图在以及图论中获得最小生成树。除此以外，图在自然科学、社会科学和人文科学等许多领域也自然科学、社会科学和人文科学等许多领域也都有着非常广泛的应用。都有着非常广泛的应用。2 2运算运算 常见的基本运算有：添加顶点、删除顶点、添常见的基本运算有：添

54、加顶点、删除顶点、添加边、删除边和遍历图。加边、删除边和遍历图。 添加顶点添加顶点 在图中添加新的顶点，新添加的顶点通常在图中添加新的顶点，新添加的顶点通常是孤立的节点，还没有边连接。是孤立的节点，还没有边连接。 删除顶点删除顶点 在图中去掉一个顶点，显然，在去掉一个在图中去掉一个顶点，显然，在去掉一个顶点的同时还应该删除与该顶点所连接的边。顶点的同时还应该删除与该顶点所连接的边。 添加边添加边 根据指定的顶点，添加相应的边。根据指定的顶点，添加相应的边。 删除边删除边 根据指定的顶点，删除相应的边。根据指定的顶点，删除相应的边。 遍历图遍历图 按照一定的规则，对图中的每个数按照一定的规则，对

55、图中的每个数据顶点逐一进行访问。据顶点逐一进行访问。3 3实现实现 图通常用数组和链表两种结构加以实现。图通常用数组和链表两种结构加以实现。对于各个顶点和顶点之间的关系分别采对于各个顶点和顶点之间的关系分别采用邻接矩阵和邻接列表来进行描述。用邻接矩阵和邻接列表来进行描述。 A B C D E A B E B A C E C B D E A B D D C E 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 A B C D E A B C D E (a) (b) (c) 6.4.1 6.4.1 概述概述 1算法的定义算法的定义 准确地说，准确地

56、说，“算法算法(Algorithm)是一组明确是一组明确的、可以执行的步骤的有序集合，它在有限的的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果时间内终止并产生结果”。 算法和数据结构之间存在密切联系。数据结构算法和数据结构之间存在密切联系。数据结构是算法的基础，数据结构的不同，通常的采用是算法的基础，数据结构的不同，通常的采用的算法也会不同；当问题的求解算法一旦确定，的算法也会不同；当问题的求解算法一旦确定，也可以选择合适的数据结构加以实现，合理的也可以选择合适的数据结构加以实现，合理的数据结构能够简化算法。数据结构能够简化算法。6.4 6.4 算法分析基础算法分析基础 (1)

57、有穷性有穷性(可终止性可终止性) 一个算法必须在有限个操作步骤内以及合一个算法必须在有限个操作步骤内以及合理的时间内执行完成。理的时间内执行完成。 (2) 确定性确定性 算法中的每一个操作步骤都必须有明确的算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。含义，不允许存在二义性。 (3) 有效性有效性(可执行性可执行性) 算法中描述的操作步骤都是可执行的，并算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。能最终得到确定的结果。 (4) 输入及输出输入及输出 一个算法应该有零个或多个输入数据、有一个算法应该有零个或多个输入数据、有1个或多个输出数据。个或多个输出数据。2算法的

58、特性算法的特性3 3算法的描述算法的描述(1) 自然语言表示自然语言表示 自然语言就是人们日常使用的语言，可以自然语言就是人们日常使用的语言，可以是中文、英文等。是中文、英文等。 例如，求三个数中最大值的问题，可以描述为：例如，求三个数中最大值的问题，可以描述为： 比较前两个数；比较前两个数； 将将中较大的数与第三个数进行比较；中较大的数与第三个数进行比较； 步骤步骤中较大的数即为所求。中较大的数即为所求。 (2) 流程图表示流程图表示 流程图是用规定的一组图形符号、流程线流程图是用规定的一组图形符号、流程线和文字说明来表示算法的一种表示方法。和文字说明来表示算法的一种表示方法。 (3) 伪码

59、伪码 伪码用一种介于自然语言与计算机语言之伪码用一种介于自然语言与计算机语言之间的文字和符号来描述算法。比计算机语言形间的文字和符号来描述算法。比计算机语言形式灵活，格式紧凑，没有严格的语法。式灵活，格式紧凑，没有严格的语法。 (4) 程序设计语言形式程序设计语言形式 算法也可以用某种具体的计算机程序设计算法也可以用某种具体的计算机程序设计语言来表示，如，语言来表示，如，C、C+、Java等都可以用等都可以用来描述算法。来描述算法。 例如，求两个数的较大者。用伪代码描述算法例如，求两个数的较大者。用伪代码描述算法如下：如下： Input: two number s:a,b 1.if (the

60、first number a is greater than or equal to the second number b) then 1.1 return a else 1.2 return b end if end6.4.2 6.4.2 常用算法介绍常用算法介绍 1递归算法递归算法 如果一个过程直接或间接地调用它如果一个过程直接或间接地调用它本身，则称该过程是递归的。本身，则称该过程是递归的。 例如，数学阶乘运算，可以用递归算法例如，数学阶乘运算，可以用递归算法定义函数定义函数f (n)如下：如下：1!(1)!nn n 递归的情况包括所谓的递推法和分治法。递归的情况包括所谓的递推法和分治