数据结构：第1章 绪论

1、第第1章章 绪论绪论 1.2 算法及其描述算法及其描述 1.1 什么是数据结构什么是数据结构1.3 算法分析算法分析 本章小结本章小结1.4 数据结构算法程序数据结构算法程序 1.1.1 1.1.1 数据结构的定义数据结构的定义1.1.2 1.1.2 逻辑结构类型逻辑结构类型 1.1.3 1.1.3 存储结构类型存储结构类型1.1.4 1.1.4 数据结构和数据类型数据结构和数据类型 1.1 1.1 什么是数据结构什么是数据结构 数据数据：是所有能被输入到计算机中是所有能被输入到计算机中, ,且能被计算且能被计算机处理的符号的集合。它是计算机操作的对象的总机处理的符号的集合。它是计算机操作的对

2、象的总称称, ,也是计算机处理的信息的某种特定的符号表示也是计算机处理的信息的某种特定的符号表示形式。形式。 数据元素数据元素：是数据：是数据(集合集合)中的一个中的一个“个体个体”,是数是数据的基本单位。据的基本单位。 1.1.1 1.1.1 数据结构的定义数据结构的定义 数据项数据项：是具有独立含义的数据最小单位，也称：是具有独立含义的数据最小单位，也称字段或域。字段或域。 例如例如,某班中每个学生数据记录都是一个数据元某班中每个学生数据记录都是一个数据元素素, 而其中的而其中的“张三张三”是一个数据项是一个数据项)。 数据结构：是指数据结构：是指数据数据以及数据元素相互之间的以及数据元素

3、相互之间的联系联系。可以看作是相互之间存在着某种特定关系的数据元素可以看作是相互之间存在着某种特定关系的数据元素的集合。的集合。 因此因此,可时把数据结构看成是带结构的数据元素的可时把数据结构看成是带结构的数据元素的集合。集合。 数据结构包括如下几个方面：数据结构包括如下几个方面： (1) 数据元素之间的逻辑关系数据元素之间的逻辑关系,即数据的逻辑结构。即数据的逻辑结构。 (2) 数据元素及其关系在计算机存储器中的存储数据元素及其关系在计算机存储器中的存储方式方式,即数据的存储结构即数据的存储结构,也称为数据的物理结构。也称为数据的物理结构。 (3) 施加在该数据上的操作施加在该数据上的操作,

4、即数据的运算即数据的运算。 例例1.1 有一个学生表如表有一个学生表如表1.1所示。这个表中所示。这个表中的数据元素是学生记录的数据元素是学生记录,每个数据元素由四个数每个数据元素由四个数据项据项(即学号、姓别、性别和班号即学号、姓别、性别和班号)组成。组成。学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901表表1.1 学生表学生表 该表中的记录顺序反映了数据元素之间的逻辑关系该表中的记录顺序反映了数据元素之间的逻辑关系, , 用学号标识每个学生记录用

5、学号标识每个学生记录, ,这种逻辑关系可以表示为：这种逻辑关系可以表示为： , 其中尖括号其中尖括号“”表示元素表示元素ai和和ai+1之间是相邻之间是相邻的的,即即ai在在ai+1之前之前,ai+1在在ai之后。之后。 数据数据在计算机存储器中的存储方式就是在计算机存储器中的存储方式就是存储存储结构结构。 C/C+语言中，通常采用结构体数组和链表两语言中，通常采用结构体数组和链表两种方式实现其存储结构。种方式实现其存储结构。存放学生表的结构体数组存放学生表的结构体数组Stud定义为：定义为： struct int no; /*存储学号存储学号*/ char name8; /*存储姓名存储姓名

6、*/ char sex2; /*存储性别存储性别*/ char class4; /*存储班号存储班号*/ Stud7=1,“张斌张斌”,“男男”,“9901”, 5,王萍王萍,女女,9901; 结构体数组结构体数组Stud各元素在内存中顺序存放各元素在内存中顺序存放,即即第第i(1i6)个学生对应的元素个学生对应的元素Studi存放在第存放在第i+1个学生对应的元素个学生对应的元素Studi+1之前之前,Studi+1正好正好在在Studi之后。之后。9901女王萍59901男张斌张斌1Stud0Stud6Stud数组起始地址数组起始地址 存放学生表的链表的结点类型存放学生表的链表的结点类型S

