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