数据结构与算法

　　《数据结构与算法》是数据结构与算法设计的教材，其宗旨是将数据结构与算法设计有机地结合起来，向读者系统介绍了数据结构的基本概念及主要的算法设计方法。全书共分9章，第1章介绍了数据结构的基本概念，第3～8章分别介绍了线性表、串、栈、队列和数组、树结构和图结构以及查找和排序等数据结构的相关知识，在第2章简单介绍算法概念的基础上，第9章详细介绍了几种算法的设计方法，并给出实例具体说明设计过程。书中主要算法都用C++语言写出，并给出了详细的注解。《数据结构与算法》概念清楚，选材精练，叙述深入浅出，用了大量的例子和图表来说明基本概念和方法，直观易懂。每章后面都附有习题，读者可以通过习题复习和检验所学知识。《数据结构与算法》可以作为高等院校理工科学生的教材，也可以作为广大计算机科学与工程领域从业人员的参考书。

　　辛运帏，1965年生。1986年毕业于南开大学计算机与系统科学系，并留校任教。曾先后从师于陈有祺教授、卢桂章教授，并获得工学硕士、博士学位，现为南开大学信息技术科学学院计算机科学技术系教授。多年来主讲“数据结构”、“形式语言与自动机”、“计算方法”等课程。主要研究领域为人工智能、电子商务、加密技术等，曾承担科技部、天津市重点基金等多项科研项目，出版教材《数据结构导论》、《Java程序设计》等，发表论文十余篇。刘璟，1942年生。1981年于南开大学数学系研究生毕业。南开大学计算机科学技术系教授，博士生导师，教育部计算机科学与技术教学指导委员会委员，基础分会副主任，天津市高等学校计算机基础教学指导委员会副主任，中国计算机学会理论计算机科学分会理事，天津市学位委员会学科评议组成员。长期讲授“高级语言程序设计”、“算法设计与分析”等课程。主要研究领域为并行与分布式系统、算法设计与分析、网络存储系统、面向对象程序设计等。曾主持国家863、自然科学基金、博士点基金项目等十余项，在国内外发表论文60篇，出版教材“计算机算法引论”、“高级语言C++程序设计”等。陈有祺，1936年生。1960年毕业于北京大学数学力学系，同年在南开大学任教。1980-1982年在美国西密西根大学作访问学者，研修人工智能和形式语言，现为南开大学教授。曾任南开大学计算机与系统科学系主任，现兼任中国计算机学会理论计算机科学分会理事，全国高等学校计算机教育研究会理事，《理论计算机科学》常务编委等职。多年来从事编译理论、形式语言与自动机、人工智能和自然语言理解等领域的教学与研究工作，共发表论著二十余篇（部）。1991年被评为天津市优秀教师。

