数据结构(第二版) (2008 年度畅销榜NO.7049 )

数据结构(第二版)是1998年出版的原书的修订版：修订版在保持了原书基本框架和特色的基础上对其中某些内容作了增删和修改：
书中讨论包括线性表、堆栈、队列、树、图等在内的各种数据结构和文件的基本概念，逻辑结构与存储结构，以及在这些结构的基础上实施的有关操作。算法用C语言书写，通俗易学，具有较好的可读性与可移植性。全书共十一章，每一章都配有丰富的、各种类型的习题，并且提供了体现各章基本内容的上机实践题。
本书可作为高等教育自学考试计算机专业文凭考试课程的理想教材，也可作为普通高等院校计算机专业本科学生“数据结构”课程的教材与教学参考书。

第一章 绪论
1. 1 什么是数据结构
*1. 2 数据结构的发展简史及其在计算机科学中的地位
1. 3 算法
1. 3. 1 算法及其性质
1. 3. 2 基本算法
1. 3. 3 算法的描述
1. 4 算法分析
1. 4. 1 时间复杂度
1. 4. 2 空间复杂度
1. 4. 3 其他方面
*1. 5 算法设计的基本步骤
习题
第二章 线性表
2. 1 线性表的定义及其基本操作
2. 1. 1 线性表的定义
2. 1. 2 线性表的基本操作
2. 2 线性表的顺序存储结构
2. 3 线性链表及其操作
2. 3. 1 线性链表的构造
2. 3. 2 线性链表的基本算法
2. 4 循环链表及其操作
2. 5 双向链表及其操作
2. 5. 1 双向链表的构造
2. 5. 2 双向链表的插入与删除算法
2. 6 链表的应用举例
2. 6. 1 链式存储结构下的一元多项式加法
2. 6. 2 打印文本文件的最后n行
习题
第三章 数组
3. 1 数组的概念
3. 1. 1 一维数组
3. 1. 2 多维数组
3. 2 数组的存储结构
3. 3 矩阵的压缩存储
3. 3. 1 对称矩阵的压缩存储
3. 3. 2 对角矩阵的压缩存储
3. 4 稀疏矩阵的三元组表表示
3. 4. 1 稀疏矩阵的三元组表存储方法
*3. 4. 2 稀疏矩阵的转置算法
*3. 4. 3 稀疏矩阵相乘算法
*3. 5 稀疏矩阵的十字链表表示
3. 6 数组的应用举例
3. 6. 1 一元多项式的数组表示
3. 6. 2 n阶魔方
习题
第四章 堆栈和队列
4. 1 堆栈的概念及其操作
4. 1. 1 堆栈的定义
4. 1. 2 堆栈的基本操作
4. 2 堆栈的顺序存储结构
4. 2. 1 顺序堆栈的构造
4. 2. 2 顺序堆栈的基本算法
*4. 2. 3 多个堆栈共享连续空间问题
4. 3 堆栈的链式存储结构
4. 3. 1 链接堆栈的构造
4. 3. 2 链接堆栈的基本算法
4. 4 堆栈的应用举例
4. 4. 1 数制转换
4. 4. 2 堆栈在递归中的应用
4. 4. 3 表达式的计算
4. 4. 4 又一个趣味游戏--迷宫
4. 5 队列的概念及其操作
4. 5. 1 队列的定义
4. 5. 2 队列的有关操作
4. 6 队列的顺序存储结构
4. 6. 1 顺序队列的构造
4. 6. 2 顺序队列的基本算法
4. 6. 3 循环队列
4. 7 队列的链式存储结构
4. 7. 1 链接队列的构造
4. 7. 2 链接队列的基本算法
习题
第五章 广义表
5. 1 广义表的概念
5. 2 广义表的存储结构
*5. 3 多元多项式的表示
习题
第六章 串
6. 1 串的基本概念
6. 1. 1 串的定义
6. 1. 2 串的几个概念
6. 2 串的基本操作
6. 3 串的存储结构
6. 3. 1 串的顺序存储结构
6. 3. 2 串的链式存储结构
6. 4 串的几个操作
习题
第七章 树与二叉树
7. 1 树的基本概念
7. 1. 1 树的定义
7. 1. 2 树的逻辑表示方法
7. 1. 3 基本术语
7. 1. 4 树的性质
7. 1. 5 树的基本操作
*7. 2 树的存储结构
7. 2. 1 多重链表表示
7. 2. 2 三重链表表示
7. 3 二叉树
7. 3. 1 叉树的定义
7. 3. 2 叉树的基本操作
7. 3. 3 两种特殊形态的二叉树
7. 3. 4 二叉树的性质
*7. 3. 5 二叉树与树. 树林之间的转换
7. 4 二叉树的存储结构
7. 4. 1 叉树的顺序存储结构
7. 4. 2 叉树的链式存储结构
7. 5 树的遍历
7. 5. 1 二叉树的遍历
*7. 5. 2 树和树林的遍历
7. 5. 3 由遍历序列恢复二叉树
7. 6 线索二叉树
7. 6. 1 线索二叉树的构造
7. 6. 2 线索二叉树的利用
*7. 6. 3 二叉树的线索化算法
* 7. 6. 4 线索二叉树的更新
7. 7 二叉排序树
7. 7. 1 二叉排序树的定义
7. 7. 2 二叉排序树的建立
*7. 7. 3 在二叉排序树中删除结点
7. 7. 4 二叉排序树的查找
*7. 8 平衡二叉树
7. 9 哈夫曼树及其应用
7. 9. 1 哈夫曼树的概念
* 7. 9. 2 哈夫曼编码
习题
第八章 图
8. 1 图的基本概念
8. 1. 1 图的定义和基本术语
8. 1. 2 图的基本操作
8. 2 图的存储方法
8. 2. 1 邻接矩阵存储方法
8. 2. 2 邻接表存储方法
*8. 2. 3 有向图的十字链表存储方法
*8. 2. 4 无向图的多重邻接表存储方法
8. 3 图的遍历
8. 3. 1 深度优先搜索
8. 3. 2 广度优先搜索
8. 4 最小生成树
8. 4. 1 普里姆算法
8. 4. 2 克鲁斯卡尔算法
8. 5 最短路径问题
8. 6 AOV网与排扑排序
8. 6. 1 AOV网
8. 6. 2 拓扑排序
8. 6. 3 拓扑排序算法
8. 7 AOE网与关键路径
8. 7. 1 AOE网
8. 7. 2 关键路径
8. 7. 3 关键路径的确定
习题
第九章 文件及查找
9. 1 文件概述
9. 1. 1 基本术语
9. 1. 2 文件的存储介质
9. 1. 3 文件的基本操作
9. 2 顺序文件
9. 2. 1 连续顺序文件及其查找
9. 2. 2 链接顺序文件及其查找
9. 3 索引文件
9. 3. 1 稠密索引文件
9. 3. 2 非稠密索引文件
*9. 3. 3 多级索引文件
9. 4 B-树和B+树
9. 4. 1 B-树的基本概念
*9. 4. 2 B-树的基本操作
9. 4. 3 B+树的基本概念
*9. 4. 4 B+树的基本操作
9. 5 散列(Hash)文件
9. 5. 1 概述
9. 5. 2 散列函数的几种构造方法
9. 5. 3 处理冲突的方法
9. 5. 4 散列文件的操作
*9. 5. 5 散列法的平均查找长度
习题
第十章 内排序
10. 1 概述
10. 1. 1 排序的基本概念
10. 1. 2 排序的分类
10. 2 插入排序
10. 3 选择排序
10. 4 泡排序
10. 5 谢尔排序
10. 6 快速排序
10. 7 堆积排序
10. 7. 1 堆积的定义
10. 7. 2 堆积排序算法
10. 8 二路归并排序
10. 8. 1 归并子算法
10. 8. 2 一趟归并扫描子算法
10. 8. 3 二路归并排序算法
*10. 9 基数排序
10. 10 各种内排序方法的比较
10. 10. 1 稳定性比较
10. 10. 2 复杂性比较
习题
*第十一章 外排序
11. 1 概述
11. 2 磁带排序
11. 2. 1 多路平衡归并排序法
11. 2. 2 多步归并排序
11. 3 初始归并段的合理分布与产生
11. 3. 1 初始归并段的合理分布
11. 3. 2 一种产生初始归并段的方法一置换选择排序
11. 4 磁盘排序
习题
上机实践题
附录 北京市高等教育学历文凭考试"数据结构"课程考试大纲
主要参考文献

