数据结构讲义（庄波）2005年.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：1.69M 资料格式：doc 举报版权申诉

songhj2086-3418072-4744302542887239816.doc.pdf-第1页.png

第1页 / 共90页

songhj2086-3418072-4744302542887239816.doc.pdf-第2页.png

第2页 / 共90页

songhj2086-3418072-4744302542887239816.doc.pdf-第3页.png

第3页 / 共90页

songhj2086-3418072-4744302542887239816.doc.pdf-第4页.png

第4页 / 共90页

songhj2086-3418072-4744302542887239816.doc.pdf-第5页.png

第5页 / 共90页

songhj2086-3418072-4744302542887239816.doc.pdf-第6页.png

第6页 / 共90页

songhj2086-3418072-4744302542887239816.doc.pdf-第7页.png

第7页 / 共90页

songhj2086-3418072-4744302542887239816.doc.pdf-第8页.png

第8页 / 共90页

第0章复习提示

一、教材内容

二、复习提示

1. 经典算法

2. 绪论

3. 线性表

4. 栈和队列

5. 串

6. 树和二叉树

7. 图

8. 查找表

9. 内部排序

第1章绪论

一、基础知识

二、算法

三、习题

第2章线性表

一、基础知识和算法

1. 线性表及其特点

2. 顺序表——线性表的顺序存储结构

(1) 特点

(2) 类型定义

(3) 基本形态

1°. 顺序表空

2°. 顺序表满

3°. 不空也不满

(4) 基本算法——遍历

1°. 顺序访问所有元素

2°. 查找元素x

(5) 插入算法 ListInsert(&L,i,x)

1°. 前提：表不满

2°. 合理的插入范围：1≤i≤L.length+1

3°. 步骤

4°. 算法

(6) 删除算法 ListDelete(&L,i,&x)

1°. 前提：表非空

2°. 合理的删除范围：1≤i≤L.length

3°. 步骤

4°. 算法

(7) 算法分析

(8) 其他算法

1°. InitList (&L), ClearList (&L)

2°. ListEmpty (L)

3°. ListLength (L)

4°. GetElem (L, i, &e)

3. 单链表——线性表的链式存储结构之一

(1) 概念

(2) 特点

(3) 类型定义

(4) 基本形态

1°. 单链表空

2°. 单链表不空

(5) 基本算法（遍历）

1°. 顺序访问所有元素

2°. 查找元素x

3°. 查找第i个元素

4°. 查找第i-1个元素

(6) 插入算法 ListInsert(&L,i,x)

(7) 删除算法 ListDelete(&L,i,&x)

(8) 建立链表的两种方法

1°. 顺序建表

2°. 逆序建表

4. 循环链表

(1) 特点

(2) 类型定义

(3) 基本形态

(4) 与单链表的联系

5. 双向循环链表

(1) 特点

(2) 类型定义

(3) 基本形态

(4) 与单链表和循环链表的联系

(5) 插入和删除

6. 顺序表与单链表的比较

二、习题

第3章栈和队列

一、基础知识和算法

1. 栈

2. 链栈

(1) 存储结构

(2) 类型定义

(3) 基本形态

1°. 栈空

2°. 栈非空

3°. 栈满（一般不出现）

(4) 基本算法

1°. 入栈 Push (&s, x)

2°. 出栈 Pop (&s, &x)

3°. 栈顶元素

3. 顺序栈

(1) 存储结构

(2) 类型定义

(3) 基本形态

1°. 栈空

2°. 栈满

3°. 栈不空、不满

(4) 基本算法

1°. 入栈 Push (&s, x)

2°. 出栈 Pop (&s, &x)

3°. 栈顶元素

4. 队列

5. 链队列

(1) 存储结构

(2) 类型定义

(3) 基本形态

(4) 基本算法

1°. 入队列

2°. 出队列

6. 循环队列

(1) 存储结构

(2) 类型定义

(3) 基本形态

1°. 队列空

2°. 队列满

3°. 队列不空也不满

4°. 加一标志区分队列空和队列满的情况

(4) 基本算法

1°. 入队列

2°. 出队列

3°. 队列中元素个数

4°. 用标志区分队列空和满

7. 栈和队列比较

8. 简化的栈和队列结构

9. 栈和队列的应用

1°. 表达式求值

2°. 括号匹配

3°. 递归程序的非递归化

4°. 作业排队

5°. 按层次遍历二叉树

二、习题

第4章串

