java data structures (2nd edition).mht

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

decrement the <CODE>end</CODE> pointer, add the =
<CODE>array.length</CODE>, and=20
do a mod with <CODE>array.length</CODE>. This had the effect of moving =
the=20
<CODE>end</CODE> pointer backwards (as if we had inserted something at =
the=20
end).</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>Object remove()</CODE> =
method=20
works on a very similar principle. First, it checks to see if there are =
elements=20
to remove, if not, it simply returns a <CODE>null</CODE> (no=20
<CODE>Object</CODE>). It then decrements <CODE>number</CODE>. We're =
keeping=20
track of this <CODE>number</CODE> inside all insertion and removal =
methods, so=20
that it always contains the current <CODE>number</CODE> of elements. We =
then=20
create a temporary variable to hold the current position of the=20
<CODE>start</CODE> pointer. After that, we update the <CODE>start</CODE> =
pointer=20
by first decrementing it, adding <CODE>array.length</CODE> to it, and =
doing a=20
mod with <CODE>array.length</CODE>. This gives the appearance of =
removing an=20
element from the front of the list. We later return the position inside =
the=20
array, which we've saved earlier inside that temporary variable=20
<CODE>'i'</CODE>.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>Object =
removeEnd()</CODE> works=20
similar to the <CODE>insert()</CODE> method. It checks to see if there =
are=20
elements to remove by calling <CODE>isEmpty()</CODE> method, if there =
aren't, it=20
returns <CODE>null</CODE>. It then handles the <CODE>number</CODE> =
(number of=20
elements) business, and proceeds with updating the <CODE>end</CODE> =
pointer. It=20
first increments the <CODE>end</CODE> pointer, and then does a mod with=20
<CODE>array.length</CODE>, and returns the resulting position. =
Simple?</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; This next <CODE>Object peek(int =
n)</CODE>=20
method is the most tricky one. It accepts an integer, and we need to =
return the=20
number which this integer is pointing to. This would be no problem if we =
were=20
using an <CODE>array</CODE> that started at <CODE>0</CODE>, but we're =
using our=20
own implementation, and the list doesn't necessarily start at =
<CODE>array</CODE>=20
position <CODE>0</CODE>. We start this by checking if the parameter=20
<CODE>'n'</CODE> is not greater than the <CODE>number</CODE> of =
elements, if it=20
is, we return <CODE>null</CODE> (since we don't want to go past the =
bounds of=20
the <CODE>array</CODE>). What we do next is add <CODE>'n'</CODE> (the =
requesting=20
number) to an incremented <CODE>end</CODE> pointer, and do a mod=20
<CODE>array.length</CODE>. This way, it appears as if this function is=20
referencing the array from <CODE>0</CODE> (while the actual start is the =

incremented <CODE>end</CODE> pointer).</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; As I've said previously, the code =
you write=20
is useless, unless it's working, so, lets write a test driver to test =
our list=20
class. To write the test driver, I've converted that really cool Queue =
test=20
driver, and added some features to test out the specifics of lists. =
Well, here=20
it is:</P><PRE><CODE>import java.io.*;
import pArrayList;

