青岛理工大学数据结构课件第六章

LTM设计原则
实际应用 Mentoring 总结领悟 综合案例 Training 复杂概念 简单程序 Learning 基本概念
理论
实践
LTM实战训练法
Mentoring
项目
Training
案例
Learning
理论
职业能力

(3)校企合作，工学结合 学院积极推行校企合作，工学结合的培养模式，实 现了理论教学和实践教学一体化，解决了理论教学和实践 教学脱节的问题。充分利用企业实践项目教学资源、管理 资源，采用国际先进的教学模式及课程体系，大力加强学 生实践能力和职业技能的培养，高度重视实践和实训环节 教学，根据企业需求进行项目训练，对学生进行行业理解 和职业素质培养，从第二学年开始实施分专业方向教学， 从第三学年按照 “2+1” 模式实施企业化实训。以此带 动专业调整与建设，引导课程设置、教学内容和教学方法 改革。计算机系与齐鲁软件园驻园企业紧密合作，积极推 进“2+1”企业化实训，首批38人已顺利就业，专业对口 率100%。
立体化的教学资源
多样化学习方案 引导学习
自主学习
面 授 辅 导
实 训 指 导
布 置 练 习
课 件 使 用
网 络 课 程
资 源 整 合
在 线 答 疑
在 线 测 试
网 上 交 作 业
小 组 讨 论 提 案
三、教学设计
1.教学模式
(1)上课上机一体化，教、学、做一体化 围绕专业方向，不断改善实训、实习 条件，围绕课程主线与实践主线，建设融 基础实验、专业实验、创新实验、集中实 训、教学科研于一体的专业化实训中心。 确保 “两条主线”中的主干课程实现“教、 学、做”一体化，探讨课堂与实训地点一 体化模式。

查找操作
顺序查找
二分查找
链表查找
在顺序存储结构的线性表中，查找操 作需要从线性表的第一个节点开始， 逐个比较节点的数据域，直到找到目 标数据或遍历完整个线性表。时间复 杂度为O(n)。
在有序的顺序存储结构的线性表中， 查找操作可以采用二分查找算法。每 次比较目标数据与中间节点的数据域 ，如果目标数据大于中间节点，则在 右半部分继续查找；否则在左半部分 查找。时间复杂度为O(log n)。
数据结构是算法的基础。许多算法的实现需要依赖于特定的数据结构， 因此掌握常见的数据结构是编写高效算法的关键。
数据结构在解决实际问题中具有广泛应用。无论是操作系统、数据库系 统、网络通信还是人工智能等领域，数据结构都发挥着重要的作用。
数据结构的分类
根据数据的逻辑关系，数据结构可以分为线性结构和非线 性结构。线性结构如数组、链表、栈和队列等，非线性结 构如树形结构和图形结构等。
04
数据结构操作
插入操作
顺序插入
在顺序存储结构的线性表中，插入操作 需要找到插入位置的前驱节点，修改前 驱节点的指针，使其指向新节点，然后 让新节点指向后继节点。如果线性表的 第一个节点是空节点，则将新节点作为 第一个节点。
VS
链式插入
在链式存储结构的线性表中，插入操作需 要找到插入位置的前驱节点，修改前驱节 点的指针，使其指向新节点。如果线性表 的第一个节点是空节点，则将新节点作为 第一个节点。
图
01
02
03
04
图是一种非线性数据结构，由 节点和边组成，其中节点表示 数据元素，边表示节点之间的
关系。
图具有网络结构，节点之间的 关系可以是任意复杂的，包括
双向、单向、无向等。

数据类型反映了数据的取值范围以及对这类数据可以施加的运算。例如，在高级程序设计 语言中的整数都具有下列"数学特性"：1）它是…-2,-1,0,1,2，…这样一个序列；2）它可以 进行"+"、"-"、" "、"/"及"取模"等运算。
在高级程序设计语言中引入了整型、实型和布尔型等基本数据类型，程序员在编制程序时 就可以将其数据对象建立其上，避免了复杂的机器表示。数据类型就像一层外衣，使得程序员 只需知道如何使用整数、实数和布尔数，而不需要了解机器的内部细节，就能完成相应的程序 设计任务。
第1章
绪论
1.1 数据结构
3.关键码 关键码 （key）指的是数据元素中能起标识作用的数据项，例如学生信息表中的学号和姓 名。其中能起惟一标识作用的关键码称为“主关键码”，如学号；反之称为“次关键码”，如 姓名。
4.数据对象 数据对象(data object)是具有相同性质的数据元素的集合，是数据的一个子集。例如， 整数数据对象是集合Ｎ＝{0，±1，±2，…}，字母字符数据对象是集合C＝{'A'，'B'，…， 'Z'}。学生信息管理系统中的学生表也可看成一个数据对象。
新世纪应用型高等教育 计算机类课程规划教材
数据结构
新世纪应用型高等教育教材编审委员会 组编 主编 曹春萍
第2章 线性表
2.1 线性表的基本概念
线性表（linear-list）是一组具有相同特征的数据元素的有限序列。如， 某校十个教学班级的学生人数（50，53，55，52，56，59，60，55，57，51） 构成一个线性表。
第2章 线性表
第1章