高等教育学历文凭考试是我国高等教育事业发展过程中出现的一个新生事物. 它是社会力量办学与国家考试相结合, 以宽进严出. 教考分离. 全日制教学为特点的高等教育形式. 这种形式从它产生之日起, 就受到社会各界的重视和赞誉, 认为它为我国社会主义经济建设对人才的大量需求又提供了一种培养手段, 同时它也得到了国家有关领导同志的称赞, 认为这是"穷国办大教育"的一条好的途径. 北京在全国是最早进行这项试点工作的, 目前有24所民办高校参加, 开设的专业有16个, 在校生3万余人, 年均招生规模都在万人左右, 其中计算机应用专业1997年成为招生规模最大的专业. 经过五年的实践和总结, 特别是结合国家为民办高等教育培养目标"应用性. 职业性"定位的理解, 我们感到, 我市试点工作在发展过程中, 基本建设做得还不够, 其中一个表现就是抓教材建设做得不够, 特别是目前市场上还缺乏与高等职业技术教育相匹配的有关教材, 导致目前参加文凭考试的民办学校在教学上基本上是借用普通高校的教材, 因而教材与培养要求上的矛盾就尤显突出. 我们非常感谢的是, 北京航空航天大学计算机系非常积极和认真地提出了要组织编写一套适合这种考试的教材的建议, 并做了很具体的安排, 北京航空航天大学的许多专家. 教授克服了学校教学. 科研任务繁忙的困难, 按时. 保质地完成了撰稿工作. 同时此项工作也得到了科学出版社有关同志的大力配合, 没有他们耐心. 细致地做组稿和出版等工作, 这套教材能这样快地面世是不可想象的. 经过各方的通力协作, 这套教材终于可以奉献给大家了. 我们认为这套教材基本上体现了高等教育学历文凭考试计算机应用专业培养方向上的要求, 在内容上也是科学. 严谨的, 我们同意把这套教材作为推荐使用的教材. 同时, 我们也希望社会各界将对这套教材的意见和建议及时反馈给我们, 以便使它不断完善. 谢谢大家. 北京市高等教育自学考试委员会办公室 1998年6月12日

