Assignment Description:
The goal for this assignment is to implement the Radix Sort algorithm using queues we discussed in class (see Chapter-23-Part2-Advanced-Radix-Search.ppt, slides 16-18). The Queue ADT will be implemented as linked-list.
Part 1 (30 points):
Modify and reuse the code from assignment 2 (class LinkedList.java) to develop a new stand-alone generic class, called Queue.java, to implement queue operations [enqueue(E e), dequeue(), front(), size(), isEmpty()]we discussed from Chapter 20. See slides 10 – 13, file Chapter-20-Part4-Queues. The implementation of class Queue must use generic type to allow creating queue objects that can handle (store) different data types. Follow class Stack from the previous assignment. Please do not use code you may find online, develop your own class by re-using our linked-list class to meet this assignment specific requirement. Include methods countNodes() and printList() from previous classes.
Next, develop a simple test program, called TestQueue.java, to test all queue operations listed above and included in your own class Queue.java. This is similar to the test programs we developed in previous assignments. The test program must test every operation in class Queue with clear outputs, and using meaningful labels and prompts to show the queue content before and after each operation. Make sure you allow the user to enter the queue content (i.e., interactive testing, you may use a menu system in your code). Chapter-23-Part2-Advanced-Radix-Search. Please DO NOT hard-code test data.
Part 2 (70 points):
Use class Queue.java above to implement the Radix Sort algorithm using queues we discussed in class. Call the program RadixSort.java. The program prompts the user to enter 6 integer numbers and store them in an array of type integer (call it inputs). The program applies radix sort algorithm to the values stored in array inputs and then prints out the content of array before and after being sorted. For example, if the user entered the integer numbers 213, 3465, 7, 29, 541, 45, the program output would be as follows:
—-jGRASP exec: java -ea RadixSort Inputs array before sorting: 213, 3465, 7, 29, 541, 45 Inputs array after sorting: 7, 29, 45, 213, 541, 3465 —-jGRASP: operation complete.
Do not treat or manipulate input values as strings at any point for this assignment. They are manipulated as integers throughout the assignment.
Notice that we are using ONLY one array (inputs), and you need 10 queue objects to implement radix sort. See class notes.
Radix sort require digit extraction. To do so, implement a separate method in class RadixSort (call it ExtractDigit(…)) to do this function. See class notes on how to do digit extraction. You also need a method to do digit count in a number.
Design the program such that it allows the user to re-enter different inputs during the same run session. Use a proper prompt such “Do you want to re-run code with different inputs (Y/N)?” If the user enters Y, the program then prompts the user for new inputs. Otherwise, the program terminates. Document your code and organize the outputs properly.

Assigment 2

LinkedList.java

