当前课程知识点：数据结构 > 第1章 绪论 > 1.3 抽象数据类型 > 讲解（上）
这一节，我们来学习抽象数据类型
先来看数据类型的定义
数据类型是指若干值的集合
在这些值上能够执行某些操作
比如，数学上经常讲的整数型。整数型
实际上就包含了所有整数构成的集合
我们对整数可以做加减乘除
取余等等
数据类型可以分为原子型和结构型。原子类型是指不可再分的类型
无论是整型、实型、字符、布尔
指针，它们的本质都是数值
而结构类型是由原子类型或结构类型组合而成的
注意，结构类型里面的元素也可以是结构类型
比如字符串
它就是由若干个字符构成的
数组，数组是由若干个元素构成的
至于每个元素的类型
既可以是原子类型
也可以是结构类型。又比如学生
我们刚才见过了，它可以由整数的ID(编号)
字符串型的姓名
整型的年纪等等构成
还有图像，图像
我们存的是每个像素的颜色分量
可以用一个二维数组
如果存的是彩色的图像
那可以用一个三维数组
总之
结构类型都是可以再分为原子类型或者是结构类型的
需要注意的是
不同语言、编译器，甚至是同一语言的不同版本
它们各自所支持的数据类型可能不尽相同
我们举一个例子
比如，C89这个标准的C
有时候也称为ANSI C
它是不支持布尔类型的
如果我们用C89标准的编译器去写代码
那么，这时候我们可能用整型来表示真假的概念
比如，我们经常用0来表示假，任何非0的值来表示真
当然，也可以不这样
将1定义成真，0定义成假也行。到了C99
才真正有布尔类型的支持
再以Java为例
在JDK5之前，是不支持枚举类型的
直到JDK5之后，才有枚举类型
讲了数据类型的概念之后
我们再来看抽象数据类型
抽象数据类型是从逻辑结构的角度来描述元素、关系及操作
它与计算机和编程语言无关
我们刚才讲到了数据类型
它是跟所采用的编程语言、版本
还有编译器相关的
那么，抽象数据类型跟计算机、编程语言、编译器是没有任何关系
抽象数据类型跟数据结构的定义类似
只不过多了一个部分，叫做操作。抽象数据类型
由三部分构成
分别是：数据元素
元素之间的关系，以及元素支持的操作
这三部分
对于抽象数据类型，抽象的意义在哪呢
第一，分离数据类型的描述和实现
对于一种抽象数据类型
我们只需要描述清楚这种类型里面包含什么样的元素
元素之间的关系是什么
以及支持哪些操作，就行了
我们不用管这些关系以及操作
具体在计算机内部如何实现
第二
屏蔽了计算机软硬件平台的差异
正是因为数据类型是跟计算机、编译环境、编程语言相关的
为了屏蔽具体平台的差异
我们引入了抽象数据类型
它跟你所使用的计算机以及平台是没有关系的
第三，提升了模型的可理解性和可复用性
这是基于前两点——分离了描述和实现
屏蔽了平台的差异
所以，我们设计出来的抽象数据类型
它的可理解性是比较强的
即使是不懂
编程技术的人，他也能看懂一个抽象数据类型的定义
从而提升了抽象数据类型的可复用性
下面，我们来看一个抽象数据类型的具体示例
在这里，我们定义了一个名字为Complex的抽象数据类型
用来描述数学上的复数的概念
这里我们采用了类C的风格
需要注意的是
这里并不是真正的编程语言
因为抽象数据类型跟具体的编程语言是没有关系的
它只是一种数学上的符号
只是一种伪码
因为大多数学习数据结构的朋友
对C语言都有所了解
所以，我们这里采用了类C的风格
比如大括号
抽象数据类型描述了三部分信息
一部分是数据元素
在这里，我们也采用了一些数学语言
比如，复数
它是由实部和虚部构成的
也就是这里的a和b
是属于数学上的实数的范围的
关系呢
一个复数
它的实部跟虚部
实际上形成了一种偏序的关系
我们采用了离散数学上的偏序符号
再次强调——这里的元素和关系
采用任何你熟悉的，或者大家能看懂的符号
都可以，不一定要采用数学语言
第三部分
是操作
也就是，我们定义的抽象数据类型
它支持哪些操作
同样，我们这里也采用了类C的伪码
比如，我们这里定义的第一个操作
init
是用来初始化一个复数的。同时
我们给出了三个信息
作为参数，后两个参数
a和b，初始化一个复数
你要告诉我
这个复数，它的实部和虚部分别是什么
第一个参数c
大家看到，前面加了一个&符号
这是C++的引用参数语法
我们这里不仅采用了类C的伪码
还结合了C++的引用参数语法，这个引用参数语法有什么用呢
它实际上就是为了方便在一个函数内部去修改一个形参。
待会儿，我们会用一个具体的示例来演示引用参数的语法
总之
我们采用了一种类C的伪码来描述抽象数据类型
使得
抽象数据类型不仅容易理解
同时
也能很方便地
把它修改成真正的
合法的编程语言代码
我们还定义了，得到一个复数c的虚部
这样一个操作。得到的虚部
我们放在a里面
我们还定义了完成两个复数相加的操作
c1和c2相加
最后结果
我们存到sum
这个参数里
当然
你还可以去定义其他的操作
下面，我们就来专门讲一讲C++的引用参数语法
我们的问题是：如何修改一个函数的形参。比如，我们给出这样一个函数
它的形参是x
如果我们在函数体里面去修改这个形参x
你会发现，doSomething这个函数调用结束之后
你传入的那个实参
它的值在调用结束之后并不会被修改
这是因为，形参跟实参各自占据着不同的存储单元
你修改形参不会影响实参
那如何以一种比较方便的方式，让doSomething
这个函数调用完毕之后
传入的实参确实自增了1呢
第一种方式是修改
函数的返回值
我们把修改后的x
作为函数的值返回回去
这样，在调用doSomething的时候
我们用一个变量来接收修改后的值
第二种方式
是将你要修改的这个形参作为全局变量
因为全局变量能被所有的函数访问到。任意一个函数
都能修改这个全局变量
第三种方式
是将你要修改的形参声明成指针类型。我们知道，指针类型有一个作用
就是：修改这个指针指向的内容
回到主调函数当中
相应的实参也会被修改
这是因为，实参传递的时候，传递的实际上是一个地址
在被调函数里面修改这个地址指向的内容
那么，实参也会被修改
最后一种方式
是采用C++的引用参数
仅需要在要修改的形参前面，加一个&符号就可以了
现在我们来演示一下这个例子
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
