第1章数据结构绪论

1、1算法与数据结构算法与数据结构主主 讲：讲： 高高 慧慧电电 话：话： 1360645719413606457194E_mailE_mail： 2课程的重要性课程的重要性 数据结构是介于数学、计算机硬件和计算机软件数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，之间的一门计算机科学与技术专业的核心课程，是编译原理、操作系统、数据库、人工智能等课是编译原理、操作系统、数据库、人工智能等课程的基础；程的基础； 数据结构技术也广泛应用于信息科学、系统工程、数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域；应用数学以及各种工程技术领域； 计算

2、机程序设计的重要理论基础计算机程序设计的重要理论基础 程序程序 = = 算法算法 + + 数据结构数据结构为计算机处理为计算机处理问题编制的一问题编制的一组指令集组指令集处理问题的策略处理问题的策略问题的数学模型问题的数学模型计算机科学与技术专业综合考试内容计算机科学与技术专业综合考试内容34C语言语言 数据结构数据结构 软件工程软件工程掌握基本掌握基本编程方法编程方法掌握数据组掌握数据组织和数据处织和数据处理的方法理的方法掌握大型软掌握大型软件开发方法件开发方法学习识字学习识字学习写作文学习写作文学习写小说学习写小说与语文学习过程类似动手能力（上机）动手能力（上机）与相关课程的关系与相关课程

3、的关系5课程目的课程目的 能够分析研究计算机加工的对象的特性，获得能够分析研究计算机加工的对象的特性，获得其其逻辑结构逻辑结构，根据需求，选择合适的，根据需求，选择合适的存储结构存储结构及其相应的及其相应的算法算法 学习并掌握一些常用的算法学习并掌握一些常用的算法 复杂程序设计的训练过程，要求编写的程序结复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读构清楚和正确易读 初步掌握初步掌握算法的时间分析和空间分析的技术算法的时间分析和空间分析的技术6基本设想基本设想 学时：学时： 8080学时，理论学时，理论6464 + + 上机上机1616； 基本要求：基本要求： 上课认真听讲；上课认真

4、听讲； 课下阅读教材，课下阅读教材，认真、独立认真、独立完成书面作业；完成书面作业； 多写算法，多练习多写算法，多练习，重视上机实践；，重视上机实践； 考试：考试： 平时成绩平时成绩30% + 30% + 卷面成绩卷面成绩70%70%； 平时成绩包括考勤、作业、平时成绩包括考勤、作业、随堂测验随堂测验和上机；和上机； 理论和上机课共缺席理论和上机课共缺席3 3次及以上者次及以上者取消考试资格；取消考试资格；7教教 材材 必修书必修书: : 数据结构教程数据结构教程( (第第4 4版版) ) 李春葆等李春葆等 清华大学出版社清华大学出版社 数据结构教程数据结构教程( (第第4 4版版) )上机实

5、验指导上机实验指导 李春葆等李春葆等 清华大学清华大学出版社出版社 参考书参考书: : 数据结构教程数据结构教程( (第第4 4版版) )学习指导学习指导 李春葆等李春葆等 清华大学出版清华大学出版社社 数据结构（数据结构（C C语言版）语言版）( (严蔚敏严蔚敏) ) 清华大学出版社清华大学出版社 算法与数据结构（陈守孔）机械工业出版社算法与数据结构（陈守孔）机械工业出版社 C C程序设计程序设计( (谭浩强谭浩强) ) 清华大学出版社清华大学出版社-上机必备上机必备 网络资源：网络资源： 烟台大学计算机学院精品课程烟台大学计算机学院精品课程 等等8课时设置课时设置 第第1 1章章 绪论绪论

6、 5 5学时学时第第2 2章章 线性表线性表 1010学时学时第第3 3章章 栈和队列栈和队列 6 6学时学时第第4 4章章 串串 4 4学时学时第第5 5章章 递归递归 2 2学时学时第第6 6章章 数组和广义表数组和广义表 4 4学时学时第第7 7章章 树和二叉树树和二叉树 1010学时学时第第8 8章章 图图 9 9学时学时第第9 9章章 查找查找 7 7学时学时第第1010章章 内排序内排序 7 7学时学时第第1111章章 外排序外排序 不不 讲讲第第1 12 2章章 文件文件 不不 讲讲第第1 13 3章章 采用面向对象的方法描述算法采用面向对象的方法描述算法 不不 讲讲9第第1章章