将电路中的元件和连线抽象为图中的顶点和 边，利用图算法进行电路分析和优化。
路由算法
生物信息学
利用图数据结构表示计算机网络中的拓扑结 构，利用最短路径算法进行路网络、 基因调控网络等复杂生物系统，进行生物信 息学分析和挖掘。
05
查找与排序
查找的基本概念与分类
选择排序算法
简单选择排序
每次从待排序的数据元素中选出最小（或最大）的一个 元素，存放在序列的起始位置，直到全部待排序的数据 元素排完。
堆排序
利用堆这种数据结构所设计的一种排序算法，是选择排 序的一种。可以利用数组来模拟堆的结构，通过构造大 顶堆或小顶堆来实现排序。
归并排序算法
归并排序的思想
将两个（或更多）有序表合并成一个新的有序表，即把 待排序序列分为若干个子序列，每个子序列是有序的。 然后再把有序子序列合并为整体有序序列。
开放寻址法、链地址法等。
排序的基本概念与分类
排序的定义
将一组无序的记录序列调整为有序的记录序 列。
排序的分类
内部排序和外部排序，内部排序包括插入排 序、交换排序、选择排序、归并排序等。
插入排序算法
要点一
直接插入排序
每次将一个待排序的元素插入到前面已经排好序的序列中， 寻找合适的位置。
要点二
希尔排序
二叉树的遍历算法
先序遍历
先访问根节点，然后遍 历左子树，最后遍历右
子树。
中序遍历
先遍历左子树，然后访 问根节点，最后遍历右
子树。
后序遍历
层次遍历
先遍历左子树，然后遍 历右子树，最后访问根
节点。
按照层次顺序从上到下、 从左到右遍历二叉树中
的所有节点。
树和森林的遍历算法

