欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

05-树8 File Transfer

程序员文章站 2024-01-19 10:43:52
...

05-树8 File Transfer05-树8 File Transfer

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10000
typedef int ElementType; //默认元素可以用非负整数表示
typedef int SetName; //默认根结点下标作为集合的名称
typedef ElementType SetType[MaxSize]; //集合类型定义为数组

/**
 默认集合元素初始化 -1
 1~N 计算机对应下标 0~N-1
 元素下标为计算机的编号,对应存放的是父结点下标
*/

SetName Find(SetType S, ElementType X);
void Union(SetType S, SetName Root1, SetName Root2);
void Check(SetType S);
void Link(SetType S);
void Stop(SetType S, int N);

int main()
{
    int N;
    SetType S;
    char op;
    scanf("%d\n",&N);

    for(int i=0; i<N; i++)
        S[i]=-1;

    do{
        scanf("%c",&op);
        switch(op){
            case 'I': Link(S);break;
            case 'C': Check(S);break;
            case 'S': Stop(S,N);break;
        }
    }while(op != 'S');

    return 0;
}


//SetName Find(SetType S, ElementType X){
//    X--;
//    for(;S[X]>=0;X=S[X]); //直到S[X]==-1,X为树的根节点
//    return X; //返回所属集合的树的根结点下标
//}
//路径压缩优化
SetName Find(SetType S, ElementType X){
    if(S[X]<0)
        return X;
    else
        return S[X]=Find(S,S[X]);//找到根并变成X的父结点,再返回根
}


// 这个算法可能会造成某个集合的树变成单链表,增加算法的时间复杂度
//void Union(SetType S, SetName Root1, SetName Root2){
//    //默认Root1和Root2是不同集合的根结点
//    S[Root2]=Root1;
//}
// 解决方法:按秩归并
// 1.比树高
//void Union(SetType S,SetName Root1, SetName Root2){
//    if(S[Root1]>S[Root2]){ //树2比树1高
//        S[Root1]=Root2;
//    }else{
//        if(S[Root1]==S[Root2]){ //等高
//            S[Root2]=Root1;
//            S[Root1]--;
//        }else if(S[Root2]>S[Root1]){ //树1比树2高
//            S[Root2]=Root1;
//        }
//    }
//}
// 2.比规模(元素个数) 更好
void Union(SetType S,SetName Root1, SetName Root2){
    if(S[Root1]>S[Root2]){ //树2比树1元素多
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }else{
            S[Root1]+=S[Root2];
            S[Root2]=Root1;
    }
}



void Check(SetType S){
    ElementType x,y;
    SetName R1,R2;
    scanf("%d %d\n",&x,&y);
    R1=Find(S,x-1);
    R2=Find(S,y-1);
    if(R1==R2)
        printf("yes\n");
    else
        printf("no\n");
}

void Link(SetType S){
    ElementType x,y;
    SetName R1,R2;
    scanf("%d %d\n",&x,&y);
    R1=Find(S,x-1);
    R2=Find(S,y-1);
    if(R1!=R2)
        Union(S,R1,R2);
}

void Stop(SetType S, int N){
    int num=0;
    for(int i=0;i<N;i++){
        if(S[i]<0)
            num++;
    }
    if(num>1)
        printf("There are %d components.\n",num);
    else
        printf("The network is connected.\n");
}

05-树8 File Transfer