数据结构幻灯片ch1

《数据结构幻灯片ch1》由会员分享，可在线阅读，更多相关《数据结构幻灯片ch1（83页珍藏版）》请在金锄头文库上搜索。

1、1,数据结构,Data,Structure,2,第1章 绪论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析,3,计算机的功能：,处理信息(数据，包括数字、字符、声音、 图形、图像等等),4,计算机是一门研究用计算机进行信息表示和处理的科学。 信息的表示 信息的处理 而信息的表示和组成又直接关系到处理信息的程序的效率。 随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。 因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题

2、。,5,计算机的应用：科学计算非数值计算的处理工作 处理对象：数值数据 数值数据 数据 非数值数据 学习目的：合理组织数据、高效处理数据,计算机的应用由进行各种各样的科学计算 发展为文档处理、数据处理、图像处理、硬件设计、软件设计 等等 。,6,1.1什么是数据结构,对于一个课题，在计算机领域，一般遵循下面的解决原则： 需求分析 总体设计 模块分割 建立数学模型 解数学模型的算法 程序编制 调试 结果 数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法。,7,Niklaus Wirth： Algorithm + Data Structures = Programs 程序设计: 为计算

3、机处理问题编制一组指令集 算法:处理问题的策略 数据结构:问题的数学模型,例: 求一组(n个)整数中的最大值 算法: 基本操作是“比较两个数的大小” 模型：？,8,在应用程序中涉及到各种各样的数据，如何在计算机中组织、存储、传递数据，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，依此实现软件功能。,描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。,eg.数学模型:数学方程、表格、树、图,9,地位： “数据结构”在计算机科学中是一门综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程

4、序设计(特别是非数值性程序设计)的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。,10,1.2基本概念和术语,数据Data： 是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称(数字、字符、声音、图形、图像等等) 。,11,eg.一个个人书库管理程序所要处理的数据为如下所示的表格：,12,数据元素Data Elememt ： 数据的基本单位，在计算机程序中常常作为一个整体进行考虑和处理。 eg.每一行代表一本书，作为一个基本单位，即每一行为一个数据元素，上述表格数据由n个数据元素组成。 数据项Data Item： 一个数

5、据元素由若干个数据项组成。 数据项是数据的不可分割的最小单位。 eg.上述一个数据元素由5个数据项组成。,13,数据对象Data Object： 性质相同的数据元素的集合，是数据的一个子集。 eg.整数的数据对象是，-3，-2，-1，0，1，2，3， 英文字符类型的数据对象是A，B，C，D，E，F，,14,数据结构Data Structure：是相互之间存在一种或多种特定关系的数据元素的集合。 数据元素之间不是相互独立的，他们之间有某种特定的关系，这种数据元素之间的关系，称为“结构” Structure 。,15,四种基本结构(逻辑结构)p5 集合： 元素仅属于同一个集体，没有其他关系。 eg

6、.同班关系 线性结构： 存在一对一 关系，序列相邻，次序关系。 eg.大小关系 树型结构： 存在一对多关系，层次关系。 eg.家族关系 图状结构(网状结构) ： 存在多对多关系，任意性 eg.交通图,16,数据结构的形式定义： 数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 数学描述,即数学模型 eg.复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系。,17,结构中描述的关系是数据元素之间的逻辑关系,因此又称为数据的逻辑结

7、构. 数据的逻辑结构又分为线型结构和非线性结构两大类. 线性结构 数据的逻辑结构 非线性结构,18,对于任意一个逻辑结构S=(D，R)，若aD，bD，(a，b)R，则称a是b的前驱，b是a的后继；若某结点没有前驱，则称该结点为开始结点；若某结点没有后继，则称该结点为终端结点。,序偶(),19,1,2,3,4,5,在线性结构中,除了开始结点和终端结点外,其余结点有且仅有一个前驱,有且仅有一个后继. eg. 图示法,20,非线性结构分为树形结构和图状结构. 树形结构 非线性结构 图状结构 在树形结构中，每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点. 在图状结构中，每个结点的前驱和

8、后继的数目可以是任意的，因此，可能没有开始结点和终端结点，也可能有多个开始结点和终端结点。,21,a,b,c,d,e,a,b,c,d,e,eg. 树形结构 图状结构,22,user,线性结构,树形结构 树 二叉树 二叉排序树,Eg.,23,堆结构,12,3,5,4,8,7,11,10,2,9,1,6,图结构 网络结构,24,数据的逻辑结构 从逻辑关系上描述数据，与数据的存储无关； 从具体问题抽象出来的数据模型； 与数据元素本身的形式、内容无关； 与数据元素的相对位置无关。,25,讨论数据结构的目的是为了在计算机中实现对它的操作，因此还需研究如何在计算机中表示它。 数据结构在计算机中的表示称为数

