kjh.cpp

学习中自己编的一些小程序

#include <stdio.h>
#include<stdlib.h>
#include<conio.h>
#define  H  6
#define  L  6
#define  Maxsize  100		//栈可能达到的容量

typedef struct
{
	int x,y,d;
}Datatype;                  //定义坐标结构体
typedef struct               
{
  Datatype data[Maxsize];   //栈的元素为坐标结构体类型
  int top;                  //栈顶元素的下标
}SeqStack;                  //定义栈
/*****************************************************************************/
void StackInit(SeqStack *st)  
//清空
{
  	st->top=-1;
}
/*****************************************************************************/
int StackIsEmpty(SeqStack st) 
 //栈空，返回1；否则返回0
{
  	if (st.top>=0) return 0;
  	else return 1;
}
/*****************************************************************************/
int StackPush(SeqStack *st,Datatype x)
// 元素x进栈，成功返回1，失败返回0
{
  	if (st->top==Maxsize-1)              //上溢
    	{ printf("stack overflow!\n");return 0;}
  	else
    	{ 	st->top++;
      		st->data[st->top]=x;
		return 1;
	}
}
/*****************************************************************************/
int StackOut(SeqStack *st)
//出栈(成功返回1，失败返回0）
{
  	if (StackIsEmpty(*st))                          //下溢
    	{printf("stack underflow!\n");return 0;}
  	else
    	{ 	st->top--;
      		return 1;
    	}
}
/*****************************************************************************/
Datatype StackTop(SeqStack st)
// 返回栈顶元素，成功返回1，失败返回0
{
  	if (StackIsEmpty(st))                      //空栈
     	{ printf("underflow\n"); }
  	else 
	{return st.data[st.top];}
}
/*****************************************************************************/
void StackPrint(SeqStack st)
/*将栈st中所有元素从底到顶输出，此时正好是一条路径*/
{ 
	int i;
	printf("\n迷宫的一条路径：\n");
	for(i=0;i<=st.top;i++)
    { 
		printf("(%d,%d)",st.data[i].x+1,st.data[i].y+1);
    }

}
/*****************************************************************************/
void SearchPath(int maze[H][L],SeqStack *st)
{
	Datatype temp1,temp2;
	int i,j,k,x,y,test,m;//（i,j）为坐标temp1移动后的坐标值，(x,y)为坐标temp2移动后的坐标值
	//k确定方向

	if(StackIsEmpty(*st)==0)
	{
		temp1=StackTop(*st);	/*将栈顶元素保存到temp1中*/
	   // k=temp1.d;
		for(k=0;k<=3;k++)
		{
			switch(k)
			{
			case 0:i=temp1.x-1;j=temp1.y;break;
			case 1:i=temp1.x;j=temp1.y+1;break;
			case 2:i=temp1.x+1;j=temp1.y;break;
			case 3:i=temp1.x;j=temp1.y+1;break;
			}
			if (i>=0&&j>=0&&i<=H-1&&j<=L-1&&maze[i][j]==0)/*坐标有效且坐标点不是墙壁*/
			{
				temp2.x=i; temp2.y=j;		/*建立点类型临时数据*/
				test=0;			/*判断搜索到的点是否在栈中已经出现，避免出现死循环*/
								for(m=0;m<=st->top;m++)
				{ 
					if(st->data[m].x==i&&st->data[m].y==j)
						test=1;
				}
				if(test==0)
				{
					StackPush(st,temp2);			/*搜索到的点入栈*/
					if ((i==H-1)&&(j==L-1))	/*搜索到的点是终点*/
					{	
						StackPrint(*st);			/*输出当前栈中点序列——一条路径*/
									/*终点出栈*/
					}

					else
						SearchPath(maze,st);		/*以搜索到的点为新的当前点递归*/

				}
			}
		}        
		StackOut(st);			/*搜索方向都搜索过了，将该点出栈*/
	}
} 
/*****************************************************************************/
void main()
/*主函数*/
{
	Datatype temp1;
	SeqStack st;
	int maze[H][L]={	/*地图：0代表可以走，1代表墙壁*/
		{0,0,1,1,1,1},
		{1,0,1,0,1,0},
		{0,0,0,0,0,1},
		{0,0,1,1,0,1},
		{1,0,0,0,0,1},
		{0,1,1,0,0,0}
	};
	printf("迷宫如下图所示——0表示通道，1表示墙！\n");
	printf("          0,0,1,1,1,1\n");
	printf("          1,0,1,0,1,0\n");
	printf("          0,0,0,0,0,1\n");
	printf("          0,0,1,1,0,1\n");
	printf("          1,0,0,0,0,1\n");
	printf("          0,1,1,0,0,0\n");
	StackInit(&st);			/*初始化栈*/
	temp1.x=0; temp1.y=0;temp1.d=-1;	/*建立起点*/
	StackPush(&st,temp1);	/*起点入栈*/
	printf("迷宫的所有可行路径：\n");
	SearchPath(maze,&st);	/*递归地搜索所有路径*/
}