数据结构

中国水利水电出版社

【作者】陆勤主编

【I S B N 】978-7-5084-6611-8

【责任编辑】李炎

【适用读者群】本科

【出版时间】2009-09-01

【开本】16开

【装帧信息】平装（光膜）

【版次】第1版第1次印刷

【页数】

【千字数】455

【印张】17.5

【定价】￥28

【丛书】新世纪电子信息与自动化系列课程改革教材

【备注信息】

图书详情

简介

本书特色

前言

章节列表

精彩阅读

下载资源

相关图书

本书系统地阐述了基本数据结构的多种存储结构和典型算法，以及应用数据结构理论解决实际问题的基本方法和技巧，努力使读者牢固掌握数据结构的理论，培养灵活运用并巧妙解决具体问题的能力，为读者今后进一步地深入学习实践打下坚实基础。

全书内容严谨、编排合理、文字流畅、示例典型、实用性强，书中的程序均已在Microsoft Visual C++ 6.0系统下编译运行。全书共分9章。第1章介绍数据结构的基本概念和算法描述及分析。第2章至第7章分别介绍线性表、栈和队列、字符串、数组与特殊矩阵、树、图的多种存储结构和典型算法应用示例。第8章介绍了线性表的查找、查找树、哈希表查找（杂凑法）方法。第9章介绍了插入排序、交换排序、选择排序、二路归并排序、基数排序等多种排序算法。

本书可用作高等学校非计算机专业本科学生数据结构课程的教材。

本书系统阐述了基本数据结构的多种存储结构和典型算法，以及应用数据结构理论解决实际问题的基本方法和技巧。

本书力图使读者牢固掌握数据结构的理论，培养灵活运用并巧妙解决具体问题的能力，为读者今后进一步地深入学习实践打下坚实基础。

全书内容严谨、编排合理、文字流畅、示例典型、实用性强，书中的程序均已在Microsoft Visual C++ 6.0系统下编译运行。

数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示和实现”的学科。随着计算机硬件、软件技术的飞速发展和计算机系统在各行业的广泛应用，有关数据结构的理论和技术也成为了计算机应用技术教育的重要部分。

数据结构是计算机技术应用方面的主要基础课程之一，它引导学生学会从实际应用问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握算法的时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计、调试并排除错误的训练过程，要求学生编写的程序代码结构清晰、正确易读，具有良好的可维护性。

本书按照非计算机专业计算机课程基本要求中所规定的数据结构课程的教学内容，并参考教育部制定的计算机基础教学主要课程教学大纲编写。全书共分9章。第1章介绍数据结构的基本概念和算法描述及分析。第2章至第7章分别介绍线性表、栈和队列、字符串、数组与特殊矩阵、树、图的多种存储结构和典型算法应用示例。第8章介绍了线性表的查找、查找树、哈希表查找（杂凑法）方法。第9章介绍了插入排序、交换排序、选择排序、二路归并排序、基数排序等多种排序算法。

本书可用作高等学校非计算机专业本科学生数据结构课程的教材，旨在培养学生运用数据结构的基本概念和方法解决实际问题的能力。一般情况下，课堂讲授学时数应安排为40～60学时，集体上机实践时间应安排为30学时，可根据具体条件适当增减教学内容和学时数。多上机实践是学好本书内容的捷径，希望读者通过学习本书尽快掌握数据结构的基本应用技能。

本书由陆勤主编，特别感谢国防科学技术大学邹逢兴教授对本书的出版所给予的巨大帮助。此外，作者参阅了国内外一些有关数据结构的教材、书籍，受益匪浅。在此，谨向这些教材、书籍的作者表示感谢。

由于时间仓促及作者水平有限，书中难免存在错误或不当之处，敬请广大读者批评指正。

编者

2009年5月

总序
前言

