Java常用算法手册(第3版)(txt+pdf+epub+mobi电子书下载)

作者:宋娟

出版社:中国铁道出版社有限公司

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

Java常用算法手册(第3版)

Java常用算法手册(第3版)试读:

前言

Foreword

信息社会进入云计算时代,最为明显的特征就是“各种云终端+云服务器应用的组合而成。不管是编写服务器端的程序,还是编写PC、平板电脑、手机等云终端上的应用程序,采用Java基本上都是最常见的选择。而一个应用程序往往由编程语言、数据结构和算法组成。其中,算法是整个程序设计的核心。算法代表着求解具体问题的手段和方法,可以毫不夸张地说,算法是一切程序设计的灵魂和基础。选择合理的算法,可以起到事半功倍的效果。因此,对于程序员来说,学习和掌握算法成为重中之重。同时,各大公司招聘Java程序员时,除基本语法之外,算法的掌握程度也是考核的重点方面。

本书特色

为了保证读者掌握算法这个程序设计的核心技术,笔者一开始就为本书规划了一些特色,以保证它的质量和生命力。和其他书籍相比,本书有如下优点:(1)本书由浅入深,循序渐进地带领读者逐步深入学习算法和数据结构的知识。(2)本书在讲解每个知识点的同时,均给出了相应的算法原理、算法实现,同时还给出了完整的实例,每个实例都可以运行,使得读者可以快速掌握对应知识点如何应用在程序设计中。(3)本书在介绍各个知识点的时候,尽量结合历史背景并给出了问题的完整分析,使读者可以了解问题的来龙去脉,避免了代码类书籍的枯燥乏味。(4)本书对每一个实例的程序代码都进行了详细的注释和分析,并给出了运行结果,使得读者更加容易理解。(5)本书中的所有代码均采用应用较为广泛的Java语言进行编写。但是这些算法本身并不仅局限于Java语言,读者如果采用C++、C、C#、VB等其他编程语言,只需按照对应的语法格式进行少量的修改即可使用。

本书的内容

本书以实用性、系统性、完整性和前沿性为重点,详细介绍了算法的基本思想和在不同领域的应用实例。本书分为三篇,共14章内容。

第1篇 算法基础篇: 本篇共3章,详细介绍了算法和数据结构的相关知识。本篇内容中既有对算法的深入诠释,更有作者对算法基本思想的经验分享。读者可通过本篇内容细致有序地建立起对算法理解的知识性框架。

第2篇 算法应用篇: 本篇共7章,详细讲解了算法在排序、查找、数学计算、数论、历史趣题和游戏中的应用。本篇可称为本书中的出彩部分,用实例嵌入知识讲解方式对各类算法进行了翔实地阐述;同时用一些贴近现实的生动实例对算法进行了有趣的表述,提升读者的编程能力和学习兴趣。

第3篇 算法面试篇: 本篇共4章,详细讲解了常见面试中的算法。本篇中我们对面试题进行了细分,分别为上机类、逻辑推理类、教学能力类和基础-扩展算法面试类,通过对这些面试类试题的详细分析,拓展读者的思维,提升能力。

适合的读者

・大专院校相关专业的学生及教师;

・系统开发人员;

・程序设计初学者;

・Java程序员;

・计算机程序设计爱好者。

附书附赠光盘

本书光盘中包含两大部分,第一部分有:本书第14章的PDF电子档、书中源代码以及总计20讲的Java算法讲解视频,总时长约600分钟。第二部分则是一套电子书,以下是对这套电子书的详细说明。

算法是一个程序员成长的关键,但要完全掌握Java开发技能,还需要学习其他知识,本光盘是在纸质算法图书之外,额外提供一套“Java程序员成长之路”,希望以一本算法书+一张配套电子书光盘,形成一个Java学习的完整解决方案。为此,我们设计了一个大学生能成长为Java程序员需要的全部图书的电子版,从基础到开发参考全包含:(1)《打通经脉——Java基础入门编程详解》(2)《关键技术——JSP与JDBC应用详解》(3)《独门架构——Java Web开发应用详解》(4)《神兵利器——Eclipse开发技术详解》(5)《开发参考——JSTL网络标签与SSH类参考手册》

