第五章算法与数据结构 程序是建立在数据结构基础上使用计算机语 描述的算法,因此简单地讲,程序也可以 表示成:算法十数据结构。 介绍算法的概念及常用算法。并通过数组、 链表、栈、队列等数据结构以及]ava对象容 器,讨论算法的应用及算法的]ava程序实现
Java程序设计大学教程 第五章 算法与数据结构 程序是建立在数据结构基础上使用计算机语 言描述的算法，因此简单地讲，程序也可以 表示成：算法＋数据结构。 介绍算法的概念及常用算法。并通过数组、 链表、栈、队列等数据结构以及Java对象容 器，讨论算法的应用及算法的Java程序实现
5.1算法 算法是为了求解某一问题在有限步骤内、定义了具体操作序列 的规则集合。一个算法应该具有以下五个重要的特征: 确切性( No ambiguity)算法的每一步骤必须有确切的定 义。而不应该有二文性,例如,在算法中不能出现诸如“赋值为 100或1000”。 输入( Input)有0个或多个输入,用于初始化运算对象。所 谓0个输入是指无需输入条件,而算法本身定出了初始条件。 输出( Output)没有输出的算法是毫无意义的。一个算法应 该有一个或多个输出,以反映对输入数据加工后的结果。 可行性( Feasibility)算法原则上能够精确地运行,而且对 于算法中的每种运算,在原理上人们应该能用笔和纸做有限次运 算后完成 有穷性( Finite)算法必须保证执行有限步之后结束。只具有 前面四个特征的规则集合,称不上算法。例如,尽管操作系统能 完成很多任务,但是它的计算过程并不终止,而是无穷无尽的执 行、等待执行,所以操作系统不是算法
Java程序设计大学教程 5.1 算法 算法是为了求解某一问题在有限步骤内、定义了具体操作序列 的规则集合。一个算法应该具有以下五个重要的特征 ： ◼ 确切性（No ambiguity） 算法的每一步骤必须有确切的定 义。而不应该有二义性，例如，在算法中不能出现诸如“赋值为 100或1000”。 ◼ 输入（Input） 有0个或多个输入，用于初始化运算对象。所 谓0个输入是指无需输入条件，而算法本身定出了初始条件。 ◼ 输出（Output） 没有输出的算法是毫无意义的。一个算法应 该有一个或多个输出，以反映对输入数据加工后的结果。 ◼ 可行性（Feasibility） 算法原则上能够精确地运行，而且对 于算法中的每种运算，在原理上人们应该能用笔和纸做有限次运 算后完成。 ◼ 有穷性（Finite） 算法必须保证执行有限步之后结束。只具有 前面四个特征的规则集合，称不上算法。例如，尽管操作系统能 完成很多任务，但是它的计算过程并不终止，而是无穷无尽的执 行、等待执行，所以操作系统不是算法
5.1.1算法的描述 伪代码描述的算法: Java代码实现: 1.X←0 2 ttt xyz 000 3.z←0 4. while x< 100 Whe(x<100){ X=X+1 4.1dox←X+1 y =x+y 4.2y←x+y for(int t=0 t<=10, t++)t 4.3fort←0to10 Z=(z+X*y)/100; 4.3.1doz←(z+X*y) do i 4.3.2 repeat 4.3.2.1y←y+1 Z=Z- yi 4.3.2.2z←z-y }Whe(z<0); 4.3.3. until z<0 Z=X y 4.4.z←X*y 5.y←y/2 y=y/2;
Java程序设计大学教程 5.1.1 算法的描述 1、伪代码描述 : 伪代码（Pseudo-code）是一种算法描述语 言。使用伪代码的目的是为了使被描述的算 法可以容易地以任何一种编程语言（如 Pascal、C、Java等）实现。因此，伪代码 必须结构清晰，代码简单，可读性好，并且 类似自然语言。 伪代码描述的算法： 1. x ← 0 2. y ← 0 3. z ← 0 4. while x < 100 4.1 do x ← x + 1 4.2 y ← x + y 4.3 for t ← 0 to 10 4.3.1 do z ← ( z + x * y ) / 100 4.3.2 repeat 4.3.2.1 y ← y + 1 4.3.2.2 z ← z - y 4.3.3. until z < 0 4.4. z ← x * y 5. y ← y / 2 Java代码实现： int x = 0; int y = 0; int z = 0; while ( x < 100 ) { x = x + 1; y = x + y; for ( int t = 0 ,t <= 10 , t++ ) { z = ( z + x * y ) / 100; do { y = y + 1; z = z - y; } while (z < 0); }; z = x * y; } y = y / 2;
5.1.1算法的描述 2、图形描述: 程序设计中,能够用来表示算法基本概念的 图主要有:PAD图、N\S盒图、流程图 端点符 三处理 判断 预定义处 连接符三 处理 处理1 条件 处理 否、 处理1 处理2 条件 处理2 条 否 while-do) 顺序结构 选择结构 循环结构 程序流程图常用图形符号及控制结构图例
Java程序设计大学教程 5.1.1 算法的描述 2、图形描述 : 程序设计中，能够用来表示算法基本概念的 图主要有：PAD图、N\S盒图、流程图。 处理1 处理2 处理1 处理2 处理 条件 否 、 是 条 件 处理 是 条件 否 、 端点符 处理 判断 预定义处 理 连接符 顺序结构 选择结构 (while-do) (repeat-until) 循环结构 程序流程图常用图形符号及控制结构图例
Java语言实现: 2. import java. io. 3. public class Max i 4. public static void main(String[] args) throws IOException t 5 /初始化 6 Buffered Reader input new Buffered Reader (new InputStream Reader (system. in); 8 int largest=0; 9 int counter=0 10 int theInteger=0 11 ∥/循环比较 2, while( counter 10)t 13 //输入被比较的数 14 counter++;//计数 System. out printIn("请输入第"+ counter+"个被比较的数:") 16 String inputstring input readline i theInteger Integer. parseInt(inputstring; 18 /大值比较 19 if (theInteger> largest) largest=theInteger; 20 3// while 21 System. out. printin("求出最大数是:"+ argest); 22.} 23. 24.}
Java程序设计大学教程 5.1.2 常用算法 ◼ 基本算法大 都比较简单， 是其他算法 的基础。这 类算法在程 序中应用非 常普遍，如： 累加求和、 累乘求积、 求最大和最 小值等。 从10个数中求最大值算法 的例子 开始 初始化，将largest和counter设为0 计数器判断 counter larges? 否 、 是 返回largest 结束 输入被比较的数theInteger 计数：counter←counter+1 伪代码描述算法： FindLargest Input: 10 positive integers 1. largest←0 2. counter←0 3. while(counter largest) then 3.2.1 largest←theInteger end if 3.3 counter←counter+1 end while 4. Return largest End 1. Java语言实现： 2. import java.io.*; 3. public class Max { 4. public static void main(String[] args) throws IOException { 5. //初始化 6. BufferedReader input = new BufferedReader 7. (new InputStreamReader(System.in)); 8. int largest=0; 9. int counter=0; 10. int theInteger=0; 11. //循环比较 12. while(counter largest) largest=theInteger; 20. }// while 21. System.out.println("求出最大数是："+largest); 22. } 23. 24.}
5.1.2常用算法 ■排序算法根据数据的值对它们进行排列。排序是为 了把不规则的信息进行整理,以提高查找效率。常 阶乘迭代算法伪代码: 阶乘递归算法伪代码 Factorial Factorial Input: Apositive integer num Input: A positive integer num 1. Fact←1 1. if (num =0) 3. While (i or num)g then 2.j←-1 1.1 Return 1 3.1 Fact← Fact× i J else 3.2 Increment i 1.2 return num X Factorial (num-1) end while end if Return Fact end end
Java程序设计大学教程 5.1.2 常用算法 ◼ 排序算法根据数据的值对它们进行排列。排序是为 了把不规则的信息进行整理，以提高查找效率。常 用的排序方法包括：选择排序、冒泡排序、插入排 序、快速排序、合并排序、希尔排序、堆排序等。 ◼ 查找是一种在列表中确定目标所在位置的算法。基 本的查找方法有顺序查找和折半查找。 ◼ 迭代和递归是用于编写解决问题的算法的两种途径。 迭代就是反复替换的意思，它通过使用一个中间变 量保存中间结果，不断反复计算求解最终值。递归 是一个算法自我调用的过程，用递归调用的算法就 是递归算法。 阶乘迭代算法伪代码 ： Factorial Input:Apositive integer num 1. FactN←1 2. i←1 3. While（i < or = num） 3.1 FactN←FactN ×i 3.2 Increment i end while Return FactN end 阶乘递归算法伪代码 ： Factorial Input:A positive integer num 1. if（num = 0） then 1.1 Return 1 else 1.2 return num×Factorial(num-1) end if end
5.2数组 ■数组用于表示相同类型的元素的有序集合, 数组中每个元素都有一个唯一的索引 ■根据数组的分配方式可将数组分为:一维 数组和多维数组。]ava中还可以定义不 规则数组。我们可以把一维以上的数组看 作是“数组的数组
Java程序设计大学教程 5.2 数组 ◼ 数组用于表示相同类型的元素的有序集合， 数组中每个元素都有一个唯一的索引。 ◼ 根据数组的分配方式可将数组分为：一维 数组和多维数组。Java中还可以定义不 规则数组。我们可以把一维以上的数组看 作是“数组的数组”
5.2.1数组的创建和使用 律一个靳组的五 定义与创建一个数组的示例: Fruit[ fruits i /定义Frut类型的数组变量 fruits fruits new Fruit[5]; //新建有5个元素的数组 fruits fruits[o]= new Fruiti("香蕉",1000);//为数组元素赋值(引用对象) fruits[1]= new Fruit("葡萄",2000); fruits[2]= new Fruit("菠萝",2000) fruits[3]= new Fruit("草莓",1000); fruits[4]= new Fruit("橘子",1000); intn= fruits. length;//测试数组长度 ■定义与创建一个数组的语法及例子
Java程序设计大学教程 5.2.1 数组的创建和使用 ◼ 数组是一个被命名的连续存储区域的集合，存 放着相同类型的数据项。数组的每个元素通过 它在数组里的位置索引来引用。数组索引必须 是一个整数值或者一个整数表达式。 ◼ 在Java里，大多数情况下数组被当成对象来对 待。它们是用new操作符来实例化的，有自己 的实例变量（例如length，可返回数组中第一 维的元素数量）。数组变量是引用类型的变量。 ◼ 定义与创建一个数组的语法及例子。 定义与创建一个数组的语法： 数组类型名称[] 数组变量名;//定义数组变量 (也可以写成：数组类型名称 数组变量名[];//定义数 组变量) 数组变量名 = new 数组类型名称[n];//创建长度为n 的数组 以上两步也可以合并写为： 数组类型名称 数组变量名[]= new 数组类型名称[n]; 或者： 数组类型名称[] 数组变量名= new 数组类型名称[n]; 定义与创建一个数组的示例： Fruit[] fruits ; //定义Fruit类型的数组变量fruits fruits = new Fruit[5]; //新建有5个元素的数组fruits fruits[0] = new Fruit("香蕉", 1000);//为数组元素赋值（引用对象） fruits[1] = new Fruit("葡萄", 2000); fruits[2] = new Fruit("菠萝", 2000); fruits[3] = new Fruit("草莓", 1000); fruits[4] = new Fruit("橘子", 1000); int n = fruits.length; //测试数组长度
不规则数组演示程序 ArrEst 1. public class ArrTest t 23456789 public ArrTestot for (int n=l; n<myArr length; n++t my Arr[n]= new int[n+1];∥/创建数组的数组,每个数组的长度不一样 for(int m=l; m<myArr[n] length; m++t my arr[n][m]=m; 0.} 11 12. public void printArrot 13 for(int n=l; n<my Arr length; n++t 14 for(int m=1; m<myArr[n]. length; m++ System. out. print(myArr[n][m]+"\t 618 System. out. println 19.} 21. public static void main(String[] args)t 22 ArrTest arr=new ArrEst(; 2 345 r. printArro 26. int myArr[= new int[ Max+1][];//定义不规则数组,先创建数组的第1维。 27. static int max=6
Java程序设计大学教程 用不规则数组实现 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 用2维数组实现每日股指显示 0 1 2 3 4 5 1 1133 1995 1500 1655 1033 2 1605 1981 1143 1226 1265 3 1226 1015 1648 1411 1007 4 1754 1472 1680 1793 1065 5 1469 1707 1745 1477 1742 ... ... 52 1578 1550 1309 1139 1357 5.2.1 多维数组和不规则数组 ◼ 根据数组的分配方式可将数组分为：一维数组 和多维数组。Java中还可以定义不规则数组。 我们可以把一维以上的数组看作是“数组的数 组” 。 模拟每日股指的程序Stock 1. public class Stock { 2. public Stock() { 3. for (int week=1;week<=52;week++){ 4. stockValue[week][0]=week; 5. for (int weekday=1;weekday<=5;weekday++){ 6. stockValue[0][weekday]=weekday; 7. int stockIndex = (int)(Math.random()*1000+1000); 8. stockValue[week][weekday] = stockIndex; 9. } 10. } 11. } 12. 13. public void printStock(){ 14. for (int week=0;week<=52;week++){ 15. for (int weekday=0;weekday<=5;weekday++){ 16. System.out.print(stockValue[week][weekday]+"\t"); 17. } 18. System.out.println(); 19. } 20. } 21. 22. public static void main(String[] args) { 23. Stock s=new Stock(); 24. s.printStock();//打印股指年表 25. } 26. 27. int stockValue[][]= new int[53][6]; 28.} 不规则数组演示程序 ArrTest 1. public class ArrTest { 2. 3. public ArrTest() { 4. for (int n=1;n<myArr.length;n++){ 5. myArr[n] = new int[n+1];//创建数组的数组，每个数组的长度不一样。 6. for (int m=1; m<myArr[n].length; m++){ 7. myArr[n][m]=m; 8. } 9. } 10. } 11. 12. public void printArr(){ 13. for (int n=1; n<myArr.length; n++){ 14. for (int m=1;m<myArr[n].length;m++){ 15. System.out.print(myArr[n][m]+"\t"); 16. } 17. System.out.println(); 18. } 19. } 20. 21. public static void main(String[] args) { 22. ArrTest arr=new ArrTest(); 23. arr.printArr(); 24. } 25. 26. int myArr[][]= new int[Max+1][];//定义不规则数组，先创建数组的第1维。 27. static int Max=6; 28. }
5.2.3排序 ■冒泡法的基本思想是,将待排序的元素看作是竖着排列的“气 而要柽尘肌元素华餐着n(个充的克:态需 扫描来完成数据排序 决速排序是对冒泡排序的一改进。它的基本思想是,通过 轮排序将待排序的数组元 10|49 部分 元素的关键字均比身一部秀素的笑键字不,则分别可对这两 部分元素继续进行排序,以达到整个数组序列有序。 第2次比较 中阝5 交换 第3次比较 EF下下下下P|2 不交换 比较 二轮的最后巨下b下下B 交换 冒泡排序比较和交换的过程演示
Java程序设计大学教程 5.2.3 排序 ◼ 冒泡法的基本思想是，将待排序的元素看作是竖着排列的“气 泡”，较小的元素比较轻，从而要往上浮；较大的元素比较重， 从而要往下沉。一个含有n个元素的列表，冒泡排序需要n-1次 扫描来完成数据排序。 ◼ 快速排序是对冒泡排序的一种改进。它的基本思想是，通过一 轮排序将待排序的数组元素分割成独立的两部分，其中一部分 元素的关键字均比另一部分元素的关键字小，则分别可对这两 部分元素继续进行排序，以达到整个数组序列有序。 冒泡排序比较和交换的过程演示 2 3 5 8 7 6 9 10 49 25 2 5 3 8 7 6 9 10 49 25 2 3 5 7 6 8 9 10 49 25 第2次比较 第3次比较 第一轮的最后 一次比较 比较 交换 比较 比较 交换 ...... 第1次比较 2 5 3 8 7 6 9 10 49 25 比较 不交换 不交换