算法与数据结构（C语言版） (2010 年度畅销榜NO.1625 )

● 系统地介绍了各种传统的数据结构，包括线性表、栈、队列、串、数组、树、图等。
● 强调算法与数据结构的密不可分性。
● 采用容易转换为C语言程序的类C语言描述数据结构和算法。
● 引进抽象数据类型的概念，将数据类型与其上的操作封装为一体。
● 针对不同的抽象数据类型讨论不同的存储方法，并且研究不同存储方法的可能算法，体现了计算机学科方法论的理论、抽象和设计三个过程。
● 为方便广大教师，增强教学效果，本书另配有电子课件。
本书以较通俗的语言，按照由易到难的原则，详细介绍了各种数据结构的基本概念、逻辑特性和物理特性，对各种结构定义了相应的抽象数据类型(ADT)以及相关的操作和算法。本书采用类C语言描述算法，并给出了各种算法的效率分析，以及这些结构在计算机科学及其他领域的应用。在各章末尾，还给出了几个算法设计的例子。
本书可作为高等院校计算机专业的教材，同时也可供计算机工程技术人员参考。
版权所有，侵权必究。

前言
第1章 概论
1. 1 引言
1. 1. 1 解决问题的步骤
1. 1. 2 一个例子
1. 2 数据结构
1. 2. 1 为什么要学习数据结构
1. 2. 2 有关概念和术语
1. 3 抽象数据类型
1. 4 类C语言描述
1. 5 算法和算法分析
1. 5. 1 算法的定义及算法设计的要求
1. 5. 2 算法与数据结构和程序
1. 5. 3 算法性能分析与度量
1. 5. 4 复杂度函数的增长率
1. 5. 5 复杂度分析的例子
第2章 线性表
2. 1 线性表的类型定义
2. 1. 1 线性表的概念
2. 1. 2 线性表的抽象数据类型
2. 1. 3 线性表的例子
2. 2 线性表的顺序表示和实现
2. 2. 1 线性表的顺序表示
2. 2. 2 顺序表操作的实现
2. 3 线性表的链式表示和实现
2. 3. 1 单链表的表示
2. 3. 2 线性链表操作的实现
2. 4 线性表实现方法的比较
2. 5 循环链表
2. 6 双链表
2. 7 静态链表
*2. 8 算法设计举例
第3章 栈和队列
3. 1 栈
3. 1. 1 栈的类型定义
3. 1. 2 栈的表示和实现
3. 1. 3 顺序栈和链栈的比较
3. 2 队列
3. 2. 1 队列的类型定义
3. 2. 2 循环队列
3. 2. 3 链队--队列的链式表示
和实现
*3. 3 递归
3. 3. 1 递归的定义
3. 3. 2 递归的实现
3. 3. 3 递归和迭代
3. 3. 4 递归的消除
*3. 4 算法设计举例
第4章 串
4. 1 串的类型定义
4. 2 串的表示和实现
4. 2. 1 串的顺序存储结构
4. 2. 2 串的链式存储结构
*4. 3 串的模式匹配
4. 3. 1 朴素的模式匹配算法
4. 3. 2 首尾模式匹配算法
4. 3. 3 KMP算法
4. 4 串的应用举例
*4. 5 算法设计举例
第5章 数组和广义表
5. 1 数组的概念及其基本操作
5. 2 数组的顺序存储
5. 3 矩阵的压缩存储
5. 3. 1 特殊矩阵
5. 3. 2 稀疏矩阵
*5. 4 广义表
5. 4. 1 广义表的定义
5. 4. 2 广义表的存储结构
*5. 5 算法设计举例
第6章 树
6. 1 树的概念及操作
6. 2 二叉树
6. 2. 1 叉树的概念及操作
6. 2. 2 二叉树的性质
6. 2. 3 二叉树的存储结构
6. 3 二叉树的遍历
*6. 4 线索二叉树
6. 5 树和森林
6. 5. 1 树的存储结构
6. 5. 2 森林. 树. 二叉树
的相互转换
6. 5. 3 树和森林的遍历
6. 6 哈夫曼树及其应用
6. 6. 1 最优二叉树(哈夫曼树)
6. 6. 2 哈夫曼编码
*6. 7 算法设计举例
第7章 图
7. 1 图的定义和术语
7. 2 图的存储结构
7. 2. 1 数组表示法
7. 2. 2 邻接表
*7. 2. 3 十字链表
*7. 2. 4 邻接多重表
7. 3 图的遍历
7. 3. 1 深度优先搜索
7. 3. 2 广度优先搜索
7. 4 图的连通性问题
7. 4. 1 图的连通分量和生成树
7. 4. 2 最小生成树
7. 5 有向无环图及其应用
7. 5. 1 拓扑排序
*7. 5. 2 关键路径
7. 6 最短路径
7. 6. 1 从某个源点到其他各顶点的
最短路径
7. 6. 2 每一对顶点之间的最短路径
*7. 7 网络流问题
*7. 8 算法设计举例
第8章 动态存储管理
8. 1 概述
8. 2 可利用空间表及分配方法
8. 3 边界标识法
8. 4 伙伴系统
第9章 集合
9. 1 概述
9. 2 线性表上的查找
9. 2. 1 顺序表的查找
9. 2. 2 有序表的查找
9. 3 索引表上的查找
9. 4 树表上的查找
9. 4. 1 二叉排序树
9. 4. 2 平衡二叉树
*9. 4. 3 B-树
*9. 4. 4 键树
9. 5 哈希表
9. 5. 1 哈希表查找的基本概念
9. 5. 2 构造哈希函数的方法
9. 5. 3 哈希冲突的解决方法
9. 5. 4 哈希表的查找及分析
*9. 6 算法设计举例
第10章 排序
10. 1 概述
10. 2 插入排序
10. 2. 1 直接插入排序
10. 2. 2 折半插入排序
*10. 2. 3 二路插入排序
*10. 2. 4 表插入排序
10. 2. 5 希尔排序
10. 3 交换排序
10. 3. 1 起泡排序
10. 3. 2 快速排序
10. 4 选择排序
10. 4. 1 直接选择排序
10. 4. 2 树形选择排序
10. 4. 3 堆排序
10. 5 归并排序
10. 6 分配排序
10. 7 各种内部排序方法的比较
10. 8 外部排序
10. 8. 1 文件管理
10. 8. 2 外部排序的方法
10. 8. 3 多路平衡归并排序
10. 8. 4 置换选择排序
*10. 8. 5 最佳归并树
*10. 8. 6 磁带排序
*10. 9 算法设计举例
第11章 文件
11. 1 文件的基本概念
11. 2 顺序文件
11. 3 索引文件
11. 4 索引顺序文件
11. 4. 1 ISAM文件
*11. 4. 2 VSAM文件
11. 5 散列文件
*11. 6 多关键字文件
11. 6. 1 多重表文件
11. 6. 2 倒排文件
参考书目

