Java算法与数据结构基础

需积分: 0 17 浏览量更新于2024-07-26 收藏 2.33MB PDF 举报

"本书主要探讨各种重要且实用的算法，这些算法是为计算机实现而设计的，适合解决特定问题。算法与数据结构相辅相成，数据结构是组织数据的方法，使得它们能被算法高效处理。本章将介绍研究算法和数据结构所需的基本工具。首先，我们将引入基础编程模型，所有程序都是使用Java编程语言的小子集以及我们自己的输入/输出库和统计计算库来实现的。第1.1节对我们在本书中使用的语言构造、特性和库进行了概述。接下来，我们将重点讨论数据抽象，定义抽象数据类型（ADTs）以支持模块化编程。在第1.2节中，我们将介绍如何在Java中实现ADT，通过指定应用程序编程接口（API）然后进行使用。" 本资源是关于“Java算法第四版”的书籍摘要，旨在深入学习和理解适用于计算机实现的算法和数据结构。书中的内容不仅涵盖算法，还涉及与之密切相关的数据结构。作者强调了算法和数据结构的共生关系，指出良好的数据结构设计能够提升算法的效率。在编程模型方面，书中使用了Java语言的一个精简子集，并结合自定义的输入/输出库和统计计算库。第1.1节详细介绍了这些语言特性，这有助于读者建立一个基础的编程环境，以便在后续章节中进行算法和数据结构的实现。接着，数据抽象作为核心概念被提出。第1.2节探讨了数据抽象的概念，通过定义抽象数据类型（ADTs），可以实现模块化编程，提高代码的可读性和可维护性。在这里，读者将学习如何在Java中规范ADT的API，并实施这些接口，从而创建符合需求的数据结构。此外，书中还会介绍一些基本的数据结构，如袋子、队列和栈（第1.3节），这些都是算法实现中常见的数据组织形式。第1.4节分析了算法，这是理解和评估算法性能的关键部分。第1.5节通过并查集（Union-Find）的案例研究，让读者能够实际操作和理解一个具体算法的工作原理和应用。总体来说，这本书提供了算法和数据结构的全面学习，从基本的编程模型到高级的分析技巧，对于希望深入理解Java编程语言中的算法和数据结构的读者来说，是一本宝贵的资源。通过学习，读者不仅能掌握算法设计和实现，还能培养出分析和优化算法的能力。

Shortcut notations There are several ways to express a given computation; we

seek clear, elegant, and efﬁ cient code. Such code often takes advantage of the following

widely used shortcuts (that are found in many languages, not just Java).

Initializing declarations. We can combine a declaration with an assignment to ini-

tialize a variable at the same time that it is declared (created). For example, the code

int i = 1; creates an int variable named i and assigns it the initial value 1. A best

practice is to use this mechanism close to ﬁ rst use of the variable (to limit scope).

Implicit assignments. The following shortcuts are available when our purpose is to

modify a variable’s value relative to its current value:

■

Increment/decrement operators: i++ is the same as i = i + 1 and has the value

i in an expression. Similarly, i-- is the same as i = i - 1. The code ++i and

--i are the same except that the expression value is taken after the increment/

decrement, not before.

■

Other compound operations: Prepending a binary operator to the = in an as-

signment is equivalent to using the variable on the left as the ﬁ rst operand.

For example, the code

i/=2; is equivalent to the code i = i/2; Note that

i += 1; has the same effect as i = i+1; (and i++).

Single-statement blocks. If a block of statements in a conditional or a loop has only a

single statement, the curly braces may be omitted.

For notation. Many loops follow this scheme: initialize an index variable to some val-

ue and then use a

while loop to test a loop continuation condition involving the index

variable, where the last statement in the

while loop increments the index variable. You

can express such loops compactly with Java’s

for notation:

for (<initialize>; <boolean expression>; <increment>)

{

}

This code is, with only a few exceptions, equivalent to

<initialize>;

while (<boolean expression>)

{

<increment>;

}

We use for loops to support this initialize-and-increment programming idiom.

CHAPTER 1

■

Fundamentals

Arrays An array stores a sequence of values that are all of the same type. We want

not only to store values but also to access each individual value. The method that we

use to refer to individual values in an array is numbering and then indexing them. If

we have N values, we think of them as being numbered from 0 to N1. Then, we can

unambiguously specify one of them in Java code by using the notation

a[i] to refer to

the