7、tudType定义为：定义为： typedef struct studnode int no; /*存储学号存储学号*/ char name8; /*存储姓名存储姓名*/ char sex2; /*存储性别存储性别*/ char class4; /*存储班号存储班号*/ struct studnode *next; /*存储指向下一个学生的指针存储指向下一个学生的指针*/ StudType；链表首结点地址链表首结点地址headhead1张斌张斌男男 99018刘丽刘丽女女 990234李英李英女女 990120陈华陈华男男 990212王奇王奇男男 990126董强董强男男 99025王萍王萍

8、女女 9901 学生表构成的链学生表构成的链表如右图所示。其表如右图所示。其中的中的head为第一个为第一个数据元素的指针。数据元素的指针。 学生表构成的链表学生表构成的链表 对于对于“学生表学生表”这种数据结构这种数据结构, ,可以进行一系列可以进行一系列的运算的运算, ,例如例如, ,增加一个学生记录、删除一个学生记增加一个学生记录、删除一个学生记录、查找性别为录、查找性别为“女女”的学生记录、查找班号为的学生记录、查找班号为“99029902”的学生记录等等。的学生记录等等。 从前面介绍的两种存储结构看到从前面介绍的两种存储结构看到, ,同样的运算同样的运算, ,在不同的存储结构中在不同

9、的存储结构中, ,其实现过程是不同的。其实现过程是不同的。 例如例如,查找学号为查找学号为20的学生的姓名的学生的姓名： 对于对于Stud数组数组,可以从可以从Stud0开始比较开始比较,Stud0.no不等于不等于20,再与再与Stud1.no比较比较,直到直到Stud3.no等于等于20,返回返回S。 对于对于head为首结点指针的链表为首结点指针的链表,从从head所指结点开所指结点开始比较始比较,head-no不等于不等于20,从它的从它的next得到下一个结点得到下一个结点的地址的地址,再与下一个结点的再与下一个结点的no域比较域比较,直到某结点的直到某结点的no域

10、等于域等于20,返回其返回其name域域。 为了更确切地描述一种数据结构为了更确切地描述一种数据结构,通常采用二通常采用二元组表示：元组表示： B=(D,R) 其中其中,B是一种数据结构是一种数据结构,它由数据元素的集合它由数据元素的集合D和和D上二元关系的集合上二元关系的集合R所组成。其中：所组成。其中： D=di| 1in,n0 R=rj| 1jm,m0 逻辑结构的描述或表示：逻辑结构的描述或表示： 其中：其中： di表示集合表示集合D中的第中的第i个结点或数据元素。个结点或数据元素。 n为为D中结点的个数中结点的个数,特别地特别地,若若n=0,则则D是一个空是一个空集集,因而因而B也就无

11、结构可言也就无结构可言,有时也可以认为它具有任有时也可以认为它具有任一结构。一结构。 rj表示集合表示集合R中的第中的第j个二元关系个二元关系(后面均简称关后面均简称关系系)。 m为为R中关系的个数中关系的个数,特别地特别地,若若m=0,则则R是一个空是一个空集集,表明集合表明集合D中的元结点间不存在任何关系中的元结点间不存在任何关系,彼此是彼此是独立的。独立的。 序偶序偶(x,yD) x为第一结点为第一结点,y为第二结点。为第二结点。 x为为y的的直接前驱结点直接前驱结点(通常简称通常简称前驱结点前驱结点) y为为x的的直接后继结点直接后继结点(通常简称通常简称后继结点后继结点)。 若某个结

