数据结构简明教程（第3版·微课视频版）

为便于教学，本书提供丰富的配套资源，包括教学大纲、教学课件、电子教案、程序源码、上机实训、在线作业、习题答案和25小时的微课视频。本书特色：
 （1）对算法设计中用到的C/C 语言难点予以充分讲述，实现从C/C 语言程序设计到数据结构算法设计的无缝对接。
 （2）通过通俗易懂的示例简单明了地讲解数据结构解决问题的一般性思路。
 （3）采用大量图示描述算法设计的思路。
 （4）注重算法设计的简洁和易懂特性。
 （5）力求归纳数据结构算法设计的通用性方法。
 （6）提供练验题119道，便于读者练习和实训。


 

本书讨论了包括线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树及图在内的各种数据结构的基本概念、逻辑结构与存储结构，以及在这些结构的基础上所实施的相关运算。全书共9章，每章配有丰富的练习题和上机实验题。本书具有概念清楚、表述明晰、示例丰富、图示准确和内容完整的特点，尤其注重知识点之间结构关系的展示和通用算法设计方法的提炼。

本书可作为高等院校计算机及相关专业“数据结构”课程的教材，也适合计算机爱好者和参加各类计算机考试人员研习。

第1章概论/

1.1数据结构概述/

1.1.1什么是数据结构/

1.1.2逻辑结构/

1.1.3存储结构/

1.1.4数据运算/

1.1.5数据结构、数据类型和抽象数据类型/

1.2算法和算法分析/

1.2.1算法及其描述/

1.2.2算法分析/

1.3数据结构程序设计/

1.3.1数据结构程序设计步骤/

1.3.2应用程序的结构/

小结/

练习题/

上机实验题/

第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.3.4循环单链表/

2.3.5循环单链表的算法设计示例/

2.4双链表和循环双链表/

2.4.1双链表的定义/

2.4.2线性表基本运算在双链表上的实现/

2.4.3双链表的算法设计示例/

2.4.4循环双链表/

2.4.5循环双链表的算法设计示例/

2.5线性表的应用/

2.5.1设计线性表应用程序的一般步骤/

2.5.2线性表应用示例/

小结/

练习题/

上机实验题/

第3章栈和队列/

3.1栈/

3.1.1栈的基本概念/

3.1.2栈的顺序存储结构/

3.1.3栈的链式存储结构/

3.1.4栈的应用示例/

3.2队列/

3.2.1队列的基本概念/

3.2.2队列的顺序存储结构/

3.2.3队列的链式存储结构/

3.2.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.1链串的定义/

4.3.2串基本运算在链串上的实现/

4.3.3链串的算法设计示例/

4.4串的应用/

小结/

练习题/

上机实验题/

第5章数组和稀疏矩阵/

5.1数组/

5.1.1数组的定义/

5.1.2数组的存储结构/

5.1.3数组的算法设计示例/

5.2特殊矩阵的压缩存储/

5.3稀疏矩阵/

5.3.1稀疏矩阵的三元组表示/

5.3.2稀疏矩阵的十字链表表示/

小结/

练习题/

上机实验题/

第6章树和二叉树/

6.1树/

6.1.1树的定义/

6.1.2树的逻辑结构表示/

6.1.3树的基本术语/

6.1.4树的性质/

6.1.5树的基本运算/

6.1.6树的存储结构/

6.2二叉树/

6.2.1二叉树的定义/

6.2.2二叉树的性质/

6.2.3二叉树的存储结构/

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.6二叉树的构造/

6.6.1什么是二叉树的构造/

6.6.2二叉树的构造方法/

6.7二叉树与树之间的转换/

6.7.1森林/树转换成二叉树/

6.7.2二叉树还原为树/森林/

6.8线索二叉树/

6.8.1什么是线索/

6.8.2线索二叉树的存储结构/

6.8.3线索二叉树的建立及销毁/

6.8.4线索二叉树的基本运算算法/

6.9哈夫曼树/

6.9.1哈夫曼树的定义/

6.9.2构造哈夫曼树/

6.9.3哈夫曼编码/

小结/

练习题/

上机实验题/

第7章图/

7.1图的基本概念/

