数据结构--C语言描述（第二版）

中国水利水电出版社

【作者】王路群主编

【I S B N 】978-7-5084-4398-0

【责任编辑】张玉玲

【适用读者群】高职高专

【出版时间】2008-02-01

【开本】16开本

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

【版次】第2版

【页数】248

【千字数】

【印张】

【定价】￥24

【丛书】21世纪高职高专新概念教材

【备注信息】

图书详情

简介

本书特色

前言

章节列表

精彩阅读

下载资源

相关图书

本书介绍了数据结构的基本概念和基本算法。全书共分为10章，主要内容包括：绪论、线性表、栈和队列、串、数组和广义表、树、图、查找、排序、文件等。各章中所涉及的数据结构与算法均给予了C语言描述（所有程序都运行通过），以便于读者巩固和提高运用C语言进行程序设计的能力与技巧。

本书在内容的选取、概念的引入、文字的叙述以及例题和习题的选择等方面，都力求遵循面向应用、逻辑结构简明合理、由浅入深、深入浅出、循序渐进、便于自学的原则，突出其实用性与应用性。

本书为高职高专计算机专业教材，也适合作为各校非计算机专业辅修计算机专业课程的教材，还可供从事计算机软件开发的科技人员自学参考。

内容的选取、概念的引入、文字的叙述、例题和习题的选择，力求遵循面向应用、逻辑结构简明合由浅入深、循序渐进、便于自学的原则；突出实用性与应用性；培养学生分析数据、组织数据的能力；注重实践应用；每章都配有实训

第二版前言

21世纪是科学技术高速发展的信息时代，计算机知识已成为人类当代文化的一个重要组成部分。

计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到一般的符号，进而发展到具有一定结构的数据。在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计算机存储，并在此基础上又如何有效地实现对象之间的“运算”关系。许多传统的解决数值计算的理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。

数据结构是程序设计的中级课程，主要培养学生分析数据、组织数据的能力，告诉学生如何编写效率高、结构好的程序。本书作为计算机大专系列教材之一，在内容的选取、概念的引入、文字的叙述以及例题和习题的选择等方面，都力求遵循面向应用、逻辑结构简明合理、由浅入深、深入浅出、循序渐进、便于自学的原则，突出其实用性与应用性。全书共分10章。第1章主要讲述数据结构和算法的基本概念。第2～7章分别讲述线性表、栈和队列、串、数组和广义表、树和图这几种基本数据结构的特点、存储方法和基本运算。书中安排了相当的篇幅来介绍这些基本数据结构的实际应用。第8章和第9章讲述查找和排序的基本原理与方法。第10章围绕数据在外存上的组织方法介绍了文件的若干基本结构。各章中所涉及的数据结构与算法均用C语言进行描述，以便于读者巩固和提高运用C语言进行程序设计的能力与技巧。

作为《数据结构——C语言描述（第二版）》，本书的最大特点就是注重实践应用。各种常用数据结构的介绍从实际出发，避免抽象的理论论述和复杂的公式推导，在典型的算法介绍中深入浅出、简洁明了。每章都设有实训，这些实训中的许多实例都是根据现实生活中的具体实际运用来设计的。根据实例，通过上机不但能够使学生可以印证许多基本概念，而且能加深理解，从而更好地掌握相应的数据结构并能达到熟练应用。通过应用与理论知识的紧密结合，以激发学生学习数据结构的兴趣。

本书由王路群任主编，库波、曹静、邓安远任副主编，李梅、汪晓青、陆军、陈坤、张浩军、沈祥玖、李禹生参加了编写及大纲讨论工作，全书由库波统稿。

由于编者水平有限，书中不妥或错误之处在所难免，恳请广大读者批评指正。

编者

2006年12月

