`
jaesonchen
  • 浏览: 309865 次
  • 来自: ...
社区版块
存档分类
最新评论

数据结构之递归

 
阅读更多

 

 

    递归(recursion)是指在定义自身的同时又出现了对自身的引用。如果一个算法直接或间接地调用自己,则称这个算法是一个递归算法。

    任何一个有意义的递归算法总是由两部分组成:递归调用与递归终止条件。

 

 /**
 * 阶汉诺塔问题可以描述为:假设有X、Y、Z 三个塔座,初始时有n 个大小不一的
 * 盘子按照从小到大的次序放在塔座X 上。现在要求将塔座X 上的所有盘子移动到塔座Z 上
 * 并保持原来的顺序,在移动过程中要满足以下要求:在塔座之间一次只能移动一个盘子并且
 * 任何时候大盘子都不能放到小盘子上。
 */
public static void hanio (int n, char x, char y, char z) {
	if (n == 1) 
		move( x, n, z);
	else {
		hanio (n - 1, x, z, y);
		move(x, n, z);
		hanio(n - 1, y, x, z);
	}
}
private static void move(char x, int n, char y) {
	System.out.println ("Move " + n + " from " + x + " to " + y);
}

 

 

     堆栈实现:

/**
 * 求解从迷宫中的起点到某个终点的路径
 */
public class Maze {

	public static void mazeExit(char[][] maze, int sx, int sy, int ex, int ey) {
		Cell[][] cells = createMaze(maze); //创建化迷宫
		printMaze(cells); //打印迷宫
		Stack s = new StackArray(); //构造堆栈
		Cell startCell = cells[sx][sy]; //起点
		Cell endCell = cells[ex][ey]; //终点
		s.push(startCell); //起点入栈
		startCell.visited = true; //标记起点已被访问
		while (!s.isEmpty()) {
			Cell current = (Cell)s.peek();
			if (current == endCell){ //路径找到
				System.out.println("共有" + s.getSize() + "步");
				while(!s.isEmpty()){
					
					Cell cell = (Cell)s.pop();//沿路返回将路径上的单元设为*
					cell.c = '*';
					//堆栈中与cell 相邻的单元才是路径的组成部分,除此之外,
					//堆栈中还有记录下来但是未继续向下探索的单元,
					//这些单元直接出栈
					while(!s.isEmpty() && !isAdjoinCell((Cell)s.peek(), cell))
						s.pop();
				}
				System.out.println("找到从起点到终点的路径。");
				printMaze(cells);
				return;
			} else { //如果当前位置不是终点
				int x = current.x;
				int y = current.y;
				int count = 0;
				if(isValidWayCell(cells[x + 1][y])){ //向下
					s.push(cells[x + 1][y]); cells[x+1][y].visited = true; count++;}
				if(isValidWayCell(cells[x][y + 1])){ //向右
					s.push(cells[x][y + 1]); cells[x][y + 1].visited = true; count++;}
				if(isValidWayCell(cells[x - 1][y])){ //向上
					s.push(cells[x - 1][y]); cells[x - 1][y].visited = true; count++;}
				if(isValidWayCell(cells[x][y - 1])){ //向左
					s.push(cells[x][y - 1]); cells[x][y - 1].visited = true; count++;}
				if (count == 0) s.pop();//如果是死点,出栈
			}//end of if
		}//end of while

		System.out.println("没有从起点到终点的路径。");
	}
	private static void printMaze(Cell[][] cells) {
		for (int x = 0; x < cells.length; x++){
			for (int y = 0; y < cells[x].length; y++)
				System.out.print(cells[x][y].c + " ");
			System.out.println();
		}
	}
	private static boolean isAdjoinCell(Cell cell1, Cell cell2) {
		if (cell1.x == cell2.x && Math.abs(cell1.y - cell2.y) < 2) return true;
		if (cell1.y == cell2.y && Math.abs(cell1.x - cell2.x) < 2) return true;
		return false;
	}
	private static boolean isValidWayCell(Cell cell) {
		return cell.c == '0' && !cell.visited;
	}
	private static Cell[][] createMaze(char[][] maze) {
		Cell[][] cells = new Cell[maze.length][];
		for (int x = 0; x < maze.length; x++) {
			char[] row = maze[x];
			cells[x] = new Cell[row.length];
			for (int y = 0; y < row.length; y++)
				cells[x][y] = new Cell(x, y, maze[x][y], false);
		}
		return cells;
	}
	public static void main(String[] args) {
		char[][] maze = {
				{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
				{'1', '0', '0', '1', '1', '1', '0', '0', '1', '1'},
				{'1', '0', '0', '1', '1', '0', '0', '1', '0', '1'},
				{'1', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
				{'1', '0', '0', '0', '0', '1', '1', '0', '0', '1'},
				{'1', '0', '0', '1', '1', '1', '0', '0', '0', '1'},
				{'1', '0', '0', '0', '0', '1', '0', '1', '0', '1'},
				{'1', '0', '1', '1', '0', '0', '0', '0', '0', '1'},
				{'1', '1', '0', '0', '0', '0', '1', '0', '0', '1'},
				{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
		};
		mazeExit(maze, 1, 1, 2, 8);
	}

}
class Cell {
	int x = 0; //单元所在行
	int y = 0; //单元所在列
	boolean visited = false; //是否访问过
	char c = ' '; //是墙('1')、可通路('0')或起点到终点的路径('*')
	public Cell(int x, int y, char c, boolean visited) {
			this.x = x; this.y = y;
			this.c = c; this.visited = visited;
	}
}

 

 

 

 

 

 

 

 

分享到:
评论

相关推荐

    数据结构二叉树遍历递归,非递归

    理解递归遍历后,非递归遍历的关键在于使用额外的数据结构(如栈或队列)来跟踪当前的遍历状态。非递归遍历的优势在于它避免了函数调用栈的深度限制,对于非常深的树,递归可能会导致栈溢出。 在实际编程中,根据...

    数据结构课件之递归ppt

    数据结构课程中的递归是一个重要的概念,它在计算机科学中占据着核心地位,尤其是在算法设计和程序编写中。递归是指一个函数或过程在执行过程中直接或间接地调用自身来解决问题的方法。递归通常涉及分治策略,将大...

    数据结构实验-递归

    本实验主题“数据结构实验-递归”旨在通过实际操作帮助学生深入理解这两者之间的关系以及它们在解决特定问题时的应用。 首先,让我们详细讨论全排列。全排列是指从n个不同的元素中取出m(m≤n)个元素,按照一定的...

    java数据结构递归算法

    在这个"java数据结构递归算法"主题中,我们将深入探讨递归的基本概念、如何在Java中使用递归,以及一个著名的递归应用案例——八皇后问题。 递归是函数或方法调用自身的过程。它基于一个问题的规模缩小至基本情况,...

    数据结构和算法学习之递归

    在计算机科学中,数据结构和算法是编程的基础,而递归是解决复杂问题的重要方法之一。递归是一种在函数或程序中调用自身的技术,它通过简化问题来达到求解的目的。递归通常与分治策略相结合,将大问题分解为小的相似...

    迷宫游戏C++数据结构递归算法实现

    本项目是用C++语言实现的迷宫游戏,重点在于利用数据结构和递归算法解决路径寻找问题。以下将详细讲解其中涉及的关键知识点。 首先,迷宫生成通常采用随机算法,比如深度优先搜索(DFS)或Prim算法。在这个项目中,...

    C语言数据结构递归算法之迷宫求解

    "C语言数据结构递归算法之迷宫求解"是一个经典的主题,它涉及到程序设计的基本原理,如递归思想和图遍历。 首先,我们要理解什么是递归算法。递归是一种解决问题的方法,它通过调用自身来解决更小规模的问题,直到...

    数据结构_八皇后 非递归

    数据结构八皇后问题 eightqueens

    数据结构-非递归遍历二叉树

    非递归遍历二叉树是一种不依赖递归函数来访问树的所有节点的方法,它通常通过栈或队列等数据结构来实现。下面我们将详细探讨非递归遍历二叉树的先序、中序和后序策略。 先序遍历是二叉树遍历的一种方法,其顺序为:...

    数据结构中递归转非递归算法分析及模型设计研究.pdf

    递归算法在数据结构中是一种常见的算法形式,它通过将问题分解为更小的子问题来解决问题,直至达到一个基本情况(base case)后开始回溯并解决子问题,最终得到原始问题的解。递归算法具有思路明确、代码简洁的优点...

    数据结构 递归和流 算法

    在IT领域,特别是计算机科学和软件工程中,数据结构、递归和算法是核心概念,它们构成了编程的基础。本文将详细探讨这些主题,尤其是递归的运用。 首先,我们要了解什么是数据结构。数据结构是组织和存储数据的方式...

    数据结构 递归

    数据结构 递归的定义、递归的调用过程以及各种递归算法的实现。以下三种情况用到递归:定义是递归的、 数据结构是递归的、 问题的解法是递归的

    基于数据结构的程序递归算法设计.pdf

    分治是递归程序设计中常用的一种策略,它将一个问题分解为若干个规模较小但结构相同或相似的问题,递归地解决这些子问题后,再将子问题的解合并以得到原问题的解。分治策略的特点是递归地将问题分解,然后合并解决子...

    数据结构:递归

    数据结构递归ppt,有助于初学者学习!很有用。

    数据结构课件递归

    数据结构,递归操作,主要运用栈,队列,链表等结构进行操作

    数据结构中递归算法的教学研究.pdf

    在数据结构教学中,递归算法是一项基础且核心的技能,其重要性不容忽视。递归算法在程序设计中的应用极为广泛,尤其在数据结构领域中,众多的数据结构定义和操作都会涉及到递归概念。因此,理解递归算法对于学生来说...

    数据结构-二叉树递归-非递归实现

    数据结构实验二叉树用递归实现先序遍历、中序遍历和后序遍历,用几种不同非递归方法实现了中序遍历,代码附有详细注释

    数据结构 二叉树三种遍历的非递归算法(背诵版).doc

    本资料“数据结构 二叉树三种遍历的非递归算法(背诵版)”着重介绍了二叉树的三种主要遍历方法——前序遍历、中序遍历和后序遍历的非递归实现。 **前序遍历**: 前序遍历的顺序是:根节点 -&gt; 左子树 -&gt; 右子树。非...

    数据结构 利用递归法进行表的查找

    本主题主要探讨如何利用递归法进行表的查找,这是数据结构中一个非常重要的概念,尤其对于初学者来说,理解并掌握递归查找至关重要。 首先,我们需要了解什么是表。表是一种线性数据结构,它可以存储一系列有序或...

Global site tag (gtag.js) - Google Analytics