数据结构与算法实用教程

第1章绪论

1.1引言

1.1.1解决问题的步骤

1.1.2一个例子

1.2数据结构

1.2.1有关概念和术语

1.2.2抽象数据类型

1.2.3描述工具类C语言

1.3算法和算法分析

1.3.1算法的定义及算法设计的要求

1.3.2算法性能分析与度量

1.3.3复杂度函数的增长率

1.3.4复杂度分析的例子

本章小结

习题1

第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算法设计实例一元多项式的表示及相加

本章小结

习题2

第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算法设计实例

3.4.1数制转换

3.4.2表达式求值算法

本章小结

习题3

第4章串

4.1串的类型定义

4.1.1串的基本概念

4.1.2串的抽象数据类型

4.2串的表示和实现

4.2.1串的顺序存储结构

4.2.2串的链式存储结构

4.3串的模式匹配

4.3.1朴素的模式匹配算法

4.3.2KMP算法

*4.4串的应用举例

本章小结

习题4

第5章数组和广义表

5.1数组的概念及其基本操作

5.1.1数组的抽象数据类型

5.1.2二维数组

5.2数组的顺序存储

5.3矩阵的压缩存储

5.3.1特殊矩阵

5.3.2稀疏矩阵

*5.4广义表

5.4.1广义表的定义

5.4.2广义表的存储结构

本章小结

习题5

第6章树与二叉树

6.1树的概念和操作

6.1.1树的定义

6.1.2树的基本术语

6.1.3树的基本操作

6.2二叉树

6.2.1二叉树的概念及操作

6.2.2二叉树的性质

6.2.3二叉树的存储结构

6.3二叉树的遍历

6.3.1二叉树的遍历

6.3.2遍历算法的应用

6.4线索二叉树

6.4.1线索二叉树的基本概念

6.4.2线索二叉树的基本操作

6.5树和森林

6.5.1树的存储结构

6.5.2森林、树、二叉树的相互转换

6.5.3树和森林的遍历

6.6哈夫曼树及其应用

6.6.1最优二叉树（哈夫曼树）

6.6.2哈夫曼编码

*6.7算法设计实例

本章小结

习题6

第7章图

7.1图的定义和术语

7.1.1图的基本概念

7.1.2图的基本操作

7.2图的存储结构

7.2.1数组表示法

7.2.2邻接表

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算法实例

本章小结

习题7

第8章查找

8.1概述

8.2线性表上的查找

8.2.1顺序表上的查找

8.2.2有序表上的二分查找

8.3索引表上的查找

8.4树表上的查找

8.4.1二叉排序树

8.4.2平衡二叉树

*8.4.3B_树

*8.4.4键树

8.5哈希表

8.5.1哈希表查找的基本概念

8.5.2构造哈希函数的方法

8.5.3哈希冲突的解决方法

8.5.4哈希表的查找及分析

*8.6算法设计实例

本章小结

习题8

第9章排序

9.1概述

9.1.1排序的定义

9.1.2排序的分类

9.1.3排序的基本操作

9.1.4排序算法的性能评价

9.1.5排序算法涉及的数据类型

9.2插入排序

9.2.1直接插入排序

9.2.2折半插入排序

9.2.3希尔排序

9.2.4其他插入排序

9.3交换排序

9.3.1冒泡排序

9.3.2快速排序

9.4选择排序

9.4.1简单选择排序

9.4.2堆排序

9.5归并排序

9.5.1归并排序

9.5.2二路归并排序

9.6分配排序

9.6.1多关键字排序

9.6.2基数排序

9.7计数排序

9.7.1计数排序

9.7.2计数排序算法实现

9.8内部排序比较与选择

9.8.1内部排序算法性能比较

9.8.2内部排序算法的选择

*9.9外部排序简介

9.9.1磁盘文件管理

9.9.2多路归并排序

9.9.3二路归并排序算法

9.9.4磁盘文件排序的例子

9.9.5提高外部排序算法效率的途径

本章小结

习题9

第10章算法设计初步

10.1迭代法与穷举法

10.1.1迭代法

10.1.2穷举法

10.2递归技术与分治法

10.2.1递归技术

10.2.2分治法

10.3回溯法

10.3.1回溯法的基本思想

10.3.20-1背包问题

10.3.3旅行商问题

10.3.4求解迷宫问题

10.4倒推法

10.4.1倒推法的基本思想

10.4.2倒推法应用实例

10.5贪心法

10.5.1贪心法的基本思想

10.5.2使用贪心法的前提

10.5.3贪心法应用实例

10.6分枝限界法

10.6.1分枝限界法的基本思想

10.6.2分枝限界法的应用实例

10.7动态规划法

10.7.1动态规划法的基本思想

10.7.2动态规划法的基本要素

10.7.3动态规划法的变形备忘录方法

10.8随机算法

10.8.1随机数的产生

10.8.2用随机算法计算p的值

10.8.3蒙特卡罗积分

本章小结

习题10

参考文献

　　本书采用通俗易懂、由浅入深和循序渐进的方式介绍了数据结构的基本知识。每当引入一种新的数据结构时，在给出其抽象数据类型(ADT)之后，其对应的存储结构及基本操作算法均以C语言形式给出，读者可以通过上机实验来理解和验证课程的具体内容和算法过程。对于各种算法的介绍，偏重于介绍和剖析算法的基本思想、主要结构和性能优劣，而较少拘泥于对算法的时空复杂性的理论分析。本书可作为高等院校计算机专业及相关专业的教材和参考书，也可供IT工程技术人员参考。　　“数据结构与算法”是计算机科学与技术专业的一门非常重要的专业基础课，是《中国计算机科学与技术学科教程2002》指定的核心课程之一。本书由长期担任本课程教学任务的教授主持编写，内容覆盖了该教程规定的关于本门课程的全部知识点，并融入了编者的教学经验和对课程内涵的深入思考。全书共分l0章，内容涉及数据结构的基本概念、线性表、栈和队列、串和数组、广义表、树、图、查找、排序及算法设计方法。