湘潭大学 数据结构 课件 ppt Ch05 Hashing_图文.ppt.

Leftist Trees(左高树)
▪ 堆结构是一种隐式数据结构，用完全二叉树表 示的堆在数组中是隐式存贮的。由于没有存贮 结构信息，这种描述方法空间利用率很高。
▪ 尽管堆结构的时间和空间效率都很高，但它不 适合于所有优先队列的应用，尤其是当需要合 并两个优先队列或多个长度不同的队列时。因 此需要借助于其他数据结构来实现这类应用， 左高树就能满足这种要求。
if(!root) throw OutOfBounds(); x=root->data;//最大元素 HBLTNode<T> *L=root->LeftChild; HBLTNode<T> *R=root->RightChild; delete root; root=L; Meld(root,R); return *this; }
▪ 例-CPU调度
优先队列
▪ 优先队列是0个或多个元素的集合，每个元素 都有一个优先权或值。
▪ 对优先队列执行的操作有：
• 查找 • 插入一个新元素 • 删除
优先队列的线性表描述
▪ 描述最大优先队列最简单的方法是采用无序线 性表。
▪ 假设有一个具有n个元素的优先队列，插入操作 可以十分容易地在表的右端末尾执行，插入所 需时间为Θ(1)。删除操作时必须查找优先权最 大的元素，即在未排序的n个元素中查找具有最 大优先权的元素，所以删除操作所需时间为 Θ(n)。
优先队列的线性表描述
▪ 如果利用链表，插入操作在链头执行，时间为 Θ(1)，而每个删除操作所需时间为Θ(n)。
优先队列的线性表描述
▪ 另一种描述方法是采用有序线性表，当使用公 式化描述时元素按递增次序排列，使用链表时 则按递减次序排列，这两种描述方法的删除时 间均为Θ(1)，插入操作所需时间为Θ(n)。

11
10.1.4 信息系统安全评价标准
3.《计算机信息系统安全保护等级划分准则》 我国也于1999年制定了“计算机信息系统安全保护等级划
分准则”这一国家标准。该标准将计算机系统的安全保护 能力分为：用户自主保护级、系统审计保护级、安全标记 保护级、结构化保护级和访问验证保护级这五个等级。 为了指导设计者设计和实现该标准中每一个安全保护等级 的操作系统要求，我国于2006年又制定了“信息安全技 术——操作系统安全技术要求（GB/T 20272-2006）”。
B级：B级中有三个子级别。B1级：即标志安全保护。B2级：又 叫做结构保护，要求计算机系统中所有的对象都加标签，而且 给设备分配单个或多个安全级别。B3级：或称为安全区域保护。 它使用安装硬件的方式来加强安全区域保护。
A级：A级或验证设计是当前的最高级别，包括了一个严格的设 计，控制和验证过程。
计算机的内部安全指的是计算机信息在存储介质上的安全， 包括计算机软件保护、软件安全、数据安全等多方面。
7
10.1.3 计算机威胁的类型
目前常见的几种主要威胁类型如下：
假冒用户身份：攻击者伪装成一个合法用户，利用安全体制所允 许的操作去破坏系统安全。
截取数据：未经核准的人通过非正当的途径截取网络中的文件和 数据，从而造成网络信息泄露。
9
10.1.4 信息系统安全评价标准
D级：D级是最低的安全保护等级。拥有这个级别的操作系统就 像一个门户大开的房子，任何人可以自由进出，是完全不可信 的。
C级：C级有两个安全子级别。C1级：又称选择性安全保护系统， 它描述了一种典型的用在Unix系统上的安全级别。C2级：除了 C1包含的特征外，C2级别还包含有访问控制环境。
安全管理包括各种安全管理的政策和机制； 逻辑安全是指系统中的信息资源的安全，包括数据机密性、

13
图的定义
路径长度： 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。
A
从A到F长度为 3 的路径
B
E {A,B,C,F}
CF
精选ppt
14
图的定义
连通图与连通分量：
在无向图中, 若从顶点v1到顶点v2有路径, 则称顶 点v1与v2是连通的。
如果图中任意一对顶点都是连通的, 则称此图是连 通图。
构造器方法重新构建了顶点数组和在常量 NUMVERTICES中指定数值的邻接矩阵。
既然数组是基于零的，所以数据成员 numVerts存储着 顶点列表内当前的数量以便于把列表初始设置为 0。
AddVertex方法会为顶点标签取走一个字符串参数，实 例化一个新的 Vertex对象，并且把它添加到顶点数组 内。
精选ppt
22
8.2 图的存储表示
精选ppt
23
邻接矩阵(Adjacency Matrix)
在图的邻接矩阵表示中，有一个记录各个顶点 信息的顶点表，还有一个表示各个顶点之间关 系的邻接矩阵。
设图 A = (V, E)是一个有 n 个顶点的图, 图的邻 接矩阵是一个二维数组 A.edge[n][n]，
(vi, vp1)、(vp1, vp2)、...、(vpm, vj) 应是属于E的边。
精选ppt
8
图的定义
路径的长度：
从路径中第一个顶点到最后一个顶点的边 的数量。
讨论的图对象的限制 : (1) 自身环 不讨论.
0
1
(2) 与两个特定顶点相关联的边不
能多于一条，多重图也不讨论。
1
0 2
精选ppt
9
图中，边必须是不同的。