class pArrayListTest{
    public static void main(String[] args){
        pArrayList l =3D new pArrayList(10);
        Integer j =3D null;
        int i;
        System.out.println("starting...");
        for(i=3D0;i&lt;5;i++){
            j =3D new Integer((int)(Math.random() * 100));
            l.insert(j);
            System.out.println("insert: " + j);
        }
        while(!l.isFull()){
            j =3D new Integer((int)(Math.random() * 100));
            l.insertEnd(j);
            System.out.println("insertEnd: " + j);
        }
        for(i=3D0;i&lt;l.size();i++)
            System.out.println("peek "+i+": "+l.peek(i));
        for(i=3D0;i&lt;5;i++)
            System.out.println("remove: " + ((Integer)l.remove()));
        while(!l.isEmpty())
            System.out.println("removeEnd: " + =
((Integer)l.removeEnd()));
        System.out.println("Done ;-)");
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The test driver is nothing =
special, it=20
inserts (in front) five random numbers, and the rest into the back (also =
five).=20
It then prints out the entire list by calling <CODE>peek()</CODE> inside =
a=20
<CODE>for</CODE> loop. It then continues with the removal (from front) =
of five=20
numbers, and later removing the rest (also five). At the end, the =
program prints=20
"Done" with a cute smiley face ;-)</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The output from this test driver =
is given=20
below. I suggest you examine it thoroughly, and make sure you understand =
what's=20
going on inside this data structure.</P><PRE><CODE>starting...
insert: 14
insert: 72
insert: 71
insert: 11
insert: 27
insertEnd: 28
insertEnd: 67
insertEnd: 36
insertEnd: 19
insertEnd: 45
peek 0: 45
peek 1: 19
peek 2: 36
peek 3: 67
peek 4: 28
peek 5: 14
peek 6: 72
peek 7: 71
peek 8: 11
peek 9: 27
remove: 27
remove: 11
remove: 71
remove: 72
remove: 14
removeEnd: 45
removeEnd: 19
removeEnd: 36
removeEnd: 67
removeEnd: 28
Done ;-)</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Well, if you really understand =
everything up=20
to this point, there is nothing new anybody can teach you about arrays =
(since=20
you know all the basics). There are however public tools available to =
simplify=20
your life. Some are good, some are bad, but one that definitely deserves =
to have=20
a look at is the <CODE>java.util.Vector</CODE> class; and that's what =
the next=20
section is about!</P>
<HR SIZE=3D1>

<H2><A name=3DThe_Vector><I>The Vector...</I></A></H2>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>java.util.Vector</CODE> =
class is=20
provided by the Java API, and is one of the most useful array based data =
storage=20
classes I've ever seen. The information provided here is as far as JDK =
1.2 goes,=20
future versions may have other implementations; still, the functionality =
should=20
remain the same. A vector, is a growing array; as more and more elements =
are=20
added onto it, the array grows. There is also a possibility of making =
the array=20
smaller.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; But wait a minute, all this time =
I've been=20
saying that arrays can't grow or shrink, and it seems Java API has done =
it. Not=20
quite. The <CODE>java.util.Vector</CODE> class doesn't exactly grow, or =
shrink.=20
When it needs to do these operations, it simply allocates a new array =
(of=20
appropriate size), and copies the contents of the old array into the new =
array.=20
Thus, giving the impression that the array has changed size.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; All these memory operations can =
get quite=20
expensive if a <CODE>Vector</CODE> is used in a wrong way. Since a=20
<CODE>Vector</CODE> has a similar architecture to the array stack we've =
designed=20
earlier, the best and fastest way to implement a <CODE>Vector</CODE> is =
to do=20
stack operations. Usually, in programs, we need a general data storage =
class,=20
and don't really care about the order in which things are stored or =
retrieved;=20
that's where <CODE>java.util.Vector</CODE> comes in very useful.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Using a <CODE>Vector</CODE> to =
simulate a=20
queue is very expensive, since every time you insert or remove, the =
entire array=20
has to be copied (not necessarily reallocated but still involves lots of =
useless=20
work).</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; <CODE>Vector</CODE> allows us to =
view it's=20
insides using an <CODE>Enumerator</CODE>; a class to go through objects. =
It is=20
very useful to first be able to look what you're looking for, and only =
later=20
decide whether you'd like to remove it or not. A sample program that =
uses=20
<CODE>java.util.Vector</CODE> for it's storage =
follows.</P><PRE><CODE>import java.io.*;
import java.util.*;