本系列电子书针对的是想成为Java专业开发人员的读者(大学高年级和工作前3年的职场新人),给他们一揽子的解决方案,能够系统学习各个Java开发的知识和技能的方方面面。既能学会语言基础、面向对象这些基本内容,也能学到Spring、Struts、Hibernate这些真正Java开发人员必须掌握的高级开发框架技术方面的内容,目标是,学完全套图书的读者,能达到工作1-2年的Java程序员水平,覆盖大多数公司招聘Java程序员的技术要求范围。

本书由宁夏大学副教授宋娟编写,因时间仓促,不当之处,还请读者不吝指出,以期在以后的改版中进行改进。编者2016年3月第1章算法和实现算法的Java语法

计算机技术,特别是计算机程序设计大大改变了人们的工作方式。现代的设计任务大多通过计算机编程交给计算机来完成。其中,算法起到了至关重要的作用。可以毫不夸张地说,算法是一切程序设计的灵魂和基础。本章介绍算法的一些基本概念、发展历史、算法表示、本书具体实现算法的Java语言语法和应用等。1.1建立算法初步概念

很多开发者都知道“程序=数据结构+算法”这个著名的公式,但却并不真正明白算法的定义或者概念。1.1.1 什么是算法

究竟什么是算法(algorithm)呢?从字面意义上理解,算法即用于计算的方法,通过这种方法可以达到预期的计算结果。

此外,在一般的教科书或者字典中也有关于算法的专业解释,例如,算法是解决实际问题的一种精确描述方法、算法是对特定问题的求解步骤的一种精确描述方法等。目前,被广泛认可的算法的专业定义是,算法是模型分析的一组可行的、确定的和有穷的规则。

其实,通俗地讲,算法可以理解为一个完整的解题步骤,由一些基本运算和规定的运算顺序构成。通过这样的解题步骤可以解决特定的问题。从计算机程序设计的角度看,算法由一系列求解问题的指令构成,能够根据规范的输入,在有限的时间内获得有效的输出结果。算法代表了用系统的方法来描述解决问题的一种策略机制。

举一个例子来分析算法是如何在现实生活中发挥作用的。最典型的例子就是统筹安排,假设有3件事(事件A、事件B和事件C)要做:

・做事件A需要耗费5分钟;

・做事件B需要耗费5分钟但需要15分钟的时间才可以得到结果,如烧水等待水开的过程;

・做事件C需要耗费10分钟。

那么应该怎样来做这三件事情呢?一种方法是依次做,如图1-1所示,做完事件A,再做事情B,最后做事情C。这样,总的耗时为5+(5+15)+10=35分钟,这显然是浪费时间的一种方法。

在实际生活中比较可取的方法是,先做事件B,在等待事件B完成的过程中做事件A和事件C。这样,等待事件B完成的15分钟正好可以完成事件A和事件C。此时,总的耗时为5+15=20分钟,效率明显提高,如图1-2所示。图1-1 方法一图1-2 方法二

在上述例子中提到的两种方法就可以看作两种算法。第一种算法效率低,第二种算法效率高,但都达到了做完事情的目的。从这个例子可以看出,算法也是有好坏区别的,好的算法可以提高工作的效率。算法的基本任务是针对一个具体的问题,找到一个高效的处理方法,从而获得最佳的结果。

一个典型的算法一般都可以从中抽象出5个特征:有穷性、确切性、输入、输出和可行性。下面结合上述例子来分析这5个特征。

・有穷性:算法的指令或者步骤的执行次数是有限的,执行时间也是有限的。例如,在上面的例子中,通过短短的几步就可以完成任务,而且执行时间都是有限的。

・确切性:算法的每一个指令或者步骤都必须有明确的定义和描述。例如,在上面的例子中,为了完成三件事情的任务,每一步做什么事情都有明确的规定。

・输入:一个算法应该有相应的输入条件,用来刻画运算对象的初始情况。例如,在上面的例子中,有三个待完成的事件(事件A、事件B和事件C),这三个事件便是输入。

・输出:一个算法应该有明确的结果输出。这是容易理解的,因为没有得到结果的算法毫无意义。例如,在上面的例子中,输出结果便是三件事情全部做完了。

