project3-2.c

解决一个加权遍历的问题。 文件包含一个word文档

			{								/*If the one path is finded,push the vertex that will not be put in the next recursion*/
				while(S1->next!=NULL)
				{
					Push(Top(S1),S2);
					Pop(S1);
				}
				while(S2->next!=NULL)
				{
					Push(Top(S2),S);
					Push(Top(S2),S1);
					Pop(S2);
				}
			}
			Push(T->child[i]->num,S);		/*Put the child into the stack which saves all paths*/
			Push(T->child[i]->num,S1);
			if(T->child[i]->num==staticend)
			{
				Push(staticstart,S);
			}
			if(check(T->child[i]->num,S))		/*Check if there is a cycle in the path.If not,do the next*/ 
				constructtree(T->child[i],T->child[i]->num,end);		/*For the child, do the steps above again*/
			if(S->next->num!=end&&S->next->num!=staticstart)
					Pop(S);
			if(S1->next!=NULL)
				Pop(S1);
		}
	}
}

int check(int p,stacknode P)     /*The function to check if there is a cycle*/
{                                /*return 1 if no cycle and 0 if yes*/
	stacknode checkstack;
	checkstack=CreatStack();
	
	if(P->next->num==staticstart)
	{
		Push(Top(P),checkstack);
		Pop(P);
	}
	if(P->next==NULL)
	{
		while(checkstack->next!=NULL)
		{
			Push(Top(checkstack),P);
			Pop(checkstack);
		}
		return 1;
	}
	Push(Top(P),checkstack);
	Pop(P);
	while(P->next->num!=staticstart)
	{
		if(Top(P)==p)
		{
			while(checkstack->next!=NULL)
			{
				Push(Top(checkstack),P);
				Pop(checkstack);
			}
			return 0;
		}
		Push(Top(P),checkstack);
		Pop(P);
	}
	while(checkstack->next!=NULL)
	{
		Push(Top(checkstack),P);
		Pop(checkstack);
	}
	return 1;

}

void error(char *error)     /*The error function*/
{
	printf("%s\n",error);
}

int outdegree(int vertex)   /*The function to check outdegreeof the vertex*/
{							/*return 0 if the outdegree of the vertex is 0 and 1 if not*/
	int i,j=0;
	for(i=0;i<50;i++)
	{	if(V[vertex][i]<10000)
			j++;
	}
	if(j==0)
		return 0;					
	else
		return 1;
}


			

/***************************************main function***********************************/



