Java中的数据结构与算法

5星 · 超过95%的资源需积分: 9 23 浏览量更新于2024-07-24 收藏 6.51MB PDF 举报

"Data Structures and Algorithms in Java by Peter Drake" 本书《Data Structures and Algorithms in Java》是Peter Drake博士撰写的一本关于数据结构和算法的专著，面向已经掌握基础Java或C语言控制结构，并具备预科数学水平的读者。 Drake博士在书中提供了对Java和面向对象编程的简洁而引人入胜的介绍，同时充分利用了Java 1.5（即Java 5）的新特性。全书共592页，包括丰富的独特示例、统一建模语言（UML）的运用以及详尽的索引。书中的内容分为多个部分，首先从面向对象编程（Object-Oriented Programming）开始，讲述了封装（Encapsulation）、继承（Inheritance）和多态（Polymorphism）等核心概念。这部分旨在帮助读者理解如何使用Java来实现面向对象的设计思想。接下来， Drake博士深入讨论了各种数据结构，如数组（Arrays）、链表（Linked Lists）、栈（Stacks）、队列（Queues）、树（Trees）和图（Graphs）。在讲解每种数据结构时，都会配合实际应用案例，帮助读者了解它们的工作原理和用途。此外，书中还涵盖了排序和搜索算法，如冒泡排序（Bubble Sort）、快速排序（Quick Sort）、二分查找（Binary Search）等，以及复杂度分析，使读者能够评估算法的效率。书中还详细介绍了高级主题，如散列表（Hash Tables）、堆（Heaps）、优先队列（Priority Queues）以及图的遍历算法，如深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）。对于动态规划（Dynamic Programming）和贪心算法（Greedy Algorithms）等解决问题的方法也有深入探讨，这些工具在解决复杂问题时非常有用。此外，书中利用UML进行可视化表示，使得复杂的类结构和关系更易于理解。Java 1.5的新特性，如枚举类型（Enums）、泛型（Generics）和自动装箱（Autoboxing）等也被融入到教学中，让读者能掌握最新的编程实践。总而言之，《Data Structures and Algorithms in Java》是一本全面的教材，不仅教授数据结构和算法的基本理论，还注重实践应用，旨在培养读者的编程思维和问题解决能力。无论是初学者还是经验丰富的开发者，都能从中受益匪浅，提升其在Java编程领域的专业技能。

In the design phase, we decide what the program is going to look like. This includes problem

specification, the task of stating precisely what a program is supposed to do. In a programming class,

the problem specification is often given as the assignment. In real life, problem specification

involves working with the end user (for example, the customer, employer, or scientific community)

to decide what the program should do.

The design phase also includes breaking the program down into components. What are the major

components of the program? What is each component supposed to do? How do the components

interact? It is a good idea to write a comment for each component at this point, so that we have a

very clear understanding of what the component does. Commenting first also avoids the danger that

we'll put off commenting until our program has become hopelessly complicated.

The implementation phase is the writing of code. This is where we move from a description of a

rogram to a (hopefully) working program. Many students erroneously believe that this is the only

hase in which actual programming is occurring, so the other two phases are unimportant. In fact,

the more time spent on the other two phases, the less is needed in implementation. If we rush to the

keyboard to start coding, we may end up having to throw away some of our work because it doesn't

fit in with the rest of the program or doesn't meet the problem specification.

[Page 8]

In the testing phase, we run our program and verify that it does what it is supposed to do. After a

long session of programming, it is tempting to believe that our program is correct if it compiles and

runs on one test case. We must be careful to test our program thoroughly. For example, when testing

a method to search for some item in an array, we should consider cases where the target is the first

element of the array, where it is somewhere in the middle, where it is the last element, and where it is

not present at all.

The French poet Paul Valéry wrote, "A poem is never finished, only abandoned." The same can be

said of computer programs. There is some point when the software is released, but there is often

maintenance to be performed: changes to make, new features to add, bugs to fix. This maintenance is

ust more iterations of the software development cycle. This is why the cycle has no point labeled

"end" or "finished." In a programming course, assignments are often completely abandoned after

they are handed in, but general-purpose components may need some maintenance if they are to be

reused in future assignments.

Some software engineers argue that there should be, in effect, only one iteration of the cycle: the

entire program should be designed in exquisite detail, then implemented, then tested. Proponents of

this top-down approach argue that, by making all design decisions up front, we avoid wasting time

implementing components that won't fit into the final program.

Other software engineers advocate many iterations: design some simple component, implement it,

test it, expand the design very slightly, and so on. Proponents of this bottom-up approach argue that

this allows us to start testing before we have accumulated a huge body of code. Furthermore, because

Part I: Object-Oriented Programmin

2014

file:///C:/Users/Son

ZS/A

Data/Local/Tem

/~hh4E2D.ht

we put off our design decisions, we avoid wasting time redesigning the program if we discover that,

for example, we misunderstood the problem specification.

In practice, most software development falls between these two extremes. In this chapter, we will

lean toward the bottom-up end of the spectrum. When we are first learning to program, we don't yet

have the experience to envision the structure of an entire program. We are also likely to make a lot o

coding errors, so we should test early and often.

Encapsulation allows us to break up the software development cycle (Figure 1-3).

Figure 1-3. The construction of each encapsulated component (shaded) involves one or more iterations of the

software development cycle. The initial design phase involves breaking the program into components, each of