12、点没有前驱结点若某个结点没有前驱结点,则称该结点为则称该结点为开始结点开始结点；若某个结点没有后继结点若某个结点没有后继结点,则称该结点为则称该结点为终端结点终端结点。 说明：说明：表示有向关系，表示有向关系，(x,y)表示无向表示无向关系。采用离散数学的表示方法。关系。采用离散数学的表示方法。 例如例如,采用二元组表示例采用二元组表示例1.1的学生表。的学生表。 学生表中共有学生表中共有7个结点个结点,依次用依次用d1d7表示表示,则对应则对应的二元组表示为的二元组表示为B=(D,R),其中：其中： D=d1,d2,d3,d4,d5,d6,d7 R=r /只有一种关系只有一种关系 r=,又例

13、如又例如, ,有如下数据即一个矩阵：有如下数据即一个矩阵： 119105471281362 对应的二元组表示为对应的二元组表示为B=(D,R),其中：其中： D=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中其中,r1表示行关系表示行关系,r2表示列关系表示列关系 r1=, , r2=, , 一个二维数组一个二维数组 可以可以利用图形形象地表示逻辑结构。利用图形形象地表示逻辑结构。 例如，上述例如，上述“学生表学生表”数据结构用下图的图形数据结构用下图的图形表示。表示。 k1 k2 k3 k4 k5 k6 k7 学生表数据结构图示学生表数据结构图示 (1) 线性结构

14、线性结构 结点之间关系：结点之间关系：一对一。一对一。 特点：特点：开始结点和终端结点都是惟一的开始结点和终端结点都是惟一的, ,除了开始除了开始结点和终端结点以外结点和终端结点以外, ,其余结点都有且仅有一个前驱结其余结点都有且仅有一个前驱结点点, ,有且仅有一个后继结点。顺序表就是典型的线性结有且仅有一个后继结点。顺序表就是典型的线性结构。构。1.1.2 1.1.2 逻辑结构类型逻辑结构类型 (2) 树形结构树形结构 结点之间关系：结点之间关系：一对多。一对多。 特点：特点：开始结点惟一开始结点惟一, ,终端结点不惟一。除终端结点不惟一。除终端结点以外终端结点以外, ,每个结点有一个或多个

15、后续结每个结点有一个或多个后续结点；除开始结点外，每个结点有且仅有一个前点；除开始结点外，每个结点有且仅有一个前驱结点。驱结点。例例 人机对奕问题树结构树结构.将每个棋局都抽象成一个结点：将每个棋局都抽象成一个结点：棋局棋局1棋局棋局2棋局棋局3棋局棋局4棋局棋局5棋局棋局6棋局棋局7棋局棋局8棋局棋局9棋局棋局10整体：是一个数据结构，叫整体：是一个数据结构，叫“树结构树结构”运算：遍历整棵树，找出运算：遍历整棵树，找出“赢赢”的路线；等的路线；等 (3) 图形结构图形结构 结点之间关系：结点之间关系：多对多。多对多。 特点：特点：没有开始结点和终端结点，所有结没有开始结点和终端结点，所有结

16、点都可能有多个前驱结点和多个后继结点。点都可能有多个前驱结点和多个后继结点。 例：例：田径赛的时间安排问题田径赛的时间安排问题: : 设有设有六个六个比赛比赛项目项目，规定每个选，规定每个选手手至多至多可参加可参加三个项目三个项目，有，有五人五人报名报名参加参加比赛比赛（如下表所示）设计比赛日（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成程表，使得在尽可能短的时间内完成比赛。比赛。姓 名 项目 1 项目 2 项目 3 丁 一 跳高 跳 远 100 米 马 二 标 枪 铅 球 张 三 标 抢 100 米 200 米 李 四 铅 球 200 米 跳 高 王 五 跳 远 200 米 姓名姓

