project3-2.c

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

/*===============================Program Description=======================================*/
/*                                                                                         */
/* NAME:Project 3-2                                                                        */
/* Purpose:Design a program to simulate the process of finding the shortest path           */
/* written by WangMeng.                                                                    */
/*                                                                                         */
/*=========================================================================================*/

/*=============================The corresponding files are included here===================*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <malloc.h>

/*=================Definition about some data types I use in the program===================*/

struct stack;
struct treenode;
typedef struct treenode *ptrnode;
typedef ptrnode node;
typedef struct stack *ptrnodestack;
typedef ptrnodestack stacknode; 
stacknode S1;
stacknode S2;
stacknode S;
stacknode travelS1;
stacknode travelS2;
stacknode travelS;
stacknode shortesttravelstack;
int staticstart;
int staticend;
int V[50][50];			/*The matrix which used to save the distance between the sites*/
int vertex[50];			/*The array to save if the vertex has been visited*/
int flag=0;





struct stack			/*The stack used in the programme*/	
{
	int num;
	stacknode next;
};

struct treenode			/*A tree used in the process of finding all of the ways*/
{	int num;
	node child[50];
	node father;
};

struct info				/*The struct which used to save the information of the sites*/
{
	char name[30];
	char siteinfo[50];
}info[50];

/*=========================== Functions Declaration  =================================*/

void error(int a);
void constructtree(node T,int start,int end);
void alltravelpathtree(node T,int start);
void popcheck();
int outdegree(int vertex);
int check(int p,stacknode P);


/*================================== Function table =========================================*/
void install()            /*The function used to install the matrix*/
{                         /*If the two sites are not connected,the distance is 10000*/
    int i,j;
	for(i=0;i<50;i++)
		for(j=0;j<50;j++)
		{
			V[i][j]=10000;
		}
}

/*=========================The function used to operate on the stack ========================*/
int IsEmpty(stacknode P)			/*Check if the stack is empty*/
{
	return P->next==NULL;
}

void Push(int x,stacknode P)		/*Push the element x into the stack*/
{
	stacknode tempcell;
	tempcell=malloc(sizeof(struct stack));
	if(tempcell==NULL)
		error(0);
	else
	{
		tempcell->num=x;
		tempcell->next=P->next;
		P->next=tempcell;
	}
}


int Top(stacknode P)				/*Return the top elemnent of the stack*/
{
	if(!IsEmpty(P))
		return P->next->num;
	error(0);
	return 0;
}

void Pop(stacknode P)				/*Pop the top element of the stack*/
{
	stacknode firstcell;
	firstcell=malloc(sizeof(stacknode));
	if(IsEmpty(P))
		error("The stack cannot be poped");
	else
	{
		firstcell=P->next;
		P->next=P->next->next;
		free(firstcell);
	}
}

void MakeEmpty(stacknode P)			/*Make the stack empty*/
{
	if(P==NULL)
		error("The stack cannot be maked empty!");
	else 
		while(!IsEmpty(P))
			Pop(P);
}

stacknode CreatStack()				/*Creat the stack,give it a save space*/
{
	stacknode P;
	P=malloc(sizeof(struct stack));
	if(P==NULL)
		error("The stack cannot be created!");
	P->next=NULL;
	return P;
}

int alltravelpath(int maxvertexnum)	/*find all of the path which travels all sites*/
{
	int i;
	int q[100];
	int shortestlength=10000,l;		/*Install the shoertestlength to be a value large enough*/
	node traveltree;
	stacknode midtravelS;
	stacknode tempshortS;
	tempshortS=CreatStack();
	midtravelS=CreatStack();
	traveltree=malloc(sizeof(struct treenode));
	if(traveltree==NULL)
		error("The travel cannot be created!\n");
	for(i=0;i<50;i++)				/*Install vertex's elements to be -1*/
		vertex[i]=-1;
	for(i=1;i<=maxvertexnum;i++)	/*Make the elements in the vertex which stands a site to be 0*/
		vertex[i]=0;
	traveltree->num=1;
	vertex[traveltree->num]=1;
	alltravelpathtree(traveltree,traveltree->num);
	while(travelS->next!=NULL)		/*Find the shortest path from all the path,and calculate it's length*/
	{
		for(i=0;i<100;i++)
			q[i]=0;
		if(travelS->next->next!=NULL&&travelS->next->num==0)
			Pop(travelS);
		while(travelS->next!=NULL&&travelS->next->num!=0)
		{
			Push(Top(travelS),midtravelS);
			Pop(travelS);
		}
		for(i=0;midtravelS->next!=NULL;i++)
		{
			q[i]=Top(midtravelS);
			Pop(midtravelS);
		}
		for(i=0,l=0;q[i+1]!=0;i++)
		{
			if(V[q[i]][q[i+1]]<10000)
				l=l+V[q[i]][q[i+1]];
			else
				l=l+V[q[i+1]][q[i]];
		}
		if(shortestlength>l)		/*If the path is the shortest path,save it in shortestlength*/
		{							/*and save the path in the stack tempshotS*/
			shortestlength=l;
			while(tempshortS->next!=NULL)
				Pop(tempshortS);
			for(i=0;q[i]!=0;i++)
				Push(q[i],tempshortS);
		}
	}
	while(tempshortS->next!=NULL)	/*Make the path to save in the correct order to make the output easier*/
	{
		Push(Top(tempshortS),shortesttravelstack);
		Pop(tempshortS);
	}
	return shortestlength;			/*Return the length of the shortest path whick travels all sites*/
}


