第1章绪论 1.1数据结构的地位 12基本概念和术语 1.2.1关于数据结构的几个基本概念 1.22数据结构的种类。 3 1.23数据结构的形式化定义 1.24数据的物理结构 1.2.5抽象数据类型ADT 5 1.3数学预备知识 6 1.3.1集合 .6 1.32常用的数学术语 .6 133对数 、> 1.4算法和算法分析 1.4.1算法 7 1.4.2算法设计的要求 1.43算法时间效率的度量. 1.4.3算法的空间复杂度(space complexity) 14 第2音线性表 2.1线性表的类型定义 15 2.2线性表的顺序存储和基本操作的实现 .17 2.2.1顺序存储 17 2.22顺序存储结构下基本操作分析 18 2.2.3源码实现 22.4顺序表应用举例 2.3线性表的链式表示和实现 3 2.3.1基本术语 3 2.3.2链式存储结构下基本操作分析 34 .56 31相 56 3.11基本概念。 56 3.12抽象数据类型栈的定义 3.2栈的顺序存储. 58 321栈的顺序存储定义 3.22基本操作分析 59 323源玛实现 60 33钱的链式存储 63 3.4栈的应用举例 3.4.1数制转换 67
1 第 1 章 绪论.1 1.1 数据结构的地位.1 1.2 基本概念和术语.2 1.2.1 关于数据结构的几个基本概念. 2 1.2.2 数据结构的种类.2 1.2.3 数据结构的形式化定义. 3 1.2.4 数据的物理结构.4 1.2.5 抽象数据类型 ADT. 5 1.3 数学预备知识.6 1.3.1 集合.6 1.3.2 常用的数学术语.6 1.3.3 对数.7 1.4 算法和算法分析.7 1.4.1 算法.7 1.4.2 算法设计的要求. 10 1.4.3 算法时间效率的度量.11 1.4.3 算法的空间复杂度（space complexity）. 14 第 2 章 线性表.15 2.1 线性表的类型定义. 15 2.2 线性表的顺序存储和基本操作的实现. 17 2.2.1 顺序存储.17 2.2.2 顺序存储结构下基本操作分析. 18 2.2.3 源码实现.20 2.2.4 顺序表应用举例. 29 2.3 线性表的链式表示和实现. 31 2.3.1 基本术语.31 2.3.2 链式存储结构下基本操作分析. 34 2.4 一元多项式的表示和相加. 52 第 3 章 栈和队列.56 3.1 栈.56 3.1.1 基本概念：.56 3.1.2 抽象数据类型栈的定义. 57 3.2 栈的顺序存储.58 3.2.1 栈的顺序存储定义. 58 3.2.2 基本操作分析.59 3.2.3 源码实现.60 3.3 栈的链式存储.63 3.4 栈的应用举例.67 3.4.1 数制转换.67
3.4.2表达式求值 68 3.5队列 71 3.51基本概念 .71 352抽象数据类型队列的定义 72 3.5.3队列的链式存储和实现 73 3.3.4队列的顺序存储和实现 80 3.4队列的应用。 "8o 第四章串 91 4.1串类型的定义 .92 411基本概念 .92 412由的存储方式 92 4.1.3顺序存储结构下基本操作的实现 .93 4.14JAVA语言中的字符串类型 98 第五章数组和广义表 10 51粉斯组 101 5.2数组的存储. .101 53矩阵 104 5.3.1特殊矩阵的压缩存储 104 5.4义表 122 54.1广义表的定义 122 5.42广义表的存储结构 124 5.5m元多项式的表示 126 5.6求广义表深度基本操作的实现 127 第六章树和二叉树」 132 6.1树的定义和基本术语 132 6.1.1树的定义 132 612树的基本术语 133 6.13树的表示形式 134 6.14抽象数据类型树的定义. .134 6,2二叉树(Binary Tree)) 135 621二叉树的定义 135 6.2.2二叉树的性质」 137 623二叉树的存储结构 142 6.3遍历二叉树(Traversing Binary Tree)和线索二叉树 150 6.3.1遍历二叉树(Traversing Binary Tree). 150 6.3.2二叉线索链表 155 64树和森林 ,161 6.4.1树的存储 161 6.42森林与二叉树的转换 166
2 3.4.2 表达式求值.68 3.5 队列.71 3.5.1 基本概念.71 3.5.2 抽象数据类型队列的定义. 72 3.5.3 队列的链式存储和实现. 73 3.3.4 队列的顺序存储和实现. 80 3.4 队列的应用.89 第四章 串.91 4.1 串类型的定义.92 4.1.1 基本概念.92 4.1.2 串的存储方式.92 4.1.3 顺序存储结构下基本操作的实现. 93 4.1.4 JAVA 语言中的字符串类型. 98 第五章 数组和广义表. 101 5.1 数组.101 5.2 数组的存储.101 5.3 矩阵.104 5.3.1 特殊矩阵的压缩存储. 104 5.4 广义表.122 5.4.1 广义表的定义.122 5.4.2 广义表的存储结构. 124 5. 5 m 元多项式的表示. 126 5.6 求广义表深度基本操作的实现. 127 第六章 树和二叉树.132 6.1 树的定义和基本术语. 132 6.1.1 树的定义.132 6.1.2 树的基本术语.133 6.1.3 树的表示形式.134 6.1.4 抽象数据类型树的定义. 134 6.2 二叉树 (Binary Tree).135 6.2.1 二叉树的定义.135 6.2.2 二叉树的性质.137 6.2.3 二叉树的存储结构. 142 6.3 遍历二叉树 (Traversing Binary Tree) 和线索二叉树. 150 6.3.1 遍历二叉树 (Traversing Binary Tree). 150 6.3.2 二叉线索链表.155 6.4 树和森林.161 6.4.1 树的存储.161 6.4.2 森林与二叉树的转换. 166
6.43树与森林的骗历 169 6.5树与等价问题. 170 6.6赫夫曼树(Huffman Tree)及其应用. 178 6.6.1路径长度(Path Length) 178 6.6.2带权路径长度(Weighted Path Length,WPL). .178 6.6.3 Huffman(哈夫曼)树 179 6.6.4赫夫曼树的应用. 179 665顶码实现 184 6.7回溯法与树的遍历. 190 68树的计数 193 第七章图 错误！未定义书签。 7.1图的定义和术语 错操！未定义书签 72图的存储结构. 错误！未定义书签。 7.2.1邻接矩阵(adjacency matrix) 错误】未定义书签 7.2.2邻接表(adjacency 错误！未定义书签 7.2.3邻接多重表 错误！未定义书签 7.2.4十字链表 错误！未定义书签。 7.3图的遍历. 错误！未定义书签。 7.3.1深度优先遍历 错误！未定义书签 7.3.2广度优先遍历. 错误！未定义书签。 7.4图的连通性问题 错误1 未定义书签 7.4.1无向图的连通分量和生成树 错误！未定义书签 7.42有向图的强连通分量 错误！未定义书签 7.4.3最小生成树Minimum Spanning Cost Tree). 错误！未定义书签。 7,4.4关节点和重连通分量 错误！未定义书签 7.5有向无环图及其应用 错误未定义书签。 7.5.1拓扑排序」 错误！未定义书签 7.52关键路径 错误！未定义书签 7.6最短路径 错误！未定义书签 7.6.】某一顶点到其余各点最短路径 错误未定义书签。 7.6.2每一对顶点之间的最短路径 错误！未定义书签 第8章查找 错误！未定义书签 8.1查找的概念 错误未定义书签。 8.2静态查找。 错误！未定义书签 821顺序查找 错误！未定义书签。 8.2.2折半查找(Binary Search). 错误！未定义书签。 823分块杳找 错误」未定义书答 8.3动态查找 错误！未定义书签 8.3.1二叉排序树(BST)的定义. 错误！未定义书签
3 6.4.3 树与森林的遍历. 169 6.5 树与等价问题.170 6.6 赫夫曼树 (Huffman Tree)及其应用. 178 6.6.1 路径长度 (Path Length). 178 6.6.2 带权路径长度 ( Weighted Path Length, WPL ).178 6.6.3 Huffman(哈夫曼)树. 179 6.6.4 赫夫曼树的应用. 179 6.6.5 源码实现.184 6.7 回溯法与树的遍历. 190 6.8 树的计数.193 第七章 图. 错误！未定义书签。 7.1 图的定义和术语. 错误！未定义书签。 7.2 图的存储结构. 错误！未定义书签。 7.2.1 邻接矩阵（ adjacency matrix）.错误！未定义书签。 7.2.2 邻接表（adjacency list）. 错误！未定义书签。 7.2.3 邻接多重表. 错误！未定义书签。 7.2.4 十字链表. 错误！未定义书签。 7.3 图的遍历. 错误！未定义书签。 7.3.1 深度优先遍历. 错误！未定义书签。 7.3.2 广度优先遍历. 错误！未定义书签。 7.4 图的连通性问题. 错误！未定义书签。 7.4.1 无向图的连通分量和生成树.错误！未定义书签。 7.4.2 有向图的强连通分量.错误！未定义书签。 7.4.3 最小生成树(Minimum Spanning Cost Tree).错误！未定义书签。 7.4.4 关节点和重连通分量.错误！未定义书签。 7.5 有向无环图及其应用.错误！未定义书签。 7.5.1 拓扑排序. 错误！未定义书签。 7.5.2 关键路径. 错误！未定义书签。 7.6 最短路径. 错误！未定义书签。 7.6.1 某一顶点到其余各点最短路径.错误！未定义书签。 7.6.2 每一对顶点之间的最短路径.错误！未定义书签。 第 8 章 查找. 错误！未定义书签。 8.1 查找的概念. 错误！未定义书签。 8.2 静态查找. 错误！未定义书签。 8.2.1 顺序查找. 错误！未定义书签。 8.2.2 折半查找(Binary Search).错误！未定义书签。 8.2.3 分块查找. 错误！未定义书签。 8.3 动态查找. 错误！未定义书签。 8.3.1 二叉排序树(BST)的定义.错误！未定义书签
8.3.2BST树的查找 错误！未定义书签 83.3BST树的插入 错误！未定义书签。 8.34BST树的删除 错误！未定义书签 8.3.5BST树的查找分析 错误！未定义书签 8.4平衡二叉树(AVL). 错误！未定义书签 8.4.1平衡二叉树的定义 错误！未定义书签 8.4.2平衡化旋转 错误！未定义书签 8.4.3平衡二叉排序树的插入 错误！未定义书签 8.4.4平衡二叉排序树构造实例 错误！未定义书签 8.45平衡二叉树查找分析 错误！未定义书签 85索引杳战 错误！未定义书签。 8.5.1顺序索引表 错误！未定义书签。 852树形索表 错误！未定义书签 8.6哈希（散列）查找， 错误！未定义书签。 861基本概今 错误】未定义书答 8.6.2哈希函数的构造 错误1未定义书签。 863冲突处理的方法 错误」未定义书答 8.6.4哈希查找过程及分析 错误！未定义书签 第9章内部排序 错误】未定义书签 9.1排序的基本概念 错误！未定义书签 9.2插入排序 错误！未定义书签 9.2.1直接插入排序 错误！未定义书签。 9.2.2其它插入排序 错误！未定义书签 9.23希尔排序 错误！未定义书签 9.3快速排序 错误！未定义书签 9.3.1冒泡排序 错误！未定义书签 9.3.2快速排序。 错误！未定义书签 9.4选择排序 错误！未定义书签 9.4.1简单选择排序 错误！未定义书签 9.4.2树形选择排序 错误！ 未定义书签 9.4.3堆排序. 错误！未定义书签 9.5归并排序 错误！未定义书签 96其数排序 错误！未定义书签。 9.6.1多关键字排序 错误！未定义书签。 9.6.2链式基数排序 错误！未定义书签。 9.7各种内部排序的比较 错误！未定义书签 第10章文件 错误！未定义书签 10.1文件的概念 错误！未定义书签。 10.2顺序文件 错误！未定义书签
4 8.3.2 BST 树的查找.错误！未定义书签。 8.3.3 BST 树的插入.错误！未定义书签。 8.3.4 BST 树的删除.错误！未定义书签。 8.3.5 BST 树的查找分析.错误！未定义书签。 8.4 平衡二叉树(AVL).错误！未定义书签。 8.4.1 平衡二叉树的定义.错误！未定义书签。 8.4.2 平衡化旋转. 错误！未定义书签。 8.4.3 平衡二叉排序树的插入.错误！未定义书签。 8.4.4 平衡二叉排序树构造实例.错误！未定义书签。 8.4.5 平衡二叉树查找分析.错误！未定义书签。 8. 5 索引查找. 错误！未定义书签。 8.5.1 顺序索引表. 错误！未定义书签。 8.5.2 树形索引表. 错误！未定义书签。 8. 6 哈希(散列)查找.错误！未定义书签。 8.6.1 基本概念. 错误！未定义书签。 8.6.2 哈希函数的构造.错误！未定义书签。 8.6.3 冲突处理的方法.错误！未定义书签。 8.6.4 哈希查找过程及分析.错误！未定义书签。 第 9 章 内部排序. 错误！未定义书签。 9.1 排序的基本概念. 错误！未定义书签。 9.2 插入排序. 错误！未定义书签。 9.2.1 直接插入排序. 错误！未定义书签。 9.2.2 其它插入排序. 错误！未定义书签。 9.2.3 希尔排序. 错误！未定义书签。 9.3 快速排序. 错误！未定义书签。 9.3.1 冒泡排序. 错误！未定义书签。 9.3.2 快速排序. 错误！未定义书签。 9. 4 选择排序. 错误！未定义书签。 9.4.1 简单选择排序. 错误！未定义书签。 9.4.2 树形选择排序. 错误！未定义书签。 9.4.3 堆排序. 错误！未定义书签。 9. 5 归并排序. 错误！未定义书签。 9. 6 基数排序. 错误！未定义书签。 9.6.1 多关键字排序. 错误！未定义书签。 9.6.2 链式基数排序. 错误！未定义书签。 9.7 各种内部排序的比较.错误！未定义书签。 第 10 章 文件. 错误！未定义书签。 10. 1 文件的概念. 错误！未定义书签。 10. 2 顺序文件. 错误！未定义书签
10.3索引文件， 错误1未定义书签 10.4ISAM文件 错误！未定义书签 10.5VSAM文件. 错误！未定义书签。 10.6直接存取文件 错误未定义书签。 10.7多关键字文件 错误！未定义书签。 10.7.1多重表文件 错误！未定义书签。 10.7.2倒排文件. 错误！未定义书签 10.8外部排序 错误！未定义书签 10.8.1外部排序方法 错误！未定义书签。 10.8.2外排序的时间分析 错误1未定义书签
5 10. 3 索引文件. 错误！未定义书签。 10. 4 ISAM 文件. 错误！未定义书签。 10.5 VSAM 文件.错误！未定义书签。 10. 6 直接存取文件. 错误！未定义书签。 10. 7 多关键字文件. 错误！未定义书签。 10. 7.1 多重表文件. 错误！未定义书签。 10.7.2 倒排文件. 错误！未定义书签。 10.8 外部排序. 错误！未定义书签。 10.8.1 外部排序方法. 错误！未定义书签。 10.8.2 外排序的时间分析.错误！未定义书签