p6.c

本程序是实现对室内电源线及插座的布局 是数据结构中的一个程序

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "p6.h"

struct priorityQ
{
	int size;
	ElementType *Elements;
};

struct node
{
	int v1;
	int v2;
	float dist;
};

struct outlet
{
	float x;
	float y;
	float z;
};

struct queue
{
	int size;
	OutLet *OL;
};

void main()
{
	float Kruskal(Graph G,int NumVertex);
	void Initialize(DisjSet S,int NumVertex);
	void GtoHeap(Graph G,Heap H,int NumVertex);
	void BuildHeap(Heap H);
	void PercDown(Heap H,int i);
	Heap InitHeap(int HElements);
	void Equate(ElementType U,ElementType V);
	ElementType DelMin(Heap H);
	setType Find(int x,DisjSet S);
	void SetUnion(DisjSet S,setType root1,setType root2);
	float Dist(float doorx1,float doorx2,float doory1,float doory2,float doorz1,float doorz2,
		float Lx,float Ly,float Lz,
		float x1,float y1,float z1,float x2,float y2,float z2);
	float min4(float x1,float x2,float x3,float x4);
	float max4(float x1,float x2,float x3,float x4);
	int Wall(float x,float y,float Lx,float Ly);
	Queue InitOL(int NunVertex);
	void CrtGraph(Queue Q,Graph G,
			  float doorx1,float doorx2,float doory1,float doory2,float doorz1,float doorz2,
			  float Lx,float Ly,float Lz);
	float min1(float x,float y);
	float max1(float x,float y);


	int i,NumVertex;
	float dx1,dy1,dz1,dx2,dy2,dz2,dx3,dy3,dz3,dx4,dy4,dz4,
		doorx1,doorx2,doory1,doory2,doorz1,doorz2,
		Lx,Ly,Lz,len;
	Queue Q;
	Graph G;
	FILE *in,*out;

	if((in=fopen("input.txt", "r"))==NULL)			/* we will get the data from "input.txt" */
	{
		printf("Can not open file input.txt!\n");
		exit(0);
	}
	if((out=fopen("output.txt","w"))==NULL)			/* the result is put to "output.txt" */
	{
		printf("Can not open file output.txt!\n");
		exit(0);
	}

		Q=InitOL(Max);						/* initiate a queue of structures to store the information of the position of hte outlets */

	while(!feof(in))
	{
		fscanf(in,"%f%f%f",&dx1,&dy1,&dz1);			/* this is one of the 4 coordinate of the door */
		if(feof(in)) break;
		fscanf(in,"%f%f%f",&dx2,&dy2,&dz2);
		fscanf(in,"%f%f%f",&dx3,&dy3,&dz3);
		fscanf(in,"%f%f%f",&dx4,&dy4,&dz4);

		fscanf(in,"%f%f%f",&Lx,&Ly,&Lz);			/* this is the size of the room */

		doorx1=min4(dx1,dx2,dx3,dx4);				/* I convert the information of the door to another form */
		doorx2=max4(dx1,dx2,dx3,dx4);				/* doorx1,doorx2,doory1,doory2,doorz1,doorz2 stores information of the 4 corners of the door */
		doory1=min4(dy1,dy2,dy3,dy4);				/* I difine doorx1<=doorx2,doory1<=doory2,doorz1<=doorz2 */
		doory2=max4(dy1,dy2,dy3,dy4);
		doorz1=min4(dz1,dz2,dz3,dz4);
		doorz2=max4(dz1,dz2,dz3,dz4);

		fscanf(in,"%d",&NumVertex);					/* NumVertex is the number of the outlets in this test case */

		for(i=0;i<NumVertex;i++)					/* read the information into the queue */
		{
			Q->size=NumVertex;
			fscanf(in,"%f%f%f",&Q->OL[i]->x,&Q->OL[i]->y,&Q->OL[i]->z);
		}

		CrtGraph(Q,G,
			  doorx1,doorx2,doory1,doory2,doorz1,doorz2,
			  Lx,Ly,Lz);							/* convert the information of the out lets into a graph */
													/* G[i][j] = G[j][i] = the distance between outler[i] and outlet[j] */
		len=Kruskal(G,NumVertex);

		if((len-(int)len)==0)						/* out put the closest integer to len */
			fprintf(out,"%d\n",(int)len);
		else
			fprintf(out,"%d\n",(int)len+1);
	}
	free(Q->OL);									/* free the space here */
	free(Q);

	fclose(in);
	fclose(out);
}

