数据结构：第1章 绪论

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

1、第第1 1章章 绪论绪论 1.2 1.2 算法及其描述算法及其描述1.1 1.1 什么是数据结构什么是数据结构1.3 1.3 算法分析算法分析 1.41.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、的总。它是计算机操作的对象的总称称, ,也是计算机处理信息的某种特定的符号表示形也是计算机处理信息的某种特定的符号表示形式。式。 例如例如, 200902, 200902班全体学生记录的集合为一个班班全体学生记录的集合为一个班的的学生数据。学生数据。 数据元素：数据元素：是数据是数据(集合集合)中的一个中的一个“个体个体”,是数是数据的基本单位。据的基本单位。 1.1.1 1.1.1 数据结构的定义数据结构的定义 例如例如,200902,200902班全班为班全班为学生数据学生数据, ,而其中的每个学生而其中的每个学生的记录是一个个的记录是一个个数据元素数据元素) )。 数据结构：数据结构：是

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

4、据的物理结构。也称为数据的物理结构。 (3)施加在该数据上的施加在该数据上的操作操作,即数据的运算即数据的运算。 例例1.1 有有一一个个学学生生表表如如表表1.1所所示示。这这个个表表中中的的数数据据元元素素是是学学生生记记录录,每每个个数数据据元元素素由由四四个个数数据项据项(即学号、姓别、性别和班号即学号、姓别、性别和班号)组成。组成。学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901表表1.1 学生表学生表 (学生数据学生数据)记录1记录2记录

5、3记录4.记录n 该该表表中中的的记记录录顺顺序序反反映映了了数数据据元元素素之之间间的的逻逻辑辑关关系系, ,我我们们用用学学号号标标识识每每个个学学生生记记录录, ,这这种种逻逻辑辑关关系系可可以以表表示示为：为： , , 其其中中尖尖括括号号“a ”表表示示元元素素a ai i和和a ai+1i+1之之间间是是相相邻邻的的, ,即即a ai i在在a ai+1i+1之前之前,a,ai+1i+1在在a ai i之后。之后。学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男990

6、25王萍王萍女女9901将每行(一个学生)抽象为一个结点：模型：n个元素的集合及其内在关系构成了一个数据结构（叫线性表）1834265一个数据结构一个数据结构 这这些些数数据据在在计计算算机机存存储储器器中中的的存存储储方方式式就就是是存存储储结结构构。通通常常可可以以采采用用C/C+语语言言中中的的结结构构体体数数组组和和链链表表两两种种方方式式实实现现其其存存储储结结构。构。存放学生表的结构体数组存放学生表的结构体数组Stud定义为：定义为： struct Student int no; /*存储学号存储学号*/ char name8; /*存储姓名存储姓名*/ char sex2; /*

7、存储性别存储性别*/ char class4; /*存储班号存储班号*/ ; Student Stud7= 1,“张斌张斌”,“男男”,“9901”, , 5,王萍王萍,女女,9901 ; 结构体数组结构体数组Stud各元素在内存中顺序存放各元素在内存中顺序存放,即第即第i(1i6)个学生对应的元素个学生对应的元素Studi存放在第存放在第i+1个学生个学生对应的元素对应的元素Studi+1之前之前,Studi+1正好在正好在Studi之之后。后。1张斌张斌8刘丽刘丽34李英李英20陈华陈华 12王奇王奇26董强董强5王萍王萍Stud0Stud1Stud2Stud3Stud4Stud5Stud

8、6 存放学生表的链表的结点类型存放学生表的链表的结点类型StudType定义为：定义为： typedef struct studnode int no; /*存储学号存储学号*/ char name8; /*存储姓名存储姓名*/ char sex2; /*存储性别存储性别*/ char class4; /*存储班号存储班号*/ struct studnode *next; /*存储指向下一个学生的指针存储指向下一个学生的指针*/ StudType；StudType * head;head1张斌张斌男男 99018刘丽刘丽女女 990234李英李英女女 990120陈华陈华男男 990212王奇

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

