# CSC300: Lecture 3 (Simple Objects and Linked Structures (1.2, 1.3))

 Contents [0/16]

 Homework [1/16] Linked structures: Starter code [2/16] Linked structures: Loop [3/16] Linked structures: Forward recursion, nullable argument [4/16] Linked structures: Forward recursion, non-nullable argument [5/16] Linked structures: Backward recursion, nullable argument [6/16] Linked structures: Backward recursion, non-nullable argument [7/16] Common mistakes: Does this work? [8/16] Common mistakes: Does this work? [9/16] Common mistakes: Does this work? [10/16] Common mistakes: Does this work? [11/16] Common mistakes: Does this work? [12/16] Common mistakes: Does this work? [13/16] Common mistakes: Does this work? [14/16] Common mistakes: Does this work? [15/16] numFives starter code with array [16/16]

 Homework [1/16]

• If you've had a hard time with the first two weeks quizzes and assignments, try looking over some more AP material.

• Skim Algorithms section 1.2

Read Algorithms (the primary text) section 1.3: concentrate on the last section, on linked lists.

Read Core Java for the impatient chapter 3 and sections 4.1-4.4.

Look at the booksite. Find the notes on section 1.3

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ``` ```package algs13; import java.text.DecimalFormat; import stdlib.*; public class Playground { private Node first; static class Node { public double item; public Node next; public Node (double item, Node next) { this.item = item; this.next = next; } } public int numFives () { return StdRandom.uniform (100); //TODO: fix this } /* ToString method to print */ public String toString () { // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes DecimalFormat format = new DecimalFormat ("#.###"); StringBuilder result = new StringBuilder ("[ "); for (Node x = first; x != null; x = x.next) { result.append (format.format (x.item)); result.append (" "); } result.append ("]"); return result.toString (); } /* Method to create lists */ public static Playground of(String s) { Node first = null; String[] nums = s.split (" "); for (int i = nums.length-1; i >= 0; i--) { try { double num = Double.parseDouble (nums[i]); first = new Node (num, first); } catch (NumberFormatException e) { // ignore anything that is not a double } } Playground result = new Playground (); result.first = first; return result; } /* A silly method to show list creation */ public static Playground example(int i) { Node x1 = new Node (i+10, null); Node x2 = new Node (i+20, null); Node x3 = new Node (i+30, null); Node x4 = new Node (i+40, null); Playground result = new Playground (); result.first = x1; x1.next = x2; x2.next = x3; x3.next = x4; return result; } public static void main (String[] args) { Trace.drawSteps (); Trace.run (); Playground example1 = Playground.example (1); Playground example2 = Playground.example (5); Playground example3 = Playground.example (7); } public static void testNumFives (int expected, String sList) { Playground list = Playground.of (sList); int actual = list.numFives (); if (expected != actual) { StdOut.format ("Failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, list); } } public static void main1 (String[] args) { testNumFives (0, ""); testNumFives (1, "5"); testNumFives (0, "11"); testNumFives (3, "5 5 5"); testNumFives (0, "11 21 31 41"); testNumFives (1, "5 11 21 31 41"); testNumFives (1, "11 21 31 41 5"); testNumFives (1, "11 21 5 31 41"); testNumFives (5, "5 11 21 5 5 31 5 41 5"); StdOut.println ("Finished tests"); } public static void main2 (String[] args) { Trace.drawStepsOfMethod ("numFives"); Trace.drawStepsOfMethod ("numFivesH"); Trace.run (); //Playground list0 = Playground.of ("5"); Playground list1 = Playground.of ("5 11 5 5"); //Playground list2 = Playground.of ("24 35 67"); int result1 = list1.numFives (); StdOut.println ("result: " + result1); } }```

 ``` 11 12 13 14 15 16 17 18 19 ``` ``` public int numFives () { int result = 0; Node x = first; while (x != null) { if (x.item == 5) result = result + 1; x = x.next; } return result; }```

For `[5,11,5,5]`, the loop values (line 4) are

```x==[5,11,5,5], result==0
x==[11,5,5], result==1
x==[5,5], result==1
x==[5], result==2
x==[], result==3 (x==null)```

There is an image to the right of the code.
Click to animate in single-slide mode.
To enter single-slide mode, click the slide number in the title bar.

 Linked structures: Forward recursion, nullable argument [4/16]

 ``` 11 12 13 14 15 16 17 18 19 ``` ``` public int numFives () { return numFivesH (first, 0); } private static int numFivesH (Node x, int result) { if (x == null) return result; if (x.item == 5) result = result + 1; result = numFivesH (x.next, result); return result; }```

For `[5,11,5,5]`, the call tree is

```call@3 ([5,11,5,5], 0)
call@4 ([11,5,5], 1)
call@5  ([5,5], 1)
call@6  ([5], 2)
call@7 ([], 3)
retn@7 ([], 3) : 3
retn@6  ([5], 2) : 3
retn@5  ([5,5], 1) : 3
retn@4 ([11,5,5], 1) : 3
retn@3 ([5,11,5,5], 0) : 3```

 Linked structures: Forward recursion, non-nullable argument [5/16]

 ``` 11 12 13 14 15 16 17 18 19 ``` ``` public int numFives () { if (first == null) return 0; return numFivesH (first, 0); } private static int numFivesH (Node x, int result) { if (x.item == 5) result = result + 1; if (x.next != null) result = numFivesH (x.next, result); return result; }```

For `[5,11,5,5]`, the call tree is

```call@3 ([5,11,5,5], 0)
call@4 ([11,5,5], 1)
call@5  ([5,5], 1)
call@6  ([5], 2)
retn@6  ([5], 2) : 3
retn@5  ([5,5], 1) : 3
retn@4 ([11,5,5], 1) : 3
retn@3 ([5,11,5,5], 0) : 3```

 Linked structures: Backward recursion, nullable argument [6/16]

 ``` 11 12 13 14 15 16 17 18 19 ``` ``` public int numFives () { return numFivesH (first); } private static int numFivesH (Node x) { if (x == null) return 0; int result = numFivesH (x.next); if (x.item == 5) result = result + 1; return result; }```

For `[5,11,5,5]`, the call tree is

```call@3 ([5,11,5,5])
call@4 ([11,5,5])
call@5  ([5,5])
call@6  ([5])
call@7 ([])
retn@7 ([]) : 0
retn@6  ([5]) : 1
retn@5  ([5,5]) : 2
retn@4 ([11,5,5]) : 2
retn@3 ([5,11,5,5]) : 3```

 Linked structures: Backward recursion, non-nullable argument [7/16]

 ``` 11 12 13 14 15 16 17 18 19 ``` ``` public int numFives () { if (first == null) return 0; return numFivesH (first); } private static int numFivesH (Node x) { int result = (x.next == null) ? 0 : numFivesH (x.next); if (x.item == 5) result = result + 1; return result; }```
```call@3 ([5,11,5,5])
call@4 ([11,5,5])
call@5  ([5,5])
call@6  ([5])
retn@6  ([5]) : 1
retn@5  ([5,5]) : 2
retn@4 ([11,5,5]) : 2
retn@3 ([5,11,5,5]) : 3```

A more verbose version:

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 ``` ``` public int numFives () { if (first == null) return 0; return numFivesH (first); } private static int numFivesH (Node x) { int result = 0; if (x.next != null) { result = numFivesH (x.next); } if (x.item == 5) result = result + 1; return result; }```

 Common mistakes: Does this work? [8/16]

 ``` 11 12 13 14 15 16 17 ``` ``` public int numFives () { int result = 0; for (Node x = first; x != null; x = x.next) if (x.item == 5.0) result = result + 1; return result; }```

 Common mistakes: Does this work? [9/16]

 ``` 11 12 13 14 15 16 17 18 19 20 ``` ``` public int numFives () { Node x = first; int result = 0; while (x != null) { if (x.item == 5.0) result = result + 1; x = x.next; } return result; }```

 Common mistakes: Does this work? [10/16]

 ``` 11 12 13 14 15 16 17 18 19 20 ``` ``` public int numFives () { Node x = first; int result = 0; while (x != null) { if (x.item == 5.0) result = result + 1; x = x.next.next; } return result; }```

 Common mistakes: Does this work? [11/16]

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 ``` ``` public int numFives () { if (first == null) return 0; int result = 0; if (first.item == 5.0) result = result + 1; Node x = first; while (x.next != null) { if (x.next.item == 5.0) result = result + 1; x.next = x.next.next; } return result; }```

 Common mistakes: Does this work? [12/16]

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 ``` ``` public int numFives () { if (first == null) return 0; int result = 0; if (first.item == 5.0) result = result + 1; Node x = first; while (x.next != null) { if (x.next.item == 5.0) result = result + 1; x = x.next; } return result; }```

 Common mistakes: Does this work? [13/16]

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 ``` ``` public int numFives () { if (first == null) return 0; int result = 0; if (first.item == 5.0) result = result + 1; Node x = first; while (x.next != null) { if (x.item == 5.0) result = result + 1; x = x.next; } return result; }```

 Common mistakes: Does this work? [14/16]

 ``` 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ``` ``` public int numFives () { if (first.next == null) return 0; Node x = first; int result = 0; while (x.next != null) { if (x.item != 5.0) x = x.next; if (x.item == 5.0) { result = result + 1; x = x.next; } } if (x.next == null && x.item == 5.0) { result = result + 1; } return result; }```

 Common mistakes: Does this work? [15/16]

 ``` 11 12 13 14 15 16 17 18 19 20 21 ``` ``` public int numFives () { if (first == null) return 0; Node x = first; Node y = first.next; int result = 0; while (x != null) { if (x.item == 5.0) result = result + 1; x = y; } return result; }```

 numFives starter code with array [16/16]

 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 ``` ```package algs13; import java.text.DecimalFormat; import stdlib.*; public class Playground { private double a[]; private Node first; static class Node { public double item; public Node next; public Node (double item, Node next) { this.item = item; this.next = next; } } public int numFives () { return StdRandom.uniform (100); //TODO: fix this } /* ToString method to print */ public String toString () { // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes DecimalFormat format = new DecimalFormat ("#.###"); StringBuilder result = new StringBuilder ("[ "); for (Node x = first; x != null; x = x.next) { result.append (format.format (x.item)); result.append (" "); } result.append ("]"); return result.toString (); } /* Method to create lists */ public static Playground of(String s) { Playground result = new Playground (); if ("".equals (s)) { // special case for the empty array result.first = null; result.a = new double [0]; } else { String[] nums = s.split (" "); Node first = null; double[] a = new double[nums.length]; for (int i = nums.length-1; i >= 0; i--) { double num = Double.NaN; try { num = Double.parseDouble (nums[i]); } catch (NumberFormatException e) { throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"nums[i]\" as a double", s, nums[i])); } a[i] = num; first = new Node (num, first); } result.a = a; result.first = first; } return result; } public static void testNumFives (int expected, String sList) { Playground list = Playground.of (sList); int actual = list.numFives (); if (expected != actual) { StdOut.format ("Failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, list); } } public static void main (String[] args) { testNumFives (0, ""); testNumFives (1, "5"); testNumFives (0, "11"); testNumFives (3, "5 5 5"); testNumFives (0, "11 21 31 41"); testNumFives (1, "5 11 21 31 41"); testNumFives (1, "11 21 31 41 5"); testNumFives (1, "11 21 5 31 41"); testNumFives (5, "5 11 21 5 5 31 5 41 5"); StdOut.println ("Finished tests"); } public static void main1 (String[] args) { Trace.drawStepsOfMethod ("numFives"); Trace.drawStepsOfMethod ("numFivesH"); Trace.run (); Playground list0 = Playground.of ("5"); Playground list1 = Playground.of ("5 11 5 5"); int result = list1.numFives (); StdOut.println ("result: " + result); } }```

Revised: 2008/03/17 13:01