which can be developed separately. These components are combined in the implementation phase.

(This item is displayed on page 9 in the print version)

Once we divide the program into encapsulated components, we can work on each one separately. In

a project with several programmers, multiple components can be developed at the same time. Even if

we are working alone, the ability to concentrate on a single component makes it much easier to

rapidly develop correct, efficient, general-purpose code. Once the components are "complete," we

integrate them in a high-level implementation phase and then test the entire system.

Exercises

1.1 What have you done in the past to make one of your programs more correct? More

efficient? More

enera

ose? More ra

idl

develo

ed?

Discuss the extent to which your college education has consisted of encapsulated

courses.

[Pa

e 9

]

Discuss whether a to

-down or a bottom-up approach to software development is

more likely to produce a correct program. Which is likely to produce a more efficient

rogram? More genera

-purpose? More rapidly developed? Which approach do you

refer?

1.4 Discuss whether assertions

(

Appendix

) should be considered part of design, part of

lementation, or

art of testin

Part I: Object-Oriented Programmin

2014

file:///C:/Users/Son

ZS/A

Data/Local/Tem

/~hh4E2D.ht

1.5 Where do comments fit into the development cycle? How do they affect correctness,

efficienc

eneralit

, and develo

ment s

eed?

[Page 9 (continued)

]

1.2. Classes and Objects

This section illustrates the software development cycle and introduces some concepts from object-

oriented programming. As an extended example, we develop a program to play the game of Beetle

(Figure 1-4).

Classes

In Appendix A, we use the word "class" as a rough synonym for "program." While each program

needs to have a main() method in some class, many classes are not programs. In object-oriented

rogramming, a class is predominantly a description of a set of similar objects, such as the class of

birds, the class of insurance claims, or the class of dice. A class is an encapsulated component of the

rogram.

Figure 1-4. Beetle, also known as Bug or Cootie, is a children's game of pure luck. Our

implementation handles only two players.

(This item is displayed on page 10 in the print version)

Beetle

Players: 2 or more

Object: To be the first player with a complete beetle. A complete beetle has a

body, a head, six legs, two eyes, two feelers, and a tail.

Setup: Each player starts with no parts on her beetle.

Play: On your turn, roll a die, and act on the result:

1. If your beetle already has a body, pass the die to the next player.

Otherwise, add a body and roll again.

2. If your beetle already has a head or has no body, pass the die to the

next player. Otherwise, add a head and roll again.

3. If your beetle already has six legs or has no body, pass the die to the

next player. Otherwise, add two legs and roll again.

4. If your beetle already has two eyes or has no head, pass the die to the

next player. Otherwise, add an eye and roll again.

5. If your beetle already has two feelers or has no head, pass the die to

the next player. Otherwise, add a feeler and roll again.

6. If your beetle already has a tail or has no body, pass the die to the

next player. Otherwise, add a tail and roll again.

Part I: Object-Oriented Programmin

2014

file:///C:/Users/Son

ZS/A

Data/Local/Tem

/~hh4E2D.ht

ure 1-8. The file Die.java.

Objects, Fields, and Methods

We now focus on the simplest class of objects, the Die class.

What exactly is an object? An object has two kinds of components:

z The fields of the object represent its current state. In a Die, there will be one field indicating

which face of the Die is on top. Field values vary from one instance to another. One Die might

have the 2 showing, another the 6.

[Page 12]

z The methods of the object are actions it can perform. In object-oriented programming, we

don't do things to objects. Instead, we ask objects to do things to themselves. We don't roll a

die, we ask it to roll itself. All instances of a given class have the same methods.

In order to make our development cycle for the Die class as short as possible, we start by thinking,

"It will have to keep track of which face is on top." We'll design other features, such as the method

for rolling, later. In a top-down approach to software development, on the other hand, we would

specify all of the methods before thinking about implementation details such as fields.

A first shot at implementing the Die class is shown in Figure 1-9.

Figure 1-9. A first shot at implementing the Die class. It compiles, but it doesn't run.

This class compiles, but it doesn't run. The problem is that there is no main() method. Before we fix

this, notice a couple of things about the field topFace.

First, the field is not declared static. This means that it can have a different value for each instance of

Die. A field like this is called an instance field or instance variable. Since this is the most common

kind of field, it is often simply called a field.

Second, the field is declared private

. Instance fields are normally declared private. This means that

they cannot be accessed by methods in other classes. When other classes do things with Die

instances, code in those classes can't access private fields directly. This is an example of information

hiding.

1 /** A six-sided die for use in games. */

2 public class Die {

3 }

1 /** A six-sided die for use in games. */

2 public class Die {

4 /** The face of this Die that is showing. */

5 private int topFace;

7 }

Part I: Object-Oriented Programmin

2014

file:///C:/Users/Son

ZS/A

Data/Local/Tem

/~hh4E2D.ht

剩余560页未读，继续阅读

Entraver

粉丝: 0
资源: 1

Java中的数据结构与算法

Java中的数据结构与算法解析

Java算法和数据结构详解：第四版

Java数据结构与算法实战

Data structures and Algorithms in Java

Data Structures And Algorithms in Java

Data Structures And Algorithms in Java 2005

Data Structures and Algorithms in Java 4th

Data Structures and Algorithms in Java Fourth Edition

data structures and algorithms in java 4th

Data Structures And Algorithms In Java.pdf

最新资源