Java版数据结构与算法指南：实战与实例解析

需积分: 28 3 浏览量更新于2024-07-25 收藏 3.05MB PDF 举报

《Data Structures & Algorithms in Java》第二版是一本针对Java开发者的经典教材，由Robert Lafore撰写，于2001年由Sams出版社出版，书号为1571690956。这本617页的书籍深入浅出地介绍了如何在实际项目中通过Java编程实现数据结构和算法，是每个开发者不可或缺的案头参考。该书以清晰易懂的方式阐述复杂的数据结构和算法原理，强调了算法在软件程序中的核心作用——处理和操作数据结构。作者不仅提供了简洁的示例程序，还精心设计了一个可在Web浏览器上运行的小型工作坊，通过图形化的方式展示数据结构的外观和运作机制，直观地帮助读者理解。第二版的重要改进包括：更新的程序代码，提升了性能并明确了算法实现；所有示例程序与最新Java JDK版本兼容；并在每一章末尾添加了问题和练习，增强了学习的互动性和实用性。这本书旨在从基础入门，即使读者对Java或C++等语言已有基本了解，也能轻松跟上步伐。全书分为两个部分，共包含八章内容： - Part I： - Chapter 1：概述，引导读者快速了解数据结构和算法的整体概念。 - Chapter 2：数组，介绍数据结构中最基础的线性存储方式及其操作。 - Chapter 3：简单排序，探索排序算法的基础，如冒泡排序、选择排序等。 - Part II： - Chapter 4：栈和队列，这两个数据结构在程序设计中有广泛应用，涉及入栈、出栈、入队和出队等操作。 - Chapter 5：链表，更深入探讨链接型数据结构，包括单链表、双链表和循环链表等。 - Chapter 6：递归，讲解递归算法的概念以及如何在Java中实现。这本书的特点在于作者的写作风格轻松亲切，如同与读者共进午餐时分享技术心得，辅以引人入胜的图形解释。无论是初学者还是经验丰富的程序员，都能在《Data Structures & Algorithms in Java》中找到提升技能和解决实际问题所需的知识。

- 16 -

Here's the amazing breakthrough that is the key to OOP: An object contains both

functions and variables. A thermostat object, for example, would contain not only

furnace_on() and furnace_off() functions, but also currentTemp and

desiredTemp. Incidentally, before going further we should note that in Java, functions

are called methods and variables are called fields.

This new entity, the object, solves several problems simultaneously. Not only does a

programming object correspond more accurately to objects in the real world, it also

solves the problem engendered by global data in the procedural model. The

furnace_on() and furnace_off() methods can access currentTemp and

desiredTemp. These variables are hidden from methods that are not part of

thermostat, however, so they are less likely to be accidentally changed by a rogue

method.

Classes

You might think that the idea of an object would be enough for one programming

revolution, but there's more. Early on, it was realized that you might want to make several

objects of the same type. Maybe you're writing a furnace control program for an entire

apartment house, for example, and you need several dozen thermostat objects in your

program. It seems a shame to go to the trouble of specifying each one separately. Thus,

the idea of classes was born.

A class is a specification—a blueprint—for one or more objects. Here's how a

thermostat class, for example, might look in Java:

class thermostat

{

private float currentTemp();

private float desiredTemp();

public void furnace_on()

{

// method body goes here

}

public void furnace_off()

{

// method body goes here

}

} // end class thermostat

The Java keyword class introduces the class specification, followed by the name you

want to give the class; here it's thermostat. Enclosed in curly brackets are the fields

and methods (variables and functions) that make up the class. We've left out the body of

the methods; normally there would be many lines of program code for each one.

C programmers will recognize this syntax as similar to a structure, while C++

programmers will notice that it's very much like a class in C++, except that there's no

semicolon at the end. (Why did we need the semicolon in C++ anyway?)

Creating Objects

Specifying a class doesn't create any objects of that class. (In the same way specifying a

structure in C doesn't create any variables.) To actually create objects in Java you must

use the keyword new. At the same time an object is created, you need to store a

- 17 -

reference to it in a variable of suitable type; that is, the same type as the class.

What's a reference? We'll discuss references in more detail later. In the meantime, think

of it as a name for an object. (It's actually the object's address, but you don't need to

know that.)

Here's how we would create two references to type thermostat, create two new

thermostat objects, and store references to them in these variables:

thermostat therm1, therm2; // create two references

therm1 = new thermostat(); // create two objects and

therm2 = new thermostat(); // store references to them

Incidentally, creating an object is also called instantiating it, and an object is often

referred to as an instance of a class.

Accessing Object Methods

Once you've specified a class and created some objects of that class, other parts of your

program need to interact with these objects. How do they do that?

Typically, other parts of the program interact with an object's methods (functions), not

with its data (fields). For example, to tell the therm2 object to turn on the furnace, we

would say

therm2.furnace_on();

The dot operator (.) associates an object with one of its methods (or occasionally with

one of its fields).

At this point we've covered (rather telegraphically) several of the most important features

of OOP. To summarize:

•

Objects contain both methods (functions) and fields (data).

•

A class is a specification for any number of objects.

•

