数据结构

"本教材涵盖教学大纲内容，兼顾学科知识的广度和深度，适用面较广。 引入抽象数据类型的基本概念，有助于培养学生的数据抽象和算法设计能力。 《数据结构》概念表述严谨，逻辑推理严密，语言精炼，用词达意，既便于教学，又便于自学。"

本书在选材与编排上，贴近当前普通高等院校“数据结构”课程的现状和发展趋势，符合研究生考试大纲，内容难度适中，突出实用性和应用性。全书共9章，内容包括绪论、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序。 本书可作为普通高等院校计算机和信息技术相关专业“数据结构”课程的教材，也可供从事计算机工程与应用工作的科技工作者参考。 本书封面贴有清华大学出版社防伪标签，无标签者不得销售。

第1章绪论

1.1数据结构的概念

1.2数据结构的组成与分类

1.2.1数据的逻辑结构

1.2.2数据的物理结构

1.2.3数据的运算(集合)

1.3数据类型与抽象数据类型

1.3.1数据类型

1.3.2抽象数据类型

1.4算法和算法分析

1.4.1算法描述

1.4.2算法分析

习题

第2章线性表

2.1线性表的逻辑结构

2.1.1线性表的定义

2.1.2线性表的抽象数据类型

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.4应用实例

2.4.1一元多项式的表示与加法实现

2.4.2集合运算

习题

第3章栈和队列

3.1栈

3.1.1栈的定义和操作

3.1.2栈的顺序存储

3.1.3栈的链表存储

3.2应用举例

3.3队列

3.3.1队列的定义

3.3.2队列的表示与实现

3.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.1Brute-Force算法

4.3.2KMP算法

习题

第5章数组和广义表

5.1数组

5.1.1数组定义

5.1.2数组的存储结构

5.1.3特殊矩阵的压缩存储

5.2广义表

5.2.1广义表抽象数据类型

5.2.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.4.3线索二叉树遍历

6.5哈夫曼树及其应用

6.5.1基本概念

6.5.2哈夫曼算法

6.5.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.4最小生成树

7.4.1普里姆算法

7.4.2克鲁斯卡尔算法

7.5最短路径

7.5.1单源最短路径

7.5.2所有顶点对之间的最短路径

习题

第8章查找

8.1查找的基本概念

8.1.1查找

8.1.2查找表

8.1.3平均查找长度ASL

8.2线性表的查找

8.2.1顺序查找

8.2.2折半查找

8.2.3分块查找

8.3散列表的查找

8.3.1散列表的基本概念

8.3.2散列函数

8.3.3冲突的解决

8.3.4散列表查找及其分析

习题

第9章排序

9.1基本概念

9.1.1排序的概念

9.1.2排序算法的稳定性

9.1.3内排序与外排序

9.2插入排序

9.2.1直接插入排序

9.2.2希尔排序

9.3交换排序

9.3.1冒泡排序

9.3.2快速排序

9.4选择排序

9.4.1简单选择排序

9.4.2堆排序

9.5基数排序

9.6外排序

9.6.1路平衡归并

9.6.2k-路平衡归并与败者树

9.6.3很好归并树

9.7内部排序方法比较

习题

参考文献