java data structures (2nd edition).mht

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

    protected Object head[];
    protected int pointer;

    public pArrayStackObject(int capacity){
        head =3D new Object[capacity];
        pointer =3D -1;
    }
    public boolean isEmpty(){
        return pointer =3D=3D -1;
    }
    public void push(Object i){
        if(pointer+1 < head.length)
            head[++pointer] =3D i;
    }
    public Object pop(){
        if(isEmpty())
            return null;
        return head[pointer--];
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The above is very similar to the=20
<CODE>int</CODE> only version, the only things that changed are the=20
<CODE>int</CODE> to <CODE>Object</CODE>. This stack, allows the=20
<CODE>push()</CODE> and <CODE>pop()</CODE> of any <CODE>Object</CODE>. =
Lets=20
convert our old test driver to accommodate this new stack. The new test =
module=20
will be inserting <CODE>java.lang.Integer</CODE> objects (not =
<CODE>int</CODE>;=20
not primitive type).</P><PRE><CODE>import java.io.*;
import pArrayStackObject;

class pArrayStackObjectTest{
    public static void main(String[] args){
        pArrayStackObject s =3D new pArrayStackObject(10);
        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));
            s.push(j);
            System.out.println("push: " + j);
        }
        while(!s.isEmpty()){
            System.out.println("pop: " + ((Integer)s.pop()));
        }
        System.out.println("Done ;-)");
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; And for the sake of being =
complete, I'll=20
include the output. Notice that here, we're not inserting elements of=20
<CODE>int</CODE> type, we're inserting elements of=20
<CODE>java.lang.Integer</CODE> type. This means, that we can insert any=20
<CODE>Object</CODE>.</P><PRE><CODE>starting...
push: 45
push: 7
push: 33
push: 95
push: 28
push: 98
push: 87
push: 99
push: 66
push: 40
pop: 40
pop: 66
pop: 99
pop: 87
pop: 98
pop: 28
pop: 95
pop: 33
pop: 7
pop: 45
Done ;-)</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; I guess that covers stacks. The =
main idea=20
you should learn from this section is that a stack is a FILO data =
structure.=20
After this section, non of the data structures will be working with =
primitive=20
types, and everything will be done solely with objects. (now that you =
know how=20
it's done...)</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; And now, onto the array relative =
of Stack,=20
the Queue.</P>
<HR SIZE=3D1>

<H2><A name=3DArray_Queue><I>Array Queues...</I></A></H2>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; A queue is a FIFO (First In, First =
Out)=20
structure. Anything that's inserted first, will be the first to leave =
(kind of=20
like the real world queues.) This is totally the opposite of what a =
stack is.=20
Although that is true, the queue implementation is quite similar to the =
stack=20
one. It also involves pointers to specific places inside the array.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; With a queue, we need to maintain =
two=20
pointers, the <CODE>start</CODE> and the <CODE>end</CODE>. We'll =
determine when=20
the queue is empty if <CODE>start</CODE> and <CODE>end</CODE> point to =
the same=20
element. To determine if the queue is full (since it's an array), we'll =
have a=20
<CODE>boolean</CODE> variable named <CODE>full</CODE>. To insert, we'll =
add one=20
to the <CODE>start</CODE>, and mod (the <CODE>%</CODE> operator) with =
the size=20
of the array. To remove, we'll add one to the <CODE>end</CODE>, and mod =
(the=20
<CODE>%</CODE> operator) with the size of the array. Simple? Well, lets =
write=20
it.</P><PRE><CODE>public class pArrayQueue{
    protected Object[] array;
    protected int start,end;
    protected boolean full;

    public pArrayQueue(int maxsize){
        array =3D new Object[maxsize];
        start =3D end =3D 0;
        full =3D false;
    }

    public boolean isEmpty(){
        return ((start =3D=3D end) &amp;&amp; !full);
    }

    public void insert(Object o){
        if(!full)
            array[start =3D (++start % array.length)] =3D o;
        if(start =3D=3D end)
            full =3D true;
    }

    public Object remove(){
        if(full)
            full =3D false;
        else if(isEmpty())
            return null;
        return array[end =3D (++end % array.length)];
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Well, that's the queue class. In =
it, we have=20
four variables, the <CODE>array</CODE>, the <CODE>start</CODE> and=20
<CODE>end</CODE>, and a <CODE>boolean full</CODE>. The constructor=20
<CODE>pArrayQueue(int maxsize)</CODE> initializes the queue, and =
allocates an=20
<CODE>array</CODE> for data storage. The <CODE>isEmpty()</CODE> method =
is self=20
explanatory, it checks to see if <CODE>start</CODE> and <CODE>end</CODE> =
are=20
equal; this can only be in two situations: when the queue is empty, and =
when the=20
queue is full. It later checks the <CODE>full</CODE> variable and =
returns=20
whether this queue is empty or not.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>insert(Object)</CODE> =
method,=20
accepts an <CODE>Object</CODE> as a parameter, checks whether the queue =
is not=20
<CODE>full</CODE>, and inserts it. The insert works by adding one to=20
<CODE>start</CODE>, and doing a mod with <CODE>array.length</CODE> (the =
size of=20
the <CODE>array</CODE>), the resulting location is set to the incoming =
object.=20
We later check to see if this insertion caused the queue to become full, =
if yes,=20
we note this by setting the <CODE>full</CODE> variable to =
<CODE>true</CODE>.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>Object remove()</CODE> =
method,=20
doesn't accept any parameters, and returns an <CODE>Object</CODE>. It =
first=20
checks to see if the queue is <CODE>full</CODE>, if it is, it sets=20
<CODE>full</CODE> to <CODE>false</CODE> (since it will not be =
<CODE>full</CODE>=20
after this removal). If it's not <CODE>full</CODE>, it checks if the =
queue is=20
empty, by calling <CODE>isEmpty()</CODE>. If it is, the method returns a =

<CODE>null</CODE>, indicating that there's been an error. This is =
usually a=20
pretty bad bug inside a program, for it to try to remove something from =
an empty=20
queue, so, you might want to do something more drastic in such a =
situation (like=20
an exception throw). The method continues by removing the end object =
from the=20
queue. The removal is done in the same way insertion was done. By adding =
one to=20
the <CODE>end</CODE>, and later mod it with <CODE>array.length</CODE>=20
(<CODE>array</CODE> size), and that position is returned.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; There are other implementations of =
the same=20
thing, a little re-arrangement can make several <CODE>if()</CODE> =
statements=20
disappear. The reason it's like this is because it's pretty easy to =
think of it.=20
Upon insertion, you add one to <CODE>start</CODE> and mod, and upon =
removal, you=20
add one to <CODE>end</CODE> and mod... easy?</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Well, now that we know how it =
works, lets=20
actually test it! I've modified that pretty cool test driver from the =
stack=20
example, and got it ready for this queue, so, here it =
comes:</P><PRE><CODE>import java.io.*;
import pArrayQueue;

class pArrayQueueTest{
    public static void main(String[] args){
        pArrayQueue q =3D new pArrayQueue(10);
        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));
            q.insert(j);
            System.out.println("insert: " + j);
        }
        while(!q.isEmpty()){
            System.out.println("remove: " + ((Integer)q.remove()));
        }
        System.out.println("Done ;-)");
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; As you can see, it inserts ten =
random=20
<CODE>java.lang.Integer Objects</CODE> onto the queue, and later prints =
them=20
out. The output from the program follows:</P><PRE><CODE>starting...
insert: 3
insert: 70
insert: 5
insert: 17
insert: 26
insert: 79
insert: 12
insert: 44
insert: 25
insert: 27
remove: 3
remove: 70
remove: 5
remove: 17
remove: 26
remove: 79
remove: 12
remove: 44
remove: 25
remove: 27
Done ;-)</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; I suggest you compare this output =
to the one=20
from stack. It's almost completely different. I guess that's it for this =
array=20
implementation of this FIFO data structure. And now, onto something more =

complex...</P>
<HR SIZE=3D1>

<H2><A name=3DArray_List><I>Array Lists...</I></A></H2>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The next step up in complexity is =
a list.=20
Most people prefer to implement a list as a linked list (and I'll show =
how to do=20
that later), but what most people miss, is that lists can also be =
implemented=20
using arrays. A list has no particular structure; it just has to allow =
for the=20
insertion and removal of objects from both ends, and some way of looking =
at the=20
middle elements.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; A list is kind of a stack combined =
with a=20
queue; with additional feature of looking at the middle elements. =
Preferably, a=20
list should also contain the current number of elements. Well, lets not =
just=20
talk about a list, but write one!</P><PRE><CODE>public class pArrayList{
    protected Object[] array;
    protected int start,end,number;

    public pArrayList(int maxsize){
        array =3D new Object[maxsize];
        start =3D end =3D number =3D 0;
    }
    public boolean isEmpty(){
        return number =3D=3D 0;
    }
    public boolean isFull(){
        return number &gt;=3D array.length;
    }
    public int size(){
        return number;
    }
    public void insert(Object o){
        if(number &lt; array.length){
            array[start =3D (++start % array.length)] =3D o;
            number++;
        }
    }
    public void insertEnd(Object o){
        if(number &lt; array.length){
            array[end] =3D o;
            end =3D (--end + array.length) % array.length;
            number++;
        }
    }
    public Object remove(){
        if(isEmpty())
            return null;
        number--;
        int i =3D start;
        start =3D (--start + array.length) % array.length;
        return array[i];
    }
    public Object removeEnd(){
        if(isEmpty())
            return null;
        number--;
        return array[end =3D (++end % array.length)];
    }
    public Object peek(int n){
        if(n &gt;=3D number)
            return null;
        return array[(end + 1 + n) % array.length];
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The class contains four data =
elements:=20
<CODE>array</CODE>, <CODE>start</CODE>, <CODE>end</CODE>, and=20
<CODE>number</CODE>. The <CODE>number</CODE> is the number of elements =
inside=20
the array. The <CODE>start</CODE> is the starting pointer, and the=20
<CODE>end</CODE> is the ending pointer inside the <CODE>array</CODE> =
(kind of=20
like the queue design).</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The constructor, =
<CODE>pArrayList()</CODE>,=20
and methods <CODE>isEmpty()</CODE>, <CODE>isFull()</CODE>, and=20
<CODE>size()</CODE>, are pretty much self explanatory. The =
<CODE>insert()</CODE>=20
method works exactly the same way as an equivalent queue method. It just =

increments the <CODE>start</CODE> pointer, does a mod (the =
<CODE>%</CODE>=20
symbol), and inserts into the resulting position.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>insertEnd(Object)</CODE> =
method,=20
first checks that there is enough space inside the <CODE>array</CODE>. =
It then=20
inserts the element into the <CODE>end</CODE> location. The next trick =
is to=20