数据结构与算法基础（上）
什么是数据结构，数据结构研究的主要内容，了解什么是算法，如何评价一个算法的性能
数据结构
人们在使用计算机解决客观世界中存在的具体问题时，通常过程如下：首先通过对客观世界的认知形成印象和概念从而得到了信息，在此基础上建立概念模型，它必须能够如实地反映客观世界中的事物以及事物之间的联系；根据概念模型将实际问题转化为计算机能够理解的形式，然后设计程序；用户通过人机交互界面与系统交流，使系统执行相应操作，最后解决实际问题。
数据结构主要与在上述过程中从建立概念模型到实现模型转化并为后续程序设计提供基础的内容相关。它是用来反映一个概念模型的内部构成，即一个概念模型由哪些成分数据构成，以什么方式构成，呈现什么结构。数据结构主要是研究程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。
基本概念
数据：是描述客观事物的数值、字符以及能输入机器并能处理的各种符号集合。数据的含义非常广泛，除了通常的数值数据、字符、字符串是数据以外，声音、图像等一切可以输入计算机并能被处理的都是数据。例如除了表示人的姓名、身高、体重等的字符、数字是数据，人的照片、指纹、三维模型、语言指令等也都是数据。
数据元素：是数据的基本单位，是数据集合的个体，在计算机程序中通常作为一个整体来进行处理。例如一条描述一位学生的完整信息的数据记录就是一个数据元素；空间中一点的三维坐标也可以是一个数据元素。数据元素通常由若干个数据项组成，例如描述学生相关信息的姓名、性别、学号等都是数据项；三维坐标中的每一维坐标也是数据项。数据项具有原子性，是不可分割的最小单位。
数据对象：是性质相同的数据元素的集合，是数据的子集。例如一个数据的所有学生的集合就是数据对象，空间中所有点的集合也是数据对象
数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合。是组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。
由于信息可以存在于逻辑思维领域，也可以存在与计算机世界，因此作为信息载体的数据同样存在于两个世界中。表示一组数据元素及其相互关系的数据结构同样也有两种不同的表现形式，一种是数据结构的逻辑层面，即数据的逻辑结构；一种是存在于计算机世界的物理层面，即数据的存储结构。
数据的逻辑结构按照数据元素之间相互关系的特性来分，可以分为以下四种结构：集合、线性机构、树形结构和图状结构
数据结构主要有线性表、栈、队列、树和图，其中线性表、栈、队列属于线性结构，树和图属于非线性结构
数据的逻辑结构可以用两种方法来描述：二元组、图形
数据结构的二元组表示：
数据结构=｛D, S｝，其中D是数据元素的集合；S是D中数据元素之间的关系集合，并且数据元素之间的关系是使用序偶来表示的。序偶是由两个元素x和y按一定顺序排列而成的二元组，记作<x, y>,x是它的第一个元素，y是它的第二个元素。
当使用图形来表示数据结构时，使用图形中的点来表示数据元素，用图形中弧来标识数据元素之间的关系。
数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示。通过数据元素的定义可以看出，我们可以很容易的使用java中的一个类来实现它，数据元素的数据项就是类的成员变量。
数据元素之间的关系在计算机中主要有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构的特点是：数据元素的存储对应于一块连续的存储空间，数据元素之间的前驱和后续关系通过数据元素在存储中的相对位置来反映。链式存储结构的特点是：数据元素的存储对应的不是连续的存储空间，每个存储节点对应一个需要存储的数据元素。元素之间的逻辑关系通过存储节点之间的链接关系反映出来。
抽象数据类型
抽象数据类型是描述数据结构的一种理论工具。在理解抽象数据类型之前需要先理解下数据类型的基本概念
数据类型：是一组性质相同的数据元素的集合以及加在这个集合上的一组操作。例如Java语言中就有许多不同的数据类型，包括数值型的数据类型、字符串、布尔型等数据类型。以Java中的int型为例，int型的数据元素的集合是[-2147483648，2147483647]间的整数，定义在其上的操作有加、减、乘、除四则运算，还有模运算。
定义数据类型的作用是一个是隐藏计算机硬件及其特性和差别，使硬件对于用户而言是透明的，即用户可以不关心数据类型是怎么实现的而可以使用它。定义数据类型的另一个作用是，用户能够使用数据类型定义的操作，方便的实现问题的求解。例如，用户可以使用java定义在int型的加法操作完成两个整数的加法运算，而不用关心两个整数的加法在计算机中到底是如何实现的。这样不但加快了用户解决问题的速度，也使得用户可以在更高层面上考虑问题。
与机器语言、汇编语言相比，高级语言的出现大大地简便了程序设计。但是要将解答问题的步骤从非形式的自然语言表达到形式化的高级语言表达，仍然是一个复杂的过程，仍然要做很多繁杂琐碎的事情，因而仍然需要抽象。
对于一个明确的问题，要解答这个问题，总是先选用该问题的一个数据模型。接着，弄清该问题所选用的数据模型在已知条件下的初始化状态和要求的结果状态，以及隐含着的两个状态之间的关系。然后探索从数据模型的已知初始状态出发到达要求的结果状态所必需的运算步骤。
在探索运算步骤时，首先应该考虑顶层的运算步骤，然后在考虑底层的运算步骤。顶层的运算步骤是指定义在数据模型级上的运算步骤，或叫宏观运算。它们组成解答问题步骤的主干部分。其中涉及的数据是数据模型中的一个变量，暂时不关心它的数据结构；涉及的运算以数据模型中的数据变量作为运算对象，或作为运算结果，或两者兼而为之，简称为定义在数据模型上的运算。简称为定义在数据模型上的运行。由于暂时不关心变量的数据结构，这些运算都带有抽象性质，不含运算的细节。所谓底层的运算步骤是指顶层抽象的运算的具体实现。它们依赖与数据模型的结构，依赖于数据模型结构的具体表示。因此底层的运算步骤包括两部分：一是数据模型的具体标识；二是定义在该数据模型上的运算的具体实现。我们可以把它们理解为微观运算。于是，底层运算是顶层运算的细化，底层运算为顶层运算服务。为了将顶层算法与底层算法隔开，使二者在设计时不会相互影响，必须对二者的接口进行一次抽象。让底层只通过这个接口为顶层服务，顶层也只通过对这个接口调用底层的运算。这个接口就是抽象数据类型
抽象数据类型：（abstract data type,简称ADT）由一种数据模型和在该数据模型上的一组操作组成。
抽象数据类型包括定义和实现两个方面，其中定义是独立与实现的。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部的实现无关，即无论它的内部结构如何变化，只要它的逻辑特性不变，都不会影响到它的使用。其内部的变化只是可能会对外部在使用它解决问题时的效率上产生影响，因此我们一个重要任务就是如何简单、高效地实现抽象数据类型。很明显，对于不同的运算组，为使组中所有运算的效率都尽可能地高，其相应的数据模型具体表示的选择是不同的。在这个意义下，数据模型的具体表示又依赖于数据模型上定义的那些运算。
特别是，当不同运算的效率相互制约时，还必须事先将所有的运算的相应使用频率排序，让所选择的数据模型的具体表示优先保证使用频率较高的运算有较高的效率。
抽象数据类型的概念并不是全新概念。抽象数据类型和数据类型在实质上是一个概念，只不过是对数据类型的进一步抽象，不仅限于各种不同的计算机处理器中已经实现的数据类型，还包括为解决更为复杂而由用户定义的负责数据类型。
抽象数据类型一方面使得使用它的人可以只关心它的逻辑特征，不需要了解它的实现方式。另一方面可以使我们更容易描述现实世界，使得我们可以在更高的层面上来考虑问题。例如可以使用树来描述行政区划，使用图来描述通信网络
根据抽象数据类型的概念，对抽象数据类型进行定义就是约定抽象数据类型的名字，同时，约定在该类型上定义的一组运算的各种运算的名字，明确各个运算分别要有多少个参数，参数的含义和顺序，以及运算的功能。一旦定义清楚，人们在使用时就可以像应用基本数据类型那样，十分简单地引用抽象数据类型；同时，抽象数据类型的实现就有了设计依据和目标。抽象数据类型的使用和实现都是与抽象数据类型的定义打交道，这样使用和实现没有直接的联系。因此，只要严格安装定义，抽象数据类型的使用和实现就可以相互独立，互不影响，实现对它们的隔离，达到抽象的目的。
为此抽象数据类型可以使用三元组来表示：
ADT=(D,S,P)
其中D是数据对象，S是D上的关系集，P是加在D上的一组操作。
ADT抽象数据类型名｛
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
｝
小结：数据结构就是研究三个方面的主要问题：数据的逻辑结构、数据的存储结构以及定义在数据结构上的一组操作。即研究按照某种逻辑关系组织起来的一批数据，并按照一定的映像方式把它们存在计算机的存储器中，最后分析在这些数据上定义的一组操作。为此我们要考虑怎样合理的组织数据，建立合适的结构，提高实现的效率
在数据结构的实现中我们可以将数据结构中的一些基本概念和Java语言中的一些概念对应起来。数据元素可以对应到类，器数据项就是类的成员变量，某个具体的数据元素就是某个类的一个实例；数据的顺序存储结构与链式存储结构可以通过一维数组以及对象的引用来实现；抽象数据类型也可以对应到类，抽象数据类型的数据对象与数据之间的关系可以通过类的成员变量来存储和表示，抽象数据类型的操作则可以使用类的方法来实现。
转载请注明：学时网 » 数据结构与算法基础（上）
