小白专场：堆中的路径-C语言实现
堆中的路径
-
网络异常，图片无法展示|
- 5 3的意思是给你5个数据构成一个最小堆进行3次查询。第二行就是要插入的五个数据。5 4 3代表下标
堆的表示及其操作(堆是一种按一定顺序组织的完全二叉树)
#define MAXN 1001
#define MINH -10001
intH[MAXN],size;//由于堆在存储的时候是把根结点放在数组下标为1的地方，也就是说0是空缺的
//这样子按照一层层顺序逐个往数组后面存放，使得堆中的任何一个元素可以很容易的找到他的父节点在哪里，左右儿子在哪里
//整数size表示当前堆大小
voidCreate()//堆的初始化，就是建立一个空堆(size设置为0)
{
size=0;
H[0] =MINH;//设置岗哨
}
//插入操作
voidInsert(intX)
{
//将X插入H。这里省略检查堆是否已满的代码
inti;
for(i=++size;H[i/2]>X;i/=2)
H[i] =H[i/2];//i挪到父节点(i/2)的位置
H[i] =X;
}
主程序
intmain()
{
1.读入n和m
2.根据输入序列建堆
3.对m个要求：打印到根的路径
return0;
}
//具体实现程序
intmain()
{
intn,m,x,i,j;
scanf("%d%d",&n,&m);
Create();//堆初始化
for(i=0;i<n; i++ ) {//以逐个插入方式建堆
scanf("%d",&x);
Insert(x);//利用Insert函数插到堆中
}
//m个查询
for(i=0;i<m;i++){
scanf("%d",&j);
printf("d",H[j]);
while(j<1){//沿根方向输出各结点(也就是说把他的祖先全部打印出来了)当j>1是代表还没有到根的时候，根的位置是1，这时候j/2就代表了他父节点的位置
j/=2;
printf("%d",H[j]);
}
printf("\n");
}
return0;
}
小白专场[陈越]：File Transfer (是一道经典的并查集的应用题)-C语言实现
小白-FT.1 集合的简化表示
集合的表示方法
typedefstruct {
ElementTypeData;
intParent;
}SetType;
查找Find函数
intFind(SetTypeS[],ElementTypeX)
{
inti;
for(i=0; i<MaxSize&&S[i].Data!=X; i++);//找到X在集合中是第几个元素，这个时间复杂度是O(N2)这个数量级，可以有更好的方法来寻找
if( i>=MaxSize ) return-1;
for(;S[i].Parent>=0;i=S[i].Parent);
returni;
}
但其实这个声明这个Data专门用来存储是可以省略的，直接用数组来存储就行了，想知道有几个独立的集合就看数组里面有几个-1就可以了(-1表示处于最上方的了)
集合简化表示
typedefintElementType;//默认元素可以用非负整数表示
typedefintSetNameL;//默认用根结点的下标作为集合名称
typedefElementTypeSetType[MaxSize];
SetNameFind(SetTypeS,ElementTypeX)//这个X直接就是数组的下标
{
//默认集合元素全部初始化为-1
for(;S[X]>=0;X=S[X]);//这和S[X]里面存的直接就是X的父节点
returnX;
}
voidUnion (SetTypeS, SetNameRoot1,SetNameRoot2)
{
//这里默认Root1和Root2是不同集合的根结点
S[Root2] =Root1;
}
小白-FT.2 题意理解与TSSN的实现
题意理解
C：检测能不能连通，能就Yes不行就No
I：连通
S：输入结束
在这里面每台计算机都是直接或者间接连通的。在上图中1虽然是一个孤立的计算机，但他也被认为是跟自己连通的
所以这个会输出：There are 2 components (这个系统有两个连通机)
在上图的这种情况下，输出的最后一行就应该是The network is connected(这个网络是连通的)
程序框架搭建
intmain()
{
初始化集合;
do{
读入一条指令;
处理指令;
}while(没结束);
return0;
}
翻译为具体代码如下
intmain()
{
SetTypeS;//这是并查集
intn;//n是集合里面元素的个数
charin;//第一个字符被命名为in
//初始化集合
scanf("%d\n",&n);
Initialization(S,n);
do{
scanf("%c",&in);
switch(in){
case'I':Input_connection(S);break;//把两台需要连接的计算机的编号读进来，检查是否连接好了，没连接好就连接一下
//Union和Find函数都会出现在上方那个函数当中
case'C':Check_connection(s);break;//这个函数要做的就是读入待查询的计算机的编号，检查他们在不在一个集合里面，用到Find函数
case'S':Check_network(s,n);break;//检查网络是否已经连通了
}
}while(in!='S');
return0;
}
答案是A
程序框架搭建2
//处理输入
voidInput_connection(SetTypeS)
{
ElementTypeu,v;
SetNameRoot1,Root2;
scanf("%d %d\n",&u,&v);
Root1=Find(S,u-1);
Root2=Find(S,v-1);
if( Root1!=Root2 )
Union(S,Root1,Root2);
}
-----------------------------------------------------------------
//处理查询
voidCheck_connection(SetTypeS)
{
ElementTypeu,v;
SetNameRoot1,Root2;
scanf("%d %d\n",&u,&v);
Root1=Find(S,u-1);
Root2=Find(S,v-1);
if( Root1==Root2 )
printf("Yes\n");
elseprintf("no\n")
}
--------------------------------------------------
//检查整个网络是否已经连通
voidCheck_network(SetTypeS,intn)
{
inti,count=0;
for(i=0; i<n; i++){
if( S[i] <0 ) counter++//只要S[i] < 0就意味着这是一个根节点
}
if(counter==1)//只有一个根节点表示整个集合全部连通了
printf("The network is connected.\n");//输出网络连通了
else
printf("There are %d conponents.\n",counter);//输出一共有剁谁个连通集
}
运行效率取决于Find函数与Union函数怎么实现的
TSSN(to simple sometime neive)实现
小白-FT.3 按秩归并
为什么需要按秩归并？
1. Union(Find(2),Find（1))//注意2在前，1在后。前面输入集合1后面输入集合2。让集合2指向集合1。其实也就是1指向2
2. Union(Find(3),Find（1))//这里1指向3了，由于上面那个，相当于2也指向3了
-
但这样显然会让树越来越高，有几个数，树就有多高，退化成单链表了，而且每次都绑定在1身上就意味着每次都需要从1开始找，直到找到他的根结点刚才一系列Union(Find(网络异常，图片无法展示|
), Find(1))（其中
)操作的时间复杂度是：T(n) = O(n²)为什么树的高度会越来越高
网络异常，图片无法展示|
- 只要把矮树贴到高树上就可以避免这种情况。但这样就势必要判断树的高度再决定谁贴到谁身上
- 树的高度存哪里？
S[Root] =-1//这是根结点，设置为-1就不会是任何一个元素的下标了，这样就把他和其他的非根结点区别开了。写-1或者-100都是没有区别的都可以
//由这个想法向后延伸
S[Root] =-树高//依旧初始化为-1，这棵树的高度一开始就是1，每个计算机都是单独的一个结点
//代码演示(伪代码)
if( Root2高度>Root1高度 )
S[Root1] =Root2;//集合1指向集合2
else{
if(两树一样高) 树高++;//存在新的结点里面
S[Root2] =Root1;
}
//实际代码，比高度的做法
if( S[Root2] <S[Root1] )//因为存的是负数，所以需要反着来
S[Root1] =Root2;//集合1指向集合2
else{
if( S[Root1] ==S[Root2] ) Root1--;//存在新的结点里面，是负数负数负数，需要--而不是++
S[Root2] =Root1;
}
- 另一种做法：比规模
- 把小树贴在大树上
- S[Root] = -元素个数
- 最后那个结果树的规模都会改变，变为两个树的规模之和
voidUnion(SetTypeS,SetNameRoot1,SetNameRoot2)
{
if(S[Root2] <S[Root1] ){
S[Root2] +=S[Root1];
S[Root1] =Root2;//把集合小的贴到大的上面去，在这里Root2更大，条件中只是因为是负数表示反过来了而已
}
else{
S[Root1] +=S[Root2];
S[Root2] =Root1;
}
}
- 上述的两种方法都统称按秩归并
按秩归并：最坏情况下树高 = O(logN)
小白-FT.4 路径压缩
按秩归并是对Union的一个改进
路径压缩是对Find这个函数的一个改进
SetNameFind (SetTypeS,ElementTypeX)
{
if(S[X] <0 )//找到集合的根，X如果小于0的话那就意味着X本身就已经是根了，直接返回就行了
returnX;
else
returnS[X] =Find( S,S[X]);//先找到根，把根变为X的父结点，再返回根
}
路径压缩好处：
- 第一次调用find会稍微复杂一点，但只要后续还需要调用就会非常合算
- Find函数的递归调用是一个伪递归调用(不会像递归一样把堆栈压爆掉，因为是非常容易转换成循环的，编辑器可能直接执行优化过后的循环代码)
做不做路径压缩的本质区别：
- 在查找次数M前面，到底是要乘一个常数还是要乘一个logN的问题。logN是N的一个递增函数，当N趋向无穷大的时候，logN也会趋向于无穷大。常数是不会变的
- 当N充分大的时候
