集合的树表示及等价分类.cpp

树的集合表示和等价分类

#include<stdio.h>
#include<string.h>

struct treenode
{
	char s[32];
	treenode * gather;
	treenode * equal;
};

typedef treenode * T;

void readin(T);
void judge(T);
void print(T);
T attach(T,char *);

int main()
{
	T base;
	base=new treenode;

	base->gather;
	base->equal=NULL;

	readin(base);
	judge(base);

	printf("欢迎您的使用!\n");

	return 0;
}

void readin(T base)
{
	char s[32];
	T ptr1,ptr2;

	ptr1=base;
	ptr2=base;
	
	printf("请按照等价类的顺序输入该集合,每个等价类以#号结束,集合以*结束.\n");
	
	while(scanf("%s",s)==1&&s[0]!='*')
	{
			
			if(s[0]=='#')
			{	
				ptr1=new treenode;
				ptr2->equal->gather=ptr1;
				ptr2=ptr1;
			}
			else
				ptr1=attach(ptr1,s);
	}
}


void judge(T base)
{
	char s[32];
	T ptr1,ptr2;
	int flag;

	printf("输入你要查询的元素以回车结束(以#号结束该程序):\n");

	while(scanf("%s",s)==1&&s[0]!='#')
	{
		flag=0;
		
		ptr1=base;
		ptr2=base;
		while(ptr1->gather!=NULL)
		{
			ptr1=ptr1->equal;
			ptr2=ptr2->equal;
			while(ptr1!=NULL)
			{
				if(strcmp(s,ptr1->s)==0)
				{
					flag=1;
					break;
				}
				ptr1=ptr1->equal;
			}
			if(flag==1)
				break;
			ptr1=ptr2->gather;
			ptr2=ptr1;	
		}
		if(flag==1)
			print(ptr2);
		else
			printf("您输入的元素不存在！\n");
	}
}

T attach(T base,char*s)
{
	T ptr;
	ptr=new treenode;

	strcpy(ptr->s,s);

	ptr->gather=NULL;
	ptr->equal=NULL;

	base->equal=ptr;

	return ptr;
}

void print(T base)
{
	printf("与您输入的元素为同一等价类的元素为:\n");
	while(base!=NULL)
	{
		printf("%s\n",base->s);
		base=base->equal;
	}
	printf("请按照等价类的顺序输入该集合,每个等价类以#号结束,集合以*结束.\n");
	return ;
}