一、基础知识和算法

1. 概念

2. 串的基本操作

3. 串的存储结构

二、习题

第5章

第6章树和二叉树

一、基础知识和算法

1. 树及有关概念

2. 二叉树

3. 二叉树的性质

1°. 二叉树的第i层上至多有2i-1个结点。

2°. 深度为k的二叉树至多有2k-1个结点。

3°. 叶子结点n0，度为2的结点为n2，则n0 = n2+1。

4°. n个结点的完全二叉树深度为。

5°. n个结点的完全二叉树，结点按层次编号

4. 二叉树的存储结构

1°. 顺序存储结构

2°. 链式存储结构

5. 二叉树的五种基本形态

6. 遍历二叉树

1°. 常见有四种遍历方式

2°. 先序遍历算法

3°. 中序遍历算法

4°. 后序遍历

5°. 按层次遍历

6°. 非递归遍历二叉树

7°. 三叉链表的遍历算法

7. 遍历二叉树的应用

1°. 写出遍历序列（前、中、后序）

2°. 根据遍历序列画出二叉树

3°. 编写算法

8. 线索二叉树

1°. 线索

2°. 线索化二叉树

3°. 画出线索二叉树

4°. 遍历线索二叉树

9. 树和森林

1°. 树的存储结构

2°. 树与二叉树的转换

3°. 森林与二叉树的转换

4°. 树的遍历

5°. 遍历森林

6°. 遍历树、森林与遍历二叉树的关系

10. 赫夫曼树及其应用

1°. 最优二叉树(赫夫曼树，哈夫曼树)

2°. 构造赫夫曼树

3°. 赫夫曼编码(前缀码)

二、习题

第7章图

一、基础知识和算法

1. 图的有关概念

2. 图的存储结构

(1) 图的存储结构

(2) 邻接矩阵

(3) 邻接表

(4) 逆邻接表

(5) 十字链表

(6) 邻接多重表

3. 图的遍历

(1) 深度优先搜索

1°. 遍历方法

2°. 分析方法

3°. 算法

(2) 广度优先搜索

1°. 遍历方法

2°. 分析方法

3°. 算法

(3) 时间复杂度分析

4. 最小生成树

(1) 最小生成树及MST性质

(2) 克鲁斯卡尔算法

(3) 普里姆算法

(4) 两种算法的比较

5. 拓扑排序

6. 关键路径

(1) AOE网，关键路径

(2) 关键路径算法

7. 最短路径

(1) 迪杰斯特拉算法

(2) 弗洛伊德算法

二、习题

第8章

第9章查找

一、基础知识和算法

1. 有关概念

2. 顺序查找

(1) 思路

(2) 算法

(3) 分析

1°. 平均查找长度

2°. 判定树

3°. 时间复杂度

3. 折半查找

(1) 思路

(2) 算法

(3) 分析

1°. 判定树

2°. 平均查找长度

3°. 时间复杂度

4. 索引顺序表

5. 二叉排序树

(1) 二叉排序树

(2) 查找

(3) 插入

(4) 建立

(5) 删除

1°. 叶子

2°. 左子树或右子树为空

3°. 左右子树都不空

(6) 分析

6. 平衡二叉树

(1) 平衡因子和平衡二叉树(AVL树)

(2) 构造平衡二叉排序树

(3) 分析

1°. 查找 (同二叉排序树)

2°. 平均查找长度ASL

3°. 时间复杂度

7. B-树和B+树

(1) B-树

(2) B+树

8. 键树

9. 哈希表

(1) 哈希表(散列表，杂凑表)

(2) 哈希函数

(3) 冲突

1°. 开放定址法

2°. 再哈希法

3°. 链地址法

4°. 建立公共溢出区

(4) 装填因子

(5) 举例

二、习题

第10章内部排序

一、基础知识和算法

1. 排序的有关概念

2. 直接插入排序

(1) 思路

(2) 分析

3. 折半插入排序

(1) 思路

(2) 程序

(3) 分析

4. 希尔排序（缩小增量排序）

(1) 思路

(2) 程序

5. 起泡排序

(1) 思路

(2) 程序

(3) 分析

6. 快速排序

(1) 思路

(2) 程序

(3) 分析

7. 简单选择排序

(1) 思路

(2) 程序

(3) 分析

8. 堆排序

(1) 堆及其特点

(2) 判断序列是否构成堆

(3) 建立堆

(4) 堆排序

9. 归并排序

(1) 思路

