数据结构与算法-图书-人邮教育社区

内容摘要

　　本书是国家级双语教学示范课程《数据结构》的配套教材，根据教育部高等学校计算机科学与技术教学指导委员会制定的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》编写。全书每章均以数据的逻辑结构、存储结构和相应的算法实现为主线，并对算法的运算效率进行分析。全书分为8章，涵盖了各种常见数据结构。第1章主要介绍数据结构和算法分析的基本概念，第2～6章主要介绍典型的线性结构、树型结构和图型结构，第7～8章分别介绍查找和排序操作。
　　另外，每章后面附有习题和上机实验内容，上机实验提供了完整的、可运行的程序上机实验供读者参考，以加深读者对所学知识的理解和应用。
　　本书既可作为高等院校计算机及相关专业数据结构课程的教学用书，也可作为从事计算机工程与应用的广大读者的参考书。

目　录

第 1章　绪论　1
1.1　数据及其逻辑结构　1
1.1.1　基本概念　1
1.1.2　逻辑结构　2
1.2　数据结构　2
1.2.1　什么是数据结构　2
1.2.2　数据结构的二元组描述　3
1.2.3　数据结构和数据类型　4
1.3　存储实现与运算实现　4
1.3.1　顺序存储结构　4
1.3.2　链式存储结构　5
1.3.3　索引存储结构　6
1.3.4　散列存储结构　6
1.3.5　运算实现　7
1.3.6　进一步讨论　8
1.4　算法描述和算法分析　8
1.4.1　什么是算法　8
1.4.2　算法描述　9
1.4.3　算法分析　11
1.5　网络教辅资源　14
1.6　小结　14
练习一　15

第 2章　线性表　19
2.1　线性表的基本概念　19
2.2　线性表的顺序表示和实现　21
2.3　线性表的链接表示和实现　26
2.3.1　线性表的链式存储原理　27
2.3.2　线性表的链式存储算法实现　27
2.3.3　算法效率分析　32
2.4　循环链表和双链表　32
2.4.1　循环链表　32
2.4.2　双向链表　33
2.5　线性表的应用举例　35
2.5.1　问题的提出　35
2.5.2　分析问题　36
2.5.3　算法实现　36
2.5.4　程序　39
2.6　小结　44
练习二　45

第3章　栈和队列　54
3.1　栈　54
3.1.1　栈的定义　54
3.1.2　栈的基本运算　54
3.1.3　栈的顺序存储结构　55
3.1.4　栈的链式存储结构　58
3.1.5　栈的应用　60
3.2　队列　63
3.2.1　队列的定义　63
3.2.2　队列的基本运算　63
3.2.3　队列的顺序存储结构　64
3.2.4　队列的链式存储结构　68
3.2.5　队列的应用　72
3.3　小结　74
练习三　75

第4章　串和数组　79
4.1　串的基本概念　79
4.2　串的基本操作和串的存储结构　80
4.2.1　串的基本操作　80
4.2.2　串的静态顺序存储结构　81
4.2.3　串的动态顺序存储结构　87
4.2.4　串的链式存储结构　91
4.3　数组的定义和运算　92
4.4　数组的顺序存储结构　92
4.5　特殊矩阵的压缩存储　94
4.5.1　特殊矩阵　95
4.5.2　稀疏矩阵　96
4.6　小结　103
练习四　104

第5章　树和二叉树　110
5.1　树的概念与定义　110
5.1.1　树的定义　110
5.1.2　树的基本操作　111
5.2　二叉树的性质和存储结构　111
5.2.1　二叉树的定义与基本操作　111
5.2.2　二叉树的性质　112
5.2.3　二叉树的存储结构　114
5.3　二叉树的遍历与线索化　116
5.3.1　二叉树的遍历　116
5.3.2　二叉树的非递归遍历　119
5.3.3　树的唯一性问题　120
5.3.4　二叉树遍历的应用　121
5.3.5　线索二叉树　124
5.4　树、森林和二叉树的关系　126
5.4.1　树的存储结构　127
5.4.2　树、森林与二叉树的相互转换　129
5.4.3　树与森林的遍历　132
5.5　哈夫曼树及其应用　133
5.5.1　哈夫曼树的定义　133
5.5.2　哈夫曼树的构造　134
5.5.3　哈夫曼编码　135
5.6　小结　137
练习五　139

第6章　图　146
6.1　图的定义及理论　146
6.2　图的存储结构及算法实现　149
6.2.1　图的基本运算的抽象　149
6.2.2　数组表示法　150
6.2.3　邻接表表示　154
6.2.4　十字链表表示　160
6.3　图的算法实现　162
6.3.1　图的遍历算法　162
6.3.2　图的连通性　166
6.4　图的应用　167
6.4.1　图的**小生成树　167
6.4.2　**短路径　171
6.4.3　任意顶点**短路径　175
6.5　小结　176
练习六　177

第7章　查找表　183
7.1　查找表的基本概念　183
7.2　静态查找表　184
7.2.1　顺序查找　184
7.2.2　折半查找　187
7.2.3　分块查找　190
7.3　动态查找表　192
7.3.1　二叉排序树　192
7.3.2　平衡二叉树　199
7.4　哈希表　200
7.4.1　哈希表的基本概念　201
7.4.2　哈希函数的构造方法　202
7.4.3　处理哈希冲突的方法　206
7.5　小结　209
练习七　210

第8章　内部排序　217
8.1　排序的基本概念　217
8.1.1　排序　217
8.1.2　内部排序和外部排序　218
8.1.3　排序算法评价　218
8.1.4　排序算法的稳定性　218
8.1.5　待排序记录序列的存储结构　218
8.2　直接插入排序和希尔排序　218
8.2.1　直接插入排序　219
8.2.2　折半查找插入排序　222
8.2.3　希尔排序　223
8.3　选择排序和堆排序　225
8.3.1　选择排序　226
8.3.2　堆排序　227
8.4　冒泡排序和快速排序　229
8.4.1　冒泡排序　229
8.4.2　快速排序　231
8.5　归并排序　235
8.6　基数排序　236
8.6.1　基本思想　236
8.6.2　基数排序过程与算法　237
8.7　各种内部排序方法的比较讨论　241
8.8　外部排序　243
8.8.1　外部存储系统　243
8.8.2　外部排序面临的问题　246
8.8.3　外部排序的基本过程　246
8.9　小结　247
练习八　248