7、 绪论绪论 1.1 什么是数据结构什么是数据结构 1.2 算法及其描述算法及其描述 1.3 算法分析算法分析 1.4 数据结构算法程序数据结构算法程序（略）（略）101.1 什么是数据结构什么是数据结构 1.1.1 数据结构的定义数据结构的定义 1.1.2 逻辑结构类型逻辑结构类型 1.1.3 存储结构类型存储结构类型 1.1.4 数据结构和数据类型数据结构和数据类型11 1.1.1 数据结构的定义数据结构的定义 三个层次三个层次的概念：数据、数据元素、数据项的概念：数据、数据元素、数据项 数据：数据：是所有能被输入到计算机中，且能被计算是所有能被输入到计算机中，且能被计算机处理的符号的集合。

8、机处理的符号的集合。 数据元素：数据元素：是数据是数据(集合集合)中的一个中的一个“个体个体”，是数，是数据的据的基本单位基本单位。不同的条件下可称为元素、结点、。不同的条件下可称为元素、结点、顶点、记录等，通常作为一个整体考虑和处理。顶点、记录等，通常作为一个整体考虑和处理。 数据项：数据项：组成数据元素的有特定意义的组成数据元素的有特定意义的最小单位最小单位，不可分割。不可分割。 数据对象：数据对象：是具有是具有相同性质相同性质的若干个数据元素的的若干个数据元素的集合。集合。12例例1.1 有一个学生表如下所示，这个表中的数据元有一个学生表如下所示，这个表中的数据元素是学生记录素是学生记录

9、,每个数据元素由四个数据项每个数据元素由四个数据项(即学号、即学号、姓名、性别和班号姓名、性别和班号)组成。组成。学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901表表1.1 学生表学生表 数据元素数据元素数据项数据项13例例1.1 学生档案管理系统学生档案管理系统 计算机处理的对象：计算机处理的对象：表表 元素间的关系：元素间的关系：一对一对一的线性关系一的线性关系 施加于对象上的操作：施加于对象上的操作：查询、插入、删除等查询、插入、删除等 u数学

10、模型：数学模型：各种表格各种表格u数据结构：数据结构：线性结构线性结构u算法：算法：如何进行各种如何进行各种查询查询14其他例其他例 人人-机博奕机博奕.格局格局15人人-机博奕机博奕 计算机处理的对象：计算机处理的对象：格局树格局树 元素间的关系：元素间的关系：一一对多的层次关系对多的层次关系 施加于对象上的操施加于对象上的操作：查询、插入、作：查询、插入、删除等删除等 u数学模型：数学模型：棋盘棋盘u数据结构：数据结构：树形结构树形结构u算法：算法：博弈的规则和博弈的规则和策略策略16其他例其他例 快速送达疫苗快速送达疫苗 已知有邻近的五个村子发生了疫情，我们要已知有邻近的五个村子发生了疫

11、情，我们要用汽车快速地将疫苗送达到用汽车快速地将疫苗送达到5个村子。目标是个村子。目标是寻找一条消耗时间最少的路线。寻找一条消耗时间最少的路线。 胜利胜利 发生疫情的五个村子发生疫情的五个村子河源河源长利长利太华太华桦南桦南1275344123 村子联系网络村子联系网络v1v5v2v4v31275413432抽象抽象 17快速送达疫苗快速送达疫苗 计算机处理的对象：计算机处理的对象：图图 元素间的关系：元素间的关系：多多对多的网状关系对多的网状关系 施加于对象上的操施加于对象上的操作：查询、插入、作：查询、插入、删除等删除等 u数学模型：数学模型：图图u数据结构：数据结构：图形结构图形结构u算

