数据结构与算法分析第一章绪论

《数据结构与算法分析第一章绪论》由会员分享，可在线阅读，更多相关《数据结构与算法分析第一章绪论（81页珍藏版）》请在金锄头文库上搜索。

1、1第一章第一章 绪论绪论教学内容：教学内容：1.1数据结构的原则数据结构的原则1.2抽象数据类型和数据结构抽象数据类型和数据结构1.3问题、算法和程序问题、算法和程序学习要求：学习要求：理解、掌握算法的基本概念和简单的算法分析、数理解、掌握算法的基本概念和简单的算法分析、数据和数据结构的基本概念、数据的逻辑结构和存储据和数据结构的基本概念、数据的逻辑结构和存储结构的基本概念及其性质和两种结构之间的关系。结构的基本概念及其性质和两种结构之间的关系。 2引引 言言 二二十十一一世世纪纪是是科科学学技技术术高高速速发发展展的的信信息息时时代代，而而计计算算机机是是处处理理信信息息的的主主要要工工具具

2、，因因此此，人人们们已已经经认认识识到到，计计算算机机知知识识已已成成为为人人类类当当代代文文化化的的一个重要组成部分。一个重要组成部分。3计计算算机机科科学学技技术术以以惊惊人人的的速速度度向向前前发发展展，它它的的广广泛泛应应用用已已从从传传统统的的数数值值计计算算领领域域发发展展到到各各种种非非数数值值计计算算领领域域。在在非非数数值值计计算算领领域域里里，数数据据处处理理的的对对象象已已从从简简单单的的数数值值发发展展到到一一般般的的符符号号，进进而而发发展到具有一定结构的数据。展到具有一定结构的数据。4 在在这这里里，面面临临的的主主要要问问题题是是：针针对对每每一一种种新新的的应应

3、用用领领域域的的处处理理对对象象，如如何何选选择择合合适适的的数数据据表表示示（结结构构），如如何何有有效效地地组组织织计计算算机机存存贮贮，并并在在此此基基础础上上又又如如何何有有效效地地实实现现对对象象之之间间的的“运运算算”关关系系。数数据据结结构构就就是是研研究究和和解解决决这这些些问问题题的的重重要要基基础础理理论论。因因此此，“数数据据结结构构”课课程程已已成成为为计计算机类专业的一门重要专业基础课。算机类专业的一门重要专业基础课。 美美国国IEEE和和ACM的的教教学学计计划划CC2001把把算算法法与与数数据据结结构构列列入入计计算算机机以以及及信信息息技技术术相相关关学学科专

4、业的本科必修基础课程科专业的本科必修基础课程51.1 数据结构的原则数据结构的原则数据结构：一类数据的表示及其相关操作数据结构：一类数据的表示及其相关操作学习数据结构的必要性学习数据结构的必要性计算机功能强大计算机功能强大更复杂的问题更复杂的问题更复杂的问题更复杂的问题更大的计算量更大的计算量工作越复杂越偏离人们的日常经验工作越复杂越偏离人们的日常经验故：必须有一种数据结构来组织各种复杂的数据。故：必须有一种数据结构来组织各种复杂的数据。任何一种数据项集合都必须具备查询、排序、任何一种数据项集合都必须具备查询、排序、修改的功能，如果选择一个好的数据结构和算修改的功能，如果选择一个好的数据结构和

5、算法将会对程序的运行时间产生巨大的影响。法将会对程序的运行时间产生巨大的影响。一、为什么要学习数据结构？一、为什么要学习数据结构？1、什么是程序、软件？、什么是程序、软件？ N.沃思（沃思（Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+数据结构数据结构7程序的主要目标是存储信息和检索信息程序的主要目标是存储信息和检索信息,而基础是信息表示而基础是信息表示. 程序设计核心目标：程序设计核心目标： （）设计一种容易理解、编码和调试（）设计一种容易理解、编码和调试的算法的算法 （软件工程原理）（软件工程原理） （）设计一种能有效利用计算机资源（）设计一种能有效利用计算机资源的

6、算法的算法 （数据结构和算法）（数据结构和算法） 程序简明清晰（简洁）程序简明清晰（简洁）程序程序=算法算法+数据结构数据结构 以上公式说明了如下两个问题：以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和）数据上的算法决定如何构造和组织数据（算法组织数据（算法数据结构）。数据结构）。 （2）算法的选择依赖于作为基础的）算法的选择依赖于作为基础的数据结构（数据结构数据结构（数据结构算法）。算法）。 软件软件=程序程序+文档（软件工程的观点）文档（软件工程的观点）2、电子计算机的主要用途：、电子计算机的主要用途： 早期：早期： 主要用于数值计算。主要用于数值计算。 后来：后来： 处理

