数据结构课件ppt第一章.ppt

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

1、数据结构,谭艺枝 E-mail ：,第一章 绪 论,1.1 数据结构讨论的范畴,1.2 基本概念,1.3 算法和算法的量度,1.1 数据结构讨论的范畴,Niklaus Wirth： Algorithm + Data Structures = Programs,程序设计: 算法: 数据结构:,为计算机处理问题编制 一组指令集,处理问题的策略,问题的数学模型,求一组(n个)整数中的最大值,算法: ? 模型：？,基本操作是“比较两个数的大小”,取决于整数值的范围,非数值计算的程序设计问题,例一: 求一组(n个)整数中的最大值,算法: ? 模型：？,基本操作是“比较两个数的大小”,取决于整数值的范围,

2、游戏设计中的数据结构应用示例,树结构在游戏设计中的应用,算法: ? 模型：？,游戏规则,树型结构,概括地说：,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,1.2 基本概念,一、数据与数据结构,二、数据类型,三、抽象数据类型,一、数据与数据结构,所有能被输入到计算机中，且能被计算机处理的符号的集合。,数据:,是计算机操作的对象的总称,是计算机处理的信息的某种特定的符号表示形式。是计算机化的信息。,是数据（集合）中的一个“个体”,数据元素:,是数据结构中讨论的基本单位,数据项：,是数据结构中讨论的最小单位,数据元素可以是数据项的集合,

3、例如：,描述一个运动员的数据元素可以是,称之为组合项,数据项,数据对象：,性质相同的数据元素的集合。是数据的一个子集。,整数数据对象是集合N=0， 1， 2， ， 字母字符数据对象是集合C=A，B，Z,学籍表,数据项,学籍表也可看作一个数据对象。 由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同， 都是同一个数据对象。,综上所述，再分析数据概念：,一、数据特点： 1.可放入机器（与机器的关联性） 2.可被加工（能被处理） 二、数据构成： 1.数据元素：组成数据的基本单位（与数据的关系是 集合与个体） 2.数据对象

4、：性质相同的数据元素的集合（与数据的 关系是集合与子集）,数据结构：相互之间存在一种或多种特定关系的数据元素的集合。,结构：数据元素不是孤立存在的，它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。,学校组织层次结构图,数据结构：,带结构的数据元素的集合,假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。,3214,6587,9345 a1(3214),a2(6587),a3(9345),则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3,3214，6587，9345 a1 a2 a3,6587，3214，9345 a2 a1 a3,例如:

5、,或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,可见，不同的“关系”构成不同的“结构”,数据结构一般包括以下三个方面的内容： 数据的逻辑结构：数据元素之间的逻辑关系。 数据的存储结构：数据元素及其关系在计算机存储器内的表示。 数据的运算：对数据施加的操作。 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。,数据的逻辑结构,从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。分为两大类： 线性结构：若结构是非空集，则有且仅有一个开始节点和一个终端节点，并且所有节点最多只有一个直接前驱和直接