12、法：算法：如何求距离、如何求距离、最短路径等最短路径等18结结 论论 数据结构数据结构是一门研究是一门研究非数值计算非数值计算的程序的程序设计问题中计算机的设计问题中计算机的操作对象操作对象以及它们以及它们之间的之间的关系关系和和操作操作的学科。的学科。 三要素：三要素：对象、关系及操作对象、关系及操作 学习数据结构的目的之一是，将实际问学习数据结构的目的之一是，将实际问题中涉及的处理对象在计算机中表示出题中涉及的处理对象在计算机中表示出来并对它们进行处理。来并对它们进行处理。19数据结构的定义数据结构的定义（P2） 数据以及数据元素相互之间的联系数据以及数据元素相互之间的联系 相互之间存在着

13、某种特定关系的数据相互之间存在着某种特定关系的数据元素的集合元素的集合 带结构的数据元素的集合带结构的数据元素的集合20数据结构（逻辑结构）的描述或表示数据结构（逻辑结构）的描述或表示 为了更确切地描述一种数据结构，通常采用为了更确切地描述一种数据结构，通常采用二元组表示：二元组表示： B=(D,R) 其中，其中，B是一种数据结构，它由数据元素的是一种数据结构，它由数据元素的集合集合D和和D上二元关系的集合上二元关系的集合R所组成。所组成。 D=di| 1in,n0 R=rj| 1jm,m0 21 D上的一个关系上的一个关系r是是序偶的集合序偶的集合； 对于对于r中的任一序偶中的任一序偶(x,

14、yD),我们称序偶的我们称序偶的第一结点为第二结点的第一结点为第二结点的直接前驱直接前驱结点结点(简称前驱结简称前驱结点点),称第二结点为第一结点的称第二结点为第一结点的直接后继直接后继结点结点(简称简称后继结点后继结点)。 若某个结点没有前驱若某个结点没有前驱,则称该结点为则称该结点为开始结点开始结点；若；若某个结点没有后继某个结点没有后继,则称该结点为则称该结点为终端结点终端结点；除此；除此之外的结点称为之外的结点称为内部结点内部结点。 说明：说明：表示有向关系，表示有向关系，(x,y)表示无向关系。表示无向关系。逻辑关系的表示逻辑关系的表示22 表表1.11.1中的记录顺序反映了数据元素

15、之间的逻辑关系中的记录顺序反映了数据元素之间的逻辑关系, , 用学号标识每个学生记录用学号标识每个学生记录, ,这种逻辑关系可以表示为：这种逻辑关系可以表示为： ,学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901举例：逻辑关系的表示举例：逻辑关系的表示P3忽略不看忽略不看23【例】【例】用二元组表示例用二元组表示例1.1的学生表，表中共的学生表，表中共有有7个结点，依次用个结点，依次用k1k7表示，则对应的表示，则对应的二元组表示为二元组表示为 B=

16、(D,R) 其中：其中： D=k1, k2, k3, k4, k5, k6, k7 R=r r=, , , , , 24 还还可以可以利用图形形象地表示逻辑结构利用图形形象地表示逻辑结构 例如，例如，“学生表学生表”数据结构用下图的图形表示数据结构用下图的图形表示 k1 k2 k3 k4 k5 k6 k7 251.1.2 逻辑结构类型逻辑结构类型 (1) 线性结构线性结构【例【例1.3】 结点之间关系：结点之间关系：一对一一对一 特点：特点： 开始结点和终端结点都是唯一的；开始结点和终端结点都是唯一的； 除了开始结点和终端结点以外，其余结点都有且除了开始结点和终端结点以外，其余结点都有且仅有一

17、个前驱结点，有且仅有一个后继结点。仅有一个前驱结点，有且仅有一个后继结点。26 结点之间关系：结点之间关系：一对多一对多 特点：特点： 开始结点开始结点唯一，唯一，终端结点不终端结点不唯一；唯一； 除终端结点以外除终端结点以外，每个结点有一个或多个后每个结点有一个或多个后继继结点；除开始结点外，每个结点有且仅有结点；除开始结点外，每个结点有且仅有一个前驱结点。一个前驱结点。 (2) 树形结构树形结构【例【例1.4】27 结点之间关系：结点之间关系：多对多多对多 特点：特点： 没有开始结点和终端结点没有开始结点和终端结点； 所有结点都可能有多个前驱结点和多个后继结点。所有结点都可能有多个前驱结点