第1章绪论 1
1.1 数据结构讨论的范畴 2
1.2 数据结构的基本概念 2
1.2.1 基本术语 2
1.2.2 数据结构 4
1.2.3 数据类型和抽象数据类型 6
1.3 算法及其描述和分析 9
1.3.1 算法的特性及其设计原则 9
1.3.2 算法的描述 10
1.3.3 算法分析 11
思考题与习题 15
第2章线性表 17
2.1 线性表的定义和基本运算 18
2.2 线性表的顺序存储结构 20
2.2.1 顺序存储结构 20
2.2.2 顺序表的基本操作及其时间
效率分析 22
2.3 线性表的链式存储结构 24
2.3.1 单链表及其基本操作 24
2.3.2 特殊链表 32
2.4 线性表的应用示例——多项式的
代数运算 36
思考题与习题 38
第3章栈和队列 41
3.1 栈 42
3.1.1 栈的定义及其运算 42
3.1.2 顺序栈 43
3.1.3 多栈共享邻接空间 46
3.1.4 链栈 47
3.1.5 栈的应用举例 49
3.2 队列（queue） 58
3.2.1 队列的定义及其运算 59
3.2.2 队列的顺序存储结构 60
3.2.3 队列的链式存储结构 62
3.2.4 循环队列 64
3.2.5 队列的应用举例 66
思考题与习题 70
第4章字符串 73
4.1 串的概念 74
4.1.1 串的定义 74
4.1.2 主串和子串 75
4.2 串的存储结构 76
4.2.1 串的静态存储结构 76
4.2.2 串的动态存储结构 77
4.3 求子串运算 78
4.4 串的模式匹配 80
4.4.1 串的模式匹配的简单算法 80
4.4.2 模式匹配的改进算法——KMP算法 82
思考题与习题 85
第5章数组与特殊矩阵 87
5.1 数组的概念 88
5.2 静态数组与动态数组 90
5.3 特殊矩阵及其压缩存储 93
5.3.1 特殊矩阵 93
5.3.2 特殊矩阵的压缩存储 94
5.4 稀疏矩阵 97
5.4.1 三元组顺序表 98
5.4.2 行逻辑链接的顺序表 100
5.4.3 十字链表 101
思考题与习题 102
第6章树 105
6.1 基本概念 106
6.1.1 树的定义和有关术语 106
6.1.2 二叉树 108
6.2 二叉树的存储 110
6.2.1 顺序存储结构 110
6.2.2 链式存储结构 112
6.3 二叉树的抽象数据类型 112
6.4 二叉树的遍历 115
6.4.1 二叉树的遍历方法 115
6.4.2 二叉树的遍历算法 118
6.4.3 树、森林和二叉树的转换 122
6.5 二叉树的构造 124
6.5.1 用中序序列和先序序列构造二叉树 124
6.5.2 用扩充先序序列构造二叉树 126
6.6 线索二叉树 127
6.6.1 线索二叉树的定义及结构 127
6.6.2 线索二叉树的操作 128
6.7 树的存储结构 131
6.8 树和森林的遍历 135
6.8.1 树的遍历 135
6.8.2 森林的遍历 135
6.9 哈夫曼树 136
6.9.1 哈夫曼树算法 136
6.9.2 哈夫曼树在编码问题中的应用 139
思考题与习题 143
第7章图 147
7.1 基本概念 148
7.1.1 图的定义 148
7.1.2 有关术语 148
7.2 图的存储方法 151
7.2.1 邻接矩阵及其顺序存储 151
7.2.2 邻接表 154
7.2.3 十字链表 157
7.2.4 邻接多重表 160
7.3 图的遍历 162
7.3.1 深度优先搜索 162
7.3.2 广度优先搜索 167
7.4 最小生成树 169
7.4.1 最小生成树的基本概念 169
7.4.2 构造最小生成树的普里姆（Prim）
方法 169
7.4.3 构造最小生成树的克鲁斯卡尔
（Kruskal）算法 173
7.5 最短路径 176
7.5.1 单源点最短路径 176
7.5.2 每一对顶点之间的最短路径 179
7.6 有向无环图及其应用 181
7.6.1 AOV网与拓扑排序 181
7.6.2 AOE网与关键路径 191
思考题与习题 198
第8章查找 203
8.1 基本概念与术语 204
8.2 线性表的查找 205
8.2.1 顺序查找 205
8.2.2 顺序表的折半查找 206
8.2.3 分块查找 209
8.3 查找树 210
8.3.1 二叉查找树 210
8.3.2 平衡二叉树（AVL树） 218
8.3.3 B-树和B+树 226
8.4 哈希表查找（杂凑法） 234
8.4.1 哈希表与哈希方法 234
8.4.2 哈希函数的构造方法 235
8.4.3 处理冲突方法 237
8.4.4 哈希表中查找和插入算法的实现 241
8.4.5 哈希表的查找算法分析 242
思考题与习题 243
第9章排序 247
9.1 基本概念 248
9.2 插入排序 248
9.2.1 直接插入排序 248
9.2.2 二分法插入排序 250
9.2.3 表插入排序 251
9.2.4 希尔排序（Shell's Sort） 253
9.3 交换排序 254
9.3.1 冒泡排序（Bubble Sort） 254
9.3.2 快速排序 256
9.4 选择排序 258
9.4.1 简单选择排序 258
9.4.2 树形选择排序 259
9.4.3 堆排序（Heap Sort） 260
9.5 二路归并排序 264
9.6 基数排序 264
9.6.1 多关键字排序 265
9.6.2 链式基数排序 265
思考题与习题 268
参考文献 270

经典样章

关闭

打印