数据结构培训课件

《数据结构培训课件》由会员分享，可在线阅读，更多相关《数据结构培训课件（88页珍藏版）》请在装配图网上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,*,,*,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,第,1,章 绪论,1.1,什么是数据结构,,1.2,基本概念和术语,,1.3,抽象数据类型的表示与实现,,1.4,算法和算法分析,电子计算机的主要用途：,,早期：主要用于,数值计算,。,,解决问题的步骤：数学模型→解题算法→选择计算机语言编程

2、→测试→最终解答,,关键：如何得出数学模型,,当今：扩大到,非数值计算领域,。,,计算机的操作对象的关系更加复杂，数据元素间的相互关系有时无法用数学方程来描述。所处理的数据量大且具有一定的关系；而对其的操作也不再是单纯的数值计算，更多地是对其进行组织、管理和检索等。,例,1,：学籍档案管理,假设一个学籍档案管理系统应包含如下表所示的学生信息：,特点：,每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；,,每列的数据类型一样；,,表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的,线性结构,；,,对它的操作通常是插入、删除、更新、按条件检索某个学生的信息等等

3、。,例,2,：输出,n,个对象的全排列,输出,3,个对象的全排列可以使用下图所示的形式描述：,特点：,在求解过程中，所处理的数据之间具有层次关系，这是我们所说的,树形结构,；,,对它的操作有：建立树形结构，输出最低层结点内容等等。,例,3,：制定教学计划,制定教学计划时，需考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：,,课程先后关系如图：,,c1,,,,,,,,,,,,c9,c4,c2,c12,c10,c11,c5,c3,c6,c7,c8,,c1,,,,,,,,,,,,c9,c4,c2,c12,c1

4、0,c5,c3,c6,c7,c8,c11,特点：,课程之间的先后关系用,图结构,描述；,,通过实施创建图结构，按要求将图结构中的顶点进行线性排序。,结论,要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点、之间的关系，在计算机中的表示方式及各种操作的具体实现手段。因此，,《,数据结构,》,研究的主要内容是：,,数据元素之间的,逻辑关系,,数据的,存储结构,,采用何种,操作,实现算法的效率更高,程序设计,：,为计算机处理问题编制一组指令集。,,算 法,：,处理问题的策略。,,数据结构,：,问题的数学模型。,,,程序设计的实质是对确定的问题选择一种好的结构，加上设计一

5、种好的算法。,程 序,=,算 法,+,数据结构,“,Programs = Algorithm + Data Structures”,,瑞士学者,Niklaus Wirth,于,1976,年出版的书名。,课程任务：,1.,讨论现实世界中数据的各种,逻辑结构,及在计算机中的,存储结构,；,,,2.,进行各种,非数值运算的算法,。,课程目的：,掌握,数据组织,、,存储,和,处理,的常用法，为进行软件开发或后续专业课程学习打下良好的基础。,课程内容：,数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。,第,1,章 绪论,,1.1,什么是数据结构,,,1.2,基本

6、概念和术语,,1.3,抽象数据类型的表示与实现,,1.4,算法和算法分析,1.,数据,,是对客观事物的符号表示。在计算机科学中是指,所有能输入到计算机中并被计算机处理的符号的总称。计算机程序加工的“原料”。,例：,一个利用数值分析方法解代数方程的程序，其处理对象是,整数和实数,；,,一个编译程序或文字处理程序的处理对象是,字符串,。,,还有,声音,、,图象,、,视频,等等通过编码都属于数据的范畴。,2.,数据元素,,,是数据的基本单位。,,数据中的一个“个体”，数据结构中讨论的,基本单位,。,,在计算机中通常作为一个整体进行考虑和处理。,例,：一个整数“,5”,；一个字符“,N”,；图中的一个

7、顶点等。,,,复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。,,例,：一个学生的基本信息就是一个数据元素，其中的学号、姓名等被称为“数据项”。,,,因此数据项是数据结构中讨论的,最小单位,。,数据元素是数据项的集合，,数据项是数据的不可分割的最小单位,。,3.,数据对象,,,性质相同的数据元素的集合。是数据的子集。,例：,,整数数据对象是集合,N={0,，,±1,，,±2,，,…},。,,英文字母数据对象是集合,,,C={‘A’,，,……,，‘,Z’},。,,如何选定数据对象将依问题而定！,,譬如，在学生管理系统中，可能,以一个班级的学生记录,作为数据对象，也可能,以一个年