18、和多个后继结点。 (3) 图形结构图形结构【例【例1.5】28集合结构：集合结构： 线性结构：线性结构：树形结构：树形结构： 图形结构：图形结构：291.1.3 存储结构类型存储结构类型 (1) 顺序存储结构顺序存储结构 (2) 链式存储结构链式存储结构 (3) 索引存储结构索引存储结构 (4) 散列存储结构散列存储结构 存储结构存储结构(即物理结构即物理结构)： 是数据结构在计算机中的表示。是数据结构在计算机中的表示。30 存储结构存储结构(物理结构物理结构)：数据结构在计算机中的表示。数据结构在计算机中的表示。顺序存储结构：顺序存储结构：借助元素在存储器中的相对位置表示数据借助元素在存储器

19、中的相对位置表示数据元素之间的关系（逻辑相邻，物理位置也相邻）元素之间的关系（逻辑相邻，物理位置也相邻）链式存储结构：链式存储结构：借助指示元素存储地址的指针（借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系（逻辑相邻，物理位置不一表示数据元素之间的逻辑关系（逻辑相邻，物理位置不一定相邻）定相邻）【例例】 a1,a2, ana1an1000a2a310021004a1a3a4a2300020001000311.1.4 数据类型和数据结构数据类型和数据结构 (1) 数据类型数据类型 一个一个值的集合值的集合和定义在此集合上的和定义在此集合上的一组操作一组操作的总称的总称 规

20、定了在程序执行期间变量或表达式规定了在程序执行期间变量或表达式所有可能取所有可能取值的范围值的范围以及在这些值上以及在这些值上允许进行的操作允许进行的操作。 如：如：int整型数据类型整型数据类型所有整数的集合所有整数的集合(在在16位计算机中为位计算机中为3276832767的全的全体整数体整数)和相关的整数运算和相关的整数运算(如、等如、等)。 引入数据类型的目的：引入数据类型的目的：使用与实现分离使用与实现分离 数据类型是已经实现的数据结构数据类型是已经实现的数据结构（P8）32数据对象数据对象D上的上的关系集关系集对对D的基本的基本操作集操作集 (2) 抽象数据类型抽象数据类型 抽象数

21、据类型抽象数据类型(Abstract Data Type简写为简写为ADT) 用户进行软件系统设计时从问题的数学模型中抽用户进行软件系统设计时从问题的数学模型中抽象出来的象出来的逻辑数据结构和逻辑数据结构上的运算逻辑数据结构和逻辑数据结构上的运算,而而不考虑不考虑计算机的具体存储结构和运算的具体实计算机的具体存储结构和运算的具体实现算法。现算法。 一个数学模型以及定义在该模型上的一组操作一个数学模型以及定义在该模型上的一组操作 抽象数据类型的三元组表示：（抽象数据类型的三元组表示：（D，R，P）33ADT Complex 数据对象：数据对象： D=e1,e2|e1,e2均为实数均为实数数据关系

22、：数据关系： R=| e1是复数的实数部分，是复数的实数部分，e2 是复数的虚数部分是复数的虚数部分 e1e2i例如，抽象数据类型例如，抽象数据类型复数复数的定义：的定义：34基本运算：基本运算： AssignComplex(&Z,v1,v2):构造复数构造复数Z。 DestroyComplex(&Z):复数复数Z被销毁。被销毁。 GetReal(Z,&real):返回复数返回复数Z的实部值。的实部值。 GetImag(Z,&Imag):返回复数返回复数Z的虚部值。的虚部值。 Add(z1,z2,&sum):返回两个复数返回两个复数z1,z2的和。的和。

