《Java软件结构:设计和使用数据结构(第2版)》读书笔记1-递归
大学的数据结构和算法根本就是混过来的,某天在某某论坛里有个关于数据结构和算法到底在日常的编程到底有多大的用处。对于我来说,我并不觉得我用上了那些讲的数据结构和算法。Java Collection Framework已经跟我们做了这些。我已经能非常熟练的使用Collection里面的类库。但是我们用的基本上都是那些线性集合(堆栈,队列,列表,Set),非线性集合(树,堆,散列和图)我感觉比较少用到。我也主要是想对非线性集合做一些比较。线性集合比较简单。
第一章到第九章都是讲线性集合, 也比较容易理解, 在这里就忽略掉。第十章是讲递归算法。我对这章比较感兴趣,用递归实现某个算法真的感觉非常优雅,代码短而少,许多非线性集合都是用递归来实现的。但也有他的缺点, 对方法的每次递归调用都会生成新的局部变量和局部参数。假如递归层次太多的话,就会消耗太多的stack。
任何递归定义都必须有一个非递归部分;这个非递归部分叫做基本情况,它使的递归跳出无穷循环递归。
Ex 1: 1~N的累加过程,数值1~N的累加可以看成是1~N<spanstyle="font-family:宋体">-1的累加加上N。
public int sum(int num){
int result = 0;
if (num == 1){
return 1;
}
return result + num + sum(num - 1);
}
这里的基本情况就是但num==1的时候。 当然这个可以不用递归来处理,用一个for就行了(而且比用递归更直观)。我们必须能判断什么时候使用递归,什么时候不使用递归,所有问题都可以使用迭代(for循环)解决问题。不过有些情况下,迭代方式过于复杂,对某些问题,递归可以写出短小而优雅的代码。
直接递归和间接递归,方法调用自己,这就是直接递归(如上个例子)。方法调用另一个方法,最终导致再调用原方法。这就是间接递归。
河内塔问题(Towers of Hanoi)(可以上网找找这个经典问题的描述)
规则:
l 一次只能移动一张圆盘
l 不能将大盘放在小盘的上方
l 除了那张在柱子之间搬动的圆盘之外,所有圆盘都必须在某根柱子上
策略:
l 将最上方的N-1张圆盘从最初的柱子移到那根多处的柱子上
l 将最大的圆盘从最初的柱子移动到最终的柱子上
l 再将那个多出柱子上的N-1张圆盘移到最终的柱子上
Code:
public class TowersOfHanoi{
private int totalDisks;
// ------------------------------------------------------
// Sets up the puzzle with the specified number of disks
// ------------------------------------------------------
public TowersOfHanoi(int disks){
this.totalDisks = disks;
}
// ----------------------------------------------------------
// Performs the initial call to moveTower to solve the puzzle.
// Moves the disks from tower 1 to tower 3 using tower 2
// ----------------------------------------------------------
public void solve(){
moveTower(totalDisks, 1, 3,2);
}
// -----------------------------------------------------------------
// Moves the specified number of disks from one tower to another by
// moving a subtower of n-1 disks out of the way, moving one disk,
// then moving the subtower back, Base case of 1 disk.
// -----------------------------------------------------------------
private void moveTower(int numDisks, int start, int end, int temp) {
if (numDisks == 1){
moveOneDisk(start, end);
}else{
moveTower(numDisks-1, start, temp, end);
moveOneDisk(start, end);
moveTower(numDisks-1, temp, end, start);
}
}
private void moveOneDisk(int start, int end) {
System.out.println("Move one disk from " + start + " to " + end);
}
}
分享到:
相关推荐
java 数据结构 递归 八皇后 完美递归 java 数据结构 递归 八皇后 完美递归
数据结构:栈与递归--含分治与回溯.ppt
java代码-使用Java递归求和1+2+3+...+n的源代码 ——学习参考资料:仅用于个人学习使用!
Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择正确的算法 利用数据结构和算法为...
java递归树型结构通用数据库
5. 实现堆栈数据结构:演示了使用Java的Stack类来实现堆栈数据结构,并展示了入栈和出栈的操作。 6. 使用HashMap存储和检索数据:展示了如何使用HashMap来存储和检索键值对数据。 7. 实现接口和多态:演示了如何定义...
数据结构实验二叉树用递归实现先序遍历、中序遍历和后序遍历,用几种不同非递归方法实现了中序遍历,代码附有详细注释
本书从讲解什么是数据结构开始,延伸至高级数据结构和算法分析,强调数据结构和问题求解技术。本书的目的是从抽象思维和问题求解的观点提供对数据结构的实用介绍,试图包含有关数据结构、算法分析及其Java实现的所有...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
java语法 method 递归 马克-to-win java视频 方法 重载
Java递归算法构造JSON树形结构,Java递归算法构造JSON树形结构Java递归算法构造JSON树形结构
4-2-1-基本循环结构 4-2-2-通用循环构造方法 4-2-3-死循环半路循环 4-2-4-布尔表达式 6-1-1-文件的基础 6-1-2-文件的基本处理 6-1-3-文件实例一 6-1-4-文件实例二 6-2-1-字典的基础 6-2-2-字典的操作 6-2-3-字典实例...
《数据结构与算法》以基本数据结构和算法设计策略为知识单元,系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法,主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。《数据结构...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
主要内容包括:算法效率的输入规模、阶和大O,数据结构的无序和有序列表,队列和栈基于数组和链表的设计实例,递归详解,二叉查找树和AVL树,堆、散列表和排序以及图论等。对于每一种数据结构的性质和用途,《计算机...
4-2-1-基本循环结构 4-2-2-通用循环构造方法 4-2-3-死循环半路循环 4-2-4-布尔表达式 6-1-1-文件的基础 6-1-2-文件的基本处理 6-1-3-文件实例一 6-1-4-文件实例二 6-2-1-字典的基础 6-2-2-字典的操作 6-2-3-字典实例...
介绍了计算机编程中使用的...《Java数据结构和算法》(第2版)提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程,在学生掌握了编程的基础后才开始本书的学习。
数据结构递归ppt,有助于初学者学习!很有用。
演示了如何把低效率的递归函数转换成非递归的函数并完成相同的计算。