8、级的学生记录,作为数据对象。,4.,数据的逻辑结构,,讨论计算机系统中数据的组织形式及其相互关系。即相互之间存在一种或多种特定关系的数据元素的集合。,,数据逻辑结构的,形式定义,：数据逻辑结构是一个二元组：,,Data_structure={D,R},,,其中，,D,是数据元素的有限集，,R,是,D,上的关系的集合。,例：,在计算机科学中，复数可取如下定义：复数数据的逻辑结构,,,Complex = (C,R),,,其中：,C,是含两个实数的集合,{c1,c2}; R={P},，而,P,是定义在集合,C,上的一种关系,{},，其中有序偶,,表示,c1,是复数的实部，,c2,是复数的虚部。,,4

9、,数据的逻辑结构,例：,list=(D,S1),tree=(D,S2),graph=(D,S3),,D={a,b,c,d,e},,S1={,,,},,S2={,,,},,S3={,,,},,,逻辑结构示意图,,<,a,b>,,称,a,是,b,的前驱，,b,是,a,的后继。,,若某结点没有前驱，则称该结点为开始结点；,,若某结点没有后继，则称该结点为终端结点；,,b,a,c,d,e,list,a,e,d,b,c,graph,e,d,b,c,a,tree,（,a,b,c,d,e）,4.,数据的逻辑结构,,数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。,数据的逻辑结构可

10、归结为以下四类,:,,,1,）集合：数据元素之间除“同属于一个集合”的关系外无其它关系。,,2,）线性结构：数据元素间存在一对一的关系。,,3,）树形结构：数据元素间存在一对多的关系。,,4,）图（网）状结构：数据元素间存在多对多的关系。,,线性结构：一对一,非线性结构,,树形结构：一对多,图状结构：多对多,逻辑结构,集合,5.,数据的存储结构（物理结构）,,存储结构：逻辑结构在计算机中的表示,(,又称映象,),称为数据的物理结构，又称存储结构。包括数据元素的表示和关系的表示。,,计算机中表示信息的最小单位是二进制数的一位,(bit),。可用一个由若干位组合起来形成的一个位串表示一个数据元素，

11、通常称这个位串为,元素,(Element),或结点,(Node),。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为,数据域,(DataField),。,5.,数据的存储结构（物理结构）,存储的要求,：既存储各结点的数值又要存储结点与结点之间的逻辑关系。,,四种基本的存储结构,：顺序、链接、索引、散列存储。,,内存空间、内存地址,,程序在运行期间所需存储空间都在内存中分配.,,,,,,,,,,,…… 201 202 203 204 205 206 ……,1.顺序存储（用数组实现）,存储方法,:把逻辑上相邻的结点存储在一组连续的存储单元中,其结点之间的逻辑关

12、系由存储单元地址间的关系隐含表示。,,例：,list,的顺序存储结构如下,a,b,c,d,e,200 201 202 203 204,优点：节省存储空间，可实现对各结点的随机访问。,,,loc（i）＝q＋（i－1）×p,,q,是第一个结点所占存储单元的首地址；,,,p,是每个结点所占单元数。,缺点：不便于修改。进行插入、删除运算时可能要移动一系列的数据元素。,,例：,,若删除,list,结构中的第三个结点,c，,则,list,的逻辑结构变成(,a,b,d,e)。,,,若在结点,c,前插入一个新的结点,x，,则,list,的逻辑结构变成(,a,b,x,c,d,e)。,,,逻辑结构

13、发生变化后，相应的存储结构同样发生变化。,200 201 202 203 204 205,,,,,,,e,b,a,d,200 201 202 203 204 205,,,,,,,c,x,d,e,a,b,2.链接存储(用指针实现,),存储方法,：给每个机结点附加指针字段，用于存放相邻结点的存储地址。,,优点：便于修改 缺点：浪费存储空间,,例：,list （a,b,c,d,e）,的存储结构示意图如下,c,208,b,200,a,202,e,,d,206,200,,202,206,,208,204,200,,202,206,,

