数据结构第1章资料

1、计算机科学与技术学院计算机科学与技术学院曲立平曲立平Email： Data StructureData StructurePage 22022-6-18 数据结构数据结构主要介绍如何合理地主要介绍如何合理地组织数据组织数据、有效地、有效地存储和处存储和处理数据理数据，正确地，正确地设计算法设计算法以及对以及对算法的分析和评价算法的分析和评价。 数据结构数据结构是计算机科学中一门综合性的是计算机科学中一门综合性的专业基础课专业基础课，它不，它不仅是计算机学科的核心课程，而且已成为其它理工专业的热门选仅是计算机学科的核心课程，而且已成为其它理工专业的热门选修课。修课。 通过本课程的学习，使学生深透

2、地理解数据结构的通过本课程的学习，使学生深透地理解数据结构的逻辑结构逻辑结构和和物理结构物理结构的基本概念以及有关的基本概念以及有关算法算法，培养基本的、良好的程序，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等数据库等课程奠定基础课程奠定基础。Data StructureData StructurePage 32022-6-18q 第第1章章 绪论绪论q 第第2章章-第第5章章 线性数据结构线性数据结构q 第第6章章树形数据结构树形数据结构q 第第7章章图状数据结构图状数据结构q 第第9章章 查找

3、查找q 第第10章章排序排序q 第第12章章 文件结构文件结构Data StructureData StructurePage 42022-6-18q 从数据结构的逻辑结构、存储结构和数据的运算三个方面去从数据结构的逻辑结构、存储结构和数据的运算三个方面去掌握掌握线性表、栈、队列、串、数组、广义表线性表、栈、队列、串、数组、广义表、树树、图图、和、和文文件件等常用的数据结构。等常用的数据结构。q 掌握在各种常用的数据结构上实现的排序和查找掌握在各种常用的数据结构上实现的排序和查找运算运算。q 对算法的时间和空间复杂性有一定的对算法的时间和空间复杂性有一定的分析能力分析能力。q 针对简单的应用问

4、题，应能针对简单的应用问题，应能选择合适的数据结构选择合适的数据结构及设计有效及设计有效的的算法算法解决。解决。Data StructureData StructurePage 52022-6-18学时：课程讲授学时学时：课程讲授学时64 64 Data StructureData StructurePage 62022-6-18q 严蔚敏等著严蔚敏等著 数据结构数据结构 清华大学出版社清华大学出版社q 范策等著范策等著 算法与数据结构算法与数据结构 机械工业出版社机械工业出版社q 李春保李春保 数据结构与习题解析数据结构与习题解析 清华大学出版社清华大学出版社 q 谢楚屏等编著谢楚屏等编著

5、数据结构数据结构 人民邮电出版社人民邮电出版社Data StructureData StructurePage 72022-6-18q 先修课程：高级语言程序设计（先修课程：高级语言程序设计（C C）、离散数学）、离散数学q 后续课程：操作系统、数据库原理等后续课程：操作系统、数据库原理等Data StructureData StructurePage 82022-6-18q 重点和难点重点和难点v重点：了解有关数据结构的各个重点：了解有关数据结构的各个名词和术语的含义名词和术语的含义，以及，以及语句频语句频度和时间复杂度、空间复杂度的估算度和时间复杂度、空间复杂度的估算。v难点：无难点：无q

6、 知识点知识点v数据、数据元素、数据结构、数据类型、抽象数据类型、算法及数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度其设计原则、时间复杂度、空间复杂度Data StructureData StructurePage 92022-6-18用计算机解决一个具体的问题，需要经过以下几个步骤：用计算机解决一个具体的问题，需要经过以下几个步骤：q 从从具体问题抽象出具体问题抽象出一个一个适当的数学模型适当的数学模型；q 设计一个解此设计一个解此数学模型的算法数学模型的算法；q 编出程序编出程序；q 进行进行测试、调整测试、调整直至得到最终解答。直至得到最终解

