数据元素类型约定

一个抽象数据类型包括数据结构和其上的操作。本文档所讨论的所有数据结构都是某种数据元素类型的集合。而抽象数据类型上的操作最小只会涉及到数据元素的直接操作，而不会涉及到数据元素中数据项的操作。故为了隐藏数据元素对数据类型中算法实现的影响，在此对数据元素类型进行下列假设，以便后续讨论具体的数据结构。

• 所有数据元素类型名抽象为ElemType。

• 数据元素能够自动创建和销毁。

  对于 C++ 和 Java 这类面对对象的编程语言来说，这一点很自然，即使是自定义类也可以实现这样的功能，但对于 C 语言而言，如果是自定义的结构体类型，通常我们需要使用动态分配的方式来分配元素，这就导致我们必须手动创建和销毁这些元素。如果你使用 C++ 或其他面向对象编程语言，那么后续所有数据类型中关于数据元素的操作可以不用关心该点内容；而如果你是用 C 语言，并且数据元素采用动态分配的方式，那么请记住需要在后续所有操作实现中添加手动创建和销毁的操作。

• 数据元素需要支持以下操作：=（赋值、初始化）；==、!=（相等性比较）；<、<=、>、>=（关系比较）；>>、<<（输入输出）

  后续将假设所有数据元素都支持以上运算符操作。对于 C++ 来说，它的类型可以进行运算符重载，故该要求也是比较自然的。而对于 C 语言来说，如果是自定义类型则是不支持这些运算符操作的，但在后续介绍数据结构操作时仍然将直接使用这些运算符，包括 C 语言中也将使用 C++ 中的>>和<<作为输入输出运算符，虽然是错误使用，但对我们的抽象是有利的。读者如果使用 C 语言自定义类型实现数据元素，那么需要使用对应的函数来替换后续数据结构实现中数据元素间的运算符操作，包括<<、>>也使用printf和scanf进行替换。

• 对于字符串的数据元素必须是字符类型或满足字符类型的要求。