*Data Structures and Algorithms Using Java* Chapter 5: Hashed Data Structures *
ID: 3603938 • Letter: #
Question
*Data Structures and Algorithms Using Java* Chapter 5: Hashed Data Structures *
****************NO JOPTION PANE/NO POP-UP WINDOWS*NO DATABASES* -ONLY- JAVA ***************
The program should perform an UNLIMITED number of operations until the user enters a 6 to exit the program, Assume the identification numbers will be in the range 1000 to 50,000.
Code an application program that keeps track of student information at your college: their names, identification numbers (the key field), and grade point averages in a fully encapsulated, Linear Quotient (LQ Hash) (PLEASE SHOW ME THAT IT IS LINEAR QUOTIENT HASH) . When launched, the user will be asked to input the maximum size of the data set, the initial number of students, and the initial data set. Once this is complete, the user will be presented with the following menu:
Enter: 1 to insert a new student's information,
2 to fetch and output a student's information,
3 to delete a student's information,
4 to update a student's information,
5 to output all the student information, and
6 to exit the program
Explanation / Answer
Complete Program:
/*
* File: Listing.java
*/
public class Listing
{
private String name;
private int id;
private double gpa;
public Listing()
{
this.name = "";
this.id = 0;
this.gpa = 0.0;
}
public Listing(String name, int id, double gpa)
{
this.name = name;
this.id = id;
this.gpa = gpa;
}
public String getName()
{
return name;
}
public void setName(String name)
{
this.name = name;
}
public int getID()
{
return id;
}
public void setID(int id)
{
this.id = id;
}
public double getGPA()
{
return gpa;
}
public void setGPA(double gpa)
{
this.gpa = gpa;
}
public String toString()
{
return ("Name is " + name +
" ID is " + id +
" GPA is " + gpa + " ");
}
public int coompareTo(String targetKey)
{
return (name.compareTo(targetKey));
}
public Listing deepCopy()
{
Listing clone = new Listing(name, id, gpa);
return clone;
}
} // end of Listing class
/*
* File: LQHashed.java
*/
public class LQHashed
{
private final int DEFAULT_QUOTIENT = 9967;
private double loadFactor = 0.75;
private Listing[] table;
private Listing deletedListing;
private int maxLen;
private int count = 0;
public LQHashed(int maximumLength)
{
int k = (int) ((1.0 / loadFactor - 1) * 100.0);
maxLen = fourKPlus3(maximumLength, k);
table = new Listing[maxLen];
deletedListing = new Listing("", 0, 0.0);
for(int i = 0; i < maxLen; i++)
{
table[i] = null;
}
}
public boolean insert(Listing listing)
{
boolean found = false;
int passes;
int offset;
int index;
int q;
int p = listing.getID();
if((((double) count) / maxLen) < loadFactor)
{
passes = 0;
q = p / maxLen;
offset = q;
index = p % maxLen;
if(q % maxLen == 0)
offset = DEFAULT_QUOTIENT;
while(passes < maxLen)
{
if(table[index] == null || table[index] == deletedListing)
{
found = true;
break;
}
index = (index + offset) % maxLen;
passes = passes + 1;
}
if(found == true)
{
table[index] = listing.deepCopy();
count++;
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
public Listing fetch(int key)
{
boolean found = false;
int passes;
int offset;
int index;
int q;
int p = key;
passes = 0;
q = p / maxLen;
offset = q;
index = p % maxLen;
if(q % maxLen == 0)
offset = DEFAULT_QUOTIENT;
while(passes < maxLen)
{
if(table[index] == null)
break;
if(table[index].getID() == key)
{
found = true;
break;
}
index = (index + offset) % maxLen;
passes = passes + 1;
}
if(found == true)
return table[index].deepCopy();
else
return null;
}
public boolean delete(int key)
{
boolean found = false;
int passes;
int offset;
int index;
int q;
int p = key;
passes = 0;
q = p / maxLen;
offset = q;
index = p % maxLen;
if(q % maxLen == 0)
offset = DEFAULT_QUOTIENT;
while(passes < maxLen)
{
if(table[index] == null)
break;
if(table[index].getID() == key)
{
found = true;
break;
}
index = (index + offset) % maxLen;
passes = passes + 1;
}
if(found == true)
{
table[index] = deletedListing;
count--;
return true;
}
else
{
return false;
}
}
public boolean update(int key, Listing listing)
{
if(delete(key) == false)
return false;
if(insert(listing) == false)
return false;
return true;
}
public void showAll()
{
for(int i = 0; i < maxLen; i++)
{
if(table[i] != null && table[i] != deletedListing)
{
System.out.println(table[i].toString());
}
}
}
public static int fourKPlus3(int n, int k)
{
boolean isPrime;
boolean fkp3;
int number;
int hiDiv;
int d;
int p;
isPrime = false;
fkp3 = false;
p = k;
number = (int) (n * (1.0 + (p / 100.0)));
if(number % 2 == 0)
number = number + 1;
while(fkp3 == false)
{
while(isPrime == false)
{
hiDiv = (int) (Math.sqrt(number) + 0.5);
for(d = hiDiv; d > 1; d--)
{
if(number % d == 0)
break;
}
if(d == 1)
isPrime = true;
else
number = number + 2;
}
if((number - 3) % 4 == 0)
fkp3 = true;
else
{
number = number + 2;
isPrime = false;
}
}
return number;
}
} // end of LQHashed class
/*
* File: LQHashedMain.java
*/
import java.util.Scanner;
public class LQHashedMain
{
private static Scanner input = new Scanner(System.in);
public static void main(String[] args)
{
System.out.print("Enter the maximum size of the data set: ");
int maxSize = input.nextInt();
input.nextLine();
LQHashed list = new LQHashed(maxSize);
System.out.print("Enter the initial number of students: ");
int n = input.nextInt();
input.nextLine();
for(int i = 0; i < n; i++)
{
addStudent(list);
}
int choice;
do
{
choice = getMenuChoice();
switch(choice)
{
case 1:
addStudent(list);
break;
case 2:
findAndDisplayStudent(list);
break;
case 3:
removeStudent(list);
break;
case 4:
modifyStudent(list);
break;
case 5:
displayAllStudents(list);
break;
case 6:
System.out.println("Thank you.");
break;
default:
System.out.println("Invalid choice!");
}
System.out.println();
}while(choice != 6);
}
private static int getMenuChoice()
{
System.out.println(" ------------MENU------------");
System.out.println("1 to insert a new student's information");
System.out.println("2 to fetch and output a student's information");
System.out.println("3 to delete a student's information");
System.out.println("4 to update a student's information");
System.out.println("5 to output all the student information");
System.out.println("6 to exit the program");
System.out.print("Enter your choice: ");
int choice = input.nextInt();
input.nextLine();
return choice;
}
private static void addStudent(LQHashed list)
{
System.out.print(" Enter student's id: ");
int id = input.nextInt();
input.nextLine();
while(list.fetch(id) != null)
{
System.out.println("The student with the id " + id + " is already in the list.");
System.out.print("Enter new student's id: ");
id = input.nextInt();
input.nextLine();
}
System.out.print("Enter student's name: ");
String name = input.nextLine();
System.out.print("Enter student's gpa: ");
double gpa = input.nextDouble();
input.nextLine();
Listing record = new Listing(name, id, gpa);
list.insert(record);
}
private static void findAndDisplayStudent(LQHashed list)
{
System.out.print(" Enter student's id: ");
int id = input.nextInt();
input.nextLine();
Listing record = list.fetch(id);
if(record == null)
System.out.println("The student with the id " + id + " is not found in the list.");
else
{
System.out.println("Student name: " + record.getName());
System.out.println("Student ID: " + record.getID());
System.out.println("Student gpa: " + record.getGPA());
}
}
private static void removeStudent(LQHashed list)
{
System.out.print(" Enter student's id: ");
int id = input.nextInt();
input.nextLine();
if(list.delete(id))
System.out.println("The student with the id " + id + " is removed from the list.");
else
System.out.println("The student with the id " + id + " is not found in the list.");
}
private static void modifyStudent(LQHashed list)
{
System.out.print(" Enter student's id: ");
int id = input.nextInt();
input.nextLine();
System.out.print("Enter student's name: ");
String name = input.nextLine();
System.out.print("Enter student's gpa: ");
double gpa = input.nextDouble();
input.nextLine();
Listing record = new Listing(name, id, gpa);
if(list.update(id, record))
System.out.println("The student with the id " + id + " is updated from the list.");
else
System.out.println("The student with the id " + id + " is not found in the list.");
}
private static void displayAllStudents(LQHashed list)
{
list.showAll();
}
} // end of LQHashedMain class
Sample Output:
Enter the maximum size of the data set: 77
Enter the initial number of students: 3
Enter student's id: 5555
Enter student's name: John
Enter student's gpa: 99.09
Enter student's id: 3333
Enter student's name: Smith
Enter student's gpa: 88.08
Enter student's id: 4444
Enter student's name: Mike
Enter student's gpa: 77.07
------------MENU------------
1 to insert a new student's information
2 to fetch and output a student's information
3 to delete a student's information
4 to update a student's information
5 to output all the student information
6 to exit the program
Enter your choice: 5
Name is Mike
ID is 4444
GPA is 77.07
Name is Smith
ID is 3333
GPA is 88.08
Name is John
ID is 5555
GPA is 99.09
------------MENU------------
1 to insert a new student's information
2 to fetch and output a student's information
3 to delete a student's information
4 to update a student's information
5 to output all the student information
6 to exit the program
Enter your choice: 2
Enter student's id: 4444
Student name: Mike
Student ID: 4444
Student gpa: 77.07
------------MENU------------
1 to insert a new student's information
2 to fetch and output a student's information
3 to delete a student's information
4 to update a student's information
5 to output all the student information
6 to exit the program
Enter your choice: 4
Enter student's id: 3333
Enter student's name: Chars
Enter student's gpa: 66.06
The student with the id 3333 is updated from the list.
------------MENU------------
1 to insert a new student's information
2 to fetch and output a student's information
3 to delete a student's information
4 to update a student's information
5 to output all the student information
6 to exit the program
Enter your choice: 3
Enter student's id: 5555
The student with the id 5555 is removed from the list.
------------MENU------------
1 to insert a new student's information
2 to fetch and output a student's information
3 to delete a student's information
4 to update a student's information
5 to output all the student information
6 to exit the program
Enter your choice: 5
Name is Mike
ID is 4444
GPA is 77.07
Name is Chars
ID is 3333
GPA is 66.06
------------MENU------------
1 to insert a new student's information
2 to fetch and output a student's information
3 to delete a student's information
4 to update a student's information
5 to output all the student information
6 to exit the program
Enter your choice: 6
Thank you.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.