7、答。寻求数学模型的实质：寻求数学模型的实质： 分析问题，从中分析问题，从中提取操作的对象提取操作的对象，并找出这些，并找出这些操作对象操作对象之间含有的关系之间含有的关系，然后用，然后用数学的语言加以描述数学的语言加以描述。Data StructureData StructurePage 102022-6-18q 很多问题求解最后都转化为求解数学方程或数学方程组。很多问题求解最后都转化为求解数学方程或数学方程组。v在房屋设计或桥梁设计中的在房屋设计或桥梁设计中的结构应力分析计算结构应力分析计算可化解为可化解为线性代数方线性代数方程组求解程组求解的问题，的问题，v天天看到的天天看到的天气预报天气

8、预报，它的数学模型是一个，它的数学模型是一个环流模式方程环流模式方程。v预报人口增长预报人口增长情况的数学模型为情况的数学模型为微分方程微分方程。q 当计算机进入非数值计算领域，特别是用在管理上的时候，当计算机进入非数值计算领域，特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。计算机的操作对象之间的关系就无法用数学方程加以描述了。非数值计算问题的数学模型正是本课程要讨论的数据结构。非数值计算问题的数学模型正是本课程要讨论的数据结构。Data StructureData StructurePage 112022-6-18例如例如登录号：书名：作者名：分类号：出版单位

9、：出版时间：价格：书目卡片Data StructureData StructurePage 122022-6-18例如例如001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表线性的数据结构线性的数据结构Data StructureData StructurePage 132022-6-18.树形的数据结树形的数据结构构Data StructureData StructurePa

10、ge 142022-6-18CEDABABACADBABCBDDADBDCEAEBECEDData StructureData StructurePage 152022-6-18q 瑞士的计算机专家在瑞士的计算机专家在19761976年出版了一本书，书名为年出版了一本书，书名为算法算法+ +数数据结构据结构 = = 程序设计程序设计，它正说明了数据结构在程序设计中的，它正说明了数据结构在程序设计中的作用。作用。q 程序设计的实质即为计算机处理问题编制一组程序设计的实质即为计算机处理问题编制一组 指令指令 ，首先，首先需要解决两个问题：即算法和数据结构。需要解决两个问题：即算法和数据结构。算法即

11、处理问题的算法即处理问题的策略，而数据结构即为问题的数学模型策略，而数据结构即为问题的数学模型。q 简单地说，数据结构是一门讨论简单地说，数据结构是一门讨论 描述现实世界实体的数学模描述现实世界实体的数学模型型( (非数值计算非数值计算) )及其上的操作在计算机中如何表示和实现及其上的操作在计算机中如何表示和实现 的的学科。学科。 2.2.数据结构数据结构课程课程Data StructureData StructurePage 162022-6-18q 数据数据v是指所有是指所有能输入到计算机中并被计算机程序处理的符号的总称能输入到计算机中并被计算机程序处理的符号的总称。v是计算机加工的是计算

12、机加工的“原料原料”。v包括：图像、声音、数值、字符串等。包括：图像、声音、数值、字符串等。q 数据元素数据元素v是是数据的基本单位数据的基本单位。v在计算机程序中通常作为一个整体进行考虑和处理。在计算机程序中通常作为一个整体进行考虑和处理。v例如：例如：5 5，N N，记录记录，格局格局，顶点顶点。q 数据项数据项: :v一个数据元素可由多个数据项组成。一个数据元素可由多个数据项组成。v数据项是数据项是数据的不可分割的最小单位数据的不可分割的最小单位。Data StructureData StructurePage 172022-6-18q 关键字关键字v能能识别一个或多个数据元素的数据项识

13、别一个或多个数据元素的数据项。v若能起唯一识别作用，则称之为若能起唯一识别作用，则称之为 “主主” 关键字，否则称之为关键字，否则称之为 “次次” 关键字。关键字。v例如：例如：记录记录。q 数据对象数据对象v是是性质相同的数据元素的集合性质相同的数据元素的集合。v是数据的一个是数据的一个子集子集。v例如：例如：整数数据对象整数数据对象是集合是集合N=0N=0，1 1，2 2， v字母字符数据对象字母字符数据对象是集合是集合C=“A”C=“A”，“B”B”，“Z”“Z”2 2数据对象、数据结构数据对象、数据结构Data StructureData StructurePage 182022-6-

