数据结构与算法分析课件.ppt

1、数据结构与算法分析 主讲教师主讲教师 董洁董洁第一章第一章 绪论绪论知识点知识点2 ： 基本概念和术语基本概念和术语一、基本概念一、基本概念数据数据n数据数据(Data)：信息的符号表示。在计算机科学中是指所信息的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。有能输入到计算机中并被计算机程序处理的符号的总称。 例如：文字处理程序处理的字符，数值分析程序处理的整数和实数，所有计算机程序加工的原料都称为数据，含义非常含义非常广泛广泛，可以是编码后的图像、声音等。一、基本概念一、基本概念数据元素数据元素n数据元素数据元素(Data Element)：是数据的基本单位

2、，是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 例如：通讯录中的每一条信息，人机对弈程序中的棋局，地图中的每一个城市，这些都是数据元素。 一个数据元素可由若干个数据项（一个数据元素可由若干个数据项（Data Item）组成）组成。数数据项是数据的不可分割的最小单位。据项是数据的不可分割的最小单位。 例如：书目中的每一项，如书名、作者名等，都是数据项。图书信息表：图书信息表：数据、数据元素、数据项及其关系数据、数据元素、数据项及其关系数据元素数据元素数据项数据项数据数据一、基本概念一、基本概念数据对象数据对象n数据对象数据对象(Data Object)：是性质相同的数据元素的

3、集合。是数据的一个子集。 例如：整数的数据对象是-3，-2，-1，0，1，2，3，；英文字符类型的数据对象是A，B，C，D，E，F，二、数据结构（重点二、数据结构（重点） 数据结构数据结构(Data Structure)：是相互之间存在一种或多种特是相互之间存在一种或多种特定关系的数据元素的集合。定关系的数据元素的集合。 主要指：主要指：n 逻辑结构逻辑结构n 物理结构物理结构 本书采用本书采用抽象数据类型抽象数据类型来描述数据结构。来描述数据结构。进一步明确数据结构的研究内容：进一步明确数据结构的研究内容： 1、逻辑结构、逻辑结构基本结构基本结构 逻辑结构逻辑结构：数据元素之间存在的关系数据

4、元素之间存在的关系。有以下。有以下4类基本结类基本结构：构： 集合集合：同属于一种类型。：同属于一种类型。线性结构线性结构：一对一。如线性表、栈、队列：一对一。如线性表、栈、队列树型结构树型结构：一对多。如树：一对多。如树图状结构或网状结构图状结构或网状结构：多对多。：多对多。逻辑结构逻辑结构描述形式描述形式 数据结构的形式定义为：数据结构是一个二元组：数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) D是数据元素的有限集，是数据元素的有限集，S是是D上关系的有限集上关系的有限集。 如：已知逻辑结构linear=(D,R) 其中： D=1,2,3,4,5

5、R=, 则其逻辑图为： 12345练习：练习： 已知一个逻辑结构已知一个逻辑结构 t=(D,R) 其中：其中： D=a,b,c,e,f,g,h R=,判断其属于哪种类型的逻辑结构。判断其属于哪种类型的逻辑结构。abcefgh分析其逻辑图为：分析其逻辑图为：树型结构树型结构返回物理结构物理结构定义与分类定义与分类 物理结构物理结构：数据结构在计算机中的表示，又称为存储结构，数据结构在计算机中的表示，又称为存储结构，可根据在计算机中的不同表示法主要分为以下两种：可根据在计算机中的不同表示法主要分为以下两种：n顺序存储结构：顺序存储结构：借助元素在存储器中的相对位置来表示数据元借助元素在存储器中的相

6、对位置来表示数据元素间的逻辑关系素间的逻辑关系 顺序映象顺序映象n链式存储结构：链式存储结构：借助指示元素存储地址的指针表示数据元素间借助指示元素存储地址的指针表示数据元素间的逻辑关系的逻辑关系非顺序映象非顺序映象元素元素n n.元素元素i i.元素元素2 2元素元素1 11 2 i n存储序号存储序号存储内容存储内容相对位置表达逻辑顺序相对位置表达逻辑顺序顺序存储顺序存储返回1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4

