数据结构实用教程

第1章 绪论

1.1 数据结构的基本概念

1.1.1 基本概念和术语

1.1.2 数据的逻辑结构

1.1.3 数据的存储结构

1.2 抽象数据类型

1.2.1 什么是抽象数据类型

1.2.2 抽象数据类型的描述

1.3 算法的定义及特征

1.3.1 算法的定义及特征

1.3.2 算法设计的要求

1.4 算法的度量及分析

1.4.1 算法效率的度量

1.4.2 时间复杂度分析

1.4.3 常见的时间复杂度

1.4.4 空间复杂度分析

习题

第2章 线性表

2.1 定义

2.1.1 什么是线性表

2.1.2 线性表的抽象数据类型

2.2 顺序线性表

2.2.1 线性表的顺序存储

2.2.2 顺序表的基本操作

2.2.3 综合应用实例--扑克牌游戏

2.3 链式线性表一

2.3.1 线性表的链式存储

2.3.2 单链表的基本操作

2.3.3 综合应用实例--学生信息管理系统

2.4 链式线性表二

2.4.1 循环链表

2.4.2 双向链表

2.4.3 综合应用实例--约瑟夫问题

2.5 顺序表与链表的比较

习题

第3章 栈和队列

3.1 栈

3.1.1 定义

3.1.2 栈的抽象数据类型

3.2 顺序栈

3.2.1 顺序栈的存储结构

3.2.2 顺序栈的基本操作

3.2.3 综合应用实例--表达式求值

3.3 链栈

3.3.1 链栈的存储结构

3.3.2 链栈的基本操作

3.3.3 综合应用实例--老鼠钻迷宫

3.4 队列

3.4.1 定义

3.4.2 队列的抽象数据类型

3.5 顺序队列

3.5.1 顺序队列的存储结构

3.5.2 循环队列的逻辑结构

3.5.3 循环队列的基本操作

3.5.4 综合应用实例--打印文档

3.6 链队列

3.6.1 链队列的存储结构

3.6.2 链队列的基本操作

3.6.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.2 堆存储的基本操作

4.4 串的链式存储

4.4.1 串的链式存储结构

4.4.2 链式存储的基本操作

4.5 串的模式匹配

4.5.1 Brute-Force算法

4.5.2 KMP算法

4.5.3 综合应用实例--简易的“记事本”

习题

第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 广义表的抽象数据类型

5.4.3 广义表的存储结构

5.4.4 广义表的基本操作

5.4.5 综合应用实例--文件目录结构

习题

第6章 树及二叉树

6.1 树及其表示

6.1.1 树的定义和术语

6.1.2 树的逻辑表示

6.1.3 树的抽象数据类型

6.1.4 树的存储结构

6.2 二叉树

6.2.1 二叉树的定义

6.2.2 二叉树的性质

6.2.3 二叉树的抽象数据类型

6.2.4 二叉树的存储结构

6.2.5 二叉树的基本操作

6.2.6 二叉树的遍历

6.2.7 综合应用实例--算术表达式的计算

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.5.3 综合应用实例--电报编码

习题

第7章 图

7.1 定义

7.1.1 什么是图

7.1.2 图的常用术语

7.1.3 图的抽象数据类型

7.2 图的存储结构

7.2.1 邻接矩阵

7.2.2 邻接表

7.2.3 十字链表

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.5.3 综合应用实例--高速公路行驶最佳方案

7.6 拓扑排序和关键路径

7.6.1 拓扑排序

7.6.2 关键路径

7.6.3 综合应用实例--计算机课程学习的优先顺序

习题

第8章 排序

8.1 定义

8.1.1 什么是排序

8.1.2 排序算法的分类

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.6 基数排序

8.7 几种排序算法的比较

习题

第9章 查找

9.1 定义

9.1.1 什么是查找

9.1.2 查找的性能分析

9.2 静态查找

9.2.1 顺序表的查找

9.2.2 有序表的查找

9.2.3 索引顺序表的查找

9.3 动态查找

9.3.1 二叉排序树

9.3.2 平衡二叉树

9.3.3 B-树和B+树

9.4 哈希表

9.4.1 定义

9.4.2 哈希函数的构造方法

9.4.3 处理冲突的方法

9.4.4 哈希表的基本操作

习题

附录A 认识Visual C++ 6.0中文版开发环境

附录B 程序组织、预处理和调试

B.1 设置断点

B.2 控制程序运行

B.3 查看变量或数组的内容

B.4 退出Visual C++ 6

《高等学校计算机教材：数据结构实用教程（C语言版）》系统介绍线性表、栈和队列、串、数组和广义表、树和二叉树、图、排序、查找等内容。以C语言作为数据结构和算法的描述语言。一般先通过应用实例引入，在数据类型基本操作介绍后，通过综合应用实例进行应用和消化。所有的综合应用实例在Visual C++6.0环境下调试、运行通过。通过《高等学校计算机教材：数据结构实用教程（C语言版）》学习，不但可以比较容易理解数据结构主要内容，而且应用数据结构知识解决了若干个小应用问题，大大提高学生解决问题的能力。