- Java These Are The Files In Package Bst Bstimpl Java Package Sa Edu Yuc Bst Import Java Util Stack Public Clas 1 (62.15 KiB) Viewed 46 times
(bst):
BSTImpl.java:
package sa.edu.yuc.bst;
import java.util.Stack;
public class BSTImpl> implements BSTInterface{
private Node root;
private int size;
//Do Not Change the code
public class Node {
T value;
Node leftChild;
Node rightChild;
public Node(T value) {
this.value = value;
}
}
//Do Not Change the code
public boolean isEmpty() {
return this.size == 0;
}
//Do Not Change the code
@Override
public void insert(T value) {
Node newNode = new Node(value);
if (isEmpty()) {
this.root = newNode;
this.size++;
} else {
Node currentNode = root;
while(currentNode != null) {
if (value.compareTo(currentNode.value) < 0) {
if (currentNode.leftChild == null) {
currentNode.leftChild = newNode;
this.size++;
}
currentNode = currentNode.leftChild;
} else if(value.compareTo(currentNode.value) > 0)
{
if (currentNode.rightChild == null) {
currentNode.rightChild = newNode;
this.size++;
}
currentNode = currentNode.rightChild;
}else {
break;
}
}
}
}
@Override
public T findMaxPercentage(){
// TODO ... Implement this method to return the Maximum
percentage of the student.
return null;
}
//Do No Change the code
@Override
public void printAll() {
if(isEmpty())
System.out.println("Tree is Empty");
else {
Stack> s = new Stack<>();
Node current = this.root;
while (!s.empty() || current != null){
if (current != null){
s.push(current);
current = current.leftChild;
}else {
current = s.pop();
System.out.print(current.value + "\n");
current = current.rightChild;
}
}
}
}
}
BSTInterface.java:
package sa.edu.yuc.bst;
public interface BSTInterface {
//Do Not Change the code
public abstract void insert(T item);
public abstract T findMaxPercentage();
public abstract void printAll();
}
BSTTest.java:
package sa.edu.yuc.bst;
public class BSTTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//Do Not Change the code
BSTInterface bst = new BSTImpl();
bst.insert(new Student(200, "abc", 56.89));
bst.insert(new Student(89, "xyz", 69.89));
bst.insert(new Student(100, "def", 65.78));
bst.insert(new Student(210, "jkl", 89.89));
bst.insert(new Student(150, "mno", 98.76));
bst.insert(new Student(30, "pqr", 76.78));
bst.insert(new Student(90, "yts", 78.90));
bst.insert(new Student(190, "cab", 50.25));
bst.insert(new Student(175, "bac", 67.89));
System.out.println("\n Printing the Tree");
bst.printAll();
System.out.println("\n Maximum student percentage details
are\n " + bst.findMaxPercentage());
}
}
Student.java:
package sa.edu.yuc.bst;
public class Student implements Comparable{
private int id;
private String name;
private double percentage;
//Do Not Change the code
public Student(int id, String name, double percentage)
{
super();
this.id = id;
this.name = name;
this.percentage = percentage;
}
@Override
public int compareTo(Student s) {
// TODO Auto-generated method stub
if(this.id > s.id)
return 1;
else if(this.id < s.id)
return -1;
else
return 0;
}
//Do Not change the code
@Override
public String toString() {
return " id=" + id + ", name=" + name + ", percentage=" +
percentage;
}
}
- These are the files in package (hash
folder):
Dictionary.java:
package sa.edu.yuc.hash;
public class Dictionary {
public static void main(String[] args) {
/* TODO ... Modify to test your code: use put/get
methods
* Hint: you can use these words,meanings
* "HOUSE", "home"
* "REMOVE", "delete"
* "INSERT", "put"
* "TEST", "quiz"
* "TEST", "final lab"
* "TEST", "final theory"
* "TEST", "mid lab"
*/
HashInterface ht = new HashTable(Word.class, 50);
//Add the code
//No menu is required
}
}
HashInterface.java:
package sa.edu.yuc.hash;
public interface HashInterface {
//Do Change the code
public abstract void put(String word, T value);
public abstract String get(String word);
}
HashTable.java:
package sa.edu.yuc.hash;
import java.lang.reflect.Array;
public class HashTable> implements HashInterface
{
private int capacity;
private String[] keys;
private T[] values;
//Do Not Change the code
public HashTable(Class cls){
this.capacity = 50;
this.keys = new String[this.capacity];
this.values = (T[]) Array.newInstance(cls,
this.capacity);
}
//Do Not Change the code
public HashTable(Class cls, int capacity){
this.capacity = capacity;
this.keys = new String[this.capacity];
this.values = (T[]) Array.newInstance(cls,
this.capacity);
}
//Do Not Change the code
public int charToInt(char ch){
return (int) ch - 64;
}
public int hashCode(String s){
/* TODO .... Modify this method to calculate the hash
by:
* charToInt(first)+charToInt(last)
*/
char third = s.charAt(2);
return charToInt(third);
}
@Override
public void put(String key, T value) {
/* TODO .... Modify this method to implement
* linear probing in-case of a collision.
*/
int index = hashCode(key);
values[index] = value;
keys[index] = key;
}
//Do Not Change the code
@Override
public String get(String key) {
// TODO Auto-generated method stub
int index = hashCode(key);
String temp = "";
while(index < this.capacity && this.values[index]
!= null){
if(this.keys[index].compareTo(key) == 0)
temp += this.values[index] + "\n";
index++;
}
return temp;
}
}
Word.java:
package sa.edu.yuc.hash;
public class Word implements Comparable{
private String word;
private String meaning;
//Do Change the code
public Word(String word, String meaning) {
this.word = word;
this.meaning = meaning;
}
//Do Change the code
@Override
public String toString() {
return this.meaning;
}
//Do Change the code
@Override
public int compareTo(Word o) {
// TODO Auto-generated method stub
if(this.word.compareTo(o.word) > 1)
return 1;
else if(this.word.compareTo(o.word) < 1)
return -1;
else
return 0;
}
}
2. For this question, you will use the package "yuc.edu.sa.hash" You are given the implementation of a simple Hash Table. You will need to modify the code to accomplish the following: a. Modify the hashCode(String key) method in HashTable.java to calculate the hashing as a summation of the integer values of the first and the last letters in a string Hint charToInt(first) + charToInt(last) [03 Marks] b. Modify the put(String key, T value) method in HashTable java to print a warning if there is a collision and resolve the collision with linear probing. It will print a warning message as shown in the output but the put operation will carry on [05 Marks] c. Modify the main function in Dictionary.java to test your code. [04 Marks] Output: Page 3 of 4 CS204 _Tuesday, 17 May, 2022 Data Structures Meaning of HOUSE home Meaning of REMOVE delete Meaning of INSERT put Collision occured at Index = 40 and linear porbing is used to resolve collision Collision occured at Index = 40 and linear porbing is used to resolve collision Collision occured at Index = 40 and linear porbing is used to resolve collision Collision occured at Index = 40 and linear porbing is used to resolve collision Collision occured at Index = 41 and linear porbing is used to resolve collision Collision occured at Index = 40 and linear porbing is used to resolve collision Collision occured at Index = 40 and linear porbing is used to resolve collision Collision occured at Index = 41 and linear porbing is used to resolve collision Collision occured at Index = 42 and linear porbing is used to resolve collision Meaning of TEST quiz final lab final theory mid lab