14、18q 数据结构数据结构v相互之间相互之间存在一种或多种特定关系的数据元素的集合存在一种或多种特定关系的数据元素的集合。v四类基本结构：四类基本结构：集合：集合：数据元素间除数据元素间除“同属于一个集合同属于一个集合”外，外，无其它关系无其它关系。线性结构：线性结构：数据元素间存在数据元素间存在一个对一个一个对一个的关系。的关系。树形结构：树形结构：数据元素间存在数据元素间存在一个对多个一个对多个的关系。的关系。图形结构：图形结构：数据元素间存在数据元素间存在多个对多个多个对多个的关系。的关系。Data StructureData StructurePage 192022-6-18集合集合线性

15、结构线性结构树形结构树形结构图状结构图状结构（网状结构）（网状结构）Data StructureData StructurePage 202022-6-18q 数据结构的形式定义数据结构的形式定义v数据结构是一个二元组数据结构是一个二元组 Data_Structure=(D,S)Data_Structure=(D,S) 其中，其中，D D是数据元素的有限集，是数据元素的有限集，S S是是D D上关系的有限集。上关系的有限集。 例如例如： list=(D,R)list=(D,R) 其中：其中：D=1,2,3,4,5,6,7D=1,2,3,4,5,6,7 R=, R=,图形表示图形表示123456

16、7Data StructureData StructurePage 212022-6-18q逻辑结构逻辑结构v对对数据元素之间存在的逻辑关系的描述数据元素之间存在的逻辑关系的描述；v可以用一个数据元素的集合和定义在此集合上的若干关系表示。可以用一个数据元素的集合和定义在此集合上的若干关系表示。q物理结构（存贮结构）物理结构（存贮结构）v数据数据逻辑结构在计算机中的表示和实现逻辑结构在计算机中的表示和实现。v包含包含数据元素的映象数据元素的映象和和关系的映象关系的映象。数据元素可以用一个数据元素可以用一个“位串位串”表示表示，例如，数值，例如，数值“321”321”可用位可用位串串 101000

17、001 101000001 表示，字母表示，字母“A”A”可用位串可用位串 001000001 001000001 表示。当表示。当数据元素由多个数据项构成时，每个数据项即为表示数据元素的数据元素由多个数据项构成时，每个数据项即为表示数据元素的位串中的一个位串中的一个“子位串子位串”。Data StructureData StructurePage 222022-6-18关系有两种表示方法：关系有两种表示方法：顺序存储结构顺序存储结构 把把逻辑上相邻的结点存储在物理位置上相邻的存储单元逻辑上相邻的结点存储在物理位置上相邻的存储单元 里，里，结点间的逻辑关系由存储单元的邻接关系来体现结点间的逻辑

18、关系由存储单元的邻接关系来体现。 通常顺序存储结构是借助于语言的通常顺序存储结构是借助于语言的数组数组来描述的。来描述的。链式存储结构链式存储结构 不要求逻辑上相邻的结点物理上也相邻，不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑结点间的逻辑 关系是由附加的指针字段表示的。关系是由附加的指针字段表示的。 通常要借助于语言的通常要借助于语言的指针指针类型来描述。类型来描述。Data StructureData StructurePage 232022-6-18元素元素n n.元素元素i i.元素元素2 2元素元素1 1存储内容存储内容LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址

19、存储地址顺序存储结构顺序存储结构Data StructureData StructurePage 242022-6-18 链式存储结构链式存储结构 1536元素元素2 21536元素元素2 21346元素元素3 31346元素元素3 3 元素元素4 4 元素元素4 4存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 . . . . . 14001400 元素元素2 2 15361536 . . . . . 15361536 元素元素3 3 134613461400元素元素1 1h1400元素元素1 1hData

20、StructureData StructurePage 252022-6-18数据的逻辑结构与存储结构密切相关数据的逻辑结构与存储结构密切相关q 算法设计取决于选定的逻辑结构。算法设计取决于选定的逻辑结构。q 算法实现依赖于采用的存储结构。算法实现依赖于采用的存储结构。Data StructureData StructurePage 262022-6-18 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队

