《Java程序设计大学教程》由会员分享，可在线阅读，更多相关《Java程序设计大学教程（19页珍藏版）》请在金锄头文库上搜索。
1、JavaJava程序设计大学教程程序设计大学教程第五章 算法与数据结构 程序是建立在数据结构基础上使用计算机语 言描述的算法，因此简单地讲，程序也 可以表示成：算法数据结构。 介绍算法的概念及常用算法。并通过数组、 链表、栈、队列等数据结构以及Java对 象容器，讨论算法的应用及算法的Java 程序实现。JavaJava程序设计大学教程程序设计大学教程5.1 算法 算法是为了求解某一问题在有限步骤内、定义了具体操作序 列的规则集合。一个算法应该具有以下五个重要的特征 ：n确切性（No ambiguity） 算法的每一步骤必须有确切的定 义。而不应该有二义性，例如，在算法中不能出现诸如“赋值为
2、100或1000”。n输入（Input） 有0个或多个输入，用于初始化运算对象。所 谓0个输入是指无需输入条件，而算法本身定出了初始条件。n输出（Output） 没有输出的算法是毫无意义的。一个算法应 该有一个或多个输出，以反映对输入数据加工后的结果。n可行性（Feasibility） 算法原则上能够精确地运行，而且对 于算法中的每种运算，在原理上人们应该能用笔和纸做有限次 运算后完成。n有穷性（Finite） 算法必须保证执行有限步之后结束。只具 有前面四个特征的规则集合，称不上算法。例如，尽管操作系 统能完成很多任务，但是它的计算过程并不终止，而是无穷无 尽的执行、等待执行，所以操作系统不
3、是算法。JavaJava程序设计大学教程程序设计大学教程5.1.1 算法的描述 1、伪代码描述 : 伪代码（Pseudo-code）是一种算法描述 语言。使用伪代码的目的是为了使被描述的 算法可以容易地以任何一种编程语言（如 Pascal、C、Java等）实现。因此，伪代码 必须结构清晰，代码简单，可读性好，并且 类似自然语言。 伪代码描述的算法： 1. x 02. y 03. z 04. while x larges? 否 、 是返回largest结束输入被比较的数theInteger计数：countercounter+1伪代码描述算法：FindLargest Input: 10 posit
4、ive integers 1. largest0 2. counter0 3. while(counter largest)then3.2.1 largesttheIntegerend if3.3 countercounter+1end while 4. Return largest End1. Java语言实现： 2. import java.io.*; 3. public class Max 4. public static void main(String args) throws IOException 5. /初始化 6. BufferedReader input = new Buf
5、feredReader 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.JavaJava程序设计大学教程程序设计大学教程5.1.2 常用算法 n排序算法根据数据的值对它们进行排列。排序是为 了把不规则的信息进行
6、整理，以提高查找效率。常 用的排序方法包括：选择排序、冒泡排序、插入排 序、快速排序、合并排序、希尔排序、堆排序等。n查找是一种在列表中确定目标所在位置的算法。基 本的查找方法有顺序查找和折半查找。n迭代和递归是用于编写解决问题的算法的两种途径 。迭代就是反复替换的意思，它通过使用一个中间 变量保存中间结果，不断反复计算求解最终值。递 归是一个算法自我调用的过程，用递归调用的算法 就是递归算法。阶乘迭代算法伪代码 ：Factorial Input:Apositive integer num 1. FactN1 2. i1 3. While（i or = num）3.1 FactNFactN i
7、3.2 Increment iend whileReturn FactNend 阶乘递归算法伪代码 ：Factorial Input:A positive integer num 1. if（num = 0）then1.1 Return 1else1.2 return numFactorial(num-1)end if end JavaJava程序设计大学教程程序设计大学教程5.2 数组 n数组用于表示相同类型的元素的有 序集合，数组中每个元素都有一个唯一 的索引。n根据数组的分配方式可将数组分为：一 维数组和多维数组。Java中还可以定义 不规则数组。我们可以把一维以上的数 组看作是“数组的
8、数组”。 JavaJava程序设计大学教程程序设计大学教程5.2.1 数组的创建和使用 n数组是一个被命名的连续存储区域的集合，存 放着相同类型的数据项。数组的每个元素通过 它在数组里的位置索引来引用。数组索引必须 是一个整数值或者一个整数表达式。 n在Java里，大多数情况下数组被当成对象来对 待。它们是用new操作符来实例化的，有自己 的实例变量（例如length，可返回数组中第一 维的元素数量）。数组变量是引用类型的变量 。n定义与创建一个数组的语法及例子。定义与创建一个数组的语法：数组类型名称 数组变量名;/定义数组变量 (也可以写成：数组类型名称 数组变量名;/定义数 组变量) 数组
9、变量名 = new 数组类型名称n;/创建长度为n 的数组 以上两步也可以合并写为： 数组类型名称 数组变量名= new 数组类型名称n; 或者： 数组类型名称 数组变量名= new 数组类型名称n; 定义与创建一个数组的示例：Fruit fruits ;/定义Fruit类型的数组变量fruits fruits = new Fruit5;/新建有5个元素的数组fruits fruits0 = new Fruit(“香蕉“, 1000);/为数组元素赋值（引用对象） fruits1 = new Fruit(“葡萄“, 2000); fruits2 = new Fruit(“菠萝“, 2000);
10、 fruits3 = new Fruit(“草莓“, 1000); fruits4 = new Fruit(“橘子“, 1000); int n = fruits.length; /测试数组长度JavaJava程序设计大学教程程序设计大学教程用不规则数组实现1 12 123 1234 12345 123456用2维数组实现每日股指显示 012345 111331995150016551033 216051981114312261265 312261015164814111007 417541472168017931065 514691707174514771742 . . 5215781550
11、1309113913575.2.1 多维数组和不规则数组 n根据数组的分配方式可将数组分为：一维数组 和多维数组。Java中还可以定义不规则数组。 我们可以把一维以上的数组看作是“数组的数组 ”。 模拟每日股指的程序Stock1. public class Stock 2. public Stock() 3. for (int week=1;week=52;week+) 4. stockValueweek0=week; 5. for (int weekday=1;weekday=5;weekday+) 6. stockValue0weekday=weekday; 7. int stockInd
12、ex = (int)(Math.random()*1000+1000); 8. stockValueweekweekday = 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(stockValueweekweekday+“t“); 17. 18. System.out.println(); 19. 20. 21. 22. public
13、static void main(String args) 23. Stock s=new Stock(); 24. s.printStock();/打印股指年表 25. 26. 27. int stockValue= new int536; 28.不规则数组演示程序 ArrTest1.public class ArrTest 2. 3. public ArrTest() 4. for (int n=1;nmyArr.length;n+) 5. myArrn = new intn+1;/创建数组的数组，每个数组的长度不一样。 6. for (int m=1; mmyArrn.length; m
14、+) 7. myArrnm=m; 8. 9. 10. 11. 12. public void printArr() 13. for (int n=1; nmyArr.length; n+) 14. for (int m=1;mmyArrn.length;m+) 15. System.out.print(myArrnm+“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 intMax+1;/定义不规则数组，先创建数组的第1维。 27. static int Max=6; 28. JavaJava