7、逐渐扩大到非数值计算领处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构域（能处理多种复杂的具有一定结构关系的数据）。关系的数据）。（1）数值计算解决问题的一般步骤：）数值计算解决问题的一般步骤： 数学模型数学模型选择计算机语言选择计算机语言编出编出程序程序测试测试最终解答。最终解答。 数值计算的关键是：如何得出数学数值计算的关键是：如何得出数学模型（方程）？模型（方程）？ 程序设计人员比较关注程序设计的程序设计人员比较关注程序设计的技巧。技巧。（2）非数值计算问题：）非数值计算问题： 数据元素之间的相互数据元素之间的相互关系一般无法用数学关系一般无法用数学方程加以描述方程加以描述12

8、例例1 书目自动检索系统书目自动检索系统登录号：登录号：书名：书名：作者名：作者名：分类号：分类号：出版单位：出版单位：出版时间：出版时间：价格：价格：书目卡片书目卡片书目文件书目文件按书名按书名按作者名按作者名按分类号按分类号索引表索引表线性表线性表13 例例2 2 人机对奕问题人机对奕问题树树.14例例3 多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图 例例4: 电话号码查询问题：电话号码查询问题： （1）按顺序存储方式：须遍历表）按顺序存储方式：须遍历表 （2）按姓氏索引方式：）按姓氏索引方式：建立建立索引索引 要写出好的查找算法，取决于这张表的要

9、写出好的查找算法，取决于这张表的结构及存储方式。结构及存储方式。 电话号码表的结构和存储方式决定了查电话号码表的结构和存储方式决定了查找（算法）的效率。找（算法）的效率。 例例5: 田径赛的时间安排问题（无向田径赛的时间安排问题（无向图的着色问题）图的着色问题） ：设有六个比赛项目，规定每个选手至多可设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。在尽可能短的时间内完成比赛。田径赛的时间安排问题田径赛的时间安排问题姓名姓名项目项目1项目项目2项目项

10、目3丁丁1跳高跳高跳远跳远100M马马2标枪标枪铅球铅球张张3标枪标枪100M200M李李4铅球铅球200M跳高跳高王王5跳远跳远200M跳高跳远标枪铅球200M100M1 1、任一选手所选中的项目中应该两两有边相连；、任一选手所选中的项目中应该两两有边相连；2 2、任一两个有边相连的顶点颜色（时间）不能相同。、任一两个有边相连的顶点颜色（时间）不能相同。 （1）设用如下六个不同的代号代表不同的）设用如下六个不同的代号代表不同的项目：项目： 跳高跳高跳高跳高 跳远跳远跳远跳远 标枪标枪标枪标枪 铅球铅球铅球铅球 100100米米米米 200200米米米米 A A B B C D E C D E

11、 F F （2）用顶点代表比赛项目）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。不能同时进行比赛的项目之间连上一条边。不能同时进行比赛的项目之间连上一条边。不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不）某选手比赛的项目必定有边相连（不能同时比赛）。能同时比赛）。 解法如下：解法如下：姓名姓名项目项目1项目项目2项目项目3丁一丁一 A B E马二马二 C D 张三张三 C E F李四李四 D F A王五王五 B FAEBFDC比赛比赛时间时间比赛项目比赛项目1A，C2B，D3E4F 只需只需安排四安排四个单位个单位时间进时间进行比赛行比赛小小结：结

12、：求解非数值计算的问题主要考虑的是设计出合适求解非数值计算的问题主要考虑的是设计出合适的数据结构及相应的算法。的数据结构及相应的算法。即：首先要考虑即：首先要考虑对相关的各种信息如何表示、组对相关的各种信息如何表示、组织和存储？织和存储？ 因此，可以认为因此，可以认为：数据结构是一门研究非数值计数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。间的关系和操作的学科。二、数据结构课程的形成和发展：二、数据结构课程的形成和发展： 形成阶段：形成阶段： 60年代初期，年代初期，“数据结构数据结构”有关的内容散见有关

