数据结构第五周笔记——树(下)(慕课浙大版本--XiaoYu)（二）

[例]：有10台电脑{1，2，3，.....，9，10}，已知下列电脑之间已经实现了连接：
1和2、2和4、3和5、4和7、5和8、6和9、6和10
问：2和7之间，5和9之间是否是连通的？
2和7是连通的，5和9不连通

int Find(SetType S[],ElementType X)
{
    //在数组S中查找值为X的元素所属的集合
    //MaxSize是全局变量，为数组S的最大长度
    int i;
    for(i = 0;i < MaxSize && S[i].Data != X; i++);
    if(i >= MaxSize) return -1;//未找到X,返回-1
    for(;S[i].Parent >= 0; i = S[i].Parent);//Parent的值为-1的时候就是找到根结点。i = S[i].Parent：原本指向i的位置现在跳到了s[i].Parent
    return i;//找到X所属集合，返回树根结点在数组S中的下标
}

void Union(SetType S[ ],ElementType X1,ElementType X2 )
{
    int Root1,Root2;
    Root1 = Find(S,X1);//得到X1与X2对应的树根
    Root2 = Find(S,X2);
    if( Root1 != Root2 ) S[Root2].Parent = Root1;//判断如果不是本身就是同一个集合的，如果是同一个集合的话就不需要做这个并的操作。不同则合并
}

#define MAXN 1000                  /* 集合最大元素个数 */
typedef int ElementType;           /* 默认元素可以用非负整数表示 */
typedef int SetName;               /* 默认用根结点的下标作为集合名称 */
typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */
void Union( SetType S, SetName Root1, SetName Root2 )
{ /* 这里默认Root1和Root2是不同集合的根结点 */
    /* 保证小集合并入大集合 */
    if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
        S[Root2] += S[Root1];     /* 集合1并入集合2  */
        S[Root1] = Root2;
    }
    else {                         /* 如果集合1比较大 */
        S[Root1] += S[Root2];     /* 集合2并入集合1  */
        S[Root2] = Root1;
    }
}
SetName Find( SetType S, ElementType X )
{ /* 默认集合元素全部初始化为-1 */
    if ( S[X] < 0 ) /* 找到集合的根 */
        return X;
    else
        return S[X] = Find( S, S[X] ); /* 路径压缩 */

堆的表示及其操作(堆是一种按一定顺序组织的完全二叉树)
#define MAXN 1001
#define MINH -10001
int H[MAXN],size;//由于堆在存储的时候是把根结点放在数组下标为1的地方，也就是说0是空缺的
//这样子按照一层层顺序逐个往数组后面存放，使得堆中的任何一个元素可以很容易的找到他的父节点在哪里，左右儿子在哪里
//整数size表示当前堆大小
void Create()//堆的初始化，就是建立一个空堆(size设置为0)
{
    size = 0;
    H[0] = MINH;//设置岗哨
}
//插入操作
void Insert(int X)
{
    //将X插入H。这里省略检查堆是否已满的代码
    int i;
    for(i = ++size;H[i/2]>X;i/=2)
        H[i] = H[i/2];//i挪到父节点(i/2)的位置
    H[i] = X;
}
主程序
    int main()
{
    1.读入n和m
    2.根据输入序列建堆
    3.对m个要求：打印到根的路径
        return 0;
}
//具体实现程序
int main()
{
    int n,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");
    }
    return 0;
}

typedef struct {
    ElementType Data;
    int Parent;
}SetType;

int Find(SetType S[],ElementType X)
{
    int i;
    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);
    return i;
}

typedef int ElementType;//默认元素可以用非负整数表示
typedef int SetNameL;//默认用根结点的下标作为集合名称
typedef ElementType SetType[MaxSize];
SetName Find(SetType S,ElementType X)//这个X直接就是数组的下标
{
    //默认集合元素全部初始化为-1
    for(;S[X]>=0;X=S[X]);//这和S[X]里面存的直接就是X的父节点
    return X;
}
void Union (SetType S, SetName Root1,SetName Root2)
{
    //这里默认Root1和Root2是不同集合的根结点
    S[Root2] = Root1;
}

int main()
{
  初始化集合;
    do{
        读入一条指令;
        处理指令;
    }while(没结束);
    return 0;
}

int main()
{
    SetType S;//这是并查集
    int n;//n是集合里面元素的个数
    char in;//第一个字符被命名为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');
    return 0;
}

//处理输入
void Input_connection(SetType S)
{
    ElementType u,v;
    SetName Root1,Root2;
    scanf("%d %d\n",&u,&v);
    Root1 = Find(S,u-1);
    Root2 = Find(S,v-1);
    if( Root1 != Root2 )
        Union(S,Root1,Root2);
}
-----------------------------------------------------------------
//处理查询
void Check_connection(SetType S)
{
    ElementType u,v;
    SetName Root1,Root2;
    scanf("%d %d\n",&u,&v);
    Root1 = Find(S,u-1);
    Root2 = Find(S,v-1);
    if( Root1 == Root2 )
        printf("Yes\n");
    else printf("no\n")
}
--------------------------------------------------
//检查整个网络是否已经连通
    void Check_network(SetType S,int n)
{
    int i,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函数怎么实现的

1. Union(Find(2),Find（1))//注意2在前，1在后。前面输入集合1后面输入集合2。让集合2指向集合1。其实也就是1指向2
2. Union(Find(3),Find（1))//这里1指向3了，由于上面那个，相当于2也指向3了

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;
    }

void Union(SetType S,SetName Root1,SetName Root2)
{
    if(S[Root2] < S[Root1] ){
        S[Root2] += S[Root1];
        S[Root1] = Root2;//把集合小的贴到大的上面去，在这里Root2更大，条件中只是因为是负数表示反过来了而已
    }
    else{
        S[Root1] +=S[Root2];
        S[Root2] = Root1;
    }
}

SetName Find (SetType S,ElementType X)
{
    if(S[X] < 0 )//找到集合的根，X如果小于0的话那就意味着X本身就已经是根了，直接返回就行了
        return X;
    else
        return S[X] = Find( S,S[X]);//先找到根，把根变为X的父结点，再返回根
}