java data structures (2nd edition).mht

java数据结构与算法有很好的代码

every time an object is created using this class. The <CODE>set()</CODE> =
and=20
<CODE>get()</CODE> functions set and get the value of <CODE>'i'</CODE>=20
respectively. One useful terminology is that functions in objects are =
not called=20
functions, they're called methods. So, to refer to function =
<CODE>set()</CODE>,=20
you'd say "method <CODE>set()</CODE>." &nbsp; That's all there is to=20
objects!</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The way you declare a variable, or =
in this=20
case, an object of that class, is:</P><PRE><CODE>pSimpleObject myObject;
myObject =3D new pSimpleObject();</CODE></PRE>
<P align=3Djustify>or</P><PRE><CODE>pSimpleObject myObject =3D new =
pSimpleObject();</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The first example illustrates how =
you=20
declare an object named <CODE>myObject</CODE>, of class=20
<CODE>pSimpleObject</CODE>, and later instantiate it (a process of =
actual=20
creation, where it calls the object's constructor method). The second =
approach=20
illustrates that it all can be done in one line. The object does not get =
created=20
when you just declare it, it's only created when you do a =
<CODE>new</CODE> on=20
it.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; If you're familiar with C/C++, =
think of=20
objects as pointers. First, you declare it, and then you allocate a new =
object=20
to that pointer. The only limitation seems to be that you can't do math =
on these=20
pointers, other than that, they behave as plain and simple C/C++ =
pointers. (You=20
might want to think of objects as references however.)</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Using variables is really cool, =
and useful,=20
but sometimes we'd like to have more. Like the ability to work with =
hundreds or=20
maybe thousands of variables at the same time. And here's where our next =
section=20
starts, the Arrays!</P>
<HR SIZE=3D1>

<H2><A name=3DArrays><I>Arrays...</I></A></H2>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; One of the most basic data =
structures, is an=20
array. An array is just a number of items, of same type, stored in =
linear order,=20
one after another. Arrays have a set limit on their size, they can't =
grow beyond=20
that limit. Arrays usually tend to be easier to work with and generally =
more=20
efficient than other structural approaches to organizing data; way =
better than a=20
<EM>no formal structure</EM> approach.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; For example, lets say you wanted =
to have 100=20
numbers. You can always resort to having 100 different variables, but =
that would=20
be a pain. Instead, you can use the clean notation of an array to =
create, and=20
later manipulate those 100 numbers. For example, to create an array to =
hold 100=20
numbers you would do something like this:</P><PRE><CODE>int[] myArray;
myArray =3D new int[100];</CODE></PRE>
<P align=3Djustify>or</P><PRE><CODE>int[] myArray =3D new =
int[100];</CODE></PRE>
<P align=3Djustify>or</P><PRE><CODE>int myArray[] =3D new =
int[100];</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The three notations above do =
exactly the=20
same thing. The first declares an array, and then it creates an array by =
doing a=20
<CODE>new</CODE>. The second example shows that it can all be one in one =
line.=20
And the third example shows that Java holds the backwards compatibility =
with=20
C++, where the array declaration is: <CODE>int myArray[];</CODE> instead =
of=20
<CODE>int[] myArray;</CODE>. To us, these notations are exactly the =
same. I do=20
however prefer to use the Java one.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Working with arrays is also =
simple, think of=20
them as just a line of variables, we can address the 5th element =
(counting from=20
0, so, it's actually the 6th element) by simply doing:</P><PRE><CODE>int =
i =3D myArray[5];</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The code above will set integer=20
<CODE>'i'</CODE> to the value of the 5th (counting from 0) element of =
the array.=20
Similarly, we can set an array value. For example, to set the 50th =
element=20
(counting from 0), to the value of <CODE>'i'</CODE> we'd do something =
like:</P><PRE><CODE>myArray[50] =3D i;</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; As you can see, arrays are fairly =
simple.=20
The best and most convenient way to manipulate arrays is using loops. =
For=20
example, lets say we wanted to make an array from 1 to 100, to hold =
numbers from=20
1 to 100 respectively, and later add seven to every element inside that =
array.=20
This can be done very easily using two loops. (actually, it can be done =
in one=20
loop, but I am trying to separate the problem into =
two)</P><PRE><CODE>int i;
for(i=3D0;i&lt;100;i++)
    myArray[i] =3D i;
for(i=3D0;i&lt;100;i++)
    myArray[i] =3D myArray[i] + 7;</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; In Java, we don't need to remember =
the size=20
of the array as in C/C++. Here, we have the length variable in every =
array, and=20
we can check it's length whenever we need it. So to print out any array =
named:=20
<CODE>myArray</CODE>, we'd do something like:</P><PRE><CODE>for(int i =
=3D 0;i&lt;myArray.length;i++)
    System.out.println(myArray[i]);</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; This will work, given the objects =
inside the=20
myArray are printable, (have a corresponding <CODE>toString()</CODE> =
method), or=20
are of primitive type.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; One of the major limitations on =
arrays is=20
that they're fixed in size. They can't grow or shrink according to need. =
If you=20
have an array of 100 max elements, it will not be able to store 101 =
elements.=20
Similarly, if you have less elements, then the unused space is being =
wasted=20
(doing nothing).</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Java API provides data storage =
classes,=20
which implement an array for their storage. As an example, take the=20
<CODE>java.util.Vector</CODE> class (JDK 1.2), it can grow, shrink, and =
do some=20
quite useful things. The way it does it is by reallocating a new array =
every=20
time you want to do some of these operations, and later copying the old =
array=20
into the new array. It can be quite fast for small sizes, but when =
you're=20
talking about several megabyte arrays, and every time you'd like to add =
one more=20
number (or object) you might need to reallocate the entire array; that =
can get=20
quite slow. Later, we will look at other data structures where we won't =
be=20
overly concerned with the amount of the data and how often we need to=20
resize.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Even in simplest situations, =
arrays are=20
powerful storage constructs. Sometimes, however, we'd like to have more =
than=20
just a plain vanilla array.</P>
<HR SIZE=3D1>

<H2><A name=3DArray_Stack><I>Array Stack...</I></A></H2>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The next and more serious data =
structure=20
we'll examine is the Stack. A stack is a FILO (First In, Last Out), =
structure.=20
For now, we'll just deal with the array representation of the stack. =
Knowing=20
that we'll be using an array, we automatically think of the fact that =
our stack=20
has to have a maximum size.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; A stack has only one point where =
data enters=20
or leaves. We can't insert or remove elements into or from the middle of =
the=20
stack. As I've mentioned before, everything in Java is an object, (since =
it's an=20
Object Oriented language), so, lets write a stack =
object!</P><PRE><CODE>public class pArrayStackInt{
    protected int head[];
    protected int pointer;

