＞第 12 章 栈与队列＞深度优先搜索＞习题

我先看到的广搜，又发现了这里的深搜，感觉都练习完之后有很多收获。关于几个问题，我试着做了一下。
1. 我认为用堆栈可能能够正向排序吧，没试验。
2. 我试过链表，发现不行……想如果用队列，那就跟predecessor没多少区别了。最后没辙，看到第三问……
3. 用递归实现了，没用结构，主函数很简单。只用一个visit子函数以及一个print_maze函数。

算法导论里面是用的递归，但是我做完这么多之后，发现我练习了链表，还有堆栈。

最后，发现这里是C语言教程，但是包含了许多常见的算法，还有详细图解以及习题，真的很不错。支持这个网站。

第三题：
#include <stdio.h>
#define N 5
int maze[5][5] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0
};

typedef struct point {
	int row;
int col} Point;
Point stack[100];

int i = 0, count = 0;
void push(int r,int c)
{	Point p={r,c};
	stack[i] = p;
	i++;
}

Point pop()
{
	i--;
	return stack[i];
}


void dfs(int r, int c)
{
	if (r == N - 1 && c == N - 1) {
		push(r,c);
		for(int j=0;j<i;j++) {
			printf("(%d,%d)--->",stack[j].row, stack[j].col);
		}
		printf("OOO\n");
		count++;
			maze[r][c] = 0;
			pop();
	} else {

		if (r - 1 >= 0 && maze[r-1][c] == 0) {
			push(r,c);
			maze[r][c] = 2;
			dfs(r - 1, c);
			maze[r][c] = 0;
			pop();
		}
		if (c - 1 >= 0 && maze[r][c-1] == 0) {
			push(r,c);
			maze[r][c] = 2;
			dfs(r, c - 1);
			maze[r][c] = 0;
			pop();
		}
		if (r + 1 < 5 && maze[r+1][c] == 0) {
			push(r,c);
			maze[r][c] = 2;
			dfs(r + 1, c);
			maze[r][c] = 0;
			pop();
		}
		if (c + 1 < 5 && maze[r][c+1] == 0) {
			push(r,c);
			maze[r][c] = 2;
			dfs(r, c + 1);
			maze[r][c] = 0;
			pop();
		}
	}
}

int main()
{
	dfs(0, 0);
	printf("-----count:%d-----\n", count);
	return 0;
}

对第二个问题想了一会儿，才想到其实应该可以用1..MAX_ROW*MAX_COL个整数分别代表maze矩阵的所有元素，predecessor二维数组每个元素里面存对应其位置的一个整数就行了，呵呵，这算是一种方法吧

不过用这个方法的缺点在于，存储时需要计算i*MAX_COL+j，搜索结束后利用predecessor数组寻找可行路径时又要对整数取模和取商。。

/* 只要简单地将数组储存语句改为输出语句就可以输出路径
 × 使用递归解决迷宫问题
×/
#include <stdio.h>
#define MAX_LEN_STK 512
#define MAX_ROW 5
#define MAX_COL 5

int top = 0;

struct point path[MAX_LEN_STK];

struct point make_from_cor(int prow, int pcol)
{
	struct point p;
	p.row = prow;
	p.col = pcol;
	return p;
}

/* 0 means available path, 1 means wall*/
int maze[MAX_ROW][MAX_COL] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 1, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0
};

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

int path_search(struct point p)
{
	maze[p.row][p.col] = 2;
	print_maze();

	if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)		/* goal */
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.col < MAX_COL - 1 && maze[p.row][p.col+1] == 0)
			&&	(path_search(make_from_cor(p.row, p.col+1))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.row < MAX_ROW - 1 && maze[p.row+1][p.col] == 0)
			&&	(path_search(make_from_cor(p.row+1, p.col))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.col > 0 && maze[p.row][p.col-1] == 0)
			&&	(path_search(make_from_cor(p.row, p.col-1))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.row > 0 && maze[p.row-1][p.col] == 0)
			&& 	(path_search(make_from_cor(p.row-1, p.col))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}

	return 0;
}

void print_path()
{
	int i;
	--top;
	
	for (i = top; i >= 0; i--)
	{	
		printf("(%d, %d)\n", path[i].row, path[i].col);
	}
}

int main(void)
{
	struct point p = {0, 0};
	if (path_search(p))
	{
		printf("\nfound!\n");
		print_path();
	}
	else
		printf("\ncannot find the path.\n");
	return 0;
}

刚才貌似少了struct point的定义= =

/* 只要简单地将数组储存语句改为输出语句就可以输出路径
 * 使用递归解决迷宫问题
 */
#include <stdio.h>
#define MAX_LEN_STK 512
#define MAX_ROW 5
#define MAX_COL 5

int top = 0;

struct point
{
	int row;
	int col;
};

struct point path[MAX_LEN_STK];

struct point make_from_cor(int prow, int pcol)
{
	struct point p;
	p.row = prow;
	p.col = pcol;
	return p;
}

/* 0 means available path, 1 means wall*/
int maze[MAX_ROW][MAX_COL] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 1, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0
};

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

int path_search(struct point p)
{
	maze[p.row][p.col] = 2;
	print_maze();

	if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)		/* goal */
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.col < MAX_COL - 1 && maze[p.row][p.col+1] == 0)
			&&	(path_search(make_from_cor(p.row, p.col+1))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.row < MAX_ROW - 1 && maze[p.row+1][p.col] == 0)
			&&	(path_search(make_from_cor(p.row+1, p.col))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.col > 0 && maze[p.row][p.col-1] == 0)
			&&	(path_search(make_from_cor(p.row, p.col-1))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.row > 0 && maze[p.row-1][p.col] == 0)
			&& 	(path_search(make_from_cor(p.row-1, p.col))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}

	return 0;
}

void print_path()
{
	int i;
	--top;
	
	for (i = top; i >= 0; i--)
	{	
		printf("(%d, %d)\n", path[i].row, path[i].col);
	}
}

int main(void)
{
	struct point p = {0, 0};
	if (path_search(p))
	{
		printf("\nfound!\n");
		print_path();
	}
	else
		printf("\ncannot find the path.\n");
	return 0;
}

很好的教程，适合初学，也适合复习，用一个简单的迷宫就能引入DFS的思想。

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