Complete the bold section below. For the debug, disable mainDebug() and only run
ID: 3909232 • Letter: C
Question
Complete the bold section below. For the debug, disable mainDebug() and only run mainRunTests() - you don't need to do the TO DO section.
I don't have access to the trace class, unless you can specify how to obtain it.
-----------------------------------------------------------
import java.text.DecimalFormat;
import stdlib.*;
/*
* Complete the methods below.
* None of the methods should modify the list, unless that is the purpose of the method.
*
* You may not add any fields to the node or list classes.
* You may not add any methods to the node class.
*
* You MAY add private methods to the list class (helper functions for the recursion).
*/
public class MyLinked {
static class Node {
public Node (double item, Node next) { this.item = item; this.next = next; }
public double item;
public Node next;
}
int N;
Node first;
// write a function to compute the size of the list, using a loop
// empty list has size 0
public int sizeLoop () {
return StdRandom.uniform (100); //TODO: fix this
}
// write a function to compute the size of the list, using an optimistic, forward recursion
// empty list has size 0
public int sizeForward () {
return StdRandom.uniform (100); //TODO: fix this
}
// write a function to compute the size of the list, using an optimistic, backward recursion
// empty list has size 0
public int sizeBackward () {
return StdRandom.uniform (100); //TODO: fix this
}
// compute the position of the first 5.0 in the list, counting as an offset from the beginning.
// if 5.0 is the FIRST element, the position is 0
// if 5.0 does not appear, return a negative number
// you can write this using a loop or recursion, in any style, but you should only have one loop or recursive helper
// I would expect
// [0,1,2,5,5,5,5,5,8,9].positionOfFirstFiveFromBeginning() == 3
// [0,1,2,5,5,5,5,5,8,9].positionOfLastFiveFromEnd() == 2
public int positionOfFirstFiveFromBeginning () {
return StdRandom.uniform (100); //TODO: fix this
}
// compute the position of the last 5.0 in the list, counting as an offset from the end.
// if 5.0 is the LAST element, the position is 0
// if 5.0 does not appear, return a negative number
// you can write this using a loop or recursion, in any style, but you should only have one loop or recursive helper
// Hint: Use a backward recursion.
// Hint: If the number does not appear, return the distance to the END of the list as a NEGATIVE number.
public int positionOfLastFiveFromEnd () {
return StdRandom.uniform (100); //TODO: fix this
}
// delete the first element
public void deleteFirst () {
// TODO
}
// delete the kth element (where k is between 0 and N-1 inclusive)
public void delete (int k) {
if (k < 0 || k >= N) throw new IllegalArgumentException ();
// TODO
}
// reverse the list "in place"... without creating any new nodes
public void reverse () {
// TODO
}
// remove all occurrences of item from the list
public void remove (double item) {
// TODO
}
public static void main (String args[]) {
//mainDebug ();
mainRunTests ();
}
private static void mainDebug () {
// Use this for debugging!
// Add the names of helper functions if you use them.
Trace.drawStepsOfMethod ("sizeLoop");
Trace.drawStepsOfMethod ("sizeForward");
Trace.drawStepsOfMethod ("sizeBackward");
Trace.drawStepsOfMethod ("positionOfFirstFiveFromBeginning");
Trace.drawStepsOfMethod ("positionOfLastFiveFromEnd");
Trace.drawStepsOfMethod ("deleteFirst");
Trace.drawStepsOfMethod ("delete");
Trace.drawStepsOfMethod ("reverse");
Trace.drawStepsOfMethod ("remove");
Trace.run ();
// TODO: Put the test here you want to debug:
testSizeLoop (4, "11 -21.2 31 41");
// TODO: Put the test here you want to debug:
testDelete (2, "11 21 31 41", "[ 11 21 41 ]");
}
private static void mainRunTests () {
testSizeLoop (0, "");
testSizeLoop (1, "11");
testSizeLoop (2, "11 21");
testSizeLoop (4, "11 -21.2 31 41");
testSizeForward (0, "");
testSizeForward (1, "11");
testSizeForward (2, "11 21");
testSizeForward (4, "11 -21.2 31 41");
testSizeBackward (0, "");
testSizeBackward (1, "11");
testSizeBackward (2, "11 21");
testSizeBackward (4, "11 -21.2 31 41");
testPositionOfFirstFiveFromBeginning (-1, "");
testPositionOfFirstFiveFromBeginning (-1, "11");
testPositionOfFirstFiveFromBeginning (-1, "11 21 31 41");
testPositionOfFirstFiveFromBeginning (0, "5 11 21 31 41");
testPositionOfFirstFiveFromBeginning (1, "11 5 21 31 41");
testPositionOfFirstFiveFromBeginning (2, "11 21 5 31 41");
testPositionOfFirstFiveFromBeginning (3, "11 21 31 5 41");
testPositionOfFirstFiveFromBeginning (4, "11 21 31 41 5");
testPositionOfFirstFiveFromBeginning (3, "0 1 2 5 5 5 5 5 8 9");
testPositionOfLastFiveFromEnd (-1, "");
testPositionOfLastFiveFromEnd (-2, "11");
testPositionOfLastFiveFromEnd (-5, "11 21 31 41");
testPositionOfLastFiveFromEnd (4, "5 11 21 31 41");
testPositionOfLastFiveFromEnd (3, "11 5 21 31 41");
testPositionOfLastFiveFromEnd (2, "11 21 5 31 41");
testPositionOfLastFiveFromEnd (1, "11 21 31 5 41");
testPositionOfLastFiveFromEnd (0, "11 21 31 41 5");
testPositionOfLastFiveFromEnd (2, "0 1 2 5 5 5 5 5 8 9");
testPositionOfLastFiveFromEnd (2, "0 1 2 5 5 5 5 5 5 8 9");
// Trace.run (); // uncomment this to get drawings in showError
testDelete (0, "", "java.lang.IllegalArgumentException");
testDelete(-1, "11 21 31", "java.lang.IllegalArgumentException");
testDelete (3, "11 21 31", "java.lang.IllegalArgumentException");
testDelete (0, "11", "[ ]");
testDelete (0, "11 21 31 41", "[ 21 31 41 ]");
testDelete (1, "11 21 31 41", "[ 11 31 41 ]");
testDelete (2, "11 21 31 41", "[ 11 21 41 ]");
testDelete (3, "11 21 31 41", "[ 11 21 31 ]");
testDelete (0, "11 21 31 41 51", "[ 21 31 41 51 ]");
testDelete (1, "11 21 31 41 51", "[ 11 31 41 51 ]");
testDelete (2, "11 21 31 41 51", "[ 11 21 41 51 ]");
testDelete (3, "11 21 31 41 51", "[ 11 21 31 51 ]");
testDelete (4, "11 21 31 41 51", "[ 11 21 31 41 ]");
testReverse ("", "[ ]");
testReverse ("11", "[ 11 ]");
testReverse ("11 21", "[ 21 11 ]");
testReverse ("11 21 31", "[ 31 21 11 ]");
testReverse ("11 21 31 41", "[ 41 31 21 11 ]");
testReverse ("11 21 31 41 51", "[ 51 41 31 21 11 ]");
testRemove (5, "", "[ ]");
testRemove (5, "5", "[ ]");
testRemove (5, "5 5", "[ ]");
testRemove (5, "5 5 5", "[ ]");
testRemove (5, "11", "[ 11 ]");
testRemove (5, "11 21", "[ 11 21 ]");
testRemove (5, "11 21 31", "[ 11 21 31 ]");
testRemove (5, "5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5 5 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 5 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5 5 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 5 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 5 11 5 5 21 5 31 5 5 41 5 5 5", "[ 11 21 31 41 ]");
testRemove (5.1, "5.1 5.1 5.1 5 11 5.1 5.1 21 5.1 31 5.1 5.1 41 5.1 5.1 5.1", "[ 5 11 21 31 41 ]");
StdOut.println ("Finished tests");
}
Explanation / Answer
import java.text.DecimalFormat;
import stdlib.*;
/*
* Complete the methods below.
* None of the methods should modify the list, unless that is the purpose of the method.
*
* You may not add any fields to the node or list classes.
* You may not add any methods to the node class.
*
* You MAY add private methods to the list class (helper functions for the recursion).
*/
public class MyLinked {
static class Node {
public Node (double item, Node next) { this.item = item; this.next = next; }
public double item;
public Node next;
}
int N;
Node first;
// write a function to compute the size of the list, using a loop
// empty list has size 0
public int sizeLoop () {
Node curr = first;
int size = 0;
while(curr != null) {
++size;
curr = curr.next;
}
return size;
}
public int sizeForwardUtil (Node node) {
if(node==null)
return 0;
return 1 + sizeForwardUtil (node.next);
}
// write a function to compute the size of the list, using an optimistic, forward recursion
// empty list has size 0
public int sizeForward () {
return sizeForwardUtil(first);
}
// write a function to compute the size of the list, using an optimistic, backward recursion
// empty list has size 0
public int sizeBackwardUtil (Node node, int size) {
if(node==null)
return size;
return sizeBackwardUtil(node.next, size+1);
}
public int sizeBackward () {
return sizeBackwardUtil(first, 0); //TODO: fix this
}
// compute the position of the first 5.0 in the list, counting as an offset from the beginning.
// if 5.0 is the FIRST element, the position is 0
// if 5.0 does not appear, return a negative number
// you can write this using a loop or recursion, in any style, but you should only have one loop or recursive helper
// I would expect
// [0,1,2,5,5,5,5,5,8,9].positionOfFirstFiveFromBeginning() == 3
// [0,1,2,5,5,5,5,5,8,9].positionOfLastFiveFromEnd() == 2
public int positionOfFirstFiveFromBeginning () {
Node curr = first;
int index = -1 , i = 0;
while(curr != null) {
if(curr.item==5) {
return i;
}
++i ;
curr = curr.next;
}
return index;
}
// compute the position of the last 5.0 in the list, counting as an offset from the end.
// if 5.0 is the LAST element, the position is 0
// if 5.0 does not appear, return a negative number
// you can write this using a loop or recursion, in any style, but you should only have one loop or recursive helper
// Hint: Use a backward recursion.
// Hint: If the number does not appear, return the distance to the END of the list as a NEGATIVE number.
public int positionOfLastFiveFromEnd () {
Node curr = first;
int index = -1 , i = 0;
while(curr != null) {
if(curr.item==5) {
index = i;
}
++i ;
curr = curr.next;
}
if(index != -1)
return i-index-1;
return (-1*(i+1));
}
// delete the first element
public void deleteFirst () {
// TODO
if(first==null)
return;
first = first.next;
}
// delete the kth element (where k is between 0 and N-1 inclusive)
public void delete (int k) {
if (k < 0 || k >= N) throw new IllegalArgumentException ();
Node current = first;
Node prev = null, next = null;
int index = 0;
while (current != null && index < k)
{
index++;
prev = current;
current = current.next;
}
if(prev==null & current!=null) {
first = first.next;
}else {
prev.next = current.next;
}
// TODO
}
// reverse the list "in place"... without creating any new nodes
public void reverse () {
// TODO
Node current = first;
Node prev = null, next = null;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
first = prev;
}
// remove all occurrences of item from the list
public void remove(double item) {
// TODO
Node current = first;
Node prev = null;
while (current != null) {
if (current.item == item) {
if (prev == null) {
first = first.next;
current = current.next;
} else {
prev.next = current.next;
current = prev.next;
}
} else {
prev = current;
current = current.next;
}
}
}
public static void main (String args[]) {
//mainDebug ();
mainRunTests ();
}
//private static void mainDebug () {
//
//// Use this for debugging!
//
//// Add the names of helper functions if you use them.
//
//Trace.drawStepsOfMethod ("sizeLoop");
//
//Trace.drawStepsOfMethod ("sizeForward");
//
//Trace.drawStepsOfMethod ("sizeBackward");
//
//Trace.drawStepsOfMethod ("positionOfFirstFiveFromBeginning");
//
//Trace.drawStepsOfMethod ("positionOfLastFiveFromEnd");
//
//Trace.drawStepsOfMethod ("deleteFirst");
//
//Trace.drawStepsOfMethod ("delete");
//
//Trace.drawStepsOfMethod ("reverse");
//
//Trace.drawStepsOfMethod ("remove");
//
//Trace.run ();
//
//// TODO: Put the test here you want to debug:
//
//testSizeLoop (4, "11 -21.2 31 41");
//
//// TODO: Put the test here you want to debug:
//
//testDelete (2, "11 21 31 41", "[ 11 21 41 ]");
//
//}
private static void mainRunTests () {
testSizeLoop (0, "");
testSizeLoop (1, "11");
testSizeLoop (2, "11 21");
testSizeLoop (4, "11 -21.2 31 41");
testSizeForward (0, "");
testSizeForward (1, "11");
testSizeForward (2, "11 21");
testSizeForward (4, "11 -21.2 31 41");
testSizeBackward (0, "");
testSizeBackward (1, "11");
testSizeBackward (2, "11 21");
testSizeBackward (4, "11 -21.2 31 41");
testPositionOfFirstFiveFromBeginning (-1, "");
testPositionOfFirstFiveFromBeginning (-1, "11");
testPositionOfFirstFiveFromBeginning (-1, "11 21 31 41");
testPositionOfFirstFiveFromBeginning (0, "5 11 21 31 41");
testPositionOfFirstFiveFromBeginning (1, "11 5 21 31 41");
testPositionOfFirstFiveFromBeginning (2, "11 21 5 31 41");
testPositionOfFirstFiveFromBeginning (3, "11 21 31 5 41");
testPositionOfFirstFiveFromBeginning (4, "11 21 31 41 5");
testPositionOfFirstFiveFromBeginning (3, "0 1 2 5 5 5 5 5 8 9");
testPositionOfLastFiveFromEnd (-1, "");
testPositionOfLastFiveFromEnd (-2, "11");
testPositionOfLastFiveFromEnd (-5, "11 21 31 41");
testPositionOfLastFiveFromEnd (4, "5 11 21 31 41");
testPositionOfLastFiveFromEnd (3, "11 5 21 31 41");
testPositionOfLastFiveFromEnd (2, "11 21 5 31 41");
testPositionOfLastFiveFromEnd (1, "11 21 31 5 41");
testPositionOfLastFiveFromEnd (0, "11 21 31 41 5");
testPositionOfLastFiveFromEnd (2, "0 1 2 5 5 5 5 5 8 9");
testPositionOfLastFiveFromEnd (2, "0 1 2 5 5 5 5 5 5 8 9");
// Trace.run (); // uncomment this to get drawings in showError
testDelete (0, "", "java.lang.IllegalArgumentException");
testDelete(-1, "11 21 31", "java.lang.IllegalArgumentException");
testDelete (3, "11 21 31", "java.lang.IllegalArgumentException");
testDelete (0, "11", "[ ]");
testDelete (0, "11 21 31 41", "[ 21 31 41 ]");
testDelete (1, "11 21 31 41", "[ 11 31 41 ]");
testDelete (2, "11 21 31 41", "[ 11 21 41 ]");
testDelete (3, "11 21 31 41", "[ 11 21 31 ]");
testDelete (0, "11 21 31 41 51", "[ 21 31 41 51 ]");
testDelete (1, "11 21 31 41 51", "[ 11 31 41 51 ]");
testDelete (2, "11 21 31 41 51", "[ 11 21 41 51 ]");
testDelete (3, "11 21 31 41 51", "[ 11 21 31 51 ]");
testDelete (4, "11 21 31 41 51", "[ 11 21 31 41 ]");
testReverse ("", "[ ]");
testReverse ("11", "[ 11 ]");
testReverse ("11 21", "[ 21 11 ]");
testReverse ("11 21 31", "[ 31 21 11 ]");
testReverse ("11 21 31 41", "[ 41 31 21 11 ]");
testReverse ("11 21 31 41 51", "[ 51 41 31 21 11 ]");
testRemove (5, "", "[ ]");
testRemove (5, "5", "[ ]");
testRemove (5, "5 5", "[ ]");
testRemove (5, "5 5 5", "[ ]");
testRemove (5, "11", "[ 11 ]");
testRemove (5, "11 21", "[ 11 21 ]");
testRemove (5, "11 21 31", "[ 11 21 31 ]");
testRemove (5, "5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5 5 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 5 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 5 11 21 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 31 41 5 5 5", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "11 21 5 5 5 31 41", "[ 11 21 31 41 ]");
testRemove (5, "5 5 5 11 5 5 21 5 31 5 5 41 5 5 5", "[ 11 21 31 41 ]");
testRemove (5.1, "5.1 5.1 5.1 5 11 5.1 5.1 21 5.1 31 5.1 5.1 41 5.1 5.1 5.1", "[ 5 11 21 31 41 ]");
StdOut.println ("Finished tests");
}
================
Run and Let me know the Result..I will help if any of the TEST fails..
Thanks, I cant test because you have not provided the Test Code. I did my best and wrote all the CODE
PLEASE UPVOTE and comment if any of the test fails. I will help through comments
PLEASE UPVOTE
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.