    public pArrayStackInt(int capacity){
        head =3D new int[capacity];
        pointer =3D -1;
    }
    public boolean isEmpty(){
        return pointer =3D=3D -1;
    }
    public void push(int i){
        if(pointer+1 &lt; head.length)
            head[++pointer] =3D i;
    }
    public int pop(){
        if(isEmpty())
            return 0;
        return head[pointer--];
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; As you can see, that's the stack =
class. The=20
constructor named <CODE>pArrayStackInt()</CODE> accepts an integer. That =
integer=20
is to initialize the stack to that specific size. If you later try to=20
<CODE>push()</CODE> more integers onto the stack than this capacity, it =
won't=20
work. Nothing is complete without testing, so, lets write a test driver =
class to=20
test this stack.</P><PRE><CODE>import java.io.*;
import pArrayStackInt;

class pArrayStackIntTest{
    public static void main(String[] args){
        pArrayStackInt s =3D new pArrayStackInt(10);
        int i,j;
        System.out.println("starting...");
        for(i=3D0;i&lt;10;i++){
            j =3D (int)(Math.random() * 100);
            s.push(j);
            System.out.println("push: " + j);
        }
        while(!s.isEmpty()){
            System.out.println("pop: " + s.pop());
        }
        System.out.println("Done ;-)");
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The test driver does nothing =
special, it=20
inserts ten random numbers onto the stack, and then pops them off. =
Writing to=20
standard output exactly what it's doing. The output gotten from this =
program=20
is:</P><PRE><CODE>starting...
push: 33
push: 66
push: 10
push: 94
push: 67
push: 79
push: 48
push: 7
push: 79
push: 32
pop: 32
pop: 79
pop: 7
pop: 48
pop: 79
pop: 67
pop: 94
pop: 10
pop: 66
pop: 33
Done ;-)</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; As you can see, the first numbers =
to be=20
pushed on, are the last ones to be popped off. A perfect example of a =
FILO=20
structure. The output also assures us that the stack is working =
properly.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Now that you've had a chance to =
look at the=20
source, lets look at it more closely.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>pArrayStackInt</CODE> =
class is=20
using an array to store it's data. The data is <CODE>int</CODE> type =
(for=20
simplicity). There is a head data member, that's the actual array. =
Because we're=20
using an array, with limited size, we need to keep track of it's size, =
so that=20
we don't overflow it; we always look at <CODE>head.length</CODE> to =
check for=20
maximum size.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The second data member is=20
<CODE>pointer</CODE>. Pointer, in here, points to the top of the stack. =
It=20
always has the position which had the last insertion, or -1 if the stack =
is=20
empty.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The constructor:=20
<CODE>pArrayStackInt()</CODE>, accepts the maximum size parameter to set =
the=20
size of the stack. The rest of the functions is just routine =
initialization.=20
Notice that pointer is initialized to -1, this makes the next position =
to be=20
filled in an array, 0.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>isEmpty()</CODE> =
function is self=20
explanatory, it returns <CODE>true</CODE> if the stack is empty=20
(<CODE>pointer</CODE> is -1), and <CODE>false</CODE> otherwise. The =
return type=20
is <CODE>boolean</CODE>.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>push(int)</CODE> =
function is=20
fairly easy to understand too. First, it checks to see if the next =
insertion=20
will not overflow the array. If no danger from overflow, then it =
inserts. It=20
first increments the pointer and then inserts into the new location =
pointed to=20
by the updated <CODE>pointer</CODE>. It could easily be modified to =
actually=20
make the array grow, but then the whole point of "simplicity" of using =
an array=20
will be lost.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>int pop()</CODE> =
function is also=20
very simple. First, it checks to see if stack is not empty, if it is =
empty, it=20
will return 0. In general, this is a really bad error to pop of =
something from=20
an empty stack. You may want to do something more sensible than simply =
returning=20
a 0 (an exception throw would not be a bad choice). I did it this way =
for the=20
sake of simplicity. Then, it returns the value of the array element =
currently=20
pointed to by pointer, and it decrements the pointer. This way, it is =
ready for=20
the next <CODE>push</CODE> or <CODE>pop</CODE>.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; I guess that just about covers it. =
Stack is=20
very simple and is very basic. There are tons of useful algorithms which =
take=20
advantage of this FILO structure. Now, lets look at alternative=20
implementations...</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Given the above, a lot of the C++ =
people=20
would look at me strangely, and say: "All this trouble for a stack that =
can only=20
store integers?" Well, they're probably right for the example above. It =
is too=20
much trouble. The trick I'll illustrate next is what makes Java my =
favorite=20
Object Oriented language.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; In C, we have the =
<CODE>void*</CODE> type,=20
to make it possible to store "generic" data. In C++, we also have the=20
<CODE>void*</CODE> type, but there, we have very useful templates. =
Templates is=20
a C++ way to make generic objects, (objects that can be used with any =
type).=20
This makes quite a lot of sense for a data storage class; why should we =
care=20
what we're storing?</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The way Java implements these =
kinds of=20
generic classes is by the use of parent classes. In Java, every object =
is a=20
descendent of the <CODE>Object</CODE> class. So, we can just use the=20
<CODE>Object</CODE> class in all of our structures, and later cast it to =
an=20
appropriate type. Next, we'll write an example that uses this technique =
inside a=20
generic stack.</P><PRE><CODE>public class pArrayStackObject{