mintree.cpp

数据结构是编程的基础

// mintree.cpp : Defines the entry point for the console application.
//


#include "stdafx.h"
#define NULL 0

///////////////////////////////产生1-100的随机整数作为可权值////////////////////////////////////////////////////////////
#define RND 99*rand()/32767+1

/////////////////////////////定义城市间带权的线路//////////////////////////////////////////////////////////////
struct road
{
	int source;                 //城市编号                                     
	int dest;                   //城市编号
	int value;                  //线路权值
	struct road *next;
	struct road *last;
	int state;                  //线路状态，值为1：已被选定不会被删除也不参与比较，否则值为0
};
/////////////////////////////定义城市间带权的线路//////////////////////////////////////////////////////////////

/////////////////////////////定义城市森林//////////////////////////////////////////////////////////////
struct mfset
{
	int value;             //  城市树编号  
	int state;             //城市树的状态，值为1:此树已被并入另一棵树，城市不在这棵树中搜寻，否则值为0
	struct mfset *next;
};
//////////////////////////////定义城市森林/////////////////////////////////////////////////////////////

////////////////////////////定义输出文件///////////////////////////////////////////////////////////////
FILE *fp;	

//////////////////////////////初始化城市通路/////////////////////////////////////////////////////////////
struct road * initroad(int count)
{
	int i=0,j=0;
	struct road *temproad=NULL,*road=NULL;
	srand( (unsigned)time( NULL ) );
	temproad=(struct road *)malloc(sizeof(struct road));
	temproad->next=NULL;
	temproad->state=0;
	road=temproad;
	for(i=0;i<count;i++)
	{
		for(j=i+1;j<count;j++)
		{
			temproad->next=(struct road *)malloc(sizeof(struct road));
			temproad->next->source=i;
			temproad->next->dest=j;
			temproad->next->value=RND;
			temproad->next->next=NULL;
			temproad->next->state=0;
			temproad->next->last=temproad;

			printf("若从第%d城到第%d城架设线路权值为：%d\n",i+1,j+1,temproad->next->value);
			fprintf(fp,"若从第%d城到第%d城架设线路权值为：%d\n",i+1,j+1,temproad->next->value);
			temproad=temproad->next;
			
		}
	}
	return road;
}
////////////////////////////初始化城市通路///////////////////////////////////////////////////////////////

/////////////////////////////初始化城市森林//////////////////////////////////////////////////////////////
struct mfset * initmfset(int count)
{
	struct mfset *tempset=NULL;
	int i=0;
	tempset=(struct mfset *)malloc(count*sizeof(struct mfset));
	for(i=0;i<count;i++)
	{
		tempset[i].value=i;
		tempset[i].state=0;
		tempset[i].next=NULL;
	}
	return tempset;
}
//////////////////////////////初始化城市森林/////////////////////////////////////////////////////////////

///////////////////////////寻找指定城市在哪颗树上////////////////////////////////////////////////////////////////
int findcityinmfset(struct mfset *mfset,int citynumber,int count)
{
	int i=0;
	struct mfset *tempmfset=NULL;
	for(i=0;i<count;i++)
	{
		if(1==mfset[i].state)
		{
			continue;
		}
		else
		{
			tempmfset=mfset+i;
			while(NULL!=tempmfset)
			{
				if(citynumber==tempmfset->value)
				{
					return i;
				}
				tempmfset=tempmfset->next;
			}
		}
	}
	printf("未知错误!!!!!!\n");
	exit(0);
}
///////////////////////////////寻找指定城市在哪颗树上////////////////////////////////////////////////////////////

///////////////////////////////将在间通路删除////////////////////////////////////////////////////////////
void delroad(struct mfset *mfset,struct road *road,int count)
{
	struct road *temproad=NULL;
	int ss=0,dd=0;
	temproad=road;
	while(NULL!=temproad)
	{
		if(1==temproad->state)
		{
			temproad=temproad->next;
			continue;
		}
		/////////////////////////////////两城在同一颗树上，删除这条路///////////////////////////
		if((ss=findcityinmfset(mfset,temproad->source,count))==(dd=findcityinmfset(mfset,temproad->dest,count)))
		{
		    temproad->last->next=temproad->next;
			if(NULL!=temproad->next)
			temproad->next->last=temproad->last;
		}
		temproad=temproad->next;
	}
}
/////////////////////////////////将在同一颗树上的城市间通路删除//////////////////////////////////////////////////////////

////////////////////////////////将两颗树合并为一棵树///////////////////////////////////////////////////////////
void mergmfset(struct mfset *mfset,int first,int second,int count)
{
	struct mfset *tempset=NULL;
	int one=0,two=0;
	one=findcityinmfset(mfset,first,count);
	two=findcityinmfset(mfset,second,count);
	tempset=mfset+one;
	while(NULL!=tempset->next)
	{
		tempset=tempset->next;
	}
	tempset->next=mfset+two;
	mfset[two].state=1;
}
/////////////////////////将两颗树合并为一棵树//////////////////////////////////////////////////////////////////

//////////////////////////寻找最短的通路/////////////////////////////////////////////////////////////////
void findminroad(struct road *road,struct mfset *mfset,int count)
{
	struct road *temproad=NULL,*minroad=NULL;
	int i=101;
	temproad=road;
	while(NULL!=temproad)
	{
		if(0==temproad->state&&i>temproad->value)
		{
			i=temproad->value;
			minroad=temproad;
		}
		temproad=temproad->next;
	}
	minroad->state=1;
	/////////////////////////将两颗树合并为一棵树///////////////////////////////////
	mergmfset(mfset,minroad->source,minroad->dest,count);
	printf("从第%d城到第%d城架线，权值为：%d\n",minroad->source+1,minroad->dest+1,minroad->value);
	fprintf(fp,"从第%d城到第%d城架线，权值为：%d\n",minroad->source+1,minroad->dest+1,minroad->value);
}
//////////////////////////寻找最短的通路/////////////////////////////////////////////////////////////////

int main(int argc, char* argv[])
{
	int count=0,i=0;
	struct road *road=NULL;
	struct mfset *mfset=NULL;
	fp=fopen("output.txt","w");
/////////////////////////初始城市数量/////////////////////////////////////////////////////
	while(0==i)
	{
		printf("请输入城市数量(4---50之间)：");
		scanf("%d",&count);
		if(count<4||count>50)
		{
			printf("请输入正确的数量,按任意键继续。。。。。。。。。。。。\n");
			getch();
			system("cls");
			i=0;
		}
		else
		{
			i=1;
		}
	}
	//////////////////////////////初始化城市通路//////////////////////
	road=initroad(count);
	/////////////////////////////初始化城市森林/////////////////
	mfset=initmfset(count);
	printf("最佳架线方案为：\n");
	fprintf(fp,"最佳架线方案为：\n");
	for(i=0;i<count-1;i++)
	{		
		findminroad(road->next,mfset,count);
		delroad(mfset,road->next,count);
	}
	fclose(fp);
	return 0;
}