数据结构与算法-算法设计与分析-王晓东学习资料.ppt

《数据结构与算法-算法设计与分析-王晓东学习资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法-算法设计与分析-王晓东主要内容介绍（续）第7章概率算法第8章NP完全性理论第9章近似算法第10章算法优化策略2第1章算法引论1.1算法与程序1.2表达算法的抽象机制1.3描述算法1.4算法复杂性分析本章主要知识点：31.1算法与程序输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。是满足下述性质的指令序列。算法：程序：41.从机器语言到高

2、级语言的抽象1.2表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；52.抽象数据类型1.2表达算法的抽象机制抽象数据类型是算

3、法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。6在本书中，采用Java语言描述算法。1.Java程序结构1.3描述算法以下，对Java语言的若干重要特性作简

4、要概述。（1）Java程序的两种类型：应用程序和applet区别：应用程序的主方法为main，其可在命令行中用命令语句java应用程序名来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包(packages)的形式组织管理。（3）import语句：在java程序中可用import语句加载所需的包。例如，importjava.io.*;语句加载java.io包。71.3描述算法2.Java数据类型数据类型基本数据类型：详见下页表1-1非基本数据类型：如Byte,Integ

5、er,Boolean,String等。Java对两种数据类型的不同处理方式：对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:intk;对非基本数据类型：语句Strings;并不建立具有数据类型String的对象，而是建立一个类型String的引用对象，数据类型为String的对象可用下面的new语句建立。s=newString(“Welcome”);Strings=newString(“Welcome”);81.3描述算法表格1-1Java基本数据类型类型缺省值分配空间（bits）取值范围booleanfal

6、se1[true,false]byte08[-128,127]charu000016[u0000,uFFFF]double0.064±4.9*10-324~±1.8*10308float0.032±1.4*10-45~±3.4*1038int032[-2147483648,2147483647]long064±9.2*1017short016[-32768,32767]91.3描述算法3.方法在Java中，执行特定任务的函数或过程统称为方法(methods)。例如，java的Math类给出的常见数学计算的方法如下表所示：方法功能方法功能abs(x)

7、x的绝对值max(x,y)x和y中较大者ceil(x)不小于x的最小整数min(x,y)x和y中较小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整数sqrt(x)x的平方根log(x)x的自然对数tan(x)x的正切101.3描述算法3.方法计算表达式值的自定义方法ab描述如下：publicstaticintab(inta,intb){return(a+b+Math.abs(a-b))/2;}（1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中，a和b是形式参数，在调用方法时通

8、过实际参数赋值。（2）方法重载：Java允许方法重载，即允许定义有不同签名的同名