17、名项目项目1项目项目2项目项目3丁一丁一 A B E马二马二 C D 张三张三 C E F李四李四 D F A王五王五 B FAEBFDC比赛比赛时间时间比赛项目比赛项目1A，C2B，D3E4F1.1.设代号代表不同的项目设代号代表不同的项目 跳高跳高 跳远跳远 标枪标枪 A B C 铅球铅球 100米米 200米米 D E F2.2.用顶点代表比赛项目用顶点代表比赛项目: : 不能同时进行比赛的项目不能同时进行比赛的项目之间连上一条边。之间连上一条边。 安排安排四个单四个单位时间位时间进行比进行比赛赛AEBFDC(2) 链式存储方法链式存储方法 (3) 索引存储方法索引存储方法 (4) 散列

18、存储方法散列存储方法 1.1.3 1.1.3 存储结构类型存储结构类型(1) 顺序存储方法顺序存储方法 细节省略 (1) 数据类型数据类型 高级程序语言中高级程序语言中,一般须对程序中出现的每个变量、一般须对程序中出现的每个变量、常量或表达式常量或表达式,明确说明它们所属的数据类型。不同明确说明它们所属的数据类型。不同类型的变量类型的变量,其所能取的值的范围不同其所能取的值的范围不同,所能进行的操所能进行的操作不同。作不同。 数据类型数据类型是一个值的集合和定义在此集合上的是一个值的集合和定义在此集合上的一组操作的总称。一组操作的总称。1.1.4 1.1.4 数据结构和数据类型数据结构和数据类

19、型 如如C/C+中的中的int就是整型数据类型。它是所有整就是整型数据类型。它是所有整数的集合数的集合(在在16位计算机中为位计算机中为3276832767的全体整的全体整数数)和相关的整数运算和相关的整数运算(如、等如、等)。C/C+其它数据类型省略 (2) 抽象数据类型抽象数据类型 抽象数据类型抽象数据类型(Abstract Data Type简写为简写为ADT)指的是用户进行软件系统设计时从问题的数学模型指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运中抽象出来的逻辑数据结构和逻辑数据结构上的运算算,而不考虑计算机的具体存储结构和运算的具体实而不考

20、虑计算机的具体存储结构和运算的具体实现算法。现算法。 抽象数据类型抽象数据类型=数据元素集合抽象运算数据元素集合抽象运算例如例如,抽象数据类型抽象数据类型复数复数的定义：的定义：ADT Complex 数据对象：数据对象： D=e1,e2|e1,e2均为实数均为实数数据关系：数据关系： R1=| e1是复数的实数部分是复数的实数部分,e2 是复数的是复数的 虚数部分虚数部分 e1e2i基本操作：基本操作： AssignComplex(&Z,v1,v2)：构造复数：构造复数Z。 DestroyComplex(&Z):复数复数Z被销毁。被销毁。 GetReal(Z,&rea

21、l):返回复数返回复数Z的实部值。的实部值。 GetImag(Z,&Imag):返回复数返回复数Z的虚部值。的虚部值。 Add(z1,z2,&sum):返回两个复数返回两个复数z1,z2的和。的和。 ADT Complex1.2 1.2 算法及其描述算法及其描述 1.2.1 什么是算法什么是算法 1.2.2 算法描述算法描述1.2.1 1.2.1 什么是算法什么是算法 数据元素之间的关系有逻辑关系和物理关系数据元素之间的关系有逻辑关系和物理关系,对应的操作对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。有逻辑结构上的操作功能和具体存储结构上的操作实现。 通常把具体存

22、储结构上的操作实现步骤或过程称为通常把具体存储结构上的操作实现步骤或过程称为算法算法。广义地说，广义地说，算法是对特定问题求解步骤的一种描述，它是指算法是对特定问题求解步骤的一种描述，它是指令的有限序列令的有限序列，其中每个指令表示计算机的一个或多个操作，其中每个指令表示计算机的一个或多个操作。算法的五个重要的特性算法的五个重要的特性 (1) 有穷性有穷性:在有穷步之后结束。在有穷步之后结束。(2) 确定性确定性:无二义性。无二义性。 (3) 可行性可行性:可通过基本运算有限次执行来实现。可通过基本运算有限次执行来实现。(4) 有输入有输入 (5) 有输出有输出 例例1.2 考虑下列两段描述：

