大家好
我们继续学习数据结构与算法第一章概论的内容
这一讲我们主要介绍数据结构的相关定义特别是抽象数据类型的概念
首先我们来看一下什么是结构呢
一个结构，主要是包括一些实体以及实体之间的关系
把它们组合起来就成为一个有机的结构整体
在数据结构中，它主要有三个基本的面
首先是它的逻辑关系，也就是说这个实体它们之间有什么样的数学的逻辑关系
在这个逻辑关系之上，可能会有一些很好的性质
这个性质有助于我们有效地进行存储和运算
在计算机里面，我们要对这个数据进行合理的表达，一定是要把它存到内存里面，这样才能够跟CPU进行数据交换
因此我们需要对它进行一定存储的组织
另外对于我们问题求解来说，我主要是对一些相应的数据，经过一些运算操作得到相关的输出
也就是说我们的运算或者说算法是它非常重要的一个方面
可以说数据结构是由逻辑、存储和运算这三个方面来组合的
在不同的应用场景下，我们强调的侧面不同，但是它们都是不可缺少的
数据结构的逻辑结构呢，主要是分为线性和非线性两大类
线性结构就以我们以前见过的数组、链表这样的线性表为代表
线性表里面有一些特别的数据结构例如栈、队列还有字符串
这个在后面的章节都会介绍到
非线性结构主要有两大类
第一类就是树结构
这个树结构就是一种层次化的组织形式
而图结构是受限最少的一种结构
也就是说节点和节点之间的边组成了这么一个结构
在这几种结构里面，受限最多的这个结构线性表它其实是最简单的一种数据结构
然后这些结构互相之间是有一些包含关系的
整个数据结构教材可以说主要是以数据结构的逻辑结构为主线来组织
我们首先讨论各个结构的逻辑特性
然后我们讨论一些它相关的运算，也就是说它应该支持哪一些主要的操作
为了实现这些运算，我们可能要在计算机里面进行合理的存储表达
数据的存储结构其实是从逻辑到它的物理存储单元的一个映射
物理存储单元必须存在内存里，因为我们需要对这个数据结构进行操作
数据必须在内存里才能跟CPU进行直接的通讯
内存其实是被看作从低地址到高地址的一个编码的线性结构
我们想访问哪一个单元，都可以立即访问，并不需要在整个内存里面去进行一个搜索或者是遍历的过程
因此我们访问内存里任何一个地址所需要的时间都是相同的
我们看一个存储结构的例子
对于这么一个线性表，这是一个数组，它有三个元素
我们得到了起始的元素的存储地址后，在访问其他的元素的时候我们也是能够立即算出它的起始地址
例如这个A[0]它的起始地址是4
一个整型元素占用4个字节
因此我们就知道它的第二个元素的起始地址是8，第三个是12
这就是一个映射的过程
对于我们数据结构里面所定义的每一个节点，我申请的内存空间必须是连续存储的区域
如果我们指针的一个映射已经是指向另一个扩展的内容，那么这个是可以开辟另外的空间的
数据结构的存储结构主要是由顺序的、链接的还有索引和散列这四种形式组成
顺序结构就对应于我们以前的这种数组的形式
也就是说它的这样的一个连续存储正好可以表达它逻辑上相关联的先后顺序
当然如果你的逻辑结构并不是顺序的，那对它进行一个相应的线性化以后也是可以进行顺序存储的
链接的结构就对应于我们以前的链表的形式
在数据结构里面，链接结构是非常重要的，特别是对于一些非线性结构例如二叉树、树和图
很多情况下，我们用链接结构来表达是非常自然而且很方便运算的
索引和散列是在数据结构里面要重点讨论的内容
所谓索引就是对这个数据建立一个索引的表，然后通过这个表我们能够有效的找到相应的数据的存储地址
散列是一种特殊的索引结构它本身当然也是一种存储结构
散列能够通过对你要查的关键码的一个映射，能够在整个散列表里面快速地找到它的存储的空间，然后把相应的数值给找出来
在数据结构里有一个特别重要的概念就是抽象数据类型
我们回顾数据结构的三个方面，就是它的逻辑结构、存储结构和运算
可以看到存储结构纯粹是为了要在计算机里面来实现，来表达而提出来的
对于我们数据结构的使用者来说，最关心的是它的逻辑结构，也就是说它在逻辑上有什么特性，以及它能支持什么样的操作运算
你怎么样在内存里面去存放，其实它是不需要关心的
因此，我们就可以定义一套抽象的数据类型
这个抽象数据类型，我把它的逻辑结构描述清楚，把它所支持的运算描述清楚就可以了
抽象数据类型是随着模块化的发展而来的而且和面向对象的这些方法一起相应的发展起来的
有了抽象数据类型的支持，使得我们的软件可以建立在这些我们已经编好的成熟的数据结构的基础上
我就可以搭建更复杂的应用系统，而不需要关心底层的具体的实现
而且在上层引用的时候，我们的这些函数的调用形式也不需要进行一些重写，只需要对头文件的引用进行一些修改
抽象数据类型，我们刚才说了，它主要是逻辑和运算这两个方面
逻辑就表达在它的数据对象里面，对象包括这个数据本身以及数据之间的关系也就是说实体和实体之间的关系
而它的运算就体现在数据操作上
这个操作在C++等面向对象的语言里面就体现为函数
因此我们可以描述好逻辑结构以后再描述相应的函数定义，这样就可以很好的描述这个抽象数据类型
那我们来看一个例子
对于栈这样的一个抽象数据类型，首先它是一个线性结构，也就是说它的数据是有序的，从第一个元素到最后一个元素
栈还有一个特点就是它要限制这个数据结构的操作
也就是说我在建立这个数据结构以及对它进行操作的过程中，只允许在这个结构的一端进行操作
也就是说我们最后进入的数据，必须最先给它拿出来
中间的其他数据以及最先进到这个栈里面的数据是不能够随便来访问的
每次都要从栈顶来取或者是读元素
栈的运算最主要的就是读也就是出栈，还有写也就是入栈这两个pop和push的操作
定义完了它的逻辑结构以后，我们相应的把它的操作接口给定义一下
我们借用C++的模板类来描述
首先这个栈的元素类型是一个class T
我们在将来调用的时候可以指定这个栈里面的元素具体是什么类型
可以是整型实型或者是其他的复杂类型
栈的操作主要有入栈和出栈，也就是push和pop，其他的是一些辅助的操作
我们借用这么一个C++类的定义就可以描述出栈抽象数据类型最主要的操作
其实可以看到它的逻辑结构是通过我们的一个辅助语言描述来实现的，并不能够在这个类定义里面去给它形式化的表现
我们来思考一下，在数据结构里面抽象数据类型这么一个重要的概念的逻辑结构是怎么表达的
我们前面那个例子有所介绍
另外抽象数据类型是不是就是类定义
还有就是我们在表达抽象数据类型的时候，如果不用模板来描述这个ADT是不是可以呢
谢谢大家