(c语言)File Transfer (25分)

程序员文章站 2022-03-05 21:22:44

...

关于数据结构Mooc后的每一道答案基本我都已经给出了详解
希望能对大家有所帮助收藏一下也是方便大家查找吧
(c语言)浙大数据结构Mooc作者答案集

下面是关于这道题的谷歌翻译
(c语言)File Transfer (25分)

~~关于这道题的闲谈~~

其实做这两道题主要看了视频的思路但也都是没有做一步看一步都是看完了就直接开做我觉得如果是看了一步做一步的话你对题目整体的理解还有你对函数内部的实现你这道题上面是找不到属于你的影子的如果这样的话那还不如不做（怎么感觉在批评诶）
确实是这个样子的我觉得独立思考还是很重要的而不是照本宣科照搬的把代码敲出来就觉得哦我做出来了到最后你连对自己的认可都没有。
感觉自己学上来对代码的理解还是更好了果然每天都在进步的感觉真好
~~希望今天下午和班长的上课计划能交流顺利hhhh~~
~~good luck to me~~

（来到正题）
（下面关于我对这道题的思路）

其实就让我们体会了一下并查集吧也没有那么难
连接两台电脑就是用Root表示为一样的
Check是不是连接起了就是检查Root是否一样
有几台主机就是检查Root数组中有几个负数因为刚开始都初始化为-1
上面都是基本

我觉得这里最重要的就是让我们体会了
以秩归类
还有路径压缩
详细的理解还请大家移步到视频再反复画图手写理解一下
因为陈越姥姥讲的确实已经够清晰了我解释的也不会有她清晰
hhh 所以下面看代码实现吧

下面是代码实现

#include <stdio.h>
#define MAX 10000

//这里S是指的Set 集合
typedef int ElementType;
ElementType S[MAX];

void Initialization(int numbers);
void InputConnection();
void CheckConnection();
void CheckNetwork();
int Find(ElementType Element);


void Initialization(int numbers)
{
    int i;
    for(i=0;i<numbers;i++)
        S[i] = -1;
}

void InputConnection()
{
    int connect1,connect2,root1,root2;
    scanf("%d%*c%d",&connect1,&connect2);
    root1 = Find(connect1-1);
    root2 = Find(connect2-1);

    //这里使用了路径压缩 如果想看秩归类 就把注释部分看一下
    //注释部分就是秩归类的方法
    
    if(root1 != root2)
       S[root2] = root1;

    /*if(root1 != root2)
    {

        //这里就修改成了用秩归并
        //因为极端情况很有可能找Root的时候的时候是以单链表来找
        //负数表示相反 说明root1的连接个数没有root2那么多
        if(S[root1] > S[root2])
        {
            S[root1] = root2;
            S[root2]--;
        }

        //包含了root1和root2相等规模和更大规模
        else
        {
            S[root2] = root1;
            S[root1]--;
        }
    }*/


    return;
}

void CheckConnection()
{
    int check1,check2,root1,root2;
    scanf("%d%*c%d",&check1,&check2);
    root1 = Find(check1-1);
    root2 = Find(check2-1);
    if(root1 == root2)
        printf("yes\n");
    else
        printf("no\n");
    return;
}

void CheckNetwork(int numbers)
{
    int i,count = 0;
    for(i=0;i<numbers;i++)
    {
        if(S[i] < 0)
        count++;
    }
    if(count == 1)
        printf("The network is connected.");
    else
        printf("There are %d components.",count);
    return;
}

int Find(ElementType Element)
{

	//这里使用了路径压缩 如果想看秩归类 就把注释部分看一下
    //注释部分就是秩归类
    
    /*for(; S[Element]>=0 ;Element = S[Element]);
    return Element;*/
    
    if(S[Element] < 0 )
       return Element;
    else
      {
        S[Element] = Find(S[Element]);
        return S[Element];
      }

}

int main()
{
    int numbers;
    scanf("%d",&numbers);
    Initialization(numbers);
    char option;

    //这里用do while更合适一点
    //因为是要先读取再判断 而且都需要把缓冲区的空格都读走
    do
    {

        //空格把缓冲区的回车读掉
        scanf(" %c",&option);

        switch(option)
        {
            case 'I' :InputConnection();break;
            case 'C' :CheckConnection();break;
            case 'S' :CheckNetwork(numbers);break;
        }
    } while(option != 'S');
    return 0;
}