《《算法与数据结构》第2章 常用数据结构ppt113》由会员分享，可在线阅读，更多相关《《算法与数据结构》第2章 常用数据结构ppt113（113页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构,第2章 常用数据结构,第2章 常用数据结构,2.1 数据类型与数据结构 2.2 数组 2.3 串,2.1 数据类型与数据结构,2.1.1 数据、数据元素与数据类型 2.1.2 数据结构的基本概念 2.1.3 抽象数据类型,数据,计算机中的数据在计算机内的最原始形式仅是一组组二进制代码，程序设计语言以这种代码为基础建立起了所有的数据。 数据的概念不再只是那些用数字组合而成的各种数据了，如整数、小数、实数、虚数、复数、指数和对数等。 随着计算机科学技术的发展，数据的概念也相应地发生了一些重要的变化。,数据（续）,数据（Data）是信息的载体，是对自然界客观事物的符号表示。 在计算机
2、科学与技术学科，数据泛指那些能够被计算机接收、识别、存储、加工和处理的对象的全体。 换句话说，数据是对那些能够有效地输入到计算机中并且能够被计算机程序所加工和处理的符号全体的总称。 只要是能被计算机识别、存储、加工和处理的都属于数据的范畴。,数据元素,数据的基本单位是数据元素（Data Element），有时也称作元素、结点、顶点、记录等。 一个数据元素也可以由若干个数据项（Data Item）组成。 数据项是具有独立含义的数据的不可再分割的最小标识单位。例如，一个单位的职工花名册中，每一位职工的信息就是一个数据元素；职工信息中包含有职工编号、姓名、性别、民族、年龄、政治面貌、参加工作时间、工
3、资级别、职称、职务等项目，这每一个项目都是某个职工数据元素中的一个数据项。,数据组织的三个层次,数据组织的三个层次分别是数据、数据元素、数据项。 数据可以由若干个数据元素组成，数据元素又可以由若干个数据项组成。 数据项是对数据元素属性的描述，数据元素是对客观世界中某个独立个体的数据描述。 在C语言中，数据元素可以用结构体来描述，每个数据项则是结构体中的一个分量。,数据元素与数据对象,计算机中的数据可以按类型来划分，划分的结果就是数据对象。 所谓数据对象（Data Object），是指具有相同性质的数据元素的集合，是数据的一个子集。如整数数据对、字母字符数据对象。 在一个具体问题中，数据元素具有
4、相同性质，属于同一数据对象，数据元素是数据对象的一个实例。如在前述的职工花名册中，所有的职工是一个数据对象，不同的职工的信息是不同的数据元素，它们都是职工数据对象的不同实例，其数据元素值是各数据项的一个具体描述。,数据类型,数据类型（Data Type）是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 如整数数据，在计算机中它是集合minintmaxint上的整数（其中minint和maxint分别是最小整数和最大整数，在不同的计算机中表示的值不同；且这个集合是有穷集合，是数学意义上的无穷集合的一个子集），在这个集合上可以进行的操作有加、减、乘、整除和求模等算术运算以及等于
5、、不等于、大于、小于、大于等于和小于等于等关系运算。 数据对象整数以及在整数集合上的算术运算和关系运算等操作一起构成了整型这个数据类型。,数据类型（续）,数据类型有简单（或原子）数据类型和结构数据类型之分。 简单数据类型是由程序设计语言提供的一些基本类型。如整型、实型、布尔型和字符型等，其值不可再分解。 结构数据类型是由程序设计语言中提供的构造机制来定义的数据类型。如数组、文件、结构体、共用体等，其值可以再分解；它的构成成分可以是简单数据类型，也可以是结构数据类型。数据类型的概念，是程序设计语言和程序设计过程中的一个非常重要的概念。,数据类型的特征,类型决定了变量或表达式所有可能取值的全体成员
6、集合。 每一个值隶属于且仅隶属于某一类型。 任何常量、变量或表达式的类型，都可以从其形式上或所处的上下文关系中推断出来，无须了解在程序运行时计算出的具体值。 每一种操作都要求一定类型的操作数据，且得出一定类型的操作结果。 一种类型的值及其在该类型上规定的基本操作的性质可由一组公理来阐明。 高级程序设计语言使用类型信息去防止程序中出现无意义的结构，又由类型信息确定在计算机中的数据表示和数据处理方法。,2.1 数据类型与数据结构,2.1.1 数据、数据元素与数据类型 2.1.2 数据结构的基本概念 2.1.3 抽象数据类型,数据结构的基本概念,数据结构（Data Structure）是指计算机程序
7、中所操作的对象数据以及数据元素之间的相互关系和运算。 在任何问题中，数据元素之间都不会是独立的，总是存在着这样或那样的关系，这种数据元素之间的关系也称作结构。 数据结构包含以下三个方面的内容： 数据的逻辑结构 数据的存储结构数据的运算及实现,数据的逻辑结构,数据的逻辑结构是指数据元素之间的逻辑关系。 它只抽象地反映数据元素集合的结构，而不管其存储方式，可用一个二元组给出如下的形式定义：Data-Structure （D,R）其中： D是数据元素的集合； R是D上关系的集合。 从结构的观点出发，一般可将数据结构分为两大类： 线性结构 如线性表、栈、队列、串、数组和文件等； 非线性结构 如树、图和
8、集合等。,数据的存储结构,数据的存储结构是指数据及数据元素之间的关系在计算机内存中的表示，也称作数据的物理结构或存储映像。 主要的存储方式有顺序存储和链式存储两种，此外还有索引存储和散列存储等其它方式。 从逻辑结构到存储结构称之为映像。 同一逻辑结构采用不同的存储结构存储，就会得到不同的数据结构。这是因为映像变了，使结构有了改变，使得实现逻辑结构上所定义的运算的算法也随之改变了。,数据的运算及实现,数据的运算及实现。程序中的数据运算是定义在数据的逻辑结构上的运算，但运算的实现要在相应的存储结构上进行。 常用的运算有检索、插入、删除、更新、排序等。 在数据的逻辑结构上定义数据的运算时，只考虑这些
9、运算是“做什么”，而不考虑它“如何做”，是抽象运算；只有在选定了某种数据结构的存储结构时，才去考虑如何具体实现这些运算，即运算的实现。 运算的实现依赖于所选取的存储结构，也依赖于所选用的程序设计语言。,线性结构,在线性结构中，D中数据元素之间存在着一对一的次序关系。 其逻辑特征为： 存在一个惟一被称作“第一个”的数据元素，它没有前趋只有一个直接后继；有时也称作开始结点； 存在一个惟一被称之为“最后一个”的数据元素，它没有后继只有一个直接前趋；有时也称作终端结点； 其它数据元素都有且仅有一个直接前趋（immediate predecessor），也有且仅有一个直接后继（immediate suc
10、cessor）。 如职工花名册、学生成绩表、向量、数组、购物时排的队等都是线性结构的例子。,非线性结构树型结构,在非线性结构中，D中数据元素之间不存在一对一的次序关系。 树型结构中的数据元素之间，存在着一对多的层次关系，在树型结构中： 没有直接前趋的结点称之为根结点； 除根结点外每个结点有且仅有一个直接前趋（称之为双亲结点）； 没有直接后继的结点称之为叶结点，除叶结点外每个结点都有一个或多个直接后继（称之为孩子结点）。 树的例子很多，如族谱中的家族树、政府机构中的行政树、计算机文件管理中的目录树、编译程序中用到的语法树等。,树型结构示意图,非线性结构图型结构,非线性结构中的图结构，其数据元素之
11、间既不存在线性结构中的一对一次序关系，也不存在树型结构中的一对多层次关系。 在图型结构中，D中数据元素之间的关系是多对多的网状关系。 换句话说，图是一种网状结构，任意两个数据元素之间都可能相关；其中的每一个数据元素，既可以有多个直接前趋，也可以有多个直接后继。 如交通网络图，课程之间的先后修关系图，软件开发过程中所用到的程序图、控制流图、数据流图等都是图型结构的例子。,图型结构示意图,非线性结构集合结构,非线性结构中的集合结构，其D中数据元素之间的关系是“属于同一个集合”。 集合是数据元素关系极为松散的一种结构。通常是用其它结构来表示集合。,存储表示方式顺序存储,顺序存储方式，是在计算机内存储
12、器中开辟一片地址连续的存储单元顺序存放数据中的各个元素；它把逻辑上相邻的数据元素存放在物理上相邻的存储单元中，利用物理上的邻接关系表示逻辑上的先后次序关系，这种存储表示方式称作顺序存储结构（Sequential Storage Structure）。 顺序存储结构是一种最基本的存储方法，通常借助于程序设计语言中的数组来实现。 主要用于线性数据结构的存储，对于非线性结构进行线性化处理后也可实现顺序存储。,存储表示方式链式存储,链式存储方式，是把数据元素和反映元素间关系（后继和/或前趋）的地址一块存储在计算机内；它不要求在内存储器中开辟的存储单元地址连续，数据元素可以存放在内存储器中的任意位置，借
13、助指示数据元素存储地址的指针表示元素间的逻辑关系，这种存储表示方式称作链式存储结构（Linked Storage Structure）。 链式存储结构也是一种基本的存储表示方法，通常借助于程序设计语言中的指针来实现。 主要用于树型结构和图型结构数据的存储，为了某种特殊的需要也常用于一些线性结构的存储。,其他的存储表示方式,存储表示方式还有索引存储方式和散列存储方式，通常是为了检索的方便所采用的存储表示方法。 一般地说，这几种基本的存储表示方法，既可以单独使用，也可以组合起来使用。 选择何种存储结构要依具体问题的要求而定，既要考虑问题表示和运算的方便性，也还会考虑到实现算法的时间和空间效率要求。
14、,数据的逻辑结构和存储结构,数据的逻辑结构和存储结构是密切相关的两个方面： 算法的设计都取决于所选定的数据的逻辑结构； 算法的实现则依赖于所采用的存储结构。 各种数据结构，分别提供了不同类型的数据在作为计算机程序数据时的组织、管理、存储、运算和处理的方法和技术。 有些数据结构，在程序设计语言中已经实现了或提供了定义数据类型的方法或手段。如各种基本类型，数组、字符串等 有些数据结构，在程序设计语言中没有实现，要靠程序设计人员利用语言中提供的某些设施去实现或模拟实现，如栈、队列、树、二叉树、图、网络等。 在程序设计语言中实现了的数据结构称之为数据类型。,2.1 数据类型与数据结构,2.1.1 数据
15、、数据元素与数据类型 2.1.2 数据结构的基本概念 2.1.3 抽象数据类型,抽象数据类型,抽象的本质就是抽取反映问题本质的东西，忽略掉非本质的细节。 数据类型是对同一数据对象及其在该数据对象上的一组操作的抽象，抽象的结果是把用户不必了解的一切细节都封装在类型之中，对使用数据类型的用户来说是实现了信息隐藏（Information Hiding）。 用户在使用数据类型时，既不需要了解该数据类型在计算机内部是如何表示的，也不需要知道其操作是如何实现的，只须集中精力考虑所要求解的问题应该如何去解决。 抽象数据类型的概念，是我们熟知的数据类型概念的引伸和发展，是数据抽象和运算抽象紧密结合的产物。,抽
16、象数据类型（续）,抽象数据类型（Abstract Data Type简记为ADT）是指一个数据模型以及定义在该数据模型上的一组操作。这里的数据模型，是要求解问题中的各种数据的总和；通常，把这些数据可以组织成为一个或多个数据结构。 当数据模型表现为一个数据结构时，抽象数据类型就是这个数据结构以及定义在这个数据结构上的一组运算；这种情况是我们讨论和学习抽象数据类型概念的基础，也是数据结构课程对抽象数据类型定义的根本要求。 当数据模型表现为多个数据结构时，我们可以先定义以单个数据结构为基础的各个抽象数据类型，然后在此基础上（需要的话）定义抽象级别更高的抽象数据类型，并利用它们构造最终的问题求解算法。,抽象数据类型的定义,抽象数据类型的定义，仅取决于它的一组逻辑特性，而与它在计算机内部如何表示和实现无关。 也就是说不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用；如同数据类型一样，是使用与实现分离、实行封装和信息隐藏。 抽象数据类型可以通过已有的数据类型来表示和实现，利用已有的数据类型来说明新的结构，利用已经实现了的操作来完成新的操作。,