10、样样的的运运算算, ,在在不同的存储结构中不同的存储结构中, ,其实现过程是不同的其实现过程是不同的。为为了了更更确确切切地地描描述述一一种种数数据据结结构构,通通常常采采用用二二元组表示：元组表示： 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、也也就无结构可言。就无结构可言。如：如：D=d1, d2, d3, d4, d5, d6, d7 rj表表示示集集合合R中中的的第第j个个二二元元关关系系(后后面面均均简简称称关关系系),m为为R中中关关系系的的个个数数,特特别别地地,若若m=0,则则R是是一一个个空空集集,表表明明集集合合D中中的的元元结结点点间间不不存存在在任任何何关关系系,彼彼此此是是独独立立的。的。如：如： R=r1, r2 有有2种不同的关系种不同的关系r1= , , r2= , , 例如例如,采用二元组表示例采用二元组表示例1.1的学生表的学生表。 学学生生表表中中共共有有7个个结结点点,依依次次用用d1d7表表示

12、示,则则对对应应的的二二元组表示为元组表示为B=(D,R),其中：其中： D=d1, d2, d3, d4, d5, d6, d7 R=r r = , , , , , 学号学号姓名姓名性别性别班号班号d11张斌张斌男男9901d28刘丽刘丽女女9902d334李英李英女女9901d420陈华陈华男男9902d512王奇王奇男男9901d626董强董强男男9902d75王萍王萍女女9901又例如又例如, ,有如下数据即一个矩阵：有如下数据即一个矩阵： 对应的二元组表示为对应的二元组表示为B=(D,R),其中：其中：D=2,6,3,1,8,12,7,4,5,10,9,11R=r1,r2 其中其中,

13、r1表示行关系表示行关系,r2表示列关系表示列关系r1=, ,r2=, 一种数据结构还能够利用图形形象地表示出来一种数据结构还能够利用图形形象地表示出来, ,图形中的每个结点对应着一个数据元素图形中的每个结点对应着一个数据元素, ,两结点之间两结点之间的连线对应着关系中的一个序偶。的连线对应着关系中的一个序偶。 上述上述“学生表学生表”数据结构用下图的图形表示。数据结构用下图的图形表示。学生表数据结构图示学生表数据结构图示数据的逻辑结构主要有以下几类：数据的逻辑结构主要有以下几类：(1)(1)集合集合 集集合合是是指指数数据据的的各各个个数数据据元元素素之之间间没没有有关关系系。即即关关系是空

14、集。系是空集。1.1.2 1.1.2 逻辑结构类型逻辑结构类型 (2)(2)线性结构线性结构 所所谓谓线线性性结结构构, ,该该结结构构中中的的结结点点之之间间存存在在一一对对一一的的关关系系。其其特特点点是是开开始始结结点点和和终终端端结结点点都都是是惟惟一一的的, ,除除了了开开始始结结点点和和终终端端结结点点以以外外, ,其其余余结结点点都都有有且且仅仅有有一一个个前前驱驱结结点点, ,有有且且仅仅有有一一个个后后继继结结点点。顺顺序序表表就就是是典典型型的的线线性结构。性结构。 (3)非线性结构非线性结构 所谓所谓非线性结构非线性结构,该结构中的结点之间该结构中的结点之间存在存在一对多

15、或多对多的关系一对多或多对多的关系。它又可以细分为树形。它又可以细分为树形结构和图形结构两类。结构和图形结构两类。 所所谓谓树树形形结结构构, ,该该结结构构中中的的结结点点之之间间存存在在一一对对多多的的关关系系。其其特特点点是是每每个个结结点点最最多多只只有有一一个个前前驱驱, ,但但可可以以有有多个后继多个后继, ,可以有多个终端结点。树形结构简称为树。可以有多个终端结点。树形结构简称为树。 所所谓谓图图形形结结构构, ,该该结结构构中中的的结结点点之之间间存存在在多多对对多多的的关关系系。其其特特点点是是每每个个结结点点的的前前驱驱和和后后继继的的个个数数都都可可以以是是任任意意的的。

16、因因此此, ,可可能能没没有有开开始始结结点点和和终终端端结结点点, ,也也可可能能有有多多个个开开始始结结点点、多多个个终终端端结结点点。图图形形结结构构简简称称为为图。图。例例人机对奕问题树结构树结构.将每个棋局都抽象成一个结点：将每个棋局都抽象成一个结点：棋局棋局1棋局棋局2棋局棋局3棋局棋局4棋局棋局5棋局棋局6棋局棋局7 棋局棋局8 棋局棋局9 棋局棋局10整体：是一个数据结构，叫整体：是一个数据结构，叫“树结构树结构”运算：遍历整棵树，找出运算：遍历整棵树，找出“赢赢”的路线；等的路线；等用二元组表示的数据结构用二元组表示的数据结构B B = D , R )D = 棋局棋局1，棋局

