ch3_maze_queue.c

本人讲授数据结构课程时的所写的示例程序

/*
队列的应用：迷宫求解（宽度优先搜索），未完成。。。
author: kk.h
date: 2006.9
http://www.cocoon.org.cn
*/

#include "stdio.h"
#define StackSize 100

typedef struct{
  int i,j;
}PosType;

typedef struct{
  PosType pos;
  posType pos_prior; /* 记录上一个位置，使得算法结束时可以确定一条路径 */
}ElemType;

typedef struct QNode{
  ElemType elem;
  struct QNode * next;
}QNode;

typedef struct {
  QNode* front;
  QNode* rear;
}LinkQueue;

InitQueue(LinkQueue* pQ)
{
  QNode* node;
  node=(QNode*)malloc(sizeof(QNode));  /*分配一个头节点*/
  node->next = NULL;  
  pQ->front=pQ->rear=node;
}

int EnQueue(LinkQueue* pQ,ElemType e)
{
  QNode* node;
  node=(QNode*)malloc(sizeof(QNode));
  node->elem = e;
  node->next = NULL;

  pQ->rear->next = node;
  pQ->rear = node;
  return 1;
}

int DeQueue(LinkQueue* pQ,ElemType* pe)
{
  QNode* node;
  if (pQ->rear == pQ->front)    /* 队空 */
    return 0;

  node = pQ->front->next;
  *pe = node->elem;
  pQ->front->next = node->next;

  /* 注意有个头节点，当最后一个元素出队时，记得更新尾指针 */
  if (pQ->rear==node)
    pQ->rear=pQ->front;

  free(node);
  return 1;
}

DestoryQueue(LinkQueue* pQ)
{
  while(pQ->front){
    pQ->rear=pQ->front->next;
    free(pQ->front);
    pQ->front = pQ->rear;
  }
}


main()
{
  LinkQueue Q;
  ElemType e;
  PosType pos,npos;
  int maze[10][10]={      /* 离散迷宫矩阵，0表示墙壁 */
    {0,0,0,0,0,0,0,0,0,0},
    {0,1,1,0,1,1,1,0,1,0},
    {0,1,1,0,1,1,1,0,1,0},
    {0,1,1,1,1,0,0,1,1,0},
    {0,1,0,0,0,1,1,1,1,0},
    {0,1,1,1,0,1,1,1,1,0},
    {0,1,0,1,1,1,0,1,1,0},
    {0,1,0,0,0,1,0,0,1,0},
    {0,0,1,1,1,1,1,1,1,0},
    {0,0,0,0,0,0,0,0,0,0}
  };
  int i,j;

  InitQueue(&Q);

  e.pos.i=1;e.pos.j=1;
  e.pos_prior=e.pos;
  EnQueue(&Q,e);

  while(DeQueue(&Q,&e)){
    if (maze[e.pos.i][e.pos.j]==1) {  /* 当前位置不是墙壁并且没走过 */
      maze[e.pos.i][e.pos.j]=2;   /* 标记已走过 */
      if (e.pos.i==8 && e.pos.j==8)   /* 如果已经到达终点，退出循环 */
        break;
      else {
        /* 把相邻的四个方向都入队，依次等待搜索，宽度优先 */
        e.pos_prior = e.pos;
        npos = e.pos; e.pos.j++; EnQueue(&Q,e);
        e.pos=npos; e.pos.i++; EnQueue(&Q,e);
        e.pos=npos; e.pos.j--; EnQueue(&Q,e);
        e.pos=npos; e.pos.j++; EnQueue(&Q,e);
      }
    }
  }

  /* 求得的路径放在栈中 */
  printf("\n");
  while(DeQueue(&Q,&e))
    printf("\n(%d,%d)",e.pos.i,e.pos.j);


  /* 打印出整个迷宫，2的是所找到的路径，-1是走过的不通的路径 */
  printf("\n\n");
  for(i=0;i<10;i++) {
    for(j=0;j<10;j++)
      printf("%2d ",maze[i][j]);
    printf("\n");
  }

  getch();
}