14、208,204,,,b,208,a,202,e,,d,206,删除结点,c,后,,(,a,b,d,e),x,200,…,,c,208,b,100,a,202,e,,d,206,200,,202,206,,208,204,100,插入结点,x,后,,（,a,b,x,c,d,e）,3.索引存储（用数组实现）,存储方法,：根据结点的序号确定结点的存储地址。,,具体做法,：建立索引表和结点表；将各结点的数值按任意顺序存放在结点表中，而将每个结点的存储地址用顺序存储方法存入索引表中。,,例：,list （a,b,c,d,e),的索引存储结构如下,200,204,202,201,203,200,204,2

15、01,203,,a,甲,85,d,丁,90,c,丙,67,e,戊,55,b,乙,78,100,,101,,102,,103,,104,200,,201,,202,,203,,204,索引表,结点表,索引表,100,,101,,102,,103,,104,删除结点,c,后,删除结点,c,前后无变化,4.散列存储(用数组实现),存储方法,：根据结点的值确定结点的存储地址。,,具体做法,：以结点中某个字段的值为自变量，通过某个函数（称为散列函数）计算出对应的函数值,i，,再把,i,当作结点的存储地址。,,例：假定,list,结构中的5个结点数值是下列5个字符‘,Wuhan’,‘,Nanjing’,‘

16、,Shanghai’,‘,Xian’,‘,Beijing’,,,散列函数：,Loc(key)=asc(left(key,1)) mod 8,,Key Wuhan Nanjing Shanghai Xian Beijing,,asc(key) 87 78 83 88 66,,Loc(key) 7 6 3 0 2,Xian,,Beijing,Shanghai,,,Nanjing,Wuhan,0 1 2 3

17、4 5 6 7,,,数据的逻辑结构和物理结构是密切相关的两个方面，在后面的课程中我们会看到，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。,完整的数据结构概念可认为是由数据的逻辑结构、存储结构及基本操作集三个部分组成：,,,Data_Structure＝（,D,，,R,，,P,）,,其中,D,是数据元素的有限集合；,R,是,D,集上关系的有限集合，,P,是对,D,的基本操作集。,数据结构研究的内容,数据的逻辑结构,非线性结构,集合,图状结构,有向图,无向图,树形结构,一般树,二叉树,线性结构,一般线性表,线性表

18、推广,广义表,数组,串,受限线性表,栈和队列,,数据逻辑结构层次关系图,,逻辑结构与所采用的存储结构,线性表,树,图,顺序存储结构,链式存储结构,复合存储结构,逻辑结构,物理结构,6.,数据类型,,是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画（程序）,,操作对象的特性。,,,数据类型：,是一组性质相同的,值的集合,及定义于这个值集合上的,一组操作,的总称。,通用的计算机高级语言常见的有,整数、实数（浮点数）、枚举、字符、字符串、指针、数组、记录文件,等数据类型。譬如：,,整数类型通常用两个字节或四个字节表示，分别表示范围：,-2,15,～,2,15,-1,、,-2,31

19、,～,2,31,-1,。,,对其允许施加的操作通常有：单目和双目，分别是,取正,或,取负,运算,；,加、减、乘、除、取模、等于、不等于、大于,等关系（比较）运算,。,依据,“,值,”,的不同特性，高级语言中数据类型可分为两类：,,1,）原子类型,,,原子类型的值是不可分解。,,如：,C,语言中的基本类型（整型、实型、字符型和枚举型），指针型。,,2,）结构类型,,结构类型的值是由若干成分按某种结构组成，因此可以分解，且它的成分可以是非结构的，也可以是结构的。如：数组类型。,7.,抽象数据类型（简称,ADT,）,,指一个,数学模型,及定义在此数学模型上的,一组操作,。,“,抽象,”,的意义在于数

20、据类型的数学抽象特性。,,,为提高软件复用率，近代程序设计方法学指出，一个软件系统的框架应建立在数据之上，而不是操作之上（后者是传统的软件设计方法所为）。即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作细节，而在模块外部使用的只是抽象的数据和操作。,ADT,有两个重要特征,:,,1,）数据抽象,,,用,ADT,描述程序处理的实体时，,强调,的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,,2,）数据封装,,,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,抽象数据类