17、，棋局2，棋局，棋局3，., 棋局棋局n R = r r = ， ， ，. , ， ， . 例：例：田径赛的时间安排问题田径赛的时间安排问题: : 设有设有六个六个比赛比赛项目项目，规定每个选，规定每个选手手至多至多可参加可参加三个项目三个项目，有，有五人五人报名报名参加参加比赛比赛（如下表所示）设计比赛日（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成程表，使得在尽可能短的时间内完成比赛。比赛。姓名姓名项目项目1项目项目2项目项目3丁一丁一 A B E马二马二 C D 张三张三 C E F李四李四 D F A王五王五 B FAEBFDC比赛比赛时间时间比赛项目比赛项目1A，C2B，D

18、3E4F1.1.设代号代表不同的项目设代号代表不同的项目跳高跳高 跳远跳远 标枪标枪 A B C 铅球铅球 100米米 200米米 D E F2.2.用顶点代表比赛项目用顶点代表比赛项目: :不能同时进行比赛的项目之不能同时进行比赛的项目之间连上一条边。间连上一条边。安排安排四个单四个单位时间位时间进行比进行比赛赛AEBFDC用二元组表示的数据结构用二元组表示的数据结构B B = D , R )D = A, B, C, D, E, F R = r r = ， ， ， , ， ， , , AEBFDCAEBFDC(1)(1)顺序存储方法顺序存储方法 (2)(2)链式存储方法链式存储方法 (3)(

19、3)索引存储方法索引存储方法 (4)(4)散列存储方法散列存储方法 1.1.3 1.1.3 存储结构类型存储结构类型（具体细节略) 1 1 数据类型数据类型 在用高级程序语言编写的程序中在用高级程序语言编写的程序中, ,必须对必须对程序中出现的每个变量、常量或表达式程序中出现的每个变量、常量或表达式, ,明确明确说明它们所属的数据类型。不同类型的变量说明它们所属的数据类型。不同类型的变量, ,其所能取的值的范围不同其所能取的值的范围不同, ,所能进行的操作不所能进行的操作不同。同。数据类型是一组性质相同的数据类型是一组性质相同的值的集合值的集合和和定义在此集合上的一组定义在此集合上的一组操作操

20、作的总称的总称。1.1.4 1.1.4 数据类型和数据结构数据类型和数据结构 如如C/C+中的中的int就是就是整型数据类型整型数据类型。它是所。它是所有整数的集合有整数的集合(在在16位计算机中为位计算机中为32768到到32767的全体整数的全体整数)和相关的整数运算和相关的整数运算(如、如、等、等)。C+的各种数据类型介绍略的各种数据类型介绍略如：如：float, long, char, 指针类型，数组类型，指针类型，数组类型，结构体类型，共用体类型。结构体类型，共用体类型。自定义数据类型名称：用自定义数据类型名称：用typedeftypedef 旧数据类型旧数据类型 新数据类型名新数据

21、类型名如：如：typedef char ElemType则：则：ElemType 就是就是char 如：如： typedef struct stud int no; char name10; int score; student ; 定义变量时：定义变量时： 可用可用 student x , y ; 2 抽象数据类型抽象数据类型 抽象数据类型抽象数据类型(Abstract Data Type简写为简写为ADT)指的是用户进行软件系统设计时从问题的指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算据结构上的运算,而不

22、考虑计算机的具体存储结而不考虑计算机的具体存储结构和运算的具体实现算法。构和运算的具体实现算法。 ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象： D = 一个个数据对象的描述一个个数据对象的描述 数据关系：数据关系： R = 数据关系的描述数据关系的描述 基本运算：基本运算： 每一个基本运算的声明每一个基本运算的声明 ADT 抽象对象类型名抽象对象类型名例如例如,抽象数据类型抽象数据类型“复数复数”的定义：的定义：复数形式：复数形式：e1+e2i 或或（e1，e2）ADT Complex 数据对象：数据对象： D=e1, e2 | e1,e2均为实数均为实数数据关系：数据关系： R

23、= | e1是复数的实数部分是复数的实数部分,e2 是复是复 数的虚数部分数的虚数部分 基本运算：基本运算： AssignComplex(&Z,v1,v2)：构构造造复复数数Z,其其实实部部和和虚虚部部分别赋以参数分别赋以参数v1和和v2的值。的值。 DestroyComplex(&Z):复数复数Z被销毁。被销毁。 GetReal(Z,&real):用用real返回复数返回复数Z的实部值。的实部值。 GetImag(Z,&Imag):用用Imag返回复数返回复数Z的虚部值。的虚部值。 Add(z1,z2,&sum):用用sum返回两个复数返回两个复数z1,z2的和值。的和值。 ADT Comp

