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]

Linked structures: Starter code [2/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
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);
  }
}

Linked structures: Optimistic loop [3/17]

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.

numFivesLIO-

Linked structures: Cautious loop [4/17]

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
numFivesLIC-

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
numFivesLROF-

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
numFivesLROB-

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
numFivesLRCF-

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;
  }
numFivesLRCB-

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