maze.c

dfs 深度优先搜索！这是走迷宫的基本算法。用广义表建立迷宫

#include <stdio.h>
#include <stdlib.h>

typedef char VertexType;
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
	VertexType data;
	ArcNode *firstarc;
}VNode;
int FirstAdjVex(VNode *AdjList,int v){
	ArcNode *p;
	p=(AdjList+v)->firstarc;
	if(p)
		return p->adjvex;
	return -1;
}
int NextAdjVex(VNode *AdjList,int v,int w){
	ArcNode *p;
	p=(AdjList+v)->firstarc;
	while(p){
		if(p->adjvex==w)
			if(p->nextarc)
				return p->nextarc->adjvex;
		p=p->nextarc;
	}
	return -1;
}
int DFSearch(VNode *AdjList,int v,VertexType s,int *visited,char *path){
	int w;
	*(visited+v)=1;
	*path=(AdjList+v)->data;
	path++;
	*path='\0';
	if((AdjList+v)->data==s)
		return 1;
	for(w=FirstAdjVex(AdjList,v);w!=-1;w=NextAdjVex(AdjList,v,w))
		if(*(visited+w)==0)
			if(DFSearch(AdjList,w,s,visited,path))
				return 1;
	path--;
	*path='\0';
	return 0;
}
int Locate(VNode *AdjList,VertexType s,int w){
	int i;
	for(i=0;i<w-1;i++)
		if(s==(AdjList+i)->data)
			return i;
	if(i==w-1)
		return -1;
}
void main(){
	VNode *AdjList;
	ArcNode *p;
	int *visited;
	char *path;
	char *s;
	char t[100];
	int w=1;
	int i;
	FILE *fp;

	if(!(fp=fopen("maze.txt","r")))
		return;
	s=fgets(t,100,fp);
	while(*s!='\0'){
		if(*s>='a'&&*s<='z')
			if(w==1){
				AdjList=(VNode *)malloc(sizeof(VNode));
				AdjList->data=*s;
				AdjList->firstarc=NULL;
				w++;
			}
			else{
				AdjList=(VNode *)realloc(AdjList,w*sizeof(VNode));
				(AdjList+w-1)->data=*s;
				(AdjList+w-1)->firstarc=NULL;
				w++;
			}
		s++;
	}
	s=fgets(t,100,fp);
	while(*s!='(')
		s++;
	s++;
	while(*s!='\0'){
		if(*s=='('){
			s++;
			while(*s<'a'||*s>'z')
				s++;
			i=Locate(AdjList,*s,w);
			s++;
			while(*s<'a'||*s>'z')
				s++;
			if((AdjList+i)->firstarc==NULL){
				(AdjList+i)->firstarc=(ArcNode *)malloc(sizeof(ArcNode));
				(AdjList+i)->firstarc->adjvex=Locate(AdjList,*s,w);
				(AdjList+i)->firstarc->nextarc=NULL;
			}
			else{
				p=(AdjList+i)->firstarc;
				while(p->nextarc!=NULL)
					p=p->nextarc;
				p->nextarc=(ArcNode *)malloc(sizeof(ArcNode));
				p->nextarc->adjvex=Locate(AdjList,*s,w);
				p->nextarc->nextarc=NULL;
			}
		}
		s++;
	}
	visited=(int *)malloc((w-1)*sizeof(int));
	for(i=0;i<w-1;i++)
		visited[i]=0;
	path=(char *)malloc(w*sizeof(char));
	i=DFSearch(AdjList,0,(AdjList+w-2)->data,visited,path);
	if(i)
		printf("%s\n",path);
	else
		printf("Can't find a path!\n");
}