2
队列(Queues)
1. 定义 是一个线性表，其插入和删 除操作分别在表的不同端进行。 添加新元素的那一端被称为队尾 (rear)，而删除元素的那一端被 称为队首(front)。
2. 队 列 是 一 个 先 进 先 出 （ firstin-first-out, FIFO ） 的 线 性 表 。
7/15/2020
7/15/2020
22
公式化类Queue
template<class T> T Queue<T>::Last() const { //返回队列的最后一个元素
//如果队列为空，则引发异常OutOfBounds if (IsEmpty()) throw OutOfBounds(); return queue[rear]; }
7/15/2020
23
公式化类Queue
template<class T>
Queue<T>& Queue<T>::Add(const T& x)
{ //把x 添加到队列的尾部
//如果队列满，则引发异常NoMem
if (IsFull()) throw NoMem();
rear = (rear + 1) % MaxSize;
3
队列 ( Queue )
定义
队列是只允许在一端删除，在另一端插入的 顺序表
允许删除的一端叫做队首(front)，允许插入 的一端叫做队尾(rear)。
特性
先进先出(FIFO, First In First Out)
7/15/2020
4
队列
7/15/2020
5
队列

在现实中的应用：
如族谱、各种社会组织机构等。
在计算机领域：
编译程序中的语法树、数据库系统中的索引等。
6.1树的定义和基本术语
1、树的定义
树是由n(n≥0)个结点组成的有限集合。
如果n= 0，称为空树；
否则，在一棵非空树中，满足如下两个条件：
（1）有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；
3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;
2、二叉树的五种不同形态
3、二叉树和树的区别：
二叉树不是树的特殊情形，它们是两个概念。
树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
6.2.2二叉树的性质
性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：
（1）如i=1，则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为└i/2┘。
（2）如2×i>n，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i。
祖先(ancestor)结点:若树中结点k到ks存在一条路径，则称k是ks的祖先
子孙(descendant)结点:若树中结点k到ks存在一条路径，则称ks是k的子孙
结点所处层次(level) :根结点的层数为1，其余结点的层，其余结点的层数为双亲结点的层数加1
树的高度(depth):树中结点的最大层数
完全二叉树：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层的结点集中出现在左端若干连续位置上，这就是完全二叉树。

查找元素算法
总结词
有序性利用
详细描述
查找元素算法需要利用队列的有序性。 由于队列中的元素按照优先级顺序排 列，因此可以通过二分查找等算法快 速定位具有特定优先级的元素的位置。
查找元素算法
总结词
返回位置信息
详细描述
查找元素算法不仅需要返回查找到的元素本 身，还需要返回该元素在队列中的位置信息。 这有助于用户更好地了解元素在队列中的位 置和优先级情况。
THANKS FOR WATCHING
感谢您的观看
特点
优先队列中的元素可以按照优先 级的高低进行排序，优先级高的 元素具有更高的出队优先权。
优先队列的应用场景
任务调度
在任务调度中，可以按照任务的优先级进行排序， 优先级高的任务先被执行。
路由协议
在路由协议中，数据包可以根据优先级的高低进 行转发，优先级高的数据包先被转发。
操作系统
在操作系统中，进程可以根据优先级的高低进行 调度，优先级高的进程先被执行。
分段链表
将队列元素分成多个段，每个段内部使用链表结构，以减少插入和 删除操作的时间复杂度。
06 优先队列的案例分析
基于数组实现的优先队列案例
总结词：简单易懂
详细描述：基于数组实现的优先队列是最直 观和简单的实现方式。通过数组的索引访问 元素，可以快速地找到最小（或最大）元素 并进行出队操作。但需要注意的是，当元素 数量变化时，需要重新调整数组的大小，这
基于二叉堆实现的优先队列案例
总结词：平衡高效
描述：基于二叉堆实现的优先队列是一种平衡树结构， 具有高效的插入、删除和查找最小（或最大）元素的操 作。二叉堆中的每个节点都大于（或小于）其子节点， 根节点是最小（或最大）元素。通过调整节点顺序，可 以快速地实现出队操作。二叉堆在实现优先队列时具有 较好的时间和空间复杂度，是一种高效的数据结构。

链表
总结词
链表是一种线性数据结构，它通过指针将一系列节点连接起来。
详细描述
每个节点包含数据和指向下一个节点的指针。链表的长度可以在运行时动态改 变。在C语言中，链表通常使用结构体来表示节点，每个节点包含数据和指向下 一个节点的指针。
栈
总结词
栈是一种后进先出（LIFO）的数据结构，它只允许在一端进行插入和删除操作。
THANKS
感谢观看
二分查找
01
02
03
时间复杂度
O(log n)，其中n是数据 结构中的元素数量。
适用场景
适用于数据量较大且数据 结构有序的情况。
实现方式
通过比较中间元素与目标 元素的大小，不断缩小查 找范围，直到找到目标元 素或查找范围为空。
哈希查找
01
时间复杂度
O(1)，在最理想的情况下。但在哈希冲突较多的情况下，时间复杂度可
数据结构在实际生活中的应用
数据结构不仅在计算机科学和软件开发中有广泛应用，在实际生活中也有着广泛的应用。
数据结构能够有效地处理和管理现实生活中的各种数据，如人口统计数据、交通流量数据、市场调查 数据等。通过合理地组织和存储这些数据，可以更好地进行数据分析、预测和决策，为人们的生活和 工作提供更好的服务。
详细描述
冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序 错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排 序完成。
冒泡排序
时间复杂度：O(n^2)，其中n是数组的长度。 空间复杂度：O(1)。
选择排序
总结词：每次从未排序的元 素中选出最小（或最大）的 一个元素，存放到排序序列 的起始位置。

由二进制换算关系可知: 20+ 21+ 22+…+ 2k-1 = 20, 因此二 叉树树中结点的最大数目为20。 性质3在任意二叉树中, 若叶子结点（即度为零的结点） 个数为n0, 度为1的结点个数为n1, 度为2的结点个数为n2, 那么 n0 = n2+1。 设n代表二叉树结点总数, 那么 n = n0 + n1 + n2 (6.1)
由于有n个结点的二叉树总边数为n-1条, 于是得
n-1=0* n0 +1* n1+2* n2
将式(6.1)代入式(6.2) n0= n2+1
(6.2)
有两种特殊形态的二叉树 , 它们是满二叉树和完全二叉树。 深度为k并且含有2k-1个结点的二叉树称为满二叉树, 这种树的
特点是每层上的结点数都是最大结点数, 如图6.4(a)所示。对满
图6.1是一棵由 11 个结点组成的树T。 其中A是根结点, 其 余结点分为三个互不相交的子集: T1 ={B,E,F}, T2 ={C,G}, T3
={D,H,I,J,K}。 T1、 T2 、 T3都是树根Ａ的子树, 这三棵子树的
根结点分别是B、 C、 D。每棵子树本身也是一棵树, 可继续划 分。 例如子树T3以D为根结点, 它的其余结点又可分为三个互
第6章树
6.1 树的基本概念和术语 6.2 二叉树
6.3
6.4
6.5 二叉树、 树和森林
6.6 树的应用
6.7 二叉树的建立和遍历C语言源程序示例
返回主目录
第 6章 树
6.1 树的基本概念和术语
6.1.1
树（tree）是由一个或多个结点组成的有限集合T。 其中: (1) 有一个特定的结点称为该树的根（root）结点; (2) 除根结点之外的其余结点可分为 m（m≥0）个互不相 交的有限集合T1, T2, …, Tm, 且其中每一个集合本身又是一棵树, 称之为根的子树（subtree）。 这是一个递归的定义, 即在定义中又用到了树这个术语。 它反应了树的固有特性。可以认为仅有一个根结点的树是最 小树, 树中结点较多时, 每个结点都是某一棵子树的根。