float Kruskal(Graph G,int NumVertex)
{													/* this function will return the lenth of the wire used, in the form of a float */
	int EdgeAcpt,HElements;
	float len=0;
	DisjSet S;
	Heap H;
	setType Uset,Vset;
	Edge E;

	HElements=(Max+1)*Max/2;						/* HElements equals the number of the pairs of outlets */
	Initialize(S,NumVertex);
	H=InitHeap(HElements);							/* initiate a heap to perform sort the length of the edges, from shortest to longest */
	GtoHeap(G,H,NumVertex);							/* read the information into the Heap */
	BuildHeap(H);

	EdgeAcpt=0;

	while(EdgeAcpt<NumVertex-1)
	{
		E=DelMin(H);								/* pick out the shortest unused edge */
		Uset=Find(E->v1,S);							/* check if the 2 nodes is not conneted */
		Vset=Find(E->v2,S);

		if(Uset!=Vset)								/* if not,connect them */
		{
			len+=G[E->v1][E->v2];					/* add the edge into the total lenth fo wires */
			EdgeAcpt++;
			SetUnion(S,Uset,Vset);					/* connet the outlets */
		}
	}

	free(H->Elements);								/* free the space here */
	free(H);

	return len;										/* len is the total lenth of wires used */
}

void Initialize(DisjSet S,int NumVertex)
{													/* initiate the disjoint set, assume that all the outlets are not connected */
	int i;
	for(i=0;i<=Max;i++)
		S[i]=-1;
}


Heap InitHeap(int HElements)
{													/* allocate space to perform heap operations */
	Heap H;
	int i;

	H=malloc(sizeof(struct priorityQ));

	if(H==NULL)
		printf("Out of space!!!");
	
	H->size=0;

	H->Elements=malloc((HElements+1)*sizeof(struct node));	/* the information of outlets is stored as in struct element */

	for(i=0;i<=HElements;i++)
	{
		H->Elements[i]=malloc(sizeof(struct node));
	
		if(H->Elements[i]==NULL)
			printf("Out of space!!!");
	}

	return H;										/* return a pointer to Heap */
}

void GtoHeap(Graph G,Heap H,int NumVertex)
{
	int i,j,k;
	k=1;
	for(i=0;i<NumVertex;i++)
		for(j=i+1;j<NumVertex;j++)
		{
			H->Elements[k]->v1=i;					/* i,j are the number of outlets */
			H->Elements[k]->v2=j;
			H->Elements[k]->dist=G[i][j];			/* read the distance between i and j into heap */
			k++;
			H->size++;
		}
}

void BuildHeap(Heap H)
{													/* sort the elemnts in the heap */
	int i;
	for(i=(H->size/2);i>0;i--)
		PercDown(H,i);
}

void PercDown(Heap H,int i)
{													/* used to build heap */
	int child;
	ElementType V;
	V=malloc(sizeof(ElementType));

	if(V==NULL)
		printf("Out of space!!!");

	Equate(V,H->Elements[i]);						/* made the value of V equal to that of H->Elements[i], for further purpose of swapping the two */

	for(;2*i<=H->size;i=child)
	{
		child=i*2;
		if(child!=H->size && H->Elements[child+1]->dist < H->Elements[child]->dist)
			child++;								/* if leftchild is bigger than the right one, pick the right child as the root */

		if(V->dist > H->Elements[child]->dist)
			Equate(H->Elements[i],H->Elements[child]);
		else
			break;									/* find the right place of insert here */
	}
	Equate(H->Elements[i],V);						/* put the element back into the heap */
}

void Equate(ElementType U,ElementType V)
{													/* make element U equal to V */
	U->v1=V->v1;
	U->v2=V->v2;
	U->dist=V->dist;
}

ElementType DelMin(Heap H)
{													/* delete the first element of the heap */
	int i,child;									/* which is also the smallest */
	ElementType Min,Last;							/* initiate two structs to store the information */

	Min=(ElementType)malloc(sizeof(ElementType));
	Last=(ElementType)malloc(sizeof(ElementType));

	if(H->size<1)									/* H->element[0] does not exist,so when H->size < 1, heap is empty */
	{
		printf("Heap is empty!!!");
		return H->Elements[1];
	}

	Equate(Min,H->Elements[1]);
	Equate(Last,H->Elements[H->size--]);

	for(i=1;i*2 <= H->size;i=child)
	{
		child=i*2;
		if(child!=H->size && (H->Elements[child+1]->dist < H->Elements[child]->dist))
			child++;								/* after a delmin, we put the last element back into the heap */
		if(Last->dist > H->Elements[child]->dist)
			Equate(H->Elements[i],H->Elements[child]);
		else break;
	}

	Equate(H->Elements[i],Last);					/* put the element got out back into a proper position */

	return Min;										/* return the minimun element of the heap, which had been deleted */
}

