当前课程知识点：数据结构 > 第1章 绪论 > 1.4抽象数据类型的定义和实现 > 1.4抽象数据类型的定义和实现
同学们大家好
我是云南大学信息学院的教师孔兵
这一节，首先看一下数据类型的概念
数据类型这个概念来自于程序设计语言
它是指一个值得集合和定义在这个值集上的一组操作的总称
这里我们要注意操作这个概念，操作是数据类型不可分割的一部分
同样的操作定义，在不同的数据类型中
实现的方式可能都是有差异的
在数据类型的基础上我们引出了抽象数据类型的概念
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作
前面提到过，在程序设计这个领域
所谓的数学模型指的就是数据结构
所以说，抽象数据类型实际上就是指
一个数据结构以及定义在该结构上的一组操作
同样，操作和数据结构本身也是息息相关的
比如插入操作，在线性表上的插入操作
在树上的插入操作，在图上的插入操作
实际上都是不一样的
根据抽象数据类型的定义
抽象数据类型ADT可以描述为一个三元组D,S,P
其中，D是数据对象，也就是数据元素的集合
S是D上的关系集，也就是D中数据元素之间的关系集
P是基本操作集。从ADT的定义中，大家可能已经注意到了
前面的d和s实际上就是前面说的数据结构
也就是数据结构和他们之间的关系
P是在这个数据结构上定义的一个基本操作的集合
在教材中对抽象数据类型有一个定义的格式
adt加抽象数据类型的名字，在花括号中是对数据对象
数据关系，以及基本操作的定义
花括号后是adt加抽象数据类型的名字
作为抽象数据类型定义的结束
当然，抽象数据类型最终毕竟要在计算机内部加以实现
下面，我们介绍一下抽象数据类型的表示和实现
要实现抽象数据类型在计算机内部的表示
这就需要用程序设计语言来描述数据结构及基本操作
教材中，采用类C语言来描述数据结构和基本操作
类C语言是从C语言当中变化而来的
它精选了C语言的一个核心子集，同时做了一些扩充修改
主要是去掉了c语言当中比较繁琐的一些语法细节
同时，为了增加描述能力，扩充了一些描述能力强的语句形式
使它对算法的描述能力更强更清晰
要注意，类C描述的程序不能在C语言编译器中直接使用
需要把类C描述的程序进行适当的转换，这很容易
我们看一下在后面程序中用到的一些常量
这里定义了TRUE, FALSE,OK, ERROR, INFEASIBLE,OVERFLOW等常量
在后面的程序中会看到，你要知道是什么意思
另外需要说明的是
这里用typedef给整型另外起了一个类型名叫status
在后面的程序中，很多函数的返回值的类型都是Status
意思是说，函数return返回的虽然是一个整型数
但是这个整型数代表的是这个函数执行的一个状态
如果程序执行的顺利，一般我们就返回OK
在程序函数执行的过程当中，如果发生了什么问题
那么返回的就是ERROR
另外，对数据元素的类型做了一个约定
从前面的例子当中，大家注意到
在不同的问题背景下，数据元素类型其实是不一样的
三个例子当中，数据元素分别是书
格局和通道
在后面数据结构的定义中
为了不和具体问题关联
我们给出了一个抽象的数据元素类型ElemType,
我们定义的所有数据结构中
数据元素的类型均定义为ElemType
大家要注意，这是一个抽象的数据元素类型
并不是实际存在的
在具体问题当中必须把它具体化
好了同学们
我们今天的课程就到这里
下节课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
