数据结构与算法(JAVA语言版)-2

《数据结构与算法(JAVA语言版)-2》由会员分享，可在线阅读，更多相关《数据结构与算法(JAVA语言版)-2（216页珍藏版）》请在装配图网上搜索。

1、目录第一章Java与面向对象程序设计.1Java语言根底知识.1根本数据类型与运算.1流程控制语句.3字符串.3数组.5Java的面向对象特性.7类与对象.7继承.9接口.10异常.11Java与指针.12数据结构与算法根底.15数据结构.15根本概念.15抽象数据类型.17小结.19算法与性能分析.19算法.19时间复杂性.20空间复杂性.24算法时间复杂度分析.25最正确、最坏与平均情况分析.27均摊分析.29线性表.32线性表与抽象数据类型.32线性表定义.32线性表的抽象数据类型.32List接口.34Strategy接口.35线性表的顺序存储与实现.36线性表的链式存储与实现.42单

2、链表.42双向链表.46线性表的单链表实现.48两种实现的比照.53基于时间的比拟.53基于空间的比拟.53表.54基于结点的操作.54表接口.54基于双向链表实现的表.561.11.21.31.4第二章2.12.2第三章3.13.23.33.43.511 / 2163.6第四章4.1迭代器.59栈与队列.62栈.62栈的定义与抽象数据类型.62栈的顺序存储实现.63栈的链式存储实现.65队列.66队列的定义与抽象数据类型.66队列的顺序存储实现.68队列的链式存储实现.71堆栈的应用.72进制转换.72括号匹配检测.73迷宫求解.74递归.78递归与堆栈.78递归的概念.78递归的实现与堆栈

3、.80基于归纳的递归.81递推关系求解.83求解递推关系的常用方法.83线性齐次递推式的求解.85非齐次递推关系的解.86MasterMethod.87分治法.89分治法的根本思想.89矩阵乘法.91选择问题.93树.96树的定义与根本术语.96二叉树.99二叉树的定义.99二叉树的性质.99二叉树的存储结构.101二叉树根本操作的实现.105树、森林.112树的存储结构.112树、森林与二叉树的相互转换.114树与森林的遍历.115由遍历序列复原树结构.116Huffman树.117二叉编码树.117Huffman树与Huffman编码.118图.1234.24.3第五章5.15.25.35

4、.4第六章6.16.26.36.46.5第七章24.44.5图的定义.123图与根本术语.123抽象数据类型.127图的存储方法.129邻接矩阵.129邻接表.131双链式存储结构.132图ADT实现设计.138图的遍历.139深度优先搜索.139广度优先搜索.142图的连通性.143无向图的连通分量和生成树.143有向图的强连通分量.144最小生成树.145最短距离.151单源最短路径.151任意顶点间的最短路径.155有向无环图与其应用.1574.64.74.84.94.10拓扑排序.157关键路径.159第八章查找.164查找的定义.164根本概念.164查找表接口定义.165顺序查找与

5、折半查找.165查找树.168二叉查找树.168AVL树.175B-树.183哈希.188哈希表.189哈希函数.190冲突解决.191排序.194排序的根本概念.194插入类排序.195直接插入排序.195折半插入排序.196希尔排序.197交换类排序.199起泡排序.199快速排序.200选择类排序.2028.18.28.38.4第九章9.19.29.39.43简单项选择择排序.202树型选择排序.203堆排序.204归并排序.208基于比拟的排序的比照.209在线性时间排序.211计数排序.211基数排序.2129.59.69.74 周鹏单位：三峡大学理学院周鹏第一章Java 与面向对象

6、程序设计在这一章中向读者简要介绍有关Java的根本知识。Java语言是一种广泛使用并且具有许多良好的如面向对象、可移植性、强健性等特性的计算机高级程序设计语言，在这里对Java 的介绍不可能面面俱到，因此在第一章中只对理解书中Java 代码的相关知识进展介绍。对于熟悉Java的读者可以不阅读本章。1.1Java语言根底知识根本数据类型与运算在Java中每个变量在使用前均必须声明它的类型。Java共有八种根本数据类型：四种是整型，两种浮点型，一种字符型以与用于表示真假的布尔类型。各种数据类型的细节如表1-1所示。表1-1Java数据类型类型存储空间32bit围-2147483648,214748

7、3647-32768,32767intshortlongbytefloat16bit64bit8bit-08,07-128,12732bit64bit16bit1bit-3.4E38,3.4E38doublechar-1.7E308,1.7E308Unicode字符booleanTrue,false在声明一个变量时，应先给出此变量的类型，随后写上变量名。在声明变量时一行中可以有声明多个变量，并且可以在声明变量的同时对变量进展初始化。例如：inti;doublex,y = 1.2;char c=z;booleanflag;在程序设计中，常常需要在不同的数字数据类型之间进展转换。图1-1 给出了数