第l章 绪论
1.1 数据结构简介
1.1.1 数据结构的发展历史
1.1.2 数据结构的基本概念和术语
1.2 有关的预备知识
1.2.1 集合
1.2.2 递归
1.2.3 数学证明方法
习题
第2章 算法的基本概念与算法分析
2.1 算法的基本概念
2.1.1 一个简单的算法
2.1.2 什么是算法
2.1.3 算法与问题
2.1.4 算法与程序
2.2 算法的评估
2.2.1 算法的正确性
2.2.2 时间代价
2.2.3 空间代价
2.2.4 最优性
2.3 算法的复杂度度量
2.3.1 基本操作
2.3.2 问题实例长度
2.3.3 复杂度函数及其渐进性质
2.3.4 最坏情形和最优情形
2.3.5 平均情形和算法的期望复杂度
2.3.6 复杂度函数的表示
2.4 算法设计与分析的重要性
2.4.1 一个实例
2.4.2 计算机应用领域的变化
2.4.3 计算机技术的发展需要设计有效算法
2.5 MAXMIN问题
2.5.1 MAxMIN问题的平凡算法
2.5.2 第一次改进算法
2.5.3 第二次改进算法
2.5.4 采用分治策略的改进算法
2.5.5 算法MAxMIN的讨论
习题
第3章 线性表
3.1 线性表的定义和基本运算
3.2 线性表的实现
3.2.1 顺序存储结构
3.2.2 链式存储结构
3.2.3 两种基本实现方法的比较
3.2.4 循环链表
3.2.5 双向链表
3.3 线性表的应用
习题
第4章 栈、队列和数组
4.1 栈
4.1.1 顺序栈
4.1.2 链式栈
4.1.3 顺序栈与链式栈的比较
4.1.4 栈的应用
4.2 队列
4.2.1 队列的定义及基本运算
4.2.2 顺序队列
4.2.3 链式队列
4.2.4 队列的应用
4.3 数组
4.3.1 数组的抽象数据类型
4.3.2 数组的存储方式
4.3.3 特殊数组
4.3.4 数组的应用
习题
第5章 树形结构
5.1 树
5.1.1 树的基本概念
5.1.2 树的抽象数据类型
5.2 二叉树
5.2.1 二叉树的定义及其主要特性
5.2.2 二叉树的实现
5.2.3 二叉树的遍历
5.3 树、森林与二叉树的关系
5.3.1 树的存储结构
5.3.2 森林与二叉树的转换
5.3.3 树和森林的遍历
5.4 树形结构的应用
5.4.1 等价类问题
5.4.2 哈夫曼树和哈夫曼编码
习题
第6章 图
6.1 图的基本概念
6.1.1 图的基本概念
6.1.2 图的抽象数据类型
6.2 图的存储结构
6.2.1 邻接矩阵
6.2.2 邻接表
6.2.3 逆邻接表
6.2.4 邻接多重表
6.2.5 图的实现
6.3 图的遍历及求图的连通分量
6.3.1 深度优先搜索
6.3.2 广度优先搜索
6.3.3 无向图的连通分量
6.4 生成树和最小代价生成树
6.4.1 生成树
6.4.2 最小代价生成树
6.5 最短路径
6.5.1 从某个源点到其他各顶点的最短路径
6.5.2 每一对顶点间的最短路径
6.6 有向无环图及其应用
6.6.1 有向无环图
6.6.2 拓扑排序
6.6.3 关键路径
习题
第7章 查找
7.1 查找的基本概念
7.2 顺序表的查找
7.2.1 顺序查找
7.2.2 折半查找
7.2.3 索引顺贡序表的查找
7.3 树表的查找
7.3.1 二叉排序树
7.3.2 平衡二叉树
7.3.3 B-树
7.4 P台希表及其查找
7.4.1 什么是哈希
7.4.2 哈希函数的构造方法
7.4.3 处理冲突的几种方法
7.4.4 哈希表的查找及其效率分析
习题
第8章 内部排序
8.1 排序的一般概念
8.2 插入排序
8.2.1 直接插入排序
8.2.2 折半插入排序
8.2.3 希尔排序
8.3 交换排序
8.3.1 起泡排序
8.3.2 快速排序
8.4 选择排序
8.4.1 简单选择排序
8.4.2 堆排序
8.5 归并排序
8.5.1 两个有序序列的归并操作
8.5.2 归并排序
8.6 分配排序和基数排序
8.7 有关内部排序算法的比较
习题
第9章 算法设计技术
9.1 求解问题的基本思路
9.2 分治技术
9.2.1 分治策略的思想
9.2.2 大整数乘法
9.2.3 矩阵相乘的Strassen算法
9.2.4 选择问题的分治算法
9.3 贪心技术
9.3.1 贪心算法的思想
9.3.2 活动安排问题
9.3.3 背包问题
9.3.4 多机调度问题的近似算法
9.3.5 单源最短路径问题的Dijkstra算法
9.4 回溯与分枝限界技术
9.4.1 两个适合回溯技术的问题
9.4.2 八后问题
9.4.3 0-1背包问题的回溯算法
9.4.4 分枝限界算法
9.5 动态规划技术
9.5.1 Fibonacci数的计算
9.5.2 矩阵连乘的顺序问题
9.5.3 适合动态规划算法的两个条件
综合练习题一
综合练习题二
综合练习题三
综合练习题四
综合练习题五
综合模拟题一
综合模拟题二
参考文献