7.1.1图的定义/

7.1.2图的基本术语/

7.1.3图的基本操作/

7.2图的存储结构/

7.2.1邻接矩阵/

7.2.2邻接表/

7.3图的遍历/

7.3.1深度优先遍历算法/

7.3.2广度优先遍历算法/

7.3.3图遍历算法的应用/

7.4生成树和最小生成树/

7.4.1什么是图的生成树和最小生成树/

7.4.2Prim算法/

7.4.3Kruskal算法/

7.5最短路径/

7.5.1单源最短路径算法/

7.5.2多源最短路径算法/

7.6拓扑排序/

7.7AOE网与关键路径/

小结/

练习题/

上机实验题/

第8章查找/

8.1查找的概念/

8.2静态查找表/

8.2.1顺序查找/

8.2.2折半查找/

8.2.3索引查找/

8.3动态查找表/

8.3.1二叉排序树/

8.3.2二叉平衡树/

8.3.3B树/

8.3.4B 树/

8.4哈希表/

8.4.1哈希表的基本概念/

8.4.2哈希函数构造方法/

8.4.3哈希冲突解决方法/

8.4.4哈希表查找及性能分析/

小结/

练习题/

上机实验题/

第9章排序/

9.1排序的基本概念/

9.2插入排序/

9.2.1直接插入排序/

9.2.2折半插入排序/

9.2.3希尔排序/

9.3交换排序/

9.3.1冒泡排序/

9.3.2快速排序/

9.4选择排序/

9.4.1简单选择排序/

9.4.2堆排序/

9.5归并排序/

9.6基数排序/

9.7外排序/

9.7.1磁盘排序过程/

9.7.2生成初始归并段/

9.7.3多路平衡归并/

9.7.4最佳归并树/

小结/

练习题/

上机实验题/

附录/

附录A书中部分算法清单/

附录B计算机专业考研联考数据结构部分大纲(2024年)/

参考文献/

 

党的二十大报告指出： 教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，开辟发展新领域新赛道，不断塑造发展新动能新优势。高等教育与经济社会发展紧密相连，对促进就业创业、助力经济社会发展、增进人民福祉具有重要意义。

用计算机求解实际问题时，必然涉及数据组织及数据处理，这些正是“数据结构”课程的主要学习内容。“数据结构”课程在计算机科学中是一门综合性的专业基础课。在计算机科学中，数据结构内容不仅作为一般程序设计的知识，而且是设计编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。

“数据结构”课程主要的学习内容有：数据的逻辑结构描述，即表示求解问题中的数据和数据元素之间的逻辑关系；数据的存储结构设计，即将数据逻辑结构在计算机内存中表示出来；运算算法设计，即实现求解问题的功能，如设计插入、删除、修改、查询和排序算法等。

很多学习“数据结构”课程的学生都感觉数据结构比较抽象，算法理解比较困难，这很大程度上是由于没有领会数据结构的特点。首先，一个学习计算机专业的学生必须具有某种计算机语言编程能力，能够将求解问题的思路转换成计算机可以执行的程序代码，会编写基本的程序就像小学生识字和掌握基本的词汇一样重要；其次，必须掌握用计算机求解问题的三个层次，即提取求解问题中数据的逻辑结构、设计相应的存储结构和在存储结构上实现求解问题的算法。在设计一个算法时，先要充分理解相关的存储结构，试想一下，一个图的邻接表存储结构还没有弄清楚，如何设计一个图的遍历算法呢？所以在写算法时脑海里要准确地呈现数据的存储结构，这样才会下笔有“神”，流畅地写出正确的代码，如同小学生在掌握相当多的词汇量和写作技巧后才会写出高质量的作文。

本书是作者针对数据结构课程的特点，在总结自己长期教学经验的基础上编写的。本书的“简明”性主要体现在以下两方面。

一是内容上的简明性。本书的内容基本涵盖了全国计算机专业联考大纲（2024年）数据结构部分的知识点，讲授上省去了一些难度较大的应用和扩展内容，如表达式求值和迷宫问题、串的KMP算法和广义表等。

二是写作上的简明性。作者在写作时遵循由浅入深、化繁为简的风格，主要体现为知识点、知识结构和算法表述简明清晰。