6、后继。如线性表是一个线性结构。 非线性结构：一个节点可能有多个直接前驱和直接后继。如树和图都是非线性结构。,数据的逻辑结构可归结为以下四类基本结构:,线性结构,树形结构,图状结构,集合结构,(1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。 (2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。 (3) 树形结构：结构中的数据元素之间存在着一对多的层次关系。 (4) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。,逻辑结构,线性结构线性表、栈、队、字符串、数组、广义表 非线性结构树、 图,数据结构的形式定义为:,数据结构是一个二元组,D

7、ata_Structures = (D, S),其中:D 是数据元素的有限集， S 是 D上关系的有限集。,数据的存储结构（物理结构）, 逻辑结构在计算机存储器中的映象（表示），是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。,逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。,数据元素的映象方法：,用二进制位(bit)的位串表示数据元素,(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,位：计算机中表

8、示信息的最小单位是二进制数的一位。 位串：由若干位组合起来形成位串，用来表示数据元素。 用一个字长的位串表示一个整数，用8位二进制数表示一个字符。,数据元素的映象,数据元素在计算机中用位串来表示，称该位串为元素或结点，即元素或结点是数据元素在计算机中的映象。 数据元素由若干个数据项组成时，位串中对应于各个数据项的子位串称为数据域。,关系的映象方法：,（表示x, y的方法）,顺序映象：以数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。,整个存储结构中只含数据元素本身的信息,链式映象,以附加信息(指针)表示数据元素之间的逻辑关系,需要用一个和 x 在一起的附加信息指示 y 的存储位置,y

9、 x,指针：指示元素的存储地址。,二、数据类型,在用高级程序语言编写的程序中，必须对程序中出现的每个变量、 常量或表达式，明确说明它们所 属的数据类型。,例如，C 语言中提供的基本数据类型有:,整型 int,浮点型 float,字符型 char,逻辑型 bool （ C+语言）,双精度型 double,实型（ C+语言）,数据类型这个概念最早出现在高级程序设计语言中。 高级程序设计语言引入整数、浮点数、双精度数、字符等，对计算机硬件来说是一种新的数据结构。 计算机硬件系统不能直接处理如整数、浮点数、双精度数、字符等，需按一定规则把它们转换成二进制码来表示和处理。计算机能处理的数据类型只包括位、

10、字节和字。 计算机硬件对这些数据类型的操作通过编译器转化为机器语言的位、字节和字这些能接受的数据类型来实现操作。 从高级程序设计语言使用者的角度看，数据类型实现了信息的屏蔽，将一切使用者不必了解的实现细节都封装在数据类型之中，实现了数据的抽象。,高级程序设计语言使用者在使用整数时，不需要了解整数在计算机内部是如何表示，整数运算是如何实现的。 如 int x=5, y=6, z; z=x+y; 高级程序设计语言使用者只需要了解数学上整数求和的抽象操作含义，不需要了解其硬件的“位”操作如何进行。,一种数据类型显式或隐式地规定了这种数据类型变量、常量或表达式的取值范围和它们允许进行的操作集合。 如C

11、语言中的整型变量，有int，short int，long int三种类型，各类型的取值范围不同，且视具体的计算机系统而定。在微机上，int和short都是16位，long是32位；在VAX750上，short16位，int和long都是32位。 数据类型不同，在其上的操作也各不相同。,三、抽象数据类型 (Abstract Data Type 简称ADT),是指一个数学模型以及定义在此数学模型上的一组操作。,抽象数据类型,抽象数据类型（ADT）是用户在数据类型基础上自己定义和实现的数据类型。 类似于在计算机机器语言的位、字节和字的基础上引入整数、浮点数、双精度数、字符等数据类型，高级程序设计语言

12、使用者可以在高级程序设计语言整数、浮点数、双精度数、字符等数据类型的基础上引入各种新的数据类型供自己或他人使用，从而使自己或他人的程序编制达到更高一级的数据抽象。 由用户自己定义和实现的新的数据类型称为抽象数据类型。 每种抽象数据类型都要有确切的数据元素集合的定义和所允许的操作集合的定义。,ADT 有两个重要特征:,数据抽象,用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,抽象数据类型的描述方法,抽象数据类型可用（D，S，P）三元组表示。 其中

13、：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,其中基本操作的定义格式为:,基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述,赋值参数 只为操作提供输入值。 引用参数 以&打头，除可提供输入值外， 还将返回操作结果。,初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。,例如，抽象数

14、据类型复数的定义：,数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复数的实数部分 | e2 是复数的虚数部分 ,ADT Complex ,基本操作：,AssignComplex( &Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。,DestroyComplex( &Z) 操作结果：复数Z被销毁。,GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。,GetImag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPa

15、rt返回复数Z的虚部值。,Add( z1,z2, &sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的 和值。, ADT Complex,假设:z1和z2是上述定义的复数,则 Add(z1, z2, z3) 操作的结果,z3 = z1 + z2,即为用户求的结果,抽象数据类型的表示和实现,抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。,例如，以下为复数的表示和实现。,typedef struct float realpart； float imagpart； complex；,/ -存储结构的定义,/ -基本操作的函数原型说明

16、,void Assign( complex &Z, float realval, float imagval )； / 构造复数 Z,其实部和虚部分别被赋以参数 / realval 和 imagval 的值,float GetReal( cpmplex Z )； / 返回复数 Z 的实部值,float Getimag( cpmplex Z )； / 返回复数 Z 的虚部值,void add( complex z1, complex z2, complex &sum )； / 以 sum 返回两个复数 z1, z2 的和,/ -基本操作的实现,void add( complex z1, comp

17、lex z2, complex , 其它省略 ,课堂练习,研究数据结构就是研究（ ） A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其数据在运算上的实现,答案：D,2. 数据的（ ）包括集合、栈、树和图结构4种基本类型。 A. 存储结构 B. 逻辑结构 C. 基本运算 D. 算法描述,答案：B,3.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ） 存储结构 存储实现 逻辑结构 运算实现。,答案：C,4. 数据的（ ）包括查找、插入、删除、更新、排序等操作类型。 存储结构 逻辑结构 基本运算 算法描述,答案：C,判断题 1.数据元素是数据的最小单位。 2.数据结构是带有结构的数据元素的集合。 3.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据需要而建立的。 4.数据的物理结构是指数据在计算机内实际的存储形式。,答案：1.F 2.T 3.T 4.T,