《数据结构(Java版)(第3版)》附录G

章 节 第2章 线性表 2.2 顺序表 类 名 LList SeqList Node 2.3.2 单链表 SinglyLinkedList SortedSinglyLinkedList CirSinglyLinkedList DLinkNode 2.3.3 双链表 CirDoublyLinkedList SortedDoublyLinkedList 说 明 线性表接口，描述线性表抽象数据类型 顺序表类，实现LList接口，继承AbstractCollection类 单链表结点类 单链表类，实现LList接口，继承AbstractCollection类 排序单链表类，继承SinglyLinkedList类；T实现Comparable接口 循环单链表类，实现LList接口 双链表结点类 循环双链表类，实现LList接口 排序循环双链表类，继承CirDoublyLinkedList类； T实现Comparable接口 Addible TermX 2.4多项式 PolySLinkedList 可相加接口 一元多项式的项类，实现Comparable和Addible接口 多项式排序单链表类，继承SortedSinglyLinkedList类； T实现Comparable和Addible接口 Polynomial TermXY SString 第3章 串 MyString MyStringBuffer 多项式类 二元多项式的项类，继承TermX类 字符串接口，描述字符串抽象数据类型 常量字符串类，实现SString接口，模拟java.lang.String类实现 变量字符串类，实现SString接口，模拟java.lang.StringBuffer类实现 SStack 第4章 4.1 栈 SeqStack LinkedStack QQueue 4.2 队列 SeqQueue LinkedQueue 4.3 优先队列 第5章 5.1 多维数组 5.2 特殊矩阵的压缩存储 PriorityQueue Matrix DownTriangleMatrix Triple 5.2.2稀疏矩阵的压缩存储 SeqSparseMatrix LinkedSparseMatrix CrossNode 栈接口，描述栈抽象数据类型 顺序栈类，实现SStack接口 链式栈类，实现SStack接口 队列接口，描述队列抽象数据类型 顺序循环队列，实现QQueue接口 链式队列，实现QQueue接口 优先队列，实现QQueue接口 矩阵类 线性压缩存储的下三角矩阵类 稀疏矩阵非零元素的三元组类，实现Comparable和Addible接口 稀疏矩阵三元组顺序表类 采用三元组行的单链表存储的稀疏矩阵类 稀疏矩阵十字链表结点类 ·424·

CrossLinkedSparseMatrix GGenList 5.3 广义表 GenListNode GenList 6.1 树 6.2 二叉树 TTree BinaryTTree BinaryTreeNode 6.3.2 二叉树的二叉链表实现 BinaryTree CompleteBinaryTree 6.3.3 二叉树的三叉链表实现 TriNode TriBinaryTree ThreadNode ThreadBinaryTree TriElement HuffmanTree TreeNode Tree GGraph Edge AdjMatrixGraph Vertex AdjListGraph AbstractGraph HashSet BinarySortTree AbstractCCollection AbstractLList MinHeap 10.3.3 贪心法 MinSpanTree UnionFindSet 采用三元组十字链表存储的稀疏矩阵类 广义表接口，描述广义表抽象数据类型 广义表双链表示的结点类 双链表示的广义表类，实现GGenList接口 树接口，描述树抽象数据类型 二叉树接口，描述二叉树抽象数据类型 二叉树的二叉链表结点类 二叉链表存储的二叉树类，实现BinaryTTree接口 二叉链表表示的完全二叉树类，继承BinaryTree类 二叉树的三叉链表结点类 三叉链表存储的二叉树类，实现BinaryTTree接口 线索二叉树的二叉链表结点类 中序线索二叉树类 二叉树的静态三叉链表结点 哈夫曼树类 树的孩子兄弟链表结点类 树类，实现TTree接口 图接口，描述图抽象数据类型 带权值的边类 邻接矩阵表示的图类，继承AbstractGraph类 顶点表元素类 邻接表表示的图类，继承AbstractGraph类 抽象图类，实现GGraph接口 采用链地址法的散列表类 二叉排序树类，继承BinaryTree类 抽象集合类，实现java.lang.Iterable可迭代接口 抽象列表类，继承AbstractCCollection类 最小堆类 最小生成树类 并查集 6.4 线索二叉树 6.5 Huffman编码与Huffman树 6.6.3 树的孩子兄弟链表实现 第7章 图 7.2.1 图的邻接矩阵表示 7.2.2 图的邻接表表示和实现 7.3 图的遍历 8.3.4 构造链地址法的散列表 8.4.1 二叉排序树 10.2 实现迭代器

·425·

本书声明的线性表、字符串、栈和队列、广义表、树和二叉树、图等接口和类的层次关系如图G-1～G-6所示。

java.lang.Iterable可迭代接口实现AbstractCCollection抽象集合类继承AbstractLList抽象列表类继承SeqList顺序表类实现LList线性表接口实现实现CirDoublyLinkedList循环双链表类继承SortedDoublyLinkedList排序循环双链表类

SinglyLinkedList单链表类继承SortedSinglyLinkedList排序单链表类继承PolySLinkedList多项式排序单链表类图G-1 线性表接口和类的层次关系

SString字符串接口实现MyString常量字符串类实现MyStringBuffer变量字符串类

图G-2 字符串接口和类的层次关系

SStack栈接口实现SeqStack顺序栈类实现LinkedStack链式栈类实现SeqQueue顺序队列类QQueue队列接口实现LinkedQueue链式队列类实现PriorityQueue优先队列类

图G-3 栈、队列接口和类的层次关系

GGenList广义表接口实现GenList广义表类

图G-4 广义表接口和类的层次关系

·426·

BinaryTTreeTTree二叉树接口树接口实现实现BinaryTreeTree二叉链表存储的二叉树类孩子兄弟链表存储的树类

继承继承CompleteBinaryTreeBinarySortTree完全二叉树类二叉排序树类图G-5 树、二叉树接口和类的层次关系

GGraph图接口实现AbstractGraph抽象图类

继承继承AdjMatrixGraphAdjListGraph邻接矩阵表示的图类邻接表表示的图类图G-6 图接口和类的层次关系

427·

·