21、型的描述方法：,,三元组表示（,D,，,S,，,P,）,,其中，,D,是数据对象，,,,S,是,D,上的关系集，,,,P,是对,D,的基本操作集。,ADT,抽象数据类型名,{,,,数据对象：,〈,数据对象的定义,〉,,,数据关系：,〈,数据关系的定义,〉,,,基本操作：,〈,基本操作的定义,〉,,,} ADT,抽象数据类型名,,,其中，数据对象和数据关系的定义用,伪码,描述，,,,基本操作,的定义格式为：,,基本操作名（参数表）,,初始条件：,〈,初始条件描述,〉,,操作结果：,〈,操作结果描述,〉,基本操作有两种参数：,,1,）赋值参数,：,只为操作提供输入值,,2,）引用参数,：,以,&,

22、打头，除可提供输入值外，还,,将返回操作结果。,,“,初始条件,”,描述了操作执行之前数据结构和参,,数应满足的条件，若不满足，则操,,作失败，并返回相应出错信息。,,“,操作结果,”,说明了操作正常完成之后，数据结,,构的变化状况和应返回的结果。若,,初始条件为空，则将其省略。,例：抽象数据类型,——,,复数的定义,,,ADT Complex {,,,数据对象：,D,＝,{e,1,,e,2,｜,e,1,,e,2,∈RealSet },,,数据关系：,R,＝,{ | e,1,是复数的实数部分,,,,,,e,2,是复数的虚数部分,},,,基本操作：,,,InitComple

23、x( &Z, v,1,, v,2,),,,操作结果：构造复数,Z,,其实部和虚部分别被赋,,以参数,v,1,和,v,2,的值。,,,DestroyComplex( &Z),,操作结果：复数,Z,被销毁。,,GetReal( Z, &realPart ),,初始条件：复数已存在。,,操作结果：用,realPart,返回复数,Z,的实部值。,,,GetImag( Z, &ImaPart ),,初始条件：复数已存在。,,操作结果：用,ImgPart,返回复数,Z,的虚部值。,,,Add( z,1,,z,2,, &sum ),,初始条件：,z,1,,z,2,是复数。,,操作结果：用,sum,返回两个复

24、数,z,1,,z,2,的和值。,,} ADT Complex,第,1,章 绪论,,1.1,什么是数据结构,,1.2,基本概念和术语,,,1.3,抽象数据类型的表示与实现,,1.4,算法和算法分析,抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。,,本课程在高级程序设计语言的虚拟层次上讨论抽象数据类型的表示和实现，采用介于,伪码和Ｃ语言之间的类Ｃ语言,作为描述工具，下面我们对其作一下简要说明。,（,1,）预定义常量和类型：,,,#define TRUE 1,,#define FALSE 0,,#define

25、 OK 1,,#define ERROR 0,,#define INFEASIBLE -1,,#define OVERFLOW -2,,Typedef int status,,,// status,是函数的类型，,,,//,其值是函数结果状态代码,（,2,）数据结构的表示（存储结构）,,,用类型定义（,typedef,）描述。,,数据元素类型约定为,ElemType,，由用户在使用该数据类型时自行定义。,,（,3,）基本操作的算法,,,用以下形式的函数描述：,,函数类型 函数名（函数参数表）,,,{ //,算法说明,,语句序列,,,} //,函数名

26、,,说明：,,,除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。,,当函数返回值为函数结果状态码时，函数定义为,status,类型。,为了便于算法描述，除了值调用方式之外，增添了,C++,语言的引用调用的参数传递方式。在形参表中，以,&,打头的参数即为引用参数。,（,4,）赋值语句,,,简单赋值,变量名,=,表达式；,,,串联赋值,,变量名,1=,变量名,2=,…,变量名,K=,表达式；,,,成组赋值,,（变量名,1,，变量名,2,，,…,变量名,K,）,=,,,（表达式,1,，表达式,2,，,…,表达式,K,）；,,结构名,=,结构名；,,结构名,

