1、数据结构数据结构教材教材:数据结构教程数据结构教程(第第3版版)李春葆等李春葆等 清华大学出版社清华大学出版社 2009 (另配套学习指导和上机指导两书，作为参考）另配套学习指导和上机指导两书，作为参考）参考书参考书:1.1.数据结构（数据结构（C语言版）严蔚敏，吴伟民语言版）严蔚敏，吴伟民 清华大学清华大学出版社出版社 1997 2.数据结构（用面向对象方法与数据结构（用面向对象方法与C+描述）殷人昆等描述）殷人昆等 清华大学出版社清华大学出版社 1999辅导教师：辅导教师：7-8刘闯刘闯 134699674479-11洪伟洪伟15927150797C语言语言 数据结构数据结构 软件工程软件
2、工程掌握基本编掌握基本编程方法程方法掌握数据组掌握数据组织和数据处织和数据处理的方法理的方法掌握大型软掌握大型软件开发方法件开发方法学习识字学习识字学习写作文学习写作文学习写小说学习写小说基本要求课程关系与语文学习过程类比动手能力（上机）前期课程前期课程数据结构数据结构计算机基础计算机基础C语言语言离散数学离散数学后期课程后期课程操作系统操作系统编译原理编译原理数据库原理数据库原理软件工程软件工程承上承上启下启下计算机科学课程体系（偏软）计算机科学课程体系（偏软）学习和讲授方法学习和讲授方法l 演译法演译法先学习先学习/讲授理论知识，用知识解决问题讲授理论知识，用知识解决问题l 归纳法归纳法先
3、解决具体问题，由此归纳出解决问题的理论知先解决具体问题，由此归纳出解决问题的理论知识识只有归纳法才能产生新的知识！只有归纳法才能产生新的知识！编写程序编写程序1编写程序编写程序2编写程序编写程序n.具有编程的基本能力具有编程的基本能力用计算机求解问题的基本思路用计算机求解问题的基本思路学士学士精通程序设计方法精通程序设计方法了解开发环境了解开发环境硕士硕士精通开发环境精通开发环境具体一定的理论创具体一定的理论创新知识新知识博士博士 具有较高的理论具有较高的理论创新知识创新知识讲授课时：讲授课时：72上机课时：上机课时：36评分方式：评分方式：平时：平时：10上机：上机：10，作业：作业：10期
4、末考试：期末考试：70授课安排授课安排第第1章章 绪论绪论 1.2 算法及其描述算法及其描述 1.1 什么是数据结构什么是数据结构1.3 算法分析算法分析 本章小结本章小结1.4 数据结构算法程序数据结构算法程序 1.1.1 数据结构的定义数据结构的定义1.1.2 逻辑结构类型逻辑结构类型 1.1.3 存储结构类型存储结构类型1.1.4 数据结构和数据类型数据结构和数据类型 1.1 1.1 什么是数据结构什么是数据结构数据数据：是所有能被输入到计算机中：是所有能被输入到计算机中,且能被计算机处理的且能被计算机处理的符号的集合。它是计算机操作的对象的总称符号的集合。它是计算机操作的对象的总称,也
5、是计算机也是计算机处理的信息的某种特定的符号表示形式。处理的信息的某种特定的符号表示形式。数据元素数据元素：是数据：是数据(集合集合)中的一个中的一个“个体个体”,是数据的基是数据的基本单位。本单位。数据对象数据对象：是具有相同性质的若干个数据元素的集合。：是具有相同性质的若干个数据元素的集合。1.1.1 数据结构的定义数据结构的定义 例如例如,200402班为一个学生班为一个学生数据对象数据对象,而其中的而其中的“张三张三”是一个数据元素是一个数据元素)。数据结构数据结构：是指：是指数据数据以及数据元素相互之间的以及数据元素相互之间的联系联系。可以看。可以看作是相互之间存在着某种特定关系的数
6、据元素的集合。作是相互之间存在着某种特定关系的数据元素的集合。因此因此,可时把可时把数据结构数据结构看成是带结构的数据元素的集合。看成是带结构的数据元素的集合。数据结构数据结构包括如下几个方面：包括如下几个方面：数据元素之间的逻辑关系数据元素之间的逻辑关系,即数据的即数据的逻辑结构逻辑结构。数据元素及其关系在计算机存储器中的存储方式数据元素及其关系在计算机存储器中的存储方式,即数据即数据的的存储结构存储结构,也称为数据的物理结构。也称为数据的物理结构。施加在该数据上的操作施加在该数据上的操作,即数据的即数据的运算运算。例例1.1 有一个学生表如表有一个学生表如表1.1所示。这个表中的数据元所示
7、。这个表中的数据元素是学生记录素是学生记录,每个数据元素由四个数据项每个数据元素由四个数据项(即学号、姓即学号、姓别、性别和班号别、性别和班号)组成。组成。学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901表表1.1 学生表学生表 逻辑结构表示逻辑结构表示1 该表中的记录顺序反映了数据元素之间的逻辑关系该表中的记录顺序反映了数据元素之间的逻辑关系,用学用学号标识每个学生记录号标识每个学生记录,这种这种逻辑关系逻辑关系可以表示为：可以表示为：,其中尖括号
8、其中尖括号“”表示元素表示元素ai和和ai+1之间是相邻的之间是相邻的,即即ai在在ai+1之前之前,ai+1在在ai之后。之后。逻辑结构表示逻辑结构表示2 数据在计算机存储器中的存储方式就是数据在计算机存储器中的存储方式就是存储结构存储结构。逻辑结构逻辑结构存储结构存储结构映射映射映射应满足两个条件：映射应满足两个条件：存储元素存储元素 存储关系存储关系存放学生表的结构体数组存放学生表的结构体数组Stud定义为：定义为：struct int no;/存储学号存储学号 char name8;/存储姓名存储姓名 char sex2;/存储性别存储性别 char class4;/存储班号存储班号
9、Stud7=1,“张斌张斌”,“男男”,“9901”,5,王萍王萍,女女,9901;C/C+语言中，通常采用结构体数组和链表两种方式实现语言中，通常采用结构体数组和链表两种方式实现其存储结构。其存储结构。结构体数组结构体数组Stud各元素在内存中顺序存放各元素在内存中顺序存放,即第即第i(1i6)个个学生对应的元素学生对应的元素Studi存放在第存放在第i+1个学生对应的元素个学生对应的元素Studi+1之前之前,Studi+1正好在正好在Studi之后。之后。9901女王萍59901男张斌张斌1Stud0Stud6Stud数组起始地址数组起始地址存储结构表示存储结构表示1存放学生表的链表的结
10、点类型存放学生表的链表的结点类型StudType定义为：定义为：typedef struct studnode int no;/存储学号存储学号 char name8;/存储姓名存储姓名 char sex2;/存储性别存储性别 char class4;/存储班号存储班号 struct studnode*next;/存储指向下一个学生的指针存储指向下一个学生的指针 StudType；链表首结点地址链表首结点地址head1张斌张斌男男 99018刘丽刘丽女女 990234李英李英女女 990120陈华陈华男男 990212王奇王奇男男 990126董强董强男男 99025王萍王萍女女 9901 学
11、生表构成的链表如学生表构成的链表如右图所示。其中的右图所示。其中的head为第一个数据元为第一个数据元素的指针。素的指针。学生表构成的链表学生表构成的链表存储结构表示存储结构表示2 对于对于“学生表学生表”这种数据结构这种数据结构,可以进行一系列的运算可以进行一系列的运算,例例如如,增加一个学生记录、删除一个学生记录、查找性别为增加一个学生记录、删除一个学生记录、查找性别为“女女”的学生记录、查找班号为的学生记录、查找班号为“9902”的学生记录等等。的学生记录等等。运算运算 例如例如,查找学号为查找学号为20的学生的姓名的学生的姓名：对于对于Stud数组：从数组：从Stud0开始比较开始比较
12、,Stud0.no不等于不等于20,再再与与Stud1.no比较比较,直到直到Stud3.no等于等于20,返回返回Stud3.name。9902男陈华209901男张斌张斌1Stud0Stud3i3运算的实现过程运算的实现过程1对于对于head为首结点为首结点指针的链表：指针的链表：从从p=head所指结点开所指结点开始比较始比较,p-no不等于不等于20,从它的从它的next得到下一个得到下一个结点的地址结点的地址,再与下一个再与下一个结点的结点的no域比较域比较,直到直到某结点的某结点的no域等于域等于20,返返回其回其p-name域。域。head1张斌张斌男男 99018刘丽刘丽女女
13、990234李英李英女女 990120陈华陈华男男 990212王奇王奇男男 990126董强董强男男 99025王萍王萍女女 9901p运算的实现过程运算的实现过程2结论：结论：同一逻辑结构可以对应多种存储结构。同一逻辑结构可以对应多种存储结构。同样的运算同样的运算,在不同的存储结构中在不同的存储结构中,其实现过程是不同其实现过程是不同的。的。思考题：思考题：数据的逻辑结构和存储结构有什么不同？数据的逻辑结构和存储结构有什么不同？为了更确切地描述一种数据结构为了更确切地描述一种数据结构,通常采用通常采用二元组二元组表示：表示：B=(K,R)其中其中,B是一种数据结构是一种数据结构,它由数据元
14、素的集合它由数据元素的集合K和和K上上二元关系的集合二元关系的集合R所组成。其中：所组成。其中：K=ki|1in,n0 R=rj|1jm,m0 逻辑结构的描述或表示：逻辑结构的描述或表示：一种通用的逻辑结构表示方法一种通用的逻辑结构表示方法其中：其中：u ki表示集合表示集合K中的第中的第i个结点或数据元素。个结点或数据元素。u n为为K中结点的个数中结点的个数,特别地特别地,若若n=0,则则K是一个空集是一个空集,因而因而B也就无结构可言也就无结构可言,有时也可以认为它具有任一结构。有时也可以认为它具有任一结构。u rj表示集合表示集合R中的第中的第j个关系，每个关系用序偶表示。个关系，每个
15、关系用序偶表示。u m为为R中关系的个数中关系的个数,特别地特别地,若若m=0,则则R是一个空集是一个空集,表明表明集合集合K中的元结点间不存在任何关系中的元结点间不存在任何关系,彼此是独立的。彼此是独立的。序偶序偶(x,yK)x为第一结点为第一结点,y为第二结点。为第二结点。x为为y的的直接前驱结点直接前驱结点(通常简称通常简称前驱结点前驱结点)y为为x的的直接后继结点直接后继结点(通常简称通常简称后继结点后继结点)。若某个结点没有前驱结点若某个结点没有前驱结点,则称该结点为则称该结点为开始结点开始结点；若某个；若某个结点没有后继结点结点没有后继结点,则称该结点为则称该结点为终端结点终端结点
16、。说明：说明：表示有向关系，表示有向关系，(x,y)表示无向关系。表示无向关系。采用离散数学的表示方法。采用离散数学的表示方法。例如，有一个如下表所示的城市表，假设城市名是唯一的，例如，有一个如下表所示的城市表，假设城市名是唯一的，给出其逻辑结构的二元组表示。给出其逻辑结构的二元组表示。城市表城市表City中共有中共有5个记录，其逻辑结构的二元组表示如下：个记录，其逻辑结构的二元组表示如下：City=(D,R)D=Beijing,Shanghai,Wuhan,Xian,NanjingR=r只有一种关系只有一种关系r=,城市名城市名区号区号说明说明Beijing010首都首都Shanghai02
17、1直辖市直辖市Wuhan027湖北省省会湖北省省会Xian029陕西省省会陕西省省会Nanjing025江苏省省会江苏省省会又例如又例如,有如下数据即一个矩阵：有如下数据即一个矩阵：119105471281362 对应的二元组表示为对应的二元组表示为B=(K,R),其中：其中：K=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中其中,r1表示行关系表示行关系,r2表示列关系表示列关系 r1=,r2=,一个二维数组一个二维数组 可以可以利用图形形象地表示逻辑结构。利用图形形象地表示逻辑结构。例如，上述例如，上述“学生表学生表”数据结构用下图的图形表示。数据结构用下图的图
18、形表示。k1 k2 k3 k4 k5 k6 k7 学生表数据结构图示学生表数据结构图示 (1)线性结构线性结构 结点之间关系：结点之间关系：一对一。一对一。特点：特点：开始结点和终端结点都是唯一的开始结点和终端结点都是唯一的,除了开始结点和终除了开始结点和终端结点以外端结点以外,其余结点都有且仅有一个前驱结点其余结点都有且仅有一个前驱结点,有且仅有一个有且仅有一个后继结点。顺序表就是典型的线性结构。后继结点。顺序表就是典型的线性结构。1.1.2 逻辑结构类型逻辑结构类型 (2)树形结构树形结构 结点之间关系：结点之间关系：一对多。一对多。特点：特点：开始结点唯一开始结点唯一,终端结点不唯一。除
19、终端结终端结点不唯一。除终端结点以外点以外,每个结点有一个或多个后续结点；除开始结点每个结点有一个或多个后续结点；除开始结点外，每个结点有且仅有一个前驱结点。外，每个结点有且仅有一个前驱结点。(3)图形结构图形结构 结点之间关系：结点之间关系：多对多。多对多。特点：特点：没有开始结点和终端结点，所有结点都可没有开始结点和终端结点，所有结点都可能有多个前驱结点和多个后继结点。能有多个前驱结点和多个后继结点。(2)链式存储方法链式存储方法(3)索引存储方法索引存储方法(4)散列（哈希）存储方法散列（哈希）存储方法 1.1.3 存储结构类型存储结构类型(1)顺序存储方法顺序存储方法 前面通过示例已介
20、绍前面通过示例已介绍第第9章介绍章介绍 (1)数据类型数据类型 高级程序语言中高级程序语言中,一般须对程序中出现的每个变量、常量或一般须对程序中出现的每个变量、常量或表达式表达式,明确说明它们所属的数据类型。不同类型的变量明确说明它们所属的数据类型。不同类型的变量,其所其所能取的值的范围不同能取的值的范围不同,所能进行的操作不同。所能进行的操作不同。数据类型数据类型是一个值的集合和定义在此集合上的一组操作是一个值的集合和定义在此集合上的一组操作的总称。的总称。1.1.4 数据结构和数据类型数据结构和数据类型 如如C/C+中的中的int就是整型数据类型。它是所有整数的集合就是整型数据类型。它是所
21、有整数的集合(在在16位计算机中为位计算机中为3276832767的全体整数的全体整数)和相关的整数和相关的整数运算运算(如、等如、等)。int i=2,j=5,k;k=i+j;.因为因为i、j和和k都属于都属于int，而，而int提供了各种运算，所以可以进行提供了各种运算，所以可以进行相应运算。相应运算。int i=9999999999;i*;(2)抽象数据类型抽象数据类型 抽象数据类型抽象数据类型(Abstract Data Type简写为简写为ADT)指的是用指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据
22、结构上的运算数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存而不考虑计算机的具体存储结构和运算的具体实现算法。储结构和运算的具体实现算法。抽象数据类型抽象数据类型=数据元素集合抽象运算数据元素集合抽象运算 抽象数据类型实质上就是描述一个求解问题本身（与计算抽象数据类型实质上就是描述一个求解问题本身（与计算机无关），计算机人员就是在理解问题基础上实现用计算机机无关），计算机人员就是在理解问题基础上实现用计算机求解问题的过程。求解问题的过程。例如例如,抽象数据类型抽象数据类型复数复数的定义：的定义：ADT Complex 数据对象：数据对象：D=e1,e2|e1,e2均为实数均为实数数据关系
23、：数据关系：R1=|e1是复数的实数部分是复数的实数部分,e2 是复数的是复数的 虚数部分虚数部分 e1e2i（e1，e2）基本操作：基本操作：AssignComplex(&Z,v1,v2)：构造复数：构造复数Z。DestroyComplex(&Z):复数复数Z被销毁。被销毁。GetReal(Z,&real):返回复数返回复数Z的实部值。的实部值。GetImag(Z,&Imag):返回复数返回复数Z的虚部值。的虚部值。Add(z1,z2,&sum):返回两个复数返回两个复数z1,z2的和。的和。ADT Complex思考题：思考题：数据类型和抽象数据类型有什么不同？数据类型和抽象数据类型有什么
24、不同？1.2 算法及其描述算法及其描述 1.2.1 什么是算法什么是算法 1.2.2 算法描述算法描述1.2.1 什么是算法什么是算法 数据元素之间的关系有逻辑关系和物理关系数据元素之间的关系有逻辑关系和物理关系,对应的对应的操作有操作有逻辑结构上的操作功能逻辑结构上的操作功能和和具体存储结构上的操作实具体存储结构上的操作实现现。通常把具体存储结构上的操作通常把具体存储结构上的操作实现实现步骤或过程称为步骤或过程称为算算法法。属属ADT的一部分的一部分算法算法算法的五个重要的特性算法的五个重要的特性(1)有穷性有穷性:在有穷步之后结束。在有穷步之后结束。(2)确定性确定性:无二义性。无二义性。
25、(3)可行性可行性:可通过基本运算有限次执行来实现。可通过基本运算有限次执行来实现。(4)有输入有输入 (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)算法是一个死
26、循环算法是一个死循环,违反了算法的有穷性特征。违反了算法的有穷性特征。(2)算法包含除零错误算法包含除零错误,违反了算法的可行性特征违反了算法的可行性特征。思考题：思考题：算法和程序有什么不同？算法和程序有什么不同？1.2.2 算法描述算法描述 本书中采用本书中采用C/C+语言描述算法。语言描述算法。说明：说明：C+语言中提供了一种语言中提供了一种引用引用运算符运算符“&”,引用引用是个别名是个别名,当建立引用时当建立引用时,程序用另一个已定义的变量或对程序用另一个已定义的变量或对象象(目标目标)的名字初始化它的名字初始化它,从那时起从那时起,引用作为目标的别名引用作为目标的别名而使用而使用,
27、对引用的改动实际就是对目标的改动。对引用的改动实际就是对目标的改动。注意：注意：Turbo C不支持引用类型，不支持引用类型，VC+支持引用类型。支持引用类型。编写一个函数编写一个函数swap1(x,y)，当执行语句，当执行语句swap1(a,b)时时,交换交换a和和b的值。的值。void swap1(int x,int y)int tmp;tmp=x;x=y;y=tmp;注意：注意：a a和和b b的值不会发生了交换。的值不会发生了交换。为此，采用指针的方式来回传形参的值，需将上述函数为此，采用指针的方式来回传形参的值，需将上述函数改为：改为：void swap2(int*x,int*y)i
28、nt tmp;tmp=*x;/将将x的值放在的值放在tmp中中*x=*y;/将将x所指的值改为所指的值改为*y *y=tmp；/将将y所指的值改为所指的值改为tmp 上述函数的调用改为上述函数的调用改为swap2(&a,&b)，显然远不如采用引，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。用方式简洁。所以本书后面很多算法都采用引用形参。引入引入“引用引用”的概念的概念例如：例如：int a=4;/a为普通的整型变量为普通的整型变量 int&b=a;/b是是a的引用变量的引用变量 这里说明这里说明b变量是变量变量是变量a的引用的引用,b也等于也等于4,之后这两个之后这两个变量
29、同步改变。当变量同步改变。当a改变时改变时b也同步改变，同样，当也同步改变，同样，当b改变改变时时a也同步改变。也同步改变。难点难点void main()int a=2;int&b=a;printf(a=%d,b=%dn,a,b);/输出：输出：a=2,b=2 b+;printf(a=%d,b=%dn,a,b);/输出：输出：a=3,b=3 a+;printf(a=%d,b=%dn,a,b);/输出：输出：a=4,b=4 引用引用常用于函数形参中常用于函数形参中,采用引用型形参时采用引用型形参时,在函数调用时将在函数调用时将形参的改变回传给实参形参的改变回传给实参,例如例如,有如下函数有如下函
30、数(其中的形参均为引用其中的形参均为引用型形参型形参)：void swap(int&x,int&y)/形参前的形参前的“&”符号不是指针运算符符号不是指针运算符 int tmp=x;x=y;y=tmp 当用执行语句当用执行语句swap(a,b)时时,a和和b的值发生了交换。的值发生了交换。例例1.3 编写一个算法编写一个算法,读入三个整数读入三个整数x,y和和z的值的值,要求从大到小要求从大到小输出这三个数。输出这三个数。解：依次输入解：依次输入x,y和和z这三个整数这三个整数,通过比较交换后通过比较交换后,使得使得xyz,然后输出然后输出x,y,z。在算法中应考虑对这三个元素作尽可能少的比较
31、和移动在算法中应考虑对这三个元素作尽可能少的比较和移动,如如下述算法在最坏的情况下只需进行下述算法在最坏的情况下只需进行3次比较和次比较和7次移动。次移动。用用C/C+描述算法示例描述算法示例void Descending()printf(输入输入x,y,z);scanf(%d,%d,%d,&x,&y,&z);if(x=y if(yz if(x=temp)y=temp；else y=x;x=temp;printf(%d,%d,%dn,x,y,z);1.3 算法分析算法分析 1.3.1 算法时间复杂度分析算法时间复杂度分析 1.3.2 算法空间复杂度分析算法空间复杂度分析 一个算法是由控制结构一
32、个算法是由控制结构(顺序、分支和循环三种顺序、分支和循环三种)和和原操作原操作(指固有数据类型的操作指固有数据类型的操作)构成的构成的,则算法时间取则算法时间取决于两者的综合效果。决于两者的综合效果。1.3.1 算法时间复杂度分析算法时间复杂度分析 控制语句控制语句1原操作原操作控制语句控制语句n原操作原操作一个算法的构成一个算法的构成 同一问题可以采用多种算法实现。如何比较算同一问题可以采用多种算法实现。如何比较算法执行效率？法执行效率？算法描述的语言不同算法描述的语言不同 算法执行的环境不同算法执行的环境不同 其他因素其他因素 所以不能用绝对执行时间进行比较所以不能用绝对执行时间进行比较
33、为了便于比较同一问题的不同算法为了便于比较同一问题的不同算法,通常从算法中选通常从算法中选取一种对于所研究的问题来说是基本运算的原操作取一种对于所研究的问题来说是基本运算的原操作(以下以下将基本运算的原操作简称为将基本运算的原操作简称为基本运算基本运算)。算法执行时间大致为基本运算所需的时间与其运算次算法执行时间大致为基本运算所需的时间与其运算次数数(也称为频度也称为频度)的乘积。的乘积。被视为算法被视为算法基本运算基本运算的一般是最深层循环内的语句。的一般是最深层循环内的语句。在一个算法中在一个算法中,进行基本运算的次数越少进行基本运算的次数越少,其运行时间也就其运行时间也就相对地越少；基本
34、运算次数越多相对地越少；基本运算次数越多,其运行时间也就相对地越多。其运行时间也就相对地越多。所以所以,通常把算法中包含基本运算次数的多少称为算法的通常把算法中包含基本运算次数的多少称为算法的时间复杂度时间复杂度,也就是说也就是说,一个算法的时间复杂度是指该算法的基一个算法的时间复杂度是指该算法的基本运算次数本运算次数。算法中算法中基本运算次数基本运算次数T(n)是问题规模是问题规模n的某个函数的某个函数f(n),记作记作：T(n)=O(f(n)记号记号“O”读作读作“大大O”,它表示随问题规模它表示随问题规模n的增大算法执的增大算法执行时间的增长率和行时间的增长率和f(n)的增长率相同。的增
35、长率相同。“O”的形式定义为：的形式定义为：若若f(n)是正整数是正整数n的一个函数的一个函数,则则T(n)=O(f(n)表示存在一个表示存在一个正的常数正的常数M,使得当使得当nn0时都满足：时都满足：|T(n)|M|f(n)|也就是只求出也就是只求出T(n)的的最高阶最高阶,忽略其低阶项和常忽略其低阶项和常系数系数,这样既可简化这样既可简化T(n)的计算的计算,又能比较客观地反又能比较客观地反映出当映出当n很大时算法的时间性能。很大时算法的时间性能。例如例如,T(n)=3n2-5n+10000=O(n2)本质上讲，是一种本质上讲，是一种最高数量级的比较最高数量级的比较 一个没有循环的算法的
36、基本运算次数与问题规模一个没有循环的算法的基本运算次数与问题规模n无关无关,记作记作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
37、!)思考题：思考题：为什么要进行算法的时间复杂度分析？为什么要进行算法的时间复杂度分析？例例1.4 求两个求两个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;该 算 法 中 的 基 本 运 算 是 两 重 循 环 中 最 深 层 的 语 句该 算 法 中 的 基 本 运 算 是
38、两 重 循 环 中 最 深 层 的 语 句Cij=Aij+Bij,分析它的频度分析它的频度,即：即：T(n)=O(n2)102101010*11ninininjnnnnn例例1.5 分析以下算法的时间复杂度。分析以下算法的时间复杂度。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)。n
39、iijjk0001例例1.6 分析以下算法的时间复杂度。分析以下算法的时间复杂度。void func(int n)int i=0,s=0;while(sn)i+;s=s+i;基本语句基本语句 解：对于解：对于while循环语句，设执行的次数为循环语句，设执行的次数为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()。nnn 例例1.7 有如下算法：有如下算法：void fun(int a,int n,int k
40、)/数组数组a共有共有n个元素个元素 int i;if(k=n-1)for(i=0;in;i+)/n次次 printf(%dn,ai);else for(i=k;in;i+)/n-k次次ai=ai+i*i;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)其他情况其他情况
41、 则则 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(n2)。空间复杂度空间复杂度是对一个算法在运行过程中是对一个算法在运行过程中临时占用的存储空间临时占用的存储空间大小的量度大小的量度,一般也作为问题规模一般也作为问题规模n的函数的函数,以数量级形式给出以数量级形式给出,记记作：作：S(n)=O(g(n)若所需若所需额外空间额外空间相对于输入数据量来说是常数相对于输入数据量来说是常数,则称此算法为则称此算法为原地工作。若
42、所需存储量依赖于特定的输入原地工作。若所需存储量依赖于特定的输入,则通常按最坏情况则通常按最坏情况考虑。考虑。1.3.2 1.3.2 算法空间复杂度分析算法空间复杂度分析 例例1.8 分析例分析例1.4和例和例1.5的空间复杂度。的空间复杂度。解：由于这两个算法中临时变量的个数与问题规模解：由于这两个算法中临时变量的个数与问题规模n无关无关,所以空间复杂度均为所以空间复杂度均为O(1)。1.4 数据结构算法程序数据结构算法程序 数据结构对算法的影响主要在两方面数据结构对算法的影响主要在两方面 数据结构的存储能力数据结构的存储能力数据结构存储能力强、存储信息多算法将会较好设数据结构存储能力强、存
43、储信息多算法将会较好设计（时间少），存储空间大。计（时间少），存储空间大。时间和空间的平衡时间和空间的平衡 定义在数据结构上的操作定义在数据结构上的操作在数据结构上定义基本操作算法调用这些基本操作。在数据结构上定义基本操作算法调用这些基本操作。基本操作越完整，基本操作越完整，算法设计就越容算法设计就越容易易算法算法基本操作基本操作基本算法基本算法应用程序应用程序应用程序是通过应用程序是通过调用基本算法实调用基本算法实现的现的选择数据结构需要考虑的几个方面：选择数据结构需要考虑的几个方面：数据结构要适应问题的状态描述。数据结构要适应问题的状态描述。数据结构应与所选择的算法相适应。数据结构应与所选
44、择的算法相适应。数据结构的选择同时要兼顾程序设计的方便。数据结构的选择同时要兼顾程序设计的方便。灵活应用已有知识。灵活应用已有知识。问题描述：问题描述：有若干学生数据（学生数小于有若干学生数据（学生数小于50），），每个学生数据包含学号（每个学生学号是唯一的，每个学生数据包含学号（每个学生学号是唯一的，但学生记录不一定按学号顺序存放）、姓名、班但学生记录不一定按学号顺序存放）、姓名、班号和若干门课程成绩（每个学生所选课程数目可号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超过能不等，但最多不超过6门）。门）。要求：要求：设计一个程序输出每个学生的学号、姓名设计一个程序输出每个学生的
45、学号、姓名和平均分以及每门课程（课程编号从和平均分以及每门课程（课程编号从16）的平）的平均分。均分。设计方案设计方案1：将学生的全部数据项放在一个表中，一将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于课程最多可选个学生的全部数据对应一条记录。由于课程最多可选6门，门，对应的成绩项也应有对应的成绩项也应有6个。对应的数据结构如下：个。对应的数据结构如下：struct studint no;/学号学号char name10;/姓名姓名int bno;/班号班号int deg1;/课程课程1分数分数int deg2;/课程课程2分数分数int deg3;/课程课程3分数分数i
46、nt deg4;/课程课程4分数分数int deg5;/课程课程5分数分数int deg6;/课程课程6分数分数;nonamebnodeg1deg2deg3deg4deg5deg61张斌张斌99017882639285838刘丽刘丽9902659572788079特点：特点：存储空间：中（若学生没有选该课程，对应空间仍存在）存储空间：中（若学生没有选该课程，对应空间仍存在）算法时间：少算法时间：少 算法简洁性差：算法完全依赖数据结构算法简洁性差：算法完全依赖数据结构存储结构存储结构1 设计方案设计方案2：将学生的全部数据项放在一个表中，但一：将学生的全部数据项放在一个表中，但一个学生的一门课程
47、成绩对应一条记录。这样成绩项只需要个学生的一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，需增加一个课程编号项。一个，为了区分不同课程成绩，需增加一个课程编号项。对应的数据结构如下：对应的数据结构如下：struct studint no;/学号学号char name10;/姓名姓名int bno;/班号班号int cno;/课程编号课程编号int deg;/课程分数课程分数;nonamebnocnodeg1张斌张斌99011781张斌张斌99012821张斌张斌99013631张斌张斌99014921张斌张斌99015851张斌张斌99016838刘丽刘丽99021658
48、刘丽刘丽99022958刘丽刘丽99023728刘丽刘丽99024788刘丽刘丽99025808刘丽刘丽9902679存储结构存储结构2特点：特点：存储空间：大存储空间：大 算法时间：多算法时间：多 算法简洁性：好算法简洁性：好 设计方案设计方案3：将学生的学号、姓名和班号放在一个表中，将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者通过学号关联。前者一将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应一条记录。个学生对应一个记录，后者一门课程成绩对应一条记录。对应的数据结构如下：对应的数据结构如下：struct stud1int n
49、o;/学号学号char name10;/姓名姓名int bno;/班号班号;struct stud2int no;/学号学号int cno;/课程编号课程编号int deg;/分数分数;nonamebno1张斌张斌99018刘丽刘丽9902nocnodeg117812821363149215851683816582958372847885808679关联关联存储结构存储结构3特点：特点：存储空间：少。存储空间：少。算法时间：中。算法时间：中。算法简洁性：好。算法简洁性：好。最佳方案最佳方案数据结构数据结构算法算法数据类型数据类型ijk求解问题编写程序的代码：求解问题编写程序的代码：ijk种种优
50、优选选最佳方案最佳方案本课程的目标本课程的目标:确定求解问题的最佳方案确定求解问题的最佳方案思考题：思考题：学习第学习第1章有什么体会？章有什么体会？本章小结本章小结 本章介绍了数据结构的基本概念本章介绍了数据结构的基本概念,主要学习要点如下：主要学习要点如下：(1)数据结构的定义数据结构的定义,数据结构包含的逻辑结构、存储结构数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。和运算三方面的相互关系。(2)各种逻辑结构即线性结构、树形结构和图形结构之间各种逻辑结构即线性结构、树形结构和图形结构之间的差别。的差别。(3)数据结构和数据类型的差别和联系。数据结构和数据类型的差别和联系。(4)