/*
This class define a linked list that stores integer values.
*/
public class LinkedList
{
public Node head, tail;

//constructor method to create a list of object with head, tail, and size.
public LinkedList()
{
head = null;
tail = null;
}
  
//method add node to tail of list
public void addLastNode(int data)
{
if (tail == null)
head = tail = new Node(data); //empty list
else
{
tail.next = new Node(data); //link new node as last node
tail = tail.next; //make tail pointer points to last node
}
}
  
//======== Your part to complete for this assignment =========
//method #1: add first node
public void addFirstNode(int data)
{
Node nptr = new Node(data);
  
if(head == null)
{
head = nptr;
tail = head;
}
else
{
nptr.next=head;
head = nptr;
}
}
  
//method #2: add node at index
public void addAtIndex(int index, int data)
{
Node nptr = new Node(data);
Node ptr = head;
int size=countNodes();
index = index – 1 ;
for (int i = 1; i
{
if (i == index)
{
Node tmp = ptr.next ;
ptr.next=nptr;
nptr.next=tmp;
break;
}
ptr = ptr.next;
}
}
  
//method #3: remove first node
public void removeFirstNode()
{
if(head!=null)
head = head.next;
}
  
//method #4: remove last node
public void removeLastNode()
{
Node s = head;
Node t = head;
while (s != tail)
{
t = s;
s = s.next;
}
tail = t;
tail.next=null;
}
  
//method #5: remove node at index
public void removeAtIndex(int index)
{
int size=countNodes();   
if (index == 1)
{
head = head.next;
return ;
}
if (index == size)
{
Node s = head;
Node t = head;
while (s != tail)
{
t = s;
s = s.next;
}
tail = t;
tail.next=null;
return;
}
Node ptr = head;
index = index – 1 ;
for (int i = 1; i
{
if (i == index)
{
Node tmp = ptr.next;
tmp = tmp.next;
ptr.next=tmp;
break;
}
ptr = ptr.next;
}
}
  
//method #6: countNodes
public int countNodes()
{
int listSize= 0;
//complete this method
//this methods returns th//e list size
Node temp=head;
while(temp!=null)
{
listSize++;
temp=temp.next;
}
return listSize;
}

//method #7: pritnInReverse (Recursive method)
public void printInReverse(Node L)
{
if ( L != null )
{
printInReverse(L.next);
System.out.print(L.data+” “);
}
  
}   
  

//================= tail of your part ==============

//method to print out the list
public void printList()
{
Node temp;
temp = head;
while (temp != null)
{
System.out.print(temp.data + ” “);
temp = temp.next;
}
}
  
//class to create nodes as objects
private class Node
{
private int data; //data field
private Node next; //link field
  
public Node(int item) //constructor method
{
data = item;
next = null;
}
}
}

myTest.java

import java.util.Scanner;

public class myTest
{
public static void main (String[] args)
{
LinkedList myList = new LinkedList(); //create a list object
System.out.println(“Singly Linked List Testn”);
int choice;
Scanner scan = new Scanner(System.in);
/* Perform list operations */
System.out.println(“nSingly Linked List Operationsn”);
System.out.println(“0. Exit Program”);
System.out.println(“1. Add First Node”);
System.out.println(“2. Add Last Node”);
System.out.println(“3. Add At Index”);
System.out.println(“4. Remove First Node”);
System.out.println(“5. Remove Last Node”);
System.out.println(“6. Remove At Index”);
System.out.println(“7. Print List Size”);
System.out.println(“8. Print List (forward)”);
System.out.println(“9 Print List In Reverse”);
  
do
{
System.out.print(“nEnter your choie: “);
choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.print(“nEnter integer element to insert: “);
myList.addFirstNode(scan.nextInt() );   
break;
case 2 :
System.out.print(“nEnter integer element to insert: “);
myList.addLastNode(scan.nextInt() );   
break;   
case 3 :
System.out.print(“nEnter integer element to insert:”);
int num = scan.nextInt() ;
System.out.print(“Enter position: “);
int pos = scan.nextInt() ;
if (pos <= 1 || pos > myList.countNodes())
System.out.println(“Invalid positionn”);
else
myList.addAtIndex(pos, num);
break;   
case 4:
myList.removeFirstNode();
break;
case 5:
myList.removeLastNode();
break;
case 6 :
System.out.print(“nEnter position: “);
int p = scan.nextInt() ;
if (p < 1 || p > myList.countNodes())
System.out.println(“Invalid positionn”);
else
myList.removeAtIndex(p);
break;
case 7 :
System.out.println(“nSize of the list is : “+myList.countNodes());
break;   
case 8 :
System.out.println(“nList is: “);
myList.printList();
System.out.println(“n”);
break;
case 9 :
System.out.println(“nReverse list is: “);
myList.printInReverse(myList.head);
System.out.println(“nn”);
break;
case 0:
break;
default :
System.out.println(“nWrong Entry n “);
break;   
}
/* Display List */
  
} while (choice!=0);
}
}



Source link

Leave a Reply

Your email address will not be published. Required fields are marked *