21、列队列树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面Data StructureData StructurePage 272022-6-18q数据类型数据类型v是一个值的集合和定义在这个值集上的所有的操作是一个值的集合和定义在这个值集上的所有的操作。如，整型。如，整型。v在用高级程序设计语言编写的程序中，必须对程序中出现的每个在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。变量、常量或表达式，明确说明它们所属的数据类型。v数据类型可分为：数据类型可分为：原子类型原子类型和和结构类型结构类型。原子类型的值是不可分解的，

22、如：整型、实型、字符型。原子类型的值是不可分解的，如：整型、实型、字符型。结构类型的值是由若干成分按某种结构组成的，如：数组、结构类型的值是由若干成分按某种结构组成的，如：数组、结构体。结构体。数据类型可以看成是已经实现了的数据结构。数据类型可以看成是已经实现了的数据结构。Data StructureData StructurePage 282022-6-18q 抽象数据类型抽象数据类型v是指是指一个数学模型一个数学模型以及定义在该模型上的以及定义在该模型上的一组操作一组操作。v抽象数据类型的抽象数据类型的形式定义形式定义：用一个三元组来表示一个抽象数据类型。：用一个三元组来表示一个抽象数据类

23、型。 ADT = ( DADT = ( D，S S，P )P ) 其中：其中：D D 是数据对象，是数据对象， S S 是是 D D 上的关系集，上的关系集， P P 是是 D D 的基本操作集。的基本操作集。Data StructureData StructurePage 292022-6-18ADT ComplexADT Complex 数据对象数据对象：D = e1,e2 | e1,e2D = e1,e2 | e1,e2 RealSet RealSet 数据关系数据关系：R1 = | e1R1 = | e1是复数的实部，是复数的实部，e2e2是复数的虚部是复数的虚部 基本操作基本操作：I

24、nitComplexInitComplex( &Z, v1, v2 )( &Z, v1, v2 )操作结果：构造复数操作结果：构造复数Z Z，其实部和虚部分别被赋以参数，其实部和虚部分别被赋以参数v1v1和和v2v2的值。的值。 DestroyComplexDestroyComplex( &Z)( &Z)初始条件：复数已存在。初始条件：复数已存在。操作结果：复数操作结果：复数Z Z被销毁。被销毁。 GetRealGetReal( Z, &realPart( Z, &realPart ) )初始条件：复数已存在。初始条件：复数已存在。操作结果：用操

25、作结果：用 realPartrealPart 返回复数返回复数Z Z的实部值。的实部值。GetImagGetImag( Z, &ImagPart( Z, &ImagPart ) )初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用 ImagPartImagPart 返回复数返回复数Z Z的虚部值。的虚部值。AddAdd( z1,z2, &sum )( z1,z2, &sum )初始条件：初始条件：z1z1，z2 z2 是复数。是复数。操作结果：用操作结果：用sumsum返回两个复数返回两个复数z1z1，z2z2的和值。的和值。 ADT Comp

26、lexADT ComplexDSPData StructureData StructurePage 302022-6-18ADT ADT 抽象数据类型名抽象数据类型名 数据对象数据对象：数据对象的定义：数据对象的定义数据关系数据关系：数据关系的定义：数据关系的定义基本操作基本操作：基本操作的定义：基本操作的定义 ADTADT 抽象数据类型名抽象数据类型名描述抽象数据类型的形式描述抽象数据类型的形式 数据对象和数据关系的定义用伪码描述。数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式：数据基本操作的定义格式：基本操作名基本操作名（参数表）（参数表）初始条件初始条件：初始条件描述：初始条

27、件描述操作结果操作结果：操作结果描述：操作结果描述Data StructureData StructurePage 312022-6-18q预定义常量和类型预定义常量和类型#define #define TRUETRUE 1 1#define #define FALSEFALSE 0 0#define #define OKOK 1 1#define #define ERRORERROR 0 0#define #define INFEASIBLEINFEASIBLE -1 -1#define #define OVERFLOWOVERFLOW 2 2type inttype int StatusS

