算法与数据结构1.ppt

第五章 算法与数据结构,程序是建立在数据结构基础上使用计算机语言描述的算法，因此简单地讲，程序也可以表示成：算法数据结构。 介绍算法的概念及常用算法。并通过数组、链表、栈、队列等数据结构以及Java对象容器，讨论算法的应用及算法的Java程序实现。,5.1 算法,算法是为了求解某一问题在有限步骤内、定义了具体操作序列的规则集合。一个算法应该具有以下五个重要的特征 ： 确切性（No ambiguity） 算法的每一步骤必须有确切的定义。而不应该有二义性，例如，在算法中不能出现诸如“赋值为100或1000”。 输入（Input） 有0个或多个输入，用于初始化运算对象。所谓0个输入是指无需输入条件，而算法本身定出了初始条件。 输出（Output） 没有输出的算法是毫无意义的。一个算法应该有一个或多个输出，以反映对输入数据加工后的结果。 可行性（Feasibility） 算法原则上能够精确地运行，而且对于算法中的每种运算，在原理上人们应该能用笔和纸做有限次运算后完成。 有穷性（Finite） 算法必须保证执行有限步之后结束。只具有前面四个特征的规则集合，称不上算法。例如，尽管操作系统能完成很多任务，但是它的计算过程并不终止，而是无穷无尽的执行、等待执行，所以操作系统不是算法。,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图、NS盒图、流程图。,程序流程图常用图形符号及控制结构图例,5.1.2 常用算法,基本算法大都比较简单，是其他算法的基础。这类算法在程序中应用非常普遍，如：累加求和、累乘求积、求最大和最小值等。,伪代码描述算法： FindLargest Input: 10 positive integers 1. largest0 2. counter0 3. while(counter largest) then 3.2.1 largesttheInteger end if 3.3 countercounter+1 end while 4. Return largest End,Java语言实现： import java.io.*; public class Max public static void main(String args) throws IOException /初始化 BufferedReader input = new BufferedReader (new InputStreamReader(System.in); int largest=0; int counter=0; int theInteger=0; /循环比较 while(counter largest) largest=theInteger; / while System.out.println(“求出最大数是：“+largest); ,5.1.2 常用算法,排序算法根据数据的值对它们进行排列。排序是为了把不规则的信息进行整理，以提高查找效率。常用的排序方法包括：选择排序、冒泡排序、插入排序、快速排序、合并排序、希尔排序、堆排序等。 查找是一种在列表中确定目标所在位置的算法。基本的查找方法有顺序查找和折半查找。 迭代和递归是用于编写解决问题的算法的两种途径。迭代就是反复替换的意思，它通过使用一个中间变量保存中间结果，不断反复计算求解最终值。递归是一个算法自我调用的过程，用递归调用的算法就是递归算法。,阶乘迭代算法伪代码 ： Factorial Input:Apositive integer num 1. FactN1 2. i1 3. While（i or = num） 3.1 FactNFactN 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 numFactorial(num-1) end if end,5.2 数组,数组用于表示相同类型的元素的有序集合，数组中每个元素都有一个唯一的索引。 根据数组的分配方式可将数组分为：一维数组和多维数组。Java中还可以定义不规则数组。我们可以把一维以上的数组看作是“数组的数组”。,5.2.1 数组的创建和使用,数组是一个被命名的连续存储区域的集合，存放着相同类型的数据项。数组的每个元素通过它在数组里的位置索引来引用。数组索引必须是一个整数值或者一个整数表达式。 在Java里，大多数情况下数组被当成对象来对待。它们是用new操作符来实例化的，有自己的实例变量（例如length，可返回数组中第一维的元素数量）。数组变量是引用类型的变量。 定义与创建一个数组的语法及例子。,定义与创建一个数组的语法： 数组类型名称 数组变量名;/定义数组变量 (也可以写成：数组类型名称 数组变量名;/定义数组变量) 数组变量名 = 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); fruits3 = new Fruit(“草莓“, 1000); fruits4 = new Fruit(“橘子“, 1000); int n = fruits.length; /测试数组长度,用不规则数组实现 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 public class Stock public Stock() for (int week=1;week=52;week+) stockValueweek0=week; for (int weekday=1;weekday=5;weekday+) stockValue0weekday=weekday; int stockIndex = (int)(Math.random()*1000+1000); stockValueweekweekday = stockIndex; public void printStock() for (int week=0;week=52;week+) for (int weekday=0;weekday=5;weekday+) System.out.print(stockValueweekweekday+“t“); System.out.println(); public static void main(String args) Stock s=new Stock(); s.printStock();/打印股指年表 int stockValue= new int536; ,不规则数组演示程序 ArrTest public class ArrTest public ArrTest() for (int n=1;nmyArr.length;n+) myArrn = new intn+1;/创建数组的数组，每个数组的长度不一样。 for (int m=1; mmyArrn.length; m+) myArrnm=m; public void printArr() for (int n=1; nmyArr.length; n+) for (int m=1;mmyArrn.length;m+) System.out.print(myArrnm+“t“); System.out.println(); public static void main(String args) ArrTest arr=new ArrTest(); arr.printArr(); int myArr= new intMax+1;/定义不规则数组，先创建数组的第1维。 static int Max=6; ,5.2.3 排序,冒泡法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮；较大的元素比较重，从而要往下沉。一个含有n个元素的列表，冒泡排序需要n-1次扫描来完成数据排序。 快速排序是对冒泡排序的一种改进。它的基本思想是，通过一轮排序将待排序的数组元素分割成独立的两部分，其中一部分元素的关键字均比另一部分元素的关键字小，则分别可对这两部分元素继续进行排序，以达到整个数组序列有序。,冒泡排序比较和交换的过程演示,5.2.4 查找,顺序查找就是将要查找的数据的关键字按一定的顺序挨个与列表中的数据进行比较，相等时就找到了所要的数据。 对有序的列表可以使用更有效率的折半查找。折半查找是从一个列表的中间的元素来测试的，这将能够判别出目标在列表里的前半部还是后半部分。如果在前半部分，就不需要查找后半部分。如果在后半部分，就不需要查找前半部分。换句话说，可以通过判断排除一半的列表。重复这个过程直到找到目标或是目标不在这个列表里。,顺序查找和折半查找示例程序： public class Search /顺序查找 public int sequentialSearch(int arr, int key) for (int k = 0; k arr.length; k+) if (arrk = key) return k; / 成功,返回该数组元素的位置（即索引） 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 - 1; / 定位查找下半段 return -1; / 失败,返回-1 ,5.3 对象容器,使用数组管理对象虽然有较高的计算效率，但是数组要求固定对象的数量，操作起来并不方便。特别当对象数量不明确的情况下，我们需要更复杂的方法来管理对象。 Java类库中提供了一些用于管理对象集的类，称之为容器类（container classes）。它们可以在程序中用作对象的容器，持有和操作对象而不用担心容量的变化。 Java容器的缺点是：一旦把对象放进容器，便失去了该对象的类型信息。容器中对象集的元素都是最基本的Object类型，也就是说，无论是何种类型的对象，进入容器后都向上转型为Object。因此，当我们从容器中取出对象时，可能无法知道它原来的类型。如果知道或者可以通过某种算法来判定出原来的类型，则可以将其转型为最初的实际类型。,5.3.1 Java容器框架,列表（list） 按照一定次序排列的对象集，对象之间有次序关系。 集合（set） 无次序的对象集，但这些对象都是唯一的，不会重复。 映射（map） 一群成对的对象集，这些对象各自保持着“键-值”（key-value）对应关系。其中，作为“键”的那些对象一定是一个set，即这些对象是唯一的，不会重复。,5.3.2 Collection与Iterator,Collection是Java容器框架中的高层接口，它声明了所有容器类的核心方法，包括添加、清除、比较和持有对象（也称为对象集的元素）的操作。此外，Collection接口还提供了一个方法用于返回Iterator。 迭代器是一个实现了Iterator或ListIterator接口的对象。它是一种“轻量级”的对象，消耗较小的资源，具有较高的效率，能够满足对象集的遍历。,5.3.3 List及ListIterator,编程中最常用到的是List容器。List容器的重要属性是对象按次序排列。List通常由ArrayList和LinkList来实现，它提供了列表的插入、删除、定位、截取、遍历等操作。 ArrayList 以可变数组实现完成的List容器。允许快速随机访问，但是当元素的插入或移除发生于List中央位置时，效率便很差。对于ArrayList，建议使用ListIterator来进行向后或向前遍历，但而不宜用其来进行元素的插入和删除，因为所花代价远高于LinkedList。 LinkedList 以双向链表（double-linked 1ist）实现完成的List容器。