"数据结构"是20世纪70年代开始设立的计算机科学与技术专业的基础课, 现在是其重要的核心课程. 随着计算机软. 硬件技术的发展, 计算机在各个学科和领域得到广泛应用, 其当今应用的一个主要方面就是数据处理, 如情报检索. 数据采集. 企业管理. 决策分析和人工智能等. 而应用到这些领域时所面临的首要问题就是对于信息量大. 种类繁多. 结构复杂的数据和数据关系的处理, 由此必须设计高级的数据结构和数据组织, 以便有效地实现数据采集. 数据组织. 数据存储. 数据传输和数据处理. 数据结构主要研究数据的逻辑结构. 数据在计算机中的物理结构, 以及处理不同结构数据的算法. 我们研究数据结构的目的是为了学会编写更高效的程序, 而高效. 简洁的程序取决于数据结构和算法的设计. 现在, 有关算法与数据结构的教材, 一部分侧重于算法的基本思想和步骤, 用伪代码描述, 一部分用程序语言描述, 侧重于算法的程序实现. 前者侧重于对数据结构原理的阐述, 不利于学生掌握算法的程序实现以及对算法的分析. 比较. 后者增加了对数据元素的描述, 从而使得程序更难理解. 本教材对数据结构和算法用类C语言描述, 数据结构和算法在设计本质上是属于底层的, 在本书中并不提供可直接上机运行的源代码, 而是提供一种类C语言伪代码来描述算法的基本思想和基本步骤. 此外, 用类C语言描述的算法容易转换为C语言程序. 本书系统全面地介绍了各种传统的数据结构, 对每种数据结构及相关算法都进行了时间和空间效率的分析, 强调算法与数据结构的密不可分性, 引进抽象数据类型概念, 将数据类型与其上的操作封装为一体, 为面向对象的程序设计方法奠定了坚实的基础. 此外, 针对不同的抽象数据类型讨论不同的存储方法, 并且研究不同存储方法的可能算法, 从而体现了计算机学科方法论的理论. 抽象和设计三个过程. 全书分为11章：第1章是概论, 解释了从问题到程序的求解过程, 以及在这一过程中抽象数据类型的表述和作用, 介绍了程序的运行步骤及复杂度, 第2章介绍了有关线性表的概念及其基本操作, 该章是后续章节的基础, 第3章在第2章的基础上讨论了操作受限的线性表--栈与队列的特点, 并列举了几个应用示例, 第4章简要给出了非数值处理--串的处理方法, 第5章主要是关于程序设计中的一种常用数据类型--数组在计算机内部的表示和实现, 同时介绍了广义表的概念, 第6章描述了非线性复杂数据结构--树, 它是解决决策和博弈等问题的基本结构, 第7章是关于图的内容, 包括有向图和无向图. 图是一种比树更复杂的数据结构, 第8章涉及存储管理中应用的基本方法, 第9章以集合作为数据模型, 讨论了查找的方法和技术, 第10章介绍了一些常用的排序算法, 包括内部排序和外部排序, 第11章简要介绍了文件. 本书由教学一线的教授亲自主笔, 根据作者多年的教学实践经验, 针对算法与数据结构这门课程的特点撰写而成, 目的是培养学生合理组织数据和进行优秀的算法设计的能力. 本书尽量合理地安排内容顺序, 教师可以根据需要自由地重新组织内容. 本教材可作为高等院校计算机科学与技术专业的教材. 参考书和考研辅导, 同时也可供计算机工程技术人员参考. 对于计算机科学与技术专业, 可讲授64学时, 对于其他专业, 去掉带星号的章节, 可讲授48学时. 本书的第1. 2. 3章由周世平同志编写, 第4. 10章由胡潇琨同志编写, 第5. 9章由孟佳娜同志编写, 第6. 8. 11章由谭征同志编写, 第7章由范策同志编写. 全书由范策同志统稿, 陈守孔同志编写了各章最后一节的算法设计并审阅了全书, 孟佳娜同志编写了本书的电子教案. 由于作者水平所限, 加上计算机科学技术的发展十分迅速, 书中难免有不妥和挂一漏万之处, 恳请广大读者赐教. 编 者 2004年4月于烟台大学