13、的内容散见于操作系统、编译原理和表处理语言等课程。于操作系统、编译原理和表处理语言等课程。1968年，年，“数据结构数据结构”被列入美国一些大学计算被列入美国一些大学计算机科学系的教学计划。机科学系的教学计划。 发展阶段：发展阶段： 数据结构的概念不断扩充，包括了网络、数据结构的概念不断扩充，包括了网络、集合代数论、关系等集合代数论、关系等“离散数学结构离散数学结构”的内容。的内容。 70年代后期，我国高校陆续开设该课程。年代后期，我国高校陆续开设该课程。数据结构课程数据结构课程所处的地位：所处的地位：231.2抽象数据类型和数据结构抽象数据类型和数据结构一一、名词解释名词解释类型：类型：是一

14、组值的集合。如：整数是一组值的集合。如：整数数据项：数据项：一条信息或其值属于某种类型的一条信息或其值属于某种类型的一条记录。如：学生记录里的姓名项一条记录。如：学生记录里的姓名项数据类型：一种类型和定义在该类型上的数据类型：一种类型和定义在该类型上的一组操作。如整型变量是整数数据类型一组操作。如整型变量是整数数据类型的一个成员，而加法是定义在整数类型的一个成员，而加法是定义在整数类型上的一种操作上的一种操作24抽象数据类型抽象数据类型(ADT)(ADT)：指数据结构作为一个软：指数据结构作为一个软件组件的实现件组件的实现每个每个ADTADT的操作由它的输入和输出定义的操作由它的输入和输出定义

15、每个每个ADTADT的操作细节是封装的的操作细节是封装的数据结构：是数据结构：是ADTADT的实现的实现与与ADTADT联系的操作都是由一个成员函数来实联系的操作都是由一个成员函数来实现现“数据结构数据结构”常指计算机内存中的数据常指计算机内存中的数据“文件结构文件结构”常指外存储器中数据的组织常指外存储器中数据的组织25二、什么是数据结构？二、什么是数据结构？ 基本概念和术语基本概念和术语数据（数据（data)所有能输入到计算机中去的描述客观事物的所有能输入到计算机中去的描述客观事物的符号符号数据元素（数据元素（data element）数据的基本单位，也称节点数据的基本单位，也称节点（no

16、de）或记录（）或记录（record）数据项（数据项（data item）有独立含义的数据最小单位，也称有独立含义的数据最小单位，也称域域(field)数据结构（数据结构（data structure)数据元素和数据元素关系的数据元素和数据元素关系的集合集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图26逻辑形式与物理形式逻辑形式与物理形式数据项包括数据项包括逻辑逻辑与与物理物理形式形式逻辑形式逻辑形式是由是由ADTADT给出的数据项的定义给出的数据项的

17、定义物理形式物理形式是数据结构中对数据项的实现是数据结构中对数据项的实现数据类型（数据类型（*.h）ADT:类型类型操作操作数据项数据项: 逻辑形式逻辑形式数据项数据项: 物理形式物理形式数据结构数据结构:(class)存储空间存储空间子程序子程序27数据的逻辑结构数据的逻辑结构只抽象反映数据元素的逻辑关系只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的存储（物理）结构数据的逻辑结构在计算机数据的逻辑结构在计算机存储器中的实现存储器中的实现数据的逻辑结构与存储结构密切相关数据的逻辑结构与存储结构密切相关算法设计算法设计 逻辑结构逻辑结构算法实现算法实现 存储结构存储结构存储结构分为：存

18、储结构分为：顺序存储结构顺序存储结构借助元素在存储器中的相对位置来表示借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系数据元素间的逻辑关系链式存储结构链式存储结构借助指示元素存储地址的指针表示数据借助指示元素存储地址的指针表示数据 元素间的逻辑关系元素间的逻辑关系28元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储291536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容

19、存储内容 指针指针 1345 1345 元素元素1 1 1400 1400 1346 1346 元素元素4 4 . . . . . 1400 1400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 链式存储链式存储 h30 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方

20、面：三、数据结构的定义三、数据结构的定义定义定义1- 数据元素之间的相互关系称为结构，带有结构的数数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。据元素的集合称为数据结构。定义定义2- 按某种逻辑关系按某种逻辑关系组织起来的一批数据（或称带结构的组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并数据元素的集合）应用计算机语言并按一定的存储表按一定的存储表示示 方式方式把它们存储在计算机的存储器中，并把它们存储在计算机的存储器中，并在其上在其上定义了一个运算的集合。定义了一个运算的集合。32数据结构定义数据结构定义: 是一门研究非数值计算是一门研究非数值计算的