9、据的物理结构(又称映像或存储结构)，即逻辑结构到存储器的一个映射。它包括数据元素的表示和关系的表示。 数据元素的表示 物理结构 关系的表示,26,计算机使用0和1两个二进制数字，表示信息的最小单位是二进制的一位，叫做位Bit 。 计算机的信息单位还有字节和字。一个字节由8位二进制信息组成，一个字至少由一个以上的字节组成。,位 信息单位 字节 字,27,在计算机中，用一个若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素Element或结点Node。 当数据元素由若干数据项组成时，位串中对于各个数据项的子位串成为数据域Data Field。 逻辑结构: 数据元素 数据项 | |

10、| 物理结构: 元素/结点 数据域,28,数据元素之间的关系在计算机中有两种不同的表示方法: 顺序映像和非顺序映像 | | 顺序存储结构 链式存储结构 数据元素的表示 物理结构 关系的表示,29,1.顺序映像 特点: 借助元素在存储器中的相对位置来表示元素之间的逻辑关系。,以x和y存储位置的相对关系表示有序对 最简单的方法就是使y和x的存储位置之间差一个常量C， 而C是一个隐含值，整个存储结构中只含数据元素本身的信息。,30,Eg.线性结构list: 设每个结点占用一个存储单元,数据从200号单元开始从低地址向高地址存放. 存储结构如图所示:,1,2,3,4,5,1,2,3,4,5,200,2

11、01,202,203,204,31,设每个结点占用两个存储单元,数据从200号单元开始从低地址向高地址存放. 存储结构如图所示:,200,201,202,203,204,206,207,208,209,210,1,2,3,4,5,32,2.非顺序映像 特点: 借助指示元素存储地址的指针Pointer表示元素之间的逻辑关系.,x和y的存储位置随意，则需要用一个和x在一起的附加信息指示y的存储位置，这个附加信息和x绑定在一起，此时，两者合在一起作为x的存储映象。,33,Eg.每个结点占用两个单元,一个存放结点的数值,另一个存放后继结点的地址. 存储结构如图所示:,1 236,3 308,5 ,2

12、202,4 214,209,202,214,236,308,结点的数值,后继结点的地址,34,存储密度 紧凑结构：所有的空间都存储数据元素 非紧凑结构：有附加的信息 附加的信息会带来其他的优势,选择数据的存储结构 数据操作花费的时间少 占用的存储空间小 一般情况，时间优于空间,35,数据类型Data Type是一个值的集合和定义在这个值集上的一组操作的总称。 原子类型 数据类型 结构类型,36,数据类型,基本类型,构造类型,整型,字符型,实型(浮点型),枚举类型,指针类型,空类型,单精度型,双精度型,数组类型,结构体类型,共用体类型,C语言中的数据类型:,37,抽象数据类型Abstract D

13、ata Type，简称ADT，是指一个数据模型和定义在该模型上的一组操作。 每一个操作由它的输入和输出定义。 抽象的与具体的相对应。 eg. int a,b; 则 a和b可以进行+、-、*、/的运算 ， -2，-1，0，1，2，则是具体的int型数据 例如： 矩阵 +（求转置、加、乘、求逆、求特征值） 构成一个矩阵的抽象数据类型 数据结构+定义在此数据结构上的一组操作 =抽象数据类型,38,原子类型 抽象数据类型 固定聚合类型 结构类型 可变聚合类型,39,抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 ADT 抽象数据类型名 数据对象：

14、数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 其中，数据对象和数据关系的定义用伪码描述,40,基本操作的定义格式为 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述 基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头， 除可提供输入值外，还将返回操作结果。 “初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 “操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。,41,数据结构的划分,(1)按数据结构的性质划分 数据的逻辑结

15、构数据元素之间的逻辑关系 (设计算法 数学模型) 数据的物理结构数据结构在计算机中的 映像 (存储结构，算法的实现),42,(2)按数据结构在计算机内的存储方式来划分 顺序存储结构借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。 链式存储结构借助指示元素存储地址的指针表示数据元素之间的逻辑关系。 索引存储方法：在存储结点的同时，还建立附加 的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。 散列存储方法：根据结点的关键字直接计算出该结点的存储地址。 说明：四种存储方法可结合起来对数据结构进行存储映像。,43,(3)按数据结构的操作来划分 静态结构经过操作后，数据的结构特征保持不变(如