7、4 . . . . . 14001400 元素元素2 2 15361536 . . . . . 15361536 元素元素3 3 13461346 链式存储链式存储 ：额外增加指针域表示逻辑关系额外增加指针域表示逻辑关系h返回数据结构小结：数据结构小结： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构 n算法设计的选取取决于数据的逻辑结构，算算法设计的选取取决于数据

8、的逻辑结构，算法的实现依赖于采用的存储结构法的实现依赖于采用的存储结构n数据的逻辑结构只是抽象反映数据元素的逻辑关系；数据的逻辑结构只是抽象反映数据元素的逻辑关系；n数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现。数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现。三、数据类型和抽象数据类型三、数据类型和抽象数据类型定义定义：高级语言中指数据的取值范围及其上可进行的操作高级语言中指数据的取值范围及其上可进行的操作的总称。的总称。 例如，例如，C语言中的整型，值集为某个区间上的整数，定语言中的整型，值集为某个区间上的整数，定义在其上的操作为加、减、乘、除取余数等算术运算。

9、义在其上的操作为加、减、乘、除取余数等算术运算。 数据类型可分为不可再分的数据类型可分为不可再分的原子类型原子类型和若干成分按照某和若干成分按照某种结构组成的种结构组成的结构类型结构类型。1、数据类型、数据类型2、抽象数据类型、抽象数据类型 抽象数据类型抽象数据类型：一个数学模型以及定义在该模型上的一组操作。：一个数学模型以及定义在该模型上的一组操作。 本质：本质：该定义仅取决于逻辑特性，而与内部的表示无关。该定义仅取决于逻辑特性，而与内部的表示无关。实质是实质是数据类型，数据类型，但范畴但范畴更广更广，不再不再局限于已定义并实现的数据类型，局限于已定义并实现的数据类型，还还包括自定义包括自定

10、义的数据类型。的数据类型。抽象数据类型 数学模型数学模型 定义在该模型上的一组操作定义在该模型上的一组操作数据的取值范围数据的取值范围+及其上可进行操作及其上可进行操作抽象数据类型表示方法：抽象数据类型表示方法： ADT 抽象数据类型名抽象数据类型名 数据对象数据对象： 数据关系数据关系： 基本操作基本操作： ADT抽象数据类型名抽象数据类型名 其中：其中：数据对象数据对象和和关系关系的定义用伪代码，的定义用伪代码， 基本操作基本操作的定义格式为：的定义格式为： 基本操作名（参数表）基本操作名（参数表） 初始条件：初始条件： 操作结果操作结果: n基本操作有两种参数：基本操作有两种参数：赋值参

11、数：提供赋值参数：提供输入值；输入值；引用参数：以引用参数：以& &打头，打头， 主要是返回主要是返回操作结果操作结果。n “初始条件初始条件”：执行本操作时数据结构：执行本操作时数据结构和参数应满足的条和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。件，若不满足，则操作失败，并返回相应出错信息。 初始条件初始条件为为空时省略。空时省略。n “操作结果操作结果”：操作完成后：操作完成后，数据结构的变化状况，数据结构的变化状况和返回和返回的的结果。结果。例：抽象数据类型三元组的定义：例：抽象数据类型三元组的定义： 三元组是具有如下特性的数据元素：由三个相同类型的有序数三元组是具有如

12、下特性的数据元素：由三个相同类型的有序数据项组成。据项组成。ADT Triplet 数据对象：数据对象：D=e1，e2，e3|e1，e2，e3 ElemSet (定义了关系运算的某个集合定义了关系运算的某个集合) 数据关系：数据关系：R=e1，e2，=0任意数据元素的集合数据关系R1=| ai-1,ai D,i=2,.,n除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作ListInsert(&L,i,e)ListDelete(&L,i,e)L为线性表，i为位置，e为数据元素。例：线性表抽象数据类型的表示例：线性表抽象数据类型的表示n1）数据类型与抽象数据类型数据类型与抽象数据类型(ADT)的区别的区别