前言
第1章 绪论1
1.1 引言1
1.1.1 学习目的1
1.1.2 课程内容2
1.2 基本概念2
1.2.1 数据与数据结构2
1.2.2 数据类型与抽象数据类型6
1.3 算法9
1.3.1 算法的概念9
1.3.2 算法描述9
1.3.3 算法分析11
小结13
习题114
第2章 线性表17
2.1 线性表及其基本操作17
2.1.1 线性表的基本概念17
2.1.2 抽象数据类型描述18
2.1.3 线性表的存储和实现19
2.2 线性表的顺序存储19
2.2.1 顺序表19
2.2.2 顺序表的基本操作实现21
2.3 线性表的链式存储和实现25
2.3.1 单链表25
2.3.2 单链表的基本操作实现27
2.3.3 其他链表30
2.4 顺序表与链表的比较31
2.5 实验32
2.5.1 数组奇偶分割32
2.5.2 反转单向链表33
2.5.3 链表实现34
小结38
习题238
第3章 栈和队列41
3.1 栈41
3.1.1 栈的基本概念41
3.1.2 栈的抽象数据类型描述41
3.1.3 顺序栈43
3.1.4 链栈46
3.2 队列50
3.2.1 队列的基本概念50
3.2.2 队列的抽象数据类型描述50
3.2.3 顺序队列51
3.2.4 链队列55
3.2.5 优先级队列57
3.3 栈和队列的比较60
3.4 实验60
3.4.1 汉诺塔60
3.4.2 吃巧克力62
3.4.3 数头顶63
3.4.4 整数变换64
3.4.5 表达式求值66
3.4.6 用队列表示栈67
3.4.7 用栈表示队列69
3.4.8 层次遍历71
小结72
习题373
第4章 串和数组72
4.1 串76
4.1.1 串的基本概念76
4.1.2 串的抽象数据类型描述76
4.1.3 顺序串78
4.1.4 链串82
4.2 串的模式匹配82
4.2.1 Brute Force算法83
4.2.2 KMP算法83
4.3 数组87
4.3.1 数组的基本概念87
4.3.2 数组的特性88
4.3.3 数组的遍历88
4.4 特殊矩阵的压缩存储89
4.4.1 三角矩阵的压缩存储89
4.4.2 对称矩阵的压缩存储90
4.4.3 对角矩阵的压缩存储90
4.4.4 稀疏矩阵的压缩存储91
4.5 实验93
4.5.1 AZY的冒险岛93
4.5.2 最大连续子数组94
4.5.3 合并有序数组95
4.5.4 最长上升子序列96
小结97
习题497
第5章 树形结构101
5.1 树101
5.1.1 树的基本概念101
5.1.2 树的术语102
5.2 二叉树103
5.2.1 二叉树的基本概念103
5.2.2 二叉树的性质104
5.2.3 二叉树的存储结构105
5.2.4 二叉树的遍历106
5.2.5 二叉树遍历算法的应用110
5.2.6 二叉树的建立112
5.3 哈夫曼树及哈夫曼编码114
5.3.1 哈夫曼树的基本概念114
5.3.2 哈夫曼树的构造115
5.3.3 哈夫曼编码116
5.3.4 构造哈夫曼树和哈夫曼编码的类的描述116
5.4 树和森林118
5.4.1 树的存储结构118
5.4.2 树的遍历规则119
5.5 实验119
小结121
习题5121
第6章 图125
6.1 图概述125
6.1.1 图的基本概念125
6.1.2 图的抽象数据类型描述127
6.2 图的存储结构128
6.2.1 邻接矩阵128
6.2.2 邻接表132
6.3 图的遍历137
6.4 最小生成树141
6.4.1 最小生成树的基本概念141
6.4.2 Kruskal算法142
6.4.3 Prim算法142
6.5 最短路径144
6.5.1 单源最短路径144
6.5.2 求任意两个顶点间的最短路径146
6.6 拓扑排序和关键路径148
6.6.1 拓扑排序148
6.6.2 关键路径149
6.7 实验151
小结152
习题6153
第7章 排序156
7.1 排序概述156
7.1.1 排序的基本概念156
7.1.2 排序算法的性能评价156
7.1.3 待排序的记录和顺序表的类描述156
7.2 插入排序157
7.2.1 直接插入排序157
7.2.2 希尔排序159
7.3 交换排序160
7.3.1 冒泡排序160
7.3.2 快速排序161
7.4 选择排序164
7.4.1 直接选择排序164
7.4.2 堆排序166
7.5 归并排序168
7.6 实验172
7.6.1 插入排序172
7.6.2 链表排序173
7.6.3 区间排序174
小结175
习题7176
第8章 查找179
8.1 查找的基本概念179
8.1.1 什么是查找179
8.1.2 查找表179
8.1.3 平均查找长度180
8.2 静态查找表180
8.2.1 顺序查找180
8.2.2 二分查找181
8.2.3 分块查找182
8.3 动态查找表182
8.3.1 二叉排序树查找183
8.3.2 平衡二叉树187
8.3.3 B-树和B+树189
8.4 哈希表查找190
8.4.1 哈希表的概念190
8.4.2 哈希函数190
8.4.3 解决冲突的方法191
8.4.4 哈希表查找性能分析192
8.5 实验195
8.5.1 寻找山形数组的顶点195
8.5.2 寻找和为指定值的数组元素195
8.5.3 寻找数组元素196
小结197
习题8198
附录200
附录A 名校数据结构程序设计考研真题解答（部分）200
附录B 名词索引206
参考文献209