计算机科学导论第6章程序设计与算法分析.ppt

《计算机科学导论第6章程序设计与算法分析.ppt》由会员分享，可在线阅读，更多相关《计算机科学导论第6章程序设计与算法分析.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、器语言和汇编语）低级语言包括两种类型：机器语言和汇编语言。言。2）高级语言又称为程序设计语言或算法语言。）高级语言又称为程序设计语言或算法语言。5计算机科学导论低级语言的特点低级语言的特点 都与特定的计算机硬件系统紧密相关，来自都与特定的计算机硬件系统紧密相关，来自于特定系统的指令系统，可移植性差；于特定系统的指令系统，可移植性差；专业知识要求高，要求对计算机硬件的结构专业知识要求高，要求对计算机硬件的结构和工作原理非常熟悉；和工作原理非常熟悉；每条指令的功能很单一，程序员编制源程序每条指令的功能很单一，程序员编制源程序时指令比较繁琐；时指令比较繁琐；由于直接针对特定硬件编程，所以，最终的由于

4、直接针对特定硬件编程，所以，最终的可执行程序代码精炼，而且执行效率非常高。可执行程序代码精炼，而且执行效率非常高。6计算机科学导论两者主要的区别在于：机器语言无需翻译或编两者主要的区别在于：机器语言无需翻译或编译，译，CPU能够直接识别和执行。而汇编语言必能够直接识别和执行。而汇编语言必须经过汇编才能得到目标程序。须经过汇编才能得到目标程序。7计算机科学导论高级语言的产生高级语言的产生所谓高级语言是一种由表达各种意义的所谓高级语言是一种由表达各种意义的“词词”和和“公式公式”，按照一定的，按照一定的“语法规则语法规则”来来编写程序的语言，又称为程序设计语言或算编写程序的语言，又称为程序设计语言

5、或算法语言。法语言。8计算机科学导论高级语言的常见类型高级语言的常见类型(1)BASIC语言语言(2)FORTRAN语言语言(3)COBOL语言语言(4)PASCAL语言语言(5)C语言语言(6)C+语言语言(7)其他高级语言其他高级语言基于视窗类操作系统的，如基于视窗类操作系统的，如Visual Basic、Visual C+、Delphi、Power Builder、Java等等。等等。9计算机科学导论高级语言的特点高级语言的特点优点：语句的功能强，源程序比较短，容易学优点：语句的功能强，源程序比较短，容易学习，使用方便，通用性较强，便于推广和交流。习，使用方便，通用性较强，便于推广和交流

6、。缺点：编译程序比汇编程序复杂，而且编译出缺点：编译程序比汇编程序复杂，而且编译出来的目标程序往往效率不高，目标程序的长度来的目标程序往往效率不高，目标程序的长度比有经验的程序员所编的同样功能的汇编语言比有经验的程序员所编的同样功能的汇编语言程序要长程序要长半以上，运行时间也要长一些。半以上，运行时间也要长一些。10计算机科学导论6.1.3 6.1.3 高级语言的基本内容高级语言的基本内容1 1高级语言的基本符号高级语言的基本符号高级语言都是由所谓的基本符号组成的。基本高级语言都是由所谓的基本符号组成的。基本符号可以分为单字符和多字符两种情况。单字符号可以分为单字符和多字符两种情况。单字符基本

7、符号由单个字符组成，在高级语言中通符基本符号由单个字符组成，在高级语言中通常都有下列几种单字符基本符号：常都有下列几种单字符基本符号：(1)字母字母大写英文字母大写英文字母AZ，小写英文字母，小写英文字母az，共，共52个符号。个符号。(2)数字数字09，共，共10个数字符号。个数字符号。11计算机科学导论(3)特殊字符特殊字符(加加)，(减减)，*(乘乘)，/(除除)，(乘方乘方)，(等号等号)，(左括号左括号)，)(右括号右括号)，(大于大于)，(小于小于)，(逗号逗号)，(空格空格)等。等。在高级语言中的多字符基本符号由两个或两个在高级语言中的多字符基本符号由两个或两个以上的字符组成，例

