maze.cpp

数据结构课程设计报告及代码 C语言环境 迷宫问题的设计

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#define MAXNUM 8


//找到开始位置
PositionType findBegin(PositionType pos[MAXNUM][MAXNUM]){
	int i,j;
	for(i=0;i<MAXNUM;i++){
		for(j=0;j<MAXNUM;j++){
			if(pos[i][j].sign=='2'){
				break;
			}
		}
		if(pos[i][j].sign=='2') break;
	}
	//printf("开始节点是第%d行，%d列%c",i,j,pos[i][j].sign);
	if(i<MAXNUM&&j<MAXNUM){
		return pos[i][j];
	}
	return pos[0][0];
};

//找到结尾
PositionType findEnd(PositionType pos[MAXNUM][MAXNUM]){
	int i,j;
	for(i=0;i<MAXNUM;i++){
		for(j=0;j<MAXNUM;j++){
			if(pos[i][j].sign=='3'){
				break;
			}
		}
		if(pos[i][j].sign=='3') break;
	}
	if(i<MAXNUM&&j<MAXNUM){
		return pos[i][j];
	}
	return pos[MAXNUM-1][MAXNUM-1];
};


void printSign(PositionType pos[MAXNUM][MAXNUM],PositionType * current,char a){
	pos[current->row][current->col].sign=a;
}

//找到下一个位置
PositionType * findNextPosition(PositionType * current,PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
	PositionType pt;
	while(1){
		if(current->nextDirection==5){
			//if(stackEmpty(S)==0){
				printSign(pos,current,'@');
				pop(S,pt);
				//pop(S,pt);
				//pop(S,pt);
				current=&pos[pt.row][pt.col];
				//printf("%d,%d\n",current->row,current->col);
				//current=findNextPosition(current,pos,S);
				return current;
			//} else{
			//	return &pos[MAXNUM-1][MAXNUM-1];
			//}
		}

		if(current->nextDirection==1){
			pos[current->row][current->col].nextDirection++;
			if(pos[current->row][current->col+1].sign=='0'||pos[current->row][current->col+1].sign=='1'||pos[current->row][current->col+1].sign=='3'){				
				current=&pos[current->row][current->col+1];
				return current;				
			}
			//break;
		}
		if(current->nextDirection==2){
			pos[current->row][current->col].nextDirection++;
			if(pos[current->row-1][current->col].sign=='0'||pos[current->row-1][current->col].sign=='1'||pos[current->row-1][current->col].sign=='3'){				
				current=&pos[current->row-1][current->col];
				return current;
			}
			//break;
		}
		if(current->nextDirection==3){
			pos[current->row][current->col].nextDirection++;
			if(pos[current->row][current->col-1].sign=='0'||pos[current->row][current->col-1].sign=='1'||pos[current->row-1][current->col].sign=='3'){				
				current=&pos[current->row][current->col-1];
				return current;
			}			
			//break;
		}
		if(current->nextDirection==4){
			pos[current->row][current->col].nextDirection++;
			if(pos[current->row+1][current->col].sign=='0'||pos[current->row+1][current->col].sign=='1'||pos[current->row+1][current->col].sign=='3'){				
				current=&pos[current->row+1][current->col];
				return current;
			}
			if(pos[current->row+1][current->col].sign=='@'||pos[current->row+1][current->col].sign=='#'){
				pop(S,pt);
			}
			//break;
		}		
	}
}


//将迷宫打印出来
void print(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
	int i,j;
	for(i=0;i<MAXNUM;i++){
		for(j=0;j<MAXNUM;j++){
			if(pos[i][j].sign=='*'){
				//textcolor(RED);
				switch(pos[i][j].nextDirection){
				case 1:
				case 2:
					printf("→");
					break;
				case 3:
					printf("↑");
					break;
				case 4:
					printf("←");
					break;
				case 5:
					printf("↓");
					break;
				}
			}else if(pos[i][j].sign=='1'||pos[i][j].sign=='0'||pos[i][j].sign=='@'||pos[i][j].sign=='#'||pos[i][j].sign=='3'){
				printf("%c ",pos[i][j].sign);
			} else{
				printf(" ");
			}
		}
		printf("\n");
	}
}

