《数据结构基础》
作者: [美]Ellis Horowitz 霍罗维兹
译者: 朱仲涛
出版社: 清华大学出版社
ISBN: 9787302186960
在 豆瓣读书 中查看本书
数据类型
- 定义：数据类型是 数据对象 和 施加在数据对象上操作 的聚合体。
- 操作可以是前缀算符，如
atoi，或中缀算符，如+。 - 将数据对象的表示格式隐藏，提供接口处理数据对象。操作接口不变，但却可以修改表示方法。
抽象数据对象
- 定义：抽象数据类型（ADT）中的 数据对象和数据操作的规范声明 与 数据对象的表示和数据操作的实现 相互分离。
- C语言并未明显地提供实现ADT的机制，但仍可利用C语言的现有机制构造类似的数据类型。
- 抽象数据类型应独立于实现。
- 常用ADT至少包括以下类别中的一种函数：
- 构造函数/创建函数：这类函数为特定类型创建新实例。
-
变换函数：这类函数也为特定类型创建实例，但通常使用一个或多个其他实例。
变换函数与构造函数的差别。 - 观察函数/报告函数：这类函数提供数据类型的实例信息，但不修改实例。
定义ADT
示例
定义ADT NaturalNumber（摘自《数据结构基础》P16）
解释
- 该自然数抽象数据类型，从定义关键字
ADT开始，主要内容分两节：数据对象 和 成员函数。 - 数据对象是计算机系统中的整数类型，但此时并未显式指明整数的表示。
- 定义新的数据类型，可能会用到其他数据类型的操作。
- 每个成员函数的形式为：返回结果类型 函数名称 定义
- 符号
::=的意思是“定义为”。 - 第一个函数的名称是
Zero，无参量，返回自然数0，是构造函数。 - 函数
Successor(x)返回自然数序列中x的下一个，是变换函数。
如果数列中不再有后继元素，即x就是INT_MAX的话，函数返回INT_MAX。有些程序员这时倾向于返回出错信息，也可以。
习题
- 为自然数ADT加上如下成员函数：Predecessor,IsGreater,Multiply,Divide。（前驱，大于，乘法，除法）。
习题1 -by Cytosine