28、tatus; ;Data StructureData StructurePage 322022-6-18q 数据结构数据结构v表示（表示（存储结构存储结构）用类型（）用类型（typedeftypedef）定义来描述。）定义来描述。v数据数据元素类型元素类型约定为约定为ElemTypeElemType，由用户在使用时自行定义。，由用户在使用时自行定义。q 基本操作的算法用函数描述基本操作的算法用函数描述函数类型函数类型 函数名（函数参数表）函数名（函数参数表） /算法说明算法说明语句序列语句序列/函数名函数名Data StructureData StructurePage 332022-6-18

29、q 赋值语句赋值语句v简单赋值简单赋值 变量名变量名= =表达式；表达式；v串联赋值串联赋值 变量名变量名1=1=变量名变量名2=2= =变量名变量名k=k=表达式；表达式；v成组赋值成组赋值 ( (变量名变量名1 1，变量名，变量名k)= (k)= (表达式表达式1 1，表达式，表达式k)k)； 结构名结构名= =结构名；结构名； 结构名结构名= (= (值值1 1，值，值k)k)； 变量名变量名=表达式；表达式； 变量名变量名 起始下标起始下标终止下标终止下标=变量名变量名 起始下标起始下标终止下标终止下标 ；v交换赋值交换赋值 变量名变量名变量名；变量名；v条件赋值条件赋值 变量名变量名

30、= =条件表达式？表达式条件表达式？表达式T T：表达式：表达式F F；Data StructureData StructurePage 342022-6-18q 选择语句选择语句v条件语句条件语句1 1 if( if(表达式表达式) ) 语句；语句；v条件语句条件语句2 2 if( if(表达式表达式) ) 语句；语句； else else 语句；语句；v开关语句开关语句1 1 switch( switch(表达式表达式) case case 值值1 1：语句序列：语句序列1 1；break;break; case case 值值n n：语句序列：语句序列n n；break;break; d

31、efault default：语句序列：语句序列n+1;n+1; v开关语句开关语句2 2 switch( switch(表达式表达式) case case 条件条件1 1：语句序列：语句序列1 1；break;break; case case 条件条件n n：语句序列：语句序列n n；break;break; default default：语句序列：语句序列n+1;n+1; Data StructureData StructurePage 352022-6-18q 循环语句循环语句vforfor语句语句 for(for(赋初值表达式序列；条件；修改表达式序列赋初值表达式序列；条件；修改表达

32、式序列) ) 语句；语句；vwhilewhile语句语句while(while(条件条件) )语句；语句；vdo-whiledo-while语句语句 dodo 语句序列；语句序列； while (while (条件条件) )；q 结束语句结束语句v函数结束语句函数结束语句returnreturn表达式；表达式；returnreturn；vcasecase结束语句结束语句breakbreak；v异常结束语句异常结束语句exit(exit(异常代码异常代码) )；Data StructureData StructurePage 362022-6-18q 输入输出语句输入输出语句v输入语句输入语句s

33、canfscanf(格式串格式串 ，变量，变量，变量变量n n) )；v输出语句输出语句printfprintf(格式串格式串 ，表达式，表达式，表达式表达式n n) )；q 注释语句注释语句v单行注释单行注释/文字序列文字序列q 逻辑运算约定逻辑运算约定v与运算与运算& 对于对于A&BA&B，当，当A A的值为时，不再的值为时，不再B B对求值。对求值。 v或运算或运算| 对于对于A|BA|B，当，当A A的值为非时，不再的值为非时，不再B B对求值。对求值。 Data StructureData StructurePage 372022-6-18q 基本函数基本函数

34、v求最大值求最大值max(max(表达式，表达式，表达式表达式n n) )v求最小值求最小值 min(min(表达式，表达式，表达式表达式n n) )v求绝对值求绝对值abs(abs(表达式表达式) )v求不足整数值求不足整数值floor(floor(表达式表达式) )v求进位整数值求进位整数值ceil(ceil(表达式表达式) )v判定文件结束判定文件结束 eofeof( (文件变量文件变量) )或或eofeofv判定行结束判定行结束 elonelon( (文件变量文件变量) )或或eolneolnData StructureData StructurePage 382022-6-18typ