例如, 假设Tp1 ( N ) = 106N ， Tp2 ( N ) = N2. 即使看起来( N2 ) 比( N )增长得更快,但当N < 106, P2仍然比P1快.
复杂度的渐进表示法
常用函数增长表
输入规模n 8 1 3 8 24 64 512
函数 1 log2 n n n log2 n n2 n3
Note: 1. 将常数或低阶项放进大O是非常不好的习惯——低阶项一
般被忽略，常数也可以丢弃掉（要求的精度是很低的）；
2. 能够通过计算极限limf(N)/g(N)来确定两个函数的相对增长 率; 3. 不要说成f(N)<=O(g(N))，因为定义已经隐含有不等式了。
Note: 当我们比较两个程序的复杂度时，确保N足够大。
结论对 N 2k 程序在教材 同样正确 p.40
应用实例：最大子列和问题
算法 4
“在线”算法
int MaxSubsequenceSum( const int A[ ], int N ) { 该算法的核心思想是基于下面的事实： int ThisSum, MaxSum, j; /* 1*/ ThisSum = MaxSum = 0; 1 3 3 2 2 4 4 6 1 6 1 /* 2*/ for ( j = 0; j < N; j++ ) { 如果整数序列 {a1, a2 , …, /* 3*/ ThisSum += A[ j ]; an}的最大和子列是 {ai, ai+1, …, aj} ， l 那么必定有 对任意 /* 4*/ if ( ThisSum >0 MaxSum ) i ≤ l ≤ j 都成立。 a . k i k /* 5*/ MaxSum = ThisSum; /* 6*/ else if ( ThisSum < 0 ) 因此，一旦发现当前子列和为负，则可以重新开始考察一个新 /* 7*/ ThisSum = 0; 的子列。 } /* end for-j */ -2 4 1 -6 3 -1 5 /* 8*/ return MaxSum; }

三叉链存储
.
Date:May 30, 2020
4.8 二叉树的遍历
IT Education & Training
• 遍历是指按某条搜索路线遍访每个结点且不重复（又 称周游），遍历是树结构插入、删除、修改、查找和 排序运算的前提，是二叉树一切运算的基础和核心。
• 牢记一种约定，对每个结点的查看都是“先左后右”。
例子中的数学模型正是数据结构要讨论的问题。
.
Date:May 30, 2020
1.2 定义
IT Education & Training
•数据结构是一门讨论"描述现实世界实体的数学模型 及其上的操作在计算机中如何表示和实现"的学科。
a. 在解决问题时可能遇到的典型的逻辑结构（数据结构） b. 逻辑结构的存储映象（存储实现） c. 数据结构的相关操作及其实现。(算法)
•二叉树由一个根结点加上两棵分别称为左子树和右子 树的互不相交的树组成：
–每个结点最多只有两棵子树（不存在度大于2的结点） –左子树和右子树次序不能颠倒（有序树）
.
Date:May 30, 2020
4.6 树转化为二叉树
IT Education & Training
•左孩子右兄弟表示法可以将一颗多叉树转化为一颗二
• 数据结构和算法的关系：数据结构是专门研究 数据的存储问题，而对存储后的数据进行相应 的操作就是算法。
.
Date:May 30, 2020
1.5 算法效率的度量
IT Education & Training
• 我们通过大O表示法来表示算法的效率：时 间复杂度、空间复杂度。规则如下：
（1）只关注最高次项，常数项和次要项忽略； （2）时间复杂度是指最坏时间复杂度； （3）只有常数项记做1。

二分查找
二分查找法
将有序数据集分成两个部分，每次取中间位置的值与目标值进行比较，根据比 较结果缩小查找范围，直到找到目标值或确定目标值不存在。
优缺点
查找速度快，但要求数据集必须是有序的。
哈希查找
哈希表
利用哈希函数将数据元素映射到内存中的地址，实现数据的 快速查找。
优缺点
查找速度快，但需要解决哈希冲突问题，并可能存在哈希表 过大或过小的问题。
。
数据结构的基本概念
数据结构的基本概念包括：数据、数据 元素、数据类型、数据结构等。
数据结构是指数据的组织形式，即数据 元素之间的相互关系。
数据类型是指一组具有相同特征和操作 的数据对象（如整数、实数、字符串等 ）。
数据是信息的载体，是描述客观事物的 符号记录。
数据元素是数据的基本单位，一个数据 元素可以由若干个数据项组成。
稳定排序
归并排序是一种稳定的排序算法，即相等的元素在排序后 保持其原有的顺序。
非递归算法
归并排序是一种非递归算法，即通过迭代方式实现算法过 程。
需要额外的空间
归并排序需要额外的空间来存储中间结果和临时变量。
查找算法
06
线性查找
顺序查找
逐一比对数据元素，直到找到目 标值或遍历完整个数据集。
优缺点
简单易懂，但效率较低，适用于 数据量较小的情况。
拓扑排序的应用
拓扑排序是一种对有向无环图进行排序的算法， 它按照拓扑关系将图的节点排列成一个线性序列 。
有向无环图是一种没有环路的有向图，拓扑排序 可以有效地解决有向无环图的排序问题。
拓扑排序的应用非常广泛，包括确定任务的执行 顺序、确定事件的发生顺序等。
拓扑排序的基本思路是从有向无环图的任一节点 开始，删除该节点，并记录下该节点的所有后继 节点的编号，然后按编号从小到大的顺序重复以 上步骤。