・可行性:算法的执行步骤必须是可行的,且可以在有限时间内完成。例如,在上面的例子中,每一个步骤都切实可行。其实,无法执行的步骤也是毫无意义的,解决不了任何实际问题。

目前,算法的应用非常广泛,常用的算法包括递推算法、递归算法、穷举算法、贪婪算法、分治算法、动态规划算法和迭代算法等多种。本书将逐步向读者展示各种算法的原理和应用。1.1.2 算法的发展历史

关于算法的起源,可以追溯到我国古代公元前1世纪的《周髀算经》,它是算经的十书之一,原名《周髀》,主要阐述古代中国的盖天说和四分历法。在唐朝的时候,此书被定为国子监明算科的教材之一,并改名为《周髀算经》。算法在我国古代称为“演算法”。《周髀算经》中记载了勾股定理、开平方问题、等差级数问题等,其中用到了相当复杂的分数算法和开平方算法等。在随后的发展中,出现了割圆术、秦九韶算法和剩余定理等一些经典算法。

在西方,公元9世纪波斯数学家al-Khwarizmi提出了算法的概念。“算法”最初写为algorism,意思是采用阿拉伯数字的运算法则。到了18世纪,算法正式命名为algorithm。由于汉字计算的不方便,导致我国古代算法的发展比较缓慢,而采用阿拉伯数字的西方国家则发展迅速。例如,著名的欧几里德算法(又称辗转相除法)就是典型的算法。

在历史上,Ada Byron被认为是第一个程序员。她在1842年编写的巴贝奇分析机上的伯努利方程的求解算法程序虽然未能执行,但奠定了计算机算法程序设计的基础。

后来,随着计算机的发展,在计算机中实现各种算法已成为可能。算法在计算机程序设计领域又得到了重要发展。目前,几乎所有的程序员编程时,无论采用何种编程语言,都需要与算法打交道。1.1.3 算法的分类

算法是一门古老且庞大的学科,随着历史的发展,演化出多种多样的算法。按照不同的应用和特性,算法可以分为不同的类别。

1)按照应用来分类

按照算法的应用领域,即解决的问题,算法可以分为基本算法、数据结构相关的算法、几何算法、图论算法、规划算法、数值分析算法、加密/解密算法、排序算法、查找算法、并行算法和数论算法等。

2)按照确定性来分类

按照算法结果的确定性来分类,算法可以分为确定性算法和非确定性算法。

・确定性算法:这类算法在有限的时间内完成计算,得到的结果是唯一的,且经常取决于输入值。

・非确定性算法:这类算法在有限的时间内完成计算,但是得到的结果往往不是唯一的,即存在多值性。

3)按照算法的思路来分类

按照算法的思路来分类,算法可以分为递推算法、递归算法、穷举算法、贪婪算法、分治算法、动态规划算法和迭代算法等多种算法。1.2算法相关概念的区别

算法其实是一个很抽象的概念,往往需要依托于具体的实现方法才能体现其价值,如在计算机编程中的算法、数值计算中的算法等。本书重点讲解的便是算法在计算机编程中的应用。算法具有抽象性,容易混淆,这里有必要说明一些基本的概念。1.2.1 算法与公式的关系

根据前面所谈到的算法,读者很容易联想到数学中的公式。公式用于解决某类问题,有特定的输入和结果输出,能在有限时间内完成,并且公式都是完全可以操作计算的。公式确实提供了一种算法,但算法绝不完全等于公式。

公式是一种高度精简的计算方法,可以认为就是一种算法,它是人类智慧的结晶。而算法并不一定是公式,算法的形式可以比公式更复杂,解决的问题更加广泛。1.2.2 算法与程序的关系

正如前面所述,算法依托于具体的实现方式。虽然一提到算法,就使人联想到计算机程序设计,但算法并非仅用于此。例如,在传统的笔算中,通过纸和笔按照一定的步骤完成的计算也是算法的应用;在速记中,人们通过特殊的方法来达到快速牢固记忆的目的,这也是一种算法的应用。

在计算机程序设计中,算法的体现更广泛,几乎每个程序都需要用到算法,只不过有些算法比较简单,有些算法比较复杂而已。

