数据结构及算法JAVA语言版

《数据结构及算法JAVA语言版》由会员分享，可在线阅读，更多相关《数据结构及算法JAVA语言版（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.513.6第四章4.1迭代器.59栈与队列.62栈.62栈的定义及抽象数据类型.62栈的顺序存储实现.63栈的链式存储实现.65队列.66队列的定义及抽象数据类型.66队列的顺序存储实现.68队列的链式存储实现.71堆栈的应用.72进制转换.72括号匹配检测.73迷宫求解.74递归.78递归与堆栈.78递归的概念.78递归的实现与堆栈.80基于归纳

3、的递归.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第六章6.

4、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顺序查找与折半查找.16

5、5查找树.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,2147483647-32

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

8、转换。1charintbyteshortlongfloatdouble图1-1数字类型间的合法转换图1-1中六个实箭头表示无信息损失的转换，而三个虚箭头表示的转换则可能会丧失精有时在程序设计中也需要进展在图1-1中没有出现的转换，在Java中这种数字转换也度。是可以进展的，不过信息可能会丧失。在可能丧失信息的情况下进展的转换是通过强制类型转换来完成的。其语法是在需要进展强制类型转换的表达式前使用圆括号，圆括号中是需要转换的目标类型。例如：double* = 7.8;int n= (int)*;/*等于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、有用。它的形式为conditione1 :e2这是一个表达式，在condition为true时返回值为e1，否则为e2。例如：min=* y *:y;则min为* 与y 中的较小值。2流程控制语句计算机高级语言程序设计中共有三种流程构造，分别是：顺序、分支、循环。其中分支与循环流程构造需要使用固定语法的流程控制语句来完成。Java 中有两种语句可用于分支构造，一种是if条件语句，另一种是switch多项选择择语句。条件语句的形式如下：if (condition)statement1elsestatement2当if后的条件condition的值为true时执行statement1中的语句，否则

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

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

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

14、s3+ World!;/s3为HelloWorld!/s4 为abc123String s4=abc +123;Java的String类包含许多方法，其中多数均非常有用，在表1-2中只给出最常用的一些方法。表1-2Java String类常用方法charcharAt(intinde*)Returnsthecharvalueatthespecifiedinde*.intpareTo(String anotherString)pares two strings le*icographically.intpareToIgnoreCase(String str)pares two strings le

15、*icographically,ignoring case differences.booleanendsWith(String suffi*)Tests if this string ends with the specifiedsuffi*.booleanequals(Object anObject)paresthisstringtothespecifiedobject.booleanequalsIgnoreCase(String anotherString)pares this String to another String,ignoring case considerations.i

16、ntinde*Of(String str)Returns the inde* within this string of thefirst occurrence of the specified substring.intlastInde*Of(String str)Returns the inde* within this string of therightmost occurrence of the specified substring.intlength()Returns the length of this string.booleanstartsWith(String prefi

17、*)Testsifthisstringstartswiththespecifiedprefi*.Stringsubstring(intbeginInde*)Returnsanewstringthatisasubstringofthisstring.Stringsubstring(intbeginInde*, int endInde*)Returnsanewstringthatisasubstringofthisstring.chartoCharArray()Convertsthisstringtoanewcharacterarray.4StringtoLowerCase()ConvertsallofthecharactersinthisStringto lower case using the rules of the default locale.StringtoString()This object (which is already a string!) isitself returned.StringtoUpperCase()ConvertsallofthecharactersinthisStringto upper case u