数据结构：C语言描述 - 中国高校教材图书网
|
书名： |
数据结构：C语言描述
|
| ISBN： | 978-7-5606-2226-2 |
责任编辑： | |
| 作者： |
陈慧南
相关图书
|
装订： | 平装 |
| 印次： | 1-1 |
开本： | 16开 |
| 定价： |
￥30.00
折扣价：￥28.50
折扣：0.95
节省了1.5元
|
字数： |
488千字
|
| 出版社： |
西安电子科技大学出版社 |
页数： |
|
| 出版日期： |
2009-06-01 |
每包册数： |
|
| 国家规划教材： |
|
省部级规划教材： |
|
| 入选重点出版项目： |
|
获奖信息： |
|
|
|
| 内容简介： |
内 容 简 介
本书为普通高等教育“十一五”国家级规划教材。
本书保留经典数据结构知识，并引入伸展树和跳表等新内容，反映抽象、封装和信息隐蔽等现代软件设计理念，重视算法的时间和空间分析，包括搜索和排序时间的下界分析。本书使用C语言描述，内容新旧取舍恰当，广度和深度适中。
本书重视实践性和程序设计。书中算法都有完整的C程序，程序代码注释详细，结构清晰，构思精巧，所有程序都已在TC 2.01下编译通过并能正确运行。这些程序既是学习数据结构和算法的很好示例，也是很好的C程序设计示例。本书最后一章为实习指导和实习题，指导学生按软件工程学的方法设计算法、编写程序和书写文档。
本书结构严谨、内容深入浅出，配有大量的实例和图示，并有丰富的习题和实习题，易教易学。
本书可作为电气信息类、电子信息科学类、管理信息系统、电子商务、教育技术等相关专业数据结构课程的教材，也可供从事计算机软件和应用开发的工程技术人员参考。
本书配有《学习指导和习题解析》，由西安电子科技大学出版社同时出版。两者结合使用，学习效果更佳。
|
| 作者简介： |
|
|
| 章节目录： |
目 录
第1章 概论 1
1.1 什么是数据结构 1
1.1.1 基本概念 1
1.1.2 数据的逻辑结构 2
1.1.3 数据的存储结构 3
1.1.4 数据结构的运算 4
1.2 数据抽象和抽象数据类型 5
1.2.1 抽象、数据抽象和过程抽象 5
1.2.2 封装与信息隐蔽 5
1.2.3 数据类型和抽象数据类型 5
1.2.4 数据结构与抽象数据类型 6
1.3 描述数据结构 7
1.3.1 数据结构的规范 7
1.3.2 实现数据结构 8
1.4 算法和算法分析 9
1.4.1 算法及其性能标准 9
1.4.2 算法的时间复杂度 10
1.4.3 渐近时间复杂度 12
1.4.4 最坏、最好和平均情况时间复杂度 13
1.4.5 算法的空间复杂度 13
小结 14
习题1 14
第2章 数组和链表 16
2.1 结构与联合 16
2.1.1 结构 16
2.1.2 联合 17
2.2 数组 18
2.2.1 一维数组 18
2.2.2 二维数组 18
2.2.3 多维数组 20
2.3 链表 20
2.3.1 指针 20
2.3.2 单链表 24
2.3.3 带表头结点的单链表 30
2.3.4 循环链表 31
2.3.5 双向链表 31
小结 33
习题2 33
第3章 堆栈和队列 35
3.1 堆栈 35
3.1.1 堆栈ADT 35
3.1.2 堆栈的顺序表示 36
3.1.3 堆栈的链接表示 38
3.2 队列 39
3.2.1 队列ADT 39
3.2.2 队列的顺序表示 40
3.2.3 队列的链接表示 43
*3.3 表达式的计算 43
3.3.1 表达式 43
3.3.2 中缀表达式转换为后缀表达式 44
3.3.3 计算后缀表达式的值 48
*3.4 递归和递归过程 50
3.4.1 递归的概念 50
3.4.2 递归的实现 51
*3.5 演示和测试 53
小结 55
习题3 55
第4章 线性表和数组ADT 57
4.1 线性表 57
4.1.1 线性表ADT 57
4.1.2 线性表的顺序表示 58
4.1.3 线性表的链接表示 61
4.1.4 两种存储表示的比较 65
*4.2 多项式的算术运算 65
4.2.1 多项式ADT 65
4.2.2 多项式的链接表示 66
4.2.3 多项式的输入和输出 67
4.2.4 多项式相加 69
4.3 数组作为抽象数据类型 71
4.4 特殊矩阵 72
4.4.1 对称矩阵 72
*4.4.2 带状矩阵 72
4.5 稀疏矩阵 74
4.5.1 稀疏矩阵ADT 74
4.5.2 稀疏矩阵的顺序表示 74
4.5.3 稀疏矩阵转置 76
*4.5.4 稀疏矩阵相乘 78
4.5.5 稀疏矩阵的正交链表表示 81
*4.5.6 建立正交链表 84
*4.5.7 打印正交链表 85
小结 86
习题4 86
第5章 字符串和广义表 88
5.1 字符串 88
5.1.1 字符串ADT 88
5.1.2 字符串的存储表示 89
5.1.3 简单模式匹配算法 90
*5.1.4 模式匹配的KMP算法 93
*5.2 广义表 97
5.2.1 广义表的概念 97
5.2.2 广义表ADT 98
5.2.3 广义表的存储表示 99
5.2.4 广义表的算法 100
小结 101
习题5 101
第6章 树 102
6.1 树的基本概念 102
6.1.1 树的定义 102
6.1.2 基本术语 103
6.2 二叉树 104
6.2.1 二叉树的定义和性质 104
6.2.2 二叉树ADT 106
6.2.3 二叉树的存储表示 107
6.2.4 二叉树的遍历 111
*6.2.5 二叉树遍历的非递归算法 114
*6.2.6 二叉树遍历的应用实例 117
*6.2.7 线索二叉树 119
6.3 树和森林 122
6.3.1 森林与二叉树的转换 122
6.3.2 树和森林的存储表示 123
6.3.3 树和森林的遍历 125
*6.4 堆和优先权队列 126
6.4.1 堆 127
6.4.2 优先权队列 129
6.5 哈夫曼树和哈夫曼编码 132
6.5.1 树的路径长度 132
6.5.2 哈夫曼树和哈夫曼算法 134
6.5.3 哈夫曼编码 136
*6.6 并查集和等价关系 137
6.6.1 并查集 137
6.6.2 并查集的实现 138
6.6.3 集合按等价关系分组 141
小结 142
习题6 142
第7章 集合和搜索 145
7.1 集合及其表示 145
7.1.1 集合和搜索 145
7.1.2 集合ADT 146
7.1.3 集合的表示 147
7.2 顺序搜索 147
7.3 二分搜索 149
7.3.1 对半搜索 150
7.3.2 二叉判定树 151
*7.3.3 斐波那契搜索 153
*7.4 搜索算法的时间下界 154
小结 155
习题7 156
第8章 搜索树 157
8.1 二叉搜索树 157
8.1.1 二叉搜索树的定义 157
8.1.2 二叉搜索树的搜索 157
8.1.3 二叉搜索树的插入 158
8.1.4 二叉搜索树的删除 160
*8.1.5 二叉搜索树的高度 162
8.2 二叉平衡树 163
8.2.1 二叉平衡树的定义 163
8.2.2 二叉平衡树的平衡旋转 164
8.2.3 二叉平衡树的插入 170
8.2.4 二叉平衡树的删除 173
8.2.5 二叉平衡数的高度 176
8.3 B - 树 176
8.3.1 m叉搜索树 176
8.3.2 B -树的定义 178
8.3.3 B -树的高度 179
8.3.4 B -树的搜索 179
8.3.5 B -树的插入 179
8.3.6 B -树的删除 182
*8.4 键树 184
8.4.1 键树的定义 184
8.4.2 双链树 185
8.4.3 Trie树 186
*8.5 伸展树 187
小结 190
习题8 190
第9章 跳表和散列表 192
9.1 字典 192
*9.2 跳表 192
9.2.1 什么是跳表 193
9.2.2 跳表的搜索 196
9.2.3 跳表的插入 197
9.2.4 跳表的删除 198
9.3 散列表 199
9.3.1 散列技术 199
9.3.2 散列函数 200
9.3.3 解决冲突的拉链法 202
9.3.4 解决冲突的线性探查法 203
9.3.5 解决冲突的其他开地址法 207
9.3.6 性能分析 209
小结 209
习题9 210
第10章 图 211
10.1 图的基本概念 211
10.1.1 图的定义与术语 211
10.1.2 图ADT 214
10.2 图的存储结构 215
10.2.1 矩阵表示法 215
10.2.2 邻接表表示法 218
*10.2.3 多重表表示法 221
10.3 图的遍历 222
10.3.1 深度优先遍历 222
10.3.2 宽度优先遍历 224
10.4 拓扑排序和关键路径 226
10.4.1 拓扑排序 226
*10.4.2 关键路径 230
10.5 最小代价生成树 233
10.5.1 普里姆算法 234
*10.5.2 克鲁斯卡尔算法 235
*10.6 最短路径 237
10.6.1 单源最短路径 238
10.6.2 所有顶点之间的最短路径 241
小结 244
习题10 244
第11章 内排序 247
11.1 排序的基本概念 247
11.2 插入排序 248
11.2.1 直接插入排序 248
11.2.2* 希尔排序 252
11.3 交换排序 253
11.3.1 冒泡排序 253
11.3.2 快速排序 255
11.4 合并排序 260
11.4.1 两路合并排序 260
11.4.2 合并排序的迭代算法 260
*11.4.3 链表上的合并排序 262
11.5 选择排序 265
11.5.1 简单选择排序 266
*11.5.2 堆排序 267
*11.6 排序算法的时间下界 268
*11.7 基数排序 269
小结 273
习题11 273
第12章 文件和外排序 275
*12.1 辅助存储器简介 275
12.1.1 主存储器和辅助存储器 275
12.1.2 磁盘存储器 275
12.2 文件 277
12.2.1 文件的基本概念 277
12.2.2 文件的组织方式 277
12.2.3 C语言文件 281
12.3 文件的索引结构 282
12.3.1 静态索引结构 282
12.3.2 动态索引结构 283
*12.4 外排序 283
12.4.1 外排序的基本过程 284
12.4.2 初始游程的生成 284
12.4.3 多路合并 286
12.4.4 最佳合并树 288
小结 289
习题12 290
第13章 实习指导和实习题 291
13.1 实习目的和要求 291
13.1.1 实习目的 291
13.1.2 实习要求 291
13.2 实习步骤 292
13.3 实习报告 292
13.4 实习题 293
实习1 数组操作 293
实习2 链表操作 294
实习3 表达式计算 294
实习4 队列运算和用户界面设计 295
实习5 线性表运算及应用 295
实习6 一元多项式的相加和相乘 295
实习7 对称矩阵的压缩存储 296
实习8 稀疏矩阵的三元组表 296
实习9 稀疏矩阵的正交链表 296
实习10 字符串运算和文本处理 297
实习11 二叉树的基本运算 297
实习12 哈夫曼编码和译码系统 298
实习13 B-树检索 298
实习14 散列表检索 299
实习15 图运算及其应用 299
实习16 内排序算法及其性能比较 300
实习17 外排序 300
13.5 实习报告范例 301
13.5.1 实习题：表达式计算 301
13.5.2 实习报告 301
附录A 软件工程概述 307
A.1 软件开发方法 307
A.2 软件文档写作 309
A.3 系统测试方法 310
附录B 专用名词中英文对照表 314
参考文献 320
|
| 精彩片段： |
|
|
| 书 评： |
第 一 版 前 言
有关数据结构与算法的研究是计算机科学与技术的基础性研究之一。美国计算机协会(ACM)和美国电气和电子工程师学会计算机分会(IEEE－CS)在计算学科教学计划CC1991报告中，将算法与数据结构定义为计算学科研究的9个主领域之一。该组织在2001年12月递交的CC2001报告中，调整了计算学科研究领域的划分，最终将计算学科划分为14个主领域。数据结构与算法方面的知识包含在程序设计基础(PF)、算法与复杂性(AL)和程序设计语言(PL)等领域中。
掌握该领域的知识对于我们利用计算机资源，开发高效的计算机程序是非常必要的。因此，CC2001把其中的大多数知识单元规定为计算机及相关学科的本科学生必须掌握的核心知识单元，如基本数据结构(PF3)，递归技术(PF4)，数据类型和数据抽象(PL4和PL9)，面向对象的程序设计(PL6)，算法分析的基本方法(AL1)，基本的计算算法(AL3)等。其中，基本数据结构包括数组、字符串、堆栈、队列、树、图和散列表等，基本的计算算法包括查找、排序、哈希表算法、搜索树及图算法。目前，国内外所有的计算机专业都开设一到两门相关的课程讲授这方面的知识。
一般来讲，“数据结构”课程涉及的知识单元有PF3、PF4、PL4、PL6、PL9、AL1和AL3。从课程性质来看，“数据结构”是计算机科学与技术专业的一门核心课程，也是计算机软件和应用工作者必备的专业基础。近年来，“数据结构”课程的内容和讲授体系有了很大的变革，在介绍数据结构与算法知识的同时，普遍重视程序设计方面的训练，如C/C++程序设计、Java程序设计等。
本书在内容上注意兼顾广度和深度，不仅系统地介绍了各种传统的数据结构和各种搜索、内外排序方法，还引入了一些比较高级的数据结构，如伸展树和跳表。本书重视算法的时间和空间分析，包括对搜索和排序时间的下界分析。
本书既注重数据结构和算法原理，又十分强调程序设计训练。书中各算法都配有完整的C程序，程序结构清晰，构思精巧。所有程序都已在TC 2.01下编译通过并能正确运行，它们对C++环境(如Borland C++、Visual C++)同样适用。这些程序既是很好的学习数据结构和算法的示例，也是很好的程序设计示例。
书中使用C语言描述数据结构。C语言是一种主要的软件开发语言，目前很多高校将其作为第一门程序设计语言讲授。选择C语言描述数据结构，使学习过C语言、C++语言的读者能够很容易地学习本书。对于只学过Pascal语言的读者来说，也可将本书作为学习教材或参考资料。
本书采用抽象数据类型的观点讨论数据结构。面向对象方法是在抽象数据类型的基础上发展起来的软件方法。采用抽象数据类型的观点讨论数据结构与用面向对象的观点讨论数据结构本质上是一致的。学生通过本书的学习，就可以掌握数据抽象的原理。因此，学习本书的读者如果具有C++语言的知识就能方便地阅读用C++语言描述的数据结构书籍。
全书条理清晰，内容详实且深入浅出，书中对算法都做了较详细的解释，尽可能做到可读易懂，并配有大量的实例和图示，有利于读者理解算法的实质和编程思想。各章结尾处的小结可帮助读者了解本章的要点。各章配有丰富的习题，适于自学。
作者多年在南京邮电学院从事“数据结构”和“算法设计与分析”课程教学，曾使用多种教材讲授数据结构和算法，其中包括C语言和C++语言描述的《数据结构》英语原版教材。作者与他人合作编写了《数据结构》(PASCAL语言描述)教材，1994年由人民邮电出版社出版。2001年作者主编了《数据结构——使用C++语言描述》一书，由东南大学出版社出版。此外，作者还于1998年主编了《计算机软件技术基础》一书，由人民邮电出版社出版。本书是在作者上述“数据结构”课程教学和教材的基础上，参考了近年来国外出版的多种数据结构和算法的优秀教材编写而成的。
全书共分12章。
第1章是预备知识，首先给出传统的数据结构的概念，继而介绍算法规范和数据抽象，最后讨论算法的效率和算法分析的基本方法。
第2章介绍两种实现数据的顺序和链接存储的基本数据结构：数组和链表，它们是实现本书中各种抽象数据类型的基础。
第3、4章我们定义了几种线性数据结构：堆栈、队列、线性表、数组和矩阵，讨论它们的顺序表示和链接表示，并给出若干应用实例，如表达式计算、多项式的算术运算和稀疏矩阵算法。第3章中还讨论了递归和递归过程以及测试数据结构所必需的演示驱动程序的编写方法。
第5章简要介绍字符串和广义表的定义、存储表示及典型算法，如字符串匹配等内容。
第6章讨论树形数据结构，包括树和森林、二叉树、堆和优先权队列、哈夫曼树和哈夫曼编码、并查集和等价关系等内容。
第7章讨论集合和表的搜索，如顺序搜索、二分搜索(包括对半搜索和斐波那契搜索)，搜索算法的二叉判定树以及搜索算法的时间下界等内容。
第8章内容包括二叉搜索树、二叉平衡树、伸展树、B树、键树等。
第9章讨论跳表和散列表。
第10章讨论图数据结构，着重讨论几种图算法：图的遍历、拓扑排序、关键路径、最小代价生成树和最短路径算法。
第11章介绍若干内排序算法。
第12章讨论文件和外排序。
附录A介绍软件工程的基本概念，包括软件开发方法和系统测试方法。
附录B对实习目的、实习要求、实习步骤、实习报告和实习题作了说明和规定。
附录C是书中出现的专用名词的中英文对照表。
本书可作为高等院校计算机科学与技术专业和其他相关专业的“数据结构”课程80学时的教材。对于学时数少于80学时的教学计划，可根据实际学时对本书内容加以剪裁。作者已将难度较大，或非基本的章节标上了*号，供读者参考。
本书的编写得到南京邮电学院和计算机科学与技术系领导的推荐和关心，并得到了西安电子科技大学出版社的支持，在此表示衷心感谢。
书中若有不当之处，敬请读者批评指正。
作 者
2003年3月于南京
前 言
本书为普通高等教育“十一五”国家级规划教材。
本书作者多年来在南京邮电大学讲授“数据结构”和“算法设计与分析”等课程，主持的“数据结构”课程被评为江苏省精品课程，编写出版了《数据结构——C语言描述》、《数据结构——使用C++语言描述》、《算法设计与分析》、《数据结构与算法》、《计算机软件技术基础》等教材，其中前三本已被列为普通高等教育“十一五”国家级规划教材。本书是作者在上述教材的基础上，参考了近年来国内外出版的多种数据结构和算法的优秀教材编写而成的。
本书保留经典数据结构知识，并引入伸展树和跳表等新内容，反映抽象、封装和信息隐蔽等现代软件设计理念，重视算法的时间和空间分析，包括搜索和排序时间的下界分析，内容新旧取舍恰当，广度和深度适中。
书中使用C语言描述数据结构。C语言是一种主要的软件开发语言，很多高校将其作为第一门程序设计语言来讲授。本书采用抽象数据类型的观点讨论数据结构。
本书对程序设计和实验给予了足够重视，将上机实习内容专门作为单独的一章编写，指导学生按软件工程学的方法设计和编写程序。书中算法都有完整的C程序，程序代码注释详细、结构清晰、构思精巧。所有程序都已在TC 2.01下编译通过并能正确运行，它们既是学习数据结构和算法的很好示例，也是很好的C程序设计示例。
本书结构严谨，内容深入浅出，配有大量的实例和图示，并有丰富的习题和实习题，易教易学。
全书共13章。
第1章是基础知识，讨论有关数据结构、算法、数据抽象和抽象数据类型的概念，给出数据结构和算法的描述方法，介绍算法分析的基本方法。
第2章介绍数组和链表，它们是实现本书中各种抽象数据类型的基础。本章也包含对C语言的数组、指针和链表的复习。
第3章讨论堆栈和队列、递归和递归过程、表达式的计算以及测试数据结构所需的驱动程序的编写方法。
第4章讨论线性表的逻辑结构、存储表示和运算以及多项式的算术运算；数组作为一种抽象数据类型也在本章中加以讨论。
第5章简要介绍字符串和广义表的定义、存储表示及典型算法，如字符串匹配。
第6章讨论树形结构，内容包括树和森林、二叉树、堆和优先权队列、哈夫曼树和哈夫曼编码、并查集和等价关系。
第7～9章讨论集合的表示和运算。其中，第7章主要讨论顺序搜索和二分搜索，第8章讨论二叉搜索树、二叉平衡树、B树、键树和伸展树，第9章讨论跳表和散列表。
第10章讨论图结构，着重讨论几种图算法，即图的遍历、拓扑排序、关键路径、最小代价生成树和最短路径算法。
第11章介绍多种内排序算法。
第12章主要讨论外排序过程和算法。文件作为一种外存的数据结构，也在本章介绍。
数据结构的上机实习是课程教学不可或缺的重要环节，第13章和附录A是专门为上机实习而编写的。其中，第13章为实习指导和实习题，附录A介绍软件工程的基本概念，包括软件开发方法、软件文档写作和系统测试方法。
附录B是书中出现的专有名词的中英文对照表。
本书满足高等院校计算机科学与技术专业和其他相关专业的“数据结构”课程80学时的教学安排。对于学时数少于80学时的授课计划，可根据实际学时对内容加以取舍。作者已在目录中将难度较大或非基本的章节标上了*号，供读者参考。
本书的编写得到了南京邮电大学领导的帮助和关心，也得到了西安电子科技大学出版社马乐惠主任的大力推荐和支持，在此表示衷心感谢。书中若有不当之处，敬请读者批评指正。
|
| 其 它： |
|
|
|
中国大学出版社协会 |
首页 |
宏观指导 |
出版社天地 |
图书代办站 |
教材图书信息 |
教材图书评论 |
在线订购 |
教材征订
