- I -
前言
缘起
《数据结构》是一门计算机专业基础课，各类计算机考试都禁不住要考它，专升本考
试自然也不例外。我给学生辅导这门课程已经有几个年头了，讲稿换了几次，逐渐丰
富起来。加之看到学生们埋头记笔记时辛苦的样子，就产生了写一本小册子的想法。
另外，还有一层意思就是对数次辅导进行总结，以便交流之用。
说明
首先，需要说明的是这本书在语言风格上不太讲究，常有些不严谨的表达，或调侃，
或土得掉渣，难登大雅之堂，请勿在正规场合引用这些说法。这样做的目的，仅仅是
为了更简练、更直接地描述思想，方便理解、记忆和使用。凡是这种情况，往往都用
引号括起来，并加以脚注说明。
还有，本书需配合《数据结构》(严蔚敏)教材使用。由于篇幅有限，多数概念、术语
没有详释。
另外，每章之后都配有习题，或多或少，难度不一，并没有局限于专升本的要求。对
所有习题都提供了参考答案。
致谢
我要感谢所有给予我帮助的人。
张志老师的大力支持和帮助使得本书得以面世，他还提供了近年专升本试题。李永干
老师的帮助使得本书顺利印刷。谭业武老师给了我很大支持，还提出了很多建议。
最后，我要感谢隆坤，她总是给我最大的支持，使那些本来只在我想象中的事情变成
现实。
庄波
于滨州学院
2005 年 2 月 26 日
- II -
第 0 章 复习提示 ................................................................................................................ 1
一、 教材内容 ............................................................................................................ 1
二、 复习提示 ............................................................................................................ 1
1. 经典算法 ........................................................................................................ 1
2. 绪论 ............................................................................................................... 1
3. 线性表 ........................................................................................................... 2
4. 栈和队列 ........................................................................................................ 2
5. 串 .................................................................................................................. 2
6. 树和二叉树 ..................................................................................................... 2
7. 图 .................................................................................................................. 3
8. 查找表 ........................................................................................................... 3
9. 内部排序 ........................................................................................................ 3
第 1 章 绪论 ....................................................................................................................... 5
一、 基础知识 ............................................................................................................ 5
二、 算法 .................................................................................................................. 5
三、 习题 .................................................................................................................. 6
第 2 章 线性表 ................................................................................................................... 8
一、 基础知识和算法 .................................................................................................. 8
1. 线性表及其特点 .............................................................................................. 8
2. 顺序表——线性表的顺序存储结构 ..................................................................... 8
3. 单链表——线性表的链式存储结构之一 ............................................................ 11
4. 循环链表 ...................................................................................................... 16
5. 双向循环链表 ................................................................................................ 17
6. 顺序表与单链表的比较................................................................................... 17
二、 习题 ................................................................................................................ 18
第 3 章 栈和队列 .............................................................................................................. 19
一、 基础知识和算法 ................................................................................................ 19
1. 栈 ................................................................................................................ 19
2. 链栈 ............................................................................................................. 19
3. 顺序栈 ......................................................................................................... 20
4. 队列 ............................................................................................................. 21
5. 链队列 ......................................................................................................... 22
6. 循环队列 ...................................................................................................... 22
7. 栈和队列比较 ................................................................................................ 25
8. 简化的栈和队列结构 ...................................................................................... 25
9. 栈和队列的应用 ............................................................................................ 25
二、 习题 ................................................................................................................ 27
第 4 章 串 ........................................................................................................................ 27
一、 基础知识和算法 ................................................................................................ 27
1. 概念 ............................................................................................................. 27
2. 串的基本操作 ................................................................................................ 27
3. 串的存储结构 ................................................................................................ 28
二、 习题 ................................................................................................................ 28
第 6 章 树和二叉树 ........................................................................................................... 29
一、 基础知识和算法 ................................................................................................ 29
1. 树及有关概念 ................................................................................................ 29
2. 二叉树 ......................................................................................................... 29
- III -
3. 二叉树的性质 ................................................................................................ 29
4. 二叉树的存储结构 ......................................................................................... 30
5. 二叉树的五种基本形态................................................................................... 30
6. 遍历二叉树 ................................................................................................... 31
7. 遍历二叉树的应用 ......................................................................................... 35
8. 线索二叉树 ................................................................................................... 36
9. 树和森林 ...................................................................................................... 37
10. 赫夫曼树及其应用 ....................................................................................... 39
二、 习题 ................................................................................................................ 40
第 7 章 图 ........................................................................................................................ 41
一、 基础知识和算法 ................................................................................................ 41
1. 图的有关概念 ................................................................................................ 41
2. 图的存储结构 ................................................................................................ 41
3. 图的遍历 ...................................................................................................... 44
4. 最小生成树 ................................................................................................... 47
5. 拓扑排序 ...................................................................................................... 48
6. 关键路径 ...................................................................................................... 48
7. 最短路径 ...................................................................................................... 50
二、 习题 ................................................................................................................ 51
第 9 章 查找 ..................................................................................................................... 55
一、 基础知识和算法 ................................................................................................ 55
1. 有关概念 ...................................................................................................... 55
2. 顺序查找 ...................................................................................................... 55
3. 折半查找 ...................................................................................................... 56
4. 索引顺序表 ................................................................................................... 58
5. 二叉排序树 ................................................................................................... 58
6. 平衡二叉树 ................................................................................................... 61
7. B-树和 B
+
树 ................................................................................................... 63
8. 键树 ............................................................................................................. 63
9. 哈希表 ......................................................................................................... 63
二、 习题 ................................................................................................................ 65
第 10 章 内部排序 ............................................................................................................ 67
一、 基础知识和算法 ................................................................................................ 67
1. 排序的有关概念 ............................................................................................ 67
2. 直接插入排序 ................................................................................................ 67
3. 折半插入排序 ................................................................................................ 68
4. 希尔排序（缩小增量排序） ............................................................................ 69
5. 起泡排序 ...................................................................................................... 70
6. 快速排序 ...................................................................................................... 70
7. 简单选择排序 ................................................................................................ 72
8. 堆排序 ......................................................................................................... 73
9. 归并排序 ...................................................................................................... 75
10. 基数排序 .................................................................................................... 77
11. 各种排序方法比较 ....................................................................................... 78
- 1 -
第0章 复习提示
一、教材内容
使用教材《数据结构》C 语言版 严蔚敏，清华大学出版社。
章节 去掉 第 5、8、11、12 章
去掉 **部分
去掉 1.3，2.4，4.4
二、复习提示
1. 经典算法
单链表：遍历、插入、删除
循环队列：队列空、队列满的条件
二叉树：递归遍历及应用
有序表的二分法查找
快速排序
简单选择排序
2. 绪论
掌握几个重要概念
数据结构、抽象数据类型、算法
时间复杂度的简单计算（C
1
）
掌握几种说法
数据元素是…，数据项是…
数据结构中关系的四种基本结构
数据结构的形式定义
算法的五个特征
1
记号 C，表示要求掌握计算方法，会计算。本节下同。
www.juanjuantx.com 6. 树和二叉树
- 2 -
3. 线性表
线性表的概念和四个特征
顺序表和单链表的类型定义
在顺序表中查找、插入、删除，灵活运用
在单链表中查找、插入、删除，灵活运用
循环链表及双向链表的定义、插入、删除
算法：
单链表的算法，灵活运用、会编程（P
2
）
4. 栈和队列
栈和队列的概念、特点
入栈、出栈操作，灵活掌握
了解栈的实现：链栈和顺序栈（A
3
算法，P）
了解队列的实现，链队列和循环队列，注意链队列中的出队列操作
算法：
注意循环队列空和满的条件（A，P）
会运用栈和队列
5. 串
掌握相关概念
会运用串的基本操作（C），特别是 Concat()，Substring()，Index()和 Replace()
知道串的三种存储结构及其特点
6. 树和二叉树
树和二叉树的有关概念
二叉树的性质
熟练掌握遍历二叉树的递归算法，并灵活运用
知道线索二叉树，会对二叉树进行线索化
树、森林和二叉树的转化，会遍历树和森林
赫夫曼树及其应用
算法：
递归遍历二叉树及其应用（P）
构造赫夫曼树和赫夫曼编码（A）
树和二叉树的转换（A）
森林和二叉树的转换（A）
遍历树和森林（A）
2
记号 P，要求达到编写算法和程序的能力。本节下同。
3
记号 A，要求掌握算法思想，会演算。本节下同。
