第1章 绪论 1
1.1数据结构的概念 1
1.1.1 为什么要学习数据结构 1
1.1.2有关概念和术语 4
1.1.3数据结构课程的内容 6
1.2抽象数据类型 7
1.2.1 数据类型 7
1.2.2抽象数据类型 7
1.3算法和算法分析 8
1.3.1 算法特性 8
1.3.2算法描述 9
1.3.3算法性能分析与度量 9
第2章 线性表 11
2.1线性表的逻辑结构 11
2.1.1线性表的定义 11
2.1.2线性表的基本操作 11
2.2.1顺序表 12
2.2线性表的顺序存储及运算实现 12
2.2.2 顺序表上基本运算的实现 14
2.2.3顺序表应用举例 18
2.3线性表的链式存储和运算实现 20
2.3.1单链表 20
2.3.2单链表上基本运算的实现 22
2.3.3循环链表 28
2.3.4 双向链表 29
2.3.5静态链表 30
2.3.6单链表应用举例 32
2.4 顺序表和链表的比较 34
2.5 上机实训 35
2.6本章习题 36
第3章 栈和队列 39
3.1 栈 39
3.1.1栈的定义及基本运算 39
3.1.2栈的存储结构和运算实现 40
3.2栈的应用举例 44
3.3.1 队列的定义及基本运算 48
3.3 队列 48
3.3.2队列的存储结构及运算实现 49
3.4队列应用举例 56
3.5上机实训 58
3.6本章习题 60
第4章 串 63
4.1 串类型的定义 63
4.2串的存储结构 65
4.2.1 定长顺序存储结构 66
4.2.2堆分配存储表示 67
4.2.3 串的块链存储表示 70
4.3串操作应用举例 71
4.4上机实训 71
4.5本章习题 72
第5章 数组和广义表 73
5.1数组的定义及其基本操作 73
5.1.1数组的定义 73
5.2数组的顺序存储结构 74
5.1.2数组的基本操作 74
5.3矩阵的压缩存储 76
5.3.1特殊矩阵的压缩存储 76
5.3.2稀疏矩阵的压缩存储 78
5.4 广义表的概念 87
5.5上机实训 88
5.6本章习题 89
第6章 树和二叉树 90
6.1树的定义 90
6.1.1树的定义 90
6.1.2树的表示形式 91
6.1.3树的常用术语 92
6.1.4树的基本操作 92
6.2二叉树 93
6.2.1二叉树的定义 93
6.2.2二叉树的性质 95
6.2.3二叉树的存储结构 97
6.3.1遍历二叉树 100
6.3遍历二叉树和线索二叉树 100
6.3.2线索二叉树 102
6.4树、森林和二叉树的关系 105
6.4.1树的存储结构 105
6.4.2森林与二叉树的转换 109
6.4.3树和森林的遍历 112
6.5 哈夫曼树及其应用 113
6.5.1 哈夫曼树的定义 113
6.5.2 哈夫曼编码 115
6.6上机实训 116
6.7本章习题 117
第7章 图 119
7.1图的基本概念 119
7.1.1图的定义 119
7.1.2图的基本术语 120
7.2图的存储结构 122
7.2.1邻接矩阵 122
7.2.2邻接表 124
7.2.3 边集数组 126
7.3图的遍历 127
7.3.1深度优先搜索 127
7.3.2广度优先搜索 128
7.4 图的生成树和最小生成树 130
7.4.1 概念 130
7.4.2普里姆算法 130
7.4.3克鲁斯卡尔算法 133
7.5.1 求某个源点到其他顶点的最短路径 135
7.5最短路径 135
7.5.2求每对顶点之间的最短路径 137
7.6拓扑排序 138
7.6.1顶点活动网（AOV网） 138
7.6.2拓扑排序 139
7.7上机实训 142
7.8本章习题 143
第8章 查找 145
8.1查找的基本概念 145
8.2.1顺序查找法 147
8.2静态查找表 147
8.2.2折半查找法 148
8.2.3分块查找法 150
8.3动态查找表 152
8.3.1二叉排序树 152
8.3.2平衡二叉树 158
8.4 哈希查找 162
8.4.1 哈希函数的概念 162
8.4.2 哈希函数的构造方法 162
8.4.3处理冲突的方法 164
8.4.4 哈希表的查找过程及性能分析 168
8.5上机实训 170
8.6本章习题 171
第9章 排序 174
9.1基本概念 174
9.1.1排序的定义 174
9.1.3 内部排序和外部排序 175
9.1.4排序方法的性能 175
9.1.2排序方法的稳定性 175
9.2插入排序 176
9.2.1直接插入排序 176
9.2.2希尔排序 177
9.3交换排序 179
9.3.1冒泡排序 179
9.3.2快速排序 180
9.4 选择排序法 183
9.4.1直接选择排序 183
9.4.2树型选择排序 184
9.4.3 堆排序 187
9.5 归并排序法 193
9.5.1两个有序序列的归并 193
9.5.2一趟归并排序 193
9.6各种内部排序法的比较 195
9.7上机实训 196
9.8本章习题 197
附录 参考答案 199
参考文献 203