数据结构与算法详解电子书

版 权

内容提要

前 言

服务与支持

第一部分 数据结构

第0章 基础知识

0.1 基本概念和术语

0.2 数据的逻辑结构与存储结构

0.2.1 逻辑结构

0.2.2 存储结构

0.3 抽象数据类型及其描述

0.3.1 什么是抽象数据类型

0.3.2 抽象数据类型的描述

0.4 算法

0.4.1 数据结构与算法的关系

0.4.2 什么是算法

0.4.3 算法的五大特性

0.4.4 算法的描述

0.5 算法分析

0.5.1 算法设计的4个目标

0.5.2 算法的时间复杂度

0.5.3 算法的空间复杂度

第1章 线性表

1.1 顺序表及其应用

1.1.1 将两个有序的线性表合并为一个有序的线性表

1.1.2 将两个无序的线性表合并为一个线性表

1.1.3 求两个线性表的差集

1.1.4 分解顺序表，使左边的元素小于或等于0，右边的大于0

1.1.5 求两个任意长度的整数之和

1.1.6 求两个元素序列的中位数

1.2 单链表及其应用

1.2.1 逆置单链表

1.2.2 求两个单链表的差集

1.2.3 合并两个单链表

1.2.4 找出单链表表示的两个单词共同后缀起始地址

1.2.5 找出单链表中倒数第k个位置上的节点

1.3 循环单链表及其应用

1.3.1 分解一个循环单链表为两个循环单链表

1.3.2 构造3个循环单链表

1.3.3 约瑟夫问题

1.4 双向链表及其应用

1.4.1 双向链表的创建与插入操作

1.4.2 约瑟夫问题（双向链表）

1.5 线性表的典型应用

1.5.1 将两个一元多项式相加

1.5.2 将两个一元多项式相乘

第2章 栈

2.1 顺序栈及其应用

2.1.1 将元素分别入栈和出栈

2.1.2 共享栈的入栈和出栈操作

2.1.3 求C (n,m)的值

2.1.4 求Ackermann(m,n)的值

2.2 链栈及其应用

2.2.1 将十进制数转换为八进制数

2.2.2 检查表达式中的括号是否匹配

2.2.3 求算术表达式的值

2.2.4 判断字符串是否中心对称

第3章 队列

3.1 顺序队列及其应用

3.1.1 将顺序循环队列中的元素分别入队和出队

3.1.2 舞伴配对

3.1.3 模拟轮渡管理

3.2 链式队列及其应用

3.2.1 队列在杨辉三角中的应用

3.2.2 判断字符串是否为回文

3.3 栈和队列的综合应用──停车场管理

第4章 串

4.1 顺序串及其应用

4.1.1 利用串的基本运算进行赋值、插入和删除等操作

4.1.2 将浮点数转换为对应的串

4.1.3 求最长公共子串

4.1.4 求等值子串

4.1.5 将长度为5的单词转换为大写形式

4.1.6 将小写字母a左、右两边的串互换

4.2 串的模式匹配

模式匹配

第5章 数组

5.1 一维数组及其应用

5.1.1 查找第k小元素

5.1.2 将奇数移动到偶数的左边

5.2 二维数组（矩阵）及其应用

5.2.1 输出魔方阵

5.2.2 输出内螺旋矩阵

5.2.3 输出逆螺旋矩阵

5.2.4 输出外螺旋矩阵

5.2.5 输出蛇形方阵

5.2.6 输出折叠方阵

5.3 特殊矩阵的压缩存储及其应用

上三角矩阵的压缩存储

5.4 稀疏矩阵的压缩存储及其应用

稀疏矩阵的相加

第6章 广义表

6.1 头尾链表表示的广义表及其应用

创建广义表并求其长度和深度

6.2 扩展线性链表表示的广义表及其应用

创建广义表并求其长度和深度

6.3 广义表的综合应用——导师-学生制管理

第7章 树

7.1 树的表示及创建二叉树

7.1.1 采用广义表创建二叉树

7.1.2 创建二叉树

7.2 二叉树的遍历

7.2.1 非递归先序遍历二叉树

7.2.2 按层次遍历二叉树

7.2.3 由中序和后序序列构造二叉树

7.2.4 输出树的各条边

7.3 二叉树的应用

7.3.1 求树中节点的个数

7.3.2 交换二叉树的左右子树

7.3.3 判断二叉树是否为完全二叉树

7.3.4 计算二叉树的高度和最大宽度

7.3.5 求树中根节点到任意节点之间的路径

7.4 哈夫曼树