8、如以上的字符组成，例如GoTo(转移转移)、(小小于或等于于或等于)、AND(与与)等等。等等。12计算机科学导论2 2高级语言的基本元素高级语言的基本元素基本元素由基本符号组成，可分为数、逻辑值、基本元素由基本符号组成，可分为数、逻辑值、名字、标号和字符串等五大类。名字、标号和字符串等五大类。(1)数数它由它由09共共10个基本数字和其他一些符号个基本数字和其他一些符号(如如小数点小数点“.”、正负号、正负号“、”及指数符号及指数符号“E”等所构成。等所构成。(2)逻辑值逻辑值由真由真(True)和假和假(False)两个值表示。两个值表示。13计算机科学导论(3)名字名字由字符组成，一般约

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

10、转移方向。14计算机科学导论(5)字符串字符串由一串字符所组成。在不同的高级语言中，字由一串字符所组成。在不同的高级语言中，字符串中的多个字符放在一对单引号或双引号中。符串中的多个字符放在一对单引号或双引号中。15计算机科学导论3 3基本的数据类型基本的数据类型基本的数据类型通常包括整数数据类型、实数基本的数据类型通常包括整数数据类型、实数数据类型和字符数据类型等。数据类型和字符数据类型等。变量必须先定义，然后才能使用，这是变量必须先定义，然后才能使用，这是条基条基本原则。本原则。变量实质上代表了一个特定大小的内存单元空变量实质上代表了一个特定大小的内存单元空间。间。16计算机科学导论4 4结

11、构数据类型结构数据类型(1)数组类型数组类型数组是若干个相同类型的数据的集合。数组是若干个相同类型的数据的集合。(2)用户自定义的结构体类型用户自定义的结构体类型结构体是隶属于同一个事物的多个不同类型的结构体是隶属于同一个事物的多个不同类型的数据的集合，用来表示具有若干个属性的一个数据的集合，用来表示具有若干个属性的一个事物。事物。17计算机科学导论5 5运算符与表达式运算符与表达式表达式是由基本符号、基本元素和各种数据表达式是由基本符号、基本元素和各种数据通过各种运算符连接而成的。通过各种运算符连接而成的。高级语言中的运算符大致包括以下几个方面：高级语言中的运算符大致包括以下几个方面：(1)

12、逻辑运算：逻辑运算：与、或、非、异或。与、或、非、异或。(2)算术运算：算术运算：加、减、乘、除、取模。加、减、乘、除、取模。(3)数据比较：数据比较：大于、小于、等于、不等于。大于、小于、等于、不等于。18计算机科学导论(4)数据传送；数据传送；输入、输出、赋值。输入、输出、赋值。(5)算术表达式：算术表达式：该表达式的运算结果是数，该表达式的运算结果是数，它非常近似于日常的数学公式。它非常近似于日常的数学公式。(6)关系运算表达式：关系运算表达式：该表达式的运算结果是该表达式的运算结果是逻辑值，常用的运算符包含逻辑值，常用的运算符包含(大于大于)、(小小于于)、(等于等于)、(小于等于小于

13、等于)、(大大于等于于等于)、不等于。、不等于。(7)字符串表达式：字符串表达式：该表达式的运算结果是字该表达式的运算结果是字符串。符串。19计算机科学导论6 6语句语句语句是构成高级语言源程序的基本单位，是由语句是构成高级语言源程序的基本单位，是由基本元素、运算符、表达式等组成。基本元素、运算符、表达式等组成。20计算机科学导论1010高级语言程序的运行高级语言程序的运行使用高级语言编制程序的一般过程可以归纳为以下几使用高级语言编制程序的一般过程可以归纳为以下几个步骤：个步骤：(1)使用文本编辑工具，逐条编写源程序的语句。存使用文本编辑工具，逐条编写源程序的语句。存储源程序文件时文件的后缀名

14、与所用的高级语言有关。储源程序文件时文件的后缀名与所用的高级语言有关。(2)编译源程序文件，生成目标文件，文件后缀名通编译源程序文件，生成目标文件，文件后缀名通常为常为obj。(3)链接目标文件，生成可执行文件，文件后缀名通链接目标文件，生成可执行文件，文件后缀名通常为常为exe。(4)在计算机上执行可执行程序文件，进在计算机上执行可执行程序文件，进步调试和步调试和维护。维护。21计算机科学导论6.2.1 6.2.1 结构化程序设计方法结构化程序设计方法 采用采用自顶向下、逐步求精自顶向下、逐步求精的设计方法和的设计方法和单入口单出口的控制结构。单入口单出口的控制结构。1.1.结构化程序设计思

15、想结构化程序设计思想 22计算机科学导论 23计算机科学导论结构化程序设计的结构化程序设计的原则原则是：是：(1)使用顺序、选择、循环使用顺序、选择、循环3种基本控制结构种基本控制结构表示程序逻辑。表示程序逻辑。(2)程序语句组织成容易识别的语句模块，每程序语句组织成容易识别的语句模块，每个模块都是单入口、单出口。个模块都是单入口、单出口。(3)严格控制严格控制GOTO语句的使用。语句的使用。24计算机科学导论(a)顺序结构顺序结构 (b)选择结构选择结构 (c)while循环循环 (d)do-while循环循环 25计算机科学导论2 2模块模块一个复杂的问题可以划分为多个简单问题的组一个复杂

16、的问题可以划分为多个简单问题的组合。合。在自顶向下、逐步细化的过程中，把复杂问题在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块分解成一个个简单问题的最基本方法就是模块化。化。模块化便于问题的分析，模块体现了信息隐藏模块化便于问题的分析，模块体现了信息隐藏的概念。模块常用子程序加以实现。的概念。模块常用子程序加以实现。26计算机科学导论1 1面向对象的思想面向对象的思想OO(Object Oriented，面向对象，面向对象)的程序设计把的程序设计把客观事物看作具有属性和行为的对象，通过抽客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性象找出同

17、一类对象的共同属性(静态特征静态特征)和行和行为为(动态特征动态特征)，形成类。，形成类。6.2.2 6.2.2 面向对象的程序设计方法面向对象的程序设计方法 27计算机科学导论2 2对象和类对象和类对象对象 是基本的实体，既包括数据（属性），也是基本的实体，既包括数据（属性），也包括作用于数据之上的操作（方法或函数）。包括作用于数据之上的操作（方法或函数）。类类 定义了一组大体上相似的对象。一个类所定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和包含的方法和数据描述一组对象的共同行为和属性。属性。对象则是类的具体化，是类的实例。对象则是类的具体化，是类的实例。28

18、计算机科学导论3 3抽象抽象抽象抽象 是对具体事物是对具体事物(即对象即对象)进行概括，即忽略进行概括，即忽略事物的非本质特征，只注意那些与当前目标有事物的非本质特征，只注意那些与当前目标有关的本质特征，从而抽象出一类对象的共性并关的本质特征，从而抽象出一类对象的共性并加以描述。加以描述。29计算机科学导论4 4封装性封装性封装的两个含义封装的两个含义：第一是，将抽象得到的数据成员和代码成第一是，将抽象得到的数据成员和代码成员相结合，形成一个不可分割的整体，即对象，员相结合，形成一个不可分割的整体，即对象，这种数据及行为的有机结合也就是封装。这种数据及行为的有机结合也就是封装。第二个含义称为信

19、息隐蔽，即尽可能隐蔽第二个含义称为信息隐蔽，即尽可能隐蔽对象的内部细节。对象的内部细节。30计算机科学导论5 5继承性继承性继承性继承性 是父类和子类之间共享数据和方法的机是父类和子类之间共享数据和方法的机制。制。原有的类称为原有的类称为基类基类或或父类父类，产生的新类，产生的新类称为称为派生类派生类。31计算机科学导论6 6多态性多态性多态性多态性 在收到外部消息时，对象通常要予以响在收到外部消息时，对象通常要予以响应。不同的对象收到同一消息可能产生完全应。不同的对象收到同一消息可能产生完全不同的结果。不同的结果。32计算机科学导论1 1数据、数据类型数据、数据类型数据数据 是对客观事物的符

20、号表示。是对客观事物的符号表示。数据类型数据类型 是指具有相同取值范围和可以实施同种操作的数是指具有相同取值范围和可以实施同种操作的数据的集合的总称。据的集合的总称。6.3.1 6.3.1 基本概念基本概念6.3 6.3 数据结构数据结构 33计算机科学导论2 2数据元素、数据项、数据对象数据元素、数据项、数据对象能够独立并完整地描述客观世界实体的基本数能够独立并完整地描述客观世界实体的基本数据单元称为据单元称为数据元素数据元素，它是组成数据的基本单，它是组成数据的基本单位。位。数据项数据项是组成数据元素的不可分割的最小单是组成数据元素的不可分割的最小单位。最简单的数据元素就是由一个数据项构成

21、位。最简单的数据元素就是由一个数据项构成的。的。同类数据元素的集合称为同类数据元素的集合称为数据对象数据对象。34计算机科学导论3 3数据结构数据结构数据结构数据结构 是指数据元素之间的相互关系的集合，包是指数据元素之间的相互关系的集合，包括了数据的逻辑结构、物理结构以及数据的运括了数据的逻辑结构、物理结构以及数据的运算。算。35计算机科学导论数据的逻辑结构数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑数据的逻辑结构是指数据元素之间的逻辑关系。数据之间可以根据不同的关系组成不同关系。数据之间可以根据不同的关系组成不同的数据结构。的数据结构。(2)数据的物理结构数据的物理结构 数据的物理结

22、构是指逻辑结构在计算机存数据的物理结构是指逻辑结构在计算机存储器中的表示。数据的物理结构不仅要存储数储器中的表示。数据的物理结构不仅要存储数据本身，还要存储表示数据间的逻辑关系。据本身，还要存储表示数据间的逻辑关系。36计算机科学导论顺序结构顺序结构 把所有元素存放在一片连续的存储单元中，把所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存储在物理位置相邻的存储逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结单元中，由此得到的存储表示称为顺序存储结构。构。顺序存储结构常借助于程序设计语言中的顺序存储结构常借助于程序设计语言中的数组来实现。优点是使用方法简单，

23、缺点是必数组来实现。优点是使用方法简单，缺点是必须预先分析出所需定义数组的大小。须预先分析出所需定义数组的大小。37计算机科学导论链表结构链表结构 对逻辑上相邻的元素不要求其物理位置相对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针域来实邻，元素间的逻辑关系通过附设的指针域来实现，由此得到的存储表示称为链式存储结构。现，由此得到的存储表示称为链式存储结构。链式存储结构通常借助于程序设计语言中链式存储结构通常借助于程序设计语言中的指针来实现。的指针来实现。38计算机科学导论索引结构索引结构 针对每个数据结构建立一张所谓的索引表，针对每个数据结构建立一张所谓的索引表，每个数据

24、元素占用表中的一项，每个表项包含每个数据元素占用表中的一项，每个表项包含一个能够惟一识别一个元素的关键字和用以指一个能够惟一识别一个元素的关键字和用以指示该元素的地址指针。示该元素的地址指针。散列结构散列结构 通过构造相应的散列函数，由散列函数的值通过构造相应的散列函数，由散列函数的值来确定元素存放的地址。来确定元素存放的地址。39计算机科学导论(3)数据运算数据运算 数据操作的集合。常见的数据操作有数数据操作的集合。常见的数据操作有数据的插入、删除、查找、遍历等。据的插入、删除、查找、遍历等。数据操作通常由计算机程序加以实现，数据操作通常由计算机程序加以实现，通常也叫通常也叫算法实现算法实现

25、。40计算机科学导论6.3.2 6.3.2 线性表线性表1定义定义 线性表线性表是由有限个相同的数据元素构成的序是由有限个相同的数据元素构成的序列，元素之间是一对一的线性关系，除了第列，元素之间是一对一的线性关系，除了第一个元素只有直接后继、最后一个元素只有一个元素只有直接后继、最后一个元素只有直接前驱外，其余数据元素都有一个直接前直接前驱外，其余数据元素都有一个直接前驱和一个直接后继，如图。驱和一个直接后继，如图。41计算机科学导论2运算和实现运算和实现 线性表通常采用顺序和链表两种物理实现。线性表通常采用顺序和链表两种物理实现。对于经常变化的表，通常采取链表结构。对于经常变化的表，通常采取

26、链表结构。42计算机科学导论插入插入 在保持原有的存储结构的前提下，根据插在保持原有的存储结构的前提下，根据插入要求，在适当的位置插入一个元素。插入操入要求，在适当的位置插入一个元素。插入操作要求线性表要有足够的存放新元素的空间，作要求线性表要有足够的存放新元素的空间，如果空间不足，插入操作无法进行，线性表会如果空间不足，插入操作无法进行，线性表会溢出。溢出。删除删除 在线性表中，找到满足条件的数据元素，在线性表中，找到满足条件的数据元素，并删除。如果线性表为空，删除就会失败。并删除。如果线性表为空，删除就会失败。43计算机科学导论查询查询 在线性表中，按照查询条件，定位数据在线性表中，按照查

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

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

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

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

31、队 出队是在队列中删除一个数据元素的过程，出队是在队列中删除一个数据元素的过程，删除在队首进行并把出来的数据传递给用户程删除在队首进行并把出来的数据传递给用户程序。序。49计算机科学导论 50计算机科学导论 51计算机科学导论判断：判断：判断操作用来检查队列是否为空，返回结果判断操作用来检查队列是否为空，返回结果是一个逻辑值：真或假，如图。是一个逻辑值：真或假，如图。52计算机科学导论6.3.5 6.3.5 树树1定义定义 树形数据结构中，每个数据元素称为是树形数据结构中，每个数据元素称为是一个节点，除了一个惟一的所谓一个节点，除了一个惟一的所谓根节点根节点外，其外，其他每个节点都有且只有一个

32、父节点，每个元素他每个节点都有且只有一个父节点，每个元素可以有多个子节点。可以有多个子节点。树主要用在大型、动态列表的搜索，人树主要用在大型、动态列表的搜索，人工智能系统和编码算法等问题中。工智能系统和编码算法等问题中。53计算机科学导论2 2运算运算树常见的基本运算有：插入、删除和遍历。树常见的基本运算有：插入、删除和遍历。插入插入 在树中合适的位置，添加一个节点，通常插入新在树中合适的位置，添加一个节点，通常插入新的节点后，仍然应该保持该树本身所具有的性质。的节点后，仍然应该保持该树本身所具有的性质。删除删除 在树中找到满足条件的节点并删除。通常删除节在树中找到满足条件的节点并删除。通常删

33、除节点后，也要保持该树本身所具有的性质。点后，也要保持该树本身所具有的性质。遍历遍历 按照某种顺序或规则，对树中的每个节点逐一进按照某种顺序或规则，对树中的每个节点逐一进行访问的过程。行访问的过程。54计算机科学导论3 3实现实现 55计算机科学导论6.3.6 6.3.6 图图1定义定义 在图形结构中，每个数据元素称为一个顶在图形结构中，每个数据元素称为一个顶点，任意两个顶点之间都可能相关，这种相关点，任意两个顶点之间都可能相关，这种相关性用一条边来表示，顶点之间的邻接关系可以性用一条边来表示，顶点之间的邻接关系可以是任意的。是任意的。图可以用来描述计算机网络的拓扑结构，图可以用来描述计算机网

34、络的拓扑结构，以及图论中获得最小生成树。除此以外，图在以及图论中获得最小生成树。除此以外，图在自然科学、社会科学和人文科学等许多领域也自然科学、社会科学和人文科学等许多领域也都有着非常广泛的应用。都有着非常广泛的应用。56计算机科学导论2 2运算运算常见的基本运算有：添加顶点、删除顶点、添常见的基本运算有：添加顶点、删除顶点、添加边、删除边和遍历图。加边、删除边和遍历图。添加顶点添加顶点 在图中添加新的顶点，新添加的顶点通常在图中添加新的顶点，新添加的顶点通常是孤立的节点，还没有边连接。是孤立的节点，还没有边连接。删除顶点删除顶点 在图中去掉一个顶点，显然，在去掉一个在图中去掉一个顶点，显然，

35、在去掉一个顶点的同时还应该删除与该顶点所连接的边。顶点的同时还应该删除与该顶点所连接的边。57计算机科学导论添加边添加边 根据指定的顶点，添加相应的边。根据指定的顶点，添加相应的边。删除边删除边 根据指定的顶点，删除相应的边。根据指定的顶点，删除相应的边。遍历图遍历图 按照一定的规则，对图中的每个数据顶按照一定的规则，对图中的每个数据顶点逐一进行访问。点逐一进行访问。58计算机科学导论3 3实现实现图通常用数组和链表两种结构加以实现。对图通常用数组和链表两种结构加以实现。对于各个顶点和顶点之间的关系分别采用邻接于各个顶点和顶点之间的关系分别采用邻接矩阵和邻接列表来进行描述。矩阵和邻接列表来进行

36、描述。59计算机科学导论 60计算机科学导论6.4.1 6.4.1 概述概述1算法的定义算法的定义 准确地说，准确地说，“算法算法(Algorithm)是一组明是一组明确的、可以执行的步骤的有序集合，它在有确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果限的时间内终止并产生结果”。6.4 6.4 算法分析基础算法分析基础 61计算机科学导论2算法的特性算法的特性(1)有穷性有穷性(可终止性可终止性)一个算法必须在有限个操作步骤内以及合理的时一个算法必须在有限个操作步骤内以及合理的时间内执行完成。间内执行完成。(2)确定性确定性 算法中的每一个操作步骤都必须有明确的含义，算法中的每

37、一个操作步骤都必须有明确的含义，不允许存在二义性。不允许存在二义性。(3)有效性有效性(可执行性可执行性)算法中描述的操作步骤都是可执行的，并能最终算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。得到确定的结果。(4)输入及输出输入及输出 一个算法应该有零个或多个输入数据、有一个算法应该有零个或多个输入数据、有1个或多个或多个输出数据。个输出数据。62计算机科学导论3 3算法的描述算法的描述(1)自然语言表示自然语言表示 自然语言就是人们日常使用的语言，可以是自然语言就是人们日常使用的语言，可以是中文、英文等。中文、英文等。63计算机科学导论(2)流程图表示流程图表示 流程图是用规定

38、的一组图形符号、流程线和文字流程图是用规定的一组图形符号、流程线和文字说明来表示算法的一种表示方法。说明来表示算法的一种表示方法。(3)伪码伪码 伪码用一种介于自然语言与计算机语言之间的文伪码用一种介于自然语言与计算机语言之间的文字和符号来描述算法。比计算机语言形式灵活，格式字和符号来描述算法。比计算机语言形式灵活，格式紧凑，没有严格的语法。紧凑，没有严格的语法。(4)程序设计语言形式程序设计语言形式 算法也可以用某种具体的计算机程序设计语言来算法也可以用某种具体的计算机程序设计语言来表示，如，表示，如，C、C+、Java等都可以用来描述算法。等都可以用来描述算法。64计算机科学导论例如，求两

39、个数的较大者。用伪代码描述算法如下：例如，求两个数的较大者。用伪代码描述算法如下：Input:two number s:a,b1.if(the first number a is greater than or equal to the second number b)then 1.1 return a else 1.2 return bend if end 65计算机科学导论6.4.2 6.4.2 常用算法介绍常用算法介绍1递归算法递归算法 如果一个过程直接或间接地调用它本身，如果一个过程直接或间接地调用它本身，则称该过程是递归的。则称该过程是递归的。66计算机科学导论2 2迭代算法迭代算法

40、 所谓迭代是指重复执行一组指令或操作所谓迭代是指重复执行一组指令或操作步骤，在每次执行这组指令时，都从原来的解步骤，在每次执行这组指令时，都从原来的解值的基础上推出一个新的解值。新的解值比原值的基础上推出一个新的解值。新的解值比原来的解值更加接近真实的解。这个过程不断重来的解值更加接近真实的解。这个过程不断重复，直到计算得到的解与真实解的误差满足实复，直到计算得到的解与真实解的误差满足实际要求。际要求。迭代常常用于科学计算领域对某些无法直接求迭代常常用于科学计算领域对某些无法直接求解的数值问题。解的数值问题。67计算机科学导论3 3穷举算法穷举算法 亦称枚举法，该算法首先根据问题的部亦称枚举法

41、，该算法首先根据问题的部分条件确定问题解的大致范围，然后在此范围分条件确定问题解的大致范围，然后在此范围内对所有可能的情况逐一进行验证，直到全部内对所有可能的情况逐一进行验证，直到全部情况验证完毕。情况验证完毕。68计算机科学导论4 4贪婪算法贪婪算法 贪婪算法通常具有贪婪算法通常具有贪婪选择性贪婪选择性和和最优子最优子结构性结构性。贪婪选择性贪婪选择性指的是所求解问题的整体最优解可以指的是所求解问题的整体最优解可以通过一系列局部最优的选择，即贪婪选择来达通过一系列局部最优的选择，即贪婪选择来达到。到。最优子结构性最优子结构性指的是一个问题的最优解往往包含指的是一个问题的最优解往往包含着它的子

42、问题的最优解。着它的子问题的最优解。69计算机科学导论6.4.3 6.4.3 算法的评价算法的评价对于一个算法的评价，通常要从对于一个算法的评价，通常要从正确性、可理正确性、可理解性、健壮性、时间复杂性及空间复杂性解性、健壮性、时间复杂性及空间复杂性等多等多个方面加以衡量。个方面加以衡量。70计算机科学导论1 1算法的时间复杂度算法的时间复杂度 时间复杂度时间复杂度(Time complexity)是度量时间复杂是度量时间复杂性、即算法的时间效率的指标。时间复杂度是性、即算法的时间效率的指标。时间复杂度是与求解问题规模、算法输入相关的函数，该函与求解问题规模、算法输入相关的函数，该函数表示算法

43、运行所花费的时间。数表示算法运行所花费的时间。为了简化问题，通常，用算法运行某段核心代为了简化问题，通常，用算法运行某段核心代码的码的次数次数来代替准确的执行时间，记为来代替准确的执行时间，记为T(n)，其中，其中，n代表求解问题的规模，一般是指待处代表求解问题的规模，一般是指待处理的数据量的大小。理的数据量的大小。71计算机科学导论2 2算法的空间复杂度算法的空间复杂度 算法的算法的空间复杂度空间复杂度(Space complexity)用来度用来度量算法的空间复杂性、即执行算法的程序在计量算法的空间复杂性、即执行算法的程序在计算机中运行时所占用空间的大小。算机中运行时所占用空间的大小。简单

44、讲，空间复杂度也是与求解问题规模、算简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。记为法输入相关的函数。记为S(n)，其中，其中n代表求代表求解问题的规模。解问题的规模。72计算机科学导论6.4.4 NP6.4.4 NP问题问题NP(Non-deterministic Polynomial)问题，是非问题，是非确定型多项式问题。所谓的非确定型，简单讲确定型多项式问题。所谓的非确定型，简单讲就是指算法无法直接计算出结果，只能通过进就是指算法无法直接计算出结果，只能通过进行一些有选择的行一些有选择的“猜算猜算”来得到结果。来得到结果。73计算机科学导论6.6 6.6 本章小结本章小结本章从程序设计的基础开始介绍，阐述了结构本章从程序设计的基础开始介绍，阐述了结构化程序设计和面向对象程序设计，并对这两种化程序设计和面向对象程序设计，并对这两种方法进行了比较。方法进行了比较。在数据结构中，介绍了常用的数据结构，如线在数据结构中，介绍了常用的数据结构，如线性表、栈、队列、树、图等。性表、栈、队列、树、图等。在算法分析中，讲述了设计算法的思想，评价在算法分析中，讲述了设计算法的思想，评价算法优劣的标准。算法优劣的标准。