算法和程序设计语言是不同的。目前比较流行的程序设计语言,包括Visual Basic、C、C++、C#、Java、Pascal、Delphi、PB等。程序设计语言是算法实现的一种形式,也是一种工具。读者往往需要首先熟悉程序设计语言的语法格式,然后才能使用这种程序语言编写合适的算法实现程序。学习一门程序设计语言是比较容易的,难的是如何正确合理地运用算法来编写求解问题。1.2.3 算法与数据结构的关系

数据结构是数据的组织形式,可以用来表征特定的对象数据。在计算机程序设计中,操作的对象是各式各样的数据,这些数据往往拥有不同的数据结构,如数组、结构体、联合、指针和链表等。因为不同的数据结构所采用的处理方法不同,计算的复杂程度也不同,因此算法往往依赖于某种数据结构。也就是说,数据结构是算法实现的基础。

计算机科学家尼克劳斯·沃思(Nikiklaus Wirth)曾提出了一个著名的公式:数据结构+算法=程序。后来,他为此著有《数据结构+算法=程序》一书。从中可以看到算法和数据结构的关系。

学习了前面的介绍,读者应对程序、算法、数据结构、程序设计语言有一个比较深刻的认识。如果给出一个公式,则可以表述成如下形式:数据结构+算法+程序设计语言=程序

这里,数据结构往往表示的是处理的对象,算法是计算和处理的核心方法,程序设计语言是算法的实现方法。这几者的综合便构成一个实实在在的程序。

注意: 算法是解决问题的一个抽象方法和步骤,同一个算法在不同的语言中具有不同的实现形式,这依赖于数据结构的形式和程序设计语言的语法格式。1.3算法的表示

算法是为了解决实际问题的,问题简单,算法也简单;问题复杂,算法也相应复杂。为了便于交流和进行算法处理,往往需要将算法进行描述,即算法的表示。一般来说,算法可以采用自然语言表示、流程图表示、N-S图表示和伪代码表示。1.3.1 自然语言表示

所谓自然语言,就是自然地随文化演化的语言,如英语、汉语等。通俗地讲,自然语言就是人们平时口头描述的语言。对于一些简单的算法,可以采用自然语言来口头描述算法的执行过程,如前面的统筹安排事件的例子。

但是,随着需求的发展,很多算法都比较复杂,很难用自然语言描述,同时自然语言的表述烦琐难懂,不利于发展和交流。因此,需要采用其他的方法来进行表示。

其实,我国古代早期的算法也可以看作自然语言表示。正是由于这种复杂、烦琐的自然语言表示,大大阻碍了中国古代算法的发展。这也正是为何我国古代算法起源早,但后来落后于西方国家的原因。1.3.2 流程图表示

流程图是用一种图形表示算法流程的方法,其由一些图框和流程线组成,如图1-3所示。其中,图框表示各种操作的类型,图框中的说明文字和符号表示该操作的内容,流程线表示操作的先后次序。

流程图最大的优点是简单直观、便于理解,在计算机算法领域有着广泛的应用。例如,计算两个输入数据a和b的最大值,可以采用图1-4所示的流程图来表示。图1-3 流程图的图元图1-4 求最大值的流程图

在实际使用中,一般采用如下三种流程结构。

1)顺序结构

顺序结构是最简单的一种流程结构,简单地一个接着一个地进行处理,如图1-5所示。一般来说,顺序结构适合于简单的算法。

2)分支结构

分支结构常用于根据某个条件来决定算法的走向,如图1-6所示。这里首先判断条件P,如果P成立,则执行B;否则执行A,然后再继续下面的算法。分支结构有时也称为条件结构。图1-5 顺序结构图1-6 分支结构

3)循环结构

循环结构常用于需要反复执行的算法操作,按照循环的方式,可以分为当型循环结构和直到型循环结构,分别如图1-7和图1-8所示。图1-7 当型循环结构图1-8 直到型循环结构

当型循环结构和直到型循环结构的区别如下:

・当型循环结构先对条件进行判断,然后再执行,一般采用while语句来实现;

・直到型循环结构先执行,然后再对条件进行判断,一般采用until、do…while语句来实现。

注意: 无论当型循环结构还是直到型循环结构,都需要进行合适的处理,以保证能够跳出循环;否则构成死循环是没有任何意义的。

