Java数据结构与算法实战解析

需积分: 0 178 浏览量更新于2024-08-02 收藏 3.05MB PDF 举报

"这是一本关于数据结构和算法的书籍，由Robert Lafore撰写，书名为《Data Structures & Algorithms in Java》。作者通过简洁易懂的Java示例，深入浅出地介绍了如何以实用的方式处理数据。书中包含丰富的图表，旨在帮助读者理解数据结构和算法的核心概念，适合已经掌握一种编程语言如Java或C++的读者阅读。" 在《Data Structures & Algorithms in Java》中，作者首先从基础开始讲解，涵盖了数据结构和算法的基础知识。这本书分为两个主要部分： Part I： 1. Chapter 1 - Overview：这一章通常会提供一个整体的介绍，概述数据结构和算法的重要性，以及它们在解决实际问题中的角色。它可能还会简要提及不同种类的数据结构和算法，并为后续章节建立基础。 2. Chapter 2 - Arrays：数组是最基本的数据结构之一，它允许在固定位置存储和访问元素。这一章可能会讨论一维、二维数组，以及数组的遍历、查找和排序等操作。 3. Chapter 3 - Simple Sorting：排序是算法的一个重要应用，本章将介绍一些简单的排序算法，如冒泡排序、插入排序、选择排序等，这些算法可以帮助读者理解排序的基本思想。 Part II： 4. Chapter 4 - Stacks and Queues：栈和队列是两种常用的数据结构，用于管理数据的存取顺序。栈遵循“后进先出”（LIFO）原则，而队列遵循“先进先出”（FIFO）原则。这两个概念广泛应用于计算机科学的许多领域，如表达式求值、递归、任务调度等。 5. Chapter 5 - Linked Lists：链表允许动态地添加和删除元素，比数组更灵活。本章可能包括单链表、双链表以及循环链表的概念，同时讲解插入、删除和遍历操作。 6. Chapter 6 - Recursion：递归是算法设计的一种重要技巧，它涉及函数调用自身来解决问题。这一章可能会讲解递归的基本原理，如何定义递归函数，以及递归在树遍历、排序等问题中的应用。除此之外，这本书还可能涉及其他高级数据结构，如树、图、散列表、堆和图算法等，以及更复杂的排序和搜索算法。每个主题都会结合实际的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页未读，继续阅读

q123456789098

粉丝: 309
资源: 2197

Java数据结构与算法实战解析

python数据结构与算法分析pdf

数据结构与算法分析 c++王立柱pdf

python数据结构与算法分析(第2版)pdf

数据结构和算法分析c++第四版答案

数据结构与算法分析c++第四版答案

数据结构与算法分析 c++语言描述 课后答案

数据结构与算法分析java语言描述pdf

数据结构与算法分析c++版第四版答案

数据结构与算法分析c

数据结构与算法分析–c++描述(第2版,weiss著,含习题答案)

最新资源

数据结构与算法分析 c++语言描述课后答案