migong2.c

c语言一些基础编码

/* 标准文档模板 */

#include "Stdio.h"
#include "Conio.h"



/* 迷宫2---最短路线 */
#define M2 12
#define N2 11
#define MAXLEN M2*N2
#define True  1
#define False 0
#define Null 0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

int M=M2-2,N=N2-2;


typedef struct elem  /* 定义栈元素的数据类型 */
 {
  int x,y;
  int dir;
 } ElemType;

typedef struct stktag  /* 定义顺序栈结构 */
 {
   ElemType stack[MAXLEN];
   int top;
 } STACK;

typedef struct QueEle  /* 定义队列元素的数据类型 */
 {
  int x,y;
  int pre;
 } QueElem;

typedef struct QueTag
 {
  QueElem queue[MAXLEN];
  int front,rear;
 } QUEUE;

typedef struct moved  /* 定义方向位移数组元素的类型 */
 {
  int dx,dy;
 } MOVE;


void IniMaze(int maze[][N2]); /*初始化迷宫*/
void IniMove(MOVE move[]);
void IniStack(STACK *s);
int  Push(STACK *s,ElemType x);
ElemType Pop(STACK *s);
int shortpath(int maze[][N2],MOVE move[],QUEUE *p);
void draw(int maze[][N2],STACK *s);
void IniQueue(QUEUE *s); /* 初始化队列 */
void printpath(QUEUE *p,STACK *s);  /* 显示迷宫通路 */

void main() /* 寻找迷宫通路程序*/
{
 STACK *s;
 QUEUE *p;
 int maze[M2][N2],f;
 MOVE move[8];
 IniMaze(maze); /* 初始化迷宫数组 */
 getch();
 s=(STACK *)malloc(sizeof(STACK));
 IniStack(s);
 p=(QUEUE *)malloc(sizeof(QUEUE));
 IniQueue(p);   /* 初始化队列 */
 IniMove(move); /* 初始化位移方向数组*/
 f=shortpath(maze,move,p);  /* 寻找迷宫中的一条最短路径 */
 if(f==True)
 {
  printpath(p,s); /**/
  draw(maze,s);
 }
 else printf("\n此迷宫无通路\n"); /* 如果没找到，显示"无通路" */
 getch();
}/* main */

void IniMaze(int maze[][N2]) /*初始化迷宫*/
{
 int i,j,num;
 printf("\n");
 for(i=0,j=0;i<=M+1;i++)
    maze[i][j]=1;
 for(i=0,j=N+1;i<=M+1;i++)
    maze[i][j]=1;
 for(i=0,j=0;j<=N+1;j++)
    maze[i][j]=1;
 for(i=M+1,j=0;j<=N+1;j++)
    maze[i][j]=1;
 for(i=1;i<=M;i++)
 {
  for(j=1;j<=N;j++)
  {
   num=(800*(i+j)+1500) % 327;
   if ((num<150)&&(i!=M||j!=N))
     maze[i][j]=1;
   else
    maze[i][j]=0;
  }
 }
 for(i=0;i<=M+1;i++)
 {
  printf("\n");
  for(j=0;j<=N+1;j++)
  {
   if((i==0)&&(j==0)||(i==M+1)&&(j==N+1)) printf("%3d",0);
   else printf("%3d",maze[i][j]);
  }
 }
 printf("\n");
}
/* IniMaze */

void IniMove(MOVE move[])
{
 move[0].dx=0; move[0].dy=1;   /*  North  */
 move[1].dx=1; move[1].dy=1;   /*  North-East */
 move[2].dx=1; move[2].dy=0;   /*  East */
 move[3].dx=1; move[3].dy=-1;  /*  SouthEast */
 move[4].dx=0; move[4].dy=-1;  /*  South */
 move[5].dx=-1; move[5].dy=-1; /*  SouthWest */
 move[6].dx=-1; move[6].dy=0;  /* West  */
 move[7].dx=-1; move[7].dy=1;  /* NorthWest */
}
/* IniMove */