一般来说,采用上述三种流程结构,可以完成所有的算法任务。通过合理安排流程结构,可以构成结构化的程序,这样便于算法程序的开发和交流。1.3.3 N-S图表示

N-S图也称为盒图或者CHAPIN图,1973年由美国学者I.Nassi和B.Shneiderman提出。他们发现采用流程图可以清楚地表示算法或程序的运行过程,但其中的流程线并不是必需的,因此而创立了N-S图。在N-S图中,将整个程序写在一个大框图内,这个大框图由若干个小的基本框图构成。采用N-S图也可以方便地表示流程图的内容。

采用N-S图表示的顺序结构,如图1-9所示。采用N-S图表示的分支结构,如图1-10所示。采用N-S图表示的当型循环结构,如图1-11所示。采用N-S图表示的直到型循环结构,如图1-12所示。图1-9 顺序结构图1-10 分支结构图1-11 当型循环结构图1-12 直到型循环结构1.3.4 伪代码表示

伪代码(Pseudocode)是另外一种算法描述的方式。伪代码并非真正的程序代码,其介于自然语言和编程语言之间。因此,伪代码并不能在计算机中运行。使用伪代码的目的是将算法描述成一种类似于编程语言的形式,如C、C++、Java、Pascal等。这样,程序员便可以很容易理解算法的结构,再根据编程语言的语法特点,稍加修改,即可实现一个真正的算法程序。