void alltravelpathtree(node T,int start)	/*Find all paths which travel all sites*/
{
	int knownum=0;							/*The variable to judge if the vertex is visited*/
	int i,j=0;
	int temp;
	int m,n;
	node tempnode;
	node *tempT[50];
	for(i=0;i<50;i++)
	{
		if(vertex[i]==0)
			knownum++;
	}
	if(knownum!=0)						/*If the vertex has not been visited,do the next*/
	{
		temp=start;
		for(i=0;i<50;i++)
			T->child[i]=NULL;
		for(i=0;i<50;i++)									/*To check if there are vertexes which is connected to it*/
		{	if(V[temp][i]<10000&&vertex[i]!=1)				/*if there are, put there address into T's child array*/
			{	tempnode=malloc(sizeof(struct treenode));
				if(tempnode==NULL)
					error("Tempnode cannot be created!\n");
				T->child[j]=tempnode;
				tempnode->father=T;
				tempnode->num=i;
				j++;
			}	
		}
		for(i=0;T->child[i]!=NULL;i++)				/*For every child*/
		{	
			vertex[T->child[i]->num]=1;
			if(travelS->next==NULL)
				Push(1,travelS);
			if(travelS1->next==NULL)
			{
				Push(0,travelS1);
				Push(1,travelS1);
			}
			if(flag==1)						/*If all sites have been visited*/
			{
				while(travelS1->next!=NULL)
				{
					Push(Top(travelS1),travelS2);
					Pop(travelS1);
				}
				while(travelS2->next!=NULL)
				{
					Push(Top(travelS2),travelS);
					Push(Top(travelS2),travelS1);
					Pop(travelS2);
				}
				flag=0;
			}
			Push(T->child[i]->num,travelS);		/*Put the child into the stack which saves all paths*/
			Push(T->child[i]->num,travelS1);
			alltravelpathtree(T->child[i],T->child[i]->num);	/*For the child, do the steps above again*/
			vertex[T->child[i]->num]=0;
			if(travelS1->next!=NULL)
				Pop(travelS1);
		}
		if(j==0&&T->num!=1)					/*If no chiids but not all sites have been visited,turn to his father*/
		{
			Push(T->father->num,travelS);
			Push(T->father->num,travelS1);
			for(m=0;m<50;m++)
				tempT[m]=T->father->child[m];
			alltravelpathtree(T->father,T->father->num);
			for(m=0;m<50;m++)				/*Save the old address of T's father*/
				T->father->child[m]=tempT[m];
			if(travelS1->next!=NULL)
				Pop(travelS1);
		}
	}
	else
		flag=1;								/*If all sites have been visited,make flag equal to 1*/
}
		
void allpath()            /*The function to find all path between every two sites*/
{
	int start,end;
	int i=0,j=0;
	node Tree;
	printf("Enter the start site's number\n");
	scanf("%d",&start);
	printf("Enter the end site's number\n");
	scanf("%d",&end);
	Tree=malloc(sizeof(struct treenode));
	if(Tree==NULL)
		error("The tree cannot be created!");
	Tree->father=NULL;
	Tree->num=start;
	staticstart=start;
	staticend=end;
	constructtree(Tree,start,end);
}

void constructtree(node T,int start,int end)  /*The function to construct the tree*/
{	
	int i,j=0,m,n,q;
	int temp;
	node tempnode;
	if(T->num!=end&&outdegree(T->num))
	{
		temp=start;
		for(i=0;i<50;i++)
			T->child[i]=NULL;
		for(i=0;i<50;i++)					/*To check if there are vertexes which is connected to it*/
		{	if(V[temp][i]<10000)			/*if there are, put there address into T's child array*/
			{	tempnode=malloc(sizeof(struct treenode));
				if(tempnode==NULL)
					error(1);
				T->child[j]=tempnode;
				tempnode->father=T;
				tempnode->num=i;
				j++;
			}	
		}
		for(i=0;T->child[i]!=NULL;i++)		/*For every child*/
		{	
			if(S->next==NULL)
					Push(staticstart,S);
			if(S->next->next!=NULL&&S->next->next->next!=NULL&&S->next->next->num==end)