23、 ADT Complex351.2 算法及其描述算法及其描述 1.2.1 什么是算法什么是算法 1.2.2 算法描述算法描述361.2.1 什么是算法什么是算法 算法算法 对特定问题求解步骤的一种描述，是指令的有限序列。对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。其中每一条指令表示一个或多个操作。 算法的五个重要的特性算法的五个重要的特性 (1) 有穷性有穷性：在有穷步之后结束：在有穷步之后结束 (2) 确定性确定性：无二义性：无二义性 (3) 可行性可行性：算法中描述的操作都可以通过已经实现的算法中描述的操作都可以通过已经实现的基本操作执行有限次来实现基

24、本操作执行有限次来实现 (4) 有输入：有输入：零个或多个零个或多个 (5) 有输出：有输出：一个或多个一个或多个37算法与程序的区别算法与程序的区别 程序不一定满足有穷性程序不一定满足有穷性。如操作系统，只要整个系。如操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法。不是一个算法。 程序是用机器可执行的语言书写的程序是用机器可执行的语言书写的，程序中的指令，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。必须是机器可执行的，而算法中的指令则无此限制。 算法代表了对问题的解，而算法代表了对问题的解，而程序则是算法

25、在计算机程序则是算法在计算机上的特定的实现上的特定的实现。一个算法若用程序设计语言来描。一个算法若用程序设计语言来描述，则它就是一个程序。述，则它就是一个程序。38(1) 描述一描述一void exam1() n2; while (n%20) nn+2; printf(%dn,n); (2) 描述二描述二void exam2() y=0; x=5/y; printf(“%d,%dn”,x,y); 以下两段描述均不能满足算法的特征以下两段描述均不能满足算法的特征,试问它们违反了哪些特征？试问它们违反了哪些特征？ 解：解：(1)算法是一个算法是一个死循环死循环，违反了算法的，违反了算法的有穷性有穷

26、性特征。特征。 (2)算法包含算法包含除零错误除零错误，违反了算法的，违反了算法的可行性可行性特征。特征。39 1.2.2 算法描述算法描述 算法可用文字描述（算法可用文字描述（P11P11例例1.71.7），也可用语言、图），也可用语言、图形和表格等形和表格等 本书中采用本书中采用C/C+C/C+语言语言描述算法描述算法 C+C+语言中提供了一种引用运算符语言中提供了一种引用运算符“& &”（P9P9） 引用是个引用是个别名别名, ,当建立引用时当建立引用时, ,程序用另一个已定义程序用另一个已定义的变量或对象的变量或对象( (目标目标) )的名字的名字初始化初始化它它, ,

27、从那时起从那时起, ,引用引用作为目标的别名而使用作为目标的别名而使用, ,对引用的改动实际就是对目对引用的改动实际就是对目标的改动标的改动 例如：例如：int &b=a; /*b是是a的引用变量的引用变量*/40 引用引用常用于函数形参中，采用引用型形参时，在常用于函数形参中，采用引用型形参时，在函数调用结束时函数调用结束时将形参的改变回传给实参。将形参的改变回传给实参。 【例】例】有如下函数有如下函数(其中的形参均为其中的形参均为引用型形参引用型形参) void swap(int &x, int &y) /*形参前的形参前的“&”符号不是取地址运算符符号不是

28、取地址运算符*/ int tmp=x; x=y; y=tmp; 当用执行语句当用执行语句swap(a,b)时，时，a和和b的值发生了交换。的值发生了交换。41 void swap1(int x,int y) int tmp; tmp=x; x=y; y=tmp; 注意：注意：a a和和b b的值不会发生交换。的值不会发生交换。形参形参实参实参 10 10a x形参形参实参实参编写一个函数编写一个函数swap1(x,y)，当执行语句，当执行语句swap1(a,b)时时,交换交换a和和b的值。的值。值传递值传递42 为此，为此，采用指针的方式来回传形参的值采用指针的方式来回传形参的值。 将上述函数

