a2水 Lecture8 8-1 数据结构 与 算法 30m Programming in Java JAVA
8-1 Programming in Java 数据结构 与 算法 Lecture8
a2水 提纲 8-2 ·算法 >递归算法 >排序算法 ·数据结构 >链表 >队列 >堆栈 >树 Programming in Java JAVA
8-2 Programming in Java 提纲 • 算法 ➢递归算法 ➢排序算法 • 数据结构 ➢ 链表 ➢ 队列 ➢堆栈 ➢ 树
递阳 8-3 递归是常用的编程技术，实现技术为直接或间接 地调用自身的方法 ·递归算法的步骤： >求得范围缩小的同性质问题的结果 >利用已得到的结果和一个简单的操作求得问题的最 后解答 >例如：求n的阶乘n! ·递归算法的主要内容： •定义递归头 •定义如何从同性质的简化问题求得当前问题 AVA
8-3 Programming in Java 递归 • 递归是常用的编程技术，实现技术为直接或间接 地调用自身的方法 • 递归算法的步骤： ➢求得范围缩小的同性质问题的结果 ➢利用已得到的结果和一个简单的操作求得问题的最 后解答 ➢ 例如：求n的阶乘n！ • 递归算法的主要内容： •定义递归头 •定义如何从同性质的简化问题求得当前问题
阶乘计算示例(1) 8-4 ·简单实现： public class Factorial{ public static int factorial(int x){ int fact 1; for (inti=2;i <=x;i++) /1o0P fact *i; //shorthand for:fact=fact*i; return fact; 3 public class ComputingFactorial{ public static void main(String arg[]){ int a Factorial.factorial(Integer.parselnt(arg[O]); System.out.println(a); Programming in Java JAVA
8-4 Programming in Java 阶乘计算示例（1） public class Factorial { public static int factorial(int x) { int fact = 1; for (int i =2; i <= x; i ++) //loop fact *= i; //shorthand for: fact=fact*i; return fact; } } public class ComputingFactorial { public static void main(String arg[]) { int a = Factorial.factorial(Integer.parseInt(arg[0])); System.out.println(a); } } • 简单实现:
阶乘什算示例(2) 8-5 ·改进 public class Factorial2{ //create an array to cache values 0!Through 20! Static long[]table new long[21]; Static {table[0]1;} //factorial of 0 is 1 //Remember the highest initialized value in the array static int last 0; public static long factorial(int x){ while (last x){ table [last 1]table[last]*(last 1); last++; Programming in Java JAVA
8-5 Programming in Java public class Factorial2 { //create an array to cache values 0! Through 20! Static long[] table = new long[21]; Static {table[0] = 1;} //factorial of 0 is 1 //Remember the highest initialized value in the array static int last = 0; public static long factorial(int x) { while (last < x) { table [last + 1] = table[last]*(last + 1); last++; } } 阶乘计算示例（2） • 改进
阶乘什算示例(3) 8-6 ·递归算法 /兴* This class shows a recursive method to compute factorials.This method calls itself repeatedly based on the formula:n!=n*(n-1)! **/ public class Factorial3 public long factorial(int n){ if(n=1)return n;/递归头 else return n*factorial(n-1);/递归调用自己 Programming in Java JAVA
8-6 Programming in Java • 递归算法 /** * This class shows a recursive method to compute factorials. This method * calls itself repeatedly based on the formula: n! = n*(n-1)! **/ public class Factorial3 { public long factorial(int n) { if (n == 1) return n; //递归头 else return n*factorial(n - 1); //递归调用自己 } } 阶乘计算示例（3）
Fibonacci 8-7 fibonacci(n)=n,n=0,1; fibonacci(n)=fibonacci(n-l)+fibonacci(n-2),n为其它 整数 public long fibonacci(int n){ if (n=0lln==1) return n; else return (fibonacci(n-1)*factorial(n-2)); P148-149:一维数组记录各次递归调用的情况 定义一个专门的方法计算反映递归层次的缩进 Programming in Java JAVA
8-7 Programming in Java fibonacci(n) = n, n=0,1; fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) , n为其它 整数 public long fibonacci(int n) { if (n == 0 || n == 1 ) return n; else return (fibonacci(n - 1)*factorial(n - 2)); } Fibonacci •P148-149: 一维数组记录各次递归调用的情况 定义一个专门的方法计算反映递归层次的缩进
辣序 8-8 。排序： 将一个数据序列中的各个数据元素根据某个给出 的关键值进行从大到小或从小到大排列的过程 39165482107 12345678910 •排序算法 Programming in Java JAVA
8-8 Programming in Java 排序 • 排序: 将一个数据序列中的各个数据元素根据某个给出 的关键值进行从大到小或从小到大排列的过程 3 9 1 6 5 4 8 2 10 7 1 2 3 4 5 6 7 8 9 10 •排序算法
R 冒池排序(1) 8-9 。算法： 两两比较，调整顺序 > 输入：包含n个整数的数组 > 输出：排序后的数组 1.i:=2; 2.从A()到A(m中发现最小的元素； 3.如果比A(i-1)大，将A(i-1)和交换； 4.i:=i+1;goto step (2). Programming in Java JAVA
8-9 Programming in Java 冒泡排序(1) • 算法： 两两比较，调整顺序 ➢ 输入: 包含 n个整数的数组 ➢ 输出: 排序后的数组 1. i := 2; 2. 从 A(i) 到 A(n)中发现最小的元素; 3. 如果a比 A(i - 1)大, 将 A(i - 1) 和 a交换; 4. i := i + 1; goto step (2)
a2k 冒池辣序(2) 8-10 ·排序过程 swap swap 1st step: 39165482107 swap 2nd step: 31654829710 13245678910 12345678910 Programming in Java JAVA
8-10 Programming in Java • 排序过程 1st step: 3 9 1 6 5 4 8 2 10 7 2nd step: 3 1 6 5 4 8 2 9 7 10 1 3 2 4 5 6 7 8 9 10 … ... 1 2 3 4 5 6 7 8 9 10 swap swap 冒泡排序(2) swap