新编数据结构习题与解析（第2版）

本书内容包括概论、线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树、图、查找和排序，附录中给出书中部分算法清单、全国计算机专业数据结构联考大纲、部分练习题的参考答案

李春葆，武汉大学计算机学院教授，主要研究方向为数据挖掘和算法设计。先后主持和参加多项国家自然科学基金项目和应用开发项目。在清华大学出版社、人民邮电出版社和机械工业出版社等出版社出版教材和论著30余本。

C O N T E N T S
目录

 

 

源码下载

 

第1章绪论

1．1知识点1：  数据结构的基本概念

1．1．1要点归纳

1．1．2例题解析

1．2知识点2：  算法和算法分析

1．2．1要点归纳

1．2．2例题解析

第2章线性表

2．1知识点1：  线性表的基本概念

2．1．1要点归纳

2．1．2例题解析

2．2知识点2：  顺序表的算法

2．2．1要点归纳

2．2．2例题解析

2．3知识点3：  单链表的算法

2．3．1要点归纳

2．3．2例题解析

2．4知识点4：  双链表的算法

2．4．1要点归纳

2．4．2例题解析

2．5知识点5：  循环链表的算法

2．5．1要点归纳

2．5．2例题解析

第3章栈和递归

3.1知识点1：  栈的基本概念

3.1.1要点归纳

3.1.2例题解析

3.2知识点2：  顺序栈的算法

3.2.1要点归纳

3.2.2例题解析

3.3知识点3：  链栈的算法

3.3.1要点归纳

3.3.2例题解析

3.4知识点4：  递归

3.4.1要点归纳

3.4.2例题解析

第4章队列

4.1知识点1：  队列的基本概念

4.1.1要点归纳

4.1.2例题解析

4.2知识点2：  顺序队的算法

4.2.1要点归纳

4.2.2例题解析

4.3知识点3：  链队的算法

4.3.1要点归纳

4.3.2例题解析

第5章串

5．1知识点1：  串的基本概念

5．1．1要点归纳

5．1．2例题解析

5．2知识点2：  顺序串的算法

5．2．1要点归纳

5．2．2例题解析

5．3知识点3：  链串的算法

5．3．1要点归纳

5．3．2例题解析

5．4知识点4：  模式匹配的算法

5．4．1要点归纳

5．4．2例题解析

第6章数组和稀疏矩阵

6．1知识点1：  数组和特殊矩阵

6．1．1要点归纳

6．1．2例题解析

6．2知识点2：  稀疏矩阵

6．2．1要点归纳

6．2．2例题解析

第7章树和二叉树

7．1知识点1：  树的基本概念

7．1．1要点归纳

7．1．2例题解析

7．2知识点2：  二叉树的基本概念

7．2．1要点归纳

7．2．2例题解析

7．3知识点3：  二叉树的算法

7．3．1要点归纳

7．3．2例题解析

7．4知识点4：  线索二叉树

7．4．1要点归纳

7．4．2例题解析

7．5知识点5：  哈夫曼树

7．5．1要点归纳

7．5．2例题解析

7．6知识点6：  树算法设计

7．6．1要点归纳

7．6．2例题解析

第8章广义表

8.1知识点1：  广义表的基本概念

8.1.1要点归纳

8.1.2例题解析

8.2知识点2：  广义表的算法设计

8.2.1要点归纳

8.2.2例题解析

第9章图

9.1知识点1：  图的基本概念

9.1.1要点归纳

9.1.2例题解析

9.2知识点2：  图的遍历算法

9.2.1要点归纳

9.2.2例题解析

9.3知识点3：  小生成树

9.3.1要点归纳

9.3.2例题解析

9.4知识点4：  短路径

9.4.1要点归纳

9.4.2例题解析

9.5知识点5：  AOV网和拓扑排序

9.5.1要点归纳

9.5.2例题解析

9.6知识点6：  AOE网与关键路径

9.6.1要点归纳

9.6.2例题解析

第10章查找

10．1知识点1：  线性表的查找

10．1．1要点归纳

10．1．2例题解析

10．2知识点2：  树表的查找

10．2．1要点归纳

10．2．2例题解析

10．3知识点3：  哈希表的查找

10．3．1要点归纳

10．3．2例题解析

第11章内排序

11.1知识点1：  插入排序算法

11.1.1要点归纳

11.1.2例题解析

11.2知识点2：  选择排序算法

11.2.1要点归纳

11.2.2例题解析

11.3知识点3：  交换排序算法

11.3.1要点归纳

11.3.2例题解析

11.4知识点4：  归并排序算法

11.4.1要点归纳

11.4.2例题解析

11.5知识点5：  基数排序算法

11.5.1要点归纳

11.5.2例题解析

第12章外排序和文件

12.1知识点1：  外排序

12.1.1要点归纳

12.1.2例题解析

12.2知识点2：  文件

12.2.1要点归纳

12.2.2例题解析

附录A四份重点大学本科“数据结构”科目考试试题

试题1

试题1参考答案

试题2

试题2参考答案

试题3

试题3参考答案

试题4

试题4参考答案

附录B2012—2018年全国计算机专业硕士学位研究生入学考试数据结构
部分试题视频讲解

附录C书中视频对应二维码汇总表

F O R E W O R D
前言

 

 

 

