数据结构——用C语言描述

中国水利水电出版社

【作者】蔡明志编著

【I S B N 】978-7-5084-3428-5

【责任编辑】吴萍

【适用读者群】本科

【出版时间】2006-01-01

【开本】16开本

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

【版次】第1版

【页数】392

【千字数】

【印张】

【定价】￥34

【丛书】21世纪高等院校计算机科学与技术规划教材

【备注信息】

图书详情

简介

本书特色

前言

章节列表

精彩阅读

下载资源

相关图书

本书是根据作者多年教学的经验，并参考了近年出版的多种国外大学数据结构教科书而编写的。

本书以C语言为程序设计语言，采用系列式的叙述方式，引导读者循序渐进地掌握数组、链接表、栈和队列、树与森林、图和堆等不同的数据结构，并系统地介绍了查找和排序的各种实现方法。对每一种数据结构，除了详细阐述其基本概念和具体实现外，都尽可能地对每种操作给出C语言的算法描述；对查找和排序的各种算法，还着重在时间上做出定量或定性的分析比较。

本书不但涉及内容广泛、涵盖的知识点全面，而且条理清晰、通俗易懂、图文并茂，有利于学生系统性地学习。

本书可作为计算机类专业或软件专业的本科或专科教材，也可供从事计算机工程与应用工作的科技工作者参考。

数据结构是与数据相关的一门重要学科，不论是想通过升学考试还是想把程序编写得有水平，都要对这门学科下一点功夫才行。

笔者教授数据结构已有多年了（大概大于10年吧！），对于其内容已了如指掌，知道学生在研究上有哪些盲点，因此在内容的规划上尽可能让读者有事半功倍的学习效果。

本书的内容按不同的主题分为14章，每一章的每一小节均附有练习题及类似题，旨在让读者测试对该小节所谈及的内容是否已全部了解。在每一章的最后有动动脑时间，每一题的前面均加上此题的相关章节，如[1.2]表示此题目与1.2节相关，读者可以参考。

在每一章重要的主题后均附有程序加以测试，期使读者对理论能进一步认识与了解，尤其是第四章的链接表，笔者用一种更有效率的算法（algorithms）进行执行，希望读者能与笔者分享这份甜美果实。

本书的繁转简工作由董国平、林晓珊、李强、黄浩、林丽、王晓青、李欣、杨勇、林广毅、刘涛、曲波等人完成，在此对他们所做的工作表示感谢，也感谢中国水利水电出版社的编辑们，是他们的认真工作使得本书得以尽快地与读者见面。

最后，感谢邱义伦在程序上的测试，使得本书能够早日完成。笔者才疏学浅，若有叙述不详之处，盼各位批评与指教。

编者

2005年10月