24、lex抽象数据类型抽象数据类型 = 逻辑结构抽象运算逻辑结构抽象运算抽象数据类型需要通过固有数据类型（也就是高级程序设计语抽象数据类型需要通过固有数据类型（也就是高级程序设计语言中已经实现的数据类型）如言中已经实现的数据类型）如C+中的类来实现。中的类来实现。数据类型数据类型 = 存储结构已实现的运算存储结构已实现的运算1.2 1.2 算法及其描述算法及其描述1.2.1 1.2.1 什么是算法什么是算法 1.2.2 1.2.2 算法描述算法描述1.2.1 1.2.1 什么是算法什么是算法 数据元素之间的关系有逻辑关系和物理关系数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的运算

25、（抽象运算）和对应的操作有逻辑结构上的运算（抽象运算）和具体存储结构上的运算（抽象运算的实现）。具体存储结构上的运算（抽象运算的实现）。 通常把在具体存储结构上实现某个运算的步骤通常把在具体存储结构上实现某个运算的步骤或过程称为或过程称为算法算法。广义地说，广义地说，算法是对特定问题求解步骤的一种描算法是对特定问题求解步骤的一种描述，它是指令的有限序列述，它是指令的有限序列，其中每个指令表示计，其中每个指令表示计算机的一个或多个操作。算机的一个或多个操作。算法的五个重要的特性算法的五个重要的特性(1)有穷性有穷性: 算法在执行有穷步骤之后结束，且每算法在执行有穷步骤之后结束，且每 一步都可在有

26、穷时间内完成。一步都可在有穷时间内完成。(2)确定性确定性: 算法的每条操作指令有确切的含义，读者理算法的每条操作指令有确切的含义，读者理 解时不会产生二义性；且在任何条件下，算解时不会产生二义性；且在任何条件下，算 法只有唯一的执行路径。法只有唯一的执行路径。 (3)可行性可行性: 每个算法中的操作都足够基本，可通过执行每个算法中的操作都足够基本，可通过执行有限次已经实现的基本操作来实现。有限次已经实现的基本操作来实现。(4)有输入：有输入：有有0个或多个外部输入作为算法加工的对象。个或多个外部输入作为算法加工的对象。若无外部输入，则算法的加工对象已被嵌入在算法中。若无外部输入，则算法的加工

27、对象已被嵌入在算法中。 (5)有输出：有输出：有有1个或多个输出，是算法进行信息加工的个或多个输出，是算法进行信息加工的 结果。结果。 例例 考虑下列两段描述：考虑下列两段描述：(1)void exam1( ) int n; n2; while (n%20) nn+2; coutn; (1)算法是一个死循环算法是一个死循环, 不能在有穷步后结束，违反了不能在有穷步后结束，违反了算法的有穷性特征。算法的有穷性特征。(2)void exam2( ) y=0; x=5/y; coutx“ ” y;算算法法包包含含除除零零错错误误,停停机机了了。这这违违反反了了算算法法的的有有穷穷性特征，不能在有穷时

28、间内完成。性特征，不能在有穷时间内完成。getsum(int num) /无输出的算法没有任何意义无输出的算法没有任何意义 int i, sum=0; for( i=1; i=num; i+ ) sum+=i; 缺少：缺少：return sum;或者：或者：coutsum=“sum; 1.2.2 1.2.2 算法描述算法描述 本书中采用本书中采用C/C+C/C+语言描述算法。语言描述算法。 说明：说明：C+语言中提供了一种引用运算符语言中提供了一种引用运算符“&”,引用是个别名引用是个别名,当建立引用时当建立引用时,程序用另一个程序用另一个已定义的变量或对象已定义的变量或对象(目标目标)的名字

29、初始化它的名字初始化它,从那时从那时起起,引用作为目标的别名而使用引用作为目标的别名而使用,对引用的改动实际对引用的改动实际就是对目标的改动。就是对目标的改动。 注意：注意：Turbo C不支持引用类型。不支持引用类型。返回返回 引引用用常常用用于于函函数数形形参参中中,采采用用引引用用型型形形参参时时,在在函函数数调调用用时时将将形形参参的的改改变变回回传传给给实实参参,例例如如,有有如如下下函函数数(其其中的形参均为引用型形参中的形参均为引用型形参)： void swap ( int &x, int &y ) /*形参前的形参前的“&”符号不是指针运算符符号不是指针运算符*/ int tm