计算机是进行数据处理的工具，数据结构课程主要讨论数据组织和处理方法，具有概念多、抽象和算法设计灵活等特点。全国联考大纲对本课程有较高的要求，不仅要求掌握数据结构的基本概念、基本原理和基本方法，还要求可以运用数据结构原理和方法进行问题的分析和求解，并具备实现算法和算法分析的能力。

要学好数据结构课程，首先要从宏观上理解本课程的目的和地位。该课程是在学完C、C 或者Java等程序设计语言相关课程后开设的，程序设计语言课程教会学生用计算机处理简单数据的方法，相当于小学阶段的识字，认识数百个汉字但不一定能写出好的作文，这是因为写作文有自身的规律和方法，同样的道理，熟悉程序设计语言却不一定能编写出“好程序”。

从数据结构角度看，编写程序的过程分为逻辑层面和实现层面。逻辑层面是理解求解问题是什么，即从求解的问题中提炼出数据逻辑结构和运算(前者指数据元素之间的相邻关系的整体，主要分为线性结构、树形结构和图形结构类型； 后者指程序功能的描述)。实现层面是将处理的数据存放到计算机内（映射），称为数据存储结构，再在存储结构之上实现对应的运算，即算法。一种数据逻辑结构可以映射成多种存储结构，不同的运算对应不同的算法，同一运算也可以有多种算法，通过算法时间和空间分析可以确定算法的好坏。数据结构课程的精髓就是设计求解问题的“好算法”。

数据结构课程总结和归纳了软件开发中常用的一些数据结构，从数据逻辑结构、存储结构和运算算法设计等各方面综合讨论这些数据结构，可以提高学生基本的数据组织和处理能力，为后续学习操作系统、数据库原理和编译原理等课程打下基础。

本书在总结作者多年的程序设计语言、数据结构和算法设计与分析课程的教学经验的基础上编写而成。全书分为12章： 第1章为绪论，讨论数据结构和算法的基本概念； 第2章为线性表，归纳了线性表的概念以及顺序表、单链表、双链表和循环链表的算法设计方法； 第3章为栈和递归，归纳了栈的概念以及顺序栈、链栈的算法设计方法，较深入地讨论了计算机学科中递归的算法设计方法； 第4章为队列，归纳了队列的概念以及顺序队、链队的算法设计方法； 第5章为串，归纳了串的概念以及顺序串、链串和模式匹配的算法设计方法； 第6章为数组和稀疏矩阵，归纳了数组、特殊矩阵和稀疏矩阵的概念与相关运算设计方法； 第7章为树和二叉树，归纳了树、二叉树、线索二叉树、哈夫曼树的概念以及二叉树算法设计方法和树算法设计方法； 第8章为广义表，归纳了广义表的概念和广义表算法设计方法； 第9章为图，归纳了图的概念、图遍历算法、图应用的各种算法设计方法； 第10章为查找，归纳了线性表、树表和哈希表等各种查找算法设计方法； 第11章为内排序，归纳了各种内排序算法设计方法； 第12章为外排序和文件，归纳了外排序过程和各类文件的组织结构。书中算法设计题中每道例题后面的数字表示该题目的难度，数字从①到⑤代表难度依次递增。

书中对部分重要知识点和示例提供了共计30小时的视频讲解，扫描书中的二维码，可以在线观看。附录A给出四份重点大学本科“数据结构”科目考试试题和参考答案； 附录B给出2012—2018年全国计算机专业硕士学位研究生入学考试数据结构部分试题的真题下载和视频讲解； 附录C给出书中视频对应二维码的汇总表。

本书以知识点归纳为引导，以求解方法总结为延伸，以典型示例讲解为扩展，以提高能力为目标，主要特色如下所述。

 强调数据结构求解问题的整体观，即数据逻辑结构、存储结构和算法设计的层次化思想。例如栈和队列属于逻辑结构的概念，顺序栈和链队属于存储结构的概念，后者是前者的存储实现，二者不能混同。

 总结知识难点的求解方法。例如求树中结点个数等，只要按照书中列出的方法套用公式，求解过程就会变得十分简单。

 力求归纳各类算法设计的规律，例如单链表算法很多是基于建表算法的，二叉树算法很多是基于遍历算法的，图算法很多是基于深度优先遍历和广度优先遍历算法的，如果读者掌握了建表算法、二叉树的遍历算法和图遍历算法，那么设计相关算法就会驾轻就熟了。

 深入讨论递归算法设计方法。递归算法设计是数据结构课程中的难点之一，编者从递归模型入手，介绍了从求解问题中提取递归模型的通用方法，讲解了从递归模型到递归算法设计的基本规律。

 提供了大量示例。全书超过1000道例题，绝大部分题目都给出了详解和分析过程，每道算法设计题都在VC 6.0中调试通过（注意程序文件扩展名为.cpp而不是.c）。读者可以从中体会求解问题的方法。

求解问题需要的是“能力”，从书本中可以获取“知识”，但知识不等于能力，能力是独有的，是自己通过学习知识提炼出解决问题的个性化方法。但愿本书能够帮助读者提高数据结构问题的解决能力。

自2013年本书出版以来，得到了广大读者的厚爱和支持，很多读者来信探讨学习方法和改进意见，成为这次改版的动力，作者衷心感谢。由于水平所限，尽管作者不遗余力，仍可能存在不足之处，敬请读者批评指正。

 

编者2019年9月