Java数据结构与算法分析入门

需积分: 0 48 浏览量更新于2024-07-29 收藏 2.97MB PDF 举报

"《Data.Structures.and.Algorithm.Analysis.in.Java》是由Robert Lafore编著的一本关于数据结构和算法分析的书籍，适用于Java编程语言的学习者。这本书以易懂的语言和丰富的图表介绍如何使用Java处理和操作数据，旨在解决实际问题。书中不仅涵盖了基础的数据结构和算法，还涉及栈、队列、链表等进阶主题。" 本书详细介绍了在Java编程环境中如何运用数据结构和算法来解决复杂问题。首先，作者在引言部分引入了数据结构和算法的基本概念，让读者对即将学习的内容有一个全面的了解。第一部分包括概述和数组章节，帮助读者巩固基础知识，理解数组这一基本数据结构的使用和操作。在第二部分，书中深入探讨了排序算法，如简单的排序方法，这对于理解和优化程序性能至关重要。这部分内容是算法学习的基础，读者将学会如何有效地组织和排序数据。接着，书中进入第三部分，介绍了栈和队列这两种重要的抽象数据类型。栈用于管理后进先出（LIFO）的数据结构，而队列则遵循先进先出（FIFO）原则，它们在很多实际应用中都有广泛的应用，如函数调用、任务调度等。第四部分讲解了链表，这是一种更灵活的数据结构，允许动态地添加和删除元素。通过链表，读者可以更深入地理解动态内存管理和数据结构的内部工作原理。此外，书中的内容可能还包括递归等高级算法主题，递归是解决问题的强大工具，常用于树形结构的遍历、分治策略等。每个章节都配有相应的Java代码示例，帮助读者在实践中学习和掌握这些概念。《Data.Structures.and.Algorithm.Analysis.in.Java》是一本适合初学者和有一定编程基础的读者提升数据结构和算法能力的优秀教程，通过学习，读者不仅可以提高编程技能，还能培养解决问题的逻辑思维。书中的实例和生动的解释使得枯燥的理论变得易于理解，有助于读者快速上手并深入理解数据结构和算法在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页未读，继续阅读

tourney

粉丝: 1
资源: 1

Java数据结构与算法分析入门

SpringBoot入门与Data Structures and Algorithm Analysis解析

"数据结构与算法分析（Java语言描述）习题答案第三版

Clifford Shaffer's Data Structures and Algorithm Analysis in C++

Addison.Wesley.Data.Structures.and.Algorithm.Analysis.in.Java.3rd.Edition.2011

Data.Structures.and.Algorithm.Analysis.in.C

Data.Structures.And.Algorithm.Analysis.In.C.1992.

\Data.Structures.and.Algorithm.Analysis.in.C.rar

数据结构和算法分析 Data.Structures.and.Algorithm.Analysis.in.C

Problem.Solving.in.Data.Structures.and.Algorithms.Using.Cplusplus.epub

Data.Structures.and.Algorithms.USING.C

最新资源