21、程序设计问题中计的程序设计问题中计算机的操作对象以及算机的操作对象以及它们之间的关系和操它们之间的关系和操作的学科作的学科数据结构的三个方面的含义：数据结构的三个方面的含义：逻辑结构逻辑结构- 数据元素间抽象化的相互关系（简称为数据结构）。数据元素间抽象化的相互关系（简称为数据结构）。 与数据的存储无关，独立于计算机，它是从具体问与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。题抽象出来的数学模型。存储结构（物理结构）存储结构（物理结构）- 数据元素及其关系在计算机存储器中的存储方式。数据元素及其关系在计算机存储器中的存储方式。 是逻辑结构用计算机语言的实现，它依赖于计算机是

22、逻辑结构用计算机语言的实现，它依赖于计算机语言。语言。运算（算法）运算（算法）（1）逻辑结构逻辑结构-线性结构线性结构- 有且仅有一个开始和一个终端结点，并且有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后所有结点都最多只有一个直接前趋和一个后继。继。 例如：线性表、栈、队列、串例如：线性表、栈、队列、串非线性结构非线性结构- 一个结点可能有多个直接前趋和直接后一个结点可能有多个直接前趋和直接后继。继。 例如：树、图、多维数组、广义表等。例如：树、图、多维数组、广义表等。（2）存储结构存储结构存储结构两方面的内容：存储结构两方面的内容：数据元素自身值的表示（数据域）数

23、据元素自身值的表示（数据域）该结点与其它结点关系的域（链域）该结点与其它结点关系的域（链域）四种基本的存储方法：四种基本的存储方法：顺序存储方法（结构）顺序存储方法（结构）链接存储方法（链式存储结构）链接存储方法（链式存储结构）索引存储方法索引存储方法散列存储方法散列存储方法 同一种逻辑结构可采用不同的存储方同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。虑的是运算方便及算法的时空要求。逻辑结构存储结构小结：逻辑结构存储结构小结：（1）数据的逻辑结构、存储结构和数据的运算）数据的逻辑结构、存储结构和数据的运算（

24、算法）构成了数据结构三个方面的含义。（算法）构成了数据结构三个方面的含义。（2）程序设计的实质是对实际问题选择一个好）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据算法在很大程度上取决于描述实际问题的数据结构。结构。效率：效率：如果能在所要求的资源限如果能在所要求的资源限制制(resource constraint)(resource constraint)内将内将问题解决好，则称该算法是有效问题解决好，则称该算法是有效率率(efficient)(efficient)的。的。代价：代价

25、：解决一个问题所耗费的关解决一个问题所耗费的关键资源键资源( (如时间、空间如时间、空间) )。代价与效益代价与效益每一个问题都有可利用空间和时间的限制只有对问题特性进行仔细分析后才能得到解决问题的最好的数据结构银行例子：开户：几分钟交易：几秒钟销户：月末（更长时间）39代价与效益代价与效益每一个数据结构都与代价与效益联系每一个数据结构都与代价与效益联系在一起在一起很难说一种算法在所有情况下都比其很难说一种算法在所有情况下都比其他算法好他算法好一个数据结构必须要求：一个数据结构必须要求：空间存储数据项空间存储数据项时间执行单个操作时间执行单个操作程序设计工作程序设计工作40学习的目的学习的目的

26、对每个数据结构加强对存在代价与效对每个数据结构加强对存在代价与效 益的观念益的观念掌握常用的数据结构掌握常用的数据结构将常用的数将常用的数据结构放入你的工具包据结构放入你的工具包理解怎样去衡量一个数据结构或程序理解怎样去衡量一个数据结构或程序的代价的代价评价标准评价标准411.3 问题、算法和程序问题：问题：需要完成的任务需要完成的任务一组输入必有一组相应的一组输入必有一组相应的输出输出问题的定义应包括对任何问题的定义应包括对任何行为可行方案所需资源行为可行方案所需资源的限制的限制42问题问题问题 函数函数函数函数是输入是输入( (定义域定义域domaindomain) )和输出和输出( (值

27、域值域rangerange) )的一种映射关系的一种映射关系函数的函数的输入输入可是一个值或一个实例可是一个值或一个实例这些值组成的输入称为函数的这些值组成的输入称为函数的参数参数对于一个给定的输入，函数每次计对于一个给定的输入，函数每次计算所得的输出应必然相同算所得的输出应必然相同43算法和程序算法：解决一个问题的方法或过程解决一个问题的方法或过程处方对于一个问题的算法给定一输入，必然会转对于一个问题的算法给定一输入，必然会转化为一个输出化为一个输出输入输出的映射一个问题可用多种算法来解决一个问题可用多种算法来解决程序：程序：用某种程序设计语言对一种算法的实用某种程序设计语言对一种算法的实现

