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

 Contents [0/17]

 Homework [1/17] Linked structures: Starter code [2/17] Linked structures: Optimistic loop [3/17] Linked structures: Cautious loop [4/17] Linked structures: Optimistic, forward recursion [5/17] Linked structures: Optimistic, backward recursion [6/17] Linked structures: Cautious, forward recursion [7/17] Linked structures: Cautious, backward recursion [8/17] Common mistakes: Does this work? [9/17] Common mistakes: Does this work? [10/17] Common mistakes: Does this work? [11/17] Common mistakes: Does this work? [12/17] Common mistakes: Does this work? [13/17] Common mistakes: Does this work? [14/17] Common mistakes: Does this work? [15/17] Common mistakes: Does this work? [16/17] numFives starter code with array [17/17]

 Homework [1/17]

• 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.

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

For [5,11,5,5], the loop values (lines 5 and 9) 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

 Linked structures: Optimistic, forward recursion [5/17]

 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: Optimistic, backward recursion [6/17]

 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: Cautious, forward recursion [7/17]

 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: Cautious, backward recursion [8/17]

 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? [9/17]

 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? [10/17]

 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? [11/17]

 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? [12/17]

 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? [13/17]

 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? [14/17]

 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? [15/17]

 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? [16/17]

 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 [17/17]

 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