summaryrefslogtreecommitdiff
path: root/labs/lab04_recurionll
diff options
context:
space:
mode:
Diffstat (limited to 'labs/lab04_recurionll')
-rw-r--r--labs/lab04_recurionll/RecursionLLTester.java232
-rw-r--r--labs/lab04_recurionll/RecursionLinkedList.java164
-rw-r--r--labs/lab04_recurionll/lab04_rll.pdfbin0 -> 74989 bytes
3 files changed, 396 insertions, 0 deletions
diff --git a/labs/lab04_recurionll/RecursionLLTester.java b/labs/lab04_recurionll/RecursionLLTester.java
new file mode 100644
index 0000000..e93ef3d
--- /dev/null
+++ b/labs/lab04_recurionll/RecursionLLTester.java
@@ -0,0 +1,232 @@
+import java.util.Random;
+
+
+public class RecursionLLTester
+{
+ public static void main(String[] args)
+ {
+ RecursionLinkedList rll = new RecursionLinkedList();
+ int point = 0;
+ boolean isError = false;
+
+ System.out.println("Create an empty RecursionLinkedList named rll.");
+
+ System.out.print("Test the method contains() on an empty RecursionLinkedList: ");
+ if(rll.contains(5) != false)
+ {
+ System.out.println("FAIL");
+ System.out.println("Nothing is added into RecursionLinkedList rll.");
+ System.out.println("rll.contains(5) should return 0.");
+ System.out.println("But your rll.contains(5) returns " + rll.contains(5) + ".");
+ }
+ else
+ {
+ System.out.println("PASS");
+ point++;
+ }
+
+ System.out.print("Test the method getFrequencyOf() on an empty RecursionLinkedList: ");
+ if(rll.getFrequencyOf(5) != 0)
+ {
+ System.out.println("FAIL");
+ System.out.println("Nothing is added into RecursionLinkedList rll.");
+ System.out.println("rll.getFrequencyOf(5) should return 0.");
+ System.out.println("But your rll.getFrequencyOf(5) returns " + rll.getFrequencyOf(5) + ".");
+ }
+ else
+ {
+ System.out.println("PASS");
+ point++;
+ }
+
+ Random rand = new Random();
+ int num = 20;
+ int[] array = new int[5];
+ for(int i = 0; i < 5; i++)
+ {
+ array[i] = 0;
+ }
+
+ System.out.println("Add the following integer into rll:");
+ String s = "]";
+
+ for(int i = 0; i < num - 1; i++)
+ {
+ int temp = rand.nextInt(5);
+ System.out.print(temp + " ");
+ s = "," + temp + s;
+ array[temp]++;
+ rll.add(temp);
+ }
+ int temp = rand.nextInt(5);
+ System.out.println(temp);
+ s = "[" + temp + s;
+ array[temp]++;
+ rll.add(temp);
+
+
+ System.out.println("\nTest the method contains() on a non-empty RecursionLinkedList");
+ System.out.print(" - Test rll.contains(-1): ");
+ if(rll.contains(-1) != false)
+ {
+ System.out.println("FAIL");
+ System.out.println("No -1 has been added into the RecursionLinkedList rll.");
+ System.out.println("rll.contains(-1) should return 0.");
+ System.out.println("But your rll.contains(-1) returns " + rll.contains(-1));
+ }
+ else
+ {
+ System.out.println("PASS");
+ point++;
+ }
+
+ for(int i = 0; i < 5; i++)
+ {
+ System.out.print(" - Test rll.contains(" + i + "): ");
+ if(rll.contains(i) != (array[i] != 0))
+ {
+ System.out.println("FAIL");
+ System.out.println("There are " + array[i] + " in RecursiveLinkedList rll.");
+ System.out.println("rll.contains(" + i + ") should return " + (array[i] != 0));
+ System.out.println("But your rll.contains(" + i + ") returns " + rll.contains(i));
+ isError = true;
+ }
+ else
+ {
+ System.out.println("PASS");
+ }
+ }
+
+ if(!isError)
+ {
+ point++;
+ isError = false;
+ }
+
+ System.out.print(" - Test rll.contains(5): ");
+ if(rll.contains(5) != false)
+ {
+ System.out.println("FAIL");
+ System.out.println("No 5 has been added into the RecursionLinkedList rll.");
+ System.out.println("rll.contains(5) should return 0.");
+ System.out.println("But your rll.contains(5) returns " + rll.contains(5));
+ }
+ else
+ {
+ System.out.println("PASS");
+ point++;
+ }
+
+ System.out.println("Test the method getFrequencyOf() on a non-empty RecursionLinkedList");
+ System.out.print(" - Test rll.getFrequencyOf(-1): ");
+ if(rll.getFrequencyOf(-1) != 0)
+ {
+ System.out.println("FAIL");
+ System.out.println("No -1 has been added into the RecursionLinkedList rll.");
+ System.out.println("rll.getFrequencyOf(-1) should return 0.");
+ System.out.println("But your rll.getFrequencyOf(-1) returns " + rll.getFrequencyOf(-1));
+ }
+ else
+ {
+ System.out.println("PASS");
+ point++;
+ }
+
+ for(int i = 0; i < 5; i++)
+ {
+ System.out.print(" - Test rll.getFrequencyOf(" + i + "): ");
+ if(rll.getFrequencyOf(i) != array[i])
+ {
+ System.out.println("FAIL");
+ System.out.println(i + " has been added to the RecursionLinkedList " + array[i] + " times.");
+ System.out.println("rll.getFrequencyOf(" + i + ") should return " + array[i] + ".");
+ System.out.println("But your rll.getFrequencyOf(" + i + ") returns " + rll.getFrequencyOf(i));
+ isError = true;
+ }
+ else
+ {
+ System.out.println("PASS");
+ }
+ }
+
+ if(!isError)
+ {
+ point++;
+ isError = false;
+ }
+
+ System.out.print(" - Test rll.getFrequencyOf(5): ");
+ if(rll.getFrequencyOf(5) != 0)
+ {
+ System.out.println("FAIL");
+ System.out.println("No 5 has been added into the RecursionLinkedList rll.");
+ System.out.println("rll.getFrequencyOf(5) should return 0.");
+ System.out.println("But your rll.getFrequencyOf(5) returns " + rll.getFrequencyOf(5));
+ }
+ else
+ {
+ System.out.println("PASS");
+ point++;
+ }
+
+ System.out.print("Test the method toString(): ");
+ if(!s.equals(rll.toString()))
+ {
+ System.out.println("FAIL");
+ System.out.println("rll.toString() should return the string \"" + s + "\".");
+ System.out.println("But your rll.toString() returns the string \"" + rll.toString() + "\".");
+ }
+ else
+ {
+ System.out.println("PASS");
+ point++;
+ }
+
+
+ System.out.println("Test the method getIndexOf()");
+ System.out.println("Currently the rll is " + rll + ".");
+
+ String[] str = rll.toString().split(",");
+ str[0] = str[0].substring(1);
+ str[str.length - 1] = str[str.length - 1].substring(0, 1);
+
+ for(int i = -1; i <= 5; i++)
+ {
+ System.out.print("Test the method getIndexOf(" + i + "): ");
+ if(getIndex(str,i) != rll.getIndexOf(i))
+ {
+ System.out.println("FAIL");
+ System.out.println("The index of " + i + " should be " + getIndex(str,i) + ".");
+ System.out.println("But your rll.getIndexOf(" + i + ") returns " + rll.getIndexOf(i) + ".");
+ isError = true;
+ }
+ else
+ {
+ System.out.println("PASS");
+ }
+ }
+
+ if(!isError)
+ {
+ point++;
+ isError = false;
+ }
+
+ System.out.println("Your current point is " + point + ".");
+ }
+
+ public static int getIndex(String[] str, int s)
+ {
+ int result = -1;
+
+ for(int i = 0; i < str.length; i++)
+ {
+ if(s == Integer.parseInt(str[i]))
+ {
+ return i;
+ }
+ }
+
+ return result;
+ }
+}
diff --git a/labs/lab04_recurionll/RecursionLinkedList.java b/labs/lab04_recurionll/RecursionLinkedList.java
new file mode 100644
index 0000000..bd1f3c5
--- /dev/null
+++ b/labs/lab04_recurionll/RecursionLinkedList.java
@@ -0,0 +1,164 @@
+
+public class RecursionLinkedList
+{
+ private Node firstNode;
+ private int numberOfEntries;
+
+ public RecursionLinkedList()
+ {
+ firstNode = null;
+ numberOfEntries = 0;
+ }
+
+ public void add(int aData)
+ {
+ if(numberOfEntries == 0)
+ {
+ firstNode = new Node(aData);
+ }
+ else
+ {
+ firstNode = new Node(aData, firstNode);
+ }
+
+ numberOfEntries++;
+ }
+
+ /**
+ * boolean contains(int aData)
+ *
+ * See whether this RecursionLinkedList contains aData
+ * @param aData a data to be located
+ * @return true if this RecursionLinkedList contains aData,
+ * or false otherwise.
+ */
+ public boolean contains(int aData)
+ {
+ return containsHelper(firstNode,aData);
+ }
+ private boolean containsHelper(Node thisnode, int aData)
+ {
+ if(thisnode == null)
+ {
+ return false;
+ }
+ else if(thisnode.data == aData)
+ {
+ return true;
+ }
+ else
+ {
+ return containsHelper(thisnode.next, aData);
+ }
+ }
+
+ /**
+ * int getFrequencyOf(int aData)
+ *
+ * Counts the number of times a given data appears in this
+ * RecursionLinkedList.
+ *
+ * @param aData the data to be counted
+ * @return the number of times aData appears in this RecursionLinkedList
+ */
+ public int getFrequencyOf(int aData)
+ {
+ return getFrequencyOfHelper(firstNode,aData);
+ }
+ private int getFrequencyOfHelper(Node thisnode, int aData)
+ {
+ if(thisnode == null)
+ {
+ return 0;
+ }
+ else if(thisnode.data == aData)
+ {
+ return getFrequencyOfHelper(thisnode.next, aData) + 1;
+ }
+ else
+ {
+ return getFrequencyOfHelper(thisnode.next, aData);
+ }
+ }
+
+ /**
+ * String toString()
+ *
+ * Return a string representation of this RecursionLinkedList. For example,
+ * if this RecursionLinkedList contains 1, 2, 3, 5, 2 and 3 from the first
+ * index to the last index, the returned string should be
+ * "[1,2,3,5,2,3]"
+ * @return the string representation of this RecursionLinkedList.
+ */
+ public String toString()
+ {
+ return "[" + firstNode.data + toStringHelper(firstNode.next) + "]";
+ }
+ private String toStringHelper(Node thisnode)
+ {
+ if(thisnode == null)
+ {
+ return "";
+ }
+ else
+ {
+ return "," + thisnode.data + toStringHelper(thisnode.next);
+ }
+ }
+ /**
+ * int getIndexOf(int aData)
+ *
+ * Return the index of the first aData where the first index of
+ * the first item in this RecursionLinkedList is 0.
+ *
+ * @param aData the data to be located
+ * @return the index of the first aData.
+ */
+ public int getIndexOf(int aData)
+ {
+ int p = getIndexOfHelper(firstNode,aData);
+ /*
+ if(p==numberOfEntries+1)
+ {
+ return -1;
+ }
+ else
+ {
+ return p;
+ }
+ */
+ return p==numberOfEntries+1?-1:p;
+ }
+ private int getIndexOfHelper(Node thisnode, int aData)
+ {
+ if(thisnode == null)
+ {
+ return 1;
+ }
+ else if(thisnode.data == aData)
+ {
+ return 0;
+ }
+ else
+ {
+ return getIndexOfHelper(thisnode.next,aData) + 1;
+ }
+ }
+
+ private class Node
+ {
+ private int data;
+ private Node next;
+
+ private Node(int aData, Node nextNode)
+ {
+ data = aData;
+ next = nextNode;
+ }
+
+ private Node(int aData)
+ {
+ this(aData, null);
+ }
+ }
+}
diff --git a/labs/lab04_recurionll/lab04_rll.pdf b/labs/lab04_recurionll/lab04_rll.pdf
new file mode 100644
index 0000000..0ec1faa
--- /dev/null
+++ b/labs/lab04_recurionll/lab04_rll.pdf
Binary files differ
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-01-18 15:21:29 +0000