28、现算法的概念和描述：算法的概念和描述：一、算法的概念：一、算法的概念： 所谓算法（所谓算法（Algorithm)是描述计算是描述计算机解决给定问题的操作过程（解题方法）机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指，即为解决某一特定问题而由若干条指令组成的令组成的有穷序列有穷序列。1.1.算法算法-求解一个特定任务的指令的有限序列。求解一个特定任务的指令的有限序列。 例例 求求a0.an-1a0.an-1中中n n个数的平均值个数的平均值( (假定假定n0)n0)。 float average(float a ,int n)float average(float a ,

29、int n) int i int i；float s=0.0float s=0.0； /累加器赋初值累加器赋初值 for (i=0for (i=0；inin；i+)i+) s=s+ai s=s+ai； /ai/ai累加到累加到s s中中 s=s/ns=s/n； /计算平均值计算平均值 printf(printf(“ave=%fave=%f”,s),s)； /输出输出 return(s)return(s)； /返回返回 其中：其中：a,na,n为输入量；为输入量；s s为输出量。为输出量。2.2.算法的算法的5 5个特征个特征(1)(1)有穷性：在有限步有穷性：在有限步( (或有限时间或有限时间

30、) )之后算法终止。之后算法终止。 例例 i=0 i=0；s=0s=0； while (i=10)while (i=10) s+=i s+=i； i+i+；/使使i i趋于趋于1010 (2)(2)确定性：无二义性。确定性：无二义性。 例例 x=5 x=5；y=10y=10； z=x+yz=x+y； printf(printf(“%d,%d,%d%d,%d,%d”,x,y,z),x,y,z)； x+y x+y 解释为：解释为：x + (+y)x + (+y)？还是？还是 (x+)+ y(x+)+ y？ 例例 intint x=0; x=0; 表达式：表达式：x+ +x+ x+ +x+ 的值的值

31、(3)(3)可行性：可以在计算机上实现。可行性：可以在计算机上实现。for( i=1,s=0for( i=1,s=0；i1000000000000i1000000000000；+i)+i) s+ s+；？；？(4)(4)输入：有输入：有0 0或多个输入量。或多个输入量。(5)(5)输出：至少有一个输出量。输出：至少有一个输出量。3.3.算法设计要求算法设计要求 (1)(1)正确性正确性 a.a.无语法错误；无语法错误； b.b.对对n n组输入产生正确结果；组输入产生正确结果； c.c.对特殊输入产生正确结果；对特殊输入产生正确结果； d.d.对所有输入产生正确结果。对所有输入产生正确结果。

32、(2)(2)可读性：可读性：“算法主要是为了人的阅读与交算法主要是为了人的阅读与交流流”。 (3)(3)健壮性健壮性 scanf(scanf(“%d%d”,&x),&x)； y/=xy/=x；？；？ (4)(4)高效与低存储量高效与低存储量50二二、算法的描述和实现、算法的描述和实现算法的描述工具：算法的描述工具：（1 1） 自然语言；自然语言；（2 2） 程序设计语言；程序设计语言；（3 3） 流程图（框图）；流程图（框图）；（4 4） 伪语言；伪语言； 是一种包括高级程序设计语言是一种包括高级程序设计语言的三种基本结构（顺序、选择、循环）的三种基本结构（顺序、选择、循环）和自然语言成分的和

33、自然语言成分的“面向读者面向读者”的语的语言。言。51如如 like C+like C+或或like Clike C 介于伪码语言和程序设计语言介于伪码语言和程序设计语言之间的一种表示形式。保留了之间的一种表示形式。保留了C+C+或或语言的精华；不拘泥与语言的精华；不拘泥与C+C+或或C C语言语言的语法细节；同时在的语法细节；同时在C C中也添加了一中也添加了一些些C+C+的成分。的成分。 特点：便于理解、阅读；能方便特点：便于理解、阅读；能方便的转换成的转换成C+C+或或C C语言。语言。 目的：便于简明扼要的描述算法；目的：便于简明扼要的描述算法；突出算法的思路。突出算法的思路。算法描述

34、举例算法描述举例 问题：设一维数组问题：设一维数组a0.n-1a0.n-1中已有中已有n n个整数个整数, ,其中其中n n为个常数为个常数, ,试设计算法试设计算法: :求求aa中的最大值。中的最大值。 算法基本思想算法基本思想: : 1.maxai=a0 1.maxai=a0； 2.i=12.i=1； 3.3.若若i=n-1,imaxai,aimaxai,则则 maxai=aimaxai=ai； 3.2 i+3.2 i+； 3.3 3.3 转转3 3 4.maxai 4.maxai为最大值。为最大值。函数函数( (算法算法) )/求数组求数组a a中中n n个元素的最大值个元素的最大值in