全书分为9章，第1章为概论，介绍数据结构的基本概念，特别强调了基本算法设计和分析的方法；第2章为线性表，介绍线性表的概念、两种存储结构即顺序表和链表、线性表基本运算的实现算法以及线性表的应用；第3章为栈和队列，介绍这两种特殊线性表的概念、存储结构和相关应用；第4章为串，介绍串的概念、串的两种存储结构和应用；第5章为数组和稀疏矩阵，介绍数组的概念、几种特殊矩阵的压缩方法、稀疏矩阵的定义和压缩存储结构；第6章为树和二叉树，介绍树的概念和性质、二叉树的概念、二叉树的两种主要存储结构、二叉树各种运算算法设计、哈夫曼树和哈夫曼编码，特别突出了二叉树递归算法设计方法；第7章为图，介绍图的概念、图的两种主要的存储结构、图遍历算法以及图的各类应用；第8章为查找，介绍各种查找算法的实现过程；第9章为排序，介绍各种主要的内排序算法设计方法和基本的外排序过程。附录A给出了书中部分算法清单，附录B给出了全国硕士研究生入学统一考试计算机科学与技术学科联考(简称计算机专业考研联考)数据结构部分大纲(2024年)。

本书的主要特色如下。

 力求实现从C/C 语言程序设计到数据结构算法设计的无缝对接，对算法设计中用到的一些C/C 语言难点如指针、引用类型等，结合算法设计的特点予以充分的讲述。算法描述中除了引用类型属于C ，其他均采用C语言的基本语法。

 通过通俗易懂的示例简单明了地讲解数据结构解决问题的一般性思路，如一些综合性示例统一从问题描述、设计存储结构、设计基本运算算法、设计主程序和程序运行结果几方面来讲解，突出数据结构求解问题的三个层次。

 采用大量图示直观地展现算法设计的思路，如求最小生成树的Prim算法、求图中最短路径的Dijkstra算法和各种内排序算法等。精心设计的图示不仅能够正确地表示算法的实现细节，而且更便于理解算法的精髓。

 注重算法实现的简洁性和易懂性，数据结构中许多算法都对应有多种实现方式，本书中尽可能采用简单的实现方式，如二叉排序树查找、删除等均采用非递归算法来实现。

 致力于归纳数据结构算法设计的通用性方法，如单链表、递归、二叉树和图等算法设计，都相应地总结出通用求解的方法，读者只要灵活运用这些通用方法，便可以举一反三，自己设计出求解较复杂问题的算法。

 书中提供各类练习题401道，各类上机实验题119道，便于读者练习和实训。

 书中所有算法都用C/C 语言编写并在Dev C 5.1中调试通过。对于学习计算机专业的学生，直接阅读程序代码比看“伪码”更简明。

 本书配套有《数据结构简明教程（第3版）学习与上机实验指导》（李春葆等，清华大学出版社，2024），涵盖所有练习题和上机实验题的参考答案。

为便于教学，本书提供丰富的配套资源，包括教学大纲、教学课件、电子教案、上机实训、程序源码和在线作业。此外，本书配套有全部知识点的教学视频，视频采用微课碎片化形式组织（含142个小视频，累计25小时）。

资源下载提示

课件等资源： 扫描封底的“课件下载”二维码，在公众号“书圈”下载。

素材（源码）等资源： 扫描目录上方的二维码下载。

在线自测题： 扫描封底的作业系统二维码，再扫描自测题二维码，可以在线做题及查看答案。

微课视频： 扫描封底的文泉云盘防盗码，再扫描书中相应章节的视频讲解二维码，可以在线学习。

 

本书可作为高等院校计算机及相关专业“数据结构”课程的教材，也适合计算机爱好者和参加各类计算机考试的人员参考。

本书的编写得到了湖北省教改项目“计算机科学与技术专业课程体系改革”的资助，清华大学出版社给予了大力支持，许多授课教师和同学提出建设性意见，编者在此一并表示衷心感谢。

由于水平所限，尽管编者不遗余力，书中仍可能存在疏漏和不足之处，欢迎读者批评指正。

 

编者2024年6月