8、字类型间的合法转换。1charintbyteshortlongfloatdouble图1-1数字类型间的合法转换图1-1中六个实箭头表示无信息损失的转换，而三个虚箭头表示的转换那么可能会丧失精有时在程序设计中也需要进展在图1-1中没有出现的转换，在Java中这种数字转换也度。是可以进展的，不过信息可能会丧失。在可能丧失信息的情况下进展的转换是通过强制类型转换来完成的。其语法是在需要进展强制类型转换的表达式前使用圆括号，圆括号中是需要转换的目标类型。例如：doublex = 7.8;int n= (int)x;/x等于7Java使用常见的算术运算符*进展加、减、乘、除的运算。当除法运算符作用于两

9、个整数时，是进展整数除法。整数的模即求余运算使用 % 运算符。对整型变量一种最常见的操作就是递增与递减运算，与C/C+一样Java也支持递增和递减运算符。例如：intn=7, m=2;doubled = 7;n= n/ m;d/= m;/n等于3/d等于3.5/n等于2/a等于4n-;inta=2 * n+;intb =2 * +m;/b等于6此外Java还具有完备的关系运算符，如=是否相等,小于,大于,=小于等于,=大于等于,!=不等于；并且Java使用&表示逻辑与，|表示逻辑或，!表示逻辑非；以与七种位运算符&与、|或、异或、非、右移、高位填充0的右移。最后Java还支持一种三元运算符?:

10、，这个运算符有时很有用。它的形式为condition?e1 :e2这是一个表达式，在condition为true时返回值为e1，否那么为e2。例如：min=x y? x:y;那么min为x 与y 中的较小值。2流程控制语句计算机高级语言程序设计中共有三种流程结构，分别是：顺序、分支、循环。其中分支与循环流程结构需要使用固定语法的流程控制语句来完成。Java 中有两种语句可用于分支结构，一种是if条件语句，另一种是switch多项选择择语句。条件语句的形式如下：if (condition)statement1elsestatement2当if后的条件condition的值为true时执行stat

11、ement1中的语句，否那么执行statement2中的语句。多项选择择语句的形式为：switch (integer expression) casevalue1: block1; break;casevalue2: block2; break;casevalueN:blockN; break;default: default block;switch语句从与选择值相匹配的case标签处开场执行，一直执行到下一个break 处或者switch的末尾。如果没有相匹配的case标签，而且存在default 子句，那么执行default子句。如果没有相匹配的 case标签，并且没有default子句

12、，那么完毕switch语句的执行，执行switch后面的语句。Java 中的循环语句主要有三种，分别是for 循环、while 循环、dowhile循环。for 循环的形式为：for (initialization;condition;increment) statement;for语句的循环控制的第一局部通常是对循环变量的初始化，第二局部给出进展循环的测试条件，第三局部那么是对循环变量的更新。while 循环的形式为：while(condition)statement;while 循环首先对循环条件进展测试，只有在循环条件满足的情况下才执行循环体。dowhile循环的形式为：do state

13、ment while(condition);与while循环不同的是，dowhile循环首先执行一次循环体，当循环条件满足时那么继续进展下一次循环。字符串字符串是指一个字符序列。在 Java 中没有置的字符串类型，而是在标准 Java库中包含一个名为String的预定义类。每个被一对双引号括起来的字符序列均是String类的一个实例。字符串可以使用如下方式定义。3String s1=null;String s2 = ;/s1 指向NULL/s2是一个不包含字符的空字符串String s3 = Hello;Java允许使用符号把两个字符串连接在一起。当连接一个字符串和一个非字符串时，后者将被转换

14、成字符串，然后进展连接。例如：s3 = s3+ World!;/s3为HelloWorld!/s4 为abc123String s4=abc +123;Java的String类包含许多方法，其中多数均非常有用，在表1-2中只给出最常用的一些方法。表1-2Java String类常用方法charcharAt(intindex)Returnsthecharvalueatthespecifiedindex.intcompareTo(String anotherString)Compares two strings lexicographically.intcompareToIgnoreCase(St

15、ring str)Compares two strings lexicographically,ignoring case differences.booleanendsWith(String suffix)Tests if this string ends with the specifiedsuffix.booleanequals(Object anObject)Comparesthisstringtothespecifiedobject.booleanequalsIgnoreCase(String anotherString)Compares this String to another

16、 String,ignoring case considerations.intindexOf(String str)Returns the index within this string of thefirst occurrence of the specified substring.intlastIndexOf(String str)Returns the index within this string of therightmost occurrence of the specified substring.intlength()Returns the length of this

17、 string.booleanstartsWith(String prefix)Testsifthisstringstartswiththespecifiedprefix.Stringsubstring(intbeginIndex)Returnsanewstringthatisasubstringofthisstring.Stringsubstring(intbeginIndex, int endIndex)Returnsanewstringthatisasubstringofthisstring.chartoCharArray()Convertsthisstringtoanewcharacterarray.4StringtoLowerCase()ConvertsallofthecharactersinthisStringto lower case using the rules of the default locale.StringtoString()This object (which is already a string!) isitself returned