数据结构

信息技术的迅速发展，为计算机的应用提供了更为广阔的空间。计算机的应用领域不再局限于科学计算，还广泛应用于控制、管理和数据处理等非数值计算的处理工作。

与之相应地，计算机加工处理的对象也由纯粹的数值发展到字符、图、表、超文本等一些具有结构的数据对象，因此非常有必要去研究这些带有结构的数据对象及其相关的算法。

为了以较少的成本、较快的速度、较好的质量开发出适合多种应用需求的软件，开发人员必须遵循软件工程的原则，设计出高效率的程序。一个高效率的程序不仅需要“编程小技巧”，更需要合理的数据组织和清晰、高效的算法。这正是计算机科学领域“数据结构设计”所研究的主要内容。

计算机科学是一种创造性的思维活动，其教育必须面向设计，数据结构正是一门面向设计且处于计算机学科核心地位的课程。通过对数据结构知识的系统学习与研究，读者可以理解和掌握数据结构与算法设计的主要方法，从而为独立完成软件设计和分析奠定坚实的理论基础，这对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者是必不可少的。

数据结构课程的目的是介绍各种常用的数据结构，阐明各种数据结构之间的内在逻辑关系，讨论它们在计算机中的存储和表示，以及对这些数据进行的操作和实际算法。数据结构课程不仅为读者学习后续软件课程提供必要的基础知识，而且可以进一步地提高读者的软件设计和编程水平，同时通过对不同存储结构和相应算法的分析比较，增强读者根据实际问题选择合适的数据结构并掌握求解算法的时间、空间复杂性的能力。

为了适应我国培养各类计算机人才的需要，本课程结合我国高等学校教育工作的现状，追踪国际计算机科学技术的发展水平，更新了教学内容和教学方法，以基本数据结构为知识单元，系统地介绍了数据结构知识与应用，以期提高学生的应用能力。本书共9章，主要内容包括数据结构的基本概念、算法的描述及复杂度分析、线性表、栈和队列、串和数组、树和二叉树、图、查找、排序等。

本书力求通俗易懂，严谨流畅，内容充实，实例丰富，符号、图像规范，既适合于教学又便于自学。本书注重算法的完整性，在给出算法之前，对其实现的基本思想和要点都做了详细的讨论，算法除了有对应的C/C 程序外，有的还给出了机器运行的结果，便于读者深入的理解和掌握。

本书对算法的描述采用多种方式，书中采用接近自然语言的伪语言和C语言两种方式来同时描述算法，另外，主要章节还给出了数据结构的ADT和C 的类描述。

本书可作为普通高等院校计算机专业“数据结构”课程的教材，也可作为信息技术与管理等专业的教材和教学参考书，同时也可供从事计算机软件开发和计算机应用相关的工程技术人员参考。

由于编者的知识和写作水平有限，书中难免有不足之处。热忱欢迎同行专家和读者的批评、指正，以使本书不断地改进，日臻完善。

编者

2021年1月

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

朱智林，男，博士，教授，山东工商学院信号与信息处理学科带头人，山东省精品课程《单片机原理及应用》负责人。研究方向为，嵌入式系统综合设计，软/硬件协同设计。完成国家自然基金、国防预研项目、省自然基金项目等多项，发表学术论文40余篇，获得山东省科技进步二等奖1项，山东省高等教育省级教学成果二等奖2项，三等奖1项。

第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内部排序方法比较

习题

参考文献

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