The first file is an array based list. We have looked at node based implementations of...
The first file is an array based list. We have looked at node based implementations of both stacks and queues. An array based list utilizes an array of nodes to support common operations; note that the node class that we utilize has neither next nor previous references. Integer subscripts are maintained to keep track of both the front and rear.
_____________________________________________________________________________________________________
class Node {
private int key;
public Node() {
key = -1;
}
public Node(int k) {
key = k;
}
public int getKey() {
return key;
}
public void setKey(int k) {
key = k;
}
}
class ArrayBasedList {
private int SIZE = 5;
private Node[] abl = new Node[SIZE];
private int front, rear;
private int kCount;
public ArrayBasedList() {
for(int i = 0; i < SIZE; i++) {
abl[i] = new Node();
}
front = rear = 0;
kCount = 0;
}
public boolean insertFront(int k) {
if(kCount == 0) {
abl[front].setKey(k);
kCount++;
return true;
}
else if(kCount == SIZE) {
System.out.println("** > OVERFLOW < **");
return false;
}
else {
Node temp = abl[front];
while(temp.getKey() != -1) {
front--;
if(front == -1) front = SIZE-1;
temp = abl[front];
}
abl[front].setKey(k);
kCount++;
return true;
}
}//closes insertFront method
public boolean insertRear(int k) {
if(kCount == 0) {
abl[rear].setKey(k);
kCount++;
return true;
}
else if(kCount == SIZE) {
System.out.println("** > OVERFLOW < **");
return false;
}
else {
Node temp = abl[rear];
while(temp.getKey() != -1) {
rear++;
if(rear == SIZE) rear = 0;
temp = abl[rear];
}
abl[rear].setKey(k);
kCount++;
return true;
}
}//closes insertRear method
public boolean deleteRear() {
if(kCount == 0) {
System.out.println(">> Empty ABL <<");
return false;
}
Node temp = abl[rear];
temp.setKey(-1);
rear--;
if(rear == -1) rear = SIZE-1;
kCount--;
return true;
}//closes deleteRear method
public boolean deleteFront() {
if(kCount == 0) {
System.out.println(">> Empty ABL <<");
return false;
}
Node temp = abl[front];
temp.setKey(-1);
front++;
if(front == SIZE) front = 0;
kCount--;
return true;
}//closes deleteFront method
public void display() {
int i = front;
int count = 0;
Node temp = abl[i];
while(temp.getKey() != -1 && count < SIZE) {
System.out.print("*> " + temp.getKey() + " <*");
i++;
count++;
if(i == SIZE) i = 0;
temp = abl[i];
}
System.out.println("** END **");
}//closes display method
}//closes ArrayBasedList class
public class ArrayBasedListApp {
public static void main(String[] args) {
ArrayBasedList alpha = new ArrayBasedList();
alpha.display();
alpha.insertRear(9);
alpha.insertFront(11);
alpha.display();
alpha.insertFront(19);
alpha.display();
alpha.insertRear(81);
alpha.display();
alpha.insertFront(22);
alpha.display();
alpha.insertFront(86);
alpha.display();
alpha.deleteRear();
alpha.display();
alpha.deleteFront();
alpha.display();
}
}
_____________________________________________________________________________________________________
The second file is a hash table that supports several operations, including insert and find. We are reading about hash tables in chapter 11 of CLR&S. We are encountering yet another data structure, built to organize keys.
_____________________________________________________________________________________________________
class HT {
private final int SIZE = 11;
private int kCount = 0;
private int[] hT;
public HT() {
hT = new int[SIZE];
for(int i=0; i < SIZE;i++) {
hT[i] = -1;
}
}//end constructor method
private int hF(int k) {
return k % (SIZE);
}//end hF method
public boolean insert(int k) {
int temp = hF(k);
if(hT[temp] == -1) {
kCount++;
hT[temp] = k;
return true;
} else {
int counter = 0;
while(hT[temp] != -1 && counter != SIZE) {
temp++;
counter++;
if(temp == SIZE) temp = 0;
}
if(counter == SIZE) return false;
kCount++;
hT[temp] = k;
return true;
}
}//end insert method
public boolean find(int k) {
int temp = hF(k);
if(hT[temp] == -1) return false;
else if(hT[temp] == 0) {
int counter = 0;
while(hT[temp] != k && counter != SIZE) {
temp++;
if(temp == SIZE) temp = 0;
counter++;
}
if(hT[temp] == k) return true;
else return false;
}
else if(hT[temp] == k) {
return true;
}
else {
int counter = 0;
while(hT[temp] != k && counter != SIZE) {
temp++;
if(temp == SIZE) temp = 0;
counter++;
}
if(hT[temp] == k) return true;
else return false;
}
}//end find method
public void display() {
for(int i=0; i < SIZE; i++) {
System.out.print("*> " + hT[i] + " <*");
}
System.out.println("**END");
}//end display method
}
public class HTApp {
public static void main(String[] args) {
HT myHT = new HT();
myHT.display();
myHT.insert(11);
myHT.display();
myHT.insert(22);
myHT.insert(33);
myHT.display();
myHT.insert(34);
myHT.insert(47);
myHT.insert(121);
myHT.insert(98);
myHT.insert(69);
myHT.insert(89);
myHT.insert(141);
//myHT.insert(57);
System.out.println("test for overflow: " + !myHT.insert(287));
myHT.display();
boolean found = false;
int key = 11;
found = myHT.find(key);
if(found) {
System.out.println(">> key: " + key + " found <<");
}
else {
System.out.println(">> key: " + key + " not found <<");
}
}
}
while(hT[temp] != k && counter != SIZE) {
temp++;
if(temp == SIZE) temp = 0;
counter++;
}
if(hT[temp] == k) return true;
else return false;
}
}//end find method
public void display() {
for(int i=0; i < SIZE; i++) {
System.out.print("*> " + hT[i] + " <*");
}
System.out.println("**END");
}//end display method
}
public class HTApp {
public static void main(String[] args) {
HT myHT = new HT();
myHT.display();
myHT.insert(11);
myHT.display();
myHT.insert(22);
myHT.insert(33);
myHT.display();
myHT.insert(34);
myHT.insert(47);
myHT.insert(121);
myHT.insert(98);
myHT.insert(69);
myHT.insert(89);
myHT.insert(141);
//myHT.insert(57);
System.out.println("test for overflow: " + !myHT.insert(287));
myHT.display();
boolean found = false;
int key = 11;
found = myHT.find(key);
if(found) {
System.out.println(">> key: " + key + " found <<");
}
else {
System.out.println(">> key: " + key + " not found <<");
}
}
}
_____________________________________________________________________________________________________
In this lab we are making modifications to the provided code and performing testing. Complete the following steps:
- Download both files and remove the txt extensions.
- Open the first file, compile and run it.
- Get a feel for how things work.
- Take note of what's happening in the main method.
- Implement a find method, to support looking for a specific key.
- Make calls to the find method to confirm that it works.
- Thoroughly test the implementation, focusing more closely on the find method than the other methods.
- Open the second file, compile and run it.
- Get a feel for how it functions.
- Take note of what's happening in the main method.
- Implement a delete method, to delete a specific key in the hash table if it's there.
- Make calls to the delete method to confirm that it works.
- Put the implementation through its paces, paying particular attention to the delete method.
- Add the txt extensions back to both files and submit in Canvas for grading.
Homework Answers
Working code implemented in Java and appropriate comments provided for better understanding:
Here I am attaching code for these files:
- HTApp.java
- ArrayBasedListApp.java
Source code for ArrayBasedListApp.java:
class Node {
private int key;
public Node() {
key = -1;
}
public Node(int k) {
key = k;
}
public int getKey() {
return key;
}
public void setKey(int k) {
key = k;
}
}
class ArrayBasedList {
private int SIZE = 5;
private Node[] abl = new Node[SIZE];
private int front, rear;
private int kCount;
public ArrayBasedList() {
for (int i = 0; i < SIZE; i++)
{
abl[i] = new
Node();
}
front = rear = 0;
kCount = 0;
}
public boolean insertFront(int k) {
if (kCount == 0) {
abl[front].setKey(k);
kCount++;
return
true;
} else if (kCount == SIZE) {
System.out.println("** > OVERFLOW < **");
return
false;
} else {
Node temp =
abl[front];
while
(temp.getKey() != -1) {
front--;
if (front == -1)
front = SIZE - 1;
temp = abl[front];
}
abl[front].setKey(k);
kCount++;
return
true;
}
}// closes insertFront method
public boolean insertRear(int k) {
if (kCount == 0) {
abl[rear].setKey(k);
kCount++;
return
true;
} else if (kCount == SIZE) {
System.out.println("** > OVERFLOW < **");
return
false;
} else {
Node temp =
abl[rear];
while
(temp.getKey() != -1) {
rear++;
if (rear == SIZE)
rear = 0;
temp = abl[rear];
}
abl[rear].setKey(k);
kCount++;
return
true;
}
}// closes insertRear method
public boolean deleteRear() {
if (kCount == 0) {
System.out.println(">> Empty ABL <<");
return
false;
}
Node temp = abl[rear];
temp.setKey(-1);
rear--;
if (rear == -1)
rear = SIZE -
1;
kCount--;
return true;
}// closes deleteRear method
public boolean deleteFront() {
if (kCount == 0) {
System.out.println(">> Empty ABL <<");
return
false;
}
Node temp = abl[front];
temp.setKey(-1);
front++;
if (front == SIZE)
front = 0;
kCount--;
return true;
}// closes deleteFront method
public void display() {
int i = front;
int count = 0;
Node temp = abl[i];
while (temp.getKey() != -1
&& count < SIZE) {
System.out.print("*> " + temp.getKey() + " <*");
i++;
count++;
if (i ==
SIZE)
i = 0;
temp =
abl[i];
}
System.out.println("** END
**");
}// closes display method
}// closes ArrayBasedList class
public class ArrayBasedListApp {
public static void main(String[] args) {
ArrayBasedList alpha = new
ArrayBasedList();
alpha.display();
alpha.insertRear(9);
alpha.insertFront(11);
alpha.display();
alpha.insertFront(19);
alpha.display();
alpha.insertRear(81);
alpha.display();
alpha.insertFront(22);
alpha.display();
alpha.insertFront(86);
alpha.display();
alpha.deleteRear();
alpha.display();
alpha.deleteFront();
alpha.display();
}
}
Source code for HTApp.java:
class HT {
private final int SIZE = 11;
private int kCount = 0;
private int[] hT;
public HT() {
hT = new int[SIZE];
for (int i = 0; i < SIZE; i++)
{
hT[i] =
-1;
}
}// end constructor method
private int hF(int k) {
return k % (SIZE);
}// end hF method
public boolean insert(int k) {
int temp = hF(k);
if (hT[temp] == -1) {
kCount++;
hT[temp] =
k;
return
true;
} else {
int counter =
0;
while (hT[temp]
!= -1 && counter != SIZE) {
temp++;
counter++;
if (temp == SIZE)
temp = 0;
}
if (counter ==
SIZE)
return false;
kCount++;
hT[temp] =
k;
return
true;
}
}// end insert method
public boolean find(int k) {
int temp = hF(k);
if (hT[temp] == -1)
return
false;
else if (hT[temp] == 0) {
int counter =
0;
while (hT[temp]
!= k && counter != SIZE) {
temp++;
if (temp == SIZE)
temp = 0;
counter++;
}
if (hT[temp] ==
k)
return true;
else
return false;
} else if (hT[temp] == k) {
return
true;
} else {
int counter =
0;
while (hT[temp]
!= k && counter != SIZE) {
temp++;
if (temp == SIZE)
temp = 0;
counter++;
}
if (hT[temp] ==
k)
return true;
else
return false;
}
}// end find method
public void display() {
for (int i = 0; i < SIZE; i++)
{
System.out.print("*> " + hT[i] + " <*");
}
System.out.println("**END");
}// end display method
public void delete(int elem) { // "int elem" will be
the number/key to be deleted
for(int i = 0; i < SIZE; i++)
{
if(hT[i] ==
elem) {
for(int j = i; j < SIZE - 1; j++) {
hT[j] = hT[j+1];
}
break;
}
}
System.out.println("Deleted key " +
elem);
}
}// end class
public class HTApp {
public static void main(String[] args) {
HT myHT = new HT();
myHT.display();
myHT.insert(11);
myHT.display();
myHT.insert(22);
myHT.insert(33);
myHT.display();
myHT.insert(34);
myHT.insert(47);
myHT.insert(121);
myHT.insert(98);
myHT.insert(69);
myHT.insert(89);
myHT.insert(141);
// myHT.insert(57);
System.out.println("test for
overflow: " + !myHT.insert(287));
myHT.display();
boolean found = false;
int key = 11;
myHT.delete(11); //deletes key
n
found = myHT.find(key);
if (found) {
System.out.println(">> key: " + key + " found
<<");
} else {
System.out.println(">> key: " + key + " not found
<<");
}
}
}
Sample Output Screenshots:
Hope it helps, if you like the answer give it a thumbs up. Thank you.
Add Answer to:
The first file is an array based list. We have looked at node
based implementations of...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
Make the Sudoku algorithm for checking for duplicates to be Big -O of N, instead of...
Make the Sudoku algorithm for checking for duplicates to be Big -O of N, instead of N-squared. I.E. No nested for loops in rowIsLatin and colIsLatin. Only nested loop allowed in goodSubsquare. public class Sudoku { public String[][] makeSudoku(String s) { int SIZE = 9; int k = 0; String[][] x = new String[SIZE][SIZE]; for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++)...
could somone please help me to complete this ! public class MyLinkedList<AnyType> { private Node<AnyType> head,...
could somone please help me to complete this ! public class MyLinkedList<AnyType> { private Node<AnyType> head, tail; private int size; public MyLinkedList() { this.head = null; this.tail = null; this.size = 0; } //1.Insert a node at the end of the list public void insert(AnyType data) { Node<AnyType> newNode = new Node(); newNode.data = data; if (head == null) { head = newNode; tail = newNode; head.next = null; tail.next = null; } else { tail.next = newNode; tail =...
I am trying to make a linked list queue and I am trying to use the...
I am trying to make a linked list queue and I am trying to use the display method I made just to see if its working but when I run it nothing is displayed please help. Also the newPlane boolean was made just so I can randomly decide if the plane is going to join the queue or not. public class PlaneSimulation { public static void main(String[] args) { int landTime = 2; int takeoffTime = 3; int avgArrivalInterval =...
My Question is: I have to modify this program, even a small modification is fine. Can...
My Question is: I have to modify this program, even a small modification is fine. Can anyone give any suggestion and solution? Thanks in Advanced. import java.util.*; class arrayQueue { protected int Queue[]; protected int front, rear, size, len; public arrayQueue(int n) { size = n; len = 0; Queue = new int[size]; front = -1; rear = -1; } public boolean isEmpty() { return front == -1; } public boolean isFull() { return front == 0 && rear ==size...
Currently, I'm getting this as my output: "Exception in thread "main" java.lang.NullPointerException at InfixExpression.execute(InfixExpression.java:98) ...
Currently, I'm getting this as my output: "Exception in thread "main" java.lang.NullPointerException at InfixExpression.execute(InfixExpression.java:98) at InfixExpression.Evaluate(InfixExpression.java:65) at InfixExpression.setWholeExpr(InfixExpression.java:24) at InfixExpression.<init>(InfixExpression.java:17) at Main.testHW1(Main.java:17) at Main.main(Main.java:6)" I need to get this as my output: "Testing InfixExpression: When passing null, the String and double = Infix String: , result: 0.0 When passing a valid String, the String and double = Infix String: ( 234.5 * ( 5.6 + 7.0 ) ) / 100.2, result: 29.488023952095805 ..." I...
PROBLEM: string CBQueue::dequeue( ) This method should remove and return the item at the front of...
PROBLEM: string CBQueue::dequeue( ) This method should remove and return the item at the front of the queue- please add comments EXISTING CODE: #include // this allows you to declare and use strings #include using namespace std; struct qNode { string data; qNode* next; qNode* prev; }; class CBQueue { public: CBQueue(); int CBQueue::getSize( ); bool CBQueue::isEmpty( ); private: qNode* front; qNode* rear; int size; }; #include "CBQueue.h" CBQueue::CBQueue() { front = NULL; rear = NULL; size = 0; }...
iImplement a Singly Linked List detectLoop in Java, it would check whether the linked list contains...
iImplement a Singly Linked List detectLoop in Java, it would check whether the linked list contains a loop. Print true if yes, false if not. Test by using the following code: LL<Integer> L = new LL<>(); for (int i = 1000; i > 0; i-=3) sl.add(i); try { L.insert(122, L.getNode(70), L.getNode(21)); if (L.detectLoop()) System.out.println("True"); else System.out.println("False."); } catch(Exception e){ e.printStackTrace(); } class Linkedlist<E>{ private static class Node<E>{ private E element; private Node<E> next; public Node(E e, Node<E> n){ element =...
I am currently using eclipse to write in java. A snapshot of the output would be...
I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify
that the program is indeed working. Thanks in advance for both your
time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in...
When compiling the LinkedList and Iterator class, the following error is being produced: Note: LinkedList.java uses...
When compiling the LinkedList and Iterator class, the following error is being produced: Note: LinkedList.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. Any suggestions? public class LinkedList<T> { Node<T> itsFirstNode; Node<T> itsLastNode; private int size; public LinkedList() { itsFirstNode = null; itsLastNode = null; size = 0; } public Iterator<T> getIterator() { return new Iterator(this); } // THIS WILL NEED...
I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify
that the program is indeed working. Thanks in advance for both your
time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in...
Most questions answered within 3 hours.
-
Jamie is doing a survey at her school about whether the students
feel the cafeteria food...
asked 18 minutes ago -
How many liters of 0.669 M KOH will be needed to raise the pH of
0.339...
asked 2 hours ago -
A liquid of density 1270 kg/m 3 flows steadily through a pipe of
varying diameter and...
asked 2 hours ago -
Questions: What should the American executive do?
'A visiting American executive finds that a foreign subsidiary...
asked 2 hours ago -
Activity based costing was introduced as an alternative to
absorption costing.
1. Discuss using illustration the...
asked 2 hours ago -
1. You own shares of Crane DVD Company and are interested in
selling them. With so...
asked 2 hours ago -
How many grams of He are necessary to fill a balloon having a
volume of 4.5E3...
asked 2 hours ago -
The 2 patients, still in the hospital, were interviewed by a
MoH epidemiologist. The interviews revealed...
asked 2 hours ago -
An uncharged capacitor and a resistor are connected in series to
a source of emf. If...
asked 3 hours ago -
If assets are $540,000 and liabilities are $236,000 what is the
amount of owner’s equity?
asked 3 hours ago -
MATH 3421 Maple Assignment 1 Due February 13, 2019 Maple is a
Computer Algebra System that...
asked 3 hours ago -
CODING IN JAVA
Dates are printed in several common formats. Two of the more
common formats...
asked 3 hours ago