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

浙大数据结构习题笔记:05-树8 File Transfer (25分)

程序员文章站 2022-03-27 14:13:50
...

05-树8 File Transfer (25分)

原题

浙大数据结构习题笔记:05-树8 File Transfer (25分)
浙大数据结构习题笔记:05-树8 File Transfer (25分)
浙大数据结构习题笔记:05-树8 File Transfer (25分)

总结

这道题就是并查集的配套习题,之前学校在学图的算法时就提到过要使用并查集实现,但因为没细讲并查集的实现导致我学的一知半解(
学完这个后,觉得还可以,这里面的并查集还是比较好实现的,通过数组下标记录对应值,数组中存储的是每个值的父节点的位置。FindUnion采用极简的操作如下

int Find(SetType S[],int n)
{
	for(;S[n] >= 0;n = S[n]);
	return x;
}

void Union(SetType s[],int x1,int x2){
	S[x2] = S[x1];
}

但是以这样的极简方法来做,可能会造成超时
于是我们采用按秩归并路径压缩的方法简化时间,具体操作如下程序
其中的按秩归并,我们设根节点的值为-元素个数,就是值为这个根下面所有元素个数的负数,如果根后无节点,就是-1,以这样的方式,我们可以做到在归并的过程中,将元素少的根节点并到元素多的根结点上,使得树的高度不会必然增加

在路径压缩中,我们采用一个尾递归的方式,在递归过程中将一个高度很高的树打散,分别接在第一个节点上,具体作用如图

浙大数据结构习题笔记:05-树8 File Transfer (25分)

具体代码实现

#include<cstdio>
#define MaxSize 10005
typedef int SetType; 
using namespace std;

void Init(SetType s[],int n){
	for(int i=0;i<n;i++)
		s[i] = -1;
}

int Find(SetType s[],int x){
	if(s[x] < 0)  // 本身已经是根 
		return x;
	else  // 1. 找到根  2. 把根变成 x 的父结点  3.再返回根 
		return s[x] = Find(s,s[x]);
} 

void Union(SetType s[],int x1,int x2){
    //S[root] = -元素个数
    if(s[x1] < s[x2]){  //x1的元素多,少的并入多的中
		s[x1] += s[x2];
		s[x2] = x1;
	}else{
		s[x2] += s[x1];
		s[x1] = x2;
	}
} 

void Input_connection(SetType s[]){
	int x1,x2;
	scanf("%d %d",&x1,&x2);
	int root1 = Find(s,x1-1);  // 以数组下标存值,下标与存值差 1 
	int root2 = Find(s,x2-1);
	if(root1 != root2)
		Union(s,root1,root2);
}

void check_connection(SetType s[]){
	int x1,x2;
	scanf("%d %d",&x1,&x2);
	int root1 = Find(s,x1-1);
	int root2 = Find(s,x2-1);
	if(root1 == root2)
		printf("yes\n");
	else
		printf("no\n");
} 

void check_network(SetType s[],int n){
	int counter = 0;
	for(int i=0;i<n;i++)
		if(s[i] < 0)
			counter++;
	if(counter == 1)
		printf("The network is connected.");
	else
		printf("There are %d components.",counter);
}


int main(){
	int n;
	char in;
	scanf("%d",&n); 
	SetType s[MaxSize];
	Init(s,n);
	do{
		getchar();
		scanf("%c",&in);
		switch(in){
			case 'I':Input_connection(s);break;
			case 'C':check_connection(s);break;
			case 'S':check_network(s,n);break;
		}		
	}while(in != 'S');

	return 0;
}