29、改为：将上述函数改为： void swap2(int *x,int *y) int tmp; tmp=*x;/*将将x的值放在的值放在tmp中中*/ *x=*y; /*将将x所指的值改为所指的值改为*y*/ *y=tmp； /*将将y所指的值改为所指的值改为tmp*/ 上述函数的调用改为上述函数的调用改为swap2(&a,&b)，显然，显然远不如采用引用方式简洁。远不如采用引用方式简洁。 所以本书后面很多算法都采用引用形参。所以本书后面很多算法都采用引用形参。 10&a x形参形参实参实参地址传递地址传递431.3 算法分析算法分析 1.3.2 算法效率分析算法效率分析

30、 1.3.3 算法存储空间分析算法存储空间分析 1.3.1 算法设计的目标算法设计的目标 441.3.1 算法设计的目标算法设计的目标 正确性正确性：CorrectnessCorrectness 可使用性可使用性：用户友好性：用户友好性 可读性可读性: Readability: Readability 健壮性健壮性: Robustness: Robustness 高效率与低存储量需求高效率与低存储量需求 时间复杂度时间复杂度 空间复杂度空间复杂度45 用高级语言编写的程序，运行的时间主要用高级语言编写的程序，运行的时间主要取决于如下因素：取决于如下因素： 硬件的速度；硬件的速度； 编写程序的语

31、言：级别越高，效率越低；编写程序的语言：级别越高，效率越低； 编译程序所产生的目标代码的质量；编译程序所产生的目标代码的质量； 算法选用的策略；算法选用的策略； 问题的规模；问题的规模；前三条与算前三条与算法设计无关法设计无关w排除其他影响算法效率的因素，认为一个算法的排除其他影响算法效率的因素，认为一个算法的运行代价只依赖于运行代价只依赖于问题的规模，问题的规模，或者说它是或者说它是问题问题规模的函数规模的函数w这种函数被称为算法的这种函数被称为算法的时间复杂度时间复杂度和和空间复杂度。空间复杂度。 衡量算法时间效率的方法主要有两大类：衡量算法时间效率的方法主要有两大类： 事后统计：利用计算

32、机的时钟；事后统计：利用计算机的时钟； 事前分析估算事前分析估算1.3.2 算法效率分析算法效率分析 46 一个算法是由一个算法是由控制结构控制结构( (顺序、分支和循环三种顺序、分支和循环三种) )和和原操作原操作构成的，则算法时间取决于两者的综合效果。构成的，则算法时间取决于两者的综合效果。 原操作：原操作：对于所研究的问题来说是对于所研究的问题来说是基本运算基本运算的操作。的操作。 被视为算法被视为算法基本运算基本运算的一般是的一般是最深层最深层循环内的语句。循环内的语句。 通常把算法中包含基本运算次数的多少称为通常把算法中包含基本运算次数的多少称为算法的算法的时间复杂度，记作时间复杂度

