元素可能与多个其他数据元素发生联系，非线性结构
有二叉树、树、堆、集合、图等。
2.1.2 数据类型
类型是一组值的集合。 数据类型（DataType）是指一个类型和定义在该类型上 的操作集合。
2.1.3 抽象数据类型
抽象数据类型（Abstract Data Type，ADT）是用户 在数据类型基础上自己定义和实现的数据类型。类似 于在计算机机器语言的位、字节和字的基础上引入整 数、浮点数、双精度数、字符等数据类型的思想方法， 高级程序设计语言使用者可以在高级程序设计语言整 数、浮点数、双精度数、字符等数据类型的基础上引 入各种新的数据类型提供给自己或他人使用，从而使 自己或他人的程序编制达到更高一级的数据抽象。这 种由用户自己定义和实现的新的数据类型称为抽象数 据类型。
因此我们说，抽象数据类型是用户在数据类型基
础上自己定义和实现的数据类型。一种抽象数据类型 定义了一种新的数据元素集合和数据元素集合上所允 许的操作集合。抽象数据类型是用户通过更高一级抽 象得到的新的数据类型。抽象数据类型在更高一级的 抽象程度上实现了信息的隐藏和封装。
Class SeqList { private: Datatype data［MaxListSize］; int size;// public: SeqList(void); ~SeqList(void); int ListSize(void)const; // // //返回元素的个数size
度数、字符等高级程序设计语言中的数据类型一样重
复使用。
2 信息隐藏
抽象数据类型封装了数据元素的具体存储方法和 各种操作的具体实现方法，抽象数据类型的使用者只 需根据调用界面调用它们，无需了解抽象数据类型数 据元素存储方法和各种操作实现方法的具体细节，从 而像程序设计语言中的数据类型一样实现了信息隐藏。
3 可靠性提高
基于模块的软件开发可以大大降低软件的复杂度， 所以可以提高软件的可靠性。 4 便于软件调试和维护 由于抽象数据类型具有信息隐藏的优点，软件设
计只需考虑高一级的程序结构，无需考虑封装在抽象
数据类型中的实现细节，所以基于抽象数据类型的软 件设计便于调试和维护。
2.2 面向对象程序设计和类
逻辑结构（Logical Structure）是数据元素的逻辑
表示方式。如图2―1就是一组数据元素的逻辑结构。
图2―1 学生登记数据元素
存储结构（Store Structure）是数据元素在计算机
中的存储方式。数据元素可以有多种存储形式，如图 2―1 所示的学生登记中的数据元素既可用一个足够大
的数组存储，也可用一个如图 2―2 所示的单链表存储。
面向对象程序设计（Oriented ObjectProgramming）是以类设计为核心的一种新的程 序设计方法，它是基于抽象数据类型程序设计方法的 进一步发展。
类（ Class ）是面向对象程序设计中相同对象的抽
象描述。类包括数据成员和方法两部分。数据成员是
数据结构（DataStructure）表示数据元素间的逻辑 结构和存储结构以及这个数据元素集合上的操作集合 的总称。如上述学生登记问题中数据元素集合和数据 元素集合上的操作集合就构成一种称为线性表的数据 结构。
数据结构课程研究程序设计中常用的各种数据结
构的数据元素间的逻辑关系和这些数据元素集合上的 操作集合，它们的不同的存储结构（或称存储方法）， 以及不同存储结构下各种操作的实现方法。 依据数据元素之间的关系，数据结构可分为线性 结构和非线性结构两大类。线性结构中各个数据元素 依次排列在一个线性序列中。线性结构有线性表、堆 栈、队列、字符串、数组等；非线性结构中各个数据
数据元素（DataElement）是计算机中描述数据的 基本单位。在大多数情况下，一个数据元素由若干个 数据项组成，数据项是数据不可分割的最小单位。如 对学生登记问题中，每个数据元素就可包括学号、姓 名、班级等，学号、姓名、班级等就称作该数据元素 的数据项。学生登记问题的数据结构是最简单的线性 表结构。
//在位置pos插入元素item
Datatype Delete(constintpos); void ClearList(void); }; //删除位置pos的元素并返回 //
2.1.5 模块化软件设计的特点
抽象数据类型是软件设计中的模块化方法，而模 块化的软件设计方法有以下特点： 1 代码可重用 所设计的抽象数据类型能像整数、浮点数、双精
非常广泛，可以认为它是描述客观事物的数字、字符、
图形、图像、声音等所有能输入到计算机中并能为计 算机接受的电子信号的集合。
它们依靠多媒体(多种传输信息媒体)的支持，能为
计算机所存储、处理和传输。在本书中所说的数据仅 指常规媒体所支持的数字、字符等信号，不包括其他
媒体所支持的声音、图形、图像等信号。
7 1 0 0 பைடு நூலகம் 1
王 兵 计 9 7 1
7 1 0 0 0 2
李 方 计 9 7 1
7 1 0 0 0 3
王 力 计 9 7 2
图2―2 单链表存储
操作集合不同的问题要求实现的操作集合将不同，
一个数据元素集合上允许（或要求）的所有操作构成 了该数据元素的操作集合。如上述学生登记问题就可
能要求实现插入、删除、打印等操作。
第2章 面向对象程序设计和算法性能分析
2.1 抽象数据类型 2.2 面向对象程序设计和类 2.3 对 象 2.4 算法、算法设计目标和算法性能分析
2.1 抽象数据类型
2.1.1 数据结构 计算机是对各种各样的数据进行处理的机器。在 计算机中如何组织数据，如何处理数据，从而如何更 好地利用数据是计算机学科的基本研究内容。 数据（ Data ）这个术语在计算机数据处理中含义
int ListEmpty(void)const;
//表空返回1；否则返回0
//返回元素item //返回位置pos
int Find(Datatype&item)const; DatatypeGetData(intpos)const;
voidInsert(const Datatype& item,int pos);