java tree problem

javastudent · **Posted:** Mon Oct 27, 2008 9:41 am

Who can help me out?

Your task is to implement a hash table using a collision resolution technique
based on chaining. The hash table is to be implemented by defining a Java class
named hashtbl that encapsulates the data structures used in implementing the
hash retrieval mechanism, along with the functions that are called by a program
that uses the hash table for storage and retrieval.

The following member functions will be needed in your implementation of the
hash table:

int hash(String key)

Hash function that transforms a key into an integer.

hashtbl()

A constructor that initializes an empty hash table.

int insert(rectype rec)

Inserts a record into the hash table. The status return
value has the following meaning:
0 = item was inserted in table
1 = item is already present in the table
2 = no more space in table

int find(rectype rec)

Retrieves from the hash table the item having the specified key.
The status return value has the following meaning:
0 = item was found in table
1 = item is not in table

int remove(String key)

Removes record with the specified key from the hash table. The
status return value has the following meaning:
0 = item was deleted from table
1 = item was not in the table

In order to test your hash machinery, a data file named hash.dat has been
created that contains a "random" sequence of entries of the following form:

I JONES 25 125.7
F JONES
R JONES

The first character on each line of the data file indicates which operation to
perform (I=insert, F=find, and R=remove). The second entry on each line is the
key, and in the case of an insert operation, the additional data values
represent the age and weight of the person whose name is the key. For each line
in the data file, your program will echo out the line, make the appropriate
function call, and then write out the results of the call (show the return
status value, and for a find operation, show the data values that are
retrieved).

******************************************************************************
Shown below is a copy of a fully operational version of the hash program, with
some of the components stripped out. Your task is to fill in the missing
components. (Places where something is missing are marked with /*??*/ in the
program.)
******************************************************************************
// Prog08.java

Code:

/*
Time:     3 hours 25 minutes
Grade:    98
Status:   Fully operational with correct output
Comments:
*/

import java.io.*;
import java.text.*;

class rectype
    {
    /*
    This class defines the structure of the data to be stored in the hash table.
    */
    String name;
    int age;
    float weight;

    public rectype()
        {
        name = "";
        age = 0;
        weight = 0;
        }  // rectype
    }  // clase rectype