35、edef struct float realpart;float imagpart; complex; / 存储结构的定义/ 基本操作的函数原型说明void Assign( complex &Z, float realval, float imagval );/ 构造复数 Z，其实部和虚部分别被赋以参数 realval 和 imagval 的值void DestroyComplex( complex &Z)/ 销毁复数 Zfloat GetReal( cpmplex Z );/ 返回复数 Z 的实部值float Getimag( cpmplex Z );/ 返回复数 Z 的虚部

36、值void add( complex z1, complex z2, complex &sum );/ 以 sum 返回两个复数 z1，z2 的和/ 基本操作的实现void add( complex z1, complex z2, complex &sum )/ 以 sum 返回两个复数 z1，z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart;Data StructureData StructurePage 392022-6-18q算法（算法（Algo

37、rithmAlgorithm）v是对特定问题是对特定问题求解步骤的一种描述求解步骤的一种描述，它是，它是指令的有限序列指令的有限序列。q算法的特性算法的特性v有穷性有穷性：一个算法必需总是在执行有穷步之后结束，且每一步都可一个算法必需总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。在有穷时间内完成。v确定性确定性：算法中每一条执行都必须有确切的含义，使算法的执行者算法中每一条执行都必须有确切的含义，使算法的执行者或阅读者不会产生二义性。并且在任何条件下，算法都只或阅读者不会产生二义性。并且在任何条件下，算法都只有一条执行路径。有一条执行路径。v可行性可行性：算法中的所有操作都必须足够基

38、本，都可以通过已经实现算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。的基本操作运算有限次实现之。v输入输入：有零个或多个的输入。：有零个或多个的输入。v输出输出：有一个或多个的输出。：有一个或多个的输出。Data StructureData StructurePage 402022-6-18q 算法的描述算法的描述采用采用C C语言语言q 算法的评价算法的评价衡量算法优劣的标准衡量算法优劣的标准v正确性正确性(correctness)(correctness)v可读性可读性(readability)(readability)v健壮性健壮性(robustness)

39、(robustness)v效率与低存储量效率与低存储量Data StructureData StructurePage 412022-6-18q事后统计事后统计v利用利用计算机内记时功能计算机内记时功能。v缺点：缺点：必须先运行依据算法编制的程序；必须先运行依据算法编制的程序；所得时间统计量依赖于硬件、软件等环境因素，掩盖算法所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣本身的优劣q事前分析估计事前分析估计v一个高级语言程序在计算机上运行所消耗的时间取决于：一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法依据的算法选用何种策略选用何种策略问题的规模问题的规模程序语言程

