＞第 12 章 栈与队列＞环形队列＞习题

#include <stdio.h>

#define MAX_ROW 5
#define MAX_COL 5
#define QUEUE_MAX (MAX_ROW*MAX_COL*2/3+1)

struct point { int row, col; };

int enqueue(struct point pushin);
struct point dequeue(void);
int is_empty(void);
int is_full(void);
int queue_add(int a,int b);
void print_maze(void);
void visit(int row, int col);
//=======================================
struct point queue[QUEUE_MAX];
int head = 0, tail = 0;

int maze[MAX_ROW][MAX_COL] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0,
};

int main()
{
	int count=0,tmpold=0,old=1,new=0;
	struct point p = { 0, 0};

	maze[p.row][p.col] = 2;
	enqueue(p);

	while (!is_empty()) {
		p = dequeue();
		if (p.row == MAX_ROW - 1  /* goal */
		    && p.col == MAX_COL - 1)
			break;
		if (p.col+1 <= MAX_COL-1     /* right */
		    && maze[p.row][p.col+1] == 0){
			visit(p.row, p.col+1);
			new++;
		}
		if (p.row+1 <= MAX_ROW-1     /* down */
		    && maze[p.row+1][p.col] == 0){
			visit(p.row+1, p.col);
			new++;
		}
		if (p.col-1 >= 0          /* left */
		    && maze[p.row][p.col-1] == 0){
			visit(p.row, p.col-1);
			new++;
		}
		if (p.row-1 >= 0          /* up */
		    && maze[p.row-1][p.col] == 0){
			visit(p.row-1, p.col);
			new++;
		}

		--old;
		if(old == 0 ){
			tmpold=old=new;
			new=0;
			++count;
		}
		printf("step : %d.%d\n",count,tmpold-old+1);
		print_maze();
	}
	if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
		printf("totle steps : %d\n", count);
	} else
		printf("No path!\n");

	return 0;
}
//=======================================
int enqueue(struct point pushin)
{
	queue[tail]=pushin;
	tail=queue_add(tail,1);
	return 0;
}

struct point dequeue(void)
{
	int head_tmp=head;
	head=queue_add(head,1);
	return queue[head_tmp];
}

int is_empty(void)
{
	return head==tail;
}

int is_full(void)
{
	return queue_add(tail,1) == head;
}

int queue_add(int a,int b)
{
	return (a+b)%QUEUE_MAX;
}

void print_maze(void)
{
	int i, j;
	for (i = 0; i < MAX_ROW; i++) {
		for (j = 0; j < MAX_COL; j++)
			printf("%d ", maze[i][j]);
		putchar('\n');
	}
	printf("*********\n");
}

void visit(int row, int col)
{
	struct point visit_point = { row, col };
	maze[row][col] = 2;
	enqueue(visit_point);
}

环形队列实现迷宫搜索，只找出用了多少步。
（1）环形队列用queue_add()函数代替原来的++运算，使队列可以环形存储；
（2）广度优先搜索用队列最大个数是 n*2/3+1
（3）步数是指前线推进的次数，注意一次前线推进并不一定都是一个方格。

如果您有建设性意见，哪怕只是纠正一个错别字，也请不吝赐教，您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见！