30、p=x; x=y; y=tmp ； 当用执行语句当用执行语句swap(a,b)时时, a和和b的值发生了交换的值发生了交换。 反之，有以下函数反之，有以下函数swap1( ) void swap1 ( int x , int y) int temp; temp=x; x=y; y=temp; 当用执行语句当用执行语句swap1(a,b)时时, a和和b的值不会发生了的值不会发生了交换。交换。例例 编编写写一一个个算算法法, 读读入入三三个个整整数数x,y和和z的的值值,要求从大到小输出这三个数。要求从大到小输出这三个数。 解解：依依次次输输入入x,y和和z这这三三个个整整数数,通通过过比比较较

31、交交换后换后,使得使得xyz,然后输出然后输出x,y,z。 在在算算法法中中应应考考虑虑对对这这三三个个元元素素作作尽尽可可能能少少的的比比较较和和移移动动,如如下下述述算算法法在在最最坏坏的的情情况况下下只只需需进进行行3次比较和次比较和7次移动。次移动。void Descending( ) int x, y, z, temp; printf(输入输入x,y,z); / coutxyz; if (x=y */ if (yz*/ if (x=temp) y=temp； else y=x;x=temp; printf(%d,%d,%dn,x,y,z); / coutxyz“n”; 另一写法：另一

32、写法：void Descending( int x, int y, int z ) / 参数作为输入参数作为输入 if (x=y*/ if (yz*/ if (x=temp) y=temp； else y=x;x=temp; printf(%d,%d,%dn,x,y,z); 再一种写法：再一种写法：void Descending( int &x, int & y, int & z ) / 引用参数既作为输入，又作为输出引用参数既作为输入，又作为输出 if (x=y*/ if (yz*/ if (x=temp) y=temp； else y=x;x=temp; 1.3 1.3 算法分析算法分析

33、1.3.1 算法设计的目标算法设计的目标 1.3.2 算法效率分析算法效率分析 1.3.3 算法存储空间分析算法存储空间分析 设计的目标：设计的目标： 正正确确性性。要要求求算算法法能能正正确确地地执执行行, 实实现现预预先先规规定的功能和性能要求。定的功能和性能要求。 可可使使用用性性。要要求求算算法法能能方方便便地地使使用用。也也叫叫用用户友好性。户友好性。 可读性。可读性。算法应该易于理解。算法应该易于理解。 健健壮壮性性。能能对对异异常常数数据据作作出出特特殊殊处处理理，不不会会造成异常中断或死机。造成异常中断或死机。 高效率和低存储量需求高效率和低存储量需求。1.3.1 1.3.1

34、算法设计的目标算法设计的目标 衡量算法效率的方法：衡量算法效率的方法：事后统计法：事后统计法：-执行程序，计算时间。执行程序，计算时间。事前分析估算法。事前分析估算法。 一一个个算算法法是是由由控控制制结结构构(顺顺序序、分分支支和和循循环环三三种种)和和原原操操作作(指指固固有有数数据据类类型型的的操操作作)构构成成的的,则算法时间取决于两者的综合效果。则算法时间取决于两者的综合效果。1.3.2 1.3.2 算法效率分析算法效率分析 例例1.8 求两个求两个n阶方阵的加法阶方阵的加法#define MAX 20void matrixadd(int n, int A MAX , B MAX ,

35、 C MAX ) int i, j; for(i=0; in; i+) 循环结构循环结构1 for(j=0; jn; j+) 循环结构循环结构2 Cij=Aij+Bij; 基本运算基本运算(原操作原操作) 算法的执行时间算法的执行时间=循环结构循环结构1的总时间的总时间+循环结构循环结构2总时间总时间 +基本运算的总时间基本运算的总时间 算算法法执执行行时时间间大大致致为为基基本本运运算算所所需需的的时时间间与其执行次数与其执行次数(也称为频度也称为频度)的乘积。的乘积。为简便，取每个基本运算的时间为简便，取每个基本运算的时间=1执行时间执行时间 = 基本运算的执行次数基本运算的执行次数 例例

36、1.8 求两个求两个n阶方阵的加法阶方阵的加法#define MAX 20void matrixadd(int n, int A MAX , B MAX , C MAX ) int i, j; for(i=0; in; i+) n+1次次 for(j=0; jn; j+) n(n+1) 次次 Cij=Aij+Bij; n2次次 算法的执行时间算法的执行时间T(n) = 循环结构循环结构1的总频度的总频度+循环结构循环结构2总频度总频度 +基本运算的总频度基本运算的总频度 = n+1+n(n+1)+n2 = 2n2 +2n+1算算法法中中基基本本运运算算执执行行次次数数T(n)是是问问题题规规模

37、模n的的函数，函数，T(n)的的数量级数量级是函数是函数f(n), 记作记作： T(n)=O( f(n) ) 读作读作“大大O”, 意指数量级意指数量级将将O( f(n) ) 称为算法的时间复杂度称为算法的时间复杂度例如例如, T(n)=3n2-5n+10000=O(n2)T(n)的数量级是的数量级是n2, 时间复杂度是时间复杂度是O(n2)主要反映主要反映n值很大时算法的时间性能值很大时算法的时间性能 记记号号“O”读读作作“大大O”,它它表表示示随随问问题题规规模模n的的增增大大算算法法执执行行时时间间T(n)的的增增长长率率和和f(n)的的增增长长率率相相同同。“O”的形式定义为：的形式

38、定义为： 若若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)例.求两个n阶方阵的乘积#definen100MATRIXMLT(floatAn,Bn,Cn);inti,j,k

39、;语句频度语句频度for(i=0;in;i+)n+1for(j=0;jn;j+)n(n+1)Cij=0;n2for(k=0;kn;k+)n2(n+1)Cij=Cij+Aik*Bkj;n3语句频度之和：T(n)=2n3+3n2+2n+1该算法的时间复杂度T(n)=2n3+3n2+2n+1=O(n3)一般地，估算估算算法中频度最大的语句算法中频度最大的语句 该该算算法法中中的的基基本本运运算算是是三三重重循循环环中中最最深深层层的的语语句句Cij=Cij+Aij*Bij, 分析它的频度分析它的频度, 即即： T(n)= =O(n3) 例例1.8 求求两两个个n阶阶方方阵阵的的相相加加C=A+B的的

40、算算法法如如下下,分分析其时间复杂度。析其时间复杂度。 #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)例例 分析以下算法的时间复杂度。分析以下算法的时间复杂度。 int fun

41、(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)。例1.9算法：在数组a0.an-1中查找值kvoidfun(inta,intn,intk)inti;i=0;while(in&ai!=k)i+;returni;例1.10递归算法：voidfun(inta,intn,intk)inti;if(

42、k=n-1)for(i=0;in;i+)coutaiendl;elsefor(i=k;in;i+)ai=ai+i*i;fun(a,n,k+1);/递归调用调用函数：fun(a,n,0),求其时间复杂度。设fun(a,n,k)的执行时间为T1(n,k)fun(a,n,0)的时间复杂度T(n)=T1(n,0)=O(n2) 一个没有循环的算法的基本运算次数与问一个没有循环的算法的基本运算次数与问题规模题规模n无关无关,记作记作O(1), 也称作常数阶也称作常数阶。 一个只有一重循环的算法的基本运算次数一个只有一重循环的算法的基本运算次数与问题规模与问题规模n的增长呈线性增大关系的增长呈线性增大关系,

43、记作记作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!)O(nn)当当n n取得取得很大时很大时，指数阶算法和多项式，指数阶算法和多项式时间时间算法算法在在所需时间所需时间上上非常悬殊非常悬殊。多项式时间算法解决的问题叫多项式时间算法解决的问题叫P P问题；问题；指数阶算法指数阶算法解决的问题叫解决的

44、问题叫NPNP问题。问题。世界难题：世界难题： NPNP问题问题 = P= P问题问题若有人能将现有若有人能将现有NPNP问题中的任何一个问题中的任何一个算法化简为多项式时间算法，那就取算法化简为多项式时间算法，那就取得了一个伟大的成就。得了一个伟大的成就。？例例：多项式时间算法与指数时间算法的执行时间比较。假设算法P1的时间复杂度为T1(n)=n2，算法P2的时间复杂度为T2(n)=2n,计算机的运算速度是1微秒（即每秒1000000次运算）。nP1运算次数运算次数P1运算时间运算时间P2运算次数运算次数P2运算时间运算时间101000.0001秒秒10240.001024秒秒204000.

45、0004秒秒10485761.049秒秒309000.0009秒秒107374802417.9分钟分钟4016000.0016秒秒1099511627776305.42小时小时6036000.0036秒秒115292150460684697636558. 9年年例例：多项式时间算法与指数时间算法的执行时间比较。假设算法P1的时间复杂度为T1(n)=n2，算法P2的时间复杂度为T2(n)=n!,计算机的运算速度是每秒4亿亿次运算-天河二号超级计算机）。nP1运算次数运算次数P1运算时间运算时间P2运算次数运算次数P2运算时间运算时间101003628800204002.43101860.8秒秒3

46、09002.6510322亿亿1千万千万年年 空间复杂度空间复杂度是对一个算法在运行过程中临时占用的是对一个算法在运行过程中临时占用的存储空间大小的量度存储空间大小的量度,一般也一般也作为问题规模作为问题规模n的函数的函数,以以数量级形式给出数量级形式给出,记作：记作： S(n) = O(g(n) 若若所所需需额额外外空空间间相相对对于于输输入入数数据据量量来来说说是是常常数数,则则称称此此算算法法为为原原地地工工作作。若若所所需需存存储储量量依依赖赖于于特特定定的的输输入入,则通常按最坏情况考虑。则通常按最坏情况考虑。1.3.3 1.3.3 算法存储空间分析算法存储空间分析 返回返回 例例

47、分析下例的空间复杂度。分析下例的空间复杂度。#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; 解：由于这个算法中临时变量的个数与问解：由于这个算法中临时变量的个数与问题规模题规模n无关无关, 所以空间复杂度均为所以空间复杂度均为O(1)。1.4 数据结构+算法=程序N.Wirth提出：数据结构+算法=程序 程序设计的本质是：对要处理的问题选择好的

48、数据结构，在此结构上施加好的算法。N.Wirth（1934年年），瑞瑞士士计计算算机机科科学学家家，1960年年获获加加利利福福尼尼亚亚大大学学伯伯克克利利分分校校博博士士学学位位。曾曾任任斯斯坦坦福福大大学学、苏苏黎黎世世联联邦邦理理工工学学院院教教授授。发发明明多多种种计计算算机机语语言言（包包括括Pascal、Modula和和Oberon等等），并并为为软软件件工工程程领领域域作作出出过过开开拓拓性性的的贡贡献献。于于1980年年 获获 得得 计计 算算 机机 科科 学学 界界 最最 高高 奖奖 图图 灵灵 奖奖（http:/en.wikipedia.org/wiki/Turing_Aw

49、ard）。）。数据是程序要计算处理的数据是程序要计算处理的“原料原料”。将将数数据据按按某某种种要要求求组组成成一一种种数数据据结结构构，对对设设计计出出简简明明、高效的程序是大有益处的。高效的程序是大有益处的。沃沃思思指指出出：程程序序就就是是在在数数据据的的某某些些特特定定的的表表示示方方法法和和结结构构的的基基础础上上，对对抽抽象象算算法法的的具具体体表表述述，所所以以说说程程序序离离不不开数据结构。开数据结构。1.4.1 程序和数据结构程序和数据结构1.4.2 算法和程序算法和程序由程序设计语言描述的算法就是计算机程序由程序设计语言描述的算法就是计算机程序。对一个。对一个求解问题而言，

50、算法就是解题的方法，没有算法，程求解问题而言，算法就是解题的方法，没有算法，程序就成了无本之末，无源之水。序就成了无本之末，无源之水。有了算法，将它表示成程序是不困难的。算法是程序有了算法，将它表示成程序是不困难的。算法是程序的核心。算法在程序设计，也可以说软件开发，甚至的核心。算法在程序设计，也可以说软件开发，甚至可以说在整个计算机科学中的地位都是极其重要的。可以说在整个计算机科学中的地位都是极其重要的。1.4.3 算法和数据结构算法和数据结构求求解解的的问问题题可可以以通通过过抽抽象象数数据据类类型型描描述述，它它由由数数据据的的逻逻辑结构和抽象运算两部分组成。辑结构和抽象运算两部分组成。

51、一一种种数数据据的的逻逻辑辑结结构构可可以以映映射射成成多多种种存存储储结结构构，抽抽象象运运算算在在不不同同的的存存储储结结构构上上实实现现可可以以对对应应多多种种算算法法，在在同同一一种种存存储储结结构构上上实实现现也也可可能能有有多多种种算算法法，通通过过算算法法的的时时间间复复杂杂度度和空间复杂度等分析，可以得到好的算法。和空间复杂度等分析，可以得到好的算法。 例电话公司的电话号码查询服务。方案1：数据结构是线性表。TelName13100001张三13600002李四通过姓名查询号码的算法采用顺序查询算法，时间=n/2方案2：采用树结构查询算法的时间T(n)log2n当n=10000

52、00时，方案1的关键字比较次数=n/2=500000方案2的关键字比较次数=log210000002013611111111 刘明刘明13633331234 黄宏黄宏13622221111 田震田震13644441111 邓萍邓萍13655552222 蒋林蒋林13666661122 彭帅彭帅13623456266 张三张三. . . . . . . .问题描述问题描述：有若干学生数据（学生数小于：有若干学生数据（学生数小于50），），每个学生数据包含学号（每个学生学号是唯一的，每个学生数据包含学号（每个学生学号是唯一的，但学生记录不一定按学号顺序存放）、姓名、班但学生记录不一定按学号顺序存放

53、）、姓名、班号和若干门课程成绩（每个学生所选课程数目可号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超过能不等，但最多不超过6门）。门）。要求要求：设计一个程序输出每个学生的学号、姓名：设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从和平均分以及每门课程（课程编号从16）的平）的平均分。均分。一个典型示例一个典型示例设计方案设计方案1：将学生的全部数据项放在一个表中，一：将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于课程最多可选个学生的全部数据对应一条记录。由于课程最多可选6门，门，对应的成绩项也应有对应的成绩项也应有6个。对应的数据结构如

54、下：个。对应的数据结构如下：struct stud int no;/学号学号char name10;/姓名姓名int bno;/班号班号int deg1;/课程课程1分数分数int deg2;/课程课程2分数分数int deg3;/课程课程3分数分数int deg4;/课程课程4分数分数int deg5;/课程课程5分数分数int deg6;/课程课程6分数分数;设计方案设计方案1的的特点：特点： 存储空间：中（若学生没有选该课程，对应空间仍存在）存储空间：中（若学生没有选该课程，对应空间仍存在） 算法时间：少算法时间：少 算法简洁性差：算法完全依赖数据结构算法简洁性差：算法完全依赖数据结构存

55、储结构存储结构1nonamebnodeg1deg2deg3deg4deg5deg61张斌张斌99017882-19285838刘丽刘丽990265-172-18079 设计方案设计方案2：将学生的全部数据项放在一个表中，但一将学生的全部数据项放在一个表中，但一个学生的一门课程成绩对应一条记录。这样成绩项只需要个学生的一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，需增加一个课程编号项。一个，为了区分不同课程成绩，需增加一个课程编号项。对应的数据结构如下：对应的数据结构如下： struct studint no;/学号学号char name10;/姓名姓名int bno;/

56、班号班号int cno;/课程编号课程编号int deg;/课程分数课程分数;存储结构存储结构2nonamebnocnodeg1张斌张斌99011781张斌张斌99012821张斌张斌99014921张斌张斌99015851张斌张斌99016838刘丽刘丽99021658刘丽刘丽99023728刘丽刘丽99025808刘丽刘丽9902679设计方案设计方案2的的特点：特点： 存储空间：大存储空间：大 算法时间：多算法时间：多 算法简洁性：好算法简洁性：好 设计方案设计方案3：将学生的学号、姓名和班号放在一个表中，将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者通过学号关联。

57、前者一将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应一条记录。个学生对应一个记录，后者一门课程成绩对应一条记录。对应的数据结构如下：对应的数据结构如下： struct stud1int no;/学号学号char name10;/姓名姓名int bno;/班号班号;struct stud2int no;/学号学号int cno;/课程编号课程编号int deg;/分数分数;nonamebno1张斌张斌99018刘丽刘丽9902关联关联存储结构存储结构3nocnodeg117812821492158516838165837285808679设计方案设计方

58、案3的的特点：特点： 存储空间：少。存储空间：少。 算法时间：中。算法时间：中。 算法简洁性：好。算法简洁性：好。最佳方案最佳方案综合分析的结果综合分析的结果本章小结本章小结 本章介绍了数据结构的基本概念本章介绍了数据结构的基本概念,主要学习要点主要学习要点如下：如下： (1)数数据据结结构构的的定定义义,数数据据结结构构包包含含的的逻逻辑辑结结构构、存储结构和运算三方面的相互关系。存储结构和运算三方面的相互关系。 (2)各各种种逻逻辑辑结结构构即即线线性性结结构构、树树形形结结构构和和图图形形结构之间的差别。结构之间的差别。返回返回 (3)数据结构和数据类型的差别和联系。数据结构和数据类型的差别和联系。 (4)算法的定义及其特性。算法的定义及其特性。 (5)算法的时间复杂度和空间复杂度分析。算法的时间复杂度和空间复杂度分析。