27、=,（值,1,，值,2,，,…,，值,K,） ；,,变量名,[ ]=,表达式；,,变量名,[,起始下标,..,终止下标,]=,,,变量名,[,起始下标,..,终止下标,],；,,,交换赋值,变量名,←→,变量名；,,,条件赋值,,,变量名,=,条件表达式？表达式,T,：表达式,F,；,（,5,）选择语句,,,条件语句,1,if,（表达式）语句；,,,条件语句,2,,if,（表达式）语句,;,,else,语句；,,开关语句,1,,,switch,（表达式）,{,,case,值,1:,语句序列,1,；,break,；,,,…,,case,值,n:,语句序列,n,；,break,；,,,defaul

28、t:,语句序列,n+1,；,},,,开关语句,2,,,switch{,,case,条件,1:,语句序列,1,；,break,；,,,…,,case,条件,n:,语句序列,n,；,break,；,,,default:,语句序列,n+1,；,},（,6,）循环语句,,,For,语句,,,for,（赋初值表达式序列；条件；,,修改表达式序列）,,语句序列；,,,While,语句,,while,（条件）语句序列；,,,,Do-While,语句,,do {,语句序列；,,,} while,（条件）,（,7,）结束语句,,,函数结束语句,,return,表达式；,,,return,；,,,Case,结束

29、语句,,break,；,,,异常结束语句,,exit,（异常代码）；,（,8,）输入输出语句,,,输入语句,,,scanf,（,[,格式串,],，变量,1,，,…,，变量,n,）；,,,输出语句,,,printf,（,[,格式串,],，表达式,1,，,…,，表达式,n,）；,,通常省略格式串。,（,9,）注释,,,单行注释,,//,文字序列；,,（,10,）逻辑运算约定,,,与运算,&&,,：,,,如：,A&&B,，当,A,的值为,0,时，不再对,B,求值。,,,或运算,||,：,,如：,A||B,，当,A,的值为非,0,时，不再对,B,求值。,（,11,）基本函数,,,求最大值,,max,（

30、表达式,1,，,…,，表达式,n,）；,,,求最小值,,min,（表达式,1,，,…,，表达式,n,）；,,,求绝对值,,abs,（表达式）；,,,求不足整数值,,floor,（表达式）；,,,求进位整数值,,ceil,（表达式）；,,,判定文件结束,,eof,（文件变量）或,eof,；,,,判定行结束,,eoln,（文件变量）或,eoln,第,1,章 绪论,,1.1,什么是数据结构,,1.2,基本概念和术语,,1.3,抽象数据类型的表示与实现,,,1.4,算法和算法分析,1.,算法定义,,,算法,(Algorithm ),是对特定问题求解步骤的一种描述，是为解决一个或一类问题给出的一个确定的

31、、有限长的操作序列。,,计算机对数据的操作可分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等。,,2.,设计算法的基本过程,,1),通过对问题进行详细地分析，抽象出相应的数学模型；,,2),确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；,,3),选用某种语言将算法转换成程序；,,4),调试并运行这些程序。,,1,）,有穷性,：对任何合法输入值，算法总是,在有穷步内结束，且每一步都可在有穷的时间内完成；,,2,）,确定性,：每条指令有确切的含义，不会产生二义性 ；只有一条执行路径，即对于相同的输入，只能

32、得到相同的输出；,,3,）,可行性,：算法中的操作都可以通过已实现的基本运算执行有限次来实现；,,4,）,有输入,：有零个或多个输入；,,5,）,有输出,：有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。,3.,算法的重要特性,1,）,正确性：,算法应当满足具体问题的需求。,,,“,正确,”,一词的含义在通常的用法中有很大差别，大体可分,4,层次：,,a.,程序不含语法错误；,,b.,程序对于几组输入数据能够得出满足规格说明要求的结果；,,,,c.,程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能得出满足规格说明要求的结果；通常以此作为衡量一个程序是否正确的标准；,,d.

33、,程序对于一切合法的输入数据都能产生满足规格说明要求的结果。,4.,算法设计的要求,2,）,可读性：,为了便于理解、测试和修改算法，算法应该具有良好的可读性。,,3,）,健壮性：,当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。,,4,）,高效率与低存储量需求：,,通俗地说，效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。,4.,算法设计的要求,5.,一般书写算法的,4,种形式：,,1,）条列式的步骤,,以条列式的步骤来描述解决问题