23、考虑下列两段描述：(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)算法是一个死循环算法是一个死循环,违反了算法的有穷违反了算法的有穷性特征。性特征。 (2)算法包含除零错误算法包含除零错误,违反了算法的可行性特征。违反了算法的可行性特征。 1.2.2 1.2

24、.2 算法描述算法描述 本书中采用本书中采用C/C+C/C+语言描述算法。语言描述算法。 说明：说明：C+语言中提供了一种语言中提供了一种引用引用运算符运算符“&”,引用是个别名引用是个别名,当建立引用时当建立引用时,程序用另一个程序用另一个已定义的变量或对象已定义的变量或对象(目标目标)的名字初始化它的名字初始化它,从那从那时起时起,引用作为目标的别名而使用引用作为目标的别名而使用,对引用的改动对引用的改动实际就是对目标的改动。实际就是对目标的改动。 注意：注意：Turbo C不支持引用类型。不支持引用类型。 编写一个函数编写一个函数swap1(x,y)，当执行语句，当执行语句swa

25、p1(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) int tmp; tmp=*x;/*将将x的值放在的值放在tmp中中*/ *x=*y; /*将将x所指的值改为所指的值改为*y*/ *y=tmp； /*将将y所指的值改为所指的值改为tmp*/ 上述函数的调用改为上述函

26、数的调用改为swap2(&a,&b)，显然远不，显然远不如采用引用方式简洁。所以本书后面很多算法都采如采用引用方式简洁。所以本书后面很多算法都采用引用形参。用引用形参。引入引入“引用引用”的概念的概念例如：例如： int a=4; /*a为普通的整型变量为普通的整型变量*/ int &b=a; /*b是是a的引用变量的引用变量*/ 这里说明这里说明b变量是变量变量是变量a的引用的引用,b也等于也等于4,之后之后这两个变量同步改变。当这两个变量同步改变。当a改变时改变时b也同步改变，也同步改变，同样，当同样，当b改变时改变时a也同步改变。也同步改变。难点难点main()

