导图社区 数据空间结构
这是一篇有关数据空间结构的思维导图，第1小节，从什么是数据结构、数据抽象和抽象数据类型等方面进行了概述和分析。
社区模板帮助中心，点此进入>>
互联网9大思维
安全教育的重要性
组织架构-单商户商城webAPP 思维导图。
个人日常活动安排思维导图
域控上线
西游记主要人物性格分析
17种头脑风暴法
python思维导图
css
CSS
数据空间结构
1.1什么是数据结构
数据(data)
就是计算机加工处理的对象
两类
数值数据(numerical data)
一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等
非数值数据(non-numerical data)
非数值数据包括字符、文字、图形、图像、语音、表格等
主要是为研究和解决如何使用计算机处理非数值问题而产生的理论、技术和方法
数据结构（如：学生情况表）
数据元素（组成数据的成分数据），如：每个学生的记录
数据项(data item)，如：学号、姓名、性别等
逻辑结构
从数学概念上讲，一个数据结构(data structure)是由数据元素依据某种逻辑联系组织起来的，是对数据元素间的逻辑关系的描述。
四种基本结构
集合结构(set)：数据元素的有限集合。数据元素之间除了“属于同一个集合”的关系之外没有其他关系。元素顺序是随意的。
线性结构(linear)或称序列(sequence)结构：数据元素的有序集合。数据元素之间形成一对一的关系。如：微博评论
树形结构(tree)：树是层次数据结构，树中数据元素之间存在一对多的关系。如，五子棋棋谱。
图结构(graph)：图中数据元素之间的关系是多对多的。如，大学课程关系。
线性结构(linear structure)
非线性结构(non-linear structure)
树、图和集合
是面向应用问题的，是从用户角度看到的数据的结构。
储存结构
计算机存储器(主存)
是由有限个存储单元组成的一个连续的存储空间
储存单元
字节编址
字编址
从存储器角度看，存储器中是一堆二进制数据
可以被机器指令解释成为指令、整数、字符、布尔数等等
也可以被数据结构的算法解释成为具有某种结构的数据
两种最基本的存储表示方法
顺序(sequential)存储结构
也称计算的方法，需要一块连续的存储空间，并把逻辑上相邻的数据元素依次存储在连续的存储单元中。
例如有四个数据元素组成的线性数据结构(a0, a1, a2, a3)，存储在某个连续的存储区内，设存储区的起始地址是100，假定每个元素占2个存储单元，则其顺序存储表示如图1－3(a)所示。
在顺序存储结构表示时，可以容易地用一个数学公式来确定每个元素的位置。对于图1－3(a)的顺序存储结构，一个简单的地址计算公式是：Loc(ak)＝102＋2*k
链接(linked)存储结构
在链接存储表示下，为了在计算机内存储一个元素，除了需要存放该元素本身的信息外，还需要存放与该元素相关的其他元素的位置信息。
这两部分信息组成存放一个数据元素的结点(node)
其中每个结点的存储块分成两部分
一部分存放元素自身
另一部分包含该元素逻辑上的后继元素(successor)的结点的存储位置
这种关于其他结点的位置信息被称为链(link)
图(b)中，电接地号表示空链(即不表示任何具体结点的单元地址)。
注意：一个结点的存储位置通常是指存放该结点的存储块的起始单元的地址。
是数据在计算机内的组织方式，是逻辑数据的存储映像，它是面向计算机的。
在以后的讨论中，在不会引起混淆的场合下，我们可以混合使用结点和元素这两个术语。但在必要时，我们将包括位置信息在内的存储块整体称为结点，而将其中的元素信息部分称为该结点的元素。
1.2 数据抽象和抽象数据类型
抽象(abstraction)可以被理解为一种机制，其实质是抽取共同的和实质的东西，忽略非本质的细节。
抽象可以使我们的求解问题过程以自顶向下的方式分步进行：首先考虑问题的最主要方面，然后再逐步细化，进一步考虑问题的某些细节，并最终实现之。
抽象的好处在于降低了问题求解的难度。
在程序设计中，抽象机制被用于两个方面：
数据
数据抽象(data abstraction)使程序设计者可以将数据元素间的逻辑关系与数据在计算机内的具体表示分别考虑。
比如六级单词的关系与其在计算机内的储存方式
过程
过程抽象(procedual abstraction)可使程序设计者将在数据上定义的运算与实现这些运算的具体方法分开考虑。
比如我要在某个地方求余数，求余数的算法单独考虑
封装(encapsulation)通常是指把数据和操纵数据的运算组合在一起的机制。
使用者只能通过一组允许的运算访问其中的数据。
从某种意义上说，数据的使用者只需知道这些运算的规范(定义)便可访问数据，而无需了解数据是如何组织和存储的，以及这些运算的具体算法如何等与实现有关的细节。也就是说对使用者隐藏了实现的细节。这种程序设计的策略称为信息隐蔽(information hiding)。比如：游戏中的战斗力计算装置。
通常将数据和操纵数据的运算组成模块(module)
每个模块有一个明确定义的接口(interface)，模块内部信息只能经过这一接口被外部访问。
一个模块的接口是实现运算的一组函数(functions)。
这样的模块被称为黑盒子(blackbox)。
一个程序使用一个采用信息隐蔽原则设计的模块被称为该模块的客户(client)。
封装和信息隐蔽有助于降低问题求解的复杂性，提高程序的可靠性。
数据类型是数据抽象的一种方式。
一个数据类型(data type)定义了一个值的集合以及作用于该值集的运算的集合。
C语言的基本数据类型
字符型、整型、实型、指针类型等原子类型
原子数据类型的值是不可分割的。
现实世界最终可以用这些初等数据来表示。
另一类是结构类型
结构类型的数据的值是由若干成分按某种结构组成的，因此是可以分解的。
数组(array)和结构(structure)是C语言提供的两种组织数据的机制。
程序设计语言中，数据类型不仅规定了该类型的变量(或常量)的取值范围，还定义了该类型允许的运算。
例如一个类型为int的变量的取值范围是－32 768～32 767，在整型数上的运算有+、－、*、/、%，关系运算<、>、<=、>=、==、!=，赋值运算=等。图1－4的上半部分给出了int的规范，它规定了整型变量(或常量)的取值范围及允许的运算；图的下半部分表示与该类型的实现有关的方面。两者是分离的。
了解一个数据类型的数据对象(变量、常量)在计算机内的表示是有用的，但也是危险的。这使得应用程序可直接编写算法操纵该数据对象，但一旦改变该对象的存储表示，则必须改变所有使用该对象的程序。目前，普遍认为对使用者隐藏一个数据类型的对象的表示是个好的设计策略，即用户只能通过使用该类型提供的函数操纵该对象。这样，当数据对象的表示或实现函数的算法改变时，只要不改变函数的调用方式，应用程序将无需改变。
一个抽象数据类型ADT(abstract data type)是一个数据类型
主要特征
该类型的数据对象及其运算的规范
它与数据对象的表示和运算的实现分离
实行封装和信息隐蔽
在一个抽象数据类型上应当定义哪些运算，这取决于应用。若一组运算是完备的，那么我们可以使用该组运算，对该数据结构实行我们希望的所有操作。
其实，C语言的类型int就是一个抽象数据类型，我们只能通过类型 int所规定的运算操纵整型变量或常量。虽然仅在面向对象程序设计语言出现后，才提供了必要的机制，使用户可以实现抽象数据类型，如C++语言的类(class)，但这并不意味着当我们使用C语言描述数据结构时，不能使用抽象数据类型的原则。
数据结构
一方面要说明它的数据的逻辑结构，
同时还应定义一组在该数据结构上执行的运算。
逻辑结构和运算的定义组成了数据结构的规范(specification)，
规范是实现的准则和依据，规范指明“做什么”，
而数据的存储结构和运算算法的描述构成了数据结构的实现(implementation)。
而实现解决“怎样做”。
从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。
在本书中，一种数据结构被作为一个抽象数据类型来加以讨论。