序
第二版前言
第一版前言
第1章绪论 1
教学要求 1
1.1 引言 1
1.2 数据结构的发展简史及其在计算机科学中所处的地位 1
1.3 数据结构的概念 2
1.4 基本概念和术语 3
1.5 算法和算法的描述 5
1.5.1 算法 5
1.5.2 算法的描述 5
1.5.3 算法评价 8
1.6 实训 9
本章小结 10
习题一 11
第2章线性表 12
教学要求 12
2.1 线性表的逻辑结构 12
2.2 线性表的顺序存储结构 13
2.2.1 线性表的顺序存储结构 14
2.2.2 线性表在顺序存储结构下的运算 14
2.3 线性表的链式存储结构 18
2.3.1 线性链表 18
2.3.2 循环链表 25
2.3.3 双向链表 26
2.4 一元多项式的表示及相加 29
2.5 实训 31
本章小结 35
习题二 36
第3章栈和队列 38
教学要求 38
3.1 栈 38
3.1.1 栈的定义及其运算 38
3.1.2 栈的顺序存储结构 39
3.1.3 多栈共享邻接空间 41
3.1.4 栈的链式存储结构 42
3.2 算术表达式求值 44
3.3 队列 48
3.3.1 队列的定义及其运算 49
3.3.2 队列的顺序存储结构 49
3.3.3 队列的链式存储结构 53
3.3.4 其他队列 55
3.4 实训 55
本章小结 63
习题三 64
第4章串 65
教学要求 65
4.1 串的基本概念 65
4.1.1 串的定义 65
4.1.2 主串和子串 65
4.2 串的存储结构 65
4.2.1 串值的存储 66
4.2.2 串名的存储映像 68
4.3 串的基本运算及其实现 69
4.3.1 串的基本运算 69
4.3.2 串的基本运算及其实现 69
4.4 文本编辑 71
4.5 实训 73
本章小结 81
习题四 82
第5章数组和广义表 83
教学要求 83
5.1 数组 83
5.1.1 数组的概念 83
5.1.2 数组在计算机内的存放 84
5.2 数组的存储结构 84
5.2.1 一维数组的存储 84
5.2.2 二维数组的存储 85
5.2.3 多维数组的存储 86
5.3 特殊矩阵及其压缩存储 86
5.3.1 特殊矩阵 86
5.3.2 压缩存储 87
5.4 稀疏矩阵 89
5.4.1 稀疏矩阵的存储 89
5.4.2 稀疏矩阵的运算 92
5.5 广义表 102
5.5.1 基本概念 102
5.5.2 存储结构 103
5.5.3 基本运算 104
5.6 实训 108
本章小结 113
习题五 113
第6章树 115
教学要求 115
6.1 树的基本概念 115
6.1.1 树的定义及相关术语 115
6.1.2 树的表示 116
6.1.3 树的基本操作 117
6.2 二叉树 118
6.2.1 二叉树的定义与基本操作 118
6.2.2 二叉树的性质 120
6.2.3 二叉树的存储结构 121
6.3 遍历二叉树 123
6.3.1 先序遍历 123
6.3.2 中序遍历 124
6.3.3 后序遍历 125
6.3.4 层次遍历 126
6.3.5 遍历算法的应用 126
6.4 线索二叉树 127
6.4.1 中序次序线索化算法 129
6.4.2 在中根线索树上检索某结点的前驱算法 130
6.4.3 在中根线索树上检索某结点的后继算法 130
6.5 二叉排序树 131
6.5.1 二叉排序树的定义 131
6.5.2 二叉排序树的生成 131
6.5.3 删除二叉排序树上的结点 132
6.6 树和森林 134
6.6.1 树的存储结构 134
6.6.2 树、森林与二叉树的转换 137
6.6.3 树和森林的遍历 140
6.7 哈夫曼树和哈夫曼算法 141
6.7.1 哈夫曼树的定义 141
6.7.2 构造哈夫曼树——哈夫曼算法 143
6.7.3 哈夫曼树的应用 143
6.8 实训 145
本章小结 153
习题六 154
第7章图 155
教学要求 155
7.1 图的基本概念 155
7.1.1 图的定义和术语 155
7.1.2 图的基本操作 158
7.2 图的存储结构 159
7.2.1 邻接矩阵 159
7.2.2 邻接表 160
7.3 图的遍历 163
7.3.1 深度优先搜索遍历 163
7.3.2 广度优先搜索遍历 166
7.4 图的生成树和最小生成树 168
7.4.1 生成树的概念 168
7.4.2 普里姆算法 170
7.4.3 克鲁斯卡尔算法 174
7.5 最短路径 175
7.5.1 单源点最短路径 176
7.5.2 所有顶点对之间的最短路径 178
7.6 拓扑排序 181
7.7 实训 183
本章小结 187
习题七 189
第8章查找 190
教学要求 190
8.1 顺序查找 190
8.2 折半查找 191
8.3 分块查找 193
8.4 哈希法 194
8.4.1 哈希表和哈希函数的概念 195
8.4.2 哈希函数的构造方法 195
8.4.3 冲突处理 196
8.5 实训 199
本章小结 200
习题八 201
第9章排序 202
教学要求 202
9.1 插入排序 202
9.1.1 线性插入排序 202
9.1.2 折半插入排序 203
9.2 希尔排序 204
9.3 选择排序 206
9.4 堆排序 208
9.5 快速排序 211
9.6 归并排序 214
9.7 基数排序 216
9.8 外部排序 217
9.9 各种排序方法的比较 218
9.10 实训 219
本章小结 221
习题九 221
第10章文件 222
教学要求 222
10.1 文件的基本概念 222
10.2 顺序文件 223
10.3 索引文件 225
10.4 索引顺序文件 226
10.5 直接存取文件 229
10.6 多关键字文件 230
10.6.1 多重表文件 230
10.6.2 倒排文件 231
10.7 实训 231
本章小结 232
习题十 233
参考文献 234

电子教案

关闭

打印