数据结构——C语言描述 - 中国高校教材图书网
|
书名： |
数据结构——C语言描述
|
| ISBN： | ISBN 978-7-5606-1114-3 |
责任编辑： | |
| 作者： |
耿国华
相关图书
|
装订： | 平装 |
| 印次： | 1-1 |
开本： | 16开 |
| 定价： |
￥42.00
折扣价：￥39.90
折扣：0.95
节省了2.1元
|
千字数： |
446
|
| 出版社： |
西安电子科技大学出版社 |
装订： | 平装 |
| 出版日期： |
2008-07-01 |
页数： |
|
| 每包册数： |
|
立体化教材： | |
| 专业分类： | 计算机在各领域的应用 |
中图法分类： | 自动化技术、计算机技术 |
| 用途分类： | 大学本科教材 |
读者分类： | 普通读者 |
| 国家规划教材： |
|
省部级规划教材： |
|
| 入选重点出版项目： |
|
获奖信息： |
|
| 印刷日期： | |
|
|
|
|
| 内容简介： |
本书主要包括数据结构的基本概念、 基本的数据结构（线性表、 栈和队列、 串、 数组与广义表、 树、 图）和基本技术（查找方法与排序方法）三个部分。 本书除重点介
绍了数据的组织技术外， 还贯穿了程序设计中应掌握的技术， 如参数传递技术、 动态处理的指针技术、 数组技术、 递归技术与队列技术等。 另外， 本书给出了许多经典的查找与排序算法， 为读者继续拓展思路提供线索。
本书是在第一版的基础上修订而成的， 内容丰富， 概念清晰， 技术实用， 同时还配
有大量的例题、 习题和实习题。 本书将读者熟悉的标准C语言作为算法描述的语言， 采用了面向对象的方法来讲述数据结构中的技术， 这种描述体系也是本书特色之一。
本书既可作为大专院校计算机等专业数据结构课程的教材， 也可供从事计算机开发和
应用的工程技术人员学习和参考。
需要本书所列结构定义函数原型定义及每章演示示例的读者可通过西北大学校园网下载获取。本书同时配有多媒体教学课件，可供教师助教使用， 需要者可与作者联系：
ghgeng@nwu.edu.cn。
|
| 作者简介： |
|
|
| 章节目录： |
编者
2008年6月
目 录
第1章 绪论 1
1.1 什么是数据结构（定义） 1
1.2 数据结构的内容 9
1.3 算法 10
1.4 算法描述的工具 12
1.5 对算法作性能评价 16
1.6 关于数据结构的学习 20
习题 22
实习题 23
第2章 线性表 24
2.1 线性表的概念及运算 24
2.1.1 线性表的逻辑结构 24
2.1.2 线性表的抽象数据类型定义 25
2.2 线性表的顺序存储 26
2.2.1 线性表的顺序存储结构 26
2.2.2 线性表顺序存储结构上的基本运算 27
2.3 线性表的链式存储 32
2.3.1 单链表 32
2.3.2 单链表上的基本运算 33
2.3.3 循环链表 40
2.3.4 双向链表 42
*2.3.5 静态链表 44
2.3.6 顺序表和链表的比较 47
2.4 一元多项式的表示及相加 48
习题 52
实习题 54
第3章 限定性线性表——栈和队列 55
3.1 栈 55
3.1.1 栈的定义 55
3.1.2 栈的表示和实现 56
3.1.3 栈的应用举例 61
3.1.4 栈与递归的实现 67
3.2 队列 73
3.2.1 队列的定义 73
3.2.2 队列的表示和实现 74
3.2.3 队列的应用举例 78
习题 80
实习题 82
第4章 串 83
4.1 串的定义 83
4.2 抽象数据类型串的实现 85
4.2.1 定长顺序串 85
4.2.2 堆串 89
4.2.3 块链串 94
4.3 串的应用举例： 文本编辑 95
习题 96
实习题 97
第5章 数组和广义表 98
5.1 数组的定义和运算 98
5.2 数组的顺序存储和实现 99
5.3 特殊矩阵的压缩存储 101
5.3.1 三角矩阵 102
5.3.2 带状矩阵 103
5.3.3 稀疏矩阵 104
5.4 广义表 113
习题 117
实习题 118
第6章 树和二叉树 119
6.1 树的概念与定义 119
6.2 二叉树 121
6.2.1 二叉树的定义与基本操作 121
6.2.2 二叉树的性质 122
6.2.3 二叉树的存储结构 124
6.3 二叉树的遍历与线索化 126
6.3.1 二叉树的遍历 126
6.3.2 基于栈的递归消除 129
6.3.3 遍历算法应用 132
6.3.4 线索二叉树 137
6.4 树、 森林和二叉树的关系 141
6.4.1 树的存储结构 141
6.4.2 树、 森林与二叉树的相互转换 143
6.4.3 树与森林的遍历 146
6.5 哈夫曼树及其应用 147
6.5.1 哈夫曼树 147
6.5.2 哈夫曼编码 149
6.5.3 哈夫曼编码算法的实现 152
习题 153
实习题 155
第7章 图 156
7.1 图的定义与基本术语 156
7.1.1 图的定义 156
7.1.2 基本术语 158
7.2 图的存储结构 160
7.2.1 邻接矩阵表示法 160
7.2.2 邻接表表示法 163
7.2.3 十字链表 165
7.2.4 邻接多重表 167
7.3 图的遍历 168
7.3.1 深度优先搜索 169
7.3.2 广度优先搜索 172
7.4 图的连通性问题 174
7.4.1 无向图的连通分量 174
7.4.2 最小生成树 175
7.5 有向无环图的应用 179
7.5.1 拓扑排序 179
7.5.2 关键路径 182
7.6 最短路径 187
7.6.1 求某一顶点到其它各顶点的最短路径 188
7.6.2 求任意一对顶点间的最短路径 190
习题 192
实习题 195
第8章 查找 196
8.1 查找的基本概念 196
8.2 基于线性表的查找法 197
8.2.1 顺序查找法 197
8.2.2 折半查找法 198
8.2.3 分块查找法 200
8.3 基于树的查找法 201
8.3.1 二叉排序树 201
8.3.2 平衡二叉排序树 207
8.3.3 B-树 215
8.4 计算式查找法——哈希法 224
8.4.1 哈希函数的构造方法 224
8.4.2 处理冲突的方法 226
8.4.3 哈希表的查找过程 228
8.4.4 哈希法性能分析 229
习题 231
实习题 233
第9章 内部排序 234
9.1 排序的基本概念 234
9.2 插入类排序 235
9.2.1 直接插入排序 235
9.2.2 折半插入排序 237
9.2.3 表插入排序 238
9.2.4 希尔排序 239
9.3 交换类排序法 241
9.3.1 冒泡排序（相邻比序法） 241
9.3.2 快速排序 243
9.4 选择类排序法 246
9.4.1 简单选择排序 246
9.4.2 树形选择排序 247
9.4.3 堆排序 248
9.5 归并排序 253
9.6 分配类排序 255
9.6.1 多关键字排序 255
9.6.2 链式基数排序 255
9.6.3 基数排序的顺序表结构 259
9.7 各种排序方法的综合比较 259
习题 260
实习题 262
第10章 外部排序 263
10.1 外存信息的特性 263
10.1.1 磁带存储器 263
10.1.2 磁盘存储器 264
10.2 外排序的基本方法 266
10.2.1 磁盘排序 266
10.2.2 磁带排序 271
习题 274
附录 数据结构试题选编 275
附录A 样卷一 275
附录B 样卷二 278
附录C 样卷三 282
附录D 样卷四 283
附录E 样卷五 285
附录F 样卷六 287
附录G 样卷七 290
参考文献 293
|
| 精彩片段： |
|
|
| 书 评： |
第 一 版 前 言
我们生活在一个物质的世界， 如果将物质世界中的事与物数字化， 那么它们在计算机中的表现则为数据。 这些数据来源于现实， 表征着具体的意义， 并且在计算机中有着统一的表
示方法， 因而成为被计算机程序处理的符号集合。 研究数据在计算机中的表示方法、 关联方
法、 存储方法以及其相关的典型处理方法， 就构成了数据结构课程的主要内容。
早在20世纪80年代初, 数据结构课程就已成为国内计算机专业教学计划中的核心课程。 目
前， ACM/IEEE CC - 2001教程已将算法与数据结构类课程列为核心课程之首， 数据结
构在信息学科中的重要地位日益凸显。
由于数据是计算机处理的对象， 使用计算机的过程就是对数据加工处理的过程， 因而数据
的组织与结构被确立为计算机科学中最为基本的内容。 通过对数据结构的学习， 使读者能够
以问题求解方法、 程序设计方法及一些典型的数据结构算法为研究对象， 学会分析数据对象
的特征， 掌握数据组织的方法和在计算机中的表示方法， 为数据选择适当的逻辑结构、 存
储结构以及相应的处理算法， 初步掌握算法的时间、 空间复杂度的分析技巧， 培养良好的程
序设计风格以及进行复杂程序设计的技能。
人类解决问题的思维方式可分为推理方式和算法方式两大类。 推理方式是从抽象的公理体
系出发， 通过演绎、 归纳、 推理来求证结果， 解决特定问题。 这种推理方式是通过数学
训练得到的。 算法方式则是凭借构造性思维， 从具体操作规范入手， 通过操作过程的构造实施来解决特定问题。 在软件系统的开发过程中所凭借的思维方法在本质上不同于公理系统的
思维方法， 而是一种算法构造性思维方法。 让学生理解、 习惯和熟悉这一套算法构造性思维
方法， 是本门课程教学的重要内容和主要难点。 对于软件开发人员来说， 仅仅了解开发工
具的语言规则和使用过程是远远不够的， 只有培养学生的数据抽象能力、 算法设计能力以及创造性思维的方法， 才能够举一反三、 触类旁通， 从而达到应用知识解决复杂问题的目的。
本书采用面向对象的方法来讲述数据结构的技术， 并将C语言作为算法描述语言。 由于
目前C语言被广泛地使用， 而且数据结构的算法本身又是底层的基本算法， 采用大家熟悉的C
语言去刻画算法中的主要概念， 可以将读者的注意力集中在算法的理解上。 本书贯穿了面
向对象的观点， 首先引进了抽象数据类型的概念及其基本性质， 然后给出了如何用C语言表
示抽象数据类型的方法， 即在每章开始使用抽象数据类型（ADT）定义， 其中不仅包含了数
学模型， 同时还包含了定义在这个模型上的数据组织和数据运算的名称， 接下来在具体章节
中再详细介绍相应的数据结构及运算实现。 抽象数据类型的概念反映了程序设计的两级抽象
，过程调用完成做什么， 过程定义去规范如何做。 一个抽象数据类型确定了一个模型， 但
将模型的实现细节隐藏起来； 它定义了一组运算， 但将运算的实现过程隐藏起来。 书中大量
的C函数的程序实例， 正是数据抽象与过程抽象的结合。 这就使数据结构的表示得以简化，
突出了算法表示的实质， 其中所列算法只需补充上相应的类型定义与调用， 就可成为可直接上机运行使用的C程序。
本书分为三个部分， 其中第一部分（第1章）是数据结构的基本概念部分； 第二部分（第2
~7章）是基本的数据结构部分， 包括线性结构（线性表、 栈和队列、 串、 数组与广义表）
与非线性结构（树、 图）； 第三部分（第8~10章）是基本技术部分， 包括查找方法与排
序方法。 除了数据组织技术外， 还包括了一些重要的程序设计技术， 如参数传递技术、 动态处理的指针技术、 数组技术（抽象规律处理）、 递归技术与队列技术。 此外， 书中给出了许多精彩的查找与排序的典型算法， 它们是人们在数据处理中智慧的结晶， 我们力求将经典算法的思路表现出来， 为学习者继续拓展思路提供线索。 本书每章后附有习题与实习题， 在附录中给出了两套标准化考题样卷， 其余四套均为硕士研究生入学考试的样卷， 以便于读者练习。
数据结构作为西北大学重点课程建设项目， 被列为“面向21世纪课程教材”， 在编写的过
程中得到西北大学教务处的大力支持； 曾指导我学习数据结构的清华大学的严蔚敏教授和唐
泽圣教授, 他们敏锐的洞察力和对教学内容的精辟讲解， 包括尔后多年中所给予的多方面指
导， 使我受益终生； 学生们学习该课程的热情为我们注入了深入教学研究的动力； 赵政文
教授仔细校审全书， 并提出了意见与建议。 所有这些都将极大地促进我们数据结构教学质量的提高， 在此表示衷心的感谢！
本书由耿国华教授任主编， 张德同老师任副主编， 其中的第1章、 2章、 3章、 6章、 7
章、 9章及附录由耿国华编写， 第5章、 8章由张德同编写， 第4章由冯宏伟编写， 第10章由卢燕宁编写。 本书算法均在Turbo C 2.0 环境下调试通过。 在本书中， 我们融入多年从事数据结构课程教学的体会， 恳请读者赐教指正。
耿国华
2001年12月
第 二 版 前 言
数据结构是重要的计算机专业基础课， 也是计算机科学与技术人才素质培养框架中的中坚
课程。 该课程一般在大学二年级开设， 具有承上启下的重要作用， 既要对前面学习的软件
技术进行总结和提高， 还要为后续专业课程的学习提供帮助。 数据结构对学生软件开发能力的培养至关重要， 掌握好相关的知识会为今后的专业生涯打下牢固的基础。
根据技术发展和教学要求， 我们在第一版教材的基础上主要做了以下修改与补充：
（1） 在第1章中增加了C语言中指针、结构体以及类型定义等复杂类型的使用与示例， 便于
读者掌握程序设计中对复杂类型的选用；
（2） 增加了算法复杂度分析的范例， 针对同一个问题给出两个复杂度不同的算法， 便于
读者更直观地理解算法复杂度的概念和算法复杂度分析的方法；
（3） 与抽象数据类型定义中的操作一致， 在部分章节中增加了相应结构下的初始化操作，
便于读者理解结构， 并建立完整的结构体系（如第2章）；
（4） 对部分算法做了优化处理， 尽可能增强算法的科学性和准确性， 同时调整了相关内
容的排列顺序（如第6章中， 将原6.6节移到了6.3节， 将“由遍历序列确定二叉树”部分作
为遍历算法的一个具体应用， 有助于加深读者对遍历算法的理解， 符合认知规律）；
（5） 在部分章节增加了一些典型技术算法内容（如在第5章中增加了广义表的基本操作算法
， 在第8章中增加了用判定树计算折半查找的平均查找长度的图示和讲解， 在第9章中增加
了归并排序的初始调用过程）， 以突出典型技术的完整性；
（6） 对附录中的样卷做了较大更新， 以供读者学习参考。
计算机科学体现的是一种创造性思维活动， 其教育必须面向设计。 数据结构的学习过程就
是创造性思维的培养过程， 而且技能培养的重要程度不亚于知识传授， 因此教学的重点在于
让学生理解和掌握算法构造的思维方法。
本教材自第一版推出以来得到了广大读者的厚爱， 先后经过了十余次印刷， 已广泛应用于全国多所高校的计算机、通信、电子、自动化、数学等专业的教学中， 并获得2005年陕西省高
校优秀教材一等奖。 作者衷心感谢广大读者对我们所编教材的信任， 真诚地期待着大家在
使用本教材的过程中提出意见和建议， 使之能够不断完善， 更好地服务于教学。
|
| 其 它： |
|
|
|
中国大学出版社协会 |
首页 |
宏观指导 |
出版社天地 |
图书代办站 |
教材图书信息 |
教材图书评论 |
在线订购 |
教材征订