27、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*/ 引用引用常用于函数形参中常用于函数形参中,采用引用型形参时采用引用型形参时,在函数在函数调用时将形参的改变回传给实参调用时将形参的改变回传给实参,例如例如,有如下函数有如下函数(其其中的形参均为引用型形参中的形参均为引用型形参)： void swap(int &x,int &a

28、mp;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。 在算法中应考虑对这三个元素作尽可能少的比较在算法中应考虑对这三个元素作尽可能少的比较和移动和移动,如下述算

29、法在最坏的情况下只需进行如下述算法在最坏的情况下只需进行3次比较次比较和和7次移动。次移动。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.3.1 算法设计的目标算法设计的目标 1.3.2 算法效率分析算法效率分析 1.3.3 算法存储空间分析算法存储空间分析 设计的目标：设计的目标： 正确性。要

30、求算法能正确地执行预先规定的正确性。要求算法能正确地执行预先规定的功能和性能要求。功能和性能要求。 可使用性。要求算法能方便地使用。也叫用可使用性。要求算法能方便地使用。也叫用户友好性。户友好性。 可读性。算法应该易于理解。可读性。算法应该易于理解。 健壮性。能对异常数据作出特殊处理，不会健壮性。能对异常数据作出特殊处理，不会造成异常中断或死机。造成异常中断或死机。 高效率和低存储量需求。高效率和低存储量需求。1.3.1 1.3.1 算法设计的目标算法设计的目标 一个算法是由控制结构一个算法是由控制结构(顺序、分支和循环顺序、分支和循环三种三种)和原操作和原操作(指固有数据类型的操作指固有数据

31、类型的操作)构成的构成的,则算法时间取决于两者的综合效果。则算法时间取决于两者的综合效果。1.3.2 1.3.2 算法时间复杂度分析算法时间复杂度分析 控制语句控制语句1原操作原操作控制语句控制语句n原操作原操作一个算法一个算法 同一问题可以采用多种算法实现。如何同一问题可以采用多种算法实现。如何比较算法执行效率？比较算法执行效率？ 算法描述的语言不同算法描述的语言不同 算法执行的环境不同算法执行的环境不同 其他因素其他因素 所以不能用绝对执行时间进行比较所以不能用绝对执行时间进行比较 为了便于比较同一问题的不同算法为了便于比较同一问题的不同算法,通常从算通常从算法中选取一种对于所研究的问题来

32、说是基本运算法中选取一种对于所研究的问题来说是基本运算的原操作的原操作(以下将基本运算的原操作简称为以下将基本运算的原操作简称为基本基本运算运算)。 算法执行时间大致为基本运算所需的时间与算法执行时间大致为基本运算所需的时间与其运算次数其运算次数(也称为频度也称为频度)的乘积。的乘积。 被视为算法被视为算法基本运算基本运算的一般是最深层循环内的一般是最深层循环内的语句。的语句。 在一个算法中在一个算法中, ,进行基本运算的次数越少进行基本运算的次数越少, ,其运行其运行时间也就相对地越少；基本运算次数越多时间也就相对地越少；基本运算次数越多, ,其运行时其运行时间也就相对地越多。间也就相对地越

33、多。 所以所以, ,通常把算法中包含基本运算次数的多少称通常把算法中包含基本运算次数的多少称为算法的时间复杂度为算法的时间复杂度, ,也就是说也就是说, ,一个算法的时间复杂一个算法的时间复杂度是指该算法的基本运算次数度是指该算法的基本运算次数。 算法中算法中基本运算次数基本运算次数T(n)是问题规模是问题规模n的某个函数的某个函数f(n),记作记作： T(n)=O(f(n) 记号记号“O”读作读作“大大O”,它表示随问题规模它表示随问题规模n的增的增大算法执行时间的增长率和大算法执行时间的增长率和f(n)的增长率相同。的增长率相同。“O”的形式定义为：的形式定义为： 若若f(n)是正整数是正

34、整数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)本质上讲，是一种本质上讲，是一种最高数量级的比较最高数量级的比较 一个没有循环的算法的基本运算次数与问题规模一个没有循环的算法的基本运算次数与问题

35、规模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!)当当n n取得取得很大时很大时，指数阶算法和多

36、项式，指数阶算法和多项式时间时间算法算法在在所需时间所需时间上上非常悬殊非常悬殊。多项式时间算法解决的问题叫多项式时间算法解决的问题叫P P问题；问题；指数阶算法指数阶算法解决的问题叫解决的问题叫NPNP问题。问题。世界难题：世界难题： NPNP问题问题 = P= P问题问题若有人能将现有若有人能将现有NPNP问题中的任何一个问题中的任何一个算法化简为多项式时间算法，那就取算法化简为多项式时间算法，那就取得了一个伟大的成就。得了一个伟大的成就。？例例：多项式时间算法与指数时间算法的执行时间比较。假设算法P1的时间复杂度为T1(n) = n2，算法P2的时间复杂度为T2(n) = 2 n , 计

37、算机的运算速度是1微秒（即每秒1000000次运算）。 nP1运算次数运算次数P1运算时间运算时间P2运算次数运算次数P2运算时间运算时间101000.0001秒秒10240.001024秒秒204000.0004秒秒10485761.049秒秒309000.0009秒秒107374802417.9分钟分钟4016000.0016秒秒1099511627776305.42小时小时6036000.0036秒秒115292150460684697636558. 9年年例例：多项式时间算法与阶乘时间算法的执行时间比较。假设算法P1的时间复杂度为T1(n) = n2，算法P2的时间复杂度为T2(n)