setType Find(int x,DisjSet S)
{
	if(S[x]<0)										/* this function deals with the disjoint set */
		return x;									/* retrun the root of a certain element */
	else S[x]=Find(S[x],S);							/* decrease the deapth of the tree */
}

void SetUnion(DisjSet S,setType root1,setType root2)
{													/* connect the two element */
	if(S[root2]<S[root1])							/* try to make the tree lower */
		S[root1]=root2;

	S[root2]=root1;
}


float Dist(float doorx1,float doorx2,float doory1,float doory2,float doorz1,float doorz2,
		float Lx,float Ly,float Lz,
		float x1,float y1,float z1,float x2,float y2,float z2)
{
	int wall1,wall2,walld;
	float t1,t2,t3,p1,p2,p3;

	if(Wall(x1,y1,Lx,Ly) > Wall(x2,y2,Lx,Ly))		/* made some adjustment of the data so wall1 is always smaller than wall2 */
	{
		t1=x1;t2=y1;t3=z1;
		x1=x2;y1=y2;z1=z2;
		x2=t1;y2=t2;z2=t3;
	}

	if(Wall(x1,y1,Lx,Ly) == Wall(x2,y2,Lx,Ly))		/* if the 2 outlet are on the same wall */
	{
		if(Wall(x1,y1,Lx,Ly)==1||Wall(x1,y1,Lx,Ly)==3)							/* make the smaller element preceed the bigger one */
		{
			if(x1>x2)
			{
				t1=x1;t2=y1;t3=z1;
				x1=x2;y1=y2;z1=z2;
				x2=t1;y2=t2;z2=t3;
			}
		}
		else if(Wall(x1,y1,Lx,Ly)==2||Wall(x1,y1,Lx,Ly)==4)
		{
			if(y1>y2)
			{
				t1=x1;t2=y1;t3=z1;
				x1=x2;y1=y2;z1=z2;
				x2=t1;y2=t2;z2=t3;
			}
		}
	}

	wall1=Wall(x1,y1,Lx,Ly);						/* make a record which wall the 2 outlets are on */
	wall2=Wall(x2,y2,Lx,Ly);

	if(doorx1==0 && doorx2==0)						/* deal with case which the 2 outlet is on the same wall */
		walld=4;
	else if(doory1==Ly && doory2==Ly)
		walld=3;
	else if(doorx2==Lx && doorx1==Lx)
		walld=2;
	else if(doory1==0 && doory2==0)
		walld=1;

	if((wall1==1 && wall2==3) || (wall1==2 && wall2==4))	/* deal with the case that the 2 outlet is on 2 counter walls */
	{														/* the are 3 possible paths */
		p1=x1+x2+y1+y2+fabs(z1-z2);							/* p1,p2,p3 records the lenth of the 3 paths */
		p2=2*Lx-(x1+x2)+2*Ly-(y1+y2)+fabs(z1-z2);
	}
	else													/* else the the outlets are on the same wall or on adjecent walls */
	{
		p1=fabs(x1-x2)+fabs(y1-y2)+fabs(z1-z2);
		p2=2*Lx-fabs(x1-x2)+2*Ly-fabs(y1-y2)+fabs(z1-z2);
	}

	if((wall1==1 && wall2==3) || (wall1==2 && wall2==4))
	{
		if(wall1==1 && wall2==3)					
		{
			p3=Ly+(z1+z2)+fabs(x1-x2);


			if(doorz1<=z1 && doorz2>=z1 && doorz1<=z2 && doorz2>=z2)			/* the wire will go accross the door */
			{
				if(walld==4 || (walld==3 && doorx2<=x2) || (walld==1 && doorx2<=x1))
					p1+=2*min1(doorz2-max1(z1,z2),min1(z1,z2)-doorz1);
				else
					p2+=2*min1(doorz2-max1(z1,z2),min1(z1,z2)-doorz1);
			}

			if(doorx1<=x1 && doorx2>=x1 && doorx1<=x2 && doorx2>=x2)
			{
				if((walld==1 && doorz2<=z1) || (walld==3 && doorz2<=z2))
					p3+=2*min1((doorx2-max1(x1,x2)),(min1(x1,x2)-doorx1));
			}
			return min4(p1,p2,p3,1000);								/* return the shortest path,1000 is a sentinel to avoide the usage of another function */
		}

		if(wall1==2 && wall2==4)									/* another case of outlets on counter walls */
		{
			p3=Lx+(z1+z2)+fabs(y1-y2);

			if(doorz1<=z1 && doorz2>=z1 && doorz1<=z2 && doorz2>=z2)
			{
				if(walld==1 || (walld==4 && doory2<=y2) || (walld==2 && doory2<=y1))
					p1+=2*min1(doorz2-max1(z1,z2),min1(z1,z2)-doorz1);
				else
					p2+=2*min1(doorz2-max1(z1,z2),min1(z1,z2)-doorz1);
			}

			if(doory1<=y1 && doory2>=y1 && doory1<=y2 && doory2>=y2)
			{
				if((walld==2 && doorz2<=z1) || (walld==4 && doorz2<=z2))
					p3+=2*min1(doory2-max1(y1,y2),min1(y1,y2)-doory1);
			}
			return min4(p1,p2,p3,1000);
		}
	}
	else																/* the outlets are on adjecent walls or on the same wall */
	{
		if(doorz1<=z1 && doorz2>=z1 && doorz1<=z2 && doorz2>=z2)
		{
			if(wall1==wall2)											/* if they are on the same wall */
			{
				if((wall1==1 && walld==1 && doorx1>=x1 && doorx2<=x2)
					||(wall1==2 && walld==2 && doory1>=y1 && doory2<=y2)
					||(wall1==3 && walld==3 && doorx1>=x1 && doorx2<=x2)
					||(wall1==2 && walld==2 && doory1>=y1 && doory2<=y2))
					p1+=2*min1(doorz2-max1(z1,z2),min1(z1,z2)-doorz1);
				return min1(p1,p2);
			}
			else if( ((wall1==1 && wall2==4) && (walld==1 && doorx2<=x1 || walld==4 && doory2<=y2))
			  ||((wall1==3 && wall2==4) && (walld==3 && doorx2<=x1 || walld==4 && doory1>=y2))
			  ||((wall1==2 && wall2==3) && (walld==2 && doory1>=y1 || walld==3 && doorx1>=x2))
			  ||((wall1==1 && wall2==2) && (walld==1 && doorx1>=x1 || walld==2 && doory2<=y2)))				/* if they are on adjecent walls */
			  p1+=2*min1( doorz2-max1(z1,z2),min1(z1,z2)-doorz1);
			else
				p2+=2*min1(doorz2-max1(z1,z2),min1(z1,z2)-doorz1);
		}
		return min1(p1,p2);												/* only 2 possible path, return the smaller one */
	}
}