40、序语言编译程序产生机器代码质量编译程序产生机器代码质量机器执行指令速度机器执行指令速度v时间复杂度和空间复杂度时间复杂度和空间复杂度Data StructureData StructurePage 422022-6-18T(n)=O(f(n)q 从算法中选取一种对于所研究的问题来说是从算法中选取一种对于所研究的问题来说是基本操作的原基本操作的原操作操作，以该基本操作，以该基本操作在算法中重复执行的次数作为算法时在算法中重复执行的次数作为算法时间复杂度的依据间复杂度的依据。q 这种衡量效率的办法所得出的不是时间量，而是一种增长这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。趋势的量

41、度。q 它与软硬件环境无关，只暴露算法本身执行效率的优劣。它与软硬件环境无关，只暴露算法本身执行效率的优劣。q 除特别指明外，本书以后章节中讨论的除特别指明外，本书以后章节中讨论的时间复杂度均指最时间复杂度均指最坏情况下的时间复杂度坏情况下的时间复杂度。Data StructureData StructurePage 432022-6-18算法算法 1.11.1void Mult_matrix(int c,int a,int bvoid Mult_matrix(int c,int a,int b，intint n) n)/ a/ a、b b和和c c均为均为n n阶方阵，且阶方阵，且c c是是

42、a a和和b b的乘积的乘积for(i=1; i=n; +i)for(i=1; i=n; +i)for(j=1; j=n; +j) for(j=1; j=n; +j) ci,j=0;ci,j=0;for(k=1; k=n; +k)for(k=1; k=n; +k)ci,j += ai,kci,j += ai,k* *bk,j;bk,j; / Mult_matrix/ Mult_matrix算法的时间复杂度为算法的时间复杂度为O O (n(n3 3) )原操原操作作Data StructureData StructurePage 442022-6-18算法算法 1.21.2void select

43、_sort(int a, intvoid select_sort(int a, int n) n)/ / 将将 a a 中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列for( i=0; in-1; +i ) for( i=0; in-1; +i ) j=i; j=i; for( k=i+1; kn; +k )for( k=i+1; kn; +k )if(akaj) j=k;if(ak1&change; -i) for(i=n-1,change=TRUE; i1&change; -i) change = FALSE;change = FALS

44、E; for(j=0; ji; +j) for(j=0; jaj+1) w=aj; aj=aj+1; if(ajaj+1) w=aj; aj=aj+1; aj+1= w; change = TRUE aj+1= w; change = TRUE / bubble_sort / bubble_sort 算法时间复杂度取决于算法时间复杂度取决于最深循环内包含基本操作的语最深循环内包含基本操作的语句的重复执行次数句的重复执行次数，称语句重复执行的次数为语句的，称语句重复执行的次数为语句的 频频度度 。算法的时间复杂度为算法的时间复杂度为O O ( (n n2 2) )原操原操作作Data Struc

45、tureData StructurePage 462022-6-18q 算法的存储量算法的存储量指的是算法执行过程中所需的最大存储空间。指的是算法执行过程中所需的最大存储空间。v输入数据所占空间输入数据所占空间v程序本身所占空间程序本身所占空间v辅助变量所占空间辅助变量所占空间v若算法所需存储量依赖于特定的输入，则通常按最坏情况考虑。若算法所需存储量依赖于特定的输入，则通常按最坏情况考虑。Data StructureData StructurePage 472022-6-18q 数据数据是计算机操作对象的总称，它是计算机处理的符号的是计算机操作对象的总称，它是计算机处理的符号的集合，集合中的个

46、体为一个数据元素。集合，集合中的个体为一个数据元素。q 数据元素数据元素可以是不可分割的原子，也可以由若干数据项合可以是不可分割的原子，也可以由若干数据项合成，因此在数据结构中讨论的基本单位是数据元素，而最成，因此在数据结构中讨论的基本单位是数据元素，而最小单位是小单位是数据项数据项。q 数据结构数据结构是由若干特性相同的数据元素构成的集合，且在是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分集合上存在一种或多种关系。由关系不同可将数据结构分为四类：为四类：线性结构、树形结构、图状结构和集合结构线性结构、树形结构、图状结构和集合结构。Data Str

47、uctureData StructurePage 482022-6-18q 数据的存储结构是数据逻辑结构在计算机中的映象，由关数据的存储结构是数据逻辑结构在计算机中的映象，由关系的两种映象方法可得到两类存储结构：一类是系的两种映象方法可得到两类存储结构：一类是顺序存储顺序存储结构结构，它以数据元素相对的存储位置表示关系，则存储结，它以数据元素相对的存储位置表示关系，则存储结构中只包含数据元素本身的信息；另一类是构中只包含数据元素本身的信息；另一类是链式存储结构链式存储结构，它以附加的指针信息（后继元素的存储地址）表示关系。它以附加的指针信息（后继元素的存储地址）表示关系。q 抽象数据类型抽象数据类型是一个数学模型以及定义在该模型上的一组是一个数学模型以及定义在该模型上的一组操作。抽象数据类型的三大要素为操作。抽象数据类型的三大要素为数据对象、数据关系和数据对象、数据关系和基本操作基本操作，同时数据抽象和数据封装是抽象数据类型的两，同时数据抽象和数据封装是抽象数据类型的两个重要特性。个重要特性。 Data StructureData StructurePage 492022-6-18q 算法算法是对问题求解的一种描述，是为解决一个或一类