《【精品】【考研计算机专业课】武汉大学数据结构ppt课件 第1章绪论（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】武汉大学数据结构ppt课件 第1章绪论（可编辑.ppt（94页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【考研计算机专业课】武汉大学数据结构PPT课件 第1章 绪论参考书参考书:1.数据结构教程数据结构教程(第第4版版)李春葆等李春葆等清华大学出版社清华大学出版社20132.数据结构（数据结构（C语言版）严蔚敏，吴伟民语言版）严蔚敏，吴伟民清华大学出清华大学出版社版社19973.数数据据结结构构（用用面面向向对对象象方方法法与与C+描描述述）殷殷人人昆昆等等清华大学出版社清华大学出版社1999C语言语言数据结构数据结构软件工程软件工程掌握基本编掌握基本编程方法程方法掌握数据组掌握数据组织和数据处织和数据处理的方法理的方法掌握大型软掌握大型软件开发方法件开发方法学习识字学习识字学习写作文学习写作文
2、学习写小说学习写小说基本要求课程关系与语文学习过程类比动手能力（上机）数据结构课程的地位数据结构课程的地位前期课程前期课程数据结构数据结构计算机基础计算机基础C语言语言离散数学离散数学后期课程后期课程操作系统操作系统编译原理编译原理数据库原理数据库原理软件工程软件工程承上承上启下启下计算机科学课程体系（偏软）计算机科学课程体系（偏软）学习和讲授方法学习和讲授方法l 演译法演译法先学习先学习/讲授理论知识，用知识解决问题讲授理论知识，用知识解决问题l 归纳法归纳法先解决具体问题，由此归纳出解决问题的理论知先解决具体问题，由此归纳出解决问题的理论知识识只有归纳法才能产生新的知识！只有归纳法才能产生
3、新的知识！1.1.软件开发过程（系统生命周期）软件开发过程（系统生命周期）阶段阶段基本任务基本任务1.需求获取需求获取定义用户要求定义用户要求规范声明规范声明2.需求分析需求分析问题分解成规模适中且便于处理的各个问题分解成规模适中且便于处理的各个部分（自顶向下、自底向上）部分（自顶向下、自底向上）3.功能设计功能设计建立软件逻辑结构建立软件逻辑结构数据对象各种操数据对象各种操作作4.求精和程序编码求精和程序编码编写程序代码编写程序代码选择存储表示，实现各选择存储表示，实现各种操作的算法种操作的算法5.正确性验证正确性验证证明程序正确、测试证明程序正确、测试发现和消除错误发现和消除错误1.1什么
4、是数据结构什么是数据结构数据：数据：是所有能被输入到计算机中，且能被计算机处理是所有能被输入到计算机中，且能被计算机处理的符号的集合。它是计算机操作的对象的总称，也是计的符号的集合。它是计算机操作的对象的总称，也是计算机处理的信息的某种特定的符号表示形式。算机处理的信息的某种特定的符号表示形式。数据元素：数据元素：是数据是数据(集合集合)中的一个中的一个“个体个体”，是数据的，是数据的基本单位。基本单位。数据对象：数据对象：是具有相同性质的若干个数据元素的集合。是具有相同性质的若干个数据元素的集合。2.2.数据结构的定义数据结构的定义 例如，例如，200402班为一个学生数据对象，而其中的班为
5、一个学生数据对象，而其中的“张三张三”是一个数据元素是一个数据元素)。数据结构数据结构是指数据以及数据元素相互之间的联系。可以看是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。作是相互之间存在着某种特定关系的数据元素的集合。因此，可时把数据结构看成是带结构的数据元素的集合。因此，可时把数据结构看成是带结构的数据元素的集合。数据结构包括如下几个方面：数据结构包括如下几个方面：逻辑结构。逻辑结构。数据元素之间的逻辑关系，即数据的逻辑结构。数据元素之间的逻辑关系，即数据的逻辑结构。存存储储结结构构。数数据据元元素素及及其其关关系系在在计计算算机机存存储储器器
6、中中的的存存储储方方式，即数据的存储结构，也称为数据的物理结构。式，即数据的存储结构，也称为数据的物理结构。运算。运算。施加在该数据上的操作，即数据的运算。施加在该数据上的操作，即数据的运算。例例如如，有有一一个个学学生生表表如如表表1.1所所示示。这这个个表表中中的的数数据据元元素素是是学学生生记记录录，每每个个数数据据元元素素由由4个个数数据据项项（即即学学号号、姓别、性别和班号）组成。姓别、性别和班号）组成。数据：学生表数据：学生表数据元素：学生记录数据元素：学生记录数据项：数据项：学号、姓别、性别和班号学号、姓别、性别和班号学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘
7、丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901表表1.1学生表学生表 逻辑结构表示逻辑结构表示1 表表中中的的记记录录顺顺序序反反映映了了数数据据元元素素之之间间的的逻逻辑辑关关系系，用用学学号号标识每个学生记录，这种逻辑关系可以表示为：标识每个学生记录，这种逻辑关系可以表示为：，其其中中尖尖括括号号“”表表示示元元素素ai和和ai+1之之间间是是相相邻邻的的，即即ai在在ai+1之前，之前，ai+1在在ai之后。之后。逻辑结构表示逻辑结构表示2数据在计算机存储器中的存储方式就是数据在计算机存储器中的存储方式
8、就是存储结构存储结构。逻辑结构逻辑结构存储结构存储结构映射映射映射信息有两种：映射信息有两种：存储元素存储元素 存储关系存储关系存放学生表的结构体数组存放学生表的结构体数组Stud定义为：定义为：struct int no;/存储学号存储学号 char name8;/存储姓名存储姓名 char sex2;/存储性别存储性别 char class4;/存储班号存储班号 Stud7=1，“张张斌斌”，“男男”，“9901”，5，王萍王萍，女女，9901;C/C+语语言言中中，通通常常采采用用结结构构体体数数组组和和链链表表两两种种方方式式实实现现其其存储结构存储结构。结构体数组结构体数组Stud各
9、元素在内存中顺序存放，即第各元素在内存中顺序存放，即第i(1i6)个学生对应的元素个学生对应的元素Studi存放在第存放在第i+1个学生对应的元素个学生对应的元素Studi+1之前，之前，Studi+1正好在正好在Studi之后。之后。9901女王萍59901男张斌张斌1Stud0Stud6Stud数组起始地址数组起始地址存储结构表示存储结构表示1存放学生表的链表的结点类型存放学生表的链表的结点类型StudType定义为：定义为：typedef struct studnode int no;/存储学号存储学号 char name8;/存储姓名存储姓名 char sex2;/存储性别存储性别 c
10、har class4;/存储班号存储班号 struct studnode*next;/存储指向下一个学生的指针存储指向下一个学生的指针 StudType；链表首结点地址链表首结点地址head1张斌张斌男男 99018刘丽刘丽女女 990234李英李英女女 990120陈华陈华男男 990212王奇王奇男男 990126董强董强男男 99025王萍王萍女女 9901学生表构成的链表如右学生表构成的链表如右图所示。其中的图所示。其中的head为第为第一个数据元素的指针。一个数据元素的指针。学生表构成的链表学生表构成的链表存储结构表示存储结构表示2对于对于“学生表学生表”这种数据结构，可以进行一系列
11、的运算，例如：这种数据结构，可以进行一系列的运算，例如：增加一个学生记录增加一个学生记录删除一个学生记录删除一个学生记录查找性别为查找性别为“女女”的学生记录的学生记录查找班号为查找班号为“9902”的学生记录。的学生记录。运算运算运算运算 例如，查找学号为例如，查找学号为20的学生的姓名：的学生的姓名：对对于于Stud数数组组：从从Stud0开开始始比比较较，Stud0.no不不等等于于20，再再 与与 Stud1.no比比 较较，直直 到到 Stud3.no等等 于于 20，返返 回回Stud3.name。9902男陈华209901男张斌张斌1Stud0Stud3i3运算的实现过程运算的实
12、现过程运算的实现过程运算的实现过程11对于对于head为首结点指针为首结点指针的链表：的链表：从从p=head所指结点开始比所指结点开始比较，较，p-no不等于不等于20，从它的，从它的next得到下一个结点的地址，得到下一个结点的地址，再与下一个结点的再与下一个结点的no域比较，域比较，直到某结点的，直到某结点的no域等于域等于20，返回其，返回其p-name域。域。head1张斌张斌男男 99018刘丽刘丽女女 990234李英李英女女 990120陈华陈华男男 990212王奇王奇男男 990126董强董强男男 99025王萍王萍女女 9901p运算的实现过程运算的实现过程运算的实现过程
13、运算的实现过程22结论：结论：同一逻辑结构可以对应多种存储结构。同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同同样的运算，在不同的存储结构中，其实现过程是不同的。的。思考题：思考题：数据的逻辑结构和存储结构有什么不同？数据的逻辑结构和存储结构有什么不同？为为了了更更确确切切地地描描述述一一种种数数据据结结构构，通通常常采采用用二二元元组组表表示：示：D=(K，R)其中，其中，D是一种数据结构，它由数据元素的集合是一种数据结构，它由数据元素的集合K和和K上二元关系的集合上二元关系的集合R所组成。其中：所组成。其中：K=ki|1in，n0R=rj|1jm，m0
14、逻辑结构的描述或表示：逻辑结构的描述或表示：一种通用的逻辑结构表示方法一种通用的逻辑结构表示方法其中：其中：lki表示集合表示集合K中的第中的第i个结点或数据元素。个结点或数据元素。ln为为K中结点的个数，特别地，若中结点的个数，特别地，若n=0，则，则K是一个空是一个空集，因而集，因而D也就无结构可言，有时也可以认为它具有也就无结构可言，有时也可以认为它具有任一结构。任一结构。lrj表示集合表示集合R中的第中的第j个关系，每个关系用序偶表示。个关系，每个关系用序偶表示。lm为为R中关系的个数，特别地，若中关系的个数，特别地，若m=0，则，则R是一个是一个空集，表明集合空集，表明集合K中的元结
15、点间不存在任何关系，彼中的元结点间不存在任何关系，彼此是独立的。此是独立的。序偶序偶(x，yK)x为第一结点，为第一结点，y为第二结点。为第二结点。x为为y的的直接前驱结点直接前驱结点（通常简称（通常简称前驱结点前驱结点）y为为x的直接后继结点（通常简称的直接后继结点（通常简称后继结点后继结点）若若某某个个结结点点没没有有前前驱驱结结点点，则则称称该该结结点点为为开开始始结结点点；若若某某个个结点没有后继结点，则称该结点为结点没有后继结点，则称该结点为终端结点终端结点。说明：说明：表示有向关系，表示有向关系，(x，y)表示无向关系。表示无向关系。采用离散数学的表示方法。采用离散数学的表示方法。
16、例如，有一个如下表所示的城市表，假设城市名是唯一的，例如，有一个如下表所示的城市表，假设城市名是唯一的，给出其逻辑结构的二元组表示。给出其逻辑结构的二元组表示。城市表城市表City中共有中共有5个记录，其逻辑结构的二元组表示如下：个记录，其逻辑结构的二元组表示如下：City=(K，R)K=Beijing，Shanghai，Wuhan，Xian，NanjingR=r只有一种关系只有一种关系r=，城市名城市名区号区号说明说明Beijing010首都首都Shanghai021直辖市直辖市Wuhan027湖北省省会湖北省省会Xian029陕西省省会陕西省省会Nanjing025江苏省省会江苏省省会又例
17、如，有如下数据即一个矩阵：又例如，有如下数据即一个矩阵：对应的二元组表示为对应的二元组表示为B=(K，R)，其中：，其中：K=2,6,3,1,8,12,7,4,5,10,9,11R=r1,r2其中，其中，r1表示行关系，表示行关系，r2表示列关系表示列关系r1=,，r2=,一个二维数组一个二维数组 可以利用图形形象地表示逻辑结构。可以利用图形形象地表示逻辑结构。例如，上述例如，上述“学生表学生表”数据结构用下图的图形表示。数据结构用下图的图形表示。学生表数据结构图示学生表数据结构图示 （1）线性结构线性结构 3.3.逻辑结构类型逻辑结构类型 l结点之间关系：一对一。结点之间关系：一对一。l特点
18、：开始结点和终端结点都是唯一的，除了开始特点：开始结点和终端结点都是唯一的，除了开始结点和终端结点以外，其余结点都有且仅有一个前结点和终端结点以外，其余结点都有且仅有一个前驱结，有且仅有一个后继结点。驱结，有且仅有一个后继结点。（2）树形结构树形结构 l结点之间关系：一对多。结点之间关系：一对多。l特点：开始结点唯一，终端结点不唯一。除终特点：开始结点唯一，终端结点不唯一。除终端结点以外，每个结点有一个或多个后续结点；端结点以外，每个结点有一个或多个后续结点；除开始结点外，每个结点有且仅有一个前驱结除开始结点外，每个结点有且仅有一个前驱结点。点。（3）图形结构）图形结构 l结点之间关系：多对多
19、。结点之间关系：多对多。l特点：没有开始结点和终端结点，所有结点都特点：没有开始结点和终端结点，所有结点都可能有多个前驱结点和多个后继结点。可能有多个前驱结点和多个后继结点。（2）链式存储方法）链式存储方法（3）索引存储方法）索引存储方法（4）散列（哈希）存储方法散列（哈希）存储方法4.4.存储结构类型存储结构类型（1）顺序存储方法）顺序存储方法前面通过示例已介绍前面通过示例已介绍后面介绍后面介绍（1）数据类型（）数据类型（DT）高级程序语言中，一般须对程序中出现的每个变量、常高级程序语言中，一般须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。不同类型的变量或表达式，明确说
20、明它们所属的数据类型。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。量，其所能取的值的范围不同，所能进行的操作不同。数据类型数据类型是一个值的集合和定义在此集合上的一组操作是一个值的集合和定义在此集合上的一组操作的总称。的总称。数据类型是数据对象和施加在数据对象上操作的聚合体。数据类型是数据对象和施加在数据对象上操作的聚合体。如如C中：中：int是是-3276832767的整数、的整数、+、-、*、/、%5.数据结构和数据类型数据结构和数据类型 （2）抽象数据类型（抽象数据类型（ADT）抽象数据类型抽象数据类型(AbstractDataType简写为简写为ADT)指的是用指的是用
21、户进行软件系统设计时从问题的数学模型中抽象出来的逻辑户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。存储结构和运算的具体实现算法。抽象数据类型抽象数据类型=逻辑结构抽象运算逻辑结构抽象运算 抽象数据类型实质上就是描述一个求解问题本身（与计算抽象数据类型实质上就是描述一个求解问题本身（与计算机无关），计算机人员就是在理解问题基础上实现用计算机机无关），计算机人员就是在理解问题基础上实现用计算机求解问题的过程。求解问题的过程。定义：抽象数据类型（定义：抽象数据类
22、型（ADT）中的数据对象和数据）中的数据对象和数据操作的规范声明与数据对象的表示和数据操作的实现相操作的规范声明与数据对象的表示和数据操作的实现相互分离。互分离。一些程序设计语言提供明显的机制区分规范声明和一些程序设计语言提供明显的机制区分规范声明和实现，如实现，如Ada语言中的语言中的package和和C+语言中的类语言中的类就提供这种支持，可供程序员直接用来定义抽象数据类就提供这种支持，可供程序员直接用来定义抽象数据类型。型。例如，抽象数据类型例如，抽象数据类型复数复数的定义：的定义：ADTComplex数据对象数据对象：D=e1，e2|e1，e2均为实数均为实数数据关系数据关系：R1=|
23、e1是复数的实数部分，是复数的实数部分，e2是复数的是复数的虚数部分虚数部分e1+e2i（e1，e2）基本操作：基本操作：AssignComplex(&Z，v1，v2)：构造复数：构造复数Z。DestroyComplex(&Z):复数复数Z被销毁。被销毁。GetReal(Z，&real):返回复数返回复数Z的实部值。的实部值。GetImag(Z，&Imag):返回复数返回复数Z的虚部值。的虚部值。Add(z1，z2，&sum):返回两个复数返回两个复数z1，z2的和。的和。ADTComplex思考题：思考题：数据类型和抽象数据类型有什么不同？数据类型和抽象数据类型有什么不同？1.什么是算法什么
24、是算法 数据元素之间的关系有逻辑关系和物理关系，对应数据元素之间的关系有逻辑关系和物理关系，对应的操作有的操作有逻辑结构上的操作功能逻辑结构上的操作功能和和具体存储结构上的操作具体存储结构上的操作实现实现。通常把具体存储结构上的操作实现步骤或过程称为算通常把具体存储结构上的操作实现步骤或过程称为算法。法。属属ADT的一部分的一部分算法算法1.2算法及其描述算法及其描述 算法的算法的5个重要的特性个重要的特性（1）有穷性有穷性:在有穷步之后结束。在有穷步之后结束。（2）确定性确定性:无二义性。无二义性。（3）可行性可行性:可通过基本运算有限次执行来实现。可通过基本运算有限次执行来实现。（4）有输
25、入有输入 （5）有输出有输出 表示存在数据处理表示存在数据处理例例考虑下列两段描述：考虑下列两段描述：（1）描述一描述一void exam1()int n2;while(n%20)nn+2;printf(%dn，n);华中科大考研题华中科大考研题（2）描述二描述二void exam2()int x，y;y=0;x=5/y;printf(“%d，%dn”，x，y);这这两两段段描描述述均均不不能能满满足足算算法法的的特特征征，试试问问它它们们违违反反了了哪些特征？哪些特征？解解：(1)算算法法是是一一个个死死循循环环，违违反反了了算算法法的的有有穷穷性性特特征。征。(2)算法包含除零错误，违反了
26、算法的可行性特征算法包含除零错误，违反了算法的可行性特征。思考题：思考题：算法和程序有什么不同？算法和程序有什么不同？2.算法描述算法描述 本书中采用本书中采用C/C+语言描述算法。语言描述算法。（1 1）引用）引用C+语言中提供了一种引用运算符语言中提供了一种引用运算符“&”，引用是个别，引用是个别名，当建立引用时，程序用另一个已定义的变量或对象名，当建立引用时，程序用另一个已定义的变量或对象(目标目标)的名字初始化它，从那时起，引用作为目标的别名的名字初始化它，从那时起，引用作为目标的别名而使用，对引用的改动实际就是对目标的改动。而使用，对引用的改动实际就是对目标的改动。注意：注意：Tur
27、boC不支持引用类型，不支持引用类型，VC+等系统支持引等系统支持引用类型。用类型。例如：例如：int a=4;/a为普通的整型变量为普通的整型变量 int&b=a;/b是是a的引用变量的引用变量这这里里说说明明b变变量量是是变变量量a的的引引用用，b也也等等于于4，之之后后这这两两个个变变量量同同步步改改变变。当当a改改变变时时b也也同同步步改改变变，同同样样，当当b改改变时变时a也同步改变。也同步改变。引引用用常常用用于于函函数数形形参参中中，采采用用引引用用型型形形参参时时，在在函函数调用时将形参的改变回传给实参。数调用时将形参的改变回传给实参。编写一个函数编写一个函数swap1(x，y
28、)，当执行语句，当执行语句swap1(a，b)时，时，交换交换a和和b的值。的值。void swap1(int x,int y)int tmp;tmp=x;x=y;y=tmp;注意：注意：a和和b的值不会发生了交换。的值不会发生了交换。为此，采用指针的方式来回传形参的值，需将上述函数为此，采用指针的方式来回传形参的值，需将上述函数改为：改为：void swap2(int*x,int*y)int tmp;tmp=*x;/将将x的值放在的值放在tmp中中*x=*y;/将将x所指的值改为所指的值改为*y *y=tmp；/将将y所指的值改为所指的值改为tmp 上述函数的调用改为上述函数的调用改为swa
29、p2(&a，&b)，它是通过指针方，它是通过指针方式间接改变实参的值。式间接改变实参的值。采用如下函数采用如下函数(其中的形参均为引用型形参其中的形参均为引用型形参)：voidswap(int&x,int&y)/形参前的形参前的“&”符号不是指针运算符符号不是指针运算符inttmp=x;x=y;y=tmp当用执行语句当用执行语句swap(a，b)时，时，a和和b的值发生了交换。的值发生了交换。（2 2）动态存储分配）动态存储分配程序在运行时需要申请存储空间，用来存放信息。程序在运行时需要申请存储空间，用来存放信息。例如：例如：int*pi;float*pf;pi=(int*)malloc(si
30、eof(int);pf=(float*)malloc(sizeof(float);*pi=1024;*pf=3.14;printf(“*pi=%d，*pf=%fn”，*p1，*pf);free(pi);free(pf);变量空间的自动分配与释放变量空间的自动分配与释放例如：例如：int fun(int x，int y)int z;z=x+y;retur z;x、y、z均为局部变量，当调用函数均为局部变量，当调用函数fun时系统为它们分配空间，当执行时系统为它们分配空间，当执行完毕系统自动释放它们占用的空间。完毕系统自动释放它们占用的空间。变量空间的手工分配与释放变量空间的手工分配与释放例如：例
31、如：void fun1(int n)int*p;p=(int*)malloc(sizeof(int)*n);.free(p);p为局部变量，当调用函数为局部变量，当调用函数fun1时系统自时系统自动为它分配一个地址空间，而所指向的空动为它分配一个地址空间，而所指向的空间是手工（动态）分配的，当不需要时应间是手工（动态）分配的，当不需要时应将将p所指向的空间用所指向的空间用free释放。而释放。而p的空间的空间是由系统自动释放的。是由系统自动释放的。一一个个算算法法是是由由控控制制结结构构（顺顺序序、分分支支和和循循环环三三种种）和和原原操操作作（指指固固有有数数据据类类型型的的操操作作）构构成
32、成的的，则则算算法法时间取决于两者的综合效果。时间取决于两者的综合效果。1.算法时间复杂度分析算法时间复杂度分析 控制语句控制语句1原操作原操作控制语句控制语句n原操作原操作一个算法的构成一个算法的构成1.3算法分析算法分析 同同一一问问题题可可以以采采用用多多种种算算法法实实现现。如如何何比比较较算算法执行效率？不能以绝对时间进行比较：法执行效率？不能以绝对时间进行比较：算法描述的语言不同算法描述的语言不同算法执行的环境不同算法执行的环境不同 其他因素其他因素 为为了了便便于于比比较较同同一一问问题题的的不不同同算算法法，通通常常从从算算法法中中选选取取一一种种对对于于所所研研究究的的问问题
33、题来来说说是是基基本本运运算算的的原原操操作作（以以下下将将基基本运算的原操作简称为本运算的原操作简称为基本运算基本运算或或基本操作基本操作）。）。算算法法执执行行时时间间大大致致为为基基本本运运算算所所需需的的时时间间与与其其运运算算次次数数（也称为频度）的乘积。（也称为频度）的乘积。被视为算法基本运算的一般是最深层循环内的语句。被视为算法基本运算的一般是最深层循环内的语句。在在一一个个算算法法中中，进进行行基基本本运运算算的的次次数数越越少少，其其运运行行时时间间也也就就相相对对地地越越少少；基基本本运运算算次次数数越越多多，其其运运行行时时间间也也就就相相对对地地越越多。多。所所以以，通
34、通常常把把算算法法中中包包含含基基本本运运算算次次数数的的多多少少称称为为算算法法的的时时间间复复杂杂度度，也也就就是是说说，一一个个算算法法的的时时间间复复杂杂度度是是指指该该算算法法的的基本运算的执行次数基本运算的执行次数。算法中基本运算次数算法中基本运算次数T(n)是问题规模是问题规模n的某个函数的某个函数f(n)，记，记作作：T(n)=O(f(n)记记号号“O”读读作作“大大O”，它它表表示示随随问问题题规规模模n的的增增大大算算法法执执行时间的增长率和行时间的增长率和f(n)的增长率相同。的增长率相同。“O”的形式定义为：的形式定义为：若若f(n)是是正正整整数数n的的一一个个函函数
35、数，则则T(n)=O(f(n)表表示示存存在在一一个正的常数个正的常数M，使得当，使得当nn0时都满足：时都满足：|T(n)|M|f(n)|也就是只求出也就是只求出T(n)的最高阶，忽略其低阶项和的最高阶，忽略其低阶项和常系数，这样既可简化常系数，这样既可简化T(n)的计算，又能比较客观的计算，又能比较客观地反映出当地反映出当n很大时算法的时间性能。很大时算法的时间性能。例如，例如，T(n)=3n2-5n+10000=O(n2)本质上讲，是一种最高本质上讲，是一种最高数量级的比较数量级的比较 一个没有循环的算法的基本运算次数与问题规模一个没有循环的算法的基本运算次数与问题规模n无关，记作无关，
36、记作O(1)，也称作，也称作常数阶常数阶。一个只有一重循环的算法的基本运算次数与问题规一个只有一重循环的算法的基本运算次数与问题规模模n的增长呈线性增大关系，记作的增长呈线性增大关系，记作O(n)，也称，也称线性阶线性阶。其余常用的还有平方阶其余常用的还有平方阶O(n2)、立方阶立方阶O(n3)、对数对数阶阶O(log2n)、指数阶指数阶O(2n)等。等。各种不同数量级对应的值存在着如下关系：各种不同数量级对应的值存在着如下关系：O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)NP问题问题思考题：思考题：为什么要进行算法的时间复杂度分析？为什么要进行
37、算法的时间复杂度分析？例例如如，求求两两个个n阶阶方方阵阵的的相相加加C=A+B的的算算法法如如下下，分析其时间复杂度。分析其时间复杂度。#define MAX 20 /定义最大的方阶定义最大的方阶 void matrixadd(int n，int AMAXMAX，int BMAXMAX，int CMAXMAX)int i，j;for(i=0;in;i+)for(j=0;jn;j+)Cij=Aij+Bij;解解：该该算算法法中中的的基基本本运运算算是是两两重重循循环环中中最最深深层层的的语语句句Cij=Aij+Bij，分析它的频度，即：，分析它的频度，即：T(n)=O(n2)例如，析以下算法的
38、时间复杂度。例如，析以下算法的时间复杂度。int fun(int n)int i，j，k，s;s=0;for(i=0;i=n;i+)for(j=0;j=i;j+)for(k=0;k=j;k+)s+;return(s);基本语句或基本操作基本语句或基本操作 解：解：该算法的基本操作是语句该算法的基本操作是语句s+，其频度：，其频度：T(n)=O(n3)则该算法的时间复杂度为则该算法的时间复杂度为O(n3)。例如，分析以下算法的时间复杂度。例如，分析以下算法的时间复杂度。void func(int n)int i=0，s=0;while(sn)i+;s=s+i;基本语句基本语句解：解：对于对于wh
39、ile循环语句，设执行的次数为循环语句，设执行的次数为m，i从从0开始递增开始递增1，直到，直到m为止，有：为止，有：s=0+1+2+(m-1)=m(m-1)/2，并满足并满足s=m(m-1)/2n，则有，则有m。T(n)=O()所以，该算法的时间复杂度为所以，该算法的时间复杂度为O()。例如，例如，有如下算法：有如下算法：void fun(int a，int n，int k)/数组数组a共有共有n个元素个元素 int i;if(k=n-1)for(i=0;in;i+)printf(“%dn”，ai);/执行执行n n次次else for(i=k;in;i+)ai=ai+i*i;/执行执行n-
40、k次次 fun(a，n，k+1);分析调用语句分析调用语句fun(a,n,0)的其时间复杂度。的其时间复杂度。解解：设设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)+2+n=O(n2)所以调用所以调用fun(a,n,0)的时间复杂度为的时间复杂度为O(
41、n2)。数据结构基础：数据结构基础：定义（大定义（大O记号）记号）f(n)=O(g(n)（读作（读作f(n)是是g(n)的大的大O），当且仅当存在正常量），当且仅当存在正常量c和和n0，使当，使当nn0时，时，f(n)cg(n)。如，如，3n+2=O(n)，因为，因为n3时，时，3n+24n100n+6=O(n)1000n2+100n-6=O(n2)，当，当n100时时1000n2+100n-61001n2。10n2+4n+2=O(n4)，因为，因为n2时，时，10n2+4n+210n4。注意：注意：f(n)=O(g(n)仅指出仅指出g(n)是当是当nn0时，时，f(n)所能取得的所能取得的上
42、界值，而并未涉及这个上界有多么好（接近），甚至可以上界值，而并未涉及这个上界有多么好（接近），甚至可以写成写成n=O(n2)，n=O(n3)。定义（大定义（大记号）记号）f(n)=(g(n)（读作（读作f(n)是是g(n)的大的大），当且仅当存在正常量），当且仅当存在正常量c和和n0，使当，使当nn0时，时，f(n)cg(n)。如，如，3n+2=(n)，因为，因为n1时，时，3n+23n100n+6=(n)10n2+4n+2=(n)，10n2+4n+2=(1)，注意：注意：f(n)=O(g(n)仅指出仅指出g(n)是当是当nn0时，时，f(n)所能取得的所能取得的下界值，而并未涉及这个下界有多
43、么好（接近）。下界值，而并未涉及这个下界有多么好（接近）。定义（大定义（大记号）记号）f(n)=(g(n)（读作（读作f(n)是是g(n)的大的大），当且仅当存在正常量），当且仅当存在正常量c1、c2和和n0，使当，使当nn0时，时，c1g(n)f(n)c2g(n)。大大记号比大记号比大O记录和大记录和大记录都精确，记录都精确，f(n)=(g(n)，当，当且仅当且仅当g(n)即是即是f(n)的上界又是的上界又是f(n)的下界。的下界。注意：注意：大大记号等同于国内教材的大记号等同于国内教材的大O记号。记号。空间复杂度空间复杂度是对一个算法在运行过程中临时占用的存储空间是对一个算法在运行过程中临
44、时占用的存储空间大小的量度，一般也作为问题规模大小的量度，一般也作为问题规模n的函数，以数量级形式给出，的函数，以数量级形式给出，记作：记作：S(n)=O(g(n)若若所所需需额额外外空空间间相相对对于于输输入入数数据据量量来来说说是是常常数数，则则称称此此算算法法为为原原地地工工作作。若若所所需需存存储储量量依依赖赖于于特特定定的的输输入入，则则通通常常按按最最坏坏情况考虑。情况考虑。2.2.算法空间复杂度分析算法空间复杂度分析 解：解：由于算法中临时变量的个数与问题规模由于算法中临时变量的个数与问题规模n无关，所无关，所以空间复杂度均为以空间复杂度均为O(1)。（1 1）定长空间分析）定长
45、空间分析即与程序输入输出无关的空间的分析。即与程序输入输出无关的空间的分析。例如，析以下算法的空间复杂度。例如，析以下算法的空间复杂度。int fun(int n)int i，j，k，s;s=0;for(i=0;i=n;i+)for(j=0;j=i;j+)for(k=0;k=j;k+)s+;return(s);（2 2）变长空间分析）变长空间分析递归算法的空间分析。递归算法的空间分析。例如，例如，有如下算法：有如下算法：void fun(int a，int n，int k)/数组数组a共有共有n个元素个元素 int i;if(k=n-1)for(i=0;in;i+)printf(“%dn”，a
46、i);/执行执行n n次次else for(i=k;in;i+)ai=ai+i*i;/执行执行n-k次次 fun(a，n，k+1);分析调用语句分析调用语句fun(a,n,0)的其空间复杂度。的其空间复杂度。解解：设设fun(a,n,0)的的空空间间复复杂杂度度为为S(n)，则则fun(a,n,k)的的占占用空间为用空间为S1(n,k)，由，由fun()算法可知：算法可知：S1(n,k)=1当当k=n-1时时S1(n,k)=1+S1(n,k+1)其他情况其他情况则则S(n)=S1(n,0)=1+S1(n,1)=1+1+S1(n,2)=1+1+1+S1(n,n-1)=n=O(n)所以调用所以调用
47、fun(a,n,0)的空间复杂度为的空间复杂度为O(n)。1.4数据结构算法程序数据结构算法程序 对于一个程序来说，数据是对于一个程序来说，数据是“原料原料”。一个程序所要进行的。一个程序所要进行的计算或处理总是以某些数据为对象的。将松散、无组织的数计算或处理总是以某些数据为对象的。将松散、无组织的数据按某种要求组成一种数据结构，对于设计一个简明、高效、据按某种要求组成一种数据结构，对于设计一个简明、高效、可靠的程序是大有益处的。可靠的程序是大有益处的。沃思指出，程序就是在数据的某些特定的表示方法和结构沃思指出，程序就是在数据的某些特定的表示方法和结构的基础上，对抽象算法的具体表述，所以说程序
48、离不开数据的基础上，对抽象算法的具体表述，所以说程序离不开数据结构。结构。程序是通过某种程序设计语言描述的，程序设计语言有实程序是通过某种程序设计语言描述的，程序设计语言有实现数据结构和算法的机制，类型定义与对象说明是其主要部现数据结构和算法的机制，类型定义与对象说明是其主要部分。程序设计语言中的类型定义与对象说明和语句是其主要分。程序设计语言中的类型定义与对象说明和语句是其主要部分。程序设计语言中的类型定义与对象说明实现数据结构；部分。程序设计语言中的类型定义与对象说明实现数据结构；程序设计语言中语句实现算法，描述了程序的行为。程序设计语言中语句实现算法，描述了程序的行为。1.4.1程序和数
49、据结构程序和数据结构1.4.2算法和程序算法和程序由程序设计语言描述的算法就是计算机程序。由程序设计语言描述的算法就是计算机程序。对一个求解问题而言，算法就是解题的方法，没有算法，对一个求解问题而言，算法就是解题的方法，没有算法，程序就成了无本之末，无源之水，有了算法，将它表示成程程序就成了无本之末，无源之水，有了算法，将它表示成程序是不困难的。算法是程序的核心。序是不困难的。算法是程序的核心。算法在程序设计，也可以说软件开发，甚至可以说在整算法在程序设计，也可以说软件开发，甚至可以说在整个计算机科学中的地位都是极其重要的。个计算机科学中的地位都是极其重要的。1.4.3算法和数据结构算法和数据
50、结构求解的问题可以通过抽象数据类型描述，它由数据的逻求解的问题可以通过抽象数据类型描述，它由数据的逻辑结构和抽象运算两部分组成。一种数据的逻辑结构可以映辑结构和抽象运算两部分组成。一种数据的逻辑结构可以映射成多种存储结构，抽象运算在不同的存储结构上实现可以射成多种存储结构，抽象运算在不同的存储结构上实现可以对应多种算法，在同一种存储结构上实现也可能有多种算法，对应多种算法，在同一种存储结构上实现也可能有多种算法，通过算法的时间复杂度和空间复杂度等分析，可以得到好的通过算法的时间复杂度和空间复杂度等分析，可以得到好的算法，如下图所示。算法，如下图所示。数据存储结构会影响算法的好坏，因此在选择存储