java data structures (2nd edition).mht

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

        return next;
    }
    public Object getData(){
        return data;
    }
    public String toString(){
        return ""+data;
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Go over the source, notice that =
it's nothing=20
more than just set and get functions (pretty simple). The two data =
members are=20
the <CODE>data</CODE> and <CODE>next</CODE>. The <CODE>data</CODE> =
member holds=20
the data of the node, and <CODE>next</CODE> holds the pointer to the =
next node.=20
Notice that <CODE>next</CODE> is of the same type as the class itself; =
it=20
effectively points to the object of same class!</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>String toString()</CODE> =
method is=20
the Java's standard way to print things. If an object wants to be =
printed in a=20
special way, it will define this method, with instructions on how to =
print this=20
object. In our case, we just want to print the <CODE>data</CODE>. Adding =

<CODE>data</CODE> to a bunch of quotation marks automatically converts =
it to=20
type <CODE>String</CODE> (hopefully, our data will also have a=20
<CODE>toString()</CODE> method defined on it). Without this method, we =
get the=20
actual binary representation of the data members of this class (not a =
pretty nor=20
meaningful printout).</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Node based data structures provide =
for=20
dynamic growing and shrinking, and are the key to some complex =
algorithms (as=20
you'll see later). Now that we know how to implement a Node, lets get to =

something cool...</P>
<HR SIZE=3D1>

<H2><A name=3DLinked_Lists><I>Linked Lists...</I></A></H2>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; A linked list is just a chain of =
nodes, with=20
each subsequent node being a child of the previous one. Many programs =
rely on=20
linked lists for their storage because these don't have any evident=20
restrictions. For example, the array list we did earlier could not grow =
or=20
shrink, but node based ones can! This means there is no limit (other =
than the=20
amount of memory) on the number of elements they can store.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; A linked list has just one node, =
that node,=20
has links to subsequent nodes. So, the entire list can be referenced =
from that=20
one node. That first node is usually referred to as the head of the =
list. The=20
last node in the chain of nodes usually has some special feature to let =
us know=20
that it's last. That feature, most of the time is a <CODE>null</CODE> =
pointer to=20
the next =
node.</P><PRE><CODE>[node0]-&gt;[node1]-&gt;[node2]-&gt;[node3]-&gt;[node=
4]-&gt;null</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The example above illustrates the =
node=20
organization inside the list. In it, <CODE>node0</CODE> is the head =
node, and=20
<CODE>node4</CODE> is the last node, because it's pointer points to=20
<CODE>null</CODE>. Well, now that you know how it's done, and what is =
meant by a=20
linked list, lets write one. (I mean, that's why we're here, to actually =
write=20
stuff!)</P><PRE><CODE>import pOneChildNode;

public class pLinkedList{
    protected pOneChildNode head;
    protected int number;

    public pLinkedList(){
        head =3D null;
        number =3D 0;
    }
    public boolean isEmpty(){
        return head =3D=3D null;
    }
    public int size(){
        return number;
    }
    public void insert(Object obj){
        head =3D new pOneChildNode(obj,head);
        number++;
    }
    public Object remove(){
        if(isEmpty())
            return null;
        pOneChildNode tmp =3D head;
        head =3D tmp.getNext();
        number--;
        return tmp.getData();
    }
    public void insertEnd(Object obj){
        if(isEmpty())
            insert(obj);
        else{
            pOneChildNode t =3D head;
            while(t.getNext() !=3D null)
                t=3Dt.getNext();
            pOneChildNode tmp =3D
                new pOneChildNode(obj,t.getNext());
            t.setNext(tmp);
            number++;
        }
    }
    public Object removeEnd(){
        if(isEmpty())
            return null;
        if(head.getNext() =3D=3D null)
            return remove();
        pOneChildNode t =3D head;
        while(t.getNext().getNext() !=3D null)
            t =3D t.getNext();
        Object obj =3D t.getNext().getData();
        t.setNext(t.getNext().getNext());
        number--;
        return obj;
    }
    public Object peek(int n){
        pOneChildNode t =3D head;
        for(int i =3D 0;i&lt;n &amp;&amp; t !=3D null;i++)
            t =3D t.getNext();
        return t.getData();
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Before we move on, lets go over =
the source.=20
There are two data members, one named <CODE>head</CODE>, and the other =
named=20
<CODE>number</CODE>. Head is the first node of the list, and =
<CODE>number</CODE>=20
is the total number of nodes in the list. Number is primarily used for =
the=20
<CODE>size()</CODE> method. The constructor, <CODE>pLinkedList()</CODE> =
is self=20
explanatory. The <CODE>size()</CODE> and <CODE>isEmpty()</CODE> methods =
are also=20
pretty easy.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Here comes the hard part, the =
insertion and=20
removal methods. Method <CODE>insert(Object)</CODE> creates a new=20
<CODE>pOneChildNode</CODE> object with <CODE>next</CODE> pointer =
pointing to the=20
current <CODE>head</CODE>, and <CODE>data</CODE> the data which is =
inserted. It=20
then sets the <CODE>head</CODE> to that new node. If you think about it, =
you'll=20
notice that the <CODE>head</CODE> is still saved, and the new node =
points to=20
it.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Method <CODE>Object =
remove()</CODE> works in=20
a very similar fashion, but instead of inserting, it is removing. It =
first=20
checks to see if the list is <CODE>isEmpty()</CODE> or not, if it is, it =
returns=20
a <CODE>null</CODE>. It then saves the current <CODE>head</CODE> node, =
and then=20
changes it to accommodate the removal (think about the logic), =
decrements the=20
<CODE>number</CODE>, and returns the <CODE>data</CODE> from the =
previously saved=20
node.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; In the method=20
<CODE>insertEnd(Object)</CODE>, we're actually inserting at the end of =
the list.=20
We first check to see if the list is <CODE>isEmpty()</CODE>, if it is, =
we do a=20
regular insertion (since it really doesn't matter which direction we're =
coming=20
from if the list is <CODE>empty</CODE>). We then setup a loop to search =
for the=20
end. The end is symbolized by the <CODE>next</CODE> pointer of the node =
being=20
<CODE>null</CODE>. When we get to the end, we create a new node, and =
place it at=20
the end location. Incrementing <CODE>number</CODE> before we return.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Method <CODE>Object =
removeEnd()</CODE> works=20
in a similar fashion as <CODE>insertend(Object)</CODE> method. It also =
goes=20
through the whole list to look for the end. At the beginning, we check =
if the=20
list is not <CODE>isEmpty()</CODE>, if it is, we return a =
<CODE>null</CODE>. We=20
then check to see if there is only one element in the list, if there is =
only=20
one, we remove it using regular <CODE>remove()</CODE>. We then setup a =
loop to=20
look for the node who's child is the last node. It is important to =
realize that=20
if we get to the last node, we won't be able to erase it; we need the =
last=20
node's parent node. When we find it, we get the <CODE>data</CODE>, setup =

necessary links, decrement <CODE>number</CODE>, and return the=20
<CODE>data</CODE>.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; The <CODE>Object peek(int)</CODE> =
method=20
simply goes through the list until it either reaches the element =
requested, or=20
the end of the list. If it reaches the end, it should return a=20
<CODE>null</CODE>, if not, it should return the correct location inside =
the=20
list.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; As I have said before, it is very =
important=20
to actually test. The ideas could be fine, and logical, but if it =
doesn't work,=20
it doesn't work. So, lets convert our <CODE>pArrayListTest</CODE> driver =
to=20
accommodate this class.</P><PRE><CODE>import java.io.*;
import pLinkedList;

class pLinkedListTest{
    public static void main(String[] args){
        pLinkedList l =3D new pLinkedList();
        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);
        }
        for(;i&lt;10;i++){
            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's=20
just a pretty simple conversion of the old test driver, so, I wont spend =
any=20
time discussing it. The output follows.</P><PRE><CODE>starting...
insert: 65
insert: 78
insert: 21
insert: 73
insert: 62
insertEnd: 82
insertEnd: 63
insertEnd: 6
insertEnd: 95
insertEnd: 57
peek 0: 62
peek 1: 73
peek 2: 21
peek 3: 78
peek 4: 65
peek 5: 82
peek 6: 63
peek 7: 6
peek 8: 95
peek 9: 57
remove: 62
remove: 73
remove: 21
remove: 78
remove: 65
removeEnd: 57
removeEnd: 95
removeEnd: 6
removeEnd: 63
removeEnd: 82
Done ;-)</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Look over the output, make sure =
you=20
understand why you get what you get. Linked lists are one of the most =
important=20
data structures you'll ever learn, and it really pays to know them well. =
Don't=20
forget that you can always experiment. One exercise I'd like to leave up =
to the=20
reader is to create a circular list. In a circular list, the last node =
is not=20
pointing to <CODE>null</CODE>, but to the first node (creating a =
circle).=20
Sometimes, lists are also implemented using two pointers; and there are =
many=20
other variations you should consider and try yourself. You can even make =
it=20
faster by having a "dummy" first node and/or "tail" node. This will =
eliminate=20
most special cases, making it faster on insertions and deletions.</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; I guess that's it for the lists, =
next, I'll=20
show you how to do simple and easy tricks to re-use code.</P>
<HR SIZE=3D1>

<H2><A name=3DReusing_Tricks><I>Reusing Tricks...</I></A></H2>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; We have already written quite a =
lot of=20
useful stuff, and there might come a time, when you're just too lazy to =
write=20
something new, and would like to reuse the old source. This section will =
show=20
you how you can convert some data structures previously devised, to =
implement a=20
stack and a queue, with almost no creativity (by simply reusing the old=20
source).</P>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; Before we start, lets review the =
function of=20
a stack. It has to be able to push and pop items of from one end. What =
structure=20
do we know that can do something similar? A list! Lets write a list=20
implementation of a stack.</P><PRE><CODE>import pLinkedList;

public class pEasyStack{
    protected pLinkedList l;

    public pEasyStack(){
        l =3D new pLinkedList();
    }
    public boolean isEmpty(){
        return l.isEmpty();
    }
    public void push(Object o){
        l.insert(o);
    }
    public Object pop(){
        return l.remove();
    }
}</CODE></PRE>
<P align=3Djustify>&nbsp;&nbsp;&nbsp; See how easily the above code =
simulates a=20
stack by using a list? It may not be the best implementation, and it's =
certainly=20
not the fastest, but when you need to get the project compiled and =
tested, you=20
don't want to spend several unnecessary minutes writing a full blown =
optimized=20
stack. Test for the stack follows:</P><PRE><C