《12 基本概念和术语.ppt》由会员分享，可在线阅读，更多相关《12 基本概念和术语.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章 绪论1.1什么是数据结构什么是数据结构1.2基本概念和术语基本概念和术语1.3抽象数据类型的表示与实现抽象数据类型的表示与实现1.4算法和算法分析算法和算法分析1.2 基本概念和术语一、数据（一、数据（data）数据是对客观事物的符号表示，数据是对客观事物的符号表示，在计算机科学中是指所有能输在计算机科学中是指所有能输入入到计算机中并被计算机程序处到计算机中并被计算机程序处理理的符号的总称。的符号的总称。1.2 基本概念和术语二、数据元素（二、数据元素（data element）数据元素是数据的基本单位，在计算数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑机程序中通常
2、作为一个整体进行考虑和处理。和处理。一个数据元素可由若干个数据项一个数据元素可由若干个数据项（data item）组成。）组成。数据项是数据的不可分割的最小单位。数据项是数据的不可分割的最小单位。1.2 基本概念和术语三、数据对象（三、数据对象（data object）数据对象是性质相同的数据元素的集合，是数数据对象是性质相同的数据元素的集合，是数据的一个据的一个子集。数据对象可以是有限的，也可以是无限子集。数据对象可以是有限的，也可以是无限的。的。1、整数数据对象、整数数据对象:N=0,1,2,2、英文字符类型的数据对象、英文字符类型的数据对象:A，B，C，D，E，F，Z3、书目数据对象：书
3、目表、书目数据对象：书目表 数据、数据元素和数据对象之间的关系：数据、数据元素和数据对象之间的关系：数据数据 数据元素数据元素 数据项数据项1.2 基本概念和术语四、数据结构（四、数据结构（data structure）数据结构是相互之间存在一种或数据结构是相互之间存在一种或多种特定关系的数据元素的集合。多种特定关系的数据元素的集合。数据结构描述：数据结构描述：Data_Structure=(D,S)D 是数据元素的有限集是数据元素的有限集 S 是是D上关系的有限集上关系的有限集 集合集合集合集合元素间为松散的元素间为松散的元素间为松散的元素间为松散的关系关系关系关系线性结构线性结构线性结构线
4、性结构元素间为严格的元素间为严格的元素间为严格的元素间为严格的一对一关系一对一关系一对一关系一对一关系树形结构树形结构树形结构树形结构元素间为严格的元素间为严格的元素间为严格的元素间为严格的一对多关系一对多关系一对多关系一对多关系图状结构图状结构图状结构图状结构（或网状（或网状（或网状（或网状结构）结构）结构）结构）元素间为多对多元素间为多对多元素间为多对多元素间为多对多关系关系关系关系示示示示 例例例例特特特特 征征征征1.2 基本概念和术语例例1-4：复数是一种数据结构：复数是一种数据结构 Complex=(C,R)其中：其中：C是含两个实数的集合是含两个实数的集合c1,c2 ；R=P，而
5、，而P是定义在集合是定义在集合C上的一种关系上的一种关系c1,c2 ，其中有序偶，其中有序偶c1,c2 表示表示c1是复数的实部，是复数的实部，c2是复数的虚部。是复数的虚部。1.2 基本概念和术语例例1-5：学科研究课题小：学科研究课题小组组 Group=(P,R)其中：其中：P=T,G1,G2,Gn,S11,S12,SnmR=R1,R2R1=|i=1,2,3R2=|i=1,2,3,j=1,1.2 基本概念和术语五、数据的物理结构和逻辑五、数据的物理结构和逻辑结构结构1、物理结构：数据结构中数、物理结构：数据结构中数据元素间的关系在存储器中据元素间的关系在存储器中的存储方法（表现和实现）。的
6、存储方法（表现和实现）。1.2 基本概念和术语2、逻辑结构：数据结构描述的元素间的逻辑、逻辑结构：数据结构描述的元素间的逻辑“关系关系”，独立于计算机。，独立于计算机。数据元素间的关系表示：数据元素间的关系表示：1）顺序映象：借助元素在存储器中的相对位）顺序映象：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。置来表示数据元素之间的逻辑关系。2）非顺序映象）非顺序映象：借助指示元素存储地址的：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。指针表示数据元素之间的逻辑关系。1.2 基本概念和术语顺序映象：顺序映象：x和和y存储位置的相对关系表示有存储位置的相对关系表示有序序对对。
7、最简单的方法就是使。最简单的方法就是使y和和x的存储的存储位位置之间差一个常量置之间差一个常量C。例如：例如：(a1,a2,a3)1.2 基本概念和术语链链式式映映象象：x和和y的的存存储储位位置置随随意意，则则需需要要用用一一个个和和x在在一一起起的的附附加加信信息息指指示示y的的存存储储位位置置，这这个个附附加加信信息息和和x绑绑定定在在一一起起，此此时时，两两者者合合在在一一起作为起作为x的存储映象。的存储映象。1.2 基本概念和术语数据的逻辑结构和物理结构的关系：数据的逻辑结构和物理结构的关系：逻辑结构只抽象地描述数据元素逻逻辑结构只抽象地描述数据元素逻辑关辑关 系（简称数据结构）系（
8、简称数据结构）算法的设算法的设计计物理结构是一个逻辑结构映像到计物理结构是一个逻辑结构映像到计算机算机 中所得到的存储表示中所得到的存储表示算法的实算法的实现现1.2 基本概念和术语 数据的逻辑结构按关系分为线性结构（关数据的逻辑结构按关系分为线性结构（关系是线性的）和非线性结构（关系是非线系是线性的）和非线性结构（关系是非线性的）性的）1.2 基本概念和术语六、数据类型六、数据类型1、数据类型是一个值的集合和定义在这个值、数据类型是一个值的集合和定义在这个值集上的一组操作的总称。集上的一组操作的总称。2、高级程序语言中的数据类型可分为两类：、高级程序语言中的数据类型可分为两类：原子类型：整型
9、、实型、字符型等原子类型：整型、实型、字符型等结构类型：由若干成分按某种结构组成的结构类型：由若干成分按某种结构组成的1.2 基本概念和术语七、抽象数据类型（七、抽象数据类型（Abstract Data Type,ADT）1、一个数学模型以及定义在该模型上的、一个数学模型以及定义在该模型上的一组操一组操 作；作；2、三元组表示（、三元组表示（D,S,P）D是数据对象；是数据对象；S是是D上的关系集；上的关系集；P是是D上的基本操作集。上的基本操作集。1.2 基本概念和术语抽象数据类型定义：抽象数据类型定义：ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据关系：数据关系：基本操作：
10、基本操作：ADT 抽象数据类型名抽象数据类型名其中：其中：1）数据对象和数据关系的定义用）数据对象和数据关系的定义用伪码伪码表表示；示；1.2 基本概念和术语基本概念和术语伪码（伪码（Pseudocode）：算法描述语言。）：算法描述语言。使用伪码的目的是为了使被描述的算使用伪码的目的是为了使被描述的算法可以容易以任何一种编程语言实现。法可以容易以任何一种编程语言实现。因此，伪码必须结构清晰，代码简单，因此，伪码必须结构清晰，代码简单，可读性强，并且类似自然语言。可读性强，并且类似自然语言。1.2 基本概念和术语2）基本操作的定义：）基本操作的定义：基本操作名（参数表）基本操作名（参数表）初始
11、条件：初始条件：操作结果：操作结果：基本操作有两种参数：基本操作有两种参数：赋值参数：为操作提供输入值赋值参数：为操作提供输入值 引用参数：以引用参数：以&打头，除提供输入打头，除提供输入值值 外，还将返回操作结外，还将返回操作结果。果。1.2 基本概念和术语初始条件：描述了操作执行之前数据结构初始条件：描述了操作执行之前数据结构和和 参数应满足的条件，若不满足，则操作失参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。败，并返回相应出错信息。操作结果：说明了操作正常完成之后，数操作结果：说明了操作正常完成之后，数据据 结构的变化状况和应返回的结果。结构的变化状况和应返回的结果。若初始条件为空，则省略之。若初始条件为空，则省略之。1.2 基本概念和术语3 3、抽象数据类型三元组的定义抽象数据类型三元组的定义:（P9，例，例1-6）ADT Triplet 数据对象：数据对象：D=e1,e2,e3|e1,e2,e3 ElemSet 数据关系：数据关系：R1=,基本操作：基本操作：InitTriplet(&T,v1,v2,v3)DestroyTriplet(&T)Get(T,i,&e)Put(&T,i,e)ADT T