数据结构：C语言描述

　　《数据结构：c语言描述》是根据2007年教育部颁发的《高等学校计算机科学与技术专业公共核心知识体系与课程》规范和2010年修订的《全国硕士研究生入学统一考试计算机专业基础综合考试大纲》编写的数据结构课程教材。全书共分7章：第1章介绍数据结构的地位和主要知识点，数据结构和算法的基本概念，算法分析的简单方法，以及用c语言编程的要点；第2～7章对应考试大纲的6个知识单元，包括线性表，栈、队列和数组，树与二叉树，图，查找，排序。本书融入了作者三十多年的教学经验和考试辅导体会，合理安排相关知识点，对学生容易忽略的地方和隐含在所讨论问题之后的内容给出适当的提示。《数据结构：c语言描述》既可作为普通高校计算机科学与技术及相关专业本科生学习数据结构课程的教材，也可作为计算机专业考研的辅导教材或其他专业计算机考试的复习教材，还可作为计算机系统开发人员的学习资料。

　　殷人昆　清华大学计算机系教授，中国科学院研究生院工程教育部兼职教授。1985年赴日本东京理科大学做访问学者，研究方向为软件工程过程的质量管理和软件产品的质量评价。主要负责清华大学计算机系“数据结构”、“软件工程”的本科课程教学工作和“软件工程技术与设计”、“软件项目管理”的研究生课程教学工作。主讲的“数据结构”课程被评为清华大学精品课程。曾与人合作或单独编写教材十余本。曾在核心刊物和专业会议发表论文多篇。

