第1章 绪论1   1.1 数据结构的研究内容1   1.2 基本概念和术语4     1.2.1 数据、数据元素、数据项和数据对象4     1.2.2 数据结构5     1.2.3 数据类型和抽象数据类型10   1.3 算法和算法分析13     1.3.1 算法的定义及特性13     1.3.2 算法评价的基本标准14     1.3.3 算法的时间复杂度15     1.3.4 算法的空间复杂度17   小结19   习题119 第2章 线性表21   2.1 线性表的类型定义21     2.1.1 线性表的定义22     2.1.2 线性表的抽象数据类型描述22   2.2 线性表的顺序存储结构26     2.2.1 线性表的顺序存储表示27     2.2.2 顺序表中基本运算的实现27     2.2.3 顺序表的特点33     2.2.4 案例分析与实现33   2.3 线性表的链式存储结构34     2.3.1 线性表的链式存储表示36     2.3.2 线性表基本运算在单链表中的实现37     2.3.3 循环链表43     2.3.4 双向链表44     2.3.5 静态链表48     2.3.6 案例分析50   小结55   习题256 第3章 栈和队列58   3.1 栈和队列的定义和特点58     3.1.1 栈的定义和特点58     3.1.2 队列的定义和特点59   3.2 栈的表示和操作实现60     3.2.1 栈的抽象类型定义60     3.2.2 顺序栈的表示和实现61     3.2.3 链栈的表示和实现64     3.2.4 案例分析与实现66   3.3 栈与递归68     3.3.1 采用递归算法解决的问题69     3.3.2 递归过程与递归工作栈71     3.3.3 递归算法的效率分析73     3.3.4 将递归转换为非递归的方法73   3.4 队列的表示和操作实现75     3.4.1 队列的抽象类型定义75     3.4.2 循环队列——队列的顺序表示和实现76     3.4.3 链队——队列的链式表示和实现79     3.4.4 其他队列83   3.5 典型栈和队列案例分析与实现84     3.5.1 栈的典型案例84     3.5.2 队列的典型案例93   小结95   习题396 第4章 串、数组和广义表97   4.1 串的定义97     4.1.1 串的定义97     4.1.2 串的抽象数据类型描述98   4.2 串的存储结构及其运算99     4.2.1 串的定长顺序存储结构100     4.2.2 串的堆分配存储结构 102     4.2.3 串的块链存储结构105     4.2.4 串的模式匹配算法107   4.3 数组112     4.3.1 数组的类型定义112     4.3.2 数组的顺序存储113     4.3.3 特殊矩阵的压缩存储114   4.4 广义表120     4.4.1 广义表的定义120     4.4.2 广义表的存储结构121   4.5 案例分析与实现123   小结128   习题4128 第5章 树和二叉树130   5.1 树130     5.1.1 树的基本概念130     5.1.2 树的抽象数据类型描述133     5.1.3 树的遍历134     5.1.4 树的存储结构134   5.2 二叉树136     5.2.1 二叉树的定义136     5.2.2  二叉树的主要性质137     5.2.3 二叉树的存储结构139     5.2.4 树与二叉树之间的转换142     5.2.5 二叉树的基本操作及实现143   5.3 二叉树的遍历149     5.3.1 二叉树的遍历方法及递归实现149     5.3.2 二叉树遍历的非递归实现151   5.4 线索二叉树153     5.4.1 线索二叉树的概念153     5.4.2 二叉树的线索化实现155     5.4.3 线索二叉树上的运算157   5.5 哈夫曼树及其应用157     5.5.1 哈夫曼树概念158     5.5.2 哈夫曼树构造算法158     5.5.3 哈夫曼编码161   5.6 案例分析——电文的编码和译码163   小结166   习题5167 第6章 图168   6.1 图的定义和基本术语168     6.1.1 图的定义168     6.1.2 图的抽象数据类型描述168     6.1.3 图的基本术语169   6.2 图的存储结构171     6.2.1 邻接矩阵171     6.2.2 邻接表172     6.2.3 十字链表174     6.2.4 邻接多重表174     6.2.5 图的存储结构设计举例176   6.3 图的遍历177     6.3.1 深度优先搜索177     6.3.2 广度优先搜索178     6.3.3 非连通图的遍历179     6.3.4 图遍历算法的应用179   6.4 图的应用182     6.4.1 最小生成树182     6.4.2 最短路径188     6.4.3 拓扑排序196     6.4.4 关键路径198   6.5 案例分析与实现201   小结206   习题6207 第7章 查找209   7.1 查找的基本概念209   7.2 线性表的查找210     7.2.1 顺序查找211     7.2.2 折半查找212     7.2.3 分块查找214   7.3 树表的查找215     7.3.1 二叉排序树216     7.3.2 平衡二叉树220     7.3.3 B-树222     7.3.4 B+树224   7.4 哈希表的查找226     7.4.1 哈希表的基本概念226     7.4.2 哈希函数的构造方法227     7.4.3 处理冲突的方法228     7.4.4 散列表的查找230   小结231   习题7232 第8章 排序234   8.1 基本概念和排序方法概述234   8.2 插入排序235     8.2.1 直接插入排序235     8.2.2 折半插入排序237     8.2.3 希尔排序238   8.3 交换排序240     8.3.1 冒泡排序240     8.3.2 快速排序242   8.4 选择排序245     8.4.1 简单选择排序246     8.4.2 树形选择排序247     8.4.3 堆排序248   8.5 归并排序253   8.6 基数排序256     8.6.1 多关键字的排序256     8.6.2 链式基数排序259   8.7 外部排序262     8.7.1 外部排序的基本方法262     8.7.2 多路归并排序263     8.7.3 置换选择排序265   小结268   习题8269 附录A C语言常用语法提要271 附录B C语言常用库函数279 附录C 实验报告模板283 参考文献286