本书是参照教育部颁发的“2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲”编写的。主要内容包括：线性表、栈和队列、树与二叉树、图、查找、内部排序。
　　 本书按线性逻辑、层次逻辑、网状逻辑的顺序编写，根据学生对新知识学习认知的规律，对每种数据结构从数据的逻辑结构开始，逐渐地引入数据的存储结构和相关的方法，达到深化学生对概念的理解和掌握的目的。另外，本书在对数据结构进行深入研究的基础上，通过分析应用实例以及经典的算法设计方法，更加强调数据结构的应用。
本书主要特色：
书中内容精心设计，不仅为考生指明了复习思路与应试技巧 而且为考生汇总了常见错误与防范措施。
内容全面，书中配有大量名校的全真考研试题，供考生演练。
深入剖析研究生入学考试的特点和规律，助考生掌握解题方法和思路，彻底治除复习中的盲点。

----------------------封面---------------------
涵盖最新考研大纲
紧扣大纲设计题目
考点解析透彻清楚
资深命题阅卷团队
-------------------封底--------------------
本书特点：
□ 书中内容精心设计，本书不仅为考生指明了复习思路与应试技巧，而且紧扣
　最新的考试大纲设计了应试题目。
□ 内容全面，书中配有大量名校的全真考研试题和答案解析，供考生演练和自
　测。
□ 深入剖析研究生入学考试的特点和规律，帮助考生掌握解题方法和思路，彻
　底消除复习中的盲点。
本书是参照教育部颁发的“全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲”编写的。主要内容包括：线性表、栈和队列、树与二叉树、图、查找、内部排序。
本书紧扣研究生入学考试大纲，全面剖析了大纲知识点和备考要点，并根据学生对新知识学习认知的规律，从每种数据结构的逻辑结构开始，依次引入数据的存储结构和相关的方法，帮助学生深入清晰地理解数据结构各部分的难点。
本书可作为计算机硕士研究生入学考试的辅导教材，也可作为高等院校计算机类、电子类等相关专业的参考书。

数据结构是计算机及其相关专业的核心课程，也是全国硕士研究生入学考试计算机专业的必考科目之一。本书由长期坚持在教学一线的教师亲自主笔，在整理多年教学经验、分析考研试题的基础上编写的。书中融汇了数据结构这门课程的特点、难点、知识点和考研的出题重点，在内容的选取上符合计算机专业考研大纲要求，并兼顾学科的广度和深度，提供了丰富的例题和练习题，其中，有很多题目取自部分名校的研究生入学试题真题，并从应试思路上对这些题目进行解析。
　　本书采用类C语言作为数据结构和算法的描述语言，在内容的取舍上紧扣教育部研究生入学统一考试大纲要求。本书从指导课程教学、学习和考试的角度出发，通过对大量常见经典题型的分析，教授一种数据结构的解题方法、解题规律和解题技巧。这对提高读者分析问题的能力，理解基本要领和理论，开拓解题思路，将会起到良好的效果。主要内容分为6章。第1章是线性表；第2章是栈和队列；第3章是树和二叉树；第4章是图；第5章是查找；第6章是内部排序。各章均由核心考点、例题分析、基础要点总结、习题及解析4部分组成。书中习题及解析部分强调解题思路，注重算法分析。其中的题目全部选自数据结构课程的经典题库和名校考研真题，对其进行详细分析解答，以供读者了解课程考试与考研的深度和模式，进行实战演练。
　　本书适合参加计算机及相关专业硕士研究生入学考试的学生采用，也可作为计算机类专业或信息类专业的本科教材，还可供从事计算机工程与应用工作的科技工作者参考。
　　由于作者水平有限，书中存在疏漏与不妥之处，恳请读者批评指正。
　　
　　编　者

计算机\数据结构

目 录
第一章 线性表 1
一、线性表的定义和基本操作 1
二、线性表的实现 3
1. 线性表顺序存储结构 3
2. 链式存储结构 15
3. 线性表的应用 32
第二章 栈和队列 35
一、栈和队列的基本概念 35
二、栈和队列的顺序存储结构 39
三、栈和队列的链式存储结构 55
四、栈和队列的应用 63
五、特殊矩阵的压缩存储 84
第三章 树与二叉树 88
一、树的基本概念 88
二、二叉树 93
1．二叉树的定义及其主要特征 93
2．二叉树的顺序存储结构和链式存储结构 99
3. 二叉树的遍历 114
4. 线索二叉树的基本概念和构造 124
5．二叉排序树 138
6．平衡二叉树 147
三、树、森林 154
1．树的存储结构 154
2．森林与二叉树的转换 156
3．树和森林的遍历 158
四、树的应用 162
1. 等价类问题 162
2. 哈夫曼树及其应用 169
第四章 图 185
一、图的基本概念 185
二、图的存储结构及基本操作 196
1. 邻接矩阵法 196
2．邻接表法 199
三、图的遍历 216
1．深度优先搜索（Depth_First Search） 217
2．广度优先搜索（Breadth_First Search） 227
四、图的基本应用及其复杂度分析 236
1．最小（代价）生成树 239
2．最短路径 258
3．拓扑排序 266
4．关键路径 270
第五章 查找 277
一、查找的基本概念 277
二、顺序查找 277
三、折半查找 287
四、B-树 294
五、散列(Hash)表及其查找 311
六、查找算法的分析及应用 318
第六章 内部排序 321
一、排序的基本概念 321
二、插入排序（Straight Insertion Sort） 321
三、起泡排序（Bubble Sort） 322
四、简单选择排序（Selection Sort） 323
五、希尔排序（Shell Sort） 331
六、快速排序（Quick Sort） 334
七、堆排序（Heap Sort） 341
八、二路归并排序（Merge Sort） 347
九、基数排序（Radix Sort） 351
十、各种内部排序算法的比较 353
十一、内部排序算法的应用 362