34、的方法,,2,）流程图,/,可读性,,以图形符号来描述解决问题的方法。,,3,）伪码,,,以夹杂程序语法和自然语言（如：中文、英文）的形式描述解决问题的方法。,,4,）程序语句,,,直接以程序语法来描述解决问题的方法。,6.,算法效率的衡量方法和准则,,,事后统计法,,计算机内部都有计时功能，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。,,缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此常采用事前分析估算法。,,,事前分析估算法,与算法执行时间相关的因素：,,,1,．算法选用的策略,,2,．问题的规模

35、,,3,．编写程序的语言,,4,．编译程序产生的机器代码的质量,,5,．计算机执行指令的速度,,显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。这表明使用绝对的时间单位衡量算法的效率是不合适的。,一个特定算法的,“,运行工作量,”,的大小，只依赖于问题的规模（通常用整数量,n,表示），或者说，它是问题规模的函数。,,假如，随着问题规模,n,的增长，算法执行时间的增长率和,f,（,n,）的增长率相同，则可记作：,,,T,（,n,）,= O,（,f,（,n,））,,称,T,（,n,）为算法的,(,渐近,),时间复杂度,一个特定算法的“运行工

36、作量”的大小，只依赖于问题的规模（通常用整数量,n,表示），或者说，它是问题规模的函数。,,一个算法的执行时间可以看成是所有语句的执行时间之和,T =,∑,(,语句,(i),的执行次数,×,语句的执行时间,),,假设每条语句执行的时间相等,,,算法的语句频度,f(n):,算法中基本操作重复执行的次数之和。,,算法的渐近时间复杂度,T,（,n,）,= O( f(n) ),这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。,,,渐近时间复杂度,（,Asymptotic Time Complexity,）,如何估算算法的时间复杂度？,,算法,=,控制结构,+,原操作（固有数据类,,型的操