序
前言
第1章算法分析 1
1.1 算法 1
1.1.1 数组元素相加（Add array members） 1
1.1.2 矩阵相乘（Matrix Multiplication） 1
1.1.3 顺序查找（Sequential search） 2
1.1.4 折半查找（Binary search） 2
1.1.5 斐波那契（Fibonacci）数列（递归的程序段） 3
1.1.6 斐波那契数列（非递归的程序片段） 3
1.2 Big-O（复杂度） 4
1.3 动动脑时间 10
第2章数组 12
2.1 数组的表示法 12
2.1.1 一维数组（one dimension array） 12
2.1.2 二维数组 12
2.1.3 三维数组 14
2.1.4 n维数组 15
2.2 上三角形和下三角形表示法 16
2.2.1 以列为主 16
2.2.2 以行为主 17
2.3 多项式表示法 17
2.4 魔术方阵 21
2.5 生命细胞游戏 25
2.6 动动脑时间 32
第3章堆栈与队列 34
3.1 堆栈与队列的基本概念 34
3.2 堆栈的插入与删除 35
3.3 队列的插入与删除 41
3.4 循环队列 42
3.5 堆栈与队列的应用 51
3.6 如何计算后序表达式 57
3.7 动动脑时间 58
第4章链表 60
4.1 单向链表 60
4.1.1 插入操作 60
4.1.2 删除操作 63
4.1.3 将两个单向链表相互连接 73
4.1.4 将一链表反转 74
4.1.5 计算链表的长度 75
4.2 循环链表 76
4.2.1 插入操作 76
4.2.2 删除操作 78
4.2.3 如何回收整个循环链表 80
4.2.4 计算循环链表的长度 80
4.3 双向链表 81
4.3.1 插入操作 82
4.3.2 删除操作 85
4.4 链表的应用 96
4.4.1 以链表表示堆栈 96
4.4.2 以链表表示队列 96
4.4.3 多项式相加 96
4.5 动动脑时间 102
第5章递归 103
5.1 一些递归的基本范例 103
5.2 一个典型的递归范例：hanoi塔 111
5.3 另一个范例：8个皇后 115
5.4 何时不要使用递归 120
5.5 动动脑时间 122
第6章树状结构 123
6.1 树状结构的一些专有名词 123
6.2 二叉树 124
6.3 二叉树的表示方法 127
6.4 二叉树的遍历 129
6.5 线索二叉树 132
6.6 其他问题 136
6.6.1 如何将一般树化为二叉树 136
6.6.2 确定惟一的二叉树 138
6.7 动动脑时间 140
第7章二叉查找树 143
7.1 什么是二叉查找树 143
7.2 二叉查找树的插入 144
7.3 二叉查找树的删除 145
7.4 动动脑时间 156
第8章堆 158
8.1 什么是堆 158
8.1.1 Heap的插入 160
8.1.2 Heap的删除 160
8.2 什么是min-heap 171
8.3 min-max heap 173
8.3.1 Max-max-heap的插入 174
8.3.2 min-max-heap的删除 175
8.4 Deap 178
8.4.1 Deap的插入 178
8.4.2 Deap的删除 179
8.5 动动脑时间 181
第9章平衡二叉查找树 183
9.1 何谓平衡二叉查找树 183
9.2 AVL-tree的插入与删除 184
9.2.1 LL型 184
9.2.2 RR型 185
9.2.3 LR型 186
9.2.4 RL型 187
9.3 AVL-tree的删除 192
9.4 动动脑时间 209
第10章 2-3 tree与2-3-4 tree 210
10.1 2-3 tree 210
10.1.1 2-3 Tree的插入 211
10.1.2 2-3 Tree的删除 213
10.2 2-3-4 Tree 217
10.2.1 2-3-4 Tree的插入 218
10.2.2 2-3-4 Tree的删除 219
10.3 动动脑时间 221
第11章 B-tree 222
11.1 m-way查找树 222
11.1.1 m-way查找树的插入 223
11.1.2 m-way查找树的删除 224
11.2 B-tree 225
11.2.1 B-tree 的插入 225
11.2.2 B-tree的删除 227
11.3 动动脑时间 250
第12章图 251
12.1 图的一些专有名词 252
12.2 图数据结构表示法 255
12.2.1 邻接矩阵（adjacency matrix） 255
12.2.2 邻接表（adjacency list） 256
12.3 图的遍历 258
12.3.1 深度优先搜索（depth first search） 258
12.3.2 广度优先搜索（breadth first search） 261
12.4 最小生成树 266
12.4.1 普里姆算法（Prim's algorithm） 267
12.4.2 克鲁斯卡尔算法（Kruskal's algorithm） 269
12.5 最短路径 275
12.6 拓扑排序 285
12.7 关键路径法 291
12.7.1 计算事件最早发生的时间 293
12.7.2 计算事件最晚发生的时间 294
12.8 动动脑时间 305
第13章排序 308
13.1 起泡排序 309
13.2 选择排序 311
13.3 插入排序 313
13.4 归并排序（merge sort） 315
13.5 快速排序 319
13.6 堆排序 321
13.7 二叉树排序（binary tree sort） 327
13.8 希尔排序 330
13.9 基数排序 332
13.10 动动脑时间 335
第14章查找 337
14.1 顺序查找 337
14.2 折半查找 338
14.3 哈希法 341
14.3.1 哈希函数 341
14.3.2 解决溢出的方法（overflow handing） 343
14.4 动动脑时间 351
练习题参考答案 353

电子教案

关闭

打印