Instructions
Requirements and Specifications
Source Code
BS TREE
public class BSTree implements BSTreeInterface
{
private Node root;
public BSTree()
{
root = null;
}
//assumes the new node does not exist in the tree
public void insertBST(E obj)
{
Node newNode = new Node(obj);
if (root == null)
root = newNode;
else {
int comp = -999; //Java requires an initialization here
Node lead, lag;
lead = lag = root;
while (lead != null) {
lag = lead;
comp = newNode.info.compareTo(lag.info);
if (comp < 0)
lead = lag.left;
else
lead = lag.right;
}
//lead fell off tree
if (comp < 0)
lag.left = newNode;
else
lag.right = newNode;
}
}
public E find(E obj)
{
Node findNode = new Node(obj);
Node r = root;
int comp;
while (r != null && (comp = r.info.compareTo(findNode.info)) != 0) {
if (comp < 0)
r = r.right;
else
r = r.left;
}
if (r == null)
return null;
return r.info;
}
private void intrav(Node r, StringBuilder sb)
{
if (r != null) {
intrav(r.left, sb);
sb.append(r.info.toString() + "\n");
intrav(r.right, sb);
}
}
public String toString()
{
StringBuilder sb = new StringBuilder();
intrav(root, sb);
return sb.toString();
}
}
CIRCULAR LIST
public class CircularList
{
private Item list;
public CircularList()
{
list = null;
}
public Boolean isEmpty()
{
return list == null;
}
public void append(int x)
{
Item r = new Item(x);
if (isEmpty()) {
r.next = r;
}
else {
r.next = list.next;
list.next = r;
}
list = r;
}
//write a new method here that returns the info of the last item in the list
//Javadoc comment required
/**
* Method, returning integer, stored int last list item or -1, if list is empty
* @return last list item data of -1 if the list is empty
*/
public int getLast() {
return isEmpty() ? -1 : list.info;
}
public String toString()
{
StringBuilder s = new StringBuilder("");
if (!isEmpty()) {
Item r = list.next;
while (r != list) {
s.append(r.info + ", ");
r = r.next;
}
//append last item
s.append(r.info);
}
return s.toString();
}
}
HASH TABLE
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class HashTable {
public static final int MAX = 30;
private String hashTable[];
public HashTable() throws FileNotFoundException {
hashTable = new String[MAX];
//be certain array contains all nulls
for (int i = 0; i < MAX; ++i)
hashTable[i] = null;
//read file of common words
int collisions = 0;
Scanner commonWords = new Scanner(new File("Common_words.txt"));
while (commonWords.hasNext()) {
String word = commonWords.nextLine();
//put word into hash table, handling collisions
for (int i = hash(word); ; i = (i + 1) % MAX) {
if (hashTable[i] == null) {
hashTable[i] = word;
break;
}
collisions++;
}
}
System.out.println
("Number of collisions building the table: " + collisions);
}
public int hash(String word) {
char ch;
double total;
total = 0.0;
for (int i = 0; i < word.length(); ++i) {
ch = word.charAt(i);
total += (double) ch;
total *= Math.PI;
}
double decimal = total - (int) total;
int hash = (int) (MAX * decimal);
return hash;
}
public Boolean find(String word) {
//use hashing here for fast search, implement linear probing to handle collisions
for (int i = hash(word); ; i = (i + 1) % MAX) {
if (hashTable[i] == null)
break;
if (word.equals(hashTable[i]))
return true;
}
//this hard-coded return value is here to allow this method stub to compile
return false;
}
public String toString() {
//traverses the hash table to output each word, preceded by a word count
//this hard-coded return value is here to allow this method stub to compile
String result = "";
for (int i = 0; i < MAX; i++) {
result += ((i + 1) + " " + hashTable[i] + System.lineSeparator());
}
return result;
}
}