37、作）,,算法的执行时间,=,原操作,(i),的执行次数,,,×,原操作,(i),的执行时间,,,算法的执行时间与原操作执行次数之和成正比,所以,,,从算法中选取一种对于所研究的问题来说是基本操作的原操作，以,该基本操作在算法中重复执行的次数,作为,算法运行时间的衡量准则,。,,一般地，常用,最深层循环内,的语句中的原操作的,执行频度,(,重复执行的次数,),来表示。,例一,,矩阵相乘,,,,,for (i=1,；,i<=n,；,++i),,for (j=1,；,j<=n,；,++j),,{,,c[i,，,j] = 0,；,,,for (k=1,；,k<=n,；,++k),,c[i,，,j] +

38、= a[i,，,k] × b[k,，,j],；,,,},,基本操作,:,乘法操作 ，时间复杂度,: O,（,n,3,）,例二,,void select_sort( int a[ ], int n),,{,//,将,a,中整数序列重新排列成自小至大有序的整数序列,,,for ( i = 0; i< n-1; ++i ),,{,,j = i;,,for ( k = i+1; k < n; ++k ),,if (a[k] < a[j] ) j = k;,,if ( j != i ) a[j] ←→ a[i],,},,} // select_sort,,基本操作,:,比较操作；时间复杂度,: O(n,

39、2,),,例三,,,,,void bubble_sort(int a[ ], int n),,{,//,将,a,中整数序列重新排列成自小至大有序的整数序列,,,for (i=n-1, change=TRUE; i>1 --i),,{,,change = FALSE;,,for (j=0; j a[j+1]),,{ a[j] ←→ a[j+1];,,change = TRUE,,},,},,} // bubble_sort,,基本操作,:,赋值操作；时间复杂度,: O,（,n,2,）,定理,：若,A(n)=a,m,n,m,+a,m-1,n,m-1,+

40、…+a,1,n+a,0,是一个,m,次多项式，则,A(n)=O(n,m,),,如果算法的执行时间,T(n),与问题规模,n,无关，是个常数，则记作,T(n)=O(1)。,,例,{++x; s=0 ;},,,将,x,自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ,(1),。,,以下六种计算算法时间的多项式是最常用的。其关系为：,,,O(1)

41、的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。,算法的存储空间需求,,空间复杂度,(,Space complexity,),：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。,记作：,S(n) = O(g(n)),,其中：,n,为问题的规模,(,或大小,),,表示随着问题规模,n,的增大，算法运行所需存储量的增长率与,g(n),的增长率相同。,,算法的存储量包括,:,,,1,．输入数据所占空间,,,2,．程序本身所占空间,,,3,．辅助变量所占空间,例：1.,sum=0;,,for(j=1

42、;j<=n;j++),,sum=sum+j;,,printf(“%d”,sum);,T(n)=O(f(n))=O(2n+3)=O(n),1,,n+1,,n,,1,2. Sum=0;,,for(I=1;I<=n;I++),,for(j=1;j<=n;j++),,sum=sum+I*j;,,Printf(“%d”,sum);,1,,n+1,,,n(n+1),,n,2,,1,T(n)=O(f(n))=O(2n,2,+2n+3)=O(n,2,),3. x=n;y=0;,,while(x>=(y+1)*(y+1)),,y++;,T(n)=O(n,½,),4. x=n;,,for(j=1;j<=1

43、00;j++),,x=x+j;,T(n)=O(1),若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的,额外空间,。,,若所需额外空间相对于输入数据量来说是常数，则称,此算法为原地工作,。,,若所需存储量依赖于特定的输入，则通常按,最坏情况,考虑。,本章小结,1.,概念和术语,,数据 数据元素 数据对象 数据结构 逻辑结构 存储结构 抽象数据类型 算法,,2.,数据结构的研究目的和研究内容  目的：寻求有效地组织和处理非数值数据的理论、技术和方法。,,内容：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。,,3.,逻辑结构的四种基本形态,,集合结

44、构、线性结构、树形结构、图状结构,本章小结,4.,数据存储结构的基本组织方式,,顺序、链式,,5.,数据结构引入,ADT,概念的优点  运用,ADT,的概念实际上是将数据结构的讨论分成两部分：一是其概念所涵盖的数据逻辑结构的说明和运算的定义，突出的是在某种关系的数据对象上可以做什么；一是在计算机中如何存储这些数据并具体实现定义的运算，解决怎样做的问题。它和面向对象方法的思想是一致的。,本章小结,6.,算法的五个重要特性,,确定性、有穷性、可行性、输入、输出,,7.,评价算法优劣的基本标准,,正确性、可读性、健壮性、效率与低存储量,,8.,算法分析的目的,,主要是考察算法的时间和空间效率

45、，以求改进算法或对不同的算法进行比较。一般情况下，鉴于运算空间（内存）比较充足，所以把算法的时间复杂度作为分析的重点。,,9.,算法的时间复杂度、空间复杂度,习 题 一,1,简要回答术语：数据，数据元素，数据结构，数据类型。,,2,数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？,,3,数据结构的主要运算包括哪些？,,4,算法分析的目的是什么？算法分析的主要方面是什么？,,5,分析以下程序段的时间复杂度，请说明分析的理由或原因。,,作业,6,.设数据逻辑结构的二元组表示为,s=(D,R),,其中,,,D＝{a,b,c,d,e,f},,R={,,,,},,,试画出这个逻辑结

46、构的示意图及类别。,,7,.求下列算法的时间复杂度及注释语句的频度,⑴,,k=0;,,for(i=1;i<=n;i++),,for(j=i;j<=n;j++),,k++;//,（,2,）,,,for(i=1;i<=n;i++),,for(j=1;j<=n;j++),,{ c[i][j]=0;,,for(k=1;k<=n;k++),,c[i][j]+=a[i][k]*b[k][j];//,,},(3),,Sum1( int n ),,{ int p=1, sum=0, m ;,,for (m=1; m<=n; m++),,{ p*=m ; sum+=p ; },,return (sum)

47、 ;,,},(4),,Sum2( int n ),,{ int sum=0, m, t ;,,for (m=1; m<=n; m++),,{ p=1 ;,,for (t=1; t<=m; t++) p*=t ;,,sum+=p ;,,},,return (sum) ;,,},i=1;,,k=0;,,while(i<=n-1),,{ k=k+10*i;//,,i++; },,i=1;,,j=0;,,while(i+j<=n),,if(i>j) j++;//,,else i++;,,3.,设一维数组,V,中存有,n,个整数，,,（1）写一个算法，将数组中的非零元素移到前面来，零元

48、素移到后面去，各非零元素间的相对位置不变；,,（2）分析所写算法的时间复杂度。,,1,、不是井里没有水，而是你挖的不够深。不是成功来得慢，而是你努力的不够多。,,,2,、孤单一人的时间使自己变得优秀，给来的人一个惊喜，也给自己一个好的交代。,,,3,、命运给你一个比别人低的起点是想告诉你，让你用你的一生去奋斗出一个绝地反击的故事，所以有什么理由不努力,!,,,4,、心中没有过分的贪求，自然苦就少。口里不说多余的话，自然祸就少。腹内的食物能减少，自然病就少。思绪中没有过分欲，自然忧就少。大悲是无泪的，同样大悟无言。缘来尽量要惜，缘尽就放。人生本来就空，对人家笑笑，对自己笑笑，笑着看天下，看日出日

49、落，花谢花开，岂不自在，哪里来的尘埃,!,,,5,、心情就像衣服，脏了就拿去洗洗，晒晒，阳光自然就会蔓延开来。阳光那么好，何必自寻烦恼，过好每一个当下，一万个美丽的未来抵不过一个温暖的现在。,,,6,、无论你正遭遇着什么，你都要从落魄中站起来重振旗鼓，要继续保持热忱，要继续保持微笑，就像从未受伤过一样。,,,7,、生命的美丽，永远展现在她的进取之中,;,就像大树的美丽，是展现在它负势向上高耸入云的蓬勃生机中,;,像雄鹰的美丽，是展现在它搏风击雨如苍天之魂的翱翔中,;,像江河的美丽，是展现在它波涛汹涌一泻千里的奔流中。,,,8,、有些事，不可避免地发生，阴晴圆缺皆有规律，我们只能坦然地接受,;,

50、有些事，只要你愿意努力，矢志不渝地付出，就能慢慢改变它的轨迹。,,,9,、与其埋怨世界，不如改变自己。管好自己的心，做好自己的事，比什么都强。人生无完美，曲折亦风景。别把失去看得过重，放弃是另一种拥有,;,不要经常艳羡他人，人做到了，心悟到了，相信属于你的风景就在下一个拐弯处。,,,10,、有些事想开了，你就会明白，在世上，你就是你，你痛痛你自己，你累累你自己，就算有人同情你，那又怎样，最后收拾残局的还是要靠你自己。,,,11,、人生的某些障碍，你是逃不掉的。与其费尽周折绕过去，不如勇敢地攀登，或许这会铸就你人生的高点。,,,12,、有些压力总是得自己扛过去，说出来就成了充满负能量的抱怨。寻求

51、安慰也无济于事，还徒增了别人的烦恼。,,,13,、认识到我们的所见所闻都是假象，认识到此生都是虚幻，我们才能真正认识到佛法的真相。钱多了会压死你，你承受得了吗,?,带，带不走，放，放不下。时时刻刻发悲心，饶益众生为他人。,,,14,、梦想总是跑在我的前面。努力追寻它们，为了那一瞬间的同步，这就是动人的生命奇迹。,,,15,、懒惰不会让你一下子跌倒，但会在不知不觉中减少你的收获,;,勤奋也不会让你一夜成功，但会在不知不觉中积累你的成果。人生需要挑战，更需要坚持和勤奋,!,,,16,、人生在世：可以缺钱，但不能缺德,;,可以失言，但不能失信,;,可以倒下，但不能跪下,;,可以求名，但不能盗名,;,可以低落，但不能堕落,;,可以放松，但不能放纵,;,可以虚荣，但不能虚伪,;,可以平凡，但不能平庸,;,可以浪漫，但不能浪荡,;,可以生气，但不能生事。,,,17,、人生没有笔直路，当你感到迷茫、失落时，找几部这种充满正能量的电影，坐下来静静欣赏，去发现生命中真正重要的东西。,,,18,、在人生的舞台上，当有人愿意在台下陪你度过无数个没有未来的夜时，你就更想展现精彩绝伦的自己。但愿每个被努力支撑的灵魂能吸引更多的人同行。,