33、，记作T(n)T(n)。 算法中算法中基本运算次数基本运算次数T(n)T(n)是问题规模是问题规模n n的某个函数的某个函数f(n),f(n),记作：记作： T(n)=O(f(n)T(n)=O(f(n)大大O表示法：表示随问题规模表示法：表示随问题规模n的增大，算法执行时间的增长率的增大，算法执行时间的增长率 和和f(n)的增长率相同。的增长率相同。1.3.2 算法效率分析算法效率分析 47 大大O表示法：表示法：只求出只求出T(n)的的最高阶，忽略其低阶项和常系数最高阶，忽略其低阶项和常系数这样既可简化这样既可简化T(n)的计算，又能比较客观地反映出的计算，又能比较客观地反映出当当n很大时，

34、算法的时间性能。很大时，算法的时间性能。 例如，例如，T(n)=3n2-5n+10000=O(n2)48+x; s=0;时间复杂度时间复杂度 for(j=1;j=n;+j)+x; s+=x;语句的频度为语句的频度为1，时间复杂度为，时间复杂度为O(1)。语句的频度为语句的频度为n，时间复杂度为，时间复杂度为O(n)。常数阶常数阶线性阶线性阶49时间复杂度时间复杂度 for(j=1;j=n;+j)for(k=1;k=n;+k)+x; s+=x;语句频度语句频度为为n n，时间复杂度为，时间复杂度为O(n2)k=0;for(i=1;i=n;i+)for(j=1;j=i;j+)aij=+k;语句频度

35、为：语句频度为： n*(n+1)/2，时间复杂度为时间复杂度为O(n2)平方阶平方阶50时间复杂度时间复杂度for(j=1;j=n;j*=2)for(k=1;k=n;+k)s+;语句频度为：语句频度为：时间复杂度为时间复杂度为O(nlog2n)nnnnjnjnk2log1 log11log22 线性对数阶线性对数阶51时间复杂度时间复杂度例：矩阵乘法例：矩阵乘法 for( i = 1; i = n; i+) /(n+1) for( j = 1; j = n; j+) /n(n+1) cij = 0； /n2 for( k= 1; k= n; k+) / n2(n+1) cij = cij+ai

36、k* bkj; / n3 说明：各语句行后的数字是该语句重复执行的次数说明：各语句行后的数字是该语句重复执行的次数; 本算法时间复杂度为本算法时间复杂度为O( n3)立方阶立方阶52 各种不同数量级对应的值存在着如下关系：各种不同数量级对应的值存在着如下关系： O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)53 例例1.8 求两个求两个n阶方阵的相加阶方阵的相加C=A+B的算法如下的算法如下,分析其时间复杂度。分析其时间复杂度。 #define MAX 20 /*定义最大的方阶定义最大的方阶*/ void matrixadd(int n,int A

37、MAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+)for (j=0;jn;j+) Cij=Aij+Bij; 54 该算法中的基本运算是两重循环中最深层的语句该算法中的基本运算是两重循环中最深层的语句Cij=Aij+Bij，分析它的频度，即，分析它的频度，即： T(n)= =O(n2) 102101010*11ninininjnnnnn55时间复杂度时间复杂度 有的情况下，算法中基本操作重复执行的次数还有的情况下，算法中基本操作重复执行的次数还随随问题的输入数据集问题的输入数据集不同而不同。不同而不同。 【例例1.9】 在这种情况下

38、，可用在这种情况下，可用最坏最坏情况下的时间复杂度作情况下的时间复杂度作为时间复杂度为时间复杂度 有时，也可计算平均情况下的时间复杂度（有时，也可计算平均情况下的时间复杂度（P16定义定义1.1）在输入在输入I 下执行的基下执行的基本运算的次数本运算的次数任一输入任一输入I出出现的概率现的概率I DnP(I)*T(I)E(n)56 （略）（略）例例1.10 有如下递归算法：有如下递归算法： void fun(int a,int n,int k) /*数组数组a共有共有n个元素个元素*/ int i;if (k=n-1) for (i=0;in;i+) printf(%dn,ai);else f

39、or (i=k;in;i+)ai=ai+i*i; fun(a,n,k+1); 调用上述算法的语句为调用上述算法的语句为fun(a,n,0)，求其时间复杂度。，求其时间复杂度。 57 解：设解：设fun(a,n,0)的时间复杂度为的时间复杂度为T(n),则则fun(a,n,k)的执行时间为的执行时间为T1(n,k)，由，由fun()算法可知：算法可知： T1(n,k)=n 当当k=n-1时时 T1(n,k)= (n-k)+T1(n,k+1) 其他情况其他情况 则则 T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=n+(n-1)+2+T1(n,n-1)=n+(n-1)