class hashtbl
    {
    /*
    This class provides the machinery necessary to implement a hash table
    lookup mechanism.
    */

    // constants
    final int MAXHASH = 50;
    final int MAXRECS = 25;
    final int NIL = -1;

    // types
    private class tblrow
        {
        rectype rec;
        int next;
        }

    // private data
    private int avail;
    private int[] htbl;
    private tblrow[] rectbl;

    // private functions
    private int getnode()
        {
        /*
        This routine retrieves from the pool of available storage a pointer to
        a new node to link onto a hash chain.  If no such node is available,
        the value NIL is returned.
        */
        int p;

        p = avail;
        if (p != NIL) avail = rectbl[avail].next;
        return(p);
        }  // getnode
    private void putnode(int p)
        {
        /*
        This routine returns a node back to the pool of available storage
        */
        rectbl[p].next = avail;
        avail = p;
        }  // putnode
    private int hash(String key)
        {
        /*
        This hash function transforms a record key into an integer.
        */
        int i,sum;

        sum = 0;
        for (i = 0; i < key.length(); i++) sum += key.charAt(i);
        sum += key.length();
        return (sum % MAXHASH);
        }  // hash

    // public functions
    public hashtbl()
        {
        /*
        Consructor to establish an empty instance of a hash table.
        */
        int i;

        htbl = new int[MAXHASH];
        rectbl = new tblrow[MAXRECS];
        for (i = 0; i < MAXHASH; i++) htbl[i] = NIL;
        avail = 0;
        for (i = 0; i < MAXRECS; i++)
            {
            rectbl[i] = new tblrow();
            rectbl[i].rec = new rectype();
            rectbl[i].next = i + 1;
            }
        rectbl[MAXRECS-1].next = NIL;
        }  // hashtbl
    public int insert(rectype rec)
        {
        /*
        Inserts a record with the specified key into the hash table.  The
        status return value has the following meaning:
             0 = record was inserted in table
             1 = record is already present in the table
             2 = no more space in table
        (Note: name field of rec contains key value)
        */
        int status;

        /*??*/

        return(status);
        }  // insert
    public int find(rectype rec)
        {
        /*
        Retrieves from the hash table the record having the specified key.
        The status return value has the following meaning:
             0 = record was found in table
             1 = record is not in table
        (Note: name field of rec contains key value)
        */
        int status;

        /*??*/

        return(status);
        }  // find
    public int remove(String key)
        {
        /*
        Removes record with the specified key from the hash table.  The
        status return value has the following meaning:
             0 = item was deleted from table
             1 = item was not in the table
        (Note: name field of rec contains key value)
        */
        int status;

        /*??*/

        return(status);
        }  // remove
    public void dumphash()
        {
        /*
        Prints out a snapshot of the hash table data values
        */
        int i;
        DecimalFormat fmt = new DecimalFormat("####0.0");

        System.out.println();
        System.out.println("Dump of hash table:");
        System.out.println("   avail: " + avail);
        for (i = 0; i < MAXHASH; i++)
            {
            System.out.print(pad(Integer.toString(i),4,'R') +
               pad(Integer.toString(htbl[i]),3,'R'));
            if (i < MAXRECS)
                {
                System.out.print
                    (
                    pad(Integer.toString(i),6,'R') + " " +
                    pad(rectbl[i].rec.name,15,'L') +
                    pad(Integer.toString(rectbl[i].rec.age),5,'R') +
                    pad(fmt.format(rectbl[i].rec.weight),7,'R') +
                    pad(Integer.toString(rectbl[i].next),4,'R')
                    );
                }
            System.out.println();
            }
        }  // dumphash
    public String pad(String instr, int width, char justify)
        /*
        This function will left or right justify the input string in an
        output string of length "width" by adding leading or trailing
        blanks to the string as necessary.
        */
        {
        StringBuffer outstr = new StringBuffer(instr);
        while (outstr.length() < width)
            {
            if (justify == 'L') outstr.append(' ');
            else outstr.insert(0,' ');
            }
        return(outstr.toString());
        }  // pad
    } // class hashtbl

class Prog08
    {
    public static void main(String[] args) throws IOException
        {
        /*
        This function reads a data file named hash.dat that contains a number
        of transactions to test the operation of the hash table machinery
        implemented by the hashtbl class.
        */
        int status;
        String line;
        String[] t;
        char option;
        String name;
        int age;
        float weight;
        hashtbl tbl = new hashtbl();
        rectype rec = new rectype();
        DecimalFormat fmt = new DecimalFormat("####0.0");

        // initialize
        BufferedReader br = new BufferedReader(new FileReader("hash.dat"));

        // process transactions
        while ((line = br.readLine()) != null)
            {
            System.out.println(line);
            t = line.split("\\s+");
            option = t[0].charAt(0);
            name = t[1];  age = 0;  weight = 0;
            if (option == 'I')
               {
               age = Integer.parseInt(t[2]);
               weight = Float.parseFloat(t[3]);
               }
            switch (option)
                {
                case 'I':
                    rec.name = new String(name);
                    rec.age = age;
                    rec.weight = weight;
                    status = tbl.insert(rec);
                    System.out.println("  status: " + status);
                    if (name.compareTo("KOOL") == 0)  tbl.dumphash();  /**/
                    break;
                case 'F':
                    rec.name = new String(name);
                    status = tbl.find(rec);
                    System.out.println("  status: " + status);
                    if (status == 0)
                        {
                        System.out.println("  name: " + rec.name +
                           "  age: " + rec.age +
                           "  weight: "  + fmt.format(rec.weight));
                        }
                    break;
                case 'R':
                    status = tbl.remove(name);
                    System.out.println("  status: " + status);
                    if (name.compareTo("BARKER") == 0)  tbl.dumphash();  /**/
                    break;
                }
            }

        // finalize
        br.close();
        }  // main
    }  // class Prog08