//返回类型为整形，0表示找不到起点，1表示找不到终点，2表示找到路径，3表示找不到路径
int mazePath(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
	//LinkStack S;
	PositionType begin;
	PositionType end;
	PositionType pt;
	PositionType * current;
	PositionType * point;
	begin=findBegin(pos);	
	if(begin.row==0&&begin.col==0){
		return 0;
	}
	end=findEnd(pos);
	if(end.row==MAXNUM-1&&end.col==MAXNUM-1){
		return 1;
	}
	current=&begin;//初始时指向开始位置
	//printf("%c",current->sign);
	int allStep=0;
	initStack(S);
	//主循环体
	do{
		switch(current->sign){
			case '1':
			case '2':
				point=current;				
				current=findNextPosition(&pos[current->row][current->col],pos,S);   //找到下一个节点
				printSign(pos,point,'*');
				push(S, pos[point->row][point->col]);
				break;
			case '3':
				//printf("当前的符号是%c,当前元素在第%d行，第%d列, nextDirection的值是%d\n",current->sign,current->row,current->col,current->nextDirection);
				push(S,pos[current->row][current->col]);
				break;
			case '0':
				printSign(pos,&pos[current->row][current->col],'#');
				pop(S,pt);
				current=&pos[pt.row][pt.col];
				break;
			case '*':
				if(current->nextDirection!=5){
					push(S, *current);
				}
				current=findNextPosition(&pos[current->row][current->col],pos,S);   //找到下一个节点
				break;
		}
		allStep++;
		/*printf("第%d次循环\n",allStep);
		printf("第1行第4列的nextDirection值是%d\n",pos[1][4].nextDirection);
		getTop(S,pt);
		printf("当前栈的高度是%d\n",stackLength(S));
		printf("栈顶的符号是%c,栈顶元素在第%d行，第%d列，nextDirection的值是%d\n",pos[pt.row][pt.col].sign,pos[pt.row][pt.col].row,pos[pt.row][pt.col].col,pos[pt.row][pt.col].nextDirection);
		printf("当前的符号是%c,当前元素在第%d行，第%d列, nextDirection的值是%d\n",current->sign,current->row,current->col,current->nextDirection);
		print(pos);*/
	} while(stackEmpty(S)==0 && pos[current->row][current->col].sign!='3');	
	if(stackLength(S)!=0){
		//printf("此次路径共走了%d步,共循环了%d次。\n",stackLength(S),allStep);	
		//getTop(S,pt);
		//printf("栈顶的符号是%c,栈顶元素在第%d行，第%d列，nextDirection的值是%d\n",pos[pt.row][pt.col].sign,pos[pt.row][pt.col].row,pos[pt.row][pt.col].col,pos[pt.row][pt.col].nextDirection);
		//printf("%d",stackLength(S));
		//printf("该迷宫不存在通路！");
		return 2;
	} else{ 
		//printf("该迷宫不存在通路！");
		return 3;		
	}
	
}