(2) 程序

(3) 分析

10. 基数排序

(1) 思路

1°. 多关键字排序

2°. 链式基数排序

(2) 分析

11. 各种排序方法比较

二、习题

附录A: 习题解答

前言缘起《数据结构》是一门计算机专业基础课，各类计算机考试都禁不住要考它，专升本考试自然也不例外。我给学生辅导这门课程已经有几个年头了，讲稿换了几次，逐渐丰富起来。加之看到学生们埋头记笔记时辛苦的样子，就产生了写一本小册子的想法。另外，还有一层意思就是对数次辅导进行总结，以便交流之用。说明首先，需要说明的是这本书在语言风格上不太讲究，常有些不严谨的表达，或调侃，或土得掉渣，难登大雅之堂，请勿在正规场合引用这些说法。这样做的目的，仅仅是为了更简练、更直接地描述思想，方便理解、记忆和使用。凡是这种情况，往往都用引号括起来，并加以脚注说明。还有，本书需配合《数据结构》(严蔚敏)教材使用。由于篇幅有限，多数概念、术语没有详释。另外，每章之后都配有习题，或多或少，难度不一，并没有局限于专升本的要求。对所有习题都提供了参考答案。致谢我要感谢所有给予我帮助的人。张志老师的大力支持和帮助使得本书得以面世，他还提供了近年专升本试题。李永干老师的帮助使得本书顺利印刷。谭业武老师给了我很大支持，还提出了很多建议。最后，我要感谢隆坤，她总是给我最大的支持，使那些本来只在我想象中的事情变成现实。庄波于滨州学院 2005 年 2 月 26 日 - I -

第 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. 串的存储结构 ......................................................................................................27 二、习题 ........................................................................................................................28 第 6 章树和二叉树 ..................................................................................................................29 一、基础知识和算法 ...................................................................................................... 29 1. 树及有关概念 ......................................................................................................29 2. 二叉树 ................................................................................................................ 29 - II -

3. 二叉树的性质 ......................................................................................................29 4. 二叉树的存储结构...............................................................................................30 5. 二叉树的五种基本形态 ........................................................................................30 6. 遍历二叉树 ......................................................................................................... 30 7. 遍历二叉树的应用 ...............................................................................................35 8. 线索二叉树 ......................................................................................................... 36 9. 树和森林 .............................................................................................................37 10. 赫夫曼树及其应用 .............................................................................................38 二、习题 ........................................................................................................................39 第 7 章图 ................................................................................................................................41 一、基础知识和算法 ...................................................................................................... 41 1. 图的有关概念 ......................................................................................................41 2. 图的存储结构 ......................................................................................................41 3. 图的遍历 .............................................................................................................44 4. 最小生成树......................................................................................................... 46 5. 拓扑排序 .............................................................................................................47 6. 关键路径 .............................................................................................................47 7. 最短路径 .............................................................................................................48 二、习题 ........................................................................................................................49 第 9 章查找 ............................................................................................................................ 51 一、基础知识和算法 ...................................................................................................... 51 1. 有关概念 .............................................................................................................51 2. 顺序查找 .............................................................................................................51 3. 折半查找 .............................................................................................................52 4. 索引顺序表......................................................................................................... 54 5. 二叉排序树 ......................................................................................................... 54 6. 平衡二叉树 ......................................................................................................... 56 7. B-树和 B+树 ......................................................................................................... 58 8. 键树 ....................................................................................................................58 9. 哈希表 ................................................................................................................ 58 二、习题 ........................................................................................................................60 第 10 章内部排序 ................................................................................................................... 61 一、基础知识和算法 ...................................................................................................... 61 1. 排序的有关概念 .................................................................................................. 61 2. 直接插入排序 ......................................................................................................61 3. 折半插入排序 ......................................................................................................62 4. 希尔排序（缩小增量排序）.................................................................................62 5. 起泡排序 .............................................................................................................63 6. 快速排序 .............................................................................................................64 7. 简单选择排序 ......................................................................................................65 8. 堆排序 ................................................................................................................ 66 9. 归并排序 .............................................................................................................67 10. 基数排序 ...........................................................................................................68 11. 各种排序方法比较 .............................................................................................69 - III -