随着计算机科学的迅速发展, 数据结构作为一门新兴学科已经越来越受到计算机界的重视, 被认为是计算机领域的一门十分重要的基础学科. 正是基于这样的原因, 我们根据国务院发布的《高等教育自学考试暂行条例》精神, 以及北京市高等教育自学考试委员会关于高等教育文凭考试"数据结构"课程考试大纲, 编写了这本《数据结构》. 本书较详细地介绍了线性结构. 非线性结构和文件三大类数据结构, 阐述了在这些结构上实施的有关算法的设计与实现. 程序设计语言与数据结构之间存在着密切的联系：程序设计语言为数据结构的描述提供了很好的手段, 数据结构为程序设计语言类型系统的发展与完善奠定了基础. 为此, 本书强调了数据结构本身的技术及其在程序设计中的应用. 全书共分十一章. 第一章阐述了数据结构的一些基本概念, 第二章至第六章主要讨论线性结构, 其中包括线性表. 堆栈. 队列以及字符串等, 第七章与第八章讨论非线性结构, 重点讨论树和二叉树. 图的基本概念及其应用, 第九章至第十一章重点讨论文件的基本概念, 其中主要是各种数据文件的组织方法及有关的操作. 在本书的编写过程中, 我们本着着重基础. 注意应用的原则, 每一章除了必要的例题之外, 还配有适量的习题与上机题供读者练习. 凡是阅读过本书并独立完成习题的读者, 都能掌握本书所要求的基本概念. 基本技术与基本方法. 数据结构是计算机专业一门实践性很强的专业基础课程. 通过该课程的学习, 应使学生能够运用数据结构提供的方法与技巧更好地进行算法设计和程序设计. 所以, 本书在讨论各种数据结构基本运算的同时, 都给出了相应的算法. 算法全部采用SPARKS语言描述, 具有较好的可读性与可移植性. SPARKS语言属于一种类PASCAL语言, 它几乎包括了所有程序设计语言所共有的. 基本的可执行语句, 且不受具体程序设计语言在词法. 语法以及语义上的严格限制, 因而, 用SPARKS语言描述的算法具有简洁. 易懂. 易学等特点, 熟悉任何一种高级程序设计语言的读者, 只要对书中的算法稍做修改或补充, 便可以得到计算机所能接受的程序. 本书取材广泛. 内容全面, 作为高等教育自学考试计算机专业学生的教材, 讲授时间为50～70学时, 也可以根据具体情况做一些增减, 有些内容只作为阅读参考, 不作要求, 如书中带*号的章节. 考虑到专科教育的针对性. 实践性和应用性, 本书也可以作为高等专科学校. 职工大学. 职业大学. 夜大学以及函授大学等大专类计算机硬件. 软件专业的教材或参考书, 同时, 本书还可以用作从事计算机系统软件和应用软件设计与开发人员的参考资料. 本书是作者在高等学校从事多年教学实践的基础上, 对原有讲义和教材进行多次修改并参考了兄弟院校同类教材编著完成的. 因此, 在内容上努力遵循深入浅出的原则, 在基本概念的阐述方面力求通俗详尽, 以便于读者自学. 由于数据结构本身是一门年轻的学科, 内容还在不断变化与更新, 加上作者水平有限以及时间仓促等原因, 书中的错误在所难免, 恳切希望读者批评指正. 作 者 1998年6月于北京

无封面