//返回另外一条通路，1表示迷宫不存在通路，2表示还有其他通路
int findAnotherPath(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
	PositionType pt;
	int allStep=0;
	PositionType * current;
	PositionType * point;
	//pop(S,pt);
	pop(S,pt);
	current=&pos[pt.row][pt.col];
	do{
		switch(current->sign){
			case '1':
			case '2':
				point=current;				
				current=findNextPosition(&pos[current->row][current->col],pos,S);   //找到下一个节点
				printSign(pos,point,'*');
				push(S, pos[point->row][point->col]);
				break;
			case '3':
				//printf("当前的符号是%c,当前元素在第%d行，第%d列, nextDirection的值是%d\n",current->sign,current->row,current->col,current->nextDirection);
				push(S,pos[current->row][current->col]);
				break;
			case '0':
				printSign(pos,&pos[current->row][current->col],'#');
				pop(S,pt);
				current=&pos[pt.row][pt.col];
				break;
			case '*':
				if(current->nextDirection!=5){
					push(S, *current);
				}
				current=findNextPosition(&pos[current->row][current->col],pos,S);   //找到下一个节点
				break;
		}
		allStep++;
		//printf("查找其他路径的第%d次循环\n",allStep);
		//printf("第1行第4列的nextDirection值是%d\n",pos[1][4].nextDirection);
		//getTop(S,pt);
		//printf("当前栈的高度是%d\n",stackLength(S));
		//printf("栈顶的符号是%c,栈顶元素在第%d行，第%d列，nextDirection的值是%d\n",pos[pt.row][pt.col].sign,pos[pt.row][pt.col].row,pos[pt.row][pt.col].col,pos[pt.row][pt.col].nextDirection);
		//printf("当前的符号是%c,当前元素在第%d行，第%d列, nextDirection的值是%d\n",current->sign,current->row,current->col,current->nextDirection);
		//print(pos,S);
	} while(stackEmpty(S)==0 && pos[current->row][current->col].sign!='3');
		if(stackEmpty(S)==1){			
			return 1;
		}
		if(pos[current->row][current->col].sign=='3'){
			//printf("该迷宫还有其他通路！");
			return 2;
		}
}

int findOtherPathes(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
	int state=2;
	int pathNumber=1;
	//printf("该迷宫的其他通路");
	while(state==2){			
		pathNumber++;		
		state=findAnotherPath(pos,S);
		//printf("该迷宫的其他通路");
		if(state==2){
			printf("第%d条路径\n",pathNumber);
			print(pos,S);
		}
	}
	return pathNumber;
}

int findPathNum(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
	int state=2;
	int pathNumber=0;
	//printf("该迷宫的其他通路");
	while(state==2){			
		pathNumber++;		
		state=findAnotherPath(pos,S);
	}
	return pathNumber;
}

void firstIntroduction(){
	int i;
	for(i=0;i<25;i++){
		printf("  *");
	}
	printf("\n    请输入字母来完成选择您要执行的操作........\n\n");
	printf("    输入c迷宫将按照默认的方式创建\n");
	printf("    输入f后系统将按照您指定的文件来创建迷宫\n");
	for(i=0;i<25;i++){
		printf("  *");
	}
	printf("\n\n\n");
}

void secondIntroduction(){
	int i;
	for(i=0;i<25;i++){
		printf("  *");
	}
	printf("\n    请输入字母来完成选择您要执行的操作........\n\n");
	printf("    输入l将可以看到系统给您找到的默认路径\n");
	printf("    输入n可查看当前迷宫共有多少条路径\n");
	printf("    输入a将可以看到所有迷宫路径\n");
	printf("    输入q将退出系统\n");
	for(i=0;i<25;i++){
		printf("  *");
	}
	printf("\n\n\n");
}

void printDefaultPath(PositionType pos[MAXNUM][MAXNUM]){
	LinkStack S;
	int state;
	state=mazePath(pos,S);
	if(state==0){
		printf("没有找到开始节点！");
		exit(1);
	}
	if(state==1){
		printf("没有找到终点！");
		exit(1);
	}
	if(state==2){
		print(pos,S);
		//getTop(S,pt);
		//printf("栈顶的符号是%c,栈顶元素在第%d行，第%d列，nextDirection的值是%d\n",pos[pt.row][pt.col].sign,pos[pt.row][pt.col].row,pos[pt.row][pt.col].col,pos[pt.row][pt.col].nextDirection);
		//printf("此次路径共走了%d步.\n",stackLength(S));
		destroyStack(S);
	}
	if(state==3){
		printf("该迷宫没有通路！");
		exit(1);
	}
}