class pVectorTest{
    public static void main(String[] args){
        Vector v =3D new Vector(15);
        Integer j =3D null;
        int i;
        System.out.println("starting...");
        for(i=3D0;i&lt;10;i++){
            j =3D new Integer((int)(Math.random() * 100));
            v.addElement(j);
            System.out.println("addElement: " + j);
        }
        System.out.println("size: "+v.size());
        System.out.println("capacity: "+v.capacity());

        Enumeration enum =3D v.elements();
        while(enum.hasMoreElements())
            System.out.println("enum: "+(Integer)enum.nextElement());

        System.out.println("Done ;-)");
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The example above should be self =
evident (if=20
you paid attention when I showed test programs for the previous data=20
structures). The main key difference is that this one doesn't actually =
remove=20
objects at the end; we just leave them inside. Removal can be =
accomplished very=20
easily, and if you'll be doing anything cool with the class, you'll sure =
to look=20
up the API specs.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Printing is accomplished using an=20
<CODE>Enumerator</CODE>; which we use to march through every element =
printing as=20
we move along. We could also have done the same by doing a =
<CODE>for</CODE>=20
loop, going from <CODE>0</CODE> to <CODE>v.size()</CODE>, doing a=20
<CODE>v.elementAt(int)</CODE> every time through the loop. The output =
from the=20
above program follows:</P><PRE><CODE>starting...
addElement: 9
addElement: 5
addElement: 54
addElement: 49
addElement: 60
addElement: 81
addElement: 8
addElement: 91
addElement: 76
addElement: 81
size: 10
capacity: 15
enum: 9
enum: 5
enum: 54
enum: 49
enum: 60
enum: 81
enum: 8
enum: 91
enum: 76
enum: 81
Done ;-)</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; You should notice that when we =
print the=20
<CODE>size</CODE> and <CODE>capacity</CODE>, they're different. The=20
<CODE>size</CODE> is the current number of elements inside the=20
<CODE>Vector</CODE>, and the <CODE>capacity</CODE>, is the maximum =
possible=20
without reallocation.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; A trick you can try yourself when =
playing=20
with the <CODE>Vector</CODE> is to have <CODE>Vectors</CODE> of=20
<CODE>Vectors</CODE> (since <CODE>Vector</CODE> is also an =
<CODE>Object</CODE>,=20
there shouldn't be any problems of doing it). Constructs like that can =
lead to=20
some interesting data structures, and even more confusion. Just try =
inserting a=20
<CODE>Vector</CODE> into a <CODE>Vector</CODE> ;-)</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; I guess that covers the =
<CODE>Vector</CODE>=20
class. If you need to know more about it, you're welcome to read the API =
specs=20
for it. I also greatly encourage you to look at =
<CODE>java.util.Vector</CODE>=20
source, and see for yourself what's going on inside that incredibly =
simple=20
structure.</P>
<HR SIZE=3D1>

<H2><A name=3DNodes><I>Nodes...</I></A></H2>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The other type of data structures =
are what's=20
called Node based data structures. Instead of storing data in it's raw =
format,=20
Node based data structures store nodes, which in turn store the data. =
Think of=20
nodes as being elements, which may have one or more pointers to other =
nodes.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Yes, I did say the "pointer" word. =
Many=20
people think that there are no pointers in Java, but just because you =
don't see=20
them directly, doesn't mean they're not there. In fact, you can treat =
any object=20
as a pointer.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Thus, the Node structure should =
have a data=20
element, and a reference to another node (or nodes). Those other nodes =
which are=20
referenced to, are called child nodes. The node itself is called the =
parent node=20
(or sometimes a "father" node) in reference to it's children. (nice big =
happy=20
family)</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Well, the best way to visualize a =
node is to=20
create one, so, lets do it. The node we'll create will be a one child =
node (it=20
will have only one pointer), and we'll later use it in later sections to =
build=20
really cool data structures. The source for our one child node =
follows:</P><PRE><CODE>public class pOneChildNode{
    protected Object data;
    protected pOneChildNode next;

    public pOneChildNode(){
        next =3D null;
        data =3D null;
    }
    public pOneChildNode(Object d,pOneChildNode n){
        data =3D d;
        next =3D n;
    }
    public void setNext(pOneChildNode n){
        next =3D n;
    }
    public void setData(Object d){
        data =3D d;
    }
    public pOneChildNode getNext(){