To create an object, you use the keyword new in conjunction with the class name.

•

To invoke a method for a particular object you use the dot operator.

These concepts are deep and far-reaching. It's almost impossible to assimilate them the

first time you see them, so don't worry if you feel a bit confused. As you see more classes

and what they do, the mist should start to clear.

A Runnable Object-Oriented Program

Let's look at an object-oriented program that runs and generates actual output. It features

a class called BankAccount that models a checking account at a bank. The program

creates an account with an opening balance, displays the balance, makes a deposit and

a withdrawal, and then displays the new balance. Here's the listing for bank.java:

// bank.java

- 19 -

Here's the output from this program:

Before transactions, balance=100

After transactions, balance=154.35

There are two classes in bank.java. The first one, BankAccount, contains the fields

and methods for our bank account. We'll examine it in detail in a moment. The second

class, BankApp, plays a special role.

The BankApp Class

To execute the program from a DOS box, you type java BankApp following the C:

prompt:

C:java BankApp

This tells the java interpreter to look in the BankApp class for the method called

main(). Every Java application must have a main() method; execution of the program

starts at the beginning of main(), as you can see in the bank.java listing. (You don't

need to worry yet about the String[] args argument in main().)

The main() method creates an object of class BankAccount, initialized to a value of

100.00, which is the opening balance, with this statement:

BankAccount ba1 = new BankAccount(100.00); // create acct

The System.out.print() method displays the string used as its argument, Before

transactions,, and the account displays its balance with the following statement:

ba1.display();

The program then makes a deposit to, and a withdrawal from, the account:

ba1.deposit(74.35);

ba1.withdraw(20.00);

Finally, the program displays the new account balance and terminates.

The BankAccount Class

The only data field in the BankAccount class is the amount of money in the account,

called balance. There are three methods. The deposit() method adds an amount to

the balance, withdrawal() subtracts an amount, and display() displays the

balance.

Constructors

The BankAccount class also features a constructor. A constructor is a special method

that's called automatically whenever a new object is created. A constructor always has

exactly the same name as the class, so this one is called BankAccount(). This

constructor has one argument, which is used to set the opening balance when the

account is created.

- 20 -

A constructor allows a new object to be initialized in a convenient way. Without the

constructor in this program, you would have needed an additional call to deposit() to

put the opening balance in the account.

Public and Private

Notice the keywords public and private in the BankAccount class. These keywords

are access modifiers and determine what methods can access a method or field. The

balance field is preceded by private. A field or method that is private can only be

accessed by methods that are part of the same class. Thus, balance cannot be

accessed by statements in main(), because main() is not a method in BankAccount.

However, all the methods in BankAccount have the access modifier public, so they

can be accessed by methods in other classes. That's why statements in main() can call

deposit(), withdrawal(), and display().

Data fields in a class are typically made private and methods are made public. This

protects the data; it can't be accidentally modified by methods of other classes. Any

outside entity that needs to access data in a class must do so using a method of the

same class. Data is like a queen bee, kept hidden in the middle of the hive, fed and cared

for by worker-bee methods.

Inheritance and Polymorphism

We'll briefly mention two other key features of object-oriented programming: inheritance

and polymorphism.

Inheritance is the creation of one class, called the extended or derived class, from

another class called the base class. The extended class has all the features of the base

class, plus some additional features. For example, a secretary class might be derived

from a more general employee class, and include a field called typingSpeed that the

employee class lacked.

In Java, inheritance is also called subclassing. The base class may be called the

superclass, and the extended class may be called the subclass.

Inheritance makes it easy to add features to an existing class and is an important aid in

the design of programs with many related classes. Inheritance thus makes it easy to

reuse classes for a slightly different purpose, a key benefit of OOP.

Polymorphism involves treating objects of different classes in the same way. For

polymorphism to work, these different classes must be derived from the same base class.

In practice, polymorphism usually involves a method call that actually executes different

methods for objects of different classes.

For example, a call to display() for a secretary object would invoke a display

method in the secretary class, while the exact same call for a manager object would

invoke a different display method in the manager class. Polymorphism simplifies and

clarifies program design and coding.

For those not familiar with them, inheritance and polymorphism involve significant

additional complexity. To keep the focus on data structures and algorithms, we have

avoided these features in our example programs. Inheritance and polymorphism are

important and powerful aspects of OOP but are not necessary for the explanation of data

structures and algorithms.

Software Engineering

剩余525页未读，继续阅读

hengbuyhouse

粉丝: 0
资源: 5

Java版数据结构与算法指南：实战与实例解析

Problem Solving in Data Structures & Algorithms Using Java 2nd Edition

Data Structures & Algorithms in Java Second Edition amazon

Data Structures & Algorithms In Java.pdf

Data Structures & Algorithms in Java(中文版2nd)

Java数据结构和算法，第二版，Data Structures & Algorithms in JAVA

Problem Solving in Data Structures & Algorithms Using Java

Problem Solving in Data Structures & Algorithms Using Java, 2nd

Problem Solving in Data Structures & Algorithms Using Java, 2nd Edition

data structure & algorithms in java

Data Structures & Algorithms

最新资源