void printAllPath(PositionType pos[MAXNUM][MAXNUM]){
	LinkStack S;
	int state,pathNumber=1;
	state=mazePath(pos,S);
	if(state==0){
		printf("没有找到开始节点！");
		exit(1);
	}
	if(state==1){
		printf("没有找到终点！");
		exit(1);
	}
	if(state==2){
		printf("第1条路径\n");
		print(pos,S);
		//getTop(S,pt);
		//printf("栈顶的符号是%c,栈顶元素在第%d行，第%d列，nextDirection的值是%d\n",pos[pt.row][pt.col].sign,pos[pt.row][pt.col].row,pos[pt.row][pt.col].col,pos[pt.row][pt.col].nextDirection);
		//printf("此次路径共走了%d步.\n",stackLength(S));
		pathNumber=findOtherPathes(pos,S);
		destroyStack(S);
	}
	if(state==3){
		printf("该迷宫没有通路！");
		exit(1);
	}
}

void printPathNum(PositionType pos[MAXNUM][MAXNUM]){
	LinkStack S;
	int state,pathNumber=1;
	state=mazePath(pos,S);
	if(state==0){
		printf("没有找到开始节点！");
		exit(1);
	}
	if(state==1){
		printf("没有找到终点！");
		exit(1);
	}
	if(state==2){
		pathNumber=findPathNum(pos,S);
		printf("     迷宫的路径数目为%d\n",pathNumber);
		destroyStack(S);
	}
	if(state==3){
		printf("该迷宫没有通路！");
		exit(1);
	}	
}

//使后面的数组和前面的数组的值相等
void same(PositionType pos[MAXNUM][MAXNUM],PositionType posCopy[MAXNUM][MAXNUM]){
	int i,j;
	for(i=0;i<MAXNUM;i++){
		for(j=0;j<MAXNUM;j++){
			posCopy[i][j]=pos[i][j];
		}
	}
}

void main(){	
	PositionType pos[MAXNUM][MAXNUM],posCopy[MAXNUM][MAXNUM];
	char array[MAXNUM][MAXNUM],string;
	int i,j,pathNumber=0,row,col;
	//LinkStack S;
	char fileName[10];
	FILE *file;
	char command;
	firstIntroduction();
	scanf("%c",&command);
	if(command=='c'){
		char array[MAXNUM][MAXNUM]={
			{'0','0','0','0','0','0'},
			{'0','2','1','1','1','0'},
			{'0','1','1','0','1','0'},
			{'0','1','1','1','3','0'},
			{'0','0','0','0','0','0'}
		};
		//使迷宫初始化
		for(i=0;i<MAXNUM;i++){
			for(j=0;j<MAXNUM;j++){
				pos[i][j].row=i;
				pos[i][j].col=j;
				pos[i][j].nextDirection=1;
				pos[i][j].sign=array[i][j];
			}
		}
		same(pos,posCopy);
		printf("创建系统默认的迷宫成功！\n");
	}
	if(command=='f'){
		printf("请输入文件名称，如a.txt\n");
		scanf("%s",fileName);
		if((file=fopen(fileName,"r"))==NULL){
			printf("您输入的文件不存在！\n");
			exit(1);
		};
		row=fgetc(file);
		row-=48;
		fgetc(file);
		col=fgetc(file);
		col-=48;
		//printf("%d,%d",row,col);
		fgetc(file);
		//printf("%c",fgetc(file));
		//printf("%c",fgetc(file));
		for(i=0;i<row;i++){
			for(j=0;j<col;j++){
				string=fgetc(file);
				array[i][j]=string;
				fgetc(file);
			}
			printf("\n");
		}

		for(i=0;i<MAXNUM;i++){
			for(j=0;j<MAXNUM;j++){
				pos[i][j].row=i;
				pos[i][j].col=j;
				pos[i][j].nextDirection=1;
				pos[i][j].sign=array[i][j];
			}
		}
		same(pos,posCopy);

		printf("创建有文件生成的迷宫成功！\n");
	}
	if(command=='q'){
		exit(1);
	}

	//	
	do{
		scanf("%c",&command);
		if(command=='l'){
			printDefaultPath(pos);
			same(posCopy,pos);
		}else if(command=='a'){
			printAllPath(pos);
			same(posCopy,pos);
		}else if(command=='n'){
			printPathNum(pos);
			same(posCopy,pos);
		} else{
			secondIntroduction();
		}
	} while(command!='q');

}