35、t a_maxint(int a,int n) int a_maxint(int a,int n) int j,maxai=a0 int j,maxai=a0； /最大值的初值最大值的初值 for (j=1for (j=1；j=n-1jmaxai) / if (ajmaxai) /比较元素大小比较元素大小 maxaimaxaiajaj； /新的最大值新的最大值 printf(maxaiprintf(maxai%dn,maxai)%dn,maxai)； /输出输出 return maxaireturn maxai； 54例例 运用伪码编写：顺序查找某一特定值的算法。运用伪码编写：顺序查找某一特定

36、值的算法。 Procedure S_Search(data,keyvalue) 设设I为为1； while( ) if(欲查找值等于欲查找值等于dataI) printf(“找到数据找到数据”)； else if(I数据个数数据个数) printf(“未能找到数据未能找到数据”)； I+；三三、 算法的简单分析算法的简单分析1 算法的评价准则（首先，算法必须是算法的评价准则（首先，算法必须是“正正确确”的）的） （1）执行算法所耗费的时间（效率）执行算法所耗费的时间（效率 要高）。要高）。 （2）执行算法所耗费的存储空间（主要考）执行算法所耗费的存储空间（主要考虑辅存空间；低存储要求）。虑辅存

37、空间；低存储要求）。 （3）算法的可读性、易维护性要好（易于）算法的可读性、易维护性要好（易于理解，易于编码，易于调试）。理解，易于编码，易于调试）。56算法效率算法效率用依据该算法编制的程用依据该算法编制的程序在计算机上执行所序在计算机上执行所消耗的时间消耗的时间来来度量度量A.事后统计事后统计利用计算机内记时功能，利用计算机内记时功能，不同算法的程序可以用一组或多组相同不同算法的程序可以用一组或多组相同的统计数据区分的统计数据区分缺点：缺点：必须先运行依据算法编制的程序必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣软件等

38、环境因素，掩盖算法本身的优劣57B.事前分析估计事前分析估计一个高级语言程序在计一个高级语言程序在计算机上运行所消耗的时间取决于：算机上运行所消耗的时间取决于： 依据的算法选用何种策略依据的算法选用何种策略 问题的规模问题的规模 程序语言程序语言 编译程序产生机器代码质量编译程序产生机器代码质量 机器执行指令速度机器执行指令速度 同一个算法用不同的语言、不同的编译程同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适所以使用绝对时间单位衡量算法效率不合适58时间复杂度：基本操作重复执行的次时间复杂

39、度：基本操作重复执行的次数的阶数数的阶数 T(n)=o(f(n)空间复杂度：空间复杂度：s(n)=o(f(n)例例15：N N矩阵相乘矩阵相乘for(i=1;i=n;i+)/n+1 for(j=1;j=n;j+)/n(n+1) cij=0;/n*n for(k=1;k=n;k+)/n*n(n+1) cij=cij+aik*bkj;/n*n*n 2 算法的简单分析：算法的简单分析：1、程序正确性的四个层面：、程序正确性的四个层面： （1）不含语法错误）不含语法错误 （2）程序对于）程序对于n组输入数据能够得出满足规格组输入数据能够得出满足规格说明要求的结果。说明要求的结果。 （3）程序对于精心选

40、择的典型、边界性的）程序对于精心选择的典型、边界性的n组组输入数据能得出满足规格说明要求的结果。输入数据能得出满足规格说明要求的结果。 （4）程序对于一切合适的输入数据都能得出）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。满足规格说明要求的结果（穷举）。2、算法效率的度量、算法效率的度量（1）程序运行所耗费的时间）程序运行所耗费的时间(由下列因素决定由下列因素决定)： 算法所选用的策略算法所选用的策略 问题的规模问题的规模 书写程序所采用的语言书写程序所采用的语言 编译程序所产生的机器代码的质量编译程序所产生的机器代码的质量 机器执行指令的速度机器执行指令的速度 一个算法

41、耗费的时间一个算法耗费的时间=算法中每条语句的执行时间之算法中每条语句的执行时间之和。和。 若不考虑机器硬、软件因素，可以认为算法若不考虑机器硬、软件因素，可以认为算法“运行工运行工作量作量”的大小是问题规模的函数的大小是问题规模的函数。算法的时间复杂度算法的时间复杂度- 算法算法( (或程序或程序) )中基本操作中基本操作( (或语句或语句) )重复执行的次数的总和。重复执行的次数的总和。 设设n n为求解的问题的规模为求解的问题的规模, ,基本操作基本操作( (或语句或语句) )执行次数执行次数总和称为语句频度总和称为语句频度, ,记作记作f(n)f(n)；时间复杂度记作；时间复杂度记作T

42、(n),T(n),有：有： T(n)=O(f(n) T(n)=O(f(n) 例例 int s int s； scanf(scanf(“%d%d”,&s),&s)； s+s+； printf(printf(“%d%d”,s),s)； 其中：语句频度为：其中：语句频度为：f(n)=f(1)=3f(n)=f(1)=3 时间复杂度为：时间复杂度为：T(n)=O(f(n)=O(3)=O(1T(n)=O(f(n)=O(3)=O(1） O(1)O(1)称成为常量阶称成为常量阶/ /常量数量级常量数量级例例 分析下面的算法分析下面的算法 void sum(int a,int n) void sum(int a

43、,int n) int s=0,i int s=0,i； / 1/ 1次次 for(i=0for(i=0；inin；i+) / ni+) / n次次( (严格为严格为2*(n+1)2*(n+1)次）次） s=s+ais=s+ai； / n/ n次次 printf(printf(“%d%d”,s),s)； / 1/ 1次次 其中：语句频度为其中：语句频度为：f(n)=1+n+n+1f(n)=1+n+n+1 时间复杂度为：时间复杂度为：T(n)=O(f(n)=O(2n+2)=O(nT(n)=O(f(n)=O(2n+2)=O(n） O(n)O(n)称成为线性阶称成为线性阶/ /线性数量级线性数量级例

44、例 分析下面的算法分析下面的算法 1. void sum(int m,int n) 1. void sum(int m,int n) 2. int i,j,s=0 2. int i,j,s=0； / 1/ 1次次 3. for(i=13. for(i=1；i=mi=m；i+) / mi+) / m次次 4. for(j=14. for(j=1；j=nj=n；j+) / m*nj+) / m*n次次 5. s+5. s+； / m*n/ m*n次次 6. printf(6. printf(“%d%d”,s),s)； / m/ m次次 7. 7. 8. 8. 其中其中:f(m,n)=1+m+2*m

45、*n+m=2mn+2m+1:f(m,n)=1+m+2*m*n+m=2mn+2m+1 当当m=nm=n时时,f(n)=2n,f(n)=2n2 2+2n+1+2n+1 T(n)=O(f(n)=O(2n T(n)=O(f(n)=O(2n2 2+2n+1)=O(n+2n+1)=O(n2 2) ) O(n O(n2 2 ) ) 称成为平方阶称成为平方阶/ /平方数量级平方数量级例例 分析下面的算法；当分析下面的算法；当n=5,n=5,指出输出结果指出输出结果 1. void sum(int n) 1. void sum(int n) 2. int i,j,s=0 2. int i,j,s=0； / 1/

46、 1次次 3. for(i=13. for(i=1；i=ni=n；i+) / ni+) / n次次 4. for(j=14. for(j=1；j=ij=i；j+) / ?j+) / ?次次 5. s+5. s+； / ?/ ?次次 6. printf(6. printf(“%d%d”,s),s)； / n/ n次次 7. 7. 8. 8. 其中：第其中：第4 4行的次数为行的次数为 1+2+.+n=n(1+n)/21+2+.+n=n(1+n)/2 第第5 5行的次数为行的次数为 1+2+.+n=n(1+n)/2 1+2+.+n=n(1+n)/2 f(n)=1+n+n(n+1)+n=n f(n)

47、=1+n+n(n+1)+n=n2 2+3n+1+3n+1 T(n)=O(f(n)=O(n T(n)=O(f(n)=O(n2 2） O(nO(n2 2）称成为平方阶）称成为平方阶/ /平方数量级平方数量级65例 求解：S=1!+2!+.+n!算法1： long sum_of_fac(int n) long s=0,t,i,j; for(i=1;i=n;i+) /n次 t=1; /n次 for(j=1;j=i;j+) /n*(n+1)/2次 t*=i; /n*(n+1)/2次 s+=t; /n次 return (s); /1次 f(n)=n+n+n*(n+1)/2+ n*(n+1)/2+n+1=n

48、2+4n+1T(n)=O(f(n)=O(n2)求i!66例 (续）： 求解：S=1!+2!+.+n!算法2： long sum_of_fac(int n) long s=0,t,i; t=1; /1次 for(i=1;i=n;i+) /n次 t*=i; /n次 s+=t; /n次 return (s); /1次 f(n)=1+n+n+n+n+1=3n+2T(n)=O(f(n)=O(n)求i!（2）问题的规模（）问题的规模（size)- 算法求解问题的输入量（或初始数据量）。算法求解问题的输入量（或初始数据量）。（3）不考虑机器软硬件环境时算法的时间耗费：）不考虑机器软硬件环境时算法的时间耗费：

49、 设：执行每条语句所需时间为单位时间，则：设：执行每条语句所需时间为单位时间，则： 一个算法耗费的时间一个算法耗费的时间=所有语句的频度之和。所有语句的频度之和。 时间复杂度时间复杂度T(n)- 即：时间耗费，它是算法求解问题即：时间耗费，它是算法求解问题n的函数。的函数。 渐近时间复杂度渐近时间复杂度- 即当问题的规模即当问题的规模n时的时间复杂度时的时间复杂度T(n)的数量级（阶），记的数量级（阶），记作：作：T(n)=O(f(n)评价一个算法的时间性能，主要标准是算法的渐近时间评价一个算法的时间性能，主要标准是算法的渐近时间复杂度复杂度(Time Complexity)68例例 x=1;

50、 for (I=1;I=n;I+) for (j=1;j=n;j+) for (k=1;k=n;k+) x+;分析：从内层向外层循环看执行次数，为分析：从内层向外层循环看执行次数，为n3+1，则，则T(n)= O(n3+1)，取，取T(n)数量级，得最后结数量级，得最后结果为：果为： T(n)= O(n3)69例例 x=1; for (I=1;I=n;I+) for (j=1;j=I;j+) for (k=1;k=j;k+) x+;由于内循环的执行次数虽与规模由于内循环的执行次数虽与规模n无直接关无直接关系，但与外循环的变量取值有关。因此系，但与外循环的变量取值有关。因此从内层向外层循环分析执

51、行次数从内层向外层循环分析执行次数。7071727374 即即: T(n)=n(n+1)(2n+1)/6+n(n+1)/2/2 所以：所以： T(n)=O(n3/6+低次项低次项) 取取T(n)的数量级阶，的数量级阶，得最后结果为：得最后结果为： T(n)=O(n3)75 常见函数的时间复杂度按数量递增排列常见函数的时间复杂度按数量递增排列及增长率及增长率 常数阶常数阶O(1) 对数阶对数阶O(log2n) 线性阶线性阶O(n) 线性对数阶线性对数阶O(nlog2n) 平方阶平方阶O(n2) 立方阶立方阶O(n3) k次方阶次方阶O(nk) 指数阶指数阶O(2n)76Growth Rate G

52、raph77换一台更快的计算机，还是换一种更快的算法？T(n)nnChangen/n10n1,00010,000n = 10n1020n5005,000 n = 10n105nlogn2501,842 10 n n 10n7.372n270223 n = 10n3.162n1316 n = n + 3-结论：换一种更快的算法，而不要换一台结论：换一种更快的算法，而不要换一台 更快的计算机更快的计算机78 本章本章总总结结 数据、数据结构等基本概念数据、数据结构等基本概念 数据结构的三个方面的内容数据结构的三个方面的内容 线性和非线性结构的逻辑特征线性和非线性结构的逻辑特征 数据存储的四种基本方

53、法数据存储的四种基本方法 算法、算法的时间复杂度及其分析算法、算法的时间复杂度及其分析的简易方法的简易方法教材及主要参考书教材及主要参考书唐宁九，游洪跃，朱宏，杨秋辉编著，数据结构与算法设计，四川大学出版社A.V.Aho,J.E.Hopcroft and J.D.Ullman,Data Structures and Algorithms,by AddisonWesley Publishing Company,Inc.,1983 美Cliford A. Shaffer著，A Practical Introduction to Data Structures and Algorithm Analysis(数据结构与算法设计C+版)，电子工业出版社殷人昆，陶永雷，谢若阳，盛绚华编著数据结构（用面向对象方法与C+描述）清华大学出版社 Knuth Donald E.The Art of Computer Programming AddisonWesley Publishing Company,Inc.,1973 Volume 1: Fundamental Algorithms, Volume 2: Seminumerical Algorithms, Volume 3: Sorting and Searching.81Thank you very much!