void main()
{	
	FILE *fpin1,*fpin2,*fpout;
	int t,a,p,m,n,u,w;
	int x,y,z=0;
	int i=0,j;
	int tem=0,length=0,vertexnum;
	int start,end,teml;
	char c[30],b[50];
	int q[50];
	int savearray[100];
	int l,shortl=10000;
	int shortesttravellength;
	stacknode midS,tempshortS,saveS,shortS;
	
					
	
	install();						/*Install the distance matrix*/					
	midS=CreatStack();				/*Creat the stack needed*/
	shortS=CreatStack();
	saveS=CreatStack();
	tempshortS=CreatStack();   
	travelS1=CreatStack();
	travelS2=CreatStack();
	travelS=CreatStack();
	shortesttravelstack=CreatStack();
	S1=CreatStack();
	S2=CreatStack();
	S=CreatStack();
					
	printf("The information of the sites:\n");
	for(i=0;i<50;i++)				/*Install the infomation struct*/
	{
		for(j=0;j<30;j++)
		   info[i].name[j]=0;
		for(j=0;j<50;j++)
		   info[i].siteinfo[j]=0;
	}
	if((fpin2=fopen("input2.txt","r"))==NULL||(fpin1=fopen("input1.txt","r"))==NULL||(fpout=fopen("output.txt","w"))==NULL)
	{
		printf("can not open file\n");
		exit(0);
	}
   
	while((fscanf(fpin1, "%d", &x))!=EOF&&x!=0)   /*Read the file input1.txt*/
	{
		j=0;
		vertexnum=x;
loop1:	fscanf(fpin1,"%s",b);
		for(i=0;j<30&&b[i]!=0;i++,j++)	
		    info[x].name[j]=b[i];
		if(b[i-1]!=')')
		{
			info[x].name[j]=' ';
			j++;
			goto loop1;
		}
		j=0;
loop2:	fscanf(fpin1,"%s",c);
		for(i=0;j<50&&c[i]!=0;i++,j++)
			info[x].siteinfo[j]=c[i];
		if(c[i-1]!=')')
		{
			info[x].siteinfo[j]=' ';
			j++;
			goto loop2;
		}
	}
	j=0;
	for(i=0;i<50;i++)							/*Print the information in input1.txt*/
	{
		if(info[i].name[0]!=0)
		{
			printf("%d ",i);	
			for(j=0;j<30&&info[i].name[j]!=0;j++)
				printf("%c",info[i].name[j]);
			printf(" ");
			for(j=0;j<50&&info[i].siteinfo[j]!=0;j++)
				printf("%c",info[i].siteinfo[j]);
			printf("\n");
		}
	}
	
	printf("\nThe distance between the sites:\n");
	i=3;
	while ((fscanf(fpin2, "%d", &a))!=EOF&&a!=0)   /*Read and print the information in input2.txt*/
	{	i++;
		if((i%3)==1)
			m=a;
		if((i%3)==2)
			n=a;
		if((i%3)==0)
			{p=a;
			 V[m][n]=p;
			 printf("V[%d][%d]=%d\n",m,n,V[m][n]);
			}
	}
	shortesttravellength=alltravelpath(vertexnum);	/*Use the function to find the shortest path which traevels all sites,and return its length*/
	fprintf(fpout,"The shortest distance path from the gate to travel all the sites: the total distance=%d\n",shortesttravellength);	/*Output the shortest path's length which travels all sites into output.txt*/
	while(shortesttravelstack->next!=NULL)			/*Output the shortest into output.txt*/
	{
		
		if(Top(shortesttravelstack)==1&&z==0)
		{
			fprintf(fpout,"%d %s (0 meter)",Top(shortesttravelstack),info[Top(shortesttravelstack)].name);
			z=Top(shortesttravelstack);
			Pop(shortesttravelstack);
		}
		else
		{
			fprintf(fpout,"->");
			if(V[z][Top(shortesttravelstack)]<10000)
				fprintf(fpout,"%d %s (%d meters)",Top(shortesttravelstack),info[Top(shortesttravelstack)].name,V[z][Top(shortesttravelstack)]);
			else
				fprintf(fpout,"%d %s (%d meters)",Top(shortesttravelstack),info[Top(shortesttravelstack)].name,V[Top(shortesttravelstack)][z]);
			z=Top(shortesttravelstack);
			Pop(shortesttravelstack);
		}
	}
	fprintf(fpout,"\n\n\n");
		
	allpath();							/*Use the function to find all path*/
	for(i=0;i<100;i++)
		savearray[i]=0;
	if(S->next==NULL)
		fprintf(fpout,"No path between the two sites! From %s To %s\n",info[staticstart].name,info[staticend].name);
	if(S->next!=NULL)
	{
		if(S->next!=NULL&&S->next->num==staticstart)		/*The following code are operate on the stack*/
			Pop(S);							/*to make sure that it output in the right order*/
		while(S->next!=NULL)
		{
			Push(Top(S),saveS);
			Pop(S);
		}
		for(i=0;saveS->next!=NULL;i++)		/*Put all paths between the two sites choosen*/
		{
			Push(Top(saveS),S);
			savearray[i]=Top(saveS);
			Pop(saveS);
		}

		while(saveS->next!=NULL)
		{	
			Pop(saveS);
		}
		
		while(S->next!=NULL)				/*Find the shortest path between the two sites,and calculate it's length*/
		{
			for(i=0;i<50;i++)
				q[i]=0;
			Push(Top(S),midS);
			Pop(S);
			while(S->next!=NULL&&S->next->num!=staticend)
			{
				Push(Top(S),midS);
				Pop(S);
			}
			for(i=0;midS->next!=NULL;i++)
			{
				q[i]=Top(midS);
				Pop(midS);
			}
			for(i=0,l=0;q[i+1]!=0;i++)
			{
				l=l+V[q[i]][q[i+1]];
			}
			if(shortl>l)					/*If the path it's the shortest path,save it in shortl*/
			{
				shortl=l;					/*and save the path in the stack tempshotS*/
				while(tempshortS->next!=NULL)
					Pop(tempshortS);
				for(i=0;q[i]!=0;i++)
					Push(q[i],tempshortS);
			}
		}
		while(tempshortS->next!=NULL)		/*Make the elements in tempshortS in the correct order*/
		{
			Push(Top(tempshortS),shortS);
			Pop(tempshortS);
		}
		printf("\n");	
		fprintf(fpout,"The shortest distance path: the total distance=%d\n",shortl);
		while(shortS->next!=NULL)			/*Output the shortest into output.txt*/
		{
			
			if(Top(shortS)==staticstart)
			{
				fprintf(fpout,"%d %s (0 meter)",Top(shortS),info[Top(shortS)].name);
				y=Top(shortS);
				Pop(shortS);
			}
			else
			{
				fprintf(fpout,"->");
				fprintf(fpout,"%d %s (%d meters)",Top(shortS),info[Top(shortS)].name,V[y][Top(shortS)]);
				y=Top(shortS);
				Pop(shortS);
			}
		}
		fprintf(fpout,"\n\n\n");
		fprintf(fpout,"All paths between the two sites: From %s To %s\n",info[staticstart].name,info[staticend].name); 
		for(i=0,t=1;savearray[i]!=0;t++)	/*Output all of the path into output.txt*/
		{
			fprintf(fpout,"Path%d : ",t);
			for(;savearray[i]!=staticend;i++)
			{
				if(savearray[i]==staticstart)
					fprintf(fpout,"%d %s (0 meters)",savearray[i],info[savearray[i]].name);
				else
				{
					fprintf(fpout,"->");
					fprintf(fpout,"%d %s (%d meters)",savearray[i],info[savearray[i]].name,V[savearray[i-1]][savearray[i]]);
				}
			}
			fprintf(fpout,"->");
			fprintf(fpout,"%d %s (%d meters)\n",savearray[i],info[savearray[i]].name,V[savearray[i-1]][savearray[i]]);
			i++;
		}
	}
	fprintf(fpout,"\n\n\n");
	fclose(fpin1);						/*Close the files*/
    fclose(fpin2);						/*Close the files*/
	fclose(fpout);						/*Close the files*/
	printf("Please see the file named 'output.txt' in the directory which the program in!\n");
}