40、+ +2+n=O(n2) 所以调用所以调用fun(a,n,0)的时间复杂度为的时间复杂度为O(n2)。 58 算法的存储量包括：算法的存储量包括：输入数据所占空间、程序本身输入数据所占空间、程序本身所占空间和所占空间和辅助变量所占空间。辅助变量所占空间。 空间复杂度是对一个算法在运行过程中空间复杂度是对一个算法在运行过程中临时占用的临时占用的存储空间存储空间大小的量度，一般也作为问题规模大小的量度，一般也作为问题规模n的函数，的函数，以数量级形式给出，记作：以数量级形式给出，记作： S(n) = O(g(n) 若所需额外空间相对于输入数据量来说是常数，则若所需额外空间相对于输入数据量来说是常数

41、，则称此算法为称此算法为原地工作。原地工作。 若所需存储量依赖于特定的输入，则通常按若所需存储量依赖于特定的输入，则通常按最坏情最坏情况况考虑。考虑。1.3.3 算法存储空间分析算法存储空间分析 59 （略）（略） 例例1.10 有如下递归算法：有如下递归算法： void fun(int a,int n,int k) /*数组数组a共有共有n个元素个元素*/ int i;if (k=n-1) for (i=0;in;i+) printf(%dn,ai);else for (i=k;in;i+)ai=ai+i*i; fun(a,n,k+1); 调用上述算法的语句为调用上述算法的语句为fun(a,

42、n,0)，求其空间复杂度。，求其空间复杂度。 60 解：设解：设fun(a,n,k)的临时空间大小为的临时空间大小为S(k)，其中定义，其中定义了一个辅助变量了一个辅助变量i，所以，所以 S(k)=1 当当k=n-1时时 S(k)= 1+S(k+1) 其他情况其他情况 则则fun(a,n,0)的空间复杂度为的空间复杂度为S(0)，由此可得：，由此可得： S(0)=1+S(1)=1+1+S(2)=1+1+1+S(n-1)=1+1+ +1+1=O(n) 所以调用所以调用fun(a,n,0)的空间复杂度为的空间复杂度为O(n)。 611.4 数据结构算法程序数据结构算法程序（略）（略） 数据结构对算

43、法的影响主要在两方面数据结构对算法的影响主要在两方面 （1 1）数据结构的存储能力）数据结构的存储能力数据结构存储能力强、存储信息多算法将会较数据结构存储能力强、存储信息多算法将会较好设计（时间少），存储空间大。好设计（时间少），存储空间大。时间和空间的平衡时间和空间的平衡（2 2）定义在数据结构上的操作）定义在数据结构上的操作在数据结构上定义基本操作算法调用这些基本在数据结构上定义基本操作算法调用这些基本操作。操作。62基本操作越完整，基本操作越完整，算法设计就越容易算法设计就越容易算法算法基本操作基本操作基本算法基本算法应用程序应用程序应用程序是通过调应用程序是通过调用基本算法实现的用基本

44、算法实现的63选择数据结构需要考虑的几个方面：选择数据结构需要考虑的几个方面：（1）数据结构要适应问题的状态描述）数据结构要适应问题的状态描述（2）数据结构应与所选择的算法相适应）数据结构应与所选择的算法相适应（3）数据结构的选择同时要兼顾程序设计的方便）数据结构的选择同时要兼顾程序设计的方便（4）灵活应用已有知识）灵活应用已有知识64例如，有若干学生数据（学生数小于例如，有若干学生数据（学生数小于50），每），每个学生数据包含学号（每个学生学号是惟一的，个学生数据包含学号（每个学生学号是惟一的，但学生记录不一定按学号顺序存放）、姓名、班但学生记录不一定按学号顺序存放）、姓名、班号和若干门课程

45、成绩（每个学生所选课程数目可号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超过能不等，但最多不超过6门）。门）。要求设计一个程序输出每个学生的学号、姓名要求设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从和平均分以及每门课程（课程编号从16）的平）的平均分。均分。65设计方案设计方案1 1：将学生的全部数据项放在一个表中，将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于课程最多可一个学生的全部数据对应一条记录。由于课程最多可选选6 6门，对应的成绩项也应有门，对应的成绩项也应有6 6个。对应的数据结构如个。对应的数据结构如下：下：struct stud int no;/*学号学号*/char name10;/*姓名姓名*/int bno;/*班号班号*/int deg1;/*课程课程1分数分数*/int deg2;/*课程课程2分数分数*/int deg3;/*课程课程3分数分数*/int deg4;/*课程课程4分数分数*/int deg5;/*课程课程5分数