出版者的话
编委会
丛书序言
前言
教学安排建议
第1章 绪论
1.1 数据结构的概念及分类
1.1.1 为什么要学习数据结构
1.1.2 与数据结构相关的基本术语
1.1.3 数据结构的分类
1.1.4 数据结构的存储结构
1.1.5 定义在数据结构上的操作
1.2 使用c语言描述数据结构
1.2.1 数据类型
1.2.2 算法的控制结构
1.2.3 算法的函数结构
1.2.4 动态存储分配
1.2.5 逻辑和关系运算的约定
1.2.6 输入与输出
1.3 算法和算法设计
1.3.1 算法的定义和特性
1.3.2 算法的设计步骤
1.3.3 算法设计的基本方法
1.4 算法分析与度量
1.4.1 算法的评价标准
1.4.2 算法的时间和空间复杂度度量
1.4.3 算法的渐近分析
小结
习题
第2章 线性表
2.1 线性表的定义及操作
2.1.1 线性表的定义和特点
2.1.2 线性表的主要操作
2.2 顺序表
2.2.1 顺序表的定义和特点
2.2.2 顺序表的结构定义
2.2.3 顺序表主要操作的实现
2.2.4 顺序表主要操作的性能分析
2.2.5 顺序表的应用举例
2.3 单链表
2.3.1 单链表的定义和特点
2.3.2 单链表的结构定义
2.3.3 单链表中的插入与删除
2.3.4 带头结点的单链表
2.3.5 单链表主要操作的性能分析
2.3.6 单链表的顺序访问与尾递归
2.3.7 单链表的应用举例
2.4 顺序表与线性链表的比较
2.5 线性链表的其他变形
2.5.1 循环链表
2.5.2 双向链表
2.5.3 静态链表
2.6 线性表的应用：字符串
2.6.1 字符串的概念
2.6.2 字符串的初始化和赋值
2.6.3 c语言中有关字符串的库函数
2.6.4 自定义字符串的存储表示
2.7 单链表的应用：一元多项式及其运算
2.7.1 一元多项式的表示
2.7.2 多项式的结构定义
2.7.3 多项式的加法
2.7.4 多项式的乘法
小结
习题
第3章 栈、队列和数组
3.1 栈
3.1.1 栈的概念
3.1.2 顺序栈
3.1.3 链式栈
3.1.4 栈的混洗
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 队列的应用
3.4.1 打印杨辉三角形与逐行处理
3.4.2 电路布线与两点间的最短路径
3.5 数组
3.5.1 一维数组
3.5.2 多维数组
3.5.3 数组的应用举例
3.6 在算法设计中使用递归
3.6.1 汉诺塔问题与分治法
3.6.2 迷宫问题与回溯法
3.6.3 计算组合数与动态规划
3.7 特殊矩阵
3.7.1 对称矩阵的压缩存储
3.7.2 三对角线矩阵的压缩存储
3.7.3 稀疏矩阵的压缩存储
3.8 双端队列
3.8.1 双端队列的概念
3.8.2 双端队列的主要操作
3.8.3 双端队列的顺序存储表示
3.8.4 双端队列的链接存储表示
小结
习题
第4章 树与二叉树
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.4.5 二叉树的计数
4.5 线索二叉树
4.5.1 线索二叉树的概念
4.5.2 线索二叉树的种类
4.5.3 中序线索二叉树的建立和遍历
4.5.4 前序与后序线索二叉树
4.6 树与森林
4.6.1 树的存储表示
4.6.2 森林与二叉树的转换
4.6.3 树与森林的深度优先遍历
4.6.4 树与森林的广度优先遍历
4.6.5 树遍历算法的应用举例
4.7 二叉树的应用：二叉排序树
4.7.1 二叉排序树的概念
4.7.2 二叉排序树的查找
4.7.3 二叉排序树的插入
4.7.4 二叉排序树的删除
4.7.5 二叉排序树的性能分析
4.8 二叉树的应用：平衡二叉树
4.8.1 平衡二叉树的概念
4.8.2 平衡化旋转
4.8.3 平衡二叉树的插入
4.8.4 平衡二叉树的删除
4.8.5 平衡二叉树的性能分析
4.9 二叉树的应用：huffman树
4.9.1 带权路径长度的概念
4.9.2 huffman树与huffman算法
4.9.3 huffman树的应用：最优判定树
4.9.4 huffman树的应用：huffman编码
4.10 二叉树的应用：堆
4.10.1 小根堆和大根堆
4.10.2 堆的建立
4.10.3 堆的插入
4.10.4 堆的删除
4.11 树的应用：八皇后问题与树的剪枝
4.11.1 八皇后问题的提出
4.11.2 八皇后问题的状态树
4.11.3 八皇后问题算法
小结
习题
第5章 图
5.1 图的基本概念
5.1.1 与图有关的概念
5.1.2 图的基本操作
5.2 图的存储结构
5.2.1 图的邻接矩阵表示
5.2.2 图的邻接表表示
5.2.3 邻接矩阵表示与邻接表表示的比较
5.2.4 图的邻接多重表表示
5.3 图的遍历
5.3.1 深度优先搜索
5.3.2 广度优先搜索
5.3.3 连通分量
5.3.4 重连通图
5.3.5 欧拉回路与一笔画问题
5.3.6 有向图的强连通分量
5.4 最小生成树
5.4.1 最小生成树求解和贪婪法
5.4.2 kruskal算法
5.4.3 prim算法
5.5 最短路径
5.5.1 非负权重的单源最短路径
5.5.2 所有顶点之间的最短路径
5.5.3 无权重的最短路径
5.6 用顶点表示活动的网络（aov网络）
5.7 用边表示活动的网络（aoe网络）
小结
习题
第6章 查找
6.1 查找的基本概念与性能分析
6.1.1 查找的概念
6.1.2 查找算法的性能分析
6.2 顺序查找法
6.2.1 顺序表上的顺序查找算法
6.2.2 线性链表上的顺序查找算法
6.3 折半查找法
6.3.1 一般的折半查找法
6.3.2 拟最优查找树：折半查找的改进方法
6.3.3 斐波那契查找：折半查找的变形
6.3.4 插值查找：折半查找的变形
6.4 b树
6.4.1 索引顺序表与分块查找
6.4.2 多级索引结构与m叉查找树
6.4.3 b树的概念
6.4.4 b树上的查找
6.4.5 b树上的插入
6.4.6 b树上的删除
6.4.7 b+树
6.5 散列表及其查找
6.5.1 散列的概念
6.5.2 常见的散列函数
6.5.3 解决冲突的开地址法
6.5.4 解决冲突的链地址法
6.5.5 散列法分析
小结
习题
第7章 排序
7.1 排序的概念与算法性能
7.1.1 排序的概念
7.1.2 排序算法的性能
7.1.3 数据表和静态链表的结构定义
7.2 几种简单的排序方法
7.2.1 直接插入排序
7.2.2 基于链表的直接插入排序
7.2.3 折半插入排序
7.2.4 起泡排序
7.2.5 简单选择排序
7.3 希尔排序
7.3.1 希尔排序的设计思路
7.3.2 希尔排序的算法实现
7.4 快速排序
7.4.1 快速排序的设计思路
7.4.2 快速排序的算法描述
7.4.3 快速排序的算法分析
7.4.4 快速排序的改进算法
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 msd基数排序
7.7.3 lsd基数排序
7.8 内排序算法的分析与比较
7.8.1 排序方法的下界
7.8.2 各种内排序方法的比较
7.8.3 链表排序结果的重排
小结
习题
附录一 2009～2011年全国考研计算机学科联考专业基础综合考试数据结构部分试题解析
附录二 大作业要求及样例
参考文献