数据结构讲义(严蔚敏版)[精品].doc

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