ith value for any value of i from 0 to N-1. This Java construct is known as a one-

dimensional array.

Creating and initializing an array. Making an array in a Java program involves three

distinct steps:

■

Declare the array name and type.

■

Create the array.

■

Initialize the array values.

To declare the array, you need to specify a name and the type of data it will contain.

To create it, you need to specify its length (the number of values). For example, the

“long form” code shown at right makes

an array of

N numbers of type double, all

initialized to

0.0. The ﬁ rst statement is

the array declaration. It is just like a dec-

laration of a variable of the correspond-

ing primitive type except for the square

brackets following the type name, which

specify that we are declaring an array.

The keyword new in the second state-

ment is a Java directive to create the ar-

ray. The reason that we need to explicitly

create arrays at run time is that the Java

compiler cannot know how much space

to reserve for the array at compile time (as it can for primitive-type values). The

for

statement initializes the

N array values. This code sets all of the array entries to the value

0.0. When you begin to write code that uses an array, you must be sure that your code

declares, creates, and initializes it. Omitting one of these steps is a common program-

ming mistake.

Short form. For economy in code, we often take advantage of Java’s default array ini-

tialization convention and combine all three steps into a single statement, as in the

“short form” code in our example. The code to the left of the equal sign constitutes the

declaration; the code to the right constitutes the creation. The

for loop is unnecessary

in this case because the default initial value of variables of type

double in a Java array is

declaration

creation

double[] a;

a = new double[N];

for (int i = 0; i < N; i++)

a[i] = 0.0;

double[] a = new double[N];

initialization

Declaring, creating and initializing an array

short form

int[] a = { 1, 1, 2, 3, 5, 8 };

initializing declaration

long form

CHAPTER 1

■

Fundamentals

0.0, but it would be required if a nonzero value were desired. The default initial value

is zero for numeric types and

false for type boolean. The third option shown for our

example is to specify the initialization values at compile time, by listing literal values

between curly braces, separated by commas.

Using an array. Typical array-processing code is shown on page 21. After declaring

and creating an array, you can refer to any individual value anywhere you would use

a variable name in a program by enclosing an integer index in square brackets after

the array name. Once we create an array, its size is ﬁ xed. A program can refer to the

length of an array

a[] with the code a.length. The last element of an array a[] is

always

a[a.length-1]. Java does automatic bounds checking—if you have created an

array of size

N and use an index whose value is less than 0 or greater than N-1, your pro-

gram will terminate with an

ArrayOutOfBoundsException runtime exception.

Aliasing. Note carefully that an array name refers to the whole array—if we assign one

array name to another, then both refer to the same array, as illustrated in the following

code fragment.

int[] a = new int[N];

...

a[i] = 1234;

...

int[] b = a;

...

b[i] = 5678; // a[i] is now 5678.

This situation is known as aliasing and can lead to subtle bugs. If your intent is to make

a copy of an array, then you need to declare, create, and initialize a new array and then

copy all of the entries in the original array to the new array, as in the third example on

page 21.

Two-dimensional arrays. A two-dimensional array in Java is an array of one-dimen-

sional arrays. A two-dimensional array may be ragged (its arrays may all be of differing

lengths), but we most often work with (for appropriate parameters M and N) M-by-N

two-dimensional arrays that are arrays of M rows, each an array of length N (so it also

makes sense to refer to the array as having N columns). Extending Java array constructs

to handle two-dimensional arrays is straightforward. To refer to the entry in row

i and

column

j of a two-dimensional array a[][], we use the notation a[i][j]; to declare a

two-dimensional array, we add another pair of square brackets; and to create the array,

we specify the number of rows followed by the number of columns after the type name

(both within square brackets), as follows:

1.1

■

Basic Programming Model

剩余240页未读，继续阅读

binxinyuwuhen

粉丝: 0
资源: 6

Java算法与数据结构基础

数据结构与Java算法第四版

Java算法第四版中文PDF，无需积分，开放下载

java算法第四版，最新

Java算法第四版课后答案深度解析

Java算法第四版代码测试与编程练习

算法 第四版 Java描述 谢路云 译 中文版

算法 第四版 谢路云 译 java实现

算法 第四版-谢路云译 Java版

算法第四版 -java描述（译）

Java经典算法第四版：必修50算法详解

最新资源

算法第四版 Java描述谢路云译中文版

算法第四版谢路云译 java实现

算法第四版-谢路云译 Java版