void IniStack(STACK *s)
{
 s->top=-1;
}/* IniStack */

int Push(STACK *s,ElemType x)  /*数据元素x进入s指针所指的栈 */
{
 if(s->top==MAXLEN-1) /* 栈满处理 */
  return (False);
 else                /*  进栈 */
 {
   s->stack[++s->top]=x;
   return (True);
 }
}
/* End of Push */

ElemType Pop(STACK *s)
{
 ElemType elem;
 if(s->top<0) /* 栈空处理 */
 {
  elem.x=Null;
  elem.y=Null;
  elem.dir=Null;
  return (elem);
 }
 else
 {
  s->top--;
  return (s->stack[s->top+1]);
 }
}/* Pop */

void IniQueue(QUEUE *s) /* 初始化队列 */
{
 s->front=1; /*设置队头在数组下标为1处 */
 s->rear=1;
 return ;
}

int shortpath(int maze[][N2],MOVE move[],QUEUE *p)
{
  int i,j,dir,x,y,f;
  p->queue[1].x=1;  /* 入口点坐标入队列 */
  p->queue[1].y=1;  /* */
  p->queue[1].pre=0;
  maze[1][1]=-1;    /* 设置入口点为已到达 */
  while(p->front<=p->rear)
  {
   i=p->queue[p->front].x; /* i,j 为出发点 */
   j=p->queue[p->front].y;
   for(dir=0;dir<8;dir++)  /* 寻找从[i][j]出发, 8个方向中有哪些点可到达 */
   {
    x=i+move[dir].dx;
    y=j+move[dir].dy;
    if(maze[x][y]==0) /* 如有可到达点，将此点坐标入对列 */
    {
     p->rear++;
     p->queue[p->rear].x=x;
     p->queue[p->rear].y=y;
     p->queue[p->rear].pre=p->front;
     maze[x][y]=-1;  /* 设置此点已到达标志 */
    }
    if((x==M)&&(y==N)) /* 如到达出口，返回True */
       return (True);
    }
    p->front++; /*队头指针指向下一个队列元素 */
   }
  return (False);
}/* shortpath */


void printpath(QUEUE *p,STACK *s) /* 显示迷宫通路 */
{
 int i,f;
 ElemType elem;
 i=p->rear;
 do /* 从队列中取出最短的迷宫通路放入栈中 */
 {
  elem.x=p->queue[i].x;
  elem.y=p->queue[i].y;
  f=Push(s,elem);
  if(f==False)  /* 如果f为假,说明栈太短 */
   printf("\n栈长度太短\n");
  i=p->queue[i].pre;
 } while(i>0);
 printf("\n   迷宫中的最短通路是：\n");
 i=s->top;
 while(i>-1)
 {
  printf("(%d,%d)",s->stack[i].x,s->stack[i].y);
  if(i>0) printf("-->");
  if((s->top-i+1)%4==0) /* 每四个点占一行 */
    printf("\n");
  i--;
 }
 printf("\n");
}/* printpath */



void draw(int maze[][N2],STACK *s) /* 从迷宫中打印最短的通路 */
{
 int i,j;
 ElemType elem;
 for(i=1;i<=M;i++) /* 将迷宫中全部的-1值恢复为0值 */
 for(j=1;j<=N;j++)
 {
  if(maze[i][j]==-1)
     maze[i][j]=0;
 }
 while(s->top>-1)/* 根据栈中元素的坐标,将通路的各个点的值改为8 */
 {
  elem=Pop(s);
  i=elem.x;
  j=elem.y;
  maze[i][j]=8;
 }
 for(i=0;i<=M+1;i++)
 {
  for(j=0;j<=N+1;j++)
  {
    if((i==0)&&(j==0)||(i==M+1)&&(j==N+1)) printf("  %c",'*');
    else if(maze[i][j]==8) printf("  %c",'*');
     else  printf("%3d",maze[i][j]); /* 显示已标记通路的迷宫 */
  }
  printf("\n");
 }
 printf("\n");
}/* draw */