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