数据结构(第2版)

本书介绍了数据结构的基本概念、基本理论和基本方法，包括线性表、栈和队列、字符串、多维矩阵和广义表、树和二叉树、图、排序、查找、索引技术以及相关操作的算法，并分析了算法复杂度，用应用实例说明了常用数据结构在计算机中的存储和实现。书中算法采用C++语言描述，适合在MSVC++下使用，也可做适当修改后在DEVC++或MSVC++.NET中使用。全书内容由浅入深，概念清晰，强调程序设计书写风格，提高算法可读性和实用性。本书可作为本科、专科计算机及相关专业的数据结构课程的教材，也可作为从事计算机软件工作人员的参考书。

第1章绪论1
1.1数据结构的研究对象1
1.2概念术语2
1.3算法和算法描述9
1.3.1算法的概念9
1.3.2算法的描述方法9
1.4算法的评价方法11
1.4.1评价算法的准则11
1.4.2算法的复杂度11
1.4.3算法描写的一些说明17
本章小结和学习要点19
习题119
思考题121
上机题121
实验121
第2章线性表22
2.1线性表及其基本操作22
2.1.1线性表的逻辑结构定义22
2.1.2线性表的抽象数据类型定义23
2.2线性表的顺序存储结构——顺序表25
2.2.1顺序表的基本表示25
2.2.2顺序表的基本操作28
2.2.3顺序表下的其他操作33
2.3线性表的链式存储结构35
2.3.1单链表35
2.3.2循环单链表44
2.3.3双链表及循环双链表45
2.3.4静态链表*46
2.4线性表的应用48
2.4.1删除整数表中值相同而多余的元素48
2.4.2合并两个有序单链表48
2.4.3逆置单链表49
2.4.4约瑟夫环问题求解50
2.5顺序表和单链表的比较51
2.5.1时间性能比较51
2.5.2空间性能比较52
本章小结和学习要点53
习题253
思考题257
上机题257
实验257
第3章栈和队列58
3.1栈58
3.1.1栈的逻辑定义58
3.1.2顺序栈58
3.1.3链栈63
3.2队列66
3.2.1队列的定义66
3.2.2队列的顺序存储结构66
3.2.3队列的链式存储结构70
3.3栈和队列的应用73
3.3.1栈的应用——算术表达式求值73
3.3.2队列的应用75
3.3.3栈和队列联合应用——停车场管理78
本章小结和学习要点79
习题380
思考题382
上机题382
实验382
第4章字符串83
4.1字符串的逻辑结构83
4.2字符串的顺序存储结构84
4.3字符串的链式存储结构85
4.4串的模式匹配算法86
4.5字符串的应用91
4.5.1大整数加法91
4.5.2名字#征数92
本章小结和学习要点92
习题492
思考题494
上机题494
实验494
第5章多维矩阵和广义表95
5.1多维矩阵的操作和简单存储95
5.2矩阵的压缩存储98
5.2.1特殊矩阵的压缩存储99
5.2.2稀疏矩阵的压缩存储102
*5.3广义表106
5.3.1广义表的概念106
5.3.2广义表的操作107
本章小结和学习要点108
习题5108
思考题5110
上机题5110
实验5110
第6章树和二叉树111
6.1树111
6.2二叉树114
6.2.1二叉树的定义和基本操作114
6.2.2二叉树的性质115
6.2.3二叉树的存储结构118
6.3遍历和建立二叉树122
6.3.1遍历二叉树122
6.3.2建立和释放二叉链表126
6.3.3二叉树的三种遍历的非递归算法128
6.3.4二叉树的其他应用算法130
6.4树和森林131
6.5哈夫曼树及其应用137
6.6森林结构的置信度推理142
本章小结和学习要点144
习题6145
思考题6149
上机题6149
实验6149
第7章图150
7.1图的定义、基本术语和操作150
7.2图的存储结构151
7.2.1邻接矩阵151
7.2.2边数组152
7.2.3邻接表152
7.2.4图的十字链表157
7.3图的遍历159
7.3.1深度优先搜索遍历图159
7.3.2广度优先搜索遍历图161
7.3.3图的遍历162
7.4图的连通性和生成树163
7.5最小生成树164
7.5.1普里姆算法164
7.5.2克鲁斯卡尔算法167
7.6最短路径问题169
7.6.1求单源顶点最短路径的Dijkstra算法169
7.6.2求顶点间最短路径的Floyd算法172
7.7拓扑排序174
7.8求关键路径175
7.9图的着色问题180
7.10隐式图与启发式搜索180
本章小结和学习要点183
习题7184
思考题7188
上机题7189
实验7189
第8章排序190
8.1排序的基本概念190
8.2插入排序191
8.2.1直接插入排序191
8.2.2谢尔排序194
8.3选择排序195
8.3.1直接选择排序195
8.3.2堆排序197
8.4交换排序200
8.4.1胃泡排序200
8.4.2快速排序202
8.5归并排序205
8.6基数排序207
8.7各种内排序算法的比较208
本章小结和学习要点211
习题8212
思考题8216
上机题8217
实验8217
第9章查找218
9.1查找的基本概念和术语218
9.2以顺序表为基础的查找219
9.2.1顺序表的顺序查找219
9.2.2有序表的二分法查找222
9.2.3分块查找226
9.3树形结构的查找228
9.3.1二叉排序树229
9.3.2平衡二叉树236
9.4散列查找242
9.4.1散列查找中的几个主要概念242
9.4.2散列函数设计方法243
9.4.3冲突的处理方法246
9.4.4散列表上的查找算法249
9.4.5散列表查找的时间复杂度分析250
本章小结和学习要点253
习题9253
思考题9256
上机题9256
实验9256
第10章索引技术257
10.1索引的基本概念257
10.2线性索引258
10.2.1稠密索引258
10.2.2稀疏索引259
10.3树形索引260
10.3.1树260
10.3.2B+树262
10.3.3键树263
本章小结和学习要点268
习题10268
思考题10270
上机题10270
主要参考文献271
附录上机实验报告格式272