float min4(float x1,float x2,float x3,float x4)
{																		/* return the smallest of 4 float */
	float min;
	min=x1;
	if(x2<min)
		min=x2;
	if(x3<min)
		min=x3;
	if(x4<min)
		min=x4;

	return min;
}

float max4(float x1,float x2,float x3,float x4)
{																		/* return the largest of 4 float */
	float max;
	max=x1;
	if(x2>max)
		max=x2;
	if(x3>max)
		max=x3;
	if(x4>max)
		max=x4;

	return max;
}

int Wall(float x,float y,float Lx,float Ly)
{																		/* this function determines which the outlet is on */
	if(y==0)
		return 1;
	if(x==0)
		return 4;
	if(x==Lx)
		return 2;
	if(y==Ly)
		return 3;
}

Queue InitOL(int NumVertex)
{																/* initiate a series of structs to store the information of outlets */
	int i;
	Queue Q;

	Q=malloc(sizeof(struct queue));
	Q->size=NumVertex;											/* record the number of outlets */

	Q->OL=malloc(NumVertex*sizeof(struct outlet));

	for(i=0;i<Max;i++)
	{
		Q->OL[i]=malloc(sizeof(struct outlet));
	}

	return Q;
}

void CrtGraph(Queue Q,Graph G,
			  float doorx1,float doorx2,float doory1,float doory2,float doorz1,float doorz2,
			  float Lx,float Ly,float Lz)
{														/* initiate the elements of the graph */
	int i,j;

	for(i=0;i<Q->size;i++)
	{
		for(j=i;j<Q->size;j++)
		{
			if(i==j)
				G[i][j]=0;								/* the distance to oneself is 0 */
			else
			{
				G[i][j]=G[j][i]=Dist(doorx1,doorx2,doory1,doory2,doorz1,doorz2,Lx,Ly,Lz,
		Q->OL[i]->x,Q->OL[i]->y,Q->OL[i]->z,Q->OL[j]->x,Q->OL[j]->y,Q->OL[j]->z);
			}											/* G[i][j] stores the distance between outlet i and outlet j */
		}
	}
}

float min1(float x,float y)
{
	if(x<y)
		return x;
	else return y;
}

float max1(float x,float y)
{
	if(x>y)
		return x;
	else return y;
}