《Java程序设计大学教程第五章.ppt》由会员分享，可在线阅读，更多相关《Java程序设计大学教程第五章.ppt（19页珍藏版）》请在金锄头文库上搜索。
1、JavaJava程序设计大学教程程序设计大学教程 第五章 算法与数据结构 程序是建立在数据结构基础上使用计算机语言描述的算法，因此简单地讲，程序也可以表示成：算法数据结构。 介绍算法的概念及常用算法。并通过数组、链表、栈、队列等数据结构以及Java对象容器，讨论算法的应用及算法的Java程序实现。JavaJava程序设计大学教程程序设计大学教程 5.1 算法 算法是为了求解某一问题在有限步骤内、定义了具体操作序列的规则集合。一个算法应该具有以下五个重要的特征 ：n确切性（确切性（No ambiguity） 算法的每一步骤必须有确切的定义。而不应该有二义性，例如，在算法中不能出现诸如“赋值为10
2、0或1000”。n输入（输入（Input） 有0个或多个输入，用于初始化运算对象。所谓0个输入是指无需输入条件，而算法本身定出了初始条件。n输出（输出（Output） 没有输出的算法是毫无意义的。一个算法应该有一个或多个输出，以反映对输入数据加工后的结果。n可行性（可行性（Feasibility） 算法原则上能够精确地运行，而且对于算法中的每种运算，在原理上人们应该能用笔和纸做有限次运算后完成。n有穷性（有穷性（Finite） 算法必须保证执行有限步之后结束。只具有前面四个特征的规则集合，称不上算法。例如，尽管操作系统能完成很多任务，但是它的计算过程并不终止，而是无穷无尽的执行、等待执行，所以
3、操作系统不是算法。JavaJava程序设计大学教程程序设计大学教程 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、 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 / 2Java代码实现：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;JavaJava程序设计大学教程程序设计大学教程 5.1.1 算法的
5、描述 2、图形描述 :程序设计中，能够用来表示算法基本概念的图主要有：PAD图、NS盒图、流程图。 处理1处理2处理1处理2处理 条件否、是条件处理 是条件否、端点符处理判断预定义处理连接符顺序结构选择结构(while-do)(repeat-until)循环结构程序流程图常用图形符号及控制结构图例 JavaJava程序设计大学教程程序设计大学教程 5.1.2 常用算法 n基本算法大都比较简单，是其他算法的基础。这类算法在程序中应用非常普遍，如：累加求和、累乘求积、求最大和最小值等。 从10个数中求最大值算法 的例子开始初始化，将largest和counter设为0计数器判断counter la
6、rges?否、是返回largest结束输入被比较的数theInteger计数：countercounter+1伪代码描述算法：FindLargestInput: 10 positive integers1. largest02. counter03. while(counter largest) then 3.2.1 largesttheInteger end if 3.3 countercounter+1 end while4. Return largestEnd1.Java语言实现：2.import java.io.*;3.public class Max 4. public static
7、 void main(String args) throws IOException 5. /初始化6. BufferedReader input = new BufferedReader7. (new InputStreamReader(System.in);8. int largest=0;9. int counter=0;10. int theInteger=0;11. /循环比较12. while(counter largest) largest=theInteger;20. / while21. System.out.println(求出最大数是：+largest);22. 23.
8、24.JavaJava程序设计大学教程程序设计大学教程 5.1.2 常用算法 n排序算法根据数据的值对它们进行排列。排序是为了把不规则的信息进行整理，以提高查找效率。常用的排序方法包括：选择排序、冒泡排序、插入排序、快速排序、合并排序、希尔排序、堆排序等。n查找是一种在列表中确定目标所在位置的算法。基本的查找方法有顺序查找和折半查找。n迭代和递归是用于编写解决问题的算法的两种途径。迭代就是反复替换的意思，它通过使用一个中间变量保存中间结果，不断反复计算求解最终值。递归是一个算法自我调用的过程，用递归调用的算法就是递归算法。阶乘迭代算法伪代码 ：FactorialInput:Apositive
9、integer num1. FactN12. i13. While（i or = num） 3.1 FactNFactN i 3.2 Increment i end while Return FactN end 阶乘递归算法伪代码 ：FactorialInput:A positive integer num1. if（num = 0） then 1.1 Return 1 else 1.2 return numFactorial(num-1) end ifend JavaJava程序设计大学教程程序设计大学教程 5.2 数组 n数组用于表示相同类型的元素的有序集合，数组中每个元素都有一个唯一的索
10、引。n根据数组的分配方式可将数组分为：一维数组和多维数组。Java中还可以定义不规则数组。我们可以把一维以上的数组看作是“数组的数组”。 JavaJava程序设计大学教程程序设计大学教程 5.2.1 数组的创建和使用 n数组是一个被命名的连续存储区域的集合，存放着相同类型的数据项。数组的每个元素通过它在数组里的位置索引来引用。数组索引必须是一个整数值或者一个整数表达式。 n在Java里，大多数情况下数组被当成对象来对待。它们是用new操作符来实例化的，有自己的实例变量（例如length，可返回数组中第一维的元素数量）。数组变量是引用类型的变量。n定义与创建一个数组的语法及例子。定义与创建一个数
11、组的语法：数组类型名称数组类型名称 数组变量名数组变量名;/定义数组变量定义数组变量(也可以写成：数组类型名称也可以写成：数组类型名称 数组变量名数组变量名;/定义数组定义数组变量变量)数组变量名数组变量名 = new 数组类型名称数组类型名称n;/创建长度为创建长度为n的的数组数组以上两步也可以合并写为：以上两步也可以合并写为：数组类型名称数组类型名称 数组变量名数组变量名= new 数组类型名称数组类型名称n;或者：或者：数组类型名称数组类型名称 数组变量名数组变量名= new 数组类型名称数组类型名称n; 定义与创建一个数组的示例：Fruit fruits ;/定义Fruit类型的数组变
12、量fruitsfruits = new Fruit5;/新建有5个元素的数组fruitsfruits0 = new Fruit(香蕉, 1000);/为数组元素赋值（引用对象）fruits1 = new Fruit(葡萄, 2000);fruits2 = new Fruit(菠萝, 2000);fruits3 = new Fruit(草莓, 1000);fruits4 = new Fruit(橘子, 1000);int n = fruits.length; /测试数组长度JavaJava程序设计大学教程程序设计大学教程 用不规则数组实现112123123412345123456用2维数组实现每
13、日股指显示012345111331995150016551033216051981114312261265312261015164814111007417541472168017931065514691707174514771742. .52157815501309113913575.2.1 多维数组和不规则数组 n根据数组的分配方式可将数组分为：一维数组和多维数组。Java中还可以定义不规则数组。我们可以把一维以上的数组看作是“数组的数组”。 模拟每日股指的程序Stock1.public class Stock 2. public Stock() 3. for (int week=1;wee
14、k=52;week+)4. stockValueweek0=week;5. for (int weekday=1;weekday=5;weekday+)6. stockValue0weekday=weekday;7. int stockIndex = (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;weekd
15、ay=5;weekday+)16. System.out.print(stockValueweekweekday+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 int536;28.不规则数组演示程序 ArrTest1.public class ArrTest 2. 3. public ArrTest() 4.
16、for (int n=1;nmyArr.length;n+)5. myArrn = new intn+1;/创建数组的数组，每个数组的长度不一样。6. for (int m=1; mmyArrn.length; m+)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
17、. 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程序设计大学教程程序设计大学教程 5.2.3 排序 n冒泡法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮；较大的元素比较重，从而要往下沉。一个含有n个元素的列表，冒泡排序需要n-1次扫描来完成数
18、据排序。n快速排序是对冒泡排序的一种改进。它的基本思想是，通过一轮排序将待排序的数组元素分割成独立的两部分，其中一部分元素的关键字均比另一部分元素的关键字小，则分别可对这两部分元素继续进行排序，以达到整个数组序列有序。冒泡排序比较和交换的过程演示 235876910492525387691049254923576891025第2次比较第3次比较第一轮的最后一次比较比较交换比较比较交换.2538769104925第1次比较比较不交换不交换JavaJava程序设计大学教程程序设计大学教程 5.2.4 查找 n顺序查找就是将要查找的数据的关键字按一定的顺序挨个与列表中的数据进行比较，相等时就找到了所
19、要的数据。n对有序的列表可以使用更有效率的折半查找。折半查找是从一个列表的中间的元素来测试的，这将能够判别出目标在列表里的前半部还是后半部分。如果在前半部分，就不需要查找后半部分。如果在后半部分，就不需要查找前半部分。换句话说，可以通过判断排除一半的列表。重复这个过程直到找到目标或是目标不在这个列表里。顺序查找和折半查找示例程序：public class Search /顺序查找 public int sequentialSearch(int arr, int key) for (int k = 0; k arr.length; k+) if (arrk = key) return k; /
20、成功,返回该数组元素的位置（即索引） return -1; / 失败,返回-1 /折半查找 public int binarySearch(int arr, int key) int low = 0; / 初始化 int high = arr.length - 1; while (low = high) int mid = (low + high) / 2; / 取折半值 if (arrmid = key) return mid; / 成功,返回该数组元素的位置（即索引） else if (arrmid key) low = mid + 1; / 定位查找上半段 else high = mid
21、 - 1; / 定位查找下半段 return -1; / 失败,返回-1 JavaJava程序设计大学教程程序设计大学教程 5.3 对象容器 n使用数组管理对象虽然有较高的计算效率，但是数组要求固定对象的数量，操作起来并不方便。特别当对象数量不明确的情况下，我们需要更复杂的方法来管理对象。nJava类库中提供了一些用于管理对象集的类，称之为容器类（container classes）。它们可以在程序中用作对象的容器，持有和操作对象而不用担心容量的变化。nJava容器的缺点是：一旦把对象放进容器，便失去了该对象的类型信息。容器中对象集的元素都是最基本的Object类型，也就是说，无论是何种类型的
22、对象，进入容器后都向上转型为Object。因此，当我们从容器中取出对象时，可能无法知道它原来的类型。如果知道或者可以通过某种算法来判定出原来的类型，则可以将其转型为最初的实际类型。 JavaJava程序设计大学教程程序设计大学教程 5.3.1 Java容器框架 n列表（列表（list） 按照一定次序排列的对象集，对象之间有次序关系。n集合（集合（set） 无次序的对象集，但这些对象都是唯一的，不会重复。n映射（映射（map） 一群成对的对象集，这些对象各自保持着“键-值”（key-value）对应关系。其中，作为“键”的那些对象一定是一个set，即这些对象是唯一的，不会重复。adacabcde
23、abcv23b012n4v41v23v17dlistmapsetJavaJava程序设计大学教程程序设计大学教程 5.3.2 Collection与Iterator nCollection是Java容器框架中的高层接口，它声明了所有容器类的核心方法，包括添加、清除、比较和持有对象（也称为对象集的元素）的操作。此外，Collection接口还提供了一个方法用于返回Iterator。n迭代器是一个实现了Iterator或ListIterator接口的对象。它是一种“轻量级”的对象，消耗较小的资源，具有较高的效率，能够满足对象集的遍历。JavaJava程序设计大学教程程序设计大学教程 5.3.3 L
24、ist及ListIterator n编程中最常用到的是List容器。List容器的重要属性是对象按次序排列。List通常由ArrayList和LinkList来实现，它提供了列表的插入、删除、定位、截取、遍历等操作。nArrayList 以可变数组实现完成的List容器。允许快速随机访问，但是当元素的插入或移除发生于List中央位置时，效率便很差。对于ArrayList，建议使用ListIterator来进行向后或向前遍历，但而不宜用其来进行元素的插入和删除，因为所花代价远高于LinkedList。nLinkedList 以双向链表（double-linked 1ist）实现完成的List容器
25、。最佳适合遍历，但不适合快速随机访问。插入和删除元素效率较高。它还提供addFirst、addLast、getFirst、getLast、removeFirst、removeLast等丰富的方法，可用于实现栈和队列的操作。JavaJava程序设计大学教程程序设计大学教程 5.4 抽象数据类型 n抽象数据类型（ADT）是把与对该数据类型有意义的操作封装在一起的数据声明。它将数据和操作封装起来，用户可通过操作接口对数据进行操作。常用的抽象数据类型有链表、栈、对列等。JavaJava程序设计大学教程程序设计大学教程 5.4.1 链表 n链表是一组互相链接的元素序列，分为：单链表、循环链表、双向链表等
26、。若在这个序列中每个元素总是与它前面的元素相链接（除第一个元素外），则形成单链表。单链表关系的实现可以通过指针来描述。n在Java类库中，LinkedList可以当作链表使用，它能实现链表常用的操作，包括：增加、删除、定位、遍历等，这足够解决一切关于有序列表的问题。使用LinkedList链表还能实现栈和队列。1000A1200B1312C1423head100012001312D1423空指针指针节点hr非空循环链表rh空表链表示意图 JavaJava程序设计大学教程程序设计大学教程 5.4.2 栈 n栈是限定仅在一端进行插入或删除操作的线性表。栈又称为后进先出（LIFO）线性表，其主要操作
27、为进栈（push）和出栈（pop）。栈的应用非常广泛，如：倒转数据、回溯等。栈栈顶栈栈顶数据栈栈顶栈栈顶数据入栈操作 出栈操作 JavaJava程序设计大学教程程序设计大学教程 5.4.3队列 n队列是线性列表的一种特殊情况，其所有的插入均限定在表的一端进行，而所有的删除则限定在表的另一端进行。队列的结构特点是先进队列的元素先出队列。队列又称为先进先出（FIFO）线性表，其主要操作为入列（enqueue）和出列（dequeue）。对列主要应用于排队处理用户请求、任务和指令。在计算机系统中，需要用队列来完成对作业或对系统设备如打印池的处理。 a1 a2 a3 an队队尾尾队队头头入入列列出出列列