能够使用伪代码的一个重要原因是C语言的广泛应用,其他语言(例如C++、Java、C#等)大都借鉴了C语言的语法特点。这些编程语言在很大程度上都和C语言类似,例如,都采用if语言表示条件分支和判断,采用for语句、while语句表示循环等。因此,可以利用这些共性来描述算法,而忽略编程语言之间的差异。

在使用伪代码表示算法时,程序员可以使用自然语言来进行表述,也可以采用简化的编程语句来表示,相当灵活。不过,为了编程代码的交流和重利用,程序员还是应该尽可能地将其表述清楚。

下面举一个简单的伪代码表示的程序代码的例子。

程序结束

在上述代码中,演示的是求两个数据最大值的伪代码。首先将输入的数据分别赋值给变量a和变量b,然后通过if语句进行判断,将最大者赋值给变量max,最后输出变量max。从这个例子可以看出,伪代码表示很灵活,但又高度接近编程语言。程序员可以根据这段伪代码和某种编程语言的语法特点进行修改,从而得到真正可执行的程序代码。

在使用伪代码时,描述应该结构清晰、代码简单、可读性好,这样才能够更有利于算法的表示。否则,将适得其反,让人很难懂,就失去伪代码表示的意义了。1.4算法的性能评价

算法其实就是解决问题的一种方法,一个问题的解决往往可以采用多种方法,但每种方法所用的时间和得到的效果往往是不一样的。从前面的统筹安排的例子可以看出,好的算法执行效率高,所耗费的时间短;差的算法则往往需要耗费更多的时间,从而导致效率很低。

算法的一个重要任务便是找到合适的、效率最高的解决问题的方法,即最好的算法。从理论上来讲,这就需要对算法的性能有一个合理的评价。一个算法的优劣往往通过算法复杂度来衡量,算法复杂度包括时间复杂度和空间复杂度两个方面。1.4.1 时间复杂度

时间复杂度即通常所说的算法执行所需要耗费的时间,时间越短,算法越好。一个算法执行的时间往往无法精确估计,通常需要在实际的计算机中运行才能够知道。但是,也可以对算法代码进行估计,而得到算法的时间复杂度。

首先,算法代码执行的时间往往和算法代码中语句执行的数量有关。由于每条语句执行都需要时间,语句执行的次数越多,整个程序所耗费的时间就越长。因此,简短、精悍的算法程序往往执行速度快。

另外,算法的时间复杂度还与问题的规模有关。这方面在专门的算法分析中有详细的分析,这里限于篇幅就不再详述了。有兴趣的读者可以参阅算法分析相关的书籍。1.4.2 空间复杂度

空间复杂度指的是算法程序在计算机中执行所需要消耗的存储空间。空间复杂度其实可以分为如下两个方面:

・程序保存所需要的存储空间,即程序的大小。

・程序在执行过程中所需要消耗的存储空间资源,如程序在执行过程中的中间变量等。

一般来说,程序的大小越小,执行过程中消耗的资源越少,这个程序就越好。在算法分析中,空间复杂度有更为详细的度量,这里限于篇幅就不再赘述了,有兴趣的读者可以阅读相关的书籍。1.5一个算法实例

通过前面的介绍,读者可对算法有一个更为清晰的认识。算法是一个抽象的解决问题的方法,需要依托于具体的实现手段才能体现其价值。由于本书重点讨论的是计算机程序设计中的算法,因此这里的实现手段可以狭隘地认为是编程语言,如C、C++、C#、Basic、Java、Pascal等。

在本书中以流行的Java语言为例来介绍各种算法的原理和应用。对于其他编程语言,只要熟悉算法的原理和编程语言的语法特点,只需对代码稍加修改,就可以很方便地进行移植。

明确了编程语言之后,还需要确定编程工具。目前流行的Java语言集成开发环境包括JDK、NetBeans、JBuiler、Eclipse等。本书选用了应用最为广泛的Eclipse集成开发环境,版本为Indigo Release。本书中的所有程序都可以不加修改或者稍加修改便可以在其他集成开发环境中运行。

在正式进入算法讲解之前,本节先带领读者在Eclipse集成开发环境中完成一个简单的算法程序的编写、调试和应用。在后面的章节中,将会直接给出算法的源代码和运行结果,而不会再赘述本节的操作步骤,以便于突出重点。1.5.1 查找数字

在一个数组中查找数据是经常用到的操作,如在一个班级学生档案集中查找某个学生的记录等。这里将此问题进行简化,程序随机生成一个20个整数数据的数组,然后输入要查找的数据。接着,可以采用最简单的逐个对比的方法进行查找,即顺序查找的方法,这种方法的伪代码示例如下。

上述伪代码仅表示了算法的一个基本流程,并非真正的算法程序代码。但从这里可以看出该程序的基本结构。首先输入待查找的数据,并生成一个随机的数据数组,然后从头到尾对数据进行逐个比较,当数据相等时找到数据,并输出该数据的位置。

下面给出该算法的完整的Java语言代码。【程序1-1】

在该程序中,main()方法生成20个随机数,然后for语句和if语句进行顺序查找。当查找到该数据时,便退出查找,输出该数据的位置;否则输出没找到数据。1.5.2 创建项目

明确算法程序后,即可在Eclipse集成开发环境中执行该程序。首先,需要创建一个Java项目,并添加一个空的源程序文件供代码编写。主要操作步骤如下:(1)启动Eclipse集成开发环境。(2)选择File→New命令,打开New Project对话框,如图1-13所示。图1-13 New Project对话框(3)在Java节点下选择Java Project选项。(4)单击Next按钮,在弹出的对话框中的Project name文本框中输入工程名P1,其他采用默认设置,如图1-14所示。(5)单击Next按钮,此时弹出Java Settings对话框,如图1-15所示。该对话框中列出了创建项目所依赖的系统库等信息。图1-14 输入工程名“P1”图1-15 Java Settings对话框(6)单击Finish按钮,完成项目的建立。此时只是一个空项目,项目中没有任何文件,如图1-16所示。图1-16 空项目(7)下面需要在该项目中添加源代码文件。选择File→New→Class命令,打开New Java Class对话框,如图1-17所示。图1-17 New Java Class对话框(8)在New Java Class对话框的Name文本框中输入源代码文件的名称P1_1,并选择public static void main(String[] args)复选框。(9)单击Finish按钮,该文件将自动添加到该项目中。

这样,便完成了一个基本Java项目的创建。这里创建的Java文件是一个框架,只需将前面的【程序1-1】输入其中即可。1.5.3 编译执行

下面需要在Eclipse集成开发环境中对该程序进行编译和运行。编译和运行的操作步骤如下:(1)Eclipse默认支持自动编译,不需要手动编译。如图1-18所示,确认Build Automatically选项被选中。源代码如果有语法错误,错误行前面会有明显的错误提示标记。图1-18 确认Build Automatically选项(2)运行程序,在文件上右击,在弹出的快捷菜单中选择Run As→Java Application命令,如图1-19所示。图1-19 运行菜单(3)查看程序执行的结果。程序执行的结果通过Console窗口显示,如图1-20所示。图1-20 执行结果

至此,便完成了在Eclipse集成开发环境中进行Java程序设计的基本步骤。本书中很多例子都可以通过这样的步骤来完成,以后不再赘述。1.6Java程序的基本结构

Java语言的程序流由若干条语句组成。在此之前所编写的程序都是一行一行的,由上而下,从左到右执行的。如果程序只能这样执行,那么程序能做的工作将会受到限制。有时可能需要控制程序执行的过程,例如,重复执行某一程序段或当一个条件出现时才执行某一程序段,而这些变化可以通过流程控制结构的相应语句来完成。

三种基本的程序结构分别为顺序结构、分支结构和循环结构。顺序结构是每条代码都按照先后顺序被执行一次;分支结构是仅有部分代码被执行一次;循环结构是部分代码在某种条件下被反复执行。Java中还有一种特殊的程序结构称为跳转,可以用break或continue来改变程序的执行,实现跳转。这些基本的程序结构语句,看起来很简单,但其各种组合,一起构成了千变万化的算法,所以,学习算法之外,还要掌握一种实现算法的程序语言基本语句。本书讲解的是Java,读者也可以把它们转化成其他程序设计语言。1.6.1 类是一个基本单元

编写程序,特别是阅读程序之前,首先需要了解程序的基本结构和组成单元,以方便剖析代码的组成。Java是面向对象的编程语言,不同于Pascal、C等面向过程的编程语言。面向对象编程用不同的方法分析和解决问题。熟悉C语言的读者在用Java编程时不能照搬传统的面向过程的求解问题的方法,而必须先将自己的思想转入一个面向对象的世界。但这种转变比较难,读者首先需要熟悉面向对象设计和编程的基本思想和基本概念。

面向对象编程(Object Oriented Programming,简称OOP)用与现实世界更一致、与人的思维模式更一致的方法来分析解决问题。面向对象编程的核心是“对象”。在现实世界中,人们无时无刻不与对象打交道。例如,磁盘、电视机、汽车、轮胎、人等,这一切都是对象。对象有两个基本特点:状态和行为。例如,汽车有质量、颜色和速度等状态,也有启动、转弯、加速等操作;人有独特的状态:名字、高矮、性别、健康等,而且还具有行走、休息和工作等行为。软件对象根据现实世界的对象建立,既可以表示现实世界中的事物,也可以表示事件。

在面向对象编程中,有很多对象共享某些属性和方法。可以利用同一类的对象共享一些属性和方法的特点,创造一个创建对象的母体。这种软件母体称为类。也就是说,类是定义同一类对象的属性和方法的蓝图或原形,对象是类的一个实例。

Java提供了几千种类,有的用于图形界面设计,有的用于数据库操作,有的用于网络编程等。另外,应用开发人员为解决实际问题也可创建用户自定义类。

类是面向对象程序的基本要素。它包含两个部分:类说明和类的主体。

类的定义格式如下:

与C++不同,Java中即使是一个最简单的程序也必须写成类。而C++中,简单的程序中完全可以不出现类,写一个main函数就可以了。要注意Java和C++在这一点上的区别。

说明: 类的说明部分是用户可见部分。在这个部分对类的一些性质进行声明,包括类的修饰符、类名等。(1)修饰符:是影响类生存空间和可访问性的关键字。常用的一种修饰符是public。它表示允许其他任何类访问。修饰符缺省时,这个类称为友好类。(2)类名:紧跟在关键字class之后,类名的命名要符合Java标识符的命名规则,类的主体由两部分构成:变量定义和方法定义。变量用来描述属性,方法用来描述行为。类实体跟在类的声明之后,用一对花括号{}界定。1.6.2 main方法

在C++程序中,main方法的声明可以是int main()或void main(),相对比较灵活。而在Java中,main方法作为Java应用程序的入口,写法基本是固定的,例如:

public static void main(String args[])

唯一可以做修改的是main方法中传递的字符数组的名称,可以不用args的名称。还有,按照Java语言的约定,声明数组时方括号也可以紧跟类型。main方法还可以写成:

public static void main(String[] yourName)

实际上不管上面的哪种写法,可以看到:(1)main方法必须定义成public,即公有的;(2)main方法必须定义成static,即静态方法;(3)main方法的返回类型固定为void;(4)main方法接收一个字符串数组作为参数。

读者在刚开始学习Java时,可能觉得main方法的书写太烦琐,多写一些程序后,逐步就会习惯了。main方法的固定写法,必须要牢记。而当以后使用集成开发环境后,写main方法相对就比较简单。在NetBeans中,输入psvm后按展开模板键(默认是Tab键,可以设置为空格键或Enter键),就可以自动填充main方法。1.6.3 自定义方法

软件对象是变量和方法的集合。根据现实世界的对象建立,软件对象与客观世界的对象存在着一一对应的映射关系。面向对象语言用变量描述对象的状态,用方法描述对象的行为。

方法声明的基本格式如下:

方法声明的第一行是方法头。(1)方法名是一个标识符。参数列表用圆括号界定,参数之间用逗号分隔。每个参数由参数类型和参数名组成。参数类型可以是基本数据类型,也可以是类。(2)方法名前必须指明方法返回值的类型。返回值类型可以是基本类型或引用类型。若方法无返回值,则返回值类型是void。一个方法最多返回一个值。若方法需要返回计算结果,可用带表达式的return语句。若无返回值,可以不用return语句,或者使用不带表达式的return语句,即:

return;(3)参数表由0个或多个参数构成。每个参数包括参数类型和参数名。参数类型可以是基本类型,也可以是引用类型。(4)修饰符是可选项,public和private是常用的修饰符。在方法头后面是方法体,由花括号界定方法体,包括变量声明和语句。

方法体中声明的变量是局部变量,只有在该方法内才有效。如果局部变量与类的成员变量同名,则局部变量屏蔽类的成员变量。局部变量和成员变量的另一个区别是,成员变量有默认值,而局部变量却没有。1.6.4 System.out.println的使用

System是位于java.lang包下的一个常用类。java.lang包称为Java的核心包,在这个包下的类可以直接使用,无须使用import语句导入。System类提供了很多的常用方法,如currentTimeMillis方法可以得到时间信息,getProperties方法可以得到当前计算机系统的相关信息。System类中有一个静态的对象out,out是PrintStream的对象,提供了print和println这样的常用方法,用于在控制台上输出信息。具体要在控制台上输出信息时,使用“System.out.println(参数);”的语法形式即可。

此外,为了在控制台得到输出结果,也可以使用“System.out.print(参数);”的语法形式。这里使用的print方法与println方法的区别是:print在显示参数后,并不将光标移动到下一行的开头,而println()在显示参数后,自动将光标位置移到下一行(与文本编辑器里按Enter键类似)。此外Java也可以使用System.out.printf()完成数据的输出,该用法完全类似于C语言的printf函数。System.out.printf()的一般格式如下:

System.out.printf(格式控制部分,表达式1,表达式2,…);

格式控制部分由普通字符和%d、%s、%f、%ld之类的格式控制符号组成,普通字符原样输出,格式符号用来输出表达式的值。例如:

System.out.printf("%d和%d的和为:",a,b,a+b);1.6.5 一个简单而完整的程序

编写Java程序,打印几个特定字符的ACSII码,包括数字0和9,大写字母A和Z,小写字母a和z。【程序1-2】【分析】 程序中dispAscii方法的声明为public void dispAscii(char ch),它的功能是接收一个字符类型的变量,将这个字符对应的ASCII码打印在控制台上。此方法不是静态(static)方法,因此,应该使用“对象名.方法名(参数)”的语法形式来调用。在调用println方法时,使用了加号将多个部分连接起来。

打印特定字符的ASCII码如图1-21所示。图1-21 打印特定字符的ASCII码

试读结束[说明:试读内容隐藏了图片]

下载完整电子书

若在网站上没有找合适的书籍,可联系网站客服获取,各类电子版图书资料皆有。

客服微信:xzh432

登入/注册
卧槽~你还有脸回来
没有账号? 忘记密码?