38、= n! , 计算机的运算速度是每秒1亿次运算）。 nP1运算次数运算次数P1运算时间运算时间P2运算次数运算次数P2运算时间运算时间101000.000001秒秒36288000.036288秒秒204000.000004秒秒2.43101777.13年年309000.000009秒秒2.6510328.41016 年年 例例1.4 求两个求两个n阶方阵的相加阶方阵的相加C=A+B的算法的算法如下如下,分析其时间复杂度。分析其时间复杂度。 #define MAX 20 /*定义最大的方阶定义最大的方阶*/ void matrixadd(int n,int AMAXMAX, int BMAXM

39、AX,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) 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+; r

40、eturn(s); 基本语句或基本操作基本语句或基本操作 解：解：该算法的基本操作是语句该算法的基本操作是语句s+,其频度：其频度： T(n)= =O(n3)则该算法的时间复杂度为则该算法的时间复杂度为O(n3)。 niijjk0001例例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)/

41、2， 并满足并满足s=m(m-1)/2n，则有，则有m 。 T(n)=O( ) 所以，该算法的时间复杂度为所以，该算法的时间复杂度为O( )。 nnn 例例1.7 有如下算法：有如下算法： 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,n,0)，求其时间复杂度。，求其时间复杂度。 解：设解：设fun(a,n,

42、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(n2)。 空间复杂度是对一个算法在运行过程中空间复杂度是对一个算法在运行过程中临时占用的临时占用的存储空间存储空间大

43、小的量度大小的量度,一般也作为问题规模一般也作为问题规模n的函数的函数,以以数量级形式给出数量级形式给出,记作：记作： S(n) = O(g(n) 若所需额外空间相对于输入数据量来说是常数若所需额外空间相对于输入数据量来说是常数,则称则称此算法为原地工作。若所需存储量依赖于特定的输入此算法为原地工作。若所需存储量依赖于特定的输入,则通常按最坏情况考虑。则通常按最坏情况考虑。1.3.3 1.3.3 算法空间复杂度分析算法空间复杂度分析 返回返回 例例1.8 分析例分析例1.4和例和例1.5的空间复杂度。的空间复杂度。 解：由于这两个算法中临时变量的个数与问解：由于这两个算法中临时变量的个数与问题

44、规模题规模n无关无关,所以空间复杂度均为所以空间复杂度均为O(1)。1.4 数据结构算法程序数据结构算法程序 数据结构对算法的影响主要在两方面数据结构对算法的影响主要在两方面 （1 1）数据结构的存储能力）数据结构的存储能力数据结构存储能力强、存储信息多算法将数据结构存储能力强、存储信息多算法将会较好设计（时间少），存储空间大。会较好设计（时间少），存储空间大。时间和空间的平衡时间和空间的平衡（2 2）定义在数据结构上的操作）定义在数据结构上的操作在数据结构上定义基本操作算法调用这些在数据结构上定义基本操作算法调用这些基本操作。基本操作。基本操作越完整，基本操作越完整，算法设计就越容算法设计就

45、越容易易算法算法基本操作基本操作基本算法基本算法应用程序应用程序应用程序是通过应用程序是通过调用基本算法实调用基本算法实现的现的选择数据结构需要考虑的几个方面：选择数据结构需要考虑的几个方面：（1）数据结构要适应问题的状态描述）数据结构要适应问题的状态描述（2）数据结构应与所选择的算法相适应）数据结构应与所选择的算法相适应（3）数据结构的选择同时要兼顾程序设计的方便）数据结构的选择同时要兼顾程序设计的方便（4）灵活应用已有知识）灵活应用已有知识例如，有若干学生数据（学生数小于例如，有若干学生数据（学生数小于50），每个学生数据包含学号（每个学生学），每个学生数据包含学号（每个学生学号是惟一的，

46、但学生记录不一定按学号顺序号是惟一的，但学生记录不一定按学号顺序存放）、姓名、班号和若干门课程成绩（每存放）、姓名、班号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超个学生所选课程数目可能不等，但最多不超过过6门）。门）。要求设计一个程序输出每个学生的学号、要求设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从姓名和平均分以及每门课程（课程编号从16）的平均分。）的平均分。设计方案设计方案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分数分数