第 0 章复习提示一、教材内容  使用教材《数据结构》C 语言版严蔚敏，清华大学出版社。  章节去掉第 5、8、11、12 章去掉 **部分去掉 1.3，2.4，4.4 二、复习提示 1. 经典算法单链表：遍历、插入、删除循环队列：队列空、队列满的条件二叉树：递归遍历及应用有序表的二分法查找快速排序简单选择排序 2. 绪论掌握几个重要概念数据结构、抽象数据类型、算法时间复杂度的简单计算（C1）掌握几种说法数据元素是…，数据项是… 数据结构中关系的四种基本结构数据结构的形式定义算法的五个特征 1 记号 C，表示要求掌握计算方法，会计算。本节下同。 - 1 -

w 3. 线性表 6. 树和二叉树线性表的概念和四个特征顺序表和单链表的类型定义在顺序表中查找、插入、删除，灵活运用在单链表中查找、插入、删除，灵活运用循环链表及双向链表的定义、插入、删除算法：单链表的算法，灵活运用、会编程（P2） 4. 栈和队列栈和队列的概念、特点入栈、出栈操作，灵活掌握了解栈的实现：链栈和顺序栈（A3算法，P）了解队列的实现，链队列和循环队列，注意链队列中的出队列操作算法：注意循环队列空和满的条件（A，P）会运用栈和队列 5. 串掌握相关概念会运用串的基本操作（C），特别是 Concat()，Substring()，Index()和 Replace() 知道串的三种存储结构及其特点 6. 树和二叉树树和二叉树的有关概念二叉树的性质熟练掌握遍历二叉树的递归算法，并灵活运用知道线索二叉树，会对二叉树进行线索化树、森林和二叉树的转化，会遍历树和森林赫夫曼树及其应用算法：递归遍历二叉树及其应用（P）构造赫夫曼树和赫夫曼编码（A）树和二叉树的转换（A）森林和二叉树的转换（A）遍历树和森林（A） 2 记号 P，要求达到编写算法和程序的能力。本节下同。 3 记号 A，要求掌握算法思想，会演算。本节下同。 - 2 -

w 7. 图 9. 内部排序图的有关概念熟练掌握图的各种存储结构图的遍历：深度优先、广度优先（A）最小生成树算法（两个）及其特点（A）拓扑排序（A）关键路径算法（A）最短路径算法（两个）（A，O4：时间复杂度） 8. 查找表查找的有关概念，ASL 等顺序查找（A，P）熟练掌握有序表的折半查找算法（A，P，C）了解索引顺序表熟练掌握二叉排序树的概念，建立（A），查找（A，P），删除（A），计算 ASL（C）平衡二叉排序树的概念，建立（A），判断失去平衡的类型，平衡化（A），计算 ASL （C）了解 B_树，B+树的概念和特点知道键树（数字查找树）哈希表的概念、特点、构造哈希表（A），计算 ASL 和装填因子α（C）了解各种查找表的性能（O） 9. 内部排序直接插入排序（A）折半插入排序（A，P）希尔排序（A）起泡排序（A）快速排序（A，P，O）简单选择排序（P，A，O）堆的概念，调整成堆（A），堆排序（A，O）归并排序（A，O）链式基数排序（A，O）各种排序算法的对比结论（O） 4 记号 O，要求掌握算法的时间复杂度。本节下同。 - 3 -

第 1 章绪论一、基础知识概念和术语(黑体字部分)。另外，注意： 1、数据元素是数据的基本单位。P4 2、数据项是数据不可分割的最小单位。P5 3、数据结构及其形式定义。P5 四种基本结构：①集合②线性结构③树形结构④图（网）状结构 4、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构）顺序映像（顺序存储结构）位置“相邻” 非顺序映像（链式存储结构）指针表示关系 P6 5、数据类型 P7 抽象数据类型（ADT）P7 ADT=（数据对象，数据关系，基本操作） ADT 细分为原子类型，固定聚合，可变聚合类型。P8 6、算法的概念 P13 7、算法的五个特征 ①有穷性 ②确定性 ③可行性 ④输入（0 个或多个） ⑤输出（1 个或多个） 8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量其中正确性的四个层次（通常要求达到 C 层）。 9、算法的时间复杂度 P15 常见有： O(1)，O(n)，O(n2)，O(log2n)5，O(n log2n)，O(2n) 语句频度，用归纳法计算。 10、算法的空间复杂度 P17 二、算法起泡排序。P16 5 分析算法的时间复杂度时，log2n 常简单记作 log n。 - 5 -

分享到：

赞收藏

资料库

数据结构讲义（庄波）2005年.doc

相关推荐

课程资源

热门标签

最新资料