aggregate.cpp

来自「数据结构经典算法的C语言实现 计算机专业数据结构课程实验」· C++ 代码 · 共 189 行

#include <iostream.h>

#define MAX 20

typedef int MFSET1[MAX + 1];
typedef struct node {
	int father;
	int count;
} MFSET2[MAX + 1];

//合并
void UNION1(int i, int j, MFSET1* parent) {
	(*parent)[i] = j;
}
//查找
int FIND1(int i, MFSET1* parent) {
	int temp;
	temp = i;
	while((*parent)[temp] > 0)
		temp = (*parent)[temp];
	return temp;
}
//初始化
void INITIAL1(int x, MFSET1* A) {
	(*A)[x] = 0;
}
//合并
void UNION2(int i, int j, MFSET2* parent) {
	if((*parent)[i].count > (*parent)[j].count) {
		(*parent)[j].father = i;
		(*parent)[i].count += (*parent)[j].count;
	}
	else {
		(*parent)[i].father = j;
		(*parent)[j].count += (*parent)[i].count;
	}
}
//查找
int FIND2(int i, MFSET2* parent) {
	while ((*parent)[i].father != 0)
		i = (*parent)[i].father;
	return i;
}
//初始化
void INITIAL2(int x, MFSET2* A) {
	(*A)[x].father = 0;
	(*A)[x].count = 1;
}
//等价分类
void EQUIVA1(MFSET1* S) {
	int i, j, m, k;
	
	for (i = 1; i <= MAX; i++)
		INITIAL1(i, S);
lable1:
	cout<<"请输入等价对，中间用空格隔开，以0 0结束："<<endl;
	cin>>i>>j;
	if(i < 0 || i > 20 || j < 0 || j > 20) {
		cout<<"输入数据不在程序允许范围内，请重新输入1－20内的数据。"<<endl;
		goto lable1;
	}
	while(!(i == 0 && j == 0)) {
		k = FIND1(i,S);
		m = FIND1(j,S);
		if(k != m)
			UNION1(k, m, S);
		cout<<"请输入等价对，中间用空格隔开，以0 0结束："<<endl;
		cin>>i>>j;
	}
}
//等价分类
void EQUIVA2(MFSET2* S) {
	int i, j, m, k;
	
	for (i = 1; i <= MAX+1; i++)
		INITIAL2(i, S);
lable2:
	cout<<"请输入等价对，中间用空格隔开，以0 0结束："<<endl;
	cin>>i>>j;
	if(i < 0 || i > 20 || j < 0 || j > 20) {
		cout<<"输入数据不在程序允许范围内，请重新输入1－20内的数据。"<<endl;
		goto lable2;
	}
	while(!(i == 0 && j == 0)) {
		k = FIND2(i,S);
		m = FIND2(j,S);
		if(k != m)
			UNION2(k, m, S);
		cout<<"请输入等价对，中间用空格隔开，以0 0结束："<<endl;
		cin>>i>>j;
	}
}
//输出等价类
void OUTPUT1(MFSET1 *S) {
	int i, j, temp;
	
	for (i = 1; i <= MAX; i++) {
		temp = i;
		if ((*S)[temp] != 0) {
			while ((*S)[temp] != 0)
				temp = (*S)[temp];			
		}
		(*S)[i] = temp;
	}
	
	for (i = 1; i <= MAX; i++) {
		if((*S)[i] != 0) {
			cout<<endl;
			temp = (*S)[i];
			for(j = i; j <= MAX; j++) {
				if ((*S)[j] == temp) {
					cout<<j<<" ";
					(*S)[j] = 0;
				}
			}
		}		
	}
}
//输出等价类
void OUTPUT2(MFSET2 *S) {
	int i, j, temp;
	
	for (i = 1; i <= MAX; i++) {
		temp = i;
		if ((*S)[temp].father != 0) {
			while ((*S)[temp].father != 0)
				temp = (*S)[temp].father;
			(*S)[i].father = temp;
		}		
	}

	for (i = 1; i <= MAX; i++) {
		if((*S)[i].father != -1) {
			if ((*S)[i].father == 0) {
				cout<<i<<" ";
				temp = i;
				for(j = i; j <= MAX; j++) {
					if ((*S)[j].father == temp) {
						cout<<j<<" ";
						(*S)[j].father = -1;
					}
				}
				cout<<endl;
			}
			else {
				temp = (*S)[i].father;
				for(j = i; j <= MAX; j++) {
					if ((*S)[j].father == temp || j == temp) {
						cout<<j<<" ";
						(*S)[j].father = -1;
					}
				}
				cout<<endl;
			}
		}		
	}
}

void main() {
	char   ch;
	char   yn;
	MFSET1 S1;
	MFSET2 S2;
lable:
	cout<<"功能描述：本程序用两种方法实现集合{1,2,……20}的树结构表示及等价分类。"<<endl;
	cout<<"请选择表示方法：1、ADT MFSET原型    2、ADT MFSET改进型    ";
	cin>>ch;
	
	if(ch == '1') {
		EQUIVA1(&S1);
		cout<<"等价类为：";
		OUTPUT1(&S1);
		cout<<endl;
	}
	else if(ch == '2') {
		EQUIVA2(&S2);
		cout<<"等价类为："<<endl;
		OUTPUT2(&S2);
	}
	else {
		cout<<"输入错误，请重新选择！"<<endl;
		goto lable;
	}
	
	cout<<"是否继续使用本程序？Y继续使用，N退出程序：";
	cin>>yn;
	if(yn == 'y' || yn == 'Y')
		goto lable;
}