数据结构复习
2022-02-20 15:56:04 0 举报
随便发发嘿嘿嘿
作者其他创作
大纲/内容
按老师列出的要点逐个复习
复习要求
数据、数据元素、数据项之间的关系
数据结构：一类普通数据的表示及其相关操作（一组数据项的组织或结构）
数据类型是指一个类型以及定义在这个类型上的一组操作
ADT，是指基于一个逻辑类型的数据类型以及这个类型上的一组操作
数据结构是ADT的物理实现
抽象数据类型（abstract data type）
数据项
数据类型
数据结构的定义
数据结构的三要素
ADT定义了数据类型的逻辑形式
数据结构是实现数据类型的物理形式
数据项、抽象数据类型和数据结构的关系
数据结构的基本概念
算法在资源上的两个方面
可以估算出问题规模变大时，一种算法及实现它的程序的效率和开销
忽略系数，重点是增长率
定义
运行时间函数的每个项数都考虑
数据规模不大时
运行时间f的增长速度只和高次项有关，具有相同高度的次项的运行时间f增长速度是一致的
数据规模不断增大时
取决于增长率，也就是最高次项的增长速度
运行时间函数的差异性
算法效率评估
上限
下限
θ表示法
使用0，表明f(n)的增长率小于或者等于某个函数的增长率
使用Ω，表明f(n)的增长率大于或者等于某个函数的增长率
使用θ，表明f(n)的增长率等于某个函数的增长率
总结：
算法时间函数的几个术语
若f(n)在O(g(n))中，且g(n)在O(h(n))中，则f(n)在O(h(n))中
若f(n)在O(k*g(n))中，对于任意常数k>0成立，则f(n)在O(g(n))中
若f1(n)在O(g1(n))中，且f2(n)在O(g2(n))中，则f1(n)*f2(n)在O(g1(n)*g2(n))中
渐进分析化简四法则
时间函数的化简法则
渐进算法分析
如果某个算法的增长率上限（最差情况下）是f(n)，那么就说这种算法在“在集合O（f(n)）中”，或“在O（f(n)）中”
对非负函数T(n)，若存在两个正常数c和n0，对任意n>n0，有T(n)<=c*f(n)，则称T(n)在O（f(n)）中
大O标记法
读作“大欧米伽”或“欧米伽”
若存在两个正常数c和n0，对任意n>n0，有T(n)>=c*f(n)，则称T(n)在Ω（f(n)）中
定义
大Ω标记法
当上、下限相等时，我们用θ表示法，读作“西塔（Theta）”。
如果一种算法既在O(h(n))中，又在Ω(h(n))中，则称其为θ(h(n))
θ标记法
牺牲空间或者其他替代资源，通常都可以减少时间代价
基于磁盘的空间—时间权衡原则为：在磁盘上的存储开销越小，程序运行得越快
时空权衡原则
算法分析
线性表是由叫做元素的数据项组成的一种有限并且有序的序列。
“有序”：线性表中的每一个元素都有自己的位置
空表：线性表中不包含任何元素
第一个数据元素没有前驱，最后一个数据元素没有后继，其余元素有且仅有一个前驱和后继
表头：线性表的开始结点，表尾：线性表的结尾结点
线性表中包含的数据元素个数不是任意的
n个元素的线性表，其插入位置有（n+1）个，其删除位置有（n）个
线性表采用顺序存储，必须占用一片连续的存储空间
在一个长度为n的顺序表中删除第i个元素（0<=i<n）时，需要向前移动（n-i-1）个元素
某个线性表以顺序表形式实现，长度为n，现在按值查找元素，假设线性表中没有该值的概率为P，且要查找的值在线性表中等概率出现。则平均比较次数为：p*n+(1-p)*(n-1)/2
关于线性表的一些问题
线性表定义
线性表的ADT
允许在线性表中的任何位置插入、删除或者访问元素
list链表
只允许在线性表的表尾插入、删除或者访问元素
stack栈
只允许在线性表的一端插入元素，在线性表的另一端删除、插入、访问元素
queue队列
线性表的种类
元素之间是连续存放的（数组）——顺序表
元素之间是离散存放的（链表）——链表
线性表的实现方式
将已经存在的表置空
head.setNext(null); curr=tail=head;
例子（链表）
clear()
判断线性表是否为空
return head.next()==null;
例子(链表)
isempty()
求线性表中的元素个数（长度）并返回
int count=0;for(Link temp=head.next();temp!=null;temp=temp.next()) count++;return count;
例子
length()
读取并返回线性表中第i个数据元素的值
get(int i)
向线性表中当前光标位置插入值为it的数据元素
insert(Object it)
删除当前光标位置的数据元素
remove()
基本操作
线性表的逻辑结构和基本操作
线性表的顺序存储结构称为 顺序表
返回index位置处的数据元素
if (index>=0 && index<this.length) return (T) this.table[index]; return null;
代码
get(int index) 实现分析
将索引值为index的数据元素替换成data
if (index>=0 && index<this.length&& data!=null) {T old = (T)this.table[index]; this.table[index] = data; return old;} return null;
需要移动数组中的数据元素（在插入点后的元素向后移动），效率较低
在头部插入或者在中间插入
无需移动数组中的元素，效率高
在尾部插入
数组容量未达最大值
数组容量已达最大值
插入元素情况分析
与插入元素情况大致类似
remove(int index) 实现分析
根据数据查找下标index
public int indexOf(T data){if (data!=null) for (int i=0; i<this.length; i++) { if (this.table[i].equals(data)) return i;} return -1;}
indexOf(T data) 实现分析
基本操作的实现
顺序存储结构对线性表基本操作的实现
线性链表的存储结构是用若干个地址分散的存储单元存放数据元素的，逻辑上相邻的数据元素在物理位置上不一定相邻，因此每个存储单元中都会有一个地址指向域，这个地址指向域指明其后继元素的位置。
链表是由一系列叫做结点（node）的对象组成的。
存储数据元素
存储指向下一个结点的指针
每个结点都由两部分组成
实现原理
单链表结点类的定义
结点类的定义（Link类）
1
不带头结点链表
带头结点链表
代码实现
链式存储结构的实现（比如单向链表以及带头结点的链表）
tail=head=curr=new Link(null)
构造函数——setup
时间复杂性：θ（1）
插入元素——insert
删除元素——remove
光标位置的向前和向后移动--next、prev
时间复杂性： θ（n）
将光标位置变成当前元素位置——setpos
注重理解以下基本操作
带头节点的链表
链式存储结构对线性表基本操作的实现
线性表实现方法的比较
链表更适合插入、删除操作
选取不同存储结构的判断能力
栈是规定仅在一端进行插入或删除的线性表
栈称为“LIFO”线性表，意思是“后进先出”
称栈的可访问元素为栈顶（top）元素
元素插入栈称为压栈（push）
删除元素时称作出栈（pop）
查看栈顶元素但不删除（peek）
术语
ADT
push(object it)
peek()
pop()
基本操作
比较
题目
栈
队列queue也是一种受限的线性表（栈也是）
队列称为“FIFO”线性表，意思是“先进先出”
队列元素只能从队尾插入（称为入队操作，enqueue）
队列元素只能从队首删除（称为出队操作，dequeue）
ADT
enqueue(E it)
dequeue()
firstVaule()
栈与队列的共同点是：只允许在端点处插入和删除元素
队列
栈、队列的逻辑结构和基本操作
采用内部数组实现顺序栈
顺序栈
采用内部数组实现顺序队列
代码
初始化循环队列时
向循环队列中插入元素
删除元素
队列满
图解
改进为循环队列
顺序队列的优化
顺序队列
顺序存储结构对栈和队列基本操作的实现
采用不带头结点的单链表实现链式栈
代码
与顺序栈相比有一个明显的优点：通常不会出现栈满的情况
链式栈
使用含头指针front、尾指针rear的单链表实现链式队列
分析
例题
链式队列
链式存储结构对栈和队列基本操作的实现
循环队列分析
顺序存储结构对实现循环队列的具体要求
若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的
若一个过程直接或间接地调用自己，则称这个过程是递归的过程
定义
必须总要有某些基准情形，它无需递归就能解出
基准情形
对于那些需要递归求解的情形，每一次递归调用都必须要使状况朝一种基准情形推进
不断推进
假设所有递归调用都能运行
设计法则
在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作
合成效益法则
递归的四个法则
递归过程
定义是递归的
数据结构是递归的
问题的解法是递归的
例子
用到递归思想的三种情况
递归
递归工作栈
栈
1
实例理解
递归调用和栈之间的关系
1-1
1-2
一个较为简单的实现
平衡符号
2-1中缀表达式
2-2操作符的优先级和结合性
2-3后缀表达式
2-4后缀表达式的计算
2-5中缀表达式转后缀表达式
后缀表达式的计算
中缀表达式转中缀表达式
混合算术表达式的计算
栈的应用
思路
时间复杂度分析
面临的问题
桶排序
基数排序
队列的应用
栈和队列的经典应用
线性表（含栈和队列）
二叉树结合了以数组实现的有序线性表和以链表实现的线性表的优点
用于描述非线性结构的数据
二叉树（binary tree）由结点（node）的有限集合组成，这个集合或者为空，或者由一个根结点（root）以及两颗不相交的二叉树组成，这两颗子树分别称作这个根的左子树（left subtree）和右子树（right subtree）————二叉树的定义是一种递归定义
子结点、父结点、兄弟结点
这条路径的长度是k-1
如果有一条路径从结点R至结点M，那么R就成为M的祖先（ancestor），而M称为R的子孙（descendant）
所有的结点都是根节点的子孙，而根结点都是它们的祖先
如果一颗树的一串结点n1，n2，......，nk有如下关系：结点ni是n（i+1）的父结点（1<=i<k），就把n1，n2，......，nk称为一条由n1到nk的路径（path）
例图
结点的深度（depth）等于该结点在这棵树中的层数
左右子树均为空的结点称为叶结点（leaf）
至少有一颗非空子树的结点称为分支结点或者内部结点（internal node）
一棵树的高度等于最深结点的深度+1
层、深度、叶结点、分支结点
主要特性
每一个结点或者是一个分支结点，并恰有两个非空子结点；或者是叶结点
满二叉树（full binar tree）
从根结点每一层从左到右填充，一颗高度为d的完全二叉树除了d-1层意外，每一层都是满的
完全二叉树（complete binar tree）
满二叉树和完全二叉树之间没有必然的联系
平衡二叉树等
特殊二叉树
在二叉树的第i层上至多有2^i个结点（i>=0）
深度为K的二叉树至多有2^(k+1) -1个结点（k>=0）
对任何一颗二叉树，如果其叶结点数为n0，具有两颗子树的分支结点的个数为n2，那么 n0=n2+1
一颗非空二叉树的数目等于其结点数目加1
具有n个结点的完全二叉树的高度为ceil（log（n+1））
ceil是向上取整
性质6
性质
获得一个二叉树的根结点
获得二叉树中某个结点的父结点
获得二叉树中某个结点的左子树、右子树
向二叉树的某个结点插入左子树或者右子树
删除二叉树中某个结点的左子树或者右子树
遍历操作，按某个次序依次访问二叉树中各个结点，并使每个结点只被访问一次
消除整颗二叉树
结点node的ADT
二叉树结点的ADT
使用指针实现
二叉树代码实现
二叉树
子集Ti（1<=i<=n）称为树T的子树（subtree）
结点的出度（out degree）定义为该结点的子结点的数目
定义及术语
最左子结点 右兄弟
树结点ADT
每个结点只保存一个指针域指向其父结点
等价类问题的处理（并查集）
适用范围
对找到一个结点的最左子结点或右侧兄弟结点这样的重要操作是不够的
缺点
数组实现形式
链表实现形式
实现方式
父指针表示法
每个结点储存一个线性表的指针，该线性表用来储存该结点的所有子结点
优：寻找某个结点的子结点非常方便
缺：寻找某个结点的兄弟结点则比较困难
优缺点
数组实现方式
1
2
链表实现方式
子结点表示法
每个结点都存储结点的值、最左子结点的位置和右侧兄弟结点的位置
ADT中规定的基本操作都可以较容易的实现
优点
实现方式
左子结点/右兄弟结点表示法
树的实现
树
零个或多个树的一个有序集合
定义及术语
森林
二叉树、树和森林的定义和异同点
遍历：按某条搜索路径寻访二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次
按照一定顺序访问二叉树的结点，称为一次周游或遍历（traversal）
对每个结点都进行一次访问并列出，称为二叉树的枚举
遍历的定义
breadthFirst--广度优先
层序遍历（广度优先遍历）
前序周游（preorder traversal）
先根序遍历、前序遍历（先根，再左，最后右）
中序周游（inorder traversal）
中根序遍历、中序遍历（先左，再根，最后右）
后序周游（postorder traversal）
后根序遍历、后序遍历（先左，再右，最后根）
外框
四种遍历
使用遍历
判断是否是叶结点 不遗漏不冗余
统计叶结点的个数
在此代码中visit为height+1那一句
Demo1
Demo2
相关操作
二叉树的遍历用递归思想编写是顺理成章的
递归的实现是需要借助栈数据结构完成的，不管是应用记的，还是系统级的
利用栈改造二叉树的三种递归遍历算法（自己思考）
总结
二叉树的四种遍历并通过遍历完成相关操作
数组
数据区--结点中存储元素
两个指向子结点的指针
每个结点至少得维护三个数据
二叉树结点类BinNodePtr
链表
二叉树的实现方式
在大多数情况下，使用数组表示树效率是很低的，不满的节点和删除掉的节点都会在数组中留下 洞，浪费存储空间。更坏的是，删除节点如果要移动子树的话，子树中的每个节点都要移到数组中新的 位置，这是很费时的。
差异
二叉树采用顺序存储和链式存储的差异性
两个结点之间路径上的分支数
路径长度
各叶结点到根结点的路径长度之和
树的外部路径长度
各非叶结点到根结点的路径长度之和
树的内部路径长度
树中所有叶子结点的带权路径长度之和
树的带权路径长度
一些概念
Huffman树：是一类带权（外部）路径【weighted path length】长度最短的树
“权”大的叶结点深度小，它相对总路径长度的花费最小，因此，其他的叶结点如果“权”小，就被推到树的较深处
基本概念
权重为字母出现的频率
结果 40<45 优化成功
特性
物理意义
Huffman编码
从下到上构造二叉树
采用的是贪心算法
3
4
构造Huffman树
平均比较次数比简单的if-else要少
Demo
应用
Huffman树（最优二叉树）
提供了查找元素花费logn的时间能力
使用线性表查找元素平均需要比较5000次
使用二叉检索树查找元素平均则只需要14次
10000个数据
提供了插入和删除元素花费logn的时间能力
功能
二叉检索树的任何一个结点，设其值为L，则该结点左子树中任意一个结点的值都小于K；右子树中任意一个结点的值都大于或等于K
关键字key
Elem元素
应该具备的操作能力
二叉检索树ADT
在BST中查找一个元素的算法
最左叶结点
查找最小值
最右叶结点
查找最大值
查找最值
删除最小值
删除最大值
删除最值
先寻找该插入的叶结点或者分支结点
插入的位置应该是所属位置父结点的空子结点
思路
代码实现
Demo
插入一个元素
真删除
BST可以用左子树的最大或右子树的最小来替代删除
替代删除
删除
直接将给结点置于null——真删除
删除的元素是叶结点
替代删除
删除的元素是分支结点
删除一个元素
平衡二叉树的操作代价为θ（logn）
非平衡二叉树最差的代价为θ（n）
搜索代价
插入、删除的代价与搜索代价类同
周游一个二叉树的代价为θ（n）
使一个二叉树保持平衡才能真正发挥二叉树的作用
各种操作的时间代价
算法
二叉检索树（Binary Search Tree，即BST）
按照重要性和优先级来组织的对象称为优先队列
是一种ADT
在多用户的环境中，操作系统调度程序必须决定在若干进程中进行哪个进程
发送到打印机中的若干个作业可能在某些时候并不想按照先来先打印的方式运行
应用
增加一个带有重要级别的元素，插入到队列中的位置并不在意
插入
队列中的重要级别最高的那个元素
删除
获得头元素
操作
O（1）——在表尾插入
插入元素：在线性表中的任何一个位置都可以
O（n）
删除元素：遍历线性表，找到线性表中优先级别最高的那个元素并删除
使用没有排序的一般线性表
插入元素：在线性表中按照重要级别扫描到合适的位置处，任何将该元素插入
O（1）
删除元素：在线性表中直接删除头位置元素即可
使用排序的线性表
O（logn）
插入元素：在二叉树平衡的情况下插入元素
删除元素：在二叉树平衡的情况下删除元素
优先队列只需要获得重要级别最高的元素，而不需要查找某个特定关键字的元素
优先队列的本身的特点并不需要二叉查找树的一些基本操作
使用二叉查找树
使用堆
优先队列（priority queue）
从结构性质看，堆是一颗完全二叉树，故可以用数组代替链表形式来完成之
对根元素的访问是最快的获取速度
重要级别最高的元素是根元素
在堆中，对于每一个结点X，X的父亲的重要界别高于（或等于）X的重要级别，除了根结点之外（该结点没有父亲）
根据二叉树的递归定义，我们考虑任意子树也应该是堆，那么应该有下面的结论
从堆序性质看，堆能够快速的（O（））找出重要级别最高的元素
任意一个结点的关键字值都大于或者等于其任意一个子结点存储的值
最大值堆
任意一个结点的关键字值都小于或者等于其任意一个子结点存储的值
最小值堆
堆的种类
时间代价是O(nlogn)
可以按照一个元素一个元素的方式插入
时间代价是O(n)
详情移步课本P107
创建堆
插入元素
删除元素
向堆中插入元素
从已知数组构建堆
最大值堆对应的上浮操作，确保满足最大值堆的结构
删除最大元素
堆的实现
堆
使用堆实现优先队列
堆与优先队列
二叉检索树、Huffman编码以及堆的实现
树、森林采用的各种存储方式的差异性
一个树决不会为空，即它至少有一个结点，并且树中的每个结点都会有0、1、2、...、n个子结点
一个森林可以由0、1、2、...、n个树组成，一个树的任何结点下面的直接子树又可以形成一个森林
一颗二叉树可以是空的，它的每个结点可以由0、1或2个子结点，同时我们还要区分“左”子结点和“右”子结点
回顾相关概念
实例
任何二叉树都对应一个唯一的森林
结论
如果n=0，则B（F）为空
课堂基础知识
在所有兄弟结点之间加一条线
对每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线
树转换成二叉树
加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来
去线。删除原二叉树中所有结点与其右孩子结点的连线
二叉树转换成树
树与二叉树
将森林中的每棵树变为二叉树
因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树
森林转换成二叉树
从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止
将每棵分离后的二叉树转换为树
二叉树转换成森林
二叉树与森林
树和森林与二叉树的转换
一般不使用树的中序遍历
概念
先序遍历
后序遍历
树的遍历
将树的根去掉之后，就成为了森林，所以森林和树的遍历本质是相同的
给定森林F，若F=∅，则遍历结束
遍历定义中术语的一般性描述
先根遍历
后根遍历
森林的深度优先遍历
树和森林的广度优先遍历不等同于其转换为对应的二叉树的任何遍历
树和森林的广度优先遍历与二叉树的层次序遍历类似，它是非递归算法，需要借用一个队列来实现。
森林的广度优先遍历
森林的遍历
树、森林在遍历上和二叉树的不同及相关性
是由一组互不相交的集合组成的一个集合结构，并在此集合上定义了运算Union和Find
集合之间是不相交的
一开始，每个集合包含一个元素
每一个要处理的元素都仅仅属于一个集合
每一个集合都有一个名称，这个名称可以用该集合中的任何一个元素名称
自反性：aRa
对称性:aRb 当且仅当bRa
传递性：若aRb且bRc则aRc
若对于每一个元素（a，b），a和b之间满足如下三种关系，则称a和b之间是等价关系
电器连通性
城市之间的连通性
主要用来解决等价关系问题
用途
返回包含给定元素的集合名字
不同于查找方式中的返回结果
Find（elementname）
生成一个新的集合，该集合是elementname1所属的集合set1和elementname2所属的集合set2的并集
Union（elementname1，elementname2）
需要支持的两个操作
每个元素都隶属于一个集合，该集合的名字就是该元素在数组中的下标
set【i】=i；
初始状态
对每一个k，如果set【k】==下标为j的元素所属的集合名称，则设置set【k】=下标为i的元素所属的集合名称
Union（i，j）
返回set【i】即可
Find（i）
由一个具有n个元素组成的数组储存各个不相交的集合
全部
例图
使用数组
不相交集可以表示为一个森林
森林中的每棵树表示为一个集合
树中的每个结点的存放顺序没有任何的约束，所以可以采用树的父指针表示法描述树
2
结点类定义
Find和Union
重量平衡原则
在教材上去看
路径压缩
重要权衡平衡原则及路径压缩
使用树
实现
不相交集ADT（并查集）
在做“合并”操作之前先判别子集中所含成员的数目，然后令含成员少的子集的树根指向含成员多的子集的根，称作“重量权衡合并规则”（weightedunion rule）。把小树合并到大树中去，可以把树的整体深度限制在Ｏ(logn)，每次Find操作只需要O(logn)时间
有利于减少减小树的深度
在合并前加一个if-else语句即可
重量权衡合并原则
首先要查找R，然后顺着由X到R的路径把每个结点的父指针域均设置为指向R
当查找一个结点X的根结点时可以采用路径压缩。
用循环实现
1设终止条件及其操作，如果访问的节点是根节点，则直接返回就好了
2非终止条件时应该执行的传递操作，find(parent[p])使得递归往根节点深入下去
用递归实现
并查集的意义，两个基本操作的实现，重量权衡合并原则和路径压缩
二叉树、树和森林
例图
种类
子图的定义
与顶点相关的概念
与路径（path）相关的概念
连通图
连通分量
无向图
有向图
连通图及连通分量
无环图
图的定义及术语
相关操作
图ADT
时间复杂性
获得第一边、判断是否是边
返回顶点下一个边
具体操作
相邻矩阵
有权值
邻接表
两种方式
图的实现
图的一些概念
邻接矩阵
图采用邻接矩阵和邻接表进行存储的差异性
基于图的拓扑结构，以特定的顺序一次访问图中各顶点，从概念上讲与树的遍历类似
从图中的某个顶点作为出发的起点，然后试探性的访问其余顶点
从起点出发可能到达不了所有其他顶点
可能会陷入死循环
可能遇到的问题
解决问题思路
基本思想
图的遍历
类似于树的先序遍历，是树的先序遍历的推广
给出指定两个顶点之间的路径
判断图是否有回路
判断图是否有连通图，如果不连通，则有几个连通分量
DFS是对图的很多问题处理的基础
假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中某个顶点v出发
访问这个v顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相连的顶点都被访问到
如果此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止
遍历过程
时间复杂性
深度优先搜索（Depth First Search，DFS）
类似于树的层序遍历
单源最短路径的dijsktrasuanfa
最小支撑树的prim算法
广泛应用于图的算法中
给出指定两个顶点之间的“最短”路径
判断图是否是连通图，如果不连通，则有几个连通分量
可以用于对图的基本操作
假设从图中某个顶点v出发，在访问了v之后，依次访问v的各个未曾访问过的邻接点，并保证先被访问的顶点的邻接点“要先于”后被访问的邻接点的访问，直至图中所有已被访问的顶点的邻接点都被访问到
若此时图中还有未被访问的顶点，则任选其中之一作为起点，重新开始上述过程，直至图中所有顶点都被访问到
遍历过程
保证“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问，也就是先到先被访问，这正好是队列的特点，因此可以使用队列来实现
访问特征
实例
DFS可以在处理某个结点的所有邻接几点之前接受访问，也可以在处理玩某个结点的所有邻接结点之后接受访问
BFS则只有在结点入队时（或者出队时）接受访问
在访问结点的时机方面：
DFS和BFS的比较
广度优先遍历和深度优先遍历
一个G中所有顶点的一种线性排序
对于G中的任意顶点i和j，如果i是j的前驱，那么在这个线性顺序中i一定在j之前
子工程的完成意味着整个工程的完成
子工程之间在进行的时间上有着一定的相互制约关系
一项工程往往可以分解为一些具有相对独立性的子工程，通常称这些子工程为“活动”
可用一个有向图表示子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为活动在顶点上的网络，简称活动顶点网络，或AOV（Activity On Vertex）网
AOV网在很多方面有应用
是一个有向图，该图中的顶点表示活动，图中的弧表示活动之间的优先关系
顶点i是顶点j的前驱当且仅当从顶点i有一条有向路径到达顶点j，顶点j也称为顶点i的后继
前驱（predecessor）、后继（successor）
对任意顶点i，j，k，如果i是j的前驱并且j是k的前驱，那么i一定也是k的前驱
对任意顶点i，i是i的前驱永远为假
活动之间的优先关系满足传递关系、非自反关系
否则意味着某个活动的开始是以这个活动的结束为先决条件的
不允许有环出现
AOV网的定义
AOV网
扫描整个图，计算每个顶点的入度
让入度为0的顶点进入队列
如果队列不为空，从队列中删除一个顶点并输出，同时将其所有相邻顶点的入度数-1，当某个相邻的顶点的入度数为0时，则将整个顶点插入到队列中
重复上述步骤直到队列为空
如果还有顶点没有输出，那么表明这个图有环，不符合AOV网的定义
充分理解
将上述过程用图示化
通过BFS获得一个拓扑排序
初始化部分
拓扑排序（topological sort）
使用广度优先搜素就可以解决
对于无权图来说，路径的代价就是指路径的长度
图中拥有的权值都一样
图中拥有权值全部为正的边
图中拥有权值为负的边
图中拥有正权值的环——（无意义）
图中拥有负权值的环——（无意义）
对于有权图来说，路径的代价就是指这个路径所经过的所有边上的权重之和
路径的代价
给定两个顶点A和B，从A到B的一条有向简单路径，并且此路径有以下属性：即不存在另外一条这样的路径且有更小的代价
最短路径
相关概念
源点——汇点最短路径（Source Sink Shorest Path）
单源最短路径（Single Source Shortest Path）
全源最短路径（all-pairs shortest-paths）
三种类型
不带权值的图的最短路径
使用Dijkstra算法
单源最短路径（Single Source Shortest Path）
使用|V|次dijkstra算法
使用FLoyd算法
每对顶点间的最短路径（all-pairs shortest-paths）
带有权值（正值）的图的最短路径
Bellman-ford算法
单源最短路径
Floyrd算法
全源最短路径
带有负权值（但不含有负权值环）的图的最短路径
解决方法
具体示例
利用BFS搜素思想，只不过将顶点从一个集合拉到另一个集合里的规则不同
按路径代价递增的次序产生最短路径
设集合S存放已经求得的最短路径的终点，从V-S中选择一个顶点t，t是目前所有还没有求得最短路径顶点中与V0之间的距离最短的顶点；将t加入到S中，并且更新V0到V-S中所有能够到达顶点之间的距离；如此反复，直到V-S中没有可以从V0到达的顶点为止
算法思想
图例
当i=v0时，distance【i】=0
1.设置一个一维数组distance，该数组记录从源点v0到任意其他顶点vi的最短路径估计
2.将v0加入到集合中
distance【j】=min{distance【k】| vk∈V-S}
3.从V-S中选择顶点vj，将该顶点加入到集合S中，vj满足如下关系
distance【k】=min{distance【k】，distance【j】+wjk}
4.对每一个V-S中的顶点vk，修改distance【k】
5.重复步骤3、4，直到V-S中没有可以能够加入到S中的顶点为止
算法步骤
Dijsktra算法
最短路径问题
这个子集中所有边的权之和为所有子集中最小的
子集中的边能够保证图是连通的
给定一个连通无向图G，且它的每条边均有相应的长度或权值，则MST是一个包括G中所有顶点及其边子集的图，边的子集满足下列条件
一个图及其MST
示例图
一个图的MST可能不唯一
MST是一颗有|V|-1条边的自由树
定义
通信网络、运输网络
weigh（f）<=weight（e）
环性质
分割性质
Prim算法
将顶点集分为|V|个等价类，每个等价类包括一个顶点
将图中的所有边按权值的大小顺序处理
在处理某条边时，如果这条边所连接到的顶点不在一个等价类中，则将这条边添加到MST中，并把两个等价类合并为一个
反复执行2、3，直到剩下一个等价类
Kruskal算法
最小支撑树（Minimum-cost Spanning Tree）
最小支撑树（Prim算法、Kruskal算法）、最短路径（Dijkstra算法）、拓扑排序的实现
图
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）
查找表只供查找，而不进行元素的插入和删除
静态查找表
查找表不仅提供元素的查找，而且还可以进行元素的插入和删除
动态查找表
查找的分类
有序数组
普通数组
单链表
平衡二叉树
insert——O(1)
Search——O(1)
Delete——O(1)
m*10^n
空间消耗严重
关键字的范围和真实关键字数量差距很大
存在的缺陷
直接寻址表（direct address table or direct access table）
散列
查找的实现(数据结构)
查找的定义
指找到表中已有表项的平均探查次数，是找到表中各个已有表项的探查次数的平均值
搜索成功的平均搜索长度ASLsucc
指在表中搜索不到待查表项，但找到插入位置的平均探查次数，它是表中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值
搜索不成功的平均搜索长度ASLunsucc
性能分析
对查找算法进行衡量的指标
顺序查找法和折半查找法的异同
是对直接寻址发的一种改进
将直接寻址中的关键字通过一个“黑盒子”，把其值压缩到另外一个范围中的某个地址值
平均情形下获得常数级别的查找数据和储存数据的时间
这是一个技术，通过它
接收待查找的关键字
这个索引接收储存关键字所对应纪录数组中的储存位置，称这个数组为Hash Table，称Hash Function返回的索引值为Hash Index
返回一个数组中的索引
Hash Function
该函数能够待查找的关键字映射到互不相同的Hash Table中的Hash Index上
基本上没有这样的函数存在
Perfect Hash Function
与Hashing有关的术语
哈希表是一个数组
哈希函数返回的是哈希表的索引号
最自然的方式就是通过mod运算
将不是整数类型的关键字通过各种方式转换成整数类型，转换后的结果我们称其为hash code
将哈希码压缩到哈希表数组的索引范围内
如果关键字不是整数类型，那么怎么进行mod运算呢？
直接定址法
H（key）=（last 7 digits of key）% n
假设关键字集合中的每个关键字都是由s位数字组成（k1，k2，。。。kn），分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址
比如：出生年月日
能预先估计出全体关键字的每一位上各种数字出现的频度
关键字中的某几部分总是相等的
仅限于
数字分析法
H（key）=（middle N digits of key^2）% n
若关键字的每一位都有某些数字重复出现频率很高的现象，则先求关键字的平方值，以通过“平方”扩大差别，同时平方值的中间几位受到整个关键字中各位的影响
平方取中法
折叠法
随机数法
保留余数法
方法
如何压缩哈希码
如何通过哈希函数将待查关键字和哈希表的索引号进行映射呢？
采用何种构造哈希函数的方法取决于建表的关键字集合的情况（包括关键字的范围和形态），总的原则是使产生冲突的可能性降到尽可能的小
要计算容易和速度快
确定性：对于同一个关键码，不管什么时候计算出来的hash index都应该是确定的
散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有m个地址时，其值域必须在0到m-1之间
Hash函数构建的小结
哈希表和哈希函数
key1<>key2，但是H（key1）==H（key2）
由于哈希函数的作用是将关键字压缩为有限的数值范围（也就是哈希表的索引范围），所以就会造成冲突
什么叫Hash冲突
定义：在哈希表中重新找一个位置
如果在哈希表的第k个位置发生了冲突，那么就依次试探其后继位置k+1，k+2，......
会产生基本聚集
若把关键码为Broad的表项真正删除，把它所在位置的info域置为Empty，以后再搜索关键码为Blum和Alton的表项时就差不下去，会错误地判断表中没有关键码为Blum和Alton的表项
不能真正删除表中已有表项，删除表项会影响其他表项的搜索
逻辑删除的副作用是：在执行多次删除后，表面上看起来散列表很慢，实际上有许多位置没有利用
若想删除一个表项，只能给它做一个删除标记deleted进行逻辑删除，不能把它真正删除
线性探查方法容易产生“堆积”，不同探查序列的关键码占据可用的空桶，为寻找某一关键码需要经历不同的探查序列，导致搜索时间增加
需要注意的问题
线性探查（linear probing）
删除元素的问题如同线性探查一样，不能真删除元素，而应该打标记
如果有两个关键字值有相同的基位置，那么它们就会有同样的探查序列，这个问题称为二次聚集
平方探查（quadratic probing）
当通过一个哈希函数得到的哈希索引发生冲突之后，获得的下一个哈希索引应该是第一个哈希索引加上通过第二个哈希函数求得的哈希索引之和
有别于第一个哈希函数
所求的值也要依赖于关键字
不能返回0值
对第二个哈希函数的要求
避免了基本聚集和二次聚集
双散列探查（double hashing probing）
怎么实现
开地址法（Open Addressing）
我们把能够代表多个元素的位置形象的称为桶
我们称同一子集中的关键码互为同义词
桶可以表示为线性表、有序线性表等
改变哈希表的结构，使哈希表中的每一个位置上不再只容纳一个元素，而是可以容纳多个
开散列法（Open Hashing）
方式
怎么解决哈希冲突
完美的哈希函数较为少见，冲突的发生是不可避免的
装载因子
为了能够度量哈希的效率，我们需要借用一个称为Load Factor的印子
开地址法的代价
开散列的代价
对哈希的效率衡量
Hashing（散列）
散列技术
查找
排序问题：给定一组记录r1，r2，......，rn，其关键码分别为k1，k2，......，kn，将这些记录排成顺序为rs1，rs2，......，rsn的一个序列S，满足条件ks1<=ks2<=......<=ksn。
换句话说，排序就是要重排一组记录，使其关键码域的值具有不减的顺序
排序的一般性定义
稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
稳定性
基数排序、直接插入排序、冒泡排序、归并排序
稳定性算法
桶排序、二分插入排序、希尔排序、快速排序、简单选择排序、堆排序
不稳定性算法
一些排序算法的稳定性
排序的稳定性
直接插入排序
冒泡排序
简单选择排序
原理
快速排序
堆排序
归并排序
各种排序算法
根据应用需求选择合适的排序算法
排序
数据结构复习
0 条评论
回复 删除
下一页