创建哈夫曼树并输出哈夫曼编码

第8章 图

8.1 图的表示及应用

8.1.1 利用邻接矩阵创建有向网

8.1.2 利用邻接表创建有向图

8.1.3 把图的邻接矩阵表示转换为邻接表表示

8.2 图的遍历

8.2.1 判断有向图中是否存在回路

8.2.2 深度优先搜索遍历无向图

8.2.3 图的广度优先搜索遍历

8.2.4 判断有向图中是否有根顶点

8.2.5 求距离顶点v0的最短路径长度为k的所有顶点

8.2.6 判断顶点u和顶点v之间是否存在简单路径

8.2.7 判断无向图是否为一棵树

第二部分 算法

第9章 查找算法

9.1 与查找算法相关的概念

9.2 基于线性表的查找

9.2.1 顺序查找

9.2.2 折半查找

9.2.3 分块查找

9.3 基于树的查找

二叉排序树的创建和插入操作

9.4 哈希表的查找

哈希表的构造与元素的查找

第10章 排序算法

10.1 排序的基本概念

10.2 插入排序

10.2.1 直接插入排序

10.2.2 折半插入排序

10.2.3 希尔排序

10.3 交换排序

10.3.1 冒泡排序

10.3.2 快速排序

10.4 选择排序

10.4.1 简单选择排序

10.4.2 堆排序

10.5 归并排序

二路归并排序

10.6 基数排序

基数排序

第11章 递推算法

11.1 顺推法

11.1.1 斐波那契数列

11.1.2 角谷猜想

11.1.3 将十进制整数转换为二进制整数

11.1.4 将十进制浮点数转换为二进制数

11.1.5 母牛生小牛问题

11.1.6 输出杨辉三角

11.1.7 质因数分解

11.1.8 求最大公约数和最小公倍数

11.2 逆推法

11.2.1 猴子摘桃

11.2.2 存钱问题

第12章 递归算法

12.1 简单递归

12.1.1 求n的阶乘

12.1.2 斐波那契数列

12.1.3 求n个元素中的最大者

12.1.4 求n个数的和

12.1.5 将十进制整数转换为二进制整数

12.1.6 求整数的逆序数

12.1.7 求最大公约数

12.1.8 求Ackermann函数的值

12.1.9 求C (n,m)的值

12.2 复杂递归

12.2.1 逆置字符串

12.2.2 求最大和次大元素

12.2.3 求无序序列中第k大的元素

12.2.4 和式分解

12.2.5 台阶问题

12.2.6 汉诺塔问题

12.2.7 大牛生小牛问题

12.2.8 从自然数1～n中任选r个数的所有组合数

第13章 枚举算法

13.1 判断n是否能被3、5、7整除

13.2 百钱买百鸡

13.3 五猴分桃

13.4 输出“水仙花数”

13.5 Mary的借书方案

13.6 整币换零

13.7 填数游戏

13.8 谁在说谎

13.9 求最大连续子序列和

13.10 0/1背包问题

第14章 贪心算法

14.1 贪心算法的基础

14.1.1 贪心算法的基本思想

14.1.2 贪心选择性质

14.1.3 贪心算法的求解步骤

14.2 找零钱问题

14.3 会议安排问题

14.4 最优装载问题

14.5 哈夫曼编码

14.6 加油点问题

14.7 背包问题

第15章 回溯算法

15.1 回溯算法的基础

15.1.1 回溯算法的解空间

15.1.2 回溯算法的搜索

15.2 求自然数1～n中r个数的所有组合

15.3 填字游戏

15.4 和式分解（非递归实现）

15.5 装箱问题

15.6 0/1背包问题

第16章 数值算法

16.1 求实数的平方根

16.2 利用二分法求方程的根

16.3 利用牛顿迭代法求方程的根

16.4 利用高斯消元法求解线性方程组

16.5 利用梯形法求定积分

16.6 计算π的近似值

第17章 实用算法

17.1 阿拉伯数字/中文大写金额的转换

17.2 将15位身份证号转换为18位

17.3 计算7的34次方

17.4 计算某年某月某日是一年中的第几天

17.5 大整数相乘

17.6 输出万年历

17.7 求两个正整数的差

17.8 利用二叉树结构计算算术表达式的值

第18章 常见错误与程序调试技术

18.1 常见错误

18.1.1 错误分类

18.1.2 常见错误举例

18.2 程序调试

18.2.1 Visual C++ 6.0开发环境中程序的调试

18.2.2 程序调试应用举例

18.3 小结