*****************************************************************************
hash.dat
*****************************************************************************
I JONES 25 125.7
I WILSON 29 116.4
I PARKER 37 193.2
I WILLIAMSON 42 149.0
I BARKER 36 250.6
I CARTER 35 178.3
I ZIMMERMAN 24 212.8
I LOOK 34 146.8
I CARTER 53 214.3
I KOOL 51 212.5
F JONES
F WILLIAMSON
F PARKER
F CARTER
F MERCER
R BARKER
I DENTON 45 164.7
F BARKER
R ABEL
I BARKER 36 250.6
R JONES
F BARKER
*****************************************************************************
Shown below is the output produced for the input file above. In addition,
use of the "dumphash" test routine is illustrated. In the program, the
dump routine is called on the lines marked with /**/ and the idea is to get
a snapshot of the contents of the data structures behind the scenes that are
implementing the hash machinery. The snapshots taken below occur just after
the initial insertion of a set of records, and then again just after the first
removal operation has been performed. For your own debugging purposes, you
can call the dump routine whenever you need to see what is going on in the
data structures. (Note: because the dump fills more than one output screen,
the best way to manage things is to exit to the DOS prompt, and use the
redirection operation to direct the program output into a file (perhaps named
prog8.out). Then view that file with your text editor.

Remember, to get file redirection, after compiling and linking the program,
type the following at the DOS prompt:

java Prog8 > prog8.out

(This assumes your source program is in a file named Prog8.java)
*****************************************************************************
I JONES 25 125.7
status: 0
I WILSON 29 116.4
status: 0
I PARKER 37 193.2
status: 0
I WILLIAMSON 42 149.0
status: 0
I BARKER 36 250.6
status: 0
I CARTER 35 178.3
status: 0
I ZIMMERMAN 24 212.8
status: 0
I LOOK 34 146.8
status: 0
I CARTER 53 214.3
status: 1
I KOOL 51 212.5
status: 0

Dump of hash table:
avail: 9
0 -1 0 JONES 25 125.7 -1
1 -1 1 WILSON 29 116.4 -1
2 -1 2 PARKER 37 193.2 -1
3 -1 3 WILLIAMSON 42 149.0 -1
4 -1 4 BARKER 36 250.6 -1
5 5 5 CARTER 35 178.3 -1
6 -1 6 ZIMMERMAN 24 212.8 -1
7 -1 7 LOOK 34 146.8 8
8 -1 8 KOOL 51 212.5 -1
9 2 9 0 0.0 10
10 -1 10 0 0.0 11
11 -1 11 0 0.0 12
12 -1 12 0 0.0 13
13 7 13 0 0.0 14
14 -1 14 0 0.0 15
15 -1 15 0 0.0 16
16 -1 16 0 0.0 17
17 -1 17 0 0.0 18
18 -1 18 0 0.0 19
19 -1 19 0 0.0 20
20 -1 20 0 0.0 21
21 -1 21 0 0.0 22
22 -1 22 0 0.0 23
23 -1 23 0 0.0 24
24 -1 24 0 0.0 -1
25 -1
26 -1
27 3
28 -1
29 -1
30 -1
31 -1
32 1
33 -1
34 -1
35 -1
36 -1
37 -1
38 0
39 -1
40 -1
41 -1
42 -1
43 -1
44 -1
45 4
46 -1
47 6
48 -1
49 -1
F JONES
status: 0
name: JONES age: 25 weight: 125.7
F WILLIAMSON
status: 0
name: WILLIAMSON age: 42 weight: 149.0
F PARKER
status: 0
name: PARKER age: 37 weight: 193.2
F CARTER
status: 0
name: CARTER age: 35 weight: 178.3
F MERCER
status: 1
R BARKER
status: 0

Dump of hash table:
avail: 4
0 -1 0 JONES 25 125.7 -1
1 -1 1 WILSON 29 116.4 -1
2 -1 2 PARKER 37 193.2 -1
3 -1 3 WILLIAMSON 42 149.0 -1
4 -1 4 0 0.0 9
5 5 5 CARTER 35 178.3 -1
6 -1 6 ZIMMERMAN 24 212.8 -1
7 -1 7 LOOK 34 146.8 8
8 -1 8 KOOL 51 212.5 -1
9 2 9 0 0.0 10
10 -1 10 0 0.0 11
11 -1 11 0 0.0 12
12 -1 12 0 0.0 13
13 7 13 0 0.0 14
14 -1 14 0 0.0 15
15 -1 15 0 0.0 16
16 -1 16 0 0.0 17
17 -1 17 0 0.0 18
18 -1 18 0 0.0 19
19 -1 19 0 0.0 20
20 -1 20 0 0.0 21
21 -1 21 0 0.0 22
22 -1 22 0 0.0 23
23 -1 23 0 0.0 24
24 -1 24 0 0.0 -1
25 -1
26 -1
27 3
28 -1
29 -1
30 -1
31 -1
32 1
33 -1
34 -1
35 -1
36 -1
37 -1
38 0
39 -1
40 -1
41 -1
42 -1
43 -1
44 -1
45 -1
46 -1
47 6
48 -1
49 -1
I DENTON 45 164.7
status: 0
F BARKER
status: 1
R ABEL
status: 1
I BARKER 36 250.6
status: 0
R JONES
status: 0
F BARKER
status: 0
name: BARKER age: 36 weight: 250.6
*****************************************************************************
THE END
*****************************************************************************

msi_333 · **Posted:** Mon Oct 27, 2008 11:18 am

Hey this is a homework ,, did u tried to make it ..

javastudent · **Posted:** Mon Oct 27, 2008 4:57 pm

Thank you so very much...I appreciate it!..Believe me I did work on it, u don't even want to see my notes!lol..But I think next time,with your permission, I'll send you my scratch code so u can help me with the debugging...

Thank once more ... God Bless You!!

PS: Do you have any tips for me to excel faster in java programming?

msi_333 · **Posted:** Mon Oct 27, 2008 5:34 pm

i suggest book like thinking in java ,just read it ,,, u have to do effort ,and after that believe me you be will great

javastudent · **Posted:** Mon Nov 10, 2008 10:42 am

Hello there... I oredered the book for 10 dollars from ebay. I plan on reading it religiousy (and jealously) during christmas break ..lol... Anyways, I have an other "brain killer" I've been working on ... You've done more than enough.. but please help

Your task is to write a program which reports the amount of time required by
various sorting algorithms to sort different numbers of data values. Then,
using the output of the program, draw a graph that represents the results.
You must at a minimum use one method whose performance is "on the order of N
squared", and one method that is better than that.

Code:

  1 **************************************************************************
  2 // Timertest.java
  3
  4 import java.io.*;
  5 import java.util.*;
  6 import java.text.*;
  7
  8 class Timer
  9     {
 10     private long starttick;
 11
 12     public void StartTimer()
 13         // This function starts the timer
 14         {
 15         starttick = System.currentTimeMillis();
 16         }  // StartTimer
 17     public double ElapsedSeconds()
 18         /*
 19         This function returns the number of seconds that have elapsed
 20         (to the nearest millisecond) since the StartTimer function was
 21         called.
 22         */
 23         {
 24         return((System.currentTimeMillis() - starttick) / 1000.0);
 25         }  // ElapsedSeconds
 26     }  // class Timer
 27 public class Timertest
 28     {
 29     public static void main(String[] args) throws IOException
 30         // This function tests the functionality of the Timer class
 31         {
 32         int inbyte;
 33         long mscount;
 34         double seconds1,seconds,seconds3;
 35         Timer t = new Timer();
 36         DecimalFormat fmt = new DecimalFormat("###0.000");
 37
 38         System.out.println(
 39             "Press one of the letters below, followed by Enter:");
 40         System.out.println("    r = run timer");
 41         System.out.println("    b = begin timer");
 42         System.out.println("    s = stop timer");
 43         System.out.println("    q = quit program");
 44         do
 45             {
 46             do
 47                 {
 48                 inbyte = System.in.read();
 49                 } while (inbyte != 'b' && inbyte != 'q' && inbyte != 'r');
 50             if (inbyte == 'r')
 51                 {
 52                 mscount = System.currentTimeMillis();
 53                 while (System.currentTimeMillis() - mscount < 50)
 54                     System.out.println(System.currentTimeMillis());
 55                 }
 56             else if (inbyte != 'q')
 57                 {
 58                 System.out.println("Timing...");
 59                 t.StartTimer();
 60                 do
 61                     {
 62                     inbyte = System.in.read();
 63                     } while (inbyte != 's' && inbyte != 'q');
 64                 seconds = t.ElapsedSeconds();
 65                 System.out.println("Elapsed seconds: " + fmt.format(seconds));
 66                 }
 67             } while (inbyte != 'q');
 68         System.out.println("End of program.");
 69         }  // main
 70     }  // class Timertest
 71 **************************************************************************
 72 // Randomtest.java
 73
 74 import java.util.*;
 75
 76 public class Randomtest
 77     {
 78     public static void fillArray(int[] a)
 79         /*
 80         This function will fill an array with the numbers from 1 to
 81         a.length and then will shuffle those numbers into a random
 82         sequence.
 83         */
 84         {
 85         int i,j,temp;
 86         Random randnum = new Random();
 87
 88         for (i = 0; i < a.length; i++) a[i] = i + 1;
 89         for (i = 0; i < a.length; i++)
 90             {
 91             j = randnum.nextInt(a.length);
 92             temp = a[j];  a[j] = a[i];  a[i] = temp;
 93             }
 94         }  // fillArray
 95     public static void main(String[] args)
 96         // This function tests the fillArray function
 97         {
 98         int i;
 99         int[] a = new int[10];
100
101         fillArray(a);
102         System.out.println("Random shuffle of numbers from 1 to " + a.length);
103         for (i = 0; i < a.length; i++)
104             {
105             System.out.println("    "+a[i]);
106             }
107         }  // main
108     }  // class Randomtest
109 **************************************************************************
110                           BUBBLE SORT EXAMPLE
111 **************************************************************************
112 The following illustrates how to translate pseudocode for the bubble sort
113 algorithm into Java code:
114 **************************************************************************
115
116 void bubblesort(int[] a, int n)
117    {
118    int i,j;
119    int temp;
120
121    for (i = 1; i < n; i++)
122       {
123       for (j = n-1; j >= i; j--);
124          {
125          if (a[j-1] > a[j])
126             {
127             temp = a[j-1];
128             a[j-1] = a[j];
129             a[j] = temp;
130             }
131          }
132       }
133    }  // bubblesort
134
135 public static void main(String[] args)
136    {
137    final int MAX = 10000;
138    int n;
139    int[] a = new int[MAX];
140    double seconds;
141    Timer t = new Timer();
142
143    ...
144    fillArray(a);
145    ...
146    t.StartTimer();
147    bubblesort(a,n);
148    seconds = t.ElapsedSeconds();
149    ...
150    }  // main
151 **************************************************************************

msi_333 · **Posted:** Mon Nov 10, 2008 12:15 pm

i looked at the code but i didn't run it yet . i think your problem is with drawing ?right .
do you know Java swings and how to use graphics library . !

here a good example for drawing a curve ..
finished-projects/curvexy-t641.html

java tree problem

Users browsing similar posts