数据结构

本书以数据的逻辑结构、存储结构和算法为主线，讨论了线性表、栈、队列、串、数组和广义表、树和二叉树、图等各种数据结构，以及程序设计中经常使用到的各种查找和排序算法。全书共分为八个章节，第1章综述了数据、数据结构和抽象数据类型等基本概念；第2章至第6章介绍上述的几种数据结构及其应用；第7章至第8章讨论查找和排序的各种算法。在此基础上，我们更加强调数据结构的综合应用，对不同的数据结构类型设计了大量经典的应用实例，深入浅出、循序渐进，每一算法或程序的编写都力求高效、简洁、易读，并遵循程序设计的规范和标准，代码完整、自成一体，培养学生良好的编程风格，帮助学生将数据结构与工程应用有机地结合起来，从而培养新工科人才运用C语言和常用算法编写程序解决复杂实际工程问题的能力。全书采用C语言作为数据结构和算法的描述语言。

目录
第1章绪论1
1.1为什么要学习数据结构1
1.2基本概念和术语2
1.2.1逻辑结构3
1.2.2存储结构4
1.2.3数据类型和抽象数据类型5
1.3算法和算法分析6
1.3.1算法的定义及特性6
1.3.2算法的设计要求6
1.3.3算法的时间复杂度7
1.3.4算法的空间复杂度10
1.3.5算法的描述形式11
1.4本章小结11
习题12
第2章线性表14
2.1线性表的定义14
2.2线性表的顺序表示和实现15
2.2.1顺序表的定义和特点15
2.2.2顺序表的存储及其操作16
2.2.3顺序表的性能分析20
2.3线性表的链式表示和实现22
2.3.1单链表的定义和表示22
2.3.2单链表的存储及其操作23
2.3.3单链表的性能分析27
2.3.4单链表的应用实例27
2.4循环链表32
2.5双向链表33
2.6链表的应用：一元多项式的运算34
2.6.1一元多项式的表示及存储34
2.6.2一元多项式的求和35
2.7本章小结39
习题39
第3章栈和队列41
3.1栈的定义41
3.2栈的表示和实现42
3.3栈的应用45
3.3.1数制转换45
3.3.2括号匹配检验46
3.3.3迷宫问题47
3.3.4表达式求值问题51
3.4栈与递归56
3.4.1递归56
3.4.2递归算法到非递归算法的转换60
3.5队列的定义64
3.6队列的表示和实现65
3.7队列的应用693.8
本章小结71
习题71
第4章数组、串和广义表73
4.1数组的定义和抽象数据类型73
4.2数组的存储结构74
4.3特殊矩阵的压缩存储75
4.3.1对称矩阵75
4.3.2三角矩阵76
4.3.3对角矩阵76
4.3.4稀疏矩阵76
4.4串91
4.4.1串的定义91
4.4.2串的存储结构93
4.4.3串的模式匹配算法94
4.5广义表104
4.5.1广义表的定义104
4.5.2广义表的链式存储结构和操作105
4.6本章小结109
习题110
第5章树和二叉树111
5.1树111
5.1.1树的定义和基本术语111
5.1.2树的抽象数据类型113
5.1.3树的存储结构114
5.2二叉树117
5.2.1二叉树的定义117
5.2.2特殊二叉树118
5.2.3二叉树的性质119
5.2.4二叉树的抽象数据类型120
5.2.5二叉树的存储结构121
5.2.6二叉链表的存储表示及操作123
5.3二叉树的遍历126
5.3.1先序遍历127
5.3.2中序遍历127
5.3.3后序遍历128
5.3.4层序遍历129
5.4线索二叉树132
5.5二叉树、树和森林136
5.5.1树和二叉树的转换137
5.5.2森林和二叉树的转换138
5.5.3树和森林的遍历139
5.6哈夫曼树及其应用140
5.6.1哈夫曼树的基本概念140
5.6.2哈夫曼树的构造141
5.6.3哈夫曼树的应用141
5.6.4哈夫曼编码的算法实现142
5.7本章小结147
习题147
第6章图149
6.1图的定义和术语149
6.2图的抽象数据类型152
6.3图的存储结构153
6.3.1邻接矩阵153
6.3.2邻接表159
6.3.3十字链表166
6.3.4邻接多重表167
6.4图的遍历169
6.4.1深度优先遍历169
6.4.2广度优先遍历171
6.5最小生成树173
6.5.1基本概念174
6.5.2普里姆算法175
6.5.3克鲁斯卡尔算法178
6.6最短路径180
6.6.1迪杰斯特拉算法181
6.6.2弗洛伊德算法184
6.7拓扑排序187
6.7.1拓扑排序介绍187
6.7.2拓扑排序算法188
6.8关键路径190
6.8.1关键路径算法原理190
6.8.2关键路径算法实现193
6.9本章小结195
习题196
第7章查找199
7.1查找的基本概念199
7.2线性表的查找200
7.2.1顺序查找200
7.2.2折半查找203
7.2.3分块查找207
7.3树表的查找209
7.3.1二叉排序树209
7.3.2平衡二叉树215
7.4散列表的查找222
7.4.1散列表的基本概念222
7.4.2散列函数的构造方法223
7.4.3处理冲突的方法225
7.4.4散列表的查找及性能分析227
7.5本章小结229
习题230
第8章排序232
8.1排序的基本概念232
8.2插入排序233
8.2.1直接插入排序233
8.2.2希尔排序236
8.3交换排序237
8.3.1冒泡排序238
8.3.2快速排序240
8.4选择排序242
8.4.1简单选择排序242
8.4.2堆排序245
8.5归并排序250
8.6分配排序252
8.6.1桶排序252
